Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2404.03834 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929303705354240 |
|---|---|
| author | Ishat-E-Rabban, Md Shi, Guangyao Bonner, Griffin Tokekar, Pratap |
| author_facet | Ishat-E-Rabban, Md Shi, Guangyao Bonner, Griffin Tokekar, Pratap |
| contents | Maintaining a robust communication network plays an important role in the success of a multi-robot team jointly performing an optimization task. A key characteristic of a robust cooperative multi-robot system is the ability to repair the communication topology in the case of robot failure. In this paper, we focus on the Fast k-connectivity Restoration (FCR) problem, which aims to repair a network to make it k-connected with minimum robot movement. We develop a Quadratically Constrained Program (QCP) formulation of the FCR problem, which provides a way to optimally solve the problem, but cannot handle large instances due to high computational overhead. We therefore present a scalable algorithm, called EA-SCR, for the FCR problem using graph theoretic concepts. By conducting empirical studies, we demonstrate that the EA-SCR algorithm performs within 10 percent of the optimal while being orders of magnitude faster. We also show that EA-SCR outperforms existing solutions by 30 percent in terms of the FCR distance metric. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03834 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance Ishat-E-Rabban, Md Shi, Guangyao Bonner, Griffin Tokekar, Pratap Robotics Maintaining a robust communication network plays an important role in the success of a multi-robot team jointly performing an optimization task. A key characteristic of a robust cooperative multi-robot system is the ability to repair the communication topology in the case of robot failure. In this paper, we focus on the Fast k-connectivity Restoration (FCR) problem, which aims to repair a network to make it k-connected with minimum robot movement. We develop a Quadratically Constrained Program (QCP) formulation of the FCR problem, which provides a way to optimally solve the problem, but cannot handle large instances due to high computational overhead. We therefore present a scalable algorithm, called EA-SCR, for the FCR problem using graph theoretic concepts. By conducting empirical studies, we demonstrate that the EA-SCR algorithm performs within 10 percent of the optimal while being orders of magnitude faster. We also show that EA-SCR outperforms existing solutions by 30 percent in terms of the FCR distance metric. |
| title | Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance |
| topic | Robotics |
| url | https://arxiv.org/abs/2404.03834 |