Home/Decentralized Multiple Mobile Depots Route Planning for Replenishing Persistent Surveillance Robots

Decentralized Multiple Mobile Depots Route Planning for Replenishing Persistent Surveillance Robots

Yifan Ding
Master's Thesis, Tech. Report, CMU-RI-TR-19-17, May, 2019

Download Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


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.

author = {Yifan Ding},
title = {Decentralized Multiple Mobile Depots Route Planning for Replenishing Persistent Surveillance Robots},
year = {2019},
month = {May},
school = {},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-19-17},
keywords = {Heuristics, Generalized Traveling Salesman Problem, Multi-robot planning},
} 2019-05-16T10:10:59-04:00