Optimal Cooperative Path-Finding with Generalized Goals in Difficult Cases

Abstract

We suggest to employ propositional satisfiability techniques in solving a problem of cooperative multi-robot path-finding optimally. Several propositional encodings of path-finding problems have been suggested recently. In this paper we evaluate how efficient these encodings are in solving certain cases of cooperative path-findings problems optimally. Particularly, a case where robots have multiple optional locations as their targets is considered in this paper.