Efficient and inefficient ant coverage methods

Ant robots ale simple creatures with limited sensing and computational capa bilities. They have the advantage that they are easy to program and cheap t o build. This makes it feasible to deploy groups of ant robots and take adv antage of the resulting fault tolerance and parallelism. We study, both the oretically and in simulation, the behavior of ant robots for one-time or re peated coverage of tel-rain, as required for lawn mowing, mine sweeping, an d surveillance. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. To overcome these lim itations, we study navigation methods that are based on real-time (heuristi c) search and leave markings in the terrain, similar to what real ants do. These markings can be sensed by all ant robots and allow them to cover terr ain even if they do not communicate with each other except via the markings , do not have any kind of memory, do not know the terrain, cannot maintain maps of the terrain, nor plan complete paths. The ant robots do not even ne ed to be localized, which completely eliminates solving difficult and time- consuming localization problems. We study two simple real-time search metho ds that differ only in how the markings ale updated. We show experimentally that both real-time search methods robustly cover terrain even if the ant robots are moved without realizing this (say, by people running into them), some ant robots fail, and some markings get destroyed. Both real-time sear ch methods are algorithmically similar, and our experimental results indica te that their cover time is similar in some terrains. Our analysis is there fore surprising. We show that the cover time of ant robots that use one of the real-time search methods is guaranteed to be polynomial in the number o f locations, whereas the cover time of ant robots that use the other real-t ime search method can be exponential in (the square root on the number of) locations even in simple terrains that correspond to (planar) undirected tr ees.