{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:15:58Z","timestamp":1761293758539},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s10458-018-9391-2","type":"journal-article","created":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T15:15:54Z","timestamp":1528902954000},"page":"693-740","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A complete multi-robot path-planning algorithm"],"prefix":"10.1007","volume":"32","author":[{"given":"Ebtehal Turki Saho","family":"Alotaibi","sequence":"first","affiliation":[]},{"given":"Hisham","family":"Al-Rawi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"9391_CR1","doi-asserted-by":"crossref","unstructured":"Bhaduri, A. (2009). A mobile robot path planning using genetic artificial immune network algorithm. In World congress on nature and biologically inspired computing (pp. 1536\u20131539). IEEE.","DOI":"10.1109\/NABIC.2009.5393670"},{"key":"9391_CR2","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C. H., Raghavan, P., Sudan, M., & Tamaki, H. (1994). Motion planning on a graph. In 1994 Proceedings. 35th Annual symposium on foundations of computer science (pp. 511\u2013520). IEEE.","DOI":"10.1109\/SFCS.1994.365740"},{"key":"9391_CR3","first-page":"1","volume-title":"Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. Lecture notes in computer science","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O. (2011). Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard. Lecture notes in computer science (pp. 1\u20135). Berlin Heidelberg: Springer."},{"key":"9391_CR4","doi-asserted-by":"crossref","unstructured":"Dresner, K., & Stone, P. (2005). Multiagent traffic management: An improved intersection control mechanism. In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems (pp. 471\u2013477). ACM.","DOI":"10.1145\/1082473.1082545"},{"issue":"1","key":"9391_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0020-0255(02)00227-X","volume":"145","author":"JM Roberts","year":"2002","unstructured":"Roberts, J. M., Duff, E. S., & Corke, P. I. (2002). Reactive navigation and opportunistic localization for autonomous underground mining vehicles. Information Sciences, 145(1), 127\u2013146.","journal-title":"Information Sciences"},{"key":"9391_CR6","doi-asserted-by":"crossref","unstructured":"Leitner, J. (2009). Multi-robot cooperation in space: a survey. In Advanced technologies for enhanced quality of life. AT-EQUAL\u201909 (pp. 144\u2013151). IEEE.","DOI":"10.1109\/AT-EQUAL.2009.37"},{"issue":"7","key":"9391_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1109\/MSPEC.2008.4547508","volume":"45","author":"E Guizzo","year":"2008","unstructured":"Guizzo, E. (2008). Three engineers, hundreds of robots, one warehouse. IEEE Spectrum, 45(7), 26\u201334.","journal-title":"IEEE Spectrum"},{"issue":"9","key":"9391_CR8","doi-asserted-by":"publisher","first-page":"1784","DOI":"10.1109\/TCYB.2014.2360368","volume":"45","author":"A Macwan","year":"2015","unstructured":"Macwan, A., Vilela, J., Nejat, G., & Benhabib, B. (2015). A multirobot path-planning strategy for autonomous wilderness search and rescue. IEEE Transactions on Cybernetics, 45(9), 1784\u20131797.","journal-title":"IEEE Transactions on Cybernetics"},{"issue":"5","key":"9391_CR9","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1109\/TRO.2005.847567","volume":"21","author":"Z Tang","year":"2005","unstructured":"Tang, Z., & Ozguner, U. (2005). Motion planning for multitarget surveillance with mobile sensor agents. IEEE Transactions on Robotics, 21(5), 898\u2013908.","journal-title":"IEEE Transactions on Robotics"},{"key":"9391_CR10","unstructured":"Zheng, T., Liu, D., & Wang, P. (2004). Priority based dynamic multiple robot path planning. In Proceedings of 2nd international conference on autonomous robots and agents."},{"issue":"1","key":"9391_CR11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.scico.2006.06.008","volume":"67","author":"D Nieuwenhuisen","year":"2007","unstructured":"Nieuwenhuisen, D., Kamphuis, A., & Overmars, M. H. (2007). High quality navigation in computer games. Science of Computer Programming, 67(1), 91\u2013104.","journal-title":"Science of Computer Programming"},{"key":"9391_CR12","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., & Spirakis, P. (1984). Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. Master\u2019s thesis, M.I.T., Cambridge.","DOI":"10.1109\/SFCS.1984.715921"},{"key":"9391_CR13","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1613\/jair.4447","volume":"51","author":"B Wilde de","year":"2014","unstructured":"de Wilde, B., ter Mors, A. W., & Witteveen, C. (2014). Push and rotate: A complete multi-agent pathfinding algorithm. Journal of Artificial Intelligence Research, 51, 443\u2013492.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9391_CR14","unstructured":"Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. In IJCAI (pp. 294\u2013300)."},{"key":"9391_CR15","doi-asserted-by":"crossref","unstructured":"Surynek, P. (2009). A novel approach to path planning for multiple robots in bi-connected graphs. In IEEE international conference on robotics and automation (pp. 3613\u20133619). IEEE.","DOI":"10.1109\/ROBOT.2009.5152326"},{"key":"9391_CR16","first-page":"55","volume":"42","author":"K-HC Wang","year":"2011","unstructured":"Wang, K.-H. C., & Botea, A. (2011). Mapp: A scalable multi-agent path planning algorithm with tractability and completeness guarantees. Journal of Artificial Intelligence Research, 42, 55\u201390.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"6","key":"9391_CR17","first-page":"10","volume":"7","author":"ETS Alotaibi","year":"2016","unstructured":"Alotaibi, E. T. S., & Al-Rawi, H. (2016). Multi-robot path-planning problem for a heavy traffic control application: A survey. International Journal of Advanced Computer Science and Applications, 7(6), 10.","journal-title":"International Journal of Advanced Computer Science and Applications"},{"key":"9391_CR18","unstructured":"Sajid, Q., Luna, R., & Bekris, K. E. (2012). Multi-agent pathfinding with simultaneous execution of single-agent primitives. In SOCS."},{"issue":"1","key":"9391_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"RM Wilson","year":"1974","unstructured":"Wilson, R. M. (1974). Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, Series B, 16(1), 86\u201396.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9391_CR20","unstructured":"Yu, J., & Rus, D. (2015). Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms. In Algorithmic foundations of robotics XI (pp. 729\u2013746). Berlin: Springer."},{"key":"9391_CR21","volume-title":"Pebbles in motion polynomial algorithms for multi-agent path planning problems","author":"P M\u00e4chler","year":"2012","unstructured":"M\u00e4chler, P. (2012). Pebbles in motion polynomial algorithms for multi-agent path planning problems. Master of Science in Computer Science: University of Basel, Basel."},{"key":"9391_CR22","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1613\/jair.2408","volume":"31","author":"MRK Ryan","year":"2008","unstructured":"Ryan, M. R. K. (2008). Exploiting subgraph structure in multi-robot path planning. Journal of Artificial Intelligence Research, 31, 497\u2013542.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9391_CR23","unstructured":"Yu, J., & LaValle, S. M. (2013). Multi-agent path planning and network flow. In Algorithmic foundations of robotics X (pp. 157\u2013173). Berlin: Springer."},{"key":"9391_CR24","volume-title":"Efficient algorithms for graph manipulation","author":"JE Hopcroft","year":"1971","unstructured":"Hopcroft, J. E., & Tarjan, R. E. (1971). Efficient algorithms for graph manipulation. Stanford, CA: University of California."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-018-9391-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9391-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9391-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T23:03:29Z","timestamp":1560380609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-018-9391-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,13]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["9391"],"URL":"https:\/\/doi.org\/10.1007\/s10458-018-9391-2","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,13]]},"assertion":[{"value":"13 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}