{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T21:55:21Z","timestamp":1786139721733,"version":"3.56.0"},"reference-count":45,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2015,9,20]],"date-time":"2015-09-20T00:00:00Z","timestamp":1442707200000},"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,6]]},"abstract":"<jats:p>\n                    Dynamic environments have obstacles that unpredictably appear, disappear, or move. We present the first sampling-based replanning algorithm that is asymptotically optimal and single-query (designed for situation in which a priori offline computation is unavailable). Our algorithm, RRT\n                    <jats:sup>X<\/jats:sup>\n                    , refines and repairs the same search-graph over the entire duration of navigation (in contrast to previous single-query replanning algorithms that prune and then regrow some or all of the search-tree). Whenever obstacles change and\/or the robot moves, a graph rewiring cascade quickly remodels the existing search-graph and repairs its shortest-path-to-goal sub-tree to reflect the new information. Both graph and tree are built directly in the robot\u2019s state-space; thus, the resulting plan(s) respect the kinematics of the robot and continue to improve during navigation. RRT\n                    <jats:sup>X<\/jats:sup>\n                    is probabilistically complete and makes no distinction between local and global planning, yet it reacts quickly enough for real-time high-speed navigation through unpredictably changing environments. Low information transfer time is essential for enabling RRT\n                    <jats:sup>X<\/jats:sup>\n                    to react quickly in dynamic environments; we prove that the information transfer time required to inform a graph of size n about an \u03b5-cost decrease is O( n log n) for RRT\n                    <jats:sup>X<\/jats:sup>\n                    \u2014faster than other current asymptotically optimal single-query algorithms (we prove RRT* is [Formula: see text] and RRT\n                    <jats:sup>#<\/jats:sup>\n                    is [Formula: see text]( n log\n                    <jats:sup>2<\/jats:sup>\n                    n)). In static environments RRT\n                    <jats:sup>X<\/jats:sup>\n                    has the same amortized runtime as RRT and RRT*, \u0398(log n), and is faster than RRT\n                    <jats:sup>#<\/jats:sup>\n                    , [Formula: see text](log\n                    <jats:sup>2<\/jats:sup>\n                    n). In order to achieve O(log n) iteration time, each node maintains a set of O(log n) expected neighbors, and the search-graph maintains \u03b5-consistency for a predefined \u03b5. Experiments and simulations confirm our theoretical analysis and demonstrate that RRT\n                    <jats:sup>X<\/jats:sup>\n                    is useful in both static and dynamic environments.\n                  <\/jats:p>","DOI":"10.1177\/0278364915594679","type":"journal-article","created":{"date-parts":[[2015,9,21]],"date-time":"2015-09-21T20:10:35Z","timestamp":1442866235000},"page":"797-822","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":219,"title":["RRT\n                    <sup>X<\/sup>\n                    : Asymptotically optimal single-query sampling-based motion planning with quick replanning"],"prefix":"10.1177","volume":"35","author":[{"given":"Michael","family":"Otte","sequence":"first","affiliation":[{"name":"Laboratory for Information and Decision, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emilio","family":"Frazzoli","sequence":"additional","affiliation":[{"name":"Laboratory for Information and Decision, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2015,9,20]]},"reference":[{"key":"bibr1-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"bibr2-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363069"},{"key":"bibr3-0278364915594679","first-page":"613","volume-title":"15th Australian international aerospace congress (AIAC\u201815)","author":"Bertola A","year":"2013"},{"key":"bibr4-0278364915594679","volume-title":"Optimizations for sampling-based motion planning algorithms","author":"Bialkowski J","year":"2014"},{"key":"bibr5-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr6-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/IRDS.2002.1041624"},{"key":"bibr7-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1641879"},{"key":"bibr8-0278364915594679","first-page":"388","volume-title":"IEEE\/RSJ international conference on intelligent robots and systems (IROS\u201803)","volume":"1","author":"Fraichard T","year":"2003"},{"key":"bibr9-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.852260"},{"key":"bibr10-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363167"},{"key":"bibr11-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-011-9254-z"},{"key":"bibr12-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556421"},{"key":"bibr13-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"bibr14-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr15-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr16-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912456444"},{"key":"bibr17-0278364915594679","first-page":"476","volume-title":"18th national conference on artificial intelligence","author":"Koenig S","year":"2002"},{"key":"bibr18-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2003.12.001"},{"key":"bibr19-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152860"},{"key":"bibr20-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2008.2012116"},{"key":"bibr21-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr22-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr23-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908099462"},{"key":"bibr24-0278364915594679","volume-title":"Algorithmic and Computational Robotics: New Directions 2000 WAFR","author":"Leven P","year":"2001"},{"key":"bibr25-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364902021012001"},{"key":"bibr26-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909340445"},{"key":"bibr27-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2234312"},{"key":"bibr28-0278364915594679","first-page":"1131","volume-title":"IEEE conference on automation science and engineering","author":"Martin SR","year":"2007"},{"key":"bibr29-0278364915594679","volume-title":"Any-com multi-robot path planning","author":"Otte M","year":"2011"},{"key":"bibr30-0278364915594679","volume-title":"International workshop on the algorithmic foundations of robotics","author":"Otte M","year":"2014"},{"key":"bibr31-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2007.4399343"},{"key":"bibr32-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20285"},{"key":"bibr33-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2047820"},{"key":"bibr34-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/CINTI.2013.6705245"},{"key":"bibr35-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.36"},{"key":"bibr36-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/70.163777"},{"key":"bibr37-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907543"},{"key":"bibr38-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914556517"},{"key":"bibr39-0278364915594679","volume-title":"39th international symposium on robotics (ISR\u201808)","author":"Sermanet P","year":"2008"},{"key":"bibr40-0278364915594679","first-page":"1652","volume-title":"International joint conference on artificial intelligence","author":"Stentz A","year":"1995"},{"key":"bibr41-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.1994.639469"},{"key":"bibr42-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910369189"},{"key":"bibr43-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915576491"},{"key":"bibr44-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-009-9151-x"},{"key":"bibr45-0278364915594679","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363553"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915594679","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915594679","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915594679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:21Z","timestamp":1777457721000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915594679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,20]]},"references-count":45,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1177\/0278364915594679"],"URL":"https:\/\/doi.org\/10.1177\/0278364915594679","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,20]]}}}