Multi-Robot-Teams: Cooperative Mapping and Exploration

Background

Multi-robot-teams are beneficial for many application domains as a group of robots can do many tasks much more robustly and much more efficiently than a single robot. A particular good example is the field of Safety, Security and Rescue Robotics (SSRR) as demonstrated with the Jacobs rescue robots. Especially reconnaissance missions, e.g. the search for victims in a rescue scenario, can profit from several robots operating in parallel. But achieving proper cooperation is non-trivial as illustrated by the following examples of contributions by Jacobs Robotics.

 

Map Merging

Mapping can potentially be speeded up in a significant way by using multiple robots exploring different parts of the environment. But the core question of multi-robot mapping is how to integrate the data of the different robots into a single global map. A significant amount of research exists in the area of multirobot-mapping that deals with techniques to estimate the relative robots poses at the start or during the mapping process. With map merging the robots in contrast individually build local maps without any knowledge about their relative positions. The goal is then to identify regions of overlap at which the local maps can be joined together. A concrete approach to this idea was developed by Jacobs Robotics in form of a special similarity metric and a stochastic search algorithm. Given two maps m and m', the search algorithm transforms m' by rotations and translations to find a maximum overlap between m and m'. In doing so, the heuristic similarity metric guides the search algorithm toward optimal solutions.

 

Cooperative Exploration

A popular basis for robot exploration is the frontier-based exploration algorithm introduced by Yamauchi in 1997. In this algorithm, the frontier is defined as the collection of regions on the boundary between open and unexplored space. A robot moves to the nearest frontier, which is the nearest unknown area. By moving to the frontier, the robot explores new parts of the environment. This new explored region is added to the map that is created during the exploration. Obviously, multi-robot systems are a very interesting option for exploration as they can lead to a significant speed-up and increased robustness. There are several possibilities to extent the frontier based algorithm to a multi robot version. First of all, there is the option to use the most straightforward extension; namely to let the robots run individually and to simply fuse their data in a global map. Each robot then simply moves to its nearest frontier cell.

More sophisticated versions try to coordinate the different robots such that they do not tend to move toward the same frontier cell. One can for example use a utility that incorporates the cost of moving to the frontiers and that discounts situations where two or more robots approach the same frontier region. An other often neglected problem for multi-robot exploration is that the robots need to exchange data. But when it comes to real multi-robot systems, communication relies on wireless networks typically based on the IEEE 802.11 family of standards, which is also known as WLAN technology, or some alternative RF technology. RF links suffer from various limitations. Especially, they have a limited range. At least, not every robot has to be within the range of each others transceiver. When using ad-hoc networking, the underlying dynamic routing can be employed to transport data via several hops of robots that are in mutual contact to bridge longer distances.

Jacobs Robotics has developed an extension of frontier based exploration, which takes constraints on the exploration like limited range of radio links into account. This algorithm is based on a utility function, which weights the benefits of exploring unknown territory versus the goal of not violating the constraints like keeping communication intact.

The following videos show how the algorithm keeps exploring robots within the limits of their radio links: