论文标题
单个机器人线覆盖范围问题：理论，算法和实验
The Single Robot Line Coverage Problem: Theory, Algorithms, and Experiments
论文作者
论文摘要
线路覆盖范围是在环境中为给定的一组一维功能提供服务的任务。这对于检查线性基础设施（例如道路网络，电力线以及石油和天然气管道）很重要。本文通过将其作为图表上的优化问题进行建模来解决空中机器人和地面机器人的单个机器人线覆盖率问题。该问题属于广泛的ARC路由问题，与不对称图上的农村邮政问题（RPP）密切相关。本文提供了一个整数线性编程公式，并提供了正确性的证明。使用最低成本流问题，我们开发近似算法，并保证解决方案质量。这些保证还改善了不对称RPP的现有结果。主要算法将问题分为三种情况，这些情况基于所需图的结构，即由需要维修的特征引起的图形。我们在世界上50个人口最多的城市中评估了我们在道路网络上的算法，其中包括多达730条路段。通过改进的启发式方法增强，该算法在3s内运行，并生成最佳最佳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 the required graph, i.e., 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 3s and generate solutions that are within 10% of the optimum. We experimentally demonstrate our algorithms with commercial UAVs.
