RI: Small: Network Formation for Multi-Robot Systems

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Many multi-robot tasks, which arise in search-and-rescue, environmental monitoring and similar applications, require the robots to communicate with one another. In contrast to most current work, where the robots are deployed in controlled settings and are guaranteed to be connected, as multi-robot systems get deployed in real-world applications, they will often lose connectivity due to navigation errors, communication failures, or planned movements into communications-denied areas. When this happens, the robots need a systematic and efficient way to reconnect into a network. This project studies the theoretical question of how should the robots move so that they can quickly form a network. Network formation generalizes a number of fundamental problems (e.g. rendezvous search, freeze tag, minimizing movement) that have been studied in relatively simple settings by disjointed groups of communities. This work attempts to introduce a unified treatment and address aspects relevant to robotics applications, such as the presence of obstacles and sensing limitations. The proposed work will study three variants of network formation for a number of practically relevant environment models. The first two variants are based on the information available to the robots (e.g., whether the initial locations are known). The third variant will introduce novel network formation problems in which a team of heterogeneous vehicles with different motion capabilities (e.g. ground robots on a terrain and aerial vehicles flying over them) try to form a network. These variants are formulated as novel-optimization problems whose solutions will provide efficient network-formation strategies with provable performance guarantees. Results will be evaluated in simulation and field applications with ground-ground and ground-air vehicle teams.