Colored Multi-Agent Path Finding: Solving Approaches

Authors

DOI:

https://doi.org/10.32473/flairs.v34i1.128535

Keywords:

path finding; multi agent; network flows; conflict-based search; Boolean satisfiability

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 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 the 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-04-18

How to Cite

Barták, R., Ivanová, M., & Švancara, J. (2021). Colored Multi-Agent Path Finding: Solving Approaches. The International FLAIRS Conference Proceedings, 34. https://doi.org/10.32473/flairs.v34i1.128535

Issue

Section

Special Track: Autonomous Robots and Agents