Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents such that they can safely reach delivery locations from pickup ones. These locations are provided at runtime, making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and online task assignment. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications: real agents often do not follow the planned paths perfectly, and may be subject to delays and failures. In this paper, we study the problem of MAPD with delays, and we present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution. In particular, we introduce two algorithms, k-\mathbf{TP} and p-\mathbf{TP}, both based on a decentralized algorithm typically used to solve MAPD, Token Passing (TP), which offer deterministic and probabilistic guarantees, respectively. Experimentally, we compare our algorithms against a version of TP enriched with online replanning. k-\mathbf{TP} and p-\mathbf{TP} provide robust solutions, significantly reducing the number of replans caused by delays, with little or no increase in solution cost and running time.

Robust Multi-Agent Pickup and Delivery with Delays / G. Lodigiani, N. Basilico, F. Amigoni - In: ECMR 2023[s.l] : Institute of Electrical and Electronics Engineers (IEEE), 2023. - ISBN 9798350307047. - pp. 172-179 (( Intervento presentato al 11. convegno European Conference on Mobile Robots : 4-7 September nel 2023 [10.1109/ECMR59166.2023.10256381].

Robust Multi-Agent Pickup and Delivery with Delays

N. Basilico
Penultimo
;
2023

Abstract

Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents such that they can safely reach delivery locations from pickup ones. These locations are provided at runtime, making MAPD a combination between classical Multi-Agent Path Finding (MAPF) and online task assignment. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications: real agents often do not follow the planned paths perfectly, and may be subject to delays and failures. In this paper, we study the problem of MAPD with delays, and we present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution. In particular, we introduce two algorithms, k-\mathbf{TP} and p-\mathbf{TP}, both based on a decentralized algorithm typically used to solve MAPD, Token Passing (TP), which offer deterministic and probabilistic guarantees, respectively. Experimentally, we compare our algorithms against a version of TP enriched with online replanning. k-\mathbf{TP} and p-\mathbf{TP} provide robust solutions, significantly reducing the number of replans caused by delays, with little or no increase in solution cost and running time.
Settore INF/01 - Informatica
2023
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Robust_Multi-Agent_Pickup_and_Delivery_with_Delays.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 397.06 kB
Formato Adobe PDF
397.06 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2303.17422v1.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 524.11 kB
Formato Adobe PDF
524.11 kB Adobe PDF Visualizza/Apri
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: https://hdl.handle.net/2434/1055009
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact