The single robot line coverage problem: Theory, algorithms, and experiments
The single robot line coverage problem: Theory, algorithms, and experiments
复制标题
单机器人线路覆盖问题：理论、算法和实验
DOI：
10.1002/net.22171
复制
发表时间：
2023
期刊：
影响因子：
2.1
通讯作者：
Akella, Srinivas
中科院分区：
文献类型：
--
作者：
Agarwal, Saurav;Akella, Srinivas
线覆盖是服务于环境中给定的一组一维特征的任务。它对于道路网络、电力线路、石油和天然气管道等线性基础设施的检测非常重要。本文讨论了空中和地面机器人的单机器人线覆盖问题，将其建模为一个图上的优化问题。该问题属于广泛的一类弧路由问题，是密切相关的农村邮递员问题（RPP）的非对称图。本文提出了一个整数线性规划公式的正确性证明。使用最小费用流问题，我们开发的近似算法的解决方案的质量保证。这些保证也改善了现有的结果为非对称RPP。主算法根据需求图的结构将问题划分为三种情况，即由需要服务的特征所诱导的图。我们评估我们的算法在道路网络从50个人口最多的城市在世界上，由多达730个路段。该算法，增强了改进算法，在3秒内运行，并产生的解决方案是在10%的最佳。我们的实验证明我们的算法与商业无人机上的夏洛特夏洛特校园道路网络。
Line coverage is the task of servicing a given set of one‐dimensional features in an environment. It is important for the inspection of linear infrastructure such as road networks, power lines, and oil and gas pipelines. This paper addresses the single robot line coverage problem for aerial and ground robots by modeling it as an optimization problem on a graph. The problem belongs to the broad class of arc routing problems and is closely related to the rural postman problem (RPP) on asymmetric graphs. The paper presents an integer linear programming formulation with proofs of correctness. Using the minimum cost flow problem, we develop approximation algorithms with guarantees on the solution quality. These guarantees also improve the existing results for the asymmetric RPP. The main algorithm partitions the problem into three cases based on the structure of therequired graph, that is, the graph induced by the features that require servicing. We evaluate our algorithms on road networks from the 50 most populous cities in the world, consisting of up to 730 road segments. The algorithms, augmented with improvement heuristics, run within 3 s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs on the UNC Charlotte campus road network.
登录
查看更多内容
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Svensson O
通讯作者：
Svensson O
混合多风电容弧路由问题的参数化近似算法：理论与实验
影响因子：
2.1
作者：
R. van Bevern;C. Komusiewicz;und M. Sorge
通讯作者：
und M. Sorge
影响因子：
2.1
作者：
Vangelis Th. Paschos;Orestis Telelis;V. Zissimopoulos
通讯作者：
Vangelis Th. Paschos;Orestis Telelis;V. Zissimopoulos
混合邮差问题的3/2近似算法
DOI：
10.1137/s0895480197331454
发表时间：
1999
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Raghavachari;J. Veerasamy
通讯作者：
J. Veerasamy
DOI：
10.1007/978-3-030-66723-8_32
发表时间：
2021
期刊：
Algorithmic Foundations of Robotics XIV (WAFR 2020
影响因子：
--
作者：
Agarwal, Saurav;Akella, Srinivas
通讯作者：
Akella, Srinivas