论文标题
桥梁检查的微型机器人路径计划：最小最大周期盖的方法
Miniature Robot Path Planning for Bridge Inspection: Min-Max Cycle Cover-Based Approach
论文作者
论文摘要
我们研究计划一组移动机器人的部署的问题。尽管问题和公式可用于许多不同的问题，但在这里，我们将桥梁检查作为启发性应用。这些机器人最初驻扎在整个桥梁的一组仓库中。然后将每个机器人分配在桥上进行检查的一组站点，并且完成后，必须返回将其存储的仓库返回。 机器人计划的问题被提出为根系的最小最大周期盖问题，其中顶点集由要检查的站点和机器人仓库组成，并且边缘的重量捕获了（i）从一端顶点到另一个顶点到另一个顶点或（ii）旅行的必要能量支出所需的时间。在第一种情况下，目标函数是总检查时间，而在后一种情况下，它是所有已部署的机器人之间的最大能量消耗。我们提出了一种近似值$ 5 +ε$的新颖算法，其中$ 0 <ε<1 $。此外，提出的算法的计算复杂性被证明为$ o \ big（n^2+2^{m-1} n \ log（n+k）\ big）$，其中$ n $是顶点的数量，而$ m $是仓库的数量。
We study the problem of planning the deployments of a group of mobile robots. While the problem and formulation can be used for many different problems, here we use a bridge inspection as the motivating application for the purpose of exposition. The robots are initially stationed at a set of depots placed throughout the bridge. Each robot is then assigned a set of sites on the bridge to inspect and, upon completion, must return to the same depot where it is stored. The problem of robot planning is formulated as a rooted min-max cycle cover problem, in which the vertex set consists of the sites to be inspected and robot depots, and the weight of an edge captures either (i) the amount of time needed to travel from one end vertex to the other vertex or (ii) the necessary energy expenditure for the travel. In the first case, the objective function is the total inspection time, whereas in the latter case, it is the maximum energy expenditure among all deployed robots. We propose a novel algorithm with approximation ratio of $5 + ε$, where $0<ε<1$. In addition, the computational complexity of the proposed algorithm is shown to be $O\big( n^2+2^{m-1} n \log(n+k) \big)$, where $n$ is the number of vertices, and $m$ is the number of depots.
