From Classical to Colored Multi-Agent Path Finding

Authors

  • Roman Barták Charles University, Faculty of Mathematics and Physics
  • Marika Ivanová Charles University, Faculty of Mathematics and Physics
  • Jiří Švancara Charles University, Faculty of Mathematics and Physics

Keywords:

Problem Compilation, Real-life Applications, Automated Synthesis Of Lower Bounds, Combinatorial Optimization

Abstract

Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents moving in a shared environment, while each agent has specified its own destination. Colored MAPF generalizes MAPF by defining groups of agents that share a set of destination locations. In the paper, we evaluate several approaches to optimally solve colored MAPF problem, namely, a method based on network flows, an extended version of conflict-based search, and two models using Boolean satisfiability. We also investigate methods for obtaining lower bounds on optimal solutions based on constraint and continuous relaxation techniques.

Downloads

Published

2021-07-21