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 according work in response robotics. 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.
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 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.
Constructor 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:
- robots exploring while being permanently connected to a fixed basestation [9.8MB]
- an example of a failed approach: an exploring robot pack being stuck after a while due to communication constraints [6.5MB]
- a successful algorithm using role changes: a robot pack recovering from a deadlock [5.1MB]
Publications
[1] S. Carpin, V. Jucikas, and A. Birk, “Multi-robot mapping for rescue robotics,” in Second IEEE International Workshop on Safety, Security, and Rescue Robotics (SSRR), Bonn, Germany, 2004. [Preprint PDF]
[2] M. Rooker and A. Birk, “Communicative Exploration in Dangerous Environments,” in Second International Workshop on Advances in Service Robotics (ASER’04), Stuttgart, Germany, 2004. [Preprint PDF]
[3] S. Carpin and A. Birk, “Stochastic map merging in rescue environments,” in RoboCup 2004: Robot Soccer World Cup VIII. vol. 3276, Springer, 2005, p. 483ff. https://doi.org/10.1007/978-3-540-32256-6_43 [Preprint PDF]
[4] S. Carpin, A. Birk, and V. Jucikas, “On Map Merging,” International Journal of Robotics and Autonomous Systems, vol. 53, pp. 1-14, 2005. https://doi.org/10.1016/j.robot.2005.07.001 [Preprint PDF]
[5] M. Rooker and A. Birk, “Combining Exploration and Ad-Hoc Networking in RoboCup Rescue,” in RoboCup 2004: Robot Soccer World Cup VIII. vol. 3276, Springer, 2005, pp. pp.236-246. https://doi.org/10.1007/978-3-540-32256-6_19 [Preprint PDF]
[6] A. Birk and S. Carpin, “Merging occupancy grid maps from multiple robots,” IEEE Proceedings, special issue on Multi-Robot Systems, vol. 94, pp. 1384-1397, 2006. https://doi.org/10.1109/JPROC.2006.876965 [Preprint PDF]
[7] M. Rooker and A. Birk, “Communicative Exploration with Robot Packs,” in {RoboCup} 2005: Robot Soccer World Cup IX. vol. 4020, Springer, 2006, pp. 267 – 278. https://doi.org/10.1007/11780519_24 [Preprint PDF]