Online Multi-Agent Pathfinding

Authors

  • Jiří Švancara Charles University
  • Marek Vlk Charles University
  • Roni Stern Ben-Gurion University
  • Dor Atzmon Ben-Gurion University
  • Roman Barták Charles University

DOI:

https://doi.org/10.1609/aaai.v33i01.33017732

Abstract

Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to a set of target destinations while avoiding collisions. In this work, we study the online version of MAPF where new agents appear over time. Several variants of online MAPF are defined and analyzed theoretically, showing that it is not possible to create an optimal online MAPF solver. Nevertheless, we propose effective online MAPF algorithms that balance solution quality, runtime, and the number of plan changes an agent makes during execution.

AAAI-19 Proceedings Cover

Downloads

Published

2019-07-17

How to Cite

Švancara, J., Vlk, M., Stern, R., Atzmon, D., & Barták, R. (2019). Online Multi-Agent Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 7732-7739. https://doi.org/10.1609/aaai.v33i01.33017732

Issue

Vol. 33 No. 01: AAAI-19, IAAI-19, EAAI-20

Section

AAAI Technical Track: Planning, Routing, and Scheduling