{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:13:08Z","timestamp":1760346788939,"version":"3.37.3"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1734419","1617744"],"award-info":[{"award-number":["1734419","1617744"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Robot"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s10514-019-09858-z","type":"journal-article","created":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:27:42Z","timestamp":1558524462000},"page":"469-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Average case constant factor time and distance optimal multi-robot path planning in well-connected environments"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4112-2250","authenticated-orcid":false,"given":"Jingjin","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"9858_CR1","doi-asserted-by":"crossref","unstructured":"Adler, A., De\u00a0Berg, M., Halperin, D., & Solovey, K. (2015). Efficient multi-robot motion planning for unlabeled discs in simple polygons. In Algorithmic foundations of robotics XI, (pp. 1\u201317). Springer.","DOI":"10.1007\/978-3-319-16595-0_1"},{"key":"9858_CR2","doi-asserted-by":"crossref","unstructured":"Alami, R., Robert, F., Ingrand, F., & Suzuki, S. (1995). Multi-robot cooperation through incremental plan-merging. In Robotics and automation, 1995. Proceedings., 1995 IEEE international conference on, (vol\u00a03, pp. 2573\u20132579). IEEE.","DOI":"10.1109\/ROBOT.1995.525645"},{"key":"9858_CR3","doi-asserted-by":"crossref","unstructured":"Alonso-Mora, J., Knepper, R., Siegwart, R., & Rus, D. (2015). Local motion planning for collaborative multi-robot manipulation of deformable objects. In 2015 IEEE international conference on robotics and automation (ICRA), (pp. 5495\u20135502). IEEE.","DOI":"10.1109\/ICRA.2015.7139967"},{"key":"9858_CR4","unstructured":"Atzmon, D., Stern, R., Felner, A., Wagner, G., Bart\u00e1k, R., & Zhou, N.F. (2018). Robust multi-agent path finding. In Proceedings of the 17th international conference on autonomous agents and multiagent systems, international foundation for autonomous agents and multiagent systems, (pp. 1862\u20131864)."},{"key":"9858_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/PL00009259","volume":"23","author":"V Auletta","year":"1999","unstructured":"Auletta, V., Monti, A., Parente, M., & Persiano, P. (1999). A linear-time algorithm for the feasbility of pebble motion on trees. Algorithmica, 23, 223\u2013245.","journal-title":"Algorithmica"},{"issue":"6","key":"9858_CR6","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/70.736776","volume":"14","author":"T Balch","year":"1998","unstructured":"Balch, T., & Arkin, R. C. (1998). Behavior-based formation control for multirobot teams. IEEE Transactions on Robotics and Automation, 14(6), 926\u2013939.","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"4","key":"9858_CR7","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1109\/LRA.2017.2715406","volume":"2","author":"J Banfi","year":"2017","unstructured":"Banfi, J., Basilico, N., & Amigoni, F. (2017). Intractability of time-optimal multirobot path planning on 2d grid graphs with holes. IEEE Robotics and Automation Letters, 2(4), 1941\u20131947.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"9858_CR8","doi-asserted-by":"crossref","unstructured":"Bekris, K. E., Tsianos, K. I., & Kavraki, L. E. (2007). A decentralized planner that guarantees the safety of communicating vehicles with complex dynamics that replan online. In 2007 IEEE\/RSJ international conference on intelligent robots and systems, (pp. 3784\u20133790). IEEE.","DOI":"10.1109\/IROS.2007.4399520"},{"key":"9858_CR9","volume-title":"Modern graph theory","author":"B Bollob\u00e1s","year":"2013","unstructured":"Bollob\u00e1s, B. (2013). Modern graph theory (Vol. 184). Berlin: Springer."},{"key":"9858_CR10","unstructured":"Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., & Shimony, E. (2015). Icbs: The improved conflict-based search algorithm for multi-agent pathfinding. In Eighth annual symposium on combinatorial search."},{"issue":"5","key":"9858_CR11","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1049\/ip-cta:20050152","volume":"153","author":"MS Branicky","year":"2006","unstructured":"Branicky, M. S., Curtiss, M. M., Levine, J., & Morgan, S. (2006). Sampling-based planning, control and verification of hybrid systems. IEE Proceedings Control Theory and Applications, 153(5), 575.","journal-title":"IEE Proceedings Control Theory and Applications"},{"key":"9858_CR12","volume-title":"The complexity of robot motion planning","author":"JF Canny","year":"1988","unstructured":"Canny, J. F. (1988). The complexity of robot motion planning. Cambridge, MA: MIT Press."},{"key":"9858_CR13","volume-title":"Principles of robot motion: Theory, algorithms, and implementations","author":"H Choset","year":"2005","unstructured":"Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., et al. (2005). Principles of robot motion: Theory, algorithms, and implementations. Cambridge, MA: MIT Press."},{"key":"9858_CR14","unstructured":"Cohen, L., Uras, T., Kumar, T., Xu, H., Ayanian, N., & Koenig, S. (2016). Improved bounded-suboptimal multi-agent path finding solvers. In International joint conference on artificial intelligence."},{"issue":"6","key":"9858_CR15","doi-asserted-by":"publisher","first-page":"1158","DOI":"10.1109\/TRO.2005.853499","volume":"21","author":"MG Earl","year":"2005","unstructured":"Earl, M. G., & D\u2019Andrea, R. (2005). Iterative milp methods for vehicle-control problems. IEEE Transactions on Robotics, 21(6), 1158\u20131167.","journal-title":"IEEE Transactions on Robotics"},{"key":"9858_CR16","doi-asserted-by":"crossref","unstructured":"Erdem, E., Kisa, D. G., \u00d6ztok, U., & Schueller, P. (2013). A general formal framework for pathfinding problems with multiple agents. In AAAI.","DOI":"10.1609\/aaai.v27i1.8592"},{"key":"9858_CR17","doi-asserted-by":"crossref","unstructured":"Erdmann, M. A., & Lozano-P\u00e9rez, T. (1986). On multiple moving objects. In Proceedings IEEE international conference on robotics and automation, (pp. 1419\u20131424).","DOI":"10.21236\/ADA196213"},{"key":"9858_CR18","doi-asserted-by":"crossref","unstructured":"Ferner, C., Wagner, G., & Choset, H. (2013). Odrm* optimal multirobot path planning in low dimensional search spaces. In Robotics and automation (ICRA), 2013 IEEE international conference on, (pp. 3854\u20133859). IEEE.","DOI":"10.1109\/ICRA.2013.6631119"},{"issue":"3","key":"9858_CR19","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1023\/A:1008937911390","volume":"8","author":"D Fox","year":"2000","unstructured":"Fox, D., Burgard, W., Kruppa, H., & Thrun, S. (2000). A probabilistic approach to collaborative multi-robot localization. Autonomous Robots, 8(3), 325\u2013344.","journal-title":"Autonomous Robots"},{"key":"9858_CR20","unstructured":"Goldreich, O. (2011). Finding the shortest move-sequence in the graph-generalized 15-puzzle is np-hard. Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation (pp. 1\u20135). Berlin: Springer."},{"key":"9858_CR21","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-009-9290-7","volume":"58","author":"G Goraly","year":"2010","unstructured":"Goraly, G., & Hassin, R. (2010). Multi-color pebble motion on graph. Algorithmica, 58, 610\u2013636.","journal-title":"Algorithmica"},{"issue":"11","key":"9858_CR22","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1177\/0278364905059067","volume":"24","author":"EJ Griffith","year":"2005","unstructured":"Griffith, E. J., & Akella, S. (2005). Coordinating multiple droplets in planar array digital microfluidic systems. International Journal of Robotics Research, 24(11), 933\u2013949.","journal-title":"International Journal of Robotics Research"},{"key":"9858_CR23","unstructured":"Guo, Y., & Parker, L. E. (2002). A distributed and optimal motion planning approach for multiple mobile robots. In Proceedings IEEE international conference on robotics and automation, (pp. 2612\u20132619)."},{"issue":"3\u20134","key":"9858_CR24","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s004539910025","volume":"26","author":"D Halperin","year":"2000","unstructured":"Halperin, D., Latombe, J. C., & Wilson, R. (2000). A general framework for assembly planning: The motion space approach. Algorithmica, 26(3\u20134), 577\u2013601.","journal-title":"Algorithmica"},{"key":"9858_CR25","unstructured":"Han, S. D., Rodriguez, E. J., & Yu, J. (2018). Sear: A polynomial-time expected constant-factor optimal algorithmic framework for multi-robot path planning. In Proceedings IEEE\/RSJ international conference on intelligent robots and systems."},{"issue":"1","key":"9858_CR26","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"RA Hearn","year":"2005","unstructured":"Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1), 72\u201396.","journal-title":"Theoretical Computer Science"},{"key":"9858_CR27","doi-asserted-by":"crossref","unstructured":"H\u00f6nig, W., Kumar, T. S., Cohen, L., Ma, H., Xu, H., Ayanian, N., & Koenig, S. (2016). Multi-agent path finding with kinematic constraints. In ICAPS, (pp. 477\u2013485).","DOI":"10.1609\/icaps.v26i1.13796"},{"issue":"4","key":"9858_CR28","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1177\/027836498400300405","volume":"3","author":"JE Hopcroft","year":"1984","unstructured":"Hopcroft, J. E., Schwartz, J. T., & Sharir, M. (1984). On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the \u201cwarehouseman\u2019s problem\u201d. The International Journal of Robotics Research, 3(4), 76\u201388.","journal-title":"The International Journal of Robotics Research"},{"key":"9858_CR29","unstructured":"Jansen, R., & Sturtevant, N. (2008). A new approach to cooperative pathfinding. In iInternational conference on autonomous agents and multiagent systems, (pp. 1401\u20131404)."},{"key":"9858_CR30","doi-asserted-by":"crossref","unstructured":"Jennings, J. S., Whelan, G., & Evans, W. F. (1997). Cooperative search and rescue with a team of mobile robots. In Proceedings IEEE international conference on robotics and automation.","DOI":"10.1109\/ICAR.1997.620182"},{"key":"9858_CR31","doi-asserted-by":"crossref","unstructured":"Katsev, M., Yu, J., & LaValle, S. M. (2013). Efficient formation path planning on large graphs. In Proceedings IEEE international conference on robotics and automation, (pp 3606\u20133611).","DOI":"10.1109\/ICRA.2013.6631083"},{"issue":"1","key":"9858_CR32","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1177\/027836498600500106","volume":"5","author":"O Khatib","year":"1986","unstructured":"Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90\u201398.","journal-title":"The International Journal of Robotics Research"},{"issue":"4","key":"9858_CR33","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1109\/TRO.2006.878952","volume":"22","author":"S Kloder","year":"2006","unstructured":"Kloder, S., & Hutchinson, S. (2006). Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics, 22(4), 650\u2013665.","journal-title":"IEEE Transactions on Robotics"},{"key":"9858_CR34","unstructured":"Knepper, R. A., & Rus, D. (2012). Pedestrian-inspired sampling-based multi-robot collision avoidance. In 2012 IEEE RO-MAN: The 21st IEEE international symposium on robot and human interactive communication, (pp. 94\u2013100). IEEE."},{"key":"9858_CR35","doi-asserted-by":"crossref","unstructured":"Kornhauser, D. M. (1984). Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. PhD thesis, Massachusetts Institute of Technology.","DOI":"10.1109\/SFCS.1984.715921"},{"key":"9858_CR36","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2, 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"6","key":"9858_CR37","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1109\/70.736775","volume":"14","author":"SM LaValle","year":"1998","unstructured":"LaValle, S. M., & Hutchinson, S. A. (1998). Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation, 14(6), 912\u2013925.","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"9858_CR38","unstructured":"Luna, R., & Bekris, K. E. (2011). Push and swap: Fast cooperative path-finding with completeness guarantees. In Proceedings international joint conference on artificial intelligence, (pp 294\u2013300)."},{"key":"9858_CR39","unstructured":"Ma, H., Li, J., Kumar, T., & Koenig, S. (2017). Lifelong multi-agent path finding for online pickup and delivery tasks. In Proceedings of the 16th conference on autonomous agents and multiagent systems, international foundation for autonomous agents and multiagent systems, (pp. 837\u2013845)."},{"key":"9858_CR40","doi-asserted-by":"crossref","unstructured":"Matari\u0107, M. J., Nilsson, M., & Simsarian, K. T. (1995). Cooperative multi-robot box pushing. In Proceedings IEEE\/RSJ international conference on intelligent robots and systems, (pp. 556\u2013561).","DOI":"10.1109\/IROS.1995.525940"},{"key":"9858_CR41","volume-title":"Theory of automatic robot assembly and programming","author":"B Nnaji","year":"1992","unstructured":"Nnaji, B. (1992). Theory of automatic robot assembly and programming. London: Chapman & Hall."},{"key":"9858_CR42","doi-asserted-by":"crossref","unstructured":"Poduri, S., & Sukhatme, G. S. (2004). Constrained coverage for mobile sensor networks. In Proceedings IEEE international conference on robotics and automation.","DOI":"10.1109\/ROBOT.2004.1307146"},{"key":"9858_CR43","doi-asserted-by":"crossref","unstructured":"Qutub, S., Alami, R., & Ingrand, F. (1997). How to solve deadlock situations within the plan-merging paradigm for multi-robot cooperation. In Intelligent robots and systems, 1997. IROS\u201997., Proceedings of the 1997 IEEE\/RSJ international conference on, (vol.\u00a03, pp 1610\u20131615). IEEE.","DOI":"10.1109\/IROS.1997.656573"},{"key":"9858_CR44","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D Ratner","year":"1990","unstructured":"Ratner, D., & Warmuth, M. (1990). The $$(n^2-1)$$-puzzle and related relocation problems. Journal of Symbolic Computation, 10, 111\u2013137.","journal-title":"Journal of Symbolic Computation"},{"key":"9858_CR45","unstructured":"Reif, J. H. (1985). Complexity of the generalized mover\u2019s problem. Tech. rep., DTIC Document"},{"key":"9858_CR46","doi-asserted-by":"crossref","unstructured":"Rodriguez, S., Amato, N. M. (2010). Behavior-based evacuation planning. In Proceedings IEEE international conference on robotics and automation, (pp. 350\u2013355).","DOI":"10.1109\/ROBOT.2010.5509502"},{"key":"9858_CR47","doi-asserted-by":"crossref","unstructured":"Rus, D., Donald, B., & Jennings, J. (1995). Moving furniture with teams of autonomous robots. In Proceedings IEEE\/RSJ international conference on intelligent robots and systems, (pp. 235\u2013242).","DOI":"10.1109\/IROS.1995.525802"},{"key":"9858_CR48","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":"9858_CR49","doi-asserted-by":"crossref","unstructured":"Saha, M., & Isto, P. (2006). Multi-robot motion planning by incremental coordination. In 2006 IEEE\/RSJ international conference on intelligent robots and systems, (pp. 5960\u20135963). IEEE.","DOI":"10.1109\/IROS.2006.282536"},{"key":"9858_CR50","unstructured":"Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2012). Conflict-based search for optimal multi-agent path finding. In Proceedings of the twenty-sixth AAAI conference on artificial intelligence."},{"key":"9858_CR51","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1016\/j.artint.2012.11.006","volume":"195","author":"G Sharon","year":"2013","unstructured":"Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2013). The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence, 195, 470\u2013495.","journal-title":"Artificial Intelligence"},{"key":"9858_CR52","doi-asserted-by":"crossref","unstructured":"Shucker, B., Murphey, T., & Bennett, J. K. (2007). Switching rules for decentralized control with simple control laws. In American control conference, (pp. 1485\u20131492).","DOI":"10.1109\/ACC.2007.4282736"},{"key":"9858_CR53","unstructured":"Silver, D. (2005), Cooperative pathfinding. In The 1st conference on artificial intelligence and interactive digital entertainment, (pp. 23\u201328)."},{"issue":"3","key":"9858_CR54","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/s11036-009-0153-x","volume":"14","author":"B Smith","year":"2009","unstructured":"Smith, B., Egerstedt, M., & Howard, A. (2009). Automatic generation of persistent formations for multi-agent networks under range constraints. ACM\/Springer Mobile Networks and Applications Journal, 14(3), 322\u2013335.","journal-title":"ACM\/Springer Mobile Networks and Applications Journal"},{"key":"9858_CR55","unstructured":"Solovey, K., & Halperin, D. (2012). $$k$$-color multi-robot motion planning. In Proceedings workshop on algorithmic foundations of robotics."},{"key":"9858_CR56","unstructured":"Solovey, K., & Halperin, D. (2015). On the hardness of unlabeled multi-robot motion planning. In Robotics: Science and systems (RSS)."},{"key":"9858_CR57","unstructured":"Solovey, K., Yu, J., Zamir, O., & Halperin, D. (2015). Motion planning for unlabeled discs with optimality guarantees. In Robotics: Science and systems."},{"issue":"1","key":"9858_CR58","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(84)90130-3","volume":"19","author":"P Spirakis","year":"1984","unstructured":"Spirakis, P., & Yap, C. K. (1984). Strong NP-hardness of moving many discs. Information Processing Letters, 19(1), 55\u201359.","journal-title":"Information Processing Letters"},{"key":"9858_CR59","unstructured":"Standley, T., & Korf, R. (2011). Complete algorithms for cooperative pathfinding problems. In Proceedings international joint conference on artificial intelligence, (pp. 668\u2013673)."},{"key":"9858_CR60","doi-asserted-by":"crossref","unstructured":"Surynek, P. (2012). Towards optimal cooperative path planning in hard setups through satisfiability solving. In Proceedings 12th pacific rim international conference on artificial intelligence.","DOI":"10.1007\/978-3-642-32695-0_50"},{"issue":"3","key":"9858_CR61","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/TRA.2004.825275","volume":"20","author":"H Tanner","year":"2004","unstructured":"Tanner, H., Pappas, G., & Kumar, V. (2004). Leader-to-formation stability. IEEE Transactions on Robotics and Automation, 20(3), 443\u2013455.","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"1","key":"9858_CR62","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1177\/0278364913515307","volume":"33","author":"M Turpin","year":"2014","unstructured":"Turpin, M., Mohta, K., Michael, N., & Kumar, V. (2014). CAPT: Concurrent assignment and planning of trajectories for multiple robots. International Journal of Robotics Research, 33(1), 98\u2013112.","journal-title":"International Journal of Robotics Research"},{"key":"9858_CR63","doi-asserted-by":"crossref","unstructured":"van\u00a0den Berg, J., Lin, M. C., & Manocha, D. (2008). Reciprocal velocity obstacles for real-time multi-agent navigation. In Proceedings IEEE international conference on robotics and automation, (pp. 1928\u20131935).","DOI":"10.1109\/ROBOT.2008.4543489"},{"key":"9858_CR64","unstructured":"van\u00a0den Berg, J., Snoeyink, J., Lin, M., & Manocha, D. (2009). Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In Robotics: Science and systems."},{"key":"9858_CR65","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset, H. (2011). M*: A complete multirobot path planning algorithm with performance bounds. In Proceedings IEEE\/RSJ international conference on intelligent robots and systems, (pp. 3260\u20133267).","DOI":"10.1109\/IROS.2011.6095022"},{"key":"9858_CR66","unstructured":"Yu, J. (2013). A linear time algorithm for the feasibility of pebble motion on graphs. arXiv:1301.2342 ."},{"issue":"1","key":"9858_CR67","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1109\/LRA.2015.2503143","volume":"1","author":"J Yu","year":"2016","unstructured":"Yu, J. (2016). Intractability of optimal multi-robot path planning on planar graphs. IEEE Robotics and Automation Letters, 1(1), 33\u201340.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"9858_CR68","doi-asserted-by":"crossref","unstructured":"Yu, J. (2017). Expected constant-factor optimal multi-robot path planning in well-connected environments. In Multi-robot and multi-agent systems (MRS), 2017 international symposium on, (pp. 48\u201355). IEEE.","DOI":"10.1109\/MRS.2017.8250930"},{"key":"9858_CR69","doi-asserted-by":"crossref","unstructured":"Yu, J., & LaValle, S. M. (2013a). Multi-agent path planning and network flow. In Algorithmic foundations of robotics X, Springer tracts in advanced robotics (Vol. 86, pp. 157\u2013173). Berlin\/Heidelberg: Springer.","DOI":"10.1007\/978-3-642-36279-8_10"},{"key":"9858_CR70","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S. M. (2013b). Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings AAAI national conference on artificial intelligence, (pp. 1444\u20131449).","DOI":"10.1609\/aaai.v27i1.8541"},{"issue":"5","key":"9858_CR71","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1109\/TRO.2016.2593448","volume":"32","author":"J Yu","year":"2016","unstructured":"Yu, J., & LaValle, S. M. (2016). Optimal multi-robot path planning on graphs: Complete algorithms and effective heuristics. IEEE Transactions on Robotics, 32(5), 1163\u20131177.","journal-title":"IEEE Transactions on Robotics"},{"key":"9858_CR72","unstructured":"Yu, J., & Rus, D. (2015). Pebble motion on graphs with rotations: Efficient feasibility tests and planning. In Algorithmic foundations of robotics XI, Springer tracts in advanced robotics (vol. 107, pp. 729\u2013746). Berlin\/Heidelberg: Springer."}],"container-title":["Autonomous Robots"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-019-09858-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10514-019-09858-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10514-019-09858-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T20:16:28Z","timestamp":1694895388000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10514-019-09858-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":72,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["9858"],"URL":"https:\/\/doi.org\/10.1007\/s10514-019-09858-z","relation":{},"ISSN":["0929-5593","1573-7527"],"issn-type":[{"type":"print","value":"0929-5593"},{"type":"electronic","value":"1573-7527"}],"subject":[],"published":{"date-parts":[[2019,5,21]]},"assertion":[{"value":"23 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}