Sector-Search with Rendezvous: Overcoming Communication Limitations in Multirobot Systems

Cooperative multirobot systems are advantageous in coverage applications such as surveillance, search and rescue, and hazardous waste cleanup. They can work in parallel and complete tasks faster than a single robot. If one robot fails, the other robots can continue with the task. In addition, if there is a dangerous mission, robots can be deployed instead of human teams to prevent human injuries and casualties. When multiple robots cooperate to complete a task, communication between robots can speed up completion. Communication can prevent robots from interfering with one another and reduce duplication in coverage. Typically, point-to-point communications can be used to coordinate robots. However, in many coverage tasks the efficiency of communications can be unpredictable due to unknown environmental characteristics and network conditions. Because persistent intrateam digital communications are not guaranteed, cooperation paradigms that do not rely upon message passing throughout exploration are needed. In previous work, the novel approach, Sector Search with Rendezvous, was proposed to overcome communication limitations. Robots explore an unknown environment in sectors, or designated areas, and periodically meet to communicate map information of what they have explored. Using simulations, it was compared to other communication paradigms. Preliminary results suggest that Sector Search with Rendezvous can serve as an alternative to continuous point-to-point communications. However, there can be discrepancies between results of simulation and physical experiments. In this paper, results from simulations and real robots experiments are discussed. Results suggest that Sector Search with Rendezvous is efficient in coordinating a team of robots. Introduction Communication in cooperative multirobot systems is essential. It can prevent duplicate coverage and reduce robot interference allowing for an increase in team performance. If the communication network is unrestricted, then robots can disperse in the environment, explore different areas, and continuously update each other of new information found. However, in scenarios that take place in unknown and unpredictable environments, such as bomb detection or search and rescue, the communications network is not always reliable or guaranteed. The efficacy of communications between robots is influenced by environmental configurations. Obstacles such as walls can interfere with communication transmissions. In addition, if robots are exchanging large amounts of data, then there is a risk of receiving incomplete information. Several researchers have implemented systems that do not require message passing to coordinate robots. Some systems make use of potential fields where robots attract and repel each other. Other approaches use ant or swarm robots where virtual pheromones or trail markings are placed in the environment to influence robot behavior. However, both approaches rely on local interactions where after a certain distance they can no longer coordinate. P ge 23056.2 Other researchers that consider message passing with communication network constraints include: an approach in which robots are required to maintain line-of-sight with other robots, an approach in which message size is reduced by allowing robots to communicate polygonal representations of the map, and an approach where rendezvous approaches allow robots to meet up to exchange information about the environment. However, there is limited research in multirobot rendezvous using physical experiments. In previous research, Sector Search with Rendezvous is presented as an approach to overcoming communication limitation. Instead of continuously passing messages throughout the entire exploration, robots explore in designated areas and rendezvous to communicate what was found. In simulation, team performance for when robots used the proposed approach was comparable to when robot communicated the entire time. However, simulation results can be inconsistent with real world results. In this paper, Sector Search with Rendezvous is investigated further on physical robots. It is compared to multirobot systems using a direct communication (message passing throughout exploration) approach in simulations and physical robot experiments. We hypothesize that Sector Search with Rendezvous can serve as an alternative to continuous point-to-point communications. Related Work Several researchers have investigated approaches that coordinate robot teams without communications. One approach makes use of potential fields. Howard et al. present a distributed virtual field force that attracts robots to targets and repels them from obstacles and other robots causing robots to spread out. However, this approach depends on local interactions, which after a certain distance robots no longer coordinate. Researchers also gather inspiration from social insects such as ants and swarms. Ferranti et al. present an approach were agents communicated indirectly by leaving information on tags deployed in the environment. They coordinate by reading and updating information on the tags. Similarly, Koenig demonstrate coordinating robots to cover a terrain similar to ants. Robots communicate via markings left by other robots and do not coordinate based on memory or maps. While these approaches do not rely on direct communications, they require local interaction to distribute robots. Some research focuses on the maintaining line-of-sight so that robots remain in communication range with each other. Rekleitis et al. address the implementation of coordinating robots when information sharing was restricted to line-of-sight communication in an unknown environment. In similar work, Arkin et al. investigated how a team of robots can self-organize during exploration by maintaining line-of-sight communications. Experiments involved robots searching for hazardous materials with varying degrees of prior knowledge. The line-of-sight approaches work well when there is a requirement for robot cohesiveness, but in general will not be as efficient in a large environment when a small number of robots have to spread out more to cover the environment. P ge 23056.3 Meier et al. present a technique for assigning targets to robots and deciding what information to transmit when using communication with limited bandwidth. Each robot explores an unknown environment and creates a polygonal approximation of a map. To reduce message sizes, polygonal representations of the map are communicated. Using their approach, they were able to effectively coordinate a team of robots under bandwidth limitations. Nevertheless, communicating polygonal representations of a map can result in an overhead of communication efforts. Approach Importance of Physical Experiments Simulations in multirobot research are used more often than real experiments . Simulations are beneficial because the resources and time it takes to acquire and maintain real robots can be expensive. In addition, simulations are a way to validate algorithms and predict robot behavior in the real world. However, typically in simulations, network and environmental conditions are optimized. Therefore, there can be discrepancies between simulations and physical robot experiments . The next step in this research is to validate the results from the simulation on physical robots. Real world results provide insight of important factors such as the environment, number of robots, and communication that can result in better or worse results in simulations. Figure 1: Robots disperse and search pre-agreed sectors. Since the environment is unknown, sectors are determined by using a semicircle to represent the environment. The arc of a semicircle is always 180°. If there are N robots, then sectors can be divided and robot will disperse 180°/N apart. Sector Search with Rendezvous Algorithm In Sector Search with Rendezvous, robots explore pre-agreed areas or sectors and periodically rendezvous to share information about what was found. Each robot performs frontier-based exploration in their sectors. Frontier-based exploration involves robots recursively exploring an unknown environment while building a map represented by an occupancy grid. Robots use a distance sensor to detect areas that are open, occupied, unknown, or a frontier. Frontier areas are the borders between open and unknown space. Robots explore frontier areas to expand their knowledge of the environment. As an asynchronous approach, robots select frontier areas based on individual utility allowing fault tolerance against individuals being disabled or out of range. When robots communicate, they only share information about open area. P ge 23056.4