Open Problem: Analyzing Ant Robot Coverage

Abstract

Ant robots can repeatedly and robustly cover terrain by always moving away from the trails that they leave in the terrain. This coverage strategy can be modeled with graph traversal strategies similar to real-time search methods (such as Learning Real-Time A*) and reinforcement learning methods (such as Real-Time Dynamic Programming). The resulting worst-case cover times are known to be exponential in the number of vertices on both directed and undirected graphs in general. The known undirected graphs with large worst-case cover times have unbounded degree vertices. However, existing ant robots navigate on grids, a special case of undirected planar graphs with bounded degree vertices. Their experimental cover times appear to scale almost identically to those of coverage strategies with polynomial worst-case cover times. However, it is an open problem to prove whether the resulting worst-case cover times on grids are indeed polynomial in the number of vertices. Ant robots are robots that either 1) leave trails in the terrain and use them for navigation, similar to learning graphs by dropping indistinguishable pebbles (Bender et al., 2002), and/or 2) use greedy navigation strategies that depend only on local observations of the terrain and thus require only limited sensing, processing and communication capabilities (Wagner & Bruckstein, 2001). Researchers have built actual ant robots that