Use of genetic algorithms for target distribution and sequencing in multiple robot operations

摘要

In this paper we propose a solution for the Multiple Traveling Salesman Problem applied to mobile robotics. A team of mobile robots (travelers) must visit a set of target locations, minimizing the time to visit all of them. Initially the targets are not distributed among the robots, but they are assigned to the team as a whole. A subset of points and its visiting order (sequence) must be assigned to each robot, minimizing the total length of the routes and the completion time of the global task (maximum path lenght). Using a genetic algorithm we compute a fast, robust, and efficient solution to this problem. The genetic algorithm is described in detail and a comprehensive experimental analysis of the proposed solution is presented, characterizing the genetic algorithm and supporting its applicability.