Michael Lindenbaum, Department of Computer Science, Technion City, Haifa 32000, Israel
Email: mic@cs.technion.ac.il
Alfred M. Bruckstein, Department of
Computer Science, Technion City, Haifa 32000, Israel
Email: freddy@cs.technion.ac.il
An ant-inspired method is described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. Such a method has applications in robotics where a robot with limited sensing capabilities but with the ability to leave marks on the ground has to cover a closed region for purposes of cleaning a dirty floor, painting a wall, or demining a mine-field. We formalize the problem and suggest the "Mark And Cover" (MAC) rule of motion to solve it using temporary markers (``pheromones'') 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.