Multi-robot system provides more advantages over a single robot. In certain situations, robots need to maintain global connectivity while proceeding tasks such as traveling some interested spots in an area. This paper formulates the
Multi-Robot Traveling Problem Constrained by Connectivity
, and proposes a
Connected Nearest Neighbor
solution aiming to minimize the total traveling distance of the robots, which performs nearly twice better than previous work. Additionally, it is load balancing, fast in response, and robust to environmental dynamics and robot failures. Further improvements of the solution are also discussed and developed. Simulations are designed to investigate the cost of maintaining connectivity, the influence of different environments, and the comparison among the algorithms.