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.
Multiple traveling salesmen problem, multirobot system, global connectivity, nearest neighbor, bold Lin-Kernighan heuristic
WANG, YUN and HU, CHENG
"Moving as a whole: multirobot traveling problem constrained by connectivity,"
Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 23:
3, Article 11.
Available at: https://journals.tubitak.gov.tr/elektrik/vol23/iss3/11