{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:41:44Z","timestamp":1762101704917,"version":"3.41.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319165943"},{"type":"electronic","value":"9783319165950"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-16595-0_1","type":"book-chapter","created":{"date-parts":[[2015,4,29]],"date-time":"2015-04-29T13:42:10Z","timestamp":1430314930000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Multi-robot Motion Planning for Unlabeled Discs in Simple Polygons"],"prefix":"10.1007","author":[{"given":"Aviv","family":"Adler","sequence":"first","affiliation":[]},{"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[]},{"given":"Kiril","family":"Solovey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,30]]},"reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/PL00009476","volume":"22","author":"B Aronov","year":"1999","unstructured":"Aronov, B., de Berg, M., van der Stappen, A.F., \u0160vestka, P., Vleugels, J.: Motion planning for multiple robots. Discret. Comput. Geom. 22(4), 505\u2013525 (1999)","journal-title":"Discret. Comput. Geom."},{"issue":"5","key":"1_CR2","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1142\/S0218195908002684","volume":"18","author":"S Bereg","year":"2008","unstructured":"Bereg, S., Dumitrescu, A., Pach, J.: Sliding disks in the plane. Int. J. Comput. Geom. Appl. 18(5), 373\u2013387 (2008)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"1_CR3","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.comgeo.2012.06.001","volume":"46","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Jiang, M.: On reconfiguration of disks in the plane and related problems. Comput. Geom.: Theory Appl. 46(3), 191\u2013202 (2013)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Shortest move-sequence in the generalized 15-puzzle is NP-hard. Manuscript, Laboratory for Computer Science, MIT 1 (1984)","DOI":"10.1007\/978-3-642-22670-0_1"},{"issue":"3","key":"1_CR5","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.: Multi-color pebble motion on graphs. Algorithmica 58(3), 610\u2013636 (2010)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"1_CR6","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.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theor. Comput. Sci. 343(1\u20132), 72\u201396 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Hirsch, S., Halperin, D.: Hybrid motion planning: coordinating two discs moving among polygonal obstacles in the plane. In: Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 239\u2013255. Springer, New York (2002)","DOI":"10.1007\/978-3-540-45058-0_15"},{"issue":"4","key":"1_CR8","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.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the warehouseman\u2019s problem. Int. J. Robot. Res. 3(4), 76\u201388 (1984)","journal-title":"Int. J. Robot. Res."},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","volume":"12","author":"LE Kavraki","year":"1996","unstructured":"Kavraki, L.E., \u0160vestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4), 566\u2013580 (1996)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discret. Comput. Geom. 1, 59\u201370 (1986)","journal-title":"Discret. Comput. Geom."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Kloder, S., Hutchinson, S.: Path planning for permutation-invariant multi-robot formations. In: ICRA, pp. 1797\u20131802 (2005)","DOI":"10.1109\/ROBOT.2005.1570374"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Kornhauser, D.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. M.Sc. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"1_CR13","unstructured":"Krontiris, A., Luna, R., Bekris, K.E.: From feasibility tests to path planners for multi-agent pathfinding. In: Symposium on Combinatorial Search (2013)"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Kuffner, J.J., Lavalle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: International Conference on Robotics and Automation (ICRA), pp. 995\u20131001 (2000)","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Raghavan, P., Sudan, M., Tamaki, H.: Motion planning on a graph. In: Foundations of Computer Science, pp. 511\u2013520 (1994)","DOI":"10.1109\/SFCS.1994.365740"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Salzman, O., Hemmer, M., Halperin, D.: On the power of manifold samples in exploring configuration spaces and the dimensionality of narrow passages to appear, Workshop on the Algorithmic Foundations of Robotics (WAFR) (2012)","DOI":"10.1007\/978-3-642-36279-8_19"},{"key":"1_CR17","unstructured":"Sanchez, G., Latombe, J.C.: Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: International Conference on Robotics and Automation (ICRA) (2002)"},{"issue":"3","key":"1_CR18","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0196-8858(83)90014-3","volume":"4","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J.T., Sharir, M.: On the piano movers problem: II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4(3), 298\u2013351 (1983)","journal-title":"Adv. Appl. Math."},{"issue":"3","key":"1_CR19","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1177\/027836498300200304","volume":"2","author":"JT Schwartz","year":"1983","unstructured":"Schwartz, J.T., Sharir, M.: On the piano movers problem: III. Coordinating the motion of several independent bodies. Int. J. Robot. Res. 2(3), 46\u201375 (1983)","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"1_CR20","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF01530889","volume":"3","author":"M Sharir","year":"1991","unstructured":"Sharir, M., Sifrony, S.: Coordinated motion planning for two independent robots. Ann. Math. Artif. Intell. 3(1), 107\u2013130 (1991)","journal-title":"Ann. Math. Artif. Intell."},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Solovey, K., Halperin, D.: $$k$$-color multi-robot motion planning. Int. J. Robot. Res. (2013, in press (already appeared on-line))","DOI":"10.1007\/978-3-642-36279-8_12"},{"key":"1_CR22","unstructured":"Solovey, K., Salzman, O., Halperin, D.: Finding a needle in an exponential haystack: discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. CoRR 1305.2889 (2013)"},{"issue":"1","key":"1_CR23","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0020-0190(84)90130-3","volume":"19","author":"PG Spirakis","year":"1984","unstructured":"Spirakis, P.G., Yap, C.K.: Strong NP-hardness of moving many discs. Inf. Process. Lett. 19(1), 55\u201359 (1984)","journal-title":"Inf. Process. Lett."},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0921-8890(97)00033-X","volume":"23","author":"P \u0160vestka","year":"1998","unstructured":"\u0160vestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23, 125\u2013152 (1998)","journal-title":"Robot. Auton. Syst."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Turpin, M., Michael, N., Kumar, V.: Concurrent assignment and planning of trajectories for large teams of interchangeable robots. In: International Conference on Robotics and Automation (ICRA), pp. 842\u2013848 (2013)","DOI":"10.1109\/ICRA.2013.6630671"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Snoeyink, J., Lin, M.C., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: Robotics: Science and Systems (RSS) (2009)","DOI":"10.15607\/RSS.2009.V.018"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset, H.: M*: A complete multirobot path planning algorithm with performance bounds. In: International Conference on Intelligent Robots and Systems (IROS), pp. 3260\u20133267 (2011)","DOI":"10.1109\/IROS.2011.6095022"},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"Wagner, G., Kang, M., Choset, H.: Probabilistic path planning for multiple robots with subdimensional expansion. In: International Conference on Robotics and Automation (ICRA), pp. 2886\u20132892 (2012)","DOI":"10.1109\/ICRA.2012.6225297"},{"key":"1_CR29","unstructured":"Yap, C.K.: Coordinating the motion of several discs. Technical report, Courant Institute of Mathematical Sciences, Michigan State University, New York (1984)"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle, S.M.: Distance optimal formation control on graphs with a tight convergence time guarantee. In: IEEE International Conference on Decision and Control, pp. 4023\u20134028 (2012)","DOI":"10.1109\/CDC.2012.6426233"}],"container-title":["Springer Tracts in Advanced Robotics","Algorithmic Foundations of Robotics XI"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-16595-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T17:33:50Z","timestamp":1748367230000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-16595-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319165943","9783319165950"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-16595-0_1","relation":{},"ISSN":["1610-7438","1610-742X"],"issn-type":[{"type":"print","value":"1610-7438"},{"type":"electronic","value":"1610-742X"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}