Moving as a whole: multirobot traveling problem constrained by connectivity

Authors

YUN WANG
CHENG HU

DOI

10.3906/elk-1302-136

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

First Page

769

Last Page

788

Recommended Citation

WANG, YUN and HU, CHENG (2015) "Moving as a whole: multirobot traveling problem constrained by connectivity," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 23: No. 3, Article 11. https://doi.org/10.3906/elk-1302-136
Available at: https://journals.tubitak.gov.tr/elektrik/vol23/iss3/11