@ARTICLE{PSury14c,
 AUTHOR= "P. Surynek",
 TITLE= "On the Complexity of Optimal Parallel Cooperative Path-Finding",
 JOURNAL= "Fundamenta Informaticae",
 VOLUME="137",
 NUMBER="4",
 PAGES= "517--548",
 YEAR= "2014",
 PDF= "http://surynek.com/publications/files/SurynekPavel_Multirobots-Theory_FundInf-2014.pdf",
 FLAGS= ":2014:,:pavelsurynek:",
 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 spatial-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."  
}

{"_id":"nP59MSLAXYnXKBu4T","bibbaseid":"surynek-onthecomplexityofoptimalparallelcooperativepathfinding-2014","authorIDs":[],"author_short":["Surynek, P."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["P."],"propositions":[],"lastnames":["Surynek"],"suffixes":[]}],"title":"On the Complexity of Optimal Parallel Cooperative Path-Finding","journal":"Fundamenta Informaticae","volume":"137","number":"4","pages":"517–548","year":"2014","pdf":"http://surynek.com/publications/files/SurynekPavel_Multirobots-Theory_FundInf-2014.pdf","flags":":2014:,:pavelsurynek:","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 spatial-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.","bibtex":"@ARTICLE{PSury14c,\n AUTHOR= \"P. Surynek\",\n TITLE= \"On the Complexity of Optimal Parallel Cooperative Path-Finding\",\n JOURNAL= \"Fundamenta Informaticae\",\n VOLUME=\"137\",\n NUMBER=\"4\",\n PAGES= \"517--548\",\n YEAR= \"2014\",\n PDF= \"http://surynek.com/publications/files/SurynekPavel_Multirobots-Theory_FundInf-2014.pdf\",\n FLAGS= \":2014:,:pavelsurynek:\",\n ABSTRACT= \n\"A parallel version of the problem of cooperative path-finding (pCPF) is\nintroduced in this paper. The task in CPF is to determine a spatial-temporal\nplan for each member of a group of agents. Each agent is given its initial\nlocation in the environment and its task is to reach the given goal\nlocation. Agents must avoid obstacles and must not collide with one\nanother. The environment where agents are moving is modeled as an undirected\ngraph. Agents are placed in vertices and they move along edges. At most one\nagent is placed in each vertex and at least one vertex remains unoccupied. An\nagent can only move into a currently unoccupied vertex in the standard version\nof CPF. In the parallel version, an agent can also move into a vertex being\ncurrently vacated by another agent supposing the character of this movement is\nnot cyclic. The optimal pCPF where the task is to find the smallest possible\nsolution of the makespan is particularly studied. The main contribution of\nthis paper is the proof of NP-completeness of the decision version of the\noptimal pCPF. A reduction of propositional satisfiability (SAT) to the problem\nis used in the proof.\" \n}\n\n","author_short":["Surynek, P."],"key":"PSury14c","id":"PSury14c","bibbaseid":"surynek-onthecomplexityofoptimalparallelcooperativepathfinding-2014","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"article","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.736Z","downloads":0,"keywords":[],"search_terms":["complexity","optimal","parallel","cooperative","path","finding","surynek"],"title":"On the Complexity of Optimal Parallel Cooperative Path-Finding","year":2014,"dataSources":["oEkRzPPMbrG9LyYPh"]}