LIMP: Incremental Multi-agent Path Planning with LPA*

Yorganci M. A., SEMİZ F., POLAT F.

14th International Conference on Agents and Artificial Intelligence (ICAART), ELECTR NETWORK, 3 - 05 February 2022, pp.208-215 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.5220/0010824400003116
  • Page Numbers: pp.208-215
  • Keywords: AI, Multi-agent, Pathfinding, MAPF, Incremental Planning
  • Middle East Technical University Affiliated: Yes


The multi-agent pathfinding (MAPF) problem is defined as finding conflict-free paths for more than one agent. There exist optimal and suboptimal solvers for MAPF, and most of the solvers focus on the MAPF problem in static environments, but the real world is far away from being static. Motivated by this requirement, in this paper, we introduce an incremental algorithm to solve MAPF. We focused on discrete-time and discrete space environments with the unit cost for all edges. We proposed an algorithm called incremental multi-agent path planning with LPA* (LIMP) and discrete lifelong planning A* (DLPA*) for solving I-MAPF (Incremental MAPF). LIMP is the combination of two algorithms which are the Conflict Based Search D*-lite (CBS-D*lite) (Semiz and Polat, 2021) and DLPA*. DLPA* is just a tailored version of the lifelong planning A* (Koenig et al., 2004) which is an incremental search algorithm for one agent. We have shown that LIMP outperforms Conflict Based Search replanner (CBS-replanner) and CBS-D*-lite (Semiz and Polat, 2021) in terms of speed. Moreover, in terms of cost, LIMP and CBS-D*-lite perform similarly, and they are close to CBS-replanner.