Restricted Communication in Online Multi-Robot Exploration

1 Introduction

Our primary contributions are two distributed algorithms for exploration using small teams of robots. The innovation in these algorithms comes from how the robots disperse into and subsequently explore the environment, even with communication restrictions. We provide proofs that the algorithms will achieve full coverage of the environment and return all functioning robots to the entry point upon completion. We demonstrate the algorithms' functionality using simulations and experiments using physical robots. We also provide comparisons to similar coverage algorithms, and developed two small extensions to our primary algorithm which perform on par with the comparison algorithms even with our communication restrictions.

Exploring unknown environments can take many forms, from the depths of the oceans to cave networks to the rubble after a disaster. In each case, there is an element of danger to humans conducting the exploration, so we seek to employ robots to explore for us. This brings its own set of challenges, particularly in the realm of communication, both between the robots and the human operators, and between the robots themselves, in the case of multi-robot systems. For a single robot, exploration is a well covered problem, including constraints on sensor ranges, cluttered or open environments, and ground or aerial robots [Brass et al., 2011], particularly with consideration for search and rescue [Murphy, 2014]. Several aspects of multi-robot systems for exploration are also well covered [Galceran and Carreras, 2013], but there are still gaps, particularly in transitioning from simulation to applications tested in the real world.

The primary reason to switch from single robots to multiple robots is the scale of the environment, especially for search and rescue, where it is critical that the search be completed as quickly as possible, to aid in saving lives. The larger the environment is, the less likely it is that a single robot can cover enough area in a short enough time to make a significant contribution to the search efforts. This has led to the use of multiple robots, but that switch results in a second challenge. Controlling and coordinating the robots requires additional communication, between the robots themselves and with the human operators. However, normal means of communication are often overloaded or limited in the aftermath of a disaster [Rooker and Birk, 2007]. Consequently, we focused on developing distributed algorithms for multi-robot exploration that provide complete coverage with limited communication.

2 Communication-Restricted Exploration

In developing our algorithms, we wanted to accommodate restricted communication, but also be able to provide full coverage guarantees. We require that each robot in the team always be in communication with at least one other robot. This requirement also helps us ensure that the robots do not get stranded in the environment, and that no reachable areas are overlooked. We do assume that the robots have the ability to avoid collisions, communicate with each other and beacons, and can carry and deposit beacons. Beacons mark the entrance, intersections, the paths to the frontier, and provide blocks to explored areas to prevent repeated coverage. We then developed two distributed algorithms with different levels of communication restrictions.

In the Rolling Dispersion Algorithm (RDA) [Jensen and Gini, 2013], the robots initially disperse as far apart as their communication range will allow. When no robots can explore further without breaking communication with the group, the algorithm switches to a Depth-First-Search (DFS) approach, fully exploring a path before moving to other paths. We are able to provide guarantees that the robots will complete coverage and return to the entrance, so long as at least one robot remains functional, due to the connectivity and beacon use.

The Sweep Exploration Algorithm (SEA), while based on RDA, uses a much more limited form of communication, such as line-of-sight color codes or chemical signals. These modes led us to reduce what was being communicated to 8 messages that conveyed only a robot's state to its immediate neighbors. From this, we restricted the robots to only one moving robot at a time, to avoid flooding the environment with messages. Thus there is no dispersion stage, just the DFS exploration of each path to its completion, using RDA's exploration and retraction method. We have shown that SEA uses the minimum number of distinct message types in order to provide the full coverage guarantee and return the robots to the entrance upon completion [Jensen et al., 2016].

While both algorithms can provide full coverage guarantees, they are both slow to complete the exploration. In comparing with other algorithms, particularly those developed for online coverage, but without communication restrictions, we saw ways to modify the RDA algorithm to improve the coverage time without sacrificing the full coverage guarantee.

The first modification, RDA-EC (extended communication), doubles the range between robots. We based this on behavior we saw in the Multi-Robot Depth-First-Search (MRDFS) algorithm [Brass et al., 2011], which leaves beacons in the environment, but only at intersections, and no communication is used between intersections. This allows the MRDFS robots to move further apart, but also leads to redundant coverage and longer return times.

Our second modification, RDA-MS (multi-start) starts the robots in multiple locations, but as separate teams, which lets the robots move without having to avoid collisions with as many other robots at the start. This change was based on the BoB algorithm [Viet et al., 2015], which uses boustrophedon motion planning to explore and Greedy A* backtracking to find new frontiers to explore. BoB requires global communication and map making, and starts the robots in separate locations, reducing interference at the start.

3 Experiments and Results

We have completed experiments in simulation and on physical robots for both algorithms and extensions. We used multiple structured and unstructured environments in simulation, and structured indoor environments for physical robot experiments. We compared our algorithms with other online coverage algorithms in simulation. Rate of coverage for a complex indoor environment with multiple loops is shown in Figure 1.

Our extension, RDA-EC, is able to match performance with MR-DFS, and has shorter paths overall. RDA-MS performs on par with BoB, even with the communication restrictions.

4 Conclusions and FutureWork

We have developed two novel distributed algorithms (as well as two modified versions) for online multi-robot coverage, with guaranteed full coverage even with communication restrictions. We show performance and compare against similar algorithms in both simulation and physical robot experiments. Future work will involve larger and more complex environments.