UniAGENT: Reduced Time-Expansion Graphs and Goal Decomposition in Sub-optimal Cooperative Path Finding
DOI:
https://doi.org/10.1609/socs.v6i1.18344Keywords:
cooperative path-finding, multi-agent path planning, propositional satisfiability, vertex disjoint pathsAbstract
Solving cooperative path finding (CPF) by translating it to propositional satisfiability represents a viable option in highly constrained situations. The task in CPF is to relocate agents from their initial positions to given goals in a collision free manner. In this paper, we propose a reduced time expansion that is focused on makespan sub-optimal solving of the problem. The suggested reduced time expansion is especially beneficial in conjunction with a goal decomposition where agents are relocated one by one.
Downloads
Published
2021-09-01
Issue
Section
Abstracts