{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T01:03:00Z","timestamp":1773622980392,"version":"3.50.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319165943","type":"print"},{"value":"9783319165950","type":"electronic"}],"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_34","type":"book-chapter","created":{"date-parts":[[2015,4,29]],"date-time":"2015-04-29T13:42:10Z","timestamp":1430314930000},"page":"591-607","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Finding a Needle in an Exponential Haystack: Discrete RRT for Exploration of Implicit Roadmaps in Multi-robot Motion Planning"],"prefix":"10.1007","author":[{"given":"Kiril","family":"Solovey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,30]]},"reference":[{"key":"34_CR1","unstructured":"PQP\u2014A Proximity Query Package. http:\/\/gamma.cs.unc.edu\/SSV\/"},{"key":"34_CR2","unstructured":"Graph Product: Wikipedia, The Free Encyclopedia. http:\/\/en.wikipedia.org\/wiki\/Graph_product (2013)"},{"key":"34_CR3","unstructured":"Adler, A., de Berg, M., Halperin, D., Solovey, K.: Efficient multi-robot motion planning for unlabeled discs in simple polygons. CoRR arXiv:1312.1038 (2013)"},{"issue":"4","key":"34_CR4","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."},{"key":"34_CR5","doi-asserted-by":"crossref","unstructured":"Auletta, V., Monti, A., Parente, M., Persiano, P.: A linear time algorithm for the feasibility of pebble motion on trees. In: SWAT, pp. 259\u2013270 (1996)","DOI":"10.1007\/3-540-61422-2_137"},{"key":"34_CR6","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Overmars, M.: Prioritized motion planning for multiple robots. In: IROS, pp. 430\u2013435 (2005)","DOI":"10.1109\/IROS.2005.1545306"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: RSS (2009)","DOI":"10.15607\/RSS.2009.V.018"},{"key":"34_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)","edition":"3"},{"key":"34_CR9","unstructured":"Branicky, M.S., Curtiss, M.M., Levine, J.A., Morgan, S.B.: RRTs for nonlinear, discrete, and hybrid planning and control. In: Decision and Control, pp. 9\u201312 (2003)"},{"key":"34_CR10","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"H Choset","year":"2005","unstructured":"Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, G., Kavraki, L., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, Cambridge (2005)"},{"issue":"4","key":"34_CR11","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1109\/MRA.2012.2205651","volume":"19","author":"IA \u015eucan","year":"2012","unstructured":"\u015eucan, I.A., Moll, M., Kavraki, L.E.: The open motion planning library. IEEE Robot. Autom. Mag. 19(4), 72\u201382 (2012)","journal-title":"IEEE Robot. Autom. Mag."},{"issue":"3","key":"34_CR12","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"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"Hirsch, S., Halperin, D.: Hybrid motion planning: coordinating two discs moving among polygonal obstacles in the plane. In: WAFR, pp. 239\u2013255. Springer, New York (2002)","DOI":"10.1007\/978-3-540-45058-0_15"},{"issue":"4","key":"34_CR14","first-page":"76","volume":"3","author":"J Hopcroft","year":"1984","unstructured":"Hopcroft, J., Schwartz, J., Sharir, M.: On the complexity of motion planning for multiple independent objects; PSPACE-hardness of the \u201cWarehouseman\u2019s Problem\u201d. IJRR 3(4), 76\u201388 (1984)","journal-title":"IJRR"},{"issue":"7","key":"34_CR15","first-page":"846","volume":"30","author":"S Karaman","year":"2011","unstructured":"Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. IJRR 30(7), 846\u2013894 (2011)","journal-title":"IJRR"},{"issue":"4","key":"34_CR16","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.: 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":"34_CR17","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":"34_CR18","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":"34_CR19","doi-asserted-by":"crossref","unstructured":"Kuffner, J.J., LaValle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: ICRA, pp. 995\u20131001 (2000)","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"34_CR20","doi-asserted-by":"crossref","unstructured":"Kuffner, J.J.: Effective sampling and distance metrics for 3D rigid body path planning. In: ICRA, pp. 3993\u20133998 (2004)","DOI":"10.1109\/ROBOT.2004.1308895"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)","DOI":"10.1017\/CBO9780511546877"},{"key":"34_CR22","unstructured":"Leroy, S., Laumond, J.P., Simeon, T.: Multiple path coordination for mobile robots: a geometric algorithm. In: IJCAI, pp. 1118\u20131123 (1999)"},{"key":"34_CR23","unstructured":"Luna, R., Bekris, K.E.: Push and swap: fast cooperative path-finding with completeness guarantees. In: IJCAI, pp. 294\u2013300 (2011)"},{"key":"34_CR24","unstructured":"Muja, M., Lowe, D.G.: Fast approximate nearest neighbors with automatic algorithm configuration. In: VISSAPP, pp. 331\u2013340. INSTICC Press (2009)"},{"key":"34_CR25","volume-title":"Heuristics: Intelligent Search Strategies for Computer Problem Solving","author":"J Pearl","year":"1984","unstructured":"Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading (1984)"},{"key":"34_CR26","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. In: WAFR, pp. 313\u2013329 (2012)","DOI":"10.1007\/978-3-642-36279-8_19"},{"key":"34_CR27","doi-asserted-by":"crossref","unstructured":"Sanchez, G., Latombe, J.C.: Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: ICRA, pp. 2112\u20132119 (2002)","DOI":"10.1109\/ROBOT.2002.1014852"},{"key":"34_CR28","doi-asserted-by":"crossref","unstructured":"Schwartz, J.T., Sharir, M.: On the piano movers\u2019 problem: III. Coordinating the motion of several independent bodies. IJRR 2(3), 46\u201375 (1983)","DOI":"10.1177\/027836498300200304"},{"issue":"1","key":"34_CR29","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":"34_CR30","doi-asserted-by":"crossref","unstructured":"Solovey, K., Halperin, D.: $$k$$-color multi-robot motion planning. In: WAFR, pp. 191\u2013207 (2012)","DOI":"10.1007\/978-3-642-36279-8_12"},{"issue":"1","key":"34_CR31","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":"34_CR32","unstructured":"Turpin, M., Michael, N., Kumar, V.: Computationally efficient trajectory planning and task assignment for large teams of unlabeled robots. In: ICRA, pp. 834\u2013840 (2013)"},{"key":"34_CR33","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.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23, 125\u2013152 (1998)","journal-title":"Robot. Auton. Syst."},{"key":"34_CR34","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset, H.: M*: a complete multirobot path planning algorithm with performance bounds. In: IROS, pp. 3260\u20133267. IEEE (2011)","DOI":"10.1109\/IROS.2011.6095022"},{"key":"34_CR35","doi-asserted-by":"crossref","unstructured":"Wagner, G., Kang, M., Choset, H.: Probabilistic path planning for multiple robots with subdimensional expansion. In: ICRA, pp. 2886\u20132892 (2012)","DOI":"10.1109\/ICRA.2012.6225297"},{"key":"34_CR36","unstructured":"Yap, C.: Coordinating the motion of several discs. Technical report, Courant Institute of Mathematical Sciences, Michigan State University, New York (1984)"}],"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_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T17:34:02Z","timestamp":1748367242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-16595-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319165943","9783319165950"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-16595-0_34","relation":{},"ISSN":["1610-7438","1610-742X"],"issn-type":[{"value":"1610-7438","type":"print"},{"value":"1610-742X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}