|Title:||Robust and Efficient Covering of Unknown Continuous Domains with Simple, Ant-Like A(ge)nts
|Authors:||Eliyahu Osherovich, Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein
|Abstract:||We propose a new ``Mark-Ant-Walk'' algorithm for robust and efficient covering of continuous
domains by ant-like robots with very limited capabilities. The
robots can mark places visited with pheromone marks and sense the
level of the pheromone in their local neighborhood.
In case of multiple robots these pheromone marks can be sensed by all robots and
provide the only way of (indirect) communication between the robots.
The robots are assumed to be memoryless, and to have no information
besides that mentioned above.
Despite the robots' simplicity, we
show that they are able, by running a very simple rule of behavior,
to ensure efficient covering of arbitrary connected
domains, including non-planar and multidimensional ones. The novelty of our
algorithm lies in the fact that, unlike previously proposed methods,
our algorithm works on continuous domains without relying on some
``induced'' underlying graph, that effectively reduces the problem to a discrete
case of graph covering. In addition we demonstrate various benefits of our
successive visits of the robot at the same location, that makes it suitable for patrolling.
Finally we provide a new theoretical bound on covering time of a wide family of such mark and walk algorithms.
|Copyright||The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information|
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2007/CIS/CIS-2007-04), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CIS technical reports of 2007
To the main CS technical reports page
Computer science department, Technion