Technical Report CIS9814

Title: MAC vs. PC - Determinism and Randomness as Complementary Approaches to Robotic Exploration of Continuous Unknown Domains
Authors: Israel A. Wagner, Michael Lindenbaum and Alfred M. Bruckstein
Abstract: Two methods are described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. We formalize the problem and show a lower bound on the length of any solution. A deterministic "mark and cover" (MAC) algorithm is then described to solve the problem using short-lived navigational markers as means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A/a), A being the total area and a - the area covered by the robot in a single step. The MAC algorithm is tested against an alternative randomized "probabilistic covering" (PC) method, which does not rely on sensors but is still able to cover an unknown region in an expected time that depends polynomially on the dimensions of the region. Both algorithms enable cooperation of several robots to achieve faster covergae. Finally we show that the two methods can be combined to yield a third, hybrid algorithm with a better tradeoff between performance and robustness.
CopyrightThe 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 (, 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 1998
To the main CS technical reports page

Computer science department, Technion