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

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 $\Omega \left(\mathrm{n}{\left(\frac{\mathrm{n}}{\log \mathrm{n}}\right)}^{1/\mathrm{D}}\right)$ and RRT^# is $\omega$ (n log² n)). In static environments RRT^X has the same amortized runtime as RRT and RRT*, Θ(log n), and is faster than RRT^#, $\omega$ (log² 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.