On the Complexity of Optimal Parallel Cooperative Path-Finding

• Autorzy: Surynek P.

Identyfikatory

DOI

10.3233/FI-2015-1192

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cooperative path-finding; CPF; parallelism; multi-agent; sliding puzzle; (N2 − 1)-puzzle; N × N-puzzle; 15-puzzle; domain dependent planning; complexity; NP-completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 137, nr 4
• Strony: 517--548
• Opis fizyczny: Bibliogr. 37 poz., rys.

Twórcy

autor

Surynek P.

• 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

Bibliografia

• [1] R. K. Ahuja, T. L.Magnanti, and J. B. Orlin. Network flows: theory, algorithms, and applications. Prentice Hall, 1993, ISBN 978-0136175490.
• [2] S. A. Cook. The Complexity of Theorem Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC 1971), pp. 151-158, ACM Press, 1971.
• [3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (Second edition). MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7.
• [4] J. C. Culberson. Sokoban is PSPACE-complete. Technical Report TR 97-02, Department of Computing Science, University of Alberta, 1997, http://webdocs.cs.ualberta.ca/˜joe/Preprints/Sokoban/ index.html [accessed April 2010].
• [5] J. D. Dixon and B.Mortimer. PermutationGroups. in Graduate Texts inMathematics, Volume 163, Springer, 1996, ISBN 978-0-387-94599-6.
• [6] S. Even, A. Itai, A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, Volume 5 (??), pp. 691-703, Society for Industrial and Applied Mathematics, 1976.
• [7] G. W. Flake, E. B. Baum. Rush Hour is PSPACE-complete, or ”Why you should generously tip parking lot attendants”. Theoretical Computer Science, Volume 270(1-2), pp. 895-911 Elsevier, 2002.
• [8] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979, ISBN: 978-0716710455.
• [9] R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, Volume 343(1-2), pp. 72-96, Elsevier, 2005.
• [10] E. Hordern. Sliding Piece Puzzles. Oxford University Press, 1986, ISBN: 978-0198532040.
• [11] M. Ivanová, P. Surynek. Adversarial Cooperative Path-Finding: A First View. The 27th AAAI Conference on Artificial Intelligence (AAAI 2013), Bellevue, WA, USA, late breaking track, technical report, AAAI Press, 2013
• [12] P. Jackson, D. Sheridan. Clause Form Conversions for Propositional Circuits. Theory and Applications of Satisfiability Testing, 7th International Conference (SAT 2004), Revised Selected Papers, pp. 183-198, Lecture Notes in Computer Science 3542, Springer 2005.
• [13] D. Kornhauser, G. L. Miller, and P. G. Spirakis. Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS 1984), pp. 241-250, IEEE Press, 1984.
• [14] C. H. Papadimitriou, P. Raghavan, M. Sudan, and H. Tamaki. Motion Planning on a Graph. Proceedings of the 35th Annual Symposiumon Foundations of Computer Science (FOCS 1994), pp. 511-520, IEEE Press, 1994.
• [15] D. Ratner and M. K. Warmuth. Finding a Shortest Solution for the N×N Extension of the 15-PUZZLE Is Intractable. Proceedings of the 5th National Conference on Artificial Intelligence (AAAI 1986), pp. 168-172, Morgan Kaufmann Publishers, 1986.
• [16] D. Ratner and M. K. Warmuth. NxN Puzzle and Related Relocation Problems. Journal of Symbolic Computation, Volume 10, pp. 111-138, Elsevier, 1990.
• [17] M. R. K. Ryan. Graph Decomlocation for Efficient Cooperative path-finding. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 2003-2008, IJCAI Conference, 2007.
• [18] M. R. K. Ryan. Exploiting Subgraph Structure in Cooperative path-finding. Journal of Artificial Intelligence Research (JAIR), Volume 31, pp. 497-542, AAAI Press, 2008.
• [19] P. E. Schupp and R. C. Lyndon. Combinatorial group theory. Springer, 2001, ISBN 978-3-540-41158-1.
• [20] D. Silver. Cooperative Pathfinding. Proceedings of the 1st Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005), pp. 117-122, AAAI Press.
• [21] T. Standley. Finding Optimal Solutions to Cooperative Pathfinding Problems. Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 173-178, AAAI Press, 2010.
• [22] P. Surynek. A Novel Approach to Path-finding for Multiple Agents in Bi-connected Graphs. Proceedings of the 2009 IEEE International Conference on Agentics and Automation (ICRA 2009), pp. 3613-3619, IEEE Press, 2009.
• [23] P. Surynek. Towards Shorter Solutions for Problems of Path-finding for Multiple Agents in _-like Environments. Proceedings of the 22nd International FLAIRS Conference (FLAIRS 2009), pp. 207-212,AAAI Press, 2009.
• [24] P. Surynek. Making Solutions of Cooperative path-finding Problems Shorter Using Weak Translocations and Critical Path Parallelism. Proceedings of the 2009 International Symposium on Combinatorial Search (SoCS 2009), University of Southern California, 2009, http://www.search-conference.org/index.php/Main/SOCS09 [accessed July 2009].
• [25] P. Surynek. An Application of Pebble Motion on Graphs to Abstract Cooperative path-finding. Proceedings of the 21st International Conference on Tools with Artificial Intelligence (ICTAI 2009), pp. 151-158, IEEE Press, 2009.
• [26] P. Surynek. An Optimization Variant of Cooperative path-finding is Intractable. Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), pp. 1261-1263, AAAI Press, 2010.
• [27] P. Surynek. Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving. Proceedings of 12th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2012), pp. 564-576, LNCS 7458, Springer, 2012.
• [28] P. Surynek. Solving Abstract Cooperative Path-Finding in Densely Populated Environments. Computational Intelligence, Volume 30, Issue 2, pp. 402-450,Wiley, 2014.
• [29] R. E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, Volume 1, pp. 146-160, Society for Industrial and Applied Mathematics, 1972.
• [30] K. C. Wang and A. Botea. Tractable Cooperative path-finding on Grid Maps. Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pp. 1870-1875, IJCAI Conference, 2009.
• [31] K. C.Wang. Bridging the Gap between Centralised and Decentralised Multi-Agent Pathfinding. Proceedings of the 14th Annual AAAI/SIGART Doctoral Consortium (AAAI-DC 2009), pp. 23-24, AAAI Press, 2009.
• [32] K. C.Wang and A. Botea. Fast andMemory-EfficientMulti-Agent Pathfinding. Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008), Australia, pp. 380-387, AAAI Press, 2008, ISBN 978-1-57735-386-7.
• [33] K. C. Wang and A. Botea. Scalable Multi-Agent Pathfinding on Grid Maps with Tractability and Completeness Guarantees. Proceedings of the European Conference on Artificial Intelligence (ECAI 2010), IOS Press, 2010.
• [34] D. B. West. Introduction to Graph Theory. Prentice Hall, 2000, ISBN: 978-0130144003.
• [35] J. Westbrook, R. E. Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, Volume 7, Number 5&6, pp. 433-464, Springer, 1992.
• [36] B. de Wilde, A. ter Mors, C. Witteveen. Push and rotate: cooperative multi-agent path planning. Proceedings of International conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), pp. 87-94, IFAAMAS, 2013.
• [37] R. M. Wilson. Graph Puzzles, Homotopy, and the Alternating Group. Journal of Combinatorial Theory, Ser. B 16, pp. 86-96, Elsevier, 1974.