Move and improve: A distributed multi-robot coordination approach for multiple depots multiple travelling salesmen problem

The multiple depot multiple travel salesman problem (MD-MTSP) is a common research problem in several mobile robots applications. The problem is known to be NP-hard and centralized solutions are computation intensive and are not suitable for mobile robots applications, in particular for large instances. In this paper, we propose a new market-based multi-robot coordination technique, called move and improve. The concept is simple: in each step of our algorithm, a robot moves and attempts to improve its solution by coordination with its neighbor robots. Our approach consists of four main steps: (1) initial target allocation, (2) tour construction, (3) negotiation of conflicting targets, (4) solution improvement. Several extensive simulations are conducted and our approach is compared against a centralized Genetic Algorithm (GA) MD-MTSP solver in terms of optimality. We demonstrate that our solution outperforms the centralized GA approach.