Affiliations: Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. pavel.surynek@mff.cuni.cz
Note: [] Address for correspondence: Charles University in Prague, Faculty of Mathematics and Physics, Malostranské náměstí 25, 11800 Praha, Czech Republic This work is supported by the Czech Science Foundation under the contract number GAP103/10/1287 and by Charles University in Prague within the PRVOUK project (section P46).
Abstract: A parallel version of the problem of cooperative path-finding (pCPF) is introduced in this paper. The task in CPF is to determine a spatio-temporal plan for each member of a group of agents. Each agent is given its initial location in the environment and its task is to reach the given goal location. Agents must avoid obstacles and must not collide with one another. The environment where agents are moving is modeled as an undirected graph. Agents are placed in vertices and they move along edges. At most one agent is placed in each vertex and at least one vertex remains unoccupied. An agent can only move into a currently unoccupied vertex in the standard version of CPF. In the parallel version, an agent can also move into a vertex being currently vacated by another agent supposing the character of this movement is not cyclic. The optimal pCPF where the task is to find the smallest possible solution of the makespan is particularly studied. The main contribution of this paper is the proof of NP-completeness of the decision version of the optimal pCPF. A reduction of propositional satisfiability (SAT) to the problem is used in the proof.
