Abstract
Autonomous vehicle (AV) motion planning often suffers from the "Frozen Robot Problem," where overly conservative behavior arises from failing to account for reactive interactions with other agents. This paper introduces Tree Policy Planning (TPP), a framework that treats driving as a contingency planning problem. By representing potential ego-trajectories and environment reactions as branching trees and solving the resulting discrete Markov Decision Process (MDP) via dynamic programming, TPP enables safe, efficient, and reactive decision-making in complex urban environments.
Introduction and Problem Statement
Traditional AV planners typically operate in an "open-loop" fashion: they predict future trajectories for surrounding agents and then optimize a single path for the ego vehicle that avoids all predicted obstacles. This approach fails to capture the interactive nature of driving—where an ego vehicle's actions influence others—and often leads to the "Frozen Robot Problem." In such scenarios, the AV becomes paralyzed by the need to account for every possible worst-case scenario simultaneously, regardless of how unlikely they are or how the AV's own presence might mitigate them.
Existing "policy planning" (closed-loop) solutions aim to address this but frequently struggle with scalability, compatibility with modern deep-learning behavior models, or computational efficiency.
The TPP Framework
TPP bridges the gap between high-capacity deep learning and classical decision theory. The framework discretizes the continuous planning space into a tree structure, allowing for "if-then" contingency planning.
Methodology Components
- Ego-Motion Sampler: Generates an ego trajectory tree composed of short, dynamically feasible maneuver segments (e.g., cubic splines). This tree represents the various paths the AV can take over a planning horizon.
- Multi-stage Prediction Model: Produces a scenario tree using state-of-the-art deep learning architectures. Crucially, these predictions are ego-conditioned, meaning they model how other agents will react specifically to the paths within the ego trajectory tree.
- Dynamic Programming (DP) Solver: The framework converts the trajectory and scenario trees into a discrete Markov Decision Process. Using the Bellman equation, the solver works backward from the horizon to the present to find the optimal sequence of segments—the "optimal policy."
A key theoretical contribution is the definition of Causal Consistency, ensuring the planner does not utilize future information when making present-time predictions, maintaining the integrity of the closed-loop simulation.
Evaluation and Results
The researchers evaluated TPP using the nuScenes dataset for training and the BITS (Bi-level Imitation for Traffic Simulation) environment for closed-loop testing. BITS is particularly valuable as it allows agents to react to the AV's movements, providing a realistic test of interaction.
Key Performance Metrics
- Safety: TPP demonstrated a significant reduction in crash rates. Using a rasterized prediction backbone, TPP achieved a 0.46% crash rate, nearly half that of a robust non-contingent baseline (0.80%).
- Efficiency: The system maintained high area coverage, indicating that the improved safety did not come at the cost of progress or overly timid behavior.
- Computational Speed: The DP solver is highly efficient, finding the optimal policy in approximately 11ms, well within the requirements for real-time deployment.
Insights and Discussion
A notable finding of the study is the "Better Prediction" Paradox: models with the lowest displacement error (standard offline metrics) do not always yield the best driving performance. For effective planning, the diversity and reactivity of predictions are often more critical than raw spatial accuracy.
By shifting from planning a single trajectory to planning a policy, TPP allows the AV to "wait and see." For example, it can begin a lane change and only fully commit once it observes the target lane's driver yielding.
Conclusion and Future Work
TPP offers a scalable, real-time solution for interactive motion planning. While the current implementation uses a fixed tree topology, future work could explore event-triggered branching to further optimize the tree structure. Additionally, reducing the overhead of specific deep-learning backbones and introducing personalized cost functions remain areas for further development.
Summary updated