RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning. (June 2016)

• Record Type: Journal Article
• Authors: Otte, Michael; Frazzoli, Emilio
• Is Part Of: International journal of robotics research. Volume 35:Number 7(2016:Jun.)
• Page Start: 797
• Page End: 822
• Publication Date: 2016-06
• Subjects: Real-time -- asymptotically optimal -- graph consistency -- motion planning -- replanning -- dynamic environments -- shortest-path; Robots -- Periodicals; Robots, Industrial -- Periodicals; 629.89205
• DOI: 10.1177/0278364915594679
• Languages: English
• ISSNs: 0278-3649

Abstract

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 X, 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's state-space; thus, the resulting plan(s) respect the kinematics of the robot and continue to improve during navigation. RRT X 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 X to react quickly in dynamic environments; we prove that the information transfer time required to inform a graph of size n about an ε -cost decrease is O ( n log n ) for RRT X —faster than other current asymptotically optimal single-query algorithms (we prove RRT* isΩ ( n ( n log n ) 1 / D ) and RRT # isω ( n log 2 n )). In static environments RRT X has the same amortized runtime as RRT and RRT*, Θ(log n ), and is faster than RRT #, ω (log 2 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 ε -consistency for a predefined ε . Experiments and simulations confirm our theoretical analysis and demonstrate that RRT X is useful in both static and dynamic environments.