Multi-Robot Coverage and Planetary exploration

By Ioannis Rekleitis, Canadian Space Agency

In this talk, I will discuss two problems: multi-robot coverage, and planetary exploration. The task of covering the free space is common to many applications. Automated humanitarian de-mining, lawn mowing, and vacuum cleaning all require the robot to pass an end-effector over a designated area. Many of those applications require complete coverage, that is, a guarantee that no area is left uncovered. Employing multiple robots improves the efficiency and robustness of the process at the cost of increased complexity. In this talk, I will introduce a variety of covering algorithms that differ in the communication capabilities of the robots. Our approach is based on a single robot complete coverage algorithm. For the first algorithm, the robots operate under the restriction that communication between two robots is available only when they are within line of sight of each other. While for the other two algorithms, the robots are distributed through space and communication is available without any restrictions. As the robots cover an unknown area with obstacles, producing an optimal algorithm is impossible. Even for a known environment, the problem is NP-hard. When communication is unrestricted, an auction mechanism is used to improve the performance.
When communication is limited, the robots follow a completely deterministic algorithm that ensures the robots do not cover the same area repeatedly. Experiments from simulated environments together with results from real robots are going to be presented.

In the second part of the talk, I will present work done currently at the Canadian Space Agency: in particular, our approach to planetary exploration together with the challenges we face.Our objective is autonomous over-the-horizon navigation using a laser based vision sensor. With the term over-the-horizon, we mean locations beyond the sensor's reach. Central to our efforts is the task of developing the autonomous capabilities of space robotic systems and in particular of planetary rovers. In order for a rover to be fully autonomous it has to be able to sense its environment, reason about the terrain it faces, plan a path, and navigate safely along the planned trajectory. In order to avoid the problems of harsh lighting conditions and to produce scientific valuable topographical maps in medium scale, we have selected the use of a laser based vision sensor. In this part of the talk I am going to present our first successful semi-autonomous experiments in over-the-horizon navigation in CSA's Mars-like terrain.

Ioannis Rekleitis is currently at the Canadian Space Agency. Between 2002 and 2003, he was a Postdoctoral Fellow at the Carnegie Mellon University in the Sensor Based Planning Lab with Professor Howie Choset. He was granted his Ph.D. from the School of Computer Science, McGill University, Montreal, Quebec, Canada in 2002 under the supervision of Professors Gregory Dudek and Evangelos Milios. Thesis title: "Cooperative Localization and Multi-Robot Exploration". He finished his M.Sc. in McGill University in the field of Computer Vision in 1995. He was granted his B.Sc. in 1991 from the Department of Informatics, University of Athens, Greece. His Research has focused on mobile robotics and in particular in the area of cooperating intelligent agents with application to multi-robot cooperative localization, mapping, exploration and coverage. His interests extend to computer vision and sensor networks.

Click here to go to the LCI Forum page