Miniature Robot Path Planning for Bridge Inspection: Min-Max Cycle Cover-Based Approach

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.