Moving as a whole: multirobot traveling problem constrained by connectivity

Authors: YUN WANG, CHENG HU

Abstract: A multirobot system provides many advantages over a single robot. In certain situations, robots need to maintain global connectivity while proceeding through tasks such as traveling to spots of interest in an area. This paper formulates the problem of multiple robots traveling while constrained by connectivity and analyzes the limits of increase in total traveling distance (TTD) caused by connectivity constraints. A connection condition is proposed and proven, which can be used to direct the design of solutions. Two algorithms satisfying the connection condition, connected nearest neighbor (CNN) and bold Lin-Kernighan heuristic (B-LKH), are proposed to solve this problem, which consider the connectivity constraint in planning paths. Simulations are designed to investigate the influence of important parameters, and comprehensive comparisons among algorithms are also conducted. The results show that CNN and B-LKH significantly outperform previous systems with respect to TTD.

Keywords: Multiple traveling salesmen problem, multirobot system, global connectivity, nearest neighbor, bold Lin-Kernighan heuristic

Full Text: PDF