Spanning tree based terrain coverage by multi robots in unknown environments

Abstract

Terrain Coverage algorithms have been studied in the robotics literature and other navigation tasks because of their numerous applications including vacuum cleaning, lawn mowing, harvesting, mine clearing, inspection and intrusion detection. There are several remarkable research attempts on Terrain Coverage based on genetic algorithms, spanning trees, exact cell decomposition, and spiral filling paths. This paper presents a novel simultaneous on-line coverage strategy for multi robots, which is structured and assures complete and robust coverage of the surface regardless of the shape of the unknown environment. In particular, we study ant-robots and how they can cover terrain by leaving markings in the terrain, similar to what ants do. These markings can be sensed by all robots and allow them to cover the unknown terrain without direct communication with each other. A real-time heuristic search method is used to implement ant-robots and simulation results for simultaneous online terrain coverage are presented.