On the complexity of the multi-robot, multi-depot map visitation problem
This paper discusses the multi-robot, multidepot 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.
|Keywords||algorithm, complexity, graph, inspection, map visitation, NP-Complete|
|Conference||8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011|
Aaron, E. (Eric), Kranakis, E, & Krizanc, D. (Danny). (2011). On the complexity of the multi-robot, multi-depot map visitation problem. Presented at the 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems, MASS 2011. doi:10.1109/MASS.2011.90