Md Ishat-E-Rabban

Md Ishat-E-Rabban

SDE at Intel | M.Sc. in CS from UMD College Park | Expert in Robotic Planning, Deep Learning, and Geometric Computing | Highly Proficient in C++ and Python

Fast Connectivity Restoration

Keywords: Graph Theory, Quadratic Optimization, Multi-Robot Systems.

Source Code: Github

In this project, we investigate the problem of making a network k-connected while minimizing robot movements. Here, a k-connected network refers to a topology that cannot be disconnected by removing any combination of k-1 nodes. The input to this problem is a set of robot positions and the integer value k. Here, we assume a disk communication model with communication radius h. The goal is to find new positions of the robots that form a k-connected topology while minimizing the maximum distance between the previous and new positions of the robots. We call this problem the Fast k-connectivity Restoration (FCR) problem. An example of the FCR problem instance is shown in the above video. In the examples shown in the video, the robots move towards a higher degree of connectivity while minimizing the length of the path traveled by the robots.

We have developed a Quadratically Constrained Program (QCP) formulation of the FCR problem, which is based on the idea of multi-commodity network flow. The QCP formulation enables us to solve the FCR problem optimally using a QCP solver. However, the QCP formulation can be used to solve only small instances of the FCR problem due to high computational overhead.

We therefore propose a scalable algorithm, EA-SCR, to solve the FCR problem which requires less computational time than the optimal QCP-based algorithm. The EA-SCR algorithm solves the FCR problem by dividing it into two phases. In the first phase, we find a set of edges that, if augmented to the input network, make the network k-connected, and the maximum cost of the augmented edges is minimized. Here the cost of an edge is proportional to the Fast k-connectivity Restoration distance between the two corresponding robots. We call this the Graph Topology Optimization (GTO) problem. We solve the GTO problem by first sorting the non-existent edges of the communication graph in increasing order of weight, and then keep adding the edges in order until the graph becomes k-connected. In the second phase, we move the robots in such a way that the edges obtained from the first phase are established, and the maximum distance traveled by a robot is minimized. We call this the Movement Minimization (MM) problem. To solve the MM problem, we propose a Breadth First Search (BFS) based idea called cascaded relocation, which establishes the edges obtained from the first phase without removing any existing edges.

We conduct extensive experimentation to evaluate the performance of our proposed algorithm. The empirical results show that the EA-SCR algorithm generates solutions that are within 10% of the optimal solution and gives 30% lower minmax distance than all existing FCR algorithms as listed below.

We also test the EA-SCR algorithm in action by performing a hardware experiment using 6 drones. A video of the hardware experiment is given below.

Tools Used

Publications