Open AccessColored Multi-Agent Path Finding: Solving Approaches
Author(s) -
Roman Barták,
Marika Ivanová,
Jiří Švancara
Publication year - 2021
Publication title -
proceedings of the ... international florida artificial intelligence research society conference
Language(s) - English
Resource type - Journals
eISSN - 2334-0762
pISSN - 2334-0754
DOI - 10.32473/flairs.v34i1.128535
Subject(s) - colored , set (abstract data type) , computer science , path (computing) , satisfiability , mathematical optimization , constraint (computer aided design) , relaxation (psychology) , constraint satisfaction problem , boolean satisfiability problem , multi agent system , theoretical computer science , algorithm , mathematics , artificial intelligence , psychology , social psychology , materials science , geometry , probabilistic logic , composite material , programming language
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.