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 e-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~2n)). In static environments RRT~X has the same amortized runtime as RRT and RRT~*, Θ(log n), and is faster than RRT~#, ω(log~2n). 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.