RRT~X: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles

摘要

We present RRT~X, the first asymptotically optimal sampling-based motion planning algorithm for real-time navigation in dynamic environments (containing obstacles that unpredictably appear, disappear, and move). Whenever obstacle changes are observed, e.g., by onboard sensors, a graph rewiring cascade quickly updates the search-graph and repairs its shortest-path-to-goal subtree. Both graph and tree are built directly in the robot's state space, respect the kinematics of the robot, and continue to improve during navigation. RRT~X is also competitive in static environments - where it has the same amortized per iteration 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 ∈.