The multi-robot coverage path-planning problem involves finding collision-free paths for a set of robots so that they can completely cover the surface of an environment. This problem is non-trivial as the geometry and location of obstacles in the environment is usually not known a priori by the robots, and they have to adapt their coverage path as they discover obstacles while moving in the environment. Additionally, the robots have to avoid repeated coverage of the same region by each other to reduce the coverage time and energy expended. This chapter discusses the research results in developing multi-robot coverage path planning techniques using mini-robots that are coordinated to move in formation. The authors present theoretical and experimental results of the proposed approach using e-puck mini-robots. Finally, they discuss some preliminary results to lay the foundation of future research for improved coverage path planning using coalition game-based, structured, robot team reconfiguration techniques.
TopIntroduction
Automated exploration of an unknown environment using a multi-robot system is an important topic within robotics that is relevant in several applications of robotic systems. These applications include automated reconnaissance and surveillance operations, automated inspection of engineering structures, and even domestic applications such as automated lawn mowing and vacuum cleaning. An integral part of robotic exploration is coverage path planning - how to enable robots to cover an initially unknown environment using a distributed terrain or area coverage algorithm. The coverage algorithm should ensure that every portion of the environment is covered by the coverage sensor or tool of at least one robot. Simultaneously, to ensure that the coverage is efficient, the coverage algorithm should prevent robots from repeatedly covering the same regions that have already been covered by themselves or by other robots. In most of the current multi-robot area coverage techniques, each robot performs and coordinates its motion individually. While individual coverage has shown promising results in many domains, there are a significant number of scenarios for multi-robot exploration such as extra-terrestrial exploration, robotic demining, unmanned search and rescue, etc., where the system can perform more efficiently if multiple robots with different types of sensors or redundant arrays of sensors can remain together as single or multiple cohesive teams (Cassinis, 2000; Chien et al., 2005; De Mot, 2005). For example, in the domain of robotic demining (Bloch, Milisavljevc & Acheroy, 2007), where autonomous robots are used to detect buried landmines, the incidence of false positive readings from underground landmines can be significantly reduced if robots with different types of sensors such as ground penetrating radar (GPR), IR (infra-red) sensors and metal detectors are able to simultaneously analyze the signals from potential landmines. In such a scenario, it would benefit if robots, each provided with one of these sensors, are able to explore the environment while maneuvering themselves together as a team. Multi-robot formation control techniques provide a suitable mechanism to build teams of robots that maintain and dynamically reconfigure their formation, while avoiding obstacles along their path (Mastellone, Stipanovic, Graunke, Intlekofer & Spong, 2008; Olfati Saber, 2006; Smith, Egerstedt & Howard, 2009). However, these techniques are not principally concerned with issues related to area coverage and coverage efficiency. To address this deficit, in this paper, we investigate whether multi-robot formation control techniques and multi-robot area coverage techniques can be integrated effectively to improve the efficiency of the area coverage operation in an unknown environment by maintaining teams of multiple robots.