On the Complexity of the Multi-Robot, Multi-Depot Map Visitation Problem

This paper discusses the multi-robot, multi-depot Map Visitation Problem, a multi-robot inspection problem in which a team of robots originating from multiple home base depots must visit a collection of previously identified critical locations in a two-dimensional navigation environment. In its precise focus on location inspection, it is related yet complementary to other inspection or surveillance problems such as boundary coverage or patrol. In the paper, we analyze graph representations and an agent model appropriate for the Map Visitation Problem, and we present complexity results for a variety of categories of map structures, including lines, rings, trees, and general graphs. In addition to complexity results, we present an algorithm for the Map Visitation Problem on trees that is optimal for single-robot problems and a second algorithm that is provably within a factor of two of optimal for two robots inspecting arbitrary graphs.