Approximation Algorithms for the Single Robot Line Coverage Problem
Approximation Algorithms for the Single Robot Line Coverage Problem
复制标题
单机器人线路覆盖问题的近似算法
DOI：
10.1007/978-3-030-66723-8_32
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Akella, Srinivas
中科院分区：
文献类型：
--
作者：
Agarwal, Saurav;Akella, Srinivas
线覆盖问题是指在一个环境中为一组给定的一维要素提供服务的任务。它的应用包括公路网、电力线和石油和天然气线路的检查。线覆盖问题是标准弧布线问题的推广，一般是NP难问题。我们解决了单个机器人生产线的复盖问题，其中服务成本和空头成本是不同的和不对称的。我们将该问题建模为最小化给定图上的总旅行成本的优化问题。利用最小费用流问题，我们给出了有效获得有界解的近似算法。我们通过考虑三个更简单的子问题来分阶段构建主算法。子问题基于等效图的结构，即由需要服务的特征所诱导的图。对于欧拉图只需要边的情况，我们首先给出了一个最优算法。接下来，我们考虑一般的图，不一定是欧拉图，只有所需的边，并给出一个2-近似算法。最后，我们考虑了同时具有必需边和非必需边的一般情况。该近似算法依赖于非对称旅行商问题(ATSP)，并且有界于其中有连通分支的ATSP算法的逼近因子。我们的上界也是对非对称农村邮递员问题已有结果的改进。
The line coverage problem is the task ofservicinga given set of one-dimensional features in an environment. Its applications include the inspection of road networks, power lines, and oil and gas lines. The line coverage problem is a generalization of the standard arc routing problems, and is NP-hard in general. We address the single robot line coverage problem where the service and deadhead costs are distinct and asymmetric. We model the problem as an optimization problem that minimizes the total cost of travel on a given graph. We present approximation algorithms to obtain bounded solutions efficiently, using the minimum cost flow problem. We build the main algorithm in stages by considering three simpler subproblems. The subproblems are based on the structure of therequired graph, i.e., the graph induced by the features that require servicing. We first present an optimal algorithm for the case of Eulerian graphs with onlyrequirededges. Next we consider general graphs, not necessarily Eulerian, with only required edges and present a 2-approximation algorithm. Finally, we consider the general case with both required and non-required edges. The approximation algorithm is dependent on the Asymmetric Traveling Salesperson Problem (ATSP), and is bounded by, whereis the approximation factor of the ATSP algorithm withCconnected components. Our upper bound is also an improvement over the existing results for the asymmetric rural postman problem.
登录
查看更多内容
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Svensson O
通讯作者：
Svensson O
混合多风电容弧路由问题的参数化近似算法：理论与实验
影响因子：
2.1
作者：
R. van Bevern;C. Komusiewicz;und M. Sorge
通讯作者：
und M. Sorge
多个机器人的线路覆盖
DOI：
10.1109/icra40945.2020.9197292
发表时间：
2020
期刊：
IEEE International Conference on Robotics and Automation
影响因子：
--
作者：
Agarwal, Saurav;Akella, Srinivas
通讯作者：
Akella, Srinivas
影响因子：
2.7
作者：
Z. Win
通讯作者：
Z. Win
DOI：
--
发表时间：
2011
期刊：
IEEE International Conference on Robotics and Automation
影响因子：
--
作者：
Ling Xu;A. Stentz
通讯作者：
A. Stentz