Online Multi-Agent Path Finding: New Results

Authors

  • Jonathan Morag Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Roni Stern Ben Gurion University of the Negev
  • Dor Atzmon Ben-Gurion University
  • Eli Boyarski Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/socs.v15i1.21772

Keywords:

Analysis Of Search Algorithms, Combinatorial Optimization, Continuous Problem Solving

Abstract

Online MAPF extends the classical Multi-Agent Path Finding problem (MAPF) by considering a more realistic problem in which new agents may appear over time. As online solvers are not aware of which agents will join in the future, the notion of snapshot-optimal was defined, where only current knowledge is considered. In this paper, we perform an extensive comparison between oracle-optimal solutions (where the solver is preinformed of future agents), snapshot-optimal solutions, and suboptimal solutions obtained by prioritised planning.
SoCS 22 Cover

Downloads

Published

2022-07-17

Issue

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Section

Short Papers