Decentralized Multiple Mobile Depots Route Planning for Replenishing Persistent Surveillance Robots

Abstract

Persistent surveillance of a target space using multiple robots has numerous applications. The continuous operation in these applications is challenged by limited onboard battery capacity of the persistent robots. We consider the problem for replenishing persistent robots using mobile depots, where mobile depots collectively compute a set of tours to drop off batteries for replenishing all persistent robots with the minimum total cost. Compared to other works, persistent robots are not required to detour for recharging or battery swapping. We formulate this problem as generalized multiple depots traveling salesman problem (GMDTSP) on a complete graph. An efficient centralized heuristic-based algorithm Multiple Depots Random Select (MDRS) is proposed, which has been proved to have an analytical constant upper bound in the worst case scenario. To provide scalability and robustness, a fully decentralized asynchronous MDRS (dec-MDRS) is proposed, with the analysis of its correctness and efficiency. We also propose a post-processing heuristic (MDRS-IM) to improve the solution quality. We demonstrate the efficiency and effectiveness of our algorithm via benchmark on multiple instances from TSPLIB and GTSPLIB. The simulation results show that the complexity of dec-MDRS grows linearly as the number of robots increases. The simulation also shows that MDRS and MDRS-IM perform significantly faster than the state of the art heuristic solver LKH with only a loss of about 10% of solution quality.