Abstract

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.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.