Among sub-optimal Multi-Agent Path Finding (MAPF) solvers, rule-based algorithms are particularly appealing since they are complete. Even in crowded scenarios, they allow finding a feasible solution that brings each agent to its target, preventing deadlock situations. However, generally, rule-based algorithms provide solutions that are much longer than the opti-malone. The main contribution of this paper is the introduction of an iterative local search procedure in MAPF. We start from a feasible suboptimal solution and we perform a local search in a neighborhood of this solution, to find a shorter one. Iteratively, we repeat this procedure until the solution cannot be shortened any longer. At the end, we obtain a solution, that is still sub-optimal, but, in general, of much better quality than the initial one. We use dynamic programming for the local search procedure. Under this respect, the fact that our search is local is fundamental to reduce the time complexity of the algorithm. Indeed, if we apply a standard dynamic programming the number of explored states grows exponentially with the number of agents. As we will see, the introduction of a locality constraint allows solving the (local) dynamic programming problem in a time that grows only polynomially with respect to the number of agents.

Local Optimization of MAPF Solutions on Directed Graphs / Ardizzoni, S.; Saccani, I.; Consolini, L.; Locatelli, M.. - (2023), pp. 8081-8086. (Intervento presentato al convegno 62nd IEEE Conference on Decision and Control, CDC 2023 tenutosi a sgp nel 2023) [10.1109/CDC49753.2023.10383280].

Local Optimization of MAPF Solutions on Directed Graphs

Ardizzoni S.;Saccani I.;Consolini L.;Locatelli M.
2023-01-01

Abstract

Among sub-optimal Multi-Agent Path Finding (MAPF) solvers, rule-based algorithms are particularly appealing since they are complete. Even in crowded scenarios, they allow finding a feasible solution that brings each agent to its target, preventing deadlock situations. However, generally, rule-based algorithms provide solutions that are much longer than the opti-malone. The main contribution of this paper is the introduction of an iterative local search procedure in MAPF. We start from a feasible suboptimal solution and we perform a local search in a neighborhood of this solution, to find a shorter one. Iteratively, we repeat this procedure until the solution cannot be shortened any longer. At the end, we obtain a solution, that is still sub-optimal, but, in general, of much better quality than the initial one. We use dynamic programming for the local search procedure. Under this respect, the fact that our search is local is fundamental to reduce the time complexity of the algorithm. Indeed, if we apply a standard dynamic programming the number of explored states grows exponentially with the number of agents. As we will see, the introduction of a locality constraint allows solving the (local) dynamic programming problem in a time that grows only polynomially with respect to the number of agents.
2023
Local Optimization of MAPF Solutions on Directed Graphs / Ardizzoni, S.; Saccani, I.; Consolini, L.; Locatelli, M.. - (2023), pp. 8081-8086. (Intervento presentato al convegno 62nd IEEE Conference on Decision and Control, CDC 2023 tenutosi a sgp nel 2023) [10.1109/CDC49753.2023.10383280].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11381/2991595
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact