RI: Small: Network Formation for Multi-Robot Systems

Consider robots dispersed over a large area. Each robot has a fixed communication radius. How should the robots move so as to form a connected network as quickly as possible? We study this network formation problem for robots deployed uniformly at random over an open field.

When a group of robots collect data from an unknown environment, it is often desirable to have the robots meet each other regularly and share the data they gathered. Robots equipped with long-range communication instruments are generally capable of transmitting coordinate information to all over the team members. However, to share a large amount of data such as photos or videos, due to high bandwidth requirements the connectivity range is typically relatively short, and robots need to come closer to each other for a stable data transfer.

To address this issue of connectivity, we study the offline connectivity problem where the robot locations are known to each other at all times. This problem is relevant for our UAV network (see the video below) where each robot is equipped with both XBee and WiFi modems. XBee has much longer range but lower bandwidth then WiFi. Therefore, the robots can communicate their locations over the XBee network but may need to form a WiFi network to exchange large amounts of data such as images. We present a field experiment which demonstrates this capability.

We also introduce the online version of the problem in which the robot locations are unknown to each other. This version of the problem is relevant when there are failures in the communication infrastructure, or the robots are too far from each other to coordinate.

We present algorithms for both of the cases of the connectivity problem, and demonstrate their performances through simulations and outdoor experiments.

Year 1:

In the first year of the project, we focused on a stochastic version of connectivity maintenance where the robots are deployed uniformly at random over a square.

Given a configuration of n robots with initial positions X = {x₁, ..., x_n} on the plane, and a connectivity radius r, the goal is to compute final positions of all the robots such that their positions form a connected communication network.

Suppose G(X,r) is a subgraph of the complete graph on X including all edges with length less than or equal to r. If l is the smallest distance such that G(X,l) is connected, then we have a solution at most O(diam(G(X,l)) × l/(l-r)) times worse than the optimal solution at the worst case in the offline version of the problem.

In the average case, when n robots are deployed in an L × L area, the maximum movement of our algorithm is at most O(√(n/lnL)) times worse than that of the optimal strategy.

In an idealized grid case for the online version, the maximum movement of our algorithm is a constant factor of L³ / nr² .

Year 2:

For the majority of this year, we worked on the offline connectivity problem where the goal is to establish the connectivity of the robots (with known initial locations) as quickly as possible. The robots exchange their coordinates over large distances using a long range device, but they need to form a connected network for a high-bandwidth mode which has a shorter range. For this problem we introduced an approximation algorithm for the case when the robot initial positions are chosen uniformly at random. This result was presented by Ph.D. student Selim Engin at the 28th International Conference on Automated Planning and Scheduling (ICAPS) in June.

During the summer, we studied an asynchronous variant of this problem known as the freeze-tag problem. In this version, only one robot is initially active. When it finds other robots, it can wake them up. Those robots can then participate in the connectivity formation process. We have promising initial results and hope to report soon.

K. S. Engin, V. Isler, "Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots" in Proceedings of The 28th International Conference on Automated Planning and Scheduling (ICAPS), 2018.

• Volkan Isler. Principal Investigator [contact information]
• Kazim Selim Engin. Ph.D. Student [contact information]
• Owen Levin. REU Researcher (Summer 2017) [results]
• Abhi Kamboj. REU Researcher (Summer 2018) [results]
• Alan Koval. REU Researcher (Summer 2018) [results]

This material is based upon work supported by the National Science Foundation under Grant No. 1617718

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.