{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T04:41:05Z","timestamp":1784004065334,"version":"3.55.0"},"reference-count":42,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2016,1,25]],"date-time":"2016-01-25T00:00:00Z","timestamp":1453680000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2016,4]]},"abstract":"<jats:p>We present a sampling-based framework for multi-robot motion planning. which combines an implicit representation of roadmaps for multi-robot motion planning with a novel approach for pathfinding in geometrically embedded graphs tailored for our setting. Our pathfinding algorithm, discrete-RRT (dRRT), is an adaptation of the celebrated RRT algorithm for the discrete case of a graph, and it enables a rapid exploration of the high-dimensional configuration space by carefully walking through an implicit representation of the tensor product of roadmaps for the individual robots. We demonstrate our approach experimentally on scenarios that involve as many as 60 degrees of freedom and on scenarios that require tight coordination between robots. On most of these scenarios our algorithm is faster by a factor of at least 10 when compared to existing algorithms that we are aware of.<\/jats:p>","DOI":"10.1177\/0278364915615688","type":"journal-article","created":{"date-parts":[[2016,1,25]],"date-time":"2016-01-25T22:29:07Z","timestamp":1453760947000},"page":"501-513","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":94,"title":["Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning"],"prefix":"10.1177","volume":"35","author":[{"given":"Kiril","family":"Solovey","sequence":"first","affiliation":[{"name":"Blavatnik School of Computer Science, Tel-Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oren","family":"Salzman","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel-Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel-Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2016,1,25]]},"reference":[{"key":"bibr1-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2015.2470096"},{"key":"bibr2-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009476"},{"key":"bibr3-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61422-2_137"},{"key":"bibr4-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2003.1272639"},{"key":"bibr5-0278364915615688","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset H","year":"2005"},{"key":"bibr6-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"bibr7-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630908"},{"key":"bibr8-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9290-7"},{"key":"bibr9-0278364915615688","volume-title":"Introduction to Probability","author":"Grinstead C","year":"2012"},{"key":"bibr10-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.008"},{"key":"bibr11-0278364915615688","first-page":"239","volume-title":"Algorithmic Foundations of Robotics V","author":"Hirsch S","year":"2002"},{"key":"bibr12-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"bibr13-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"bibr14-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr15-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr16-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2005.1570374"},{"key":"bibr17-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715921"},{"key":"bibr18-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308895"},{"key":"bibr19-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr20-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr21-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.770022"},{"key":"bibr22-0278364915615688","first-page":"1118","volume-title":"16th international joint conference on artificial intelligence (IJCAI\u201899)","author":"Leroy S","year":"1999"},{"key":"bibr23-0278364915615688","first-page":"294","volume-title":"22nd international joint conference on artificial intelligence (IJCAI\u201811)","author":"Luna R","year":"2011"},{"key":"bibr24-0278364915615688","first-page":"331","volume-title":"4th international conference on computer vision theory and applications (VISAPP\u201809)","author":"Muja M","year":"2009"},{"key":"bibr25-0278364915615688","volume-title":"Heuristics: Intelligent Search Strategies for Computer Problem Solving","author":"Pearl J","year":"1984"},{"key":"bibr26-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2014.2331983"},{"key":"bibr27-0278364915615688","author":"Salzman O","year":"2015","journal-title":"Computing Research Repository"},{"key":"bibr28-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2002.1014852"},{"key":"bibr29-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1177\/027836498300200304"},{"key":"bibr30-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530889"},{"key":"bibr31-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913506268"},{"key":"bibr32-0278364915615688","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.046"},{"key":"bibr33-0278364915615688","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.011"},{"key":"bibr34-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90130-3"},{"key":"bibr35-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"bibr36-0278364915615688","unstructured":"The CGAL Project (2011) CGAL User and Reference Manual. xxx: CGAL Editorial Board, edition3.9."},{"key":"bibr37-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-014-9412-1"},{"key":"bibr38-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2005.1545306"},{"key":"bibr39-0278364915615688","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.018"},{"key":"bibr40-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(97)00033-X"},{"key":"bibr41-0278364915615688","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.001"},{"key":"bibr42-0278364915615688","unstructured":"Yap C (1984) Coordinating the motion of several discs. Technical Report 105, Courant Institute of Mathematical Sciences, New York, USA."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915615688","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915615688","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915615688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:19Z","timestamp":1777457719000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915615688"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,25]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["10.1177\/0278364915615688"],"URL":"https:\/\/doi.org\/10.1177\/0278364915615688","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,25]]}}}