RRT X : Asymptotically optimal single-query sampling-based motion planning with quick replanning

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 Formula: see text and RRT # is Formula: see text( 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 # , Formula: see text(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.