Policy Optimization to Learn Adaptive Motion Primitives in Path Planning With Dynamic Obstacles

Brian Angulo, Aleksandr Panov, Konstantin S. Yakovlev

TL;DR

This paper introduces POLAMP, a hybrid motion planning framework that combines classical global search algorithms (like RRT and A*) with a learned local steering policy. By using Proximal Policy Optimization (PPO) and curriculum learning, the authors create "adaptive motion primitives" that allow car-like robots to navigate complex environments with up to 50 dynamic obstacles with a success rate exceeding 92%.

What Problem Does This Paper Address?

Kinodynamic motion planning for non-holonomic robots (such as cars that cannot move sideways) is a classic "hard" problem in robotics. The challenge is twofold:

  1. Kinodynamic Constraints: The planner must respect the physical limits of the robot (velocity, acceleration, and turning radius).
  2. Dynamic Obstacles: The environment is not static; the robot must predict and react to other moving agents in real-time.

Traditional methods often struggle here. Lattice-based planners use pre-computed "motion primitives" that are blind to dynamic obstacles, while sampling-based planners (like RRT) rely on local steering functions that are often computationally expensive or fail to account for moving threats. The authors aim to bridge this gap by learning a steering function that is both kinodynamically feasible and "aware" of its surroundings.

Methods

The core of the paper is the POLAMP (Policy Optimization that Learns Adaptive Motion Primitives) algorithm. Its architecture consists of two main layers:

  • The Local Planner (The "Brain"): Instead of a hard-coded mathematical formula, the authors use a neural network policy trained via Proximal Policy Optimization (PPO).
  • Input: A 39-beam 2D LiDAR scan (360° coverage) and a 10-dimensional feature vector (relative goal position, current velocity, steering angle, etc.).
  • Output: Continuous control actions—linear acceleration ($a$) and rotation rate ($\omega$).
  • The Global Planner (The "Map"): The learned local policy is plugged into classical global planners like RRT or A*. The global planner explores the workspace, while the learned policy acts as the "steering function" to connect nodes, ensuring the local paths avoid obstacles and follow car-like physics.
  • Curriculum Learning: To make training stable, the authors used a three-stage approach:
  • Empty Environment: Learn basic vehicle physics.
  • Static Obstacles: Learn to navigate around fixed objects.
  • Dynamic Obstacles: Learn to dodge adversarial moving objects.

Datasets

The authors evaluated their method using:

  • Training Data: Randomly generated tasks in 40m x 40m environments with varying obstacle densities.
  • Evaluation Maps: Three distinct "parking lot" style maps (100m x 60m) based on a real-world dataset.
  • Dynamic Scenarios: Environments populated with 0 to 70 dynamic obstacles, each moving with trajectories generated by random control inputs.

Notably, the policy was trained on fragments of "Map 1" but tested on entirely unseen maps ("Map 2" and "Map 3") to prove generalization.

Key Insights and Ideas

  • Generalization via RL: Unlike previous RL-based planners (like RL-RRT which uses DDPG), POLAMP uses on-policy PPO. The authors found that PPO generalizes significantly better to unseen maps, whereas DDPG-based policies tended to overfit to the training geometry.
  • Adaptive vs. Fixed Primitives: Traditional A* uses a fixed set of motion primitives. POLAMP's primitives are "adaptive"—the local policy can slow down, wait, or swerve based on the current position of dynamic obstacles, which a fixed primitive cannot do.
  • Efficiency in Sampling: Because the learned local planner is "smarter" at avoiding collisions, the global planner (POLAMP-RRT) requires 12x to 14x fewer samples to find a valid path compared to non-learned baselines like RRT-ES or SST*.

Key Results

  • High Success Rates: In environments with 50 simultaneously moving obstacles, POLAMP maintained a success rate of >92%.
  • Robustness: Even when the number of dynamic obstacles increased to 70, the success rate remained significantly higher than state-of-the-art competitors like RRTX or A*-CMP.
  • Generalization: The policy achieved near 100% success on static versions of unseen maps, while the baseline RL-RRT dropped to as low as 4.5% success on the same maps, highlighting the superior generalization of the PPO-based approach.

Limitations and Future Work

  • Idealized Sensing: The study assumes an "ideal environment" where LiDAR data and obstacle trajectories are perfectly known. In the real world, sensor noise and prediction uncertainty for dynamic obstacles would be significant factors.
  • Computational Overhead: While the policy reduces the number of samples needed, running a neural network inference for every local connection in a global search adds computational cost compared to simple geometric steering.
  • Future Directions: The authors suggest moving toward real-world deployment and incorporating uncertainty models for dynamic obstacle movement to make the planner more robust for actual autonomous driving. Not discussed in the paper is the specific hardware requirements for real-time execution of the A*-POLAMP variant in high-density settings.

Summary updated

Abstract

This letter addresses the kinodynamic motion planning for non-holonomic robots in dynamic environments with both static and dynamic obstacles – a challenging problem that lacks a universal solution yet. One of the promising approaches to solve it is decomposing the problem into the smaller sub-problems and combining the local solutions into the global one. The crux of any planning method for non-holonomic robots is the generation of motion primitives that generates solutions to local planning sub-problems. In this work we introduce a novel learnable steering function (policy), which takes into account kinodynamic constraints of the robot and both static and dynamic obstacles. This policy is efficiently trained via the policy optimization. Empirically, we show that our steering function generalizes well to unseen problems. We then plug in the trained policy into the sampling-based and lattice-based planners, and evaluate the resultant POLAMP algorithm (Policy Optimization that Learns Adaptive Motion Primitives) in a range of challenging setups that involve a car-like robot operating in the obstacle-rich parking-lot environments. We show that POLAMP is able to plan collision-free kinodynamic trajectories with success rates higher than 92%, when 50 simultaneously moving obstacles populate the environment showing better performance than the state-of-the-art competitors.
BibTeX
@article{angulo2023policy,
  author = {Brian Angulo and Aleksandr Panov and Konstantin S. Yakovlev},
  title = {{Policy Optimization to Learn Adaptive Motion Primitives in Path Planning With Dynamic Obstacles}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2023},
  doi = {10.1109/lra.2022.3233261},
}

Loading related content...

Figure