IROS Paper Review: RT-RRT Bidirectional Tree Planning for Dynamic Scenes
In dynamic environments, UAVs often fall into path planning difficulties due to the random appearance and movement of obstacles. Cui Bo, School of Navigation, Northwestern Polytechnical University, proposed a bidirectional tree real-time planning algorithm RT-RRT, and in Prometheus The algorithm was verified in the simulation platform, and the results showed that RT-RRT improved the path planning efficiency by 10 times and the success rate by 16.7%. This paper has been accepted by IROS 2024, the top conference in the field of robotics
Drawbacks of traditional algorithms
▪ For reverse tree (starting from the target point) algorithms such as RRTX, tree repair relies on neighbor state iteration. It is easy to fail if there are few samples, and it will take a long time if there are too many samples. ▪ Dynamic obstacles lead to frequent path interruptions and global re-planning is inefficient.
Innovation of RT-RRT
▪ Two-way tree mechanism: The reverse tree starts from the target point and pre-explores the global path. When the forward tree encounters an obstacle, it quickly "opens a new path" from the current position and connects the reverse tree. ▪ Path optimization strategy: Redundant nodes are eliminated through the dichotomy method, and the path is shortened by more than 20\%.
Three-step dismantling of RT-RRT algorithm
Reverse tree pre-layout
▪ Before the UAV takes off, the reverse tree starts from the target point and spreads around to generate multiple potential paths. ▪ Prioritize path branches close to the UAV to reduce subsequent connection distances.
Forward tree dynamic connection
▪ As shown in the figure above: When the sensor detects a new obstacle (such as a moving vehicle), a T+ tree is grown from the UAV's current position (xbot(t)), and T- is actively connected. ▪ After the connection is successful, reversely write the T+ branch to T- to generate a new path.
Path optimization
If there are "detours" in the new path, the algorithm automatically performs bisection sampling at the turning point to find a shorter safe path. The path length is shortened by an average of 20.54%, which is close to the theoretical optimal solution.
Simulation verification
The AMOVLAB Prometheus open-source platform provides a "test flight ground" for algorithm verification for the RT-RRT algorithm and becomes the core bridge for the paper's results from theory to application.
Multi-sensor simulation
Gazebo restores 1:1 UAV binocular cameras, LiDAR, IMU and other sensors.
Dynamic obstacle engine
Supports random generation of obstacles and programming of movement trajectories (speed and direction are adjustable), reproducing the "unpredictable dynamic environment" mentioned in the article.
Experimental results
Through the reproduction of simulation scenes such as mazes, passages, and moving obstacles, as well as experiments on contrasting scenes of empty fields, simple fields, passage fields, and chaotic fields, the efficient and robust path planning capabilities of the RT-RRT algorithm in dynamic environments are demonstrated. Experiments show that this algorithm can shorten the path, reduce the time and improve the success rate, and can effectively deal with unpredictable obstacle changes.
Paper details
theme:RT-RRT: Reverse Tree Guided Real-Time Path Planning/Replanning in Unpredictable Dynamic Environments
Meeting: 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)DOI: 10.1109/IROS58592.2024.10802722
Paper link: https://ieeexplore.ieee.org/document/10802722/
