Publication

P. Surynek. Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs. In Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI), pages 875-882, 2014.

Abstract: This paper addresses makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task is to relocate set of agents to given goal positions so that they do not collide with each other. A novel SAT encoding of CPF is suggested. The novel encoding uses the concept of matching in a bipartite graph to separate spatial constraint of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evaluation shown that novel encoding can be solved faster than existing encodings for CPF and also that the SAT based methods dominates over A* based methods in environment densely occupied by agents.

Download the paper in pdf.