RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning. (June 2016) - Otte, Michael; Frazzoli, Emilio
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.