Source-linked AI summary
RL-RRT: Kinodynamic Motion Planning via Learning Reachability Estimators from RL Policies
Hao-Tien Lewis Chiang, Jasmine Hsu, Marek Fiser, Lydia Tapia, Aleksandra Faust
TL;DR
Kinodynamic planning needs efficient ways to choose promising states and steer between them despite dynamics and obstacles. RL-RRT learns an obstacle-avoiding policy and an obstacle-aware reachability estimator, then uses them within RRT. Across three robots, it finds solutions faster and shorter than the reported baselines, while transferring to new environments.
Problem
Kinodynamic planners struggle to identify promising transition states and compute steering between them when dynamics and obstacles must be considered.
Method
RL-RRT trains an obstacle-avoiding RL policy as a local planner and controller, then trains a supervised estimator to predict its obstacle-aware Time To Reach for RRT guidance.
Results
Across three robots, RL-RRT finds solutions faster than SST, is up to 2.3 times more likely to identify a path within a fixed time budget, and produces paths up to 4.5 times shorter.
Takeaways & Limitations
The learned policy and reachability estimator transfer to new environments and replace expensive planning computations with neural-network inference.
Takeaways & Limitations
The reachability estimator uses local observations and can misclassify states affected by large-scale maze-like obstacle structures.
Abstract
from arXiv · showhide
This paper addresses two challenges facing sampling-based kinodynamic motion planning: a way to identify good candidate states for local transitions and the subsequent computationally intractable steering between these candidate states. Through the combination of sampling-based planning, a Rapidly Exploring Randomized Tree (RRT) and an efficient kinodynamic motion planner through machine learning, we propose an efficient solution to long-range planning for kinodynamic motion planning. First, we use deep reinforcement learning to learn an obstacle-avoiding policy that maps a robot's sensor observations to actions, which is used as a local planner during planning and as a controller during execution. Second, we train a reachability estimator in a supervised manner, which predicts the RL policy's time to reach a state in the presence of obstacles. Lastly, we introduce RL-RRT that uses the RL policy as a local planner, and the reachability estimator as the distance function to bias tree-growth towards promising regions. We evaluate our method on three kinodynamic systems, including physical robot experiments. Results across all three robots tested indicate that RL-RRT outperforms state of the art kinodynamic planners in efficiency, and also provides a shorter path finish time than a steering function free method. The learned local planner policy and accompanying reachability estimator demonstrate transferability to the previously unseen experimental environments, making RL-RRT fast because the expensive computations are replaced with simple neural network inference. Video: https://youtu.be/dDMVMTOI8KY
I. INTRODUCTION
Kinodynamic planners must find collision-free, dynamically feasible, and efficient paths, but steering functions and obstacle-aware distance estimates are difficult or expensive to compute. RL-RRT combines an obstacle-avoiding RL policy with a learned reachability estimator to guide RRT growth and plan efficiently.
- Kinodynamic plans must be collision-free, satisfy velocity and acceleration bounds, and efficiently reach the goal.
- Steering functions guide tree expansion toward specific states but require solving an generally NP-Hard optimal-control problem.
- Obstacle-aware state selection is difficult because optimal Time To Reach is expensive and conventional steering functions do not account for unseen obstacles.
- RL-RRT learns an obstacle-avoiding AutoRL policy, trains a supervised estimator for its obstacle-aware reachability time, and uses both during RRT planning.
- 74-80% accuracy identifies whether goal states are reachable, while RL-RRT is up to 2.3 times more likely to find paths and produces paths up to 4.5 times shorter than SST.
II. RELATED WORK
Prior kinodynamic planners either rely on difficult steering functions and expensive distance measures or randomly propagate actions and wander. RL-RRT learns both functions while incorporating obstacle avoidance into reachability estimation.
- Steering-function planners use a controller to pull the tree toward goals, but RL-RRT learns this steering function with AutoRL instead of solving the two-point boundary-value problem.
- Steering-function-free methods such as SST propagate random actions and can take a long time to find solutions because they tend to wander.
- Existing point-to-point obstacle-avoidance policies and hierarchical navigation methods were not designed for kinodynamic planning.
- Minimum Time To Reach is effective for sampling-based kinodynamic planning but often too computationally expensive, while prior learned approaches still require near-optimal steering functions.
- RL-RRT incorporates obstacle avoidance because obstacles can significantly change the minimum Time To Reach between states.
- RL-RRT uses the learned policy as a local planner and the reachability estimator as a distance function during planning.
A. AutoRL Local Planner
The AutoRL local planner is trained as an obstacle-avoiding point-to-point policy from noisy sensor observations to actions. The resulting policy supports local planning, execution, and reachability-data generation.
- The RL agent learns an obstacle-avoiding point-to-point task, producing a policy used for local planning, execution, and estimator data generation.
- AutoRL evolves reward functions over agent populations to maximize successful goal reaching without hand-tuning a fixed reward.
- All three robot policies share observations, goal definitions, and neural-network architectures but differ in dynamics and reward features.
- The Asteroid policy observes noisy lidar, relative goal position, velocity, and orientation, while its state includes planar position, velocity, and orientation.
- AutoRL tunes reward weights combining goal achievement, goal distance, collision, clearance, speed, step, and displacement terms.
- The obstacle-aware estimator learns Time To Reach for the RL policy, avoiding the need for an engineered near-optimal steering function and accounting for obstacles.
1) Training data collection:
RL-RRT collects supervised reachability data by rolling out an obstacle-avoiding policy and assigning each observation a cumulative future time-to-reach cost. The resulting labels distinguish successful goal-reaching trajectories from collisions or horizon failures.
- Each episode samples start and goal states, executes the policy until reaching the goal, colliding, or exceeding the time horizon, and records observations and costs.
- The per-step TTR cost is accumulated backward along each trajectory to produce one observation-label pair for every recorded state.
- Successful trajectories receive cumulative costs equal to TTR, whereas collision or horizon failures receive values larger than Thorizon.
- A regressor thresholded at the reachability horizon converts the cumulative-cost prediction into a fast reachable-versus-unreachable classifier during planning.
2) Reachability Estimator Network:
RL-RRT trains a neural reachability estimator from robot observations and integrates it into RRT node selection, while using the RL policy to propagate dynamically feasible extensions.
- Reachability Estimator Network: The estimator maps robot observations to predicted TTR using a three-layer fully connected network trained with L2 loss.
- RL-RRT tree growth: RL-RRT first filters Euclidean nearest nodes, then selects the candidate with the lowest average obstacle-aware TTR over nearby target samples.
- RL-RRT tree growth: The estimator is placed in a hierarchical nearest-neighbor selector because inference takes about 0.5 ms versus 7 µs for Euclidean distance.
- RL-RRT tree growth: After node selection, the RL policy receives lidar, robot-state, and goal information and propagates the dynamics, adding new tree nodes at fixed intervals.
- Termination: The planner terminates when the tree reaches the goal or the computation budget is exhausted; reaching the goal yields a dynamically feasible motion plan.
IV. EVALUATION
The evaluation tests RL-RRT on three kinodynamic robots in two previously unseen environments, including a physical Fetch robot experiment, against established planning baselines.
- Physical evaluation: The method is experimentally verified on a physical differential-drive Fetch robot.
- Robots: The evaluated systems are Car, Asteroid, and Fetch, representing distinct kinodynamic dynamics.
- Environments: Training uses one environment, while planning is evaluated in Map 1 and Map 2, which are roughly 15 and 81 times larger than the training environment.
- Environments: The evaluation includes cluttered regions and narrow corridors, including a noisy-SLAM map from the Fetch physical testbed.
- Baselines: RL-RRT is compared with SST for all robots and with RRT-DW and RRT-S for Fetch; experiments are repeated 50 times.
B. AutoRL Policy Performance
AutoRL policies provide obstacle-avoiding local planners, while the reachability estimator achieves moderate classification accuracy and reveals both transfer limits and prediction bias.
- AutoRL Policy Performance: 10 m or farther than training, policy performance degrades; Car performs best, while Asteroid is most challenging.
- AutoRL Policy Performance: The AutoRL policies function as both steering functions and obstacle-avoidance policies across varied robot dynamics.
- Reachability Estimator Performance: 70%–80% accuracy is reported for the reachability estimators, with high recall suggesting fewer missed nodes but lower precision causing unhelpful exploration.
- Reachability Estimator Performance: The estimator overestimates TTR for reachable states across all robots, and the paper leaves improved cost heuristics and network architectures for future work.
- Reachability Estimator Performance: For Car, estimated TTR captures unreachable regions and orientation-dependent dynamics, but predictions are inaccurate for starts inside obstacles because such trajectories are absent from training.
D. Planning Results
RL-RRT finds solutions faster than SST and produces substantially shorter finish times, while its reachability estimator improves tree growth over Euclidean distance. Physical execution shows the planned path can be followed closely by the robot.
- Planning comparisons: RL-RRT finds solutions faster than SST and steering-function baselines across the tested robots and environments.The authors attribute this to an obstacle-avoiding RL local planner that can navigate narrow corridors and corners.
- Planning comparisons: Removing the reachability estimator and using Euclidean distance causes worse performance for all tested robots.The estimator prunes potentially infeasible growth and encodes time to reach, making it more informative for kinodynamic systems.
- Planning comparisons: Up to 6 times shorter finish times than SST were achieved, with performance comparable to RRT-DWA and RRT-S on differential-drive systems.SST’s random action propagation produces jittery trajectories and longer finish times.
- Physical execution: In physical Fetch experiments, the executed trajectory stayed close to the planned path through a cluttered environment.High estimated time to reach slowed tree growth in cluttered cubicle space, while the tree expanded faster in open regions.
V. DISCUSSION
The discussion compares the learned reachability estimator with critic-based and ground-truth reachability measures, showing both its usefulness and its sensitivity to large-scale obstacle structure. Its local sensing can misclassify globally unreachable regions when planning environments differ from training conditions.
- Estimator analysis: The reachability estimator correctly predicts time to reach for Asteroid trajectories, whereas the DDPG critic value has a local maximum and is unsuitable as a distance function.This comparison motivated supervised reachability estimation rather than using the critic directly.
- Estimator limitations: The Car estimator’s predicted reachability can disagree with ground truth outside a central box in a maze-like environment.White regions represent states whose time to reach exceeds the 40-second horizon.
- Estimator limitations: The estimator relies on local information such as simulated lidar, while large-scale obstacle structures can substantially affect true reachability.Some regions outside the central box were incorrectly predicted as reachable.
- Estimator limitations: The estimator performs well when training and planning environments are similar, suggesting training in similar environments or online adaptation during planning.Online adaptation is identified as future work.
VI. CONCLUSIONS
RL-RRT combines an obstacle-avoiding learned local planner with an obstacle-aware reachability estimator used to guide RRT growth. Across simulated and physical evaluations, the method produced faster plans and shorter paths than baselines.
- VI. CONCLUSIONS: RL-RRT learns an obstacle-avoiding local planner, trains an obstacle-aware reachability estimator, and uses the estimator to bias RRT sampling.The learned policy also transfers to new environments.
- VI. CONCLUSIONS: Compared to baselines, RL-RRT plans faster and produces shorter paths across evaluations on three kinodynamic robots.The evaluation included two simulated environments and a physical differential-drive robot.
- A. P2P for differential drive robots: The differential-drive reward combines goal attainment, distance progress, collision avoidance, obstacle clearance, step cost, and turning penalties.The goal reward is 1 upon reaching the goal and 0 otherwise; collision reward is 1 upon collision and 0 otherwise.
B. P2P for kinodynamic car robots
The kinodynamic car-robot setup uses a P2P agent with a reward shaped around goal progress, collisions, motion cost, and reverse motion. The supplemental estimator analysis compares predicted and true reach times for states that can reach the goal.
- B. P2P for kinodynamic car robots: The car-robot reward includes goal attainment, goal-distance progress, collision handling, step cost, and a penalty for backward motion.Goal, collision, and step terms match the differential-drive formulation; backward motion is penalized through negative backward speed.
- B. P2P for kinodynamic car robots: The car-robot observations use 64 lidar beams.The beam count is specified alongside the reward and backward-motion definition.
- B. P2P for kinodynamic car robots: The asteroid-like system uses thruster acceleration from [-0.5, 1.0] m/s2 and turn rate from [-0.5, 0.5] rad/s.Its first-order drag coefficient is κ = 1.0 s−1, resulting in a maximum speed of 1.0 m/s.
- B. P2P for kinodynamic car robots: The supplemental TTR estimator is trained only on trajectories that reached the goal and compares predicted reach times with ground truth.Figure 8 covers states that can reach the goal across various robots.