///Yifan Ding – MSR Thesis Talk
Loading Events
This event has passed.

MSR Speaking Qualifier


Yifan Ding MSR Student Robotics Institute,
Carnegie Mellon University
Friday, April 26
3:00 pm
- 4:30 pm
Newell-Simon Hall 4305
Yifan Ding – MSR Thesis Talk

Title: Decentralized Multiple Mobile Depots Route Planning for Replenishing Persistent Surveillance Robots



Persistent surveillance of a target space using multiple robots has numerous applications. The continuous operation in these applications is challenged by the 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.



Katia Sycara (advisor)

Maxim Likhachev

Wenhao Luo