In several multirobot applications in which communication is limited, the mission could require the robots to iteratively take coordinated joint decisions on how to spread out in the environment and on how to reconnect with each other to share data and compute plans. Exploration and surveillance are examples of these applications. In this paper, we consider the problem of computing robots' paths on a graph-represented environment for restoring connections at minimum traveling cost. We call it the multirobot reconnection problem, we show its NP-hardness and hardness of approximation on some important classes of graphs, and we provide optimal and heuristic algorithms to solve it in practical settings. The techniques we propose are then exploited to derive a new efficient planning algorithm for a relevant connectivity-constrained multirobot planning problem addressed in the literature, the multirobot informative path planning with periodic connectivity problem.

Multirobot Reconnection on Graphs: Problem, Complexity, and Algorithms / J. Banfi, N. Basilico, F. Amigoni. - In: IEEE TRANSACTIONS ON ROBOTICS. - ISSN 1552-3098. - 34:5(2018 Oct), pp. 8379358.1299-8379358.1314.

Multirobot Reconnection on Graphs: Problem, Complexity, and Algorithms

J. Banfi
Primo
;
N. Basilico
Penultimo
;
2018-10

Abstract

In several multirobot applications in which communication is limited, the mission could require the robots to iteratively take coordinated joint decisions on how to spread out in the environment and on how to reconnect with each other to share data and compute plans. Exploration and surveillance are examples of these applications. In this paper, we consider the problem of computing robots' paths on a graph-represented environment for restoring connections at minimum traveling cost. We call it the multirobot reconnection problem, we show its NP-hardness and hardness of approximation on some important classes of graphs, and we provide optimal and heuristic algorithms to solve it in practical settings. The techniques we propose are then exploited to derive a new efficient planning algorithm for a relevant connectivity-constrained multirobot planning problem addressed in the literature, the multirobot informative path planning with periodic connectivity problem.
Multirobot reconnection; networked robots; path planning for multiple mobile robot systems; Control and Systems Engineering; Computer Science Applications1707 Computer Vision and Pattern Recognition; Electrical and Electronic Engineering
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
08379358.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 2.05 MB
Formato Adobe PDF
2.05 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
pij35.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 2.05 MB
Formato Adobe PDF
2.05 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/631700
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact