RT-RRT: Reverse Tree Guided Real-Time Path Planning/Replanning in Unpredictable Dynamic Environments

摘要

Path planning in unpredictable dynamic environments remains a challenging problem due to the unpredictable appearance, disappearance, and movement of dynamic obstacles during navigation. To address this problem, we propose a reverse tree guided rapid exploration random tree (RTRRT) algorithm that can efficiently perform navigation tasks in dynamic environments. The method first constructs a reverse tree rooted as goal state to search for an initial path. If a collision occurs on the path, The RT-RRT constructs a forward tree rooted as the current robot state in the same configuration space, until it connects with the reverse tree to find a new path. Furthermore, The RT-RRT improves the tree construction method and designs a path optimization strategy to reduce the path cost. The method is validated in different scenarios and has excellent navigation capabilities in unpredictable dynamic environments. In the same scenarios, the RT-RRT algorithm improves the success rate by 16.7%, reduces the path length by 20.54% and reduces the travel time by 10X compared to the RRT<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</sup> algorithm with the same number of samples.