Technical Summary: HyPlan - Hybrid Learning-Assisted Planning Under Uncertainty for Safe Autonomous Driving

1. Problem Definition

The paper addresses the Collision-Free Navigation (CFN) problem for autonomous vehicles (AVs) operating in partially observable traffic environments. The objective is to minimize the time to reach a goal while avoiding collisions with exogenous agents (pedestrians, cyclists, other cars).

This problem is modeled as a Partially Observable Markov Decision Process (POMDP). Key characteristics include:

• State Space ($S$): Composed of the ego-car's full state and the partial states of $n$ exogenous agents. While the ego-car's state is fully observable, exogenous agents are only partially observable (position only, if not occluded).
• Actions ($A$): Control inputs consisting of a steering angle and discrete acceleration choices (Accelerate, Decelerate, Maintain).
• Constraints: The environment involves uncertainty regarding agent intentions and occlusions.
• The Gap: Existing methods face a trade-off. Pure Deep Learning (DL) methods are fast but lack safety guarantees. Explicit online POMDP planners (e.g., IS-DESPOT) offer safety and provability but suffer from high execution times, making them unsuitable for real-time control compared to DL baselines.

2. Methodology: HyPlan

HyPlan is a hybrid learning-assisted online POMDP planner designed to bridge the gap between the safety of explicit planning and the speed of deep learning. It integrates four core components:

A. System Architecture

HyPlan operates in a loop where, for each scene observation:

1. Multi-Agent Behavior Prediction: Uses the MABP AutoBots model to predict trajectories of exogenous agents.
2. Path Planning: A weighted Hybrid A* planner generates a safe path for the ego-car using a costmap enriched with predicted agent paths. This determines the steering angle.
3. Velocity Planning (Core Innovation): An enhanced online POMDP planner, IS-DESPOT*, determines the optimal acceleration.

B. The IS-DESPOT* Planner

IS-DESPOT* is an extension of the standard IS-DESPOT planner. Its novelty lies in how it guides the search tree using a Deep Reinforcement Learning (DRL) component:

• NavPPO (Learner): A Proximal Policy Optimization (PPO) based neural network acts as a critic. It estimates the value of belief states (heuristic upper bounds) to guide the planner.
• Input to NavPPO:
  • An "intention image" ($I$) combining the ego-car's costmap, predicted agent paths, and the car's planned path.
  • Non-visual state features (previous reward, last action, current velocity).
  • LSTM hidden states to maintain temporal context.
• Training: NavPPO is trained to mimic the policy of the IS-DESPOT* planner (imitation learning) while learning to estimate state values. It uses a PPO-based loss function that balances policy imitation and value estimation accuracy.

C. Confidence-Based Vertical Pruning

To reduce execution time, HyPlan introduces a vertical pruning mechanism during deployment:

• Uncertainty Estimation: NavPPO performs multiple stochastic forward passes (using Monte Carlo dropout) to generate a mean ($\mu$) and variance ($\sigma^2$) for belief state value estimates.
• Calibration: The system uses CRUDE to calibrate these estimates, ensuring the confidence levels are reliable and reducing false positives.
• Pruning Logic: The planner calculates a confidence-weighted heuristic lower bound: $L(b) = (1-\phi)L_{tr}(b) + \phi U(b)$, where $\phi$ is the confidence derived from the variance.
  • If the planner reaches a belief state with a high-value estimate and high confidence, it terminates the planning trial early (vertical pruning).
  • This avoids over-exploring familiar regions of the belief space where the outcome is predictable, significantly speeding up decision-making without compromising safety.

3. Key Contributions

1. HyPlan Framework: A novel hybrid architecture combining multi-agent prediction, explicit path planning, and DRL-guided POMDP planning.
2. IS-DESPOT Algorithm:* An approximate online POMDP planner that utilizes a PPO-based learner (NavPPO) to provide heuristic value estimates and confidence metrics.
3. Vertical Pruning Strategy: A mechanism to dynamically prune the search tree based on the learner's confidence in its value estimates, drastically reducing planning time.
4. Calibration Mechanism: The integration of CRUDE to calibrate the DRL learner's confidence estimates, ensuring that pruning decisions are safe and not based on over-optimistic predictions.

4. Experimental Results

The authors evaluated HyPlan on the CARLA-CTS2 benchmark, a dataset of 23,000 critical traffic scenarios involving pedestrian crossings.

Performance Metrics

• Safety: HyPlan achieved the highest safety index among all tested methods (including pure DL, pure explicit planning, and other hybrid approaches). It had the lowest crash rate (12.36%) and near-miss rate (8.04%).
• Execution Time: HyPlan was significantly faster (up to 40% reduction) than other explicit and hybrid POMDP planners (e.g., IS-DESPOTp, LEADER, HyLEAP). However, it remained 3–4 times slower than pure deep learning baselines (NavPPO, NavA2C).
• Planning Efficiency: HyPlan required fewer planning trials, shallower search depths, and fewer belief nodes to evaluate compared to alternative planners.
• Trade-offs:
  • Pure DL methods (NavPPO) were fastest but had the worst safety record.
  • Pure explicit planners were slowest.
  • HyPlan offered the best trade-off, prioritizing safety while significantly improving the speed of explicit planning.

Ablation Study

• Without Vertical Pruning: The system was safest but had the longest execution time.
• Without Confidence Calibration: The system was fastest but suffered the worst safety due to over-optimistic pruning.
• Full HyPlan: The combination of all components provided the optimal balance between safety and execution time.

5. Significance and Claims

The paper claims that HyPlan successfully addresses the performance gap between deep learning and explicit planning in autonomous driving.

• Safety First: It demonstrates that hybrid methods can navigate safer than both pure deep learning and pure explicit planning baselines in critical pedestrian scenarios.
• Efficiency: It proves that learning-assisted pruning can make online POMDP planning viable for real-time applications, reducing execution time significantly without sacrificing the safety guarantees inherent to explicit planning.
• Modest Scope: The authors acknowledge that while HyPlan is faster than other explicit planners, it has not yet closed the speed gap with pure deep learning methods. They also note that the current evaluation is limited to the CARLA-CTS2 benchmark, with future work planned for broader scenarios like nuPlan.

The work is presented as a step toward provably correct action planning under uncertainty that does not suffer from the prohibitive computational costs traditionally associated with online POMDPs.