When an autonomous vehicle approaches an uncontrolled intersection, it faces a fundamental dilemma. If it assumes other drivers will always yield, it risks a collision. If it plans for the absolute worst-case scenario—assuming every vehicle will cut it off—it succumbs to the "frozen robot problem," slamming on the brakes and failing to make progress.
Traditional Model Predictive Control (MPC) frameworks struggle with this trade-off because they typically optimize a single, linear trajectory over a fixed time horizon. To remain safe, a linear planner must choose a path that is safe against all possible futures simultaneously, which inevitably leads to extreme conservatism.
Branching trajectory optimization (or contingency planning) resolves this tension. Instead of forcing the robot to commit to a single path or plan for a monolithic worst case, it structures the future as a tree. This allows the robot to hedge its bets: it executes a single, confident action right now while maintaining distinct, pre-calculated escape routes for every potential way the environment might evolve.
The Anatomy of a Trajectory Tree
The core insight of branching trajectory optimization is that uncertainty is not static; it resolves over time. A pedestrian will either step off the curb or stay on it; an oncoming car will either turn or go straight.
To exploit this, the planner optimizes a trajectory tree rather than a single sequence of states. This tree consists of two main components:
- The Trunk (Shared Prefix): A single sequence of immediate actions that the robot executes in the near term. Because the robot can only physically do one thing at the current time step, the trunk must be kinematically feasible and safe across all hypothesized futures.
- The Branches (Contingent Paths): At a designated "branching time"—the point where uncertainty is expected to resolve or a decision must be made—the trajectory splits into multiple distinct paths. Each branch is optimized for one specific environmental hypothesis.
/--- Branch A (Hypothesis 1: Vehicle Yields)
/
[ Current State ] === Trunk (Shared Prefix)
\
\--- Branch B (Hypothesis 2: Vehicle Cuts Off)
As formulated by Phiquepal et al. in their work on Control-Tree Optimization: an approach to MPC under discrete Partial Observability, this structure allows the system to optimize for multiple weighted hypotheses simultaneously. By enforcing a shared trunk, the robot ensures that its immediate behavior remains valid regardless of which discrete hypothesis eventually proves true. Similarly, Bajcsy et al. leverage this topology in Contingency Games for Multi-Agent Interaction to model interactive scenarios, ensuring the robot's immediate "trunk" actions preserve safety without prematurely picking a single outcome.
Why It Works: Postponing Commitment
The reason this framework unlocks both safety and efficiency lies in the concept of decision-time postponing.
In a traditional planner, if a hazard is possible in 3 seconds, the vehicle might feel compelled to brake now. In a branching framework, the vehicle can maintain its speed along the trunk because it explicitly calculates a valid backup branch (e.g., a hard braking profile) that diverges at the 2-second mark. As long as that backup branch is physically feasible, the vehicle can safely proceed along the assertive trunk. If the hazard materializes, the vehicle transitions to the backup branch; if the hazard disappears, the vehicle continues smoothly without ever having disrupted traffic.
As Tas et al. demonstrate in Decision-Time Postponing Motion Planning for Combinatorial Uncertain Maneuvering, calculating a maneuver-neutral path allows the vehicle to keep multiple options (such as leading or yielding) open until environmental uncertainty drops. This prevents premature reactions to low-probability hazards.
This optimization strategy fundamentally alters the safety-efficiency trade-off:
- Assertiveness: The vehicle can drive more confidently because it avoids premature conservatism, as shown by Cui et al. in LookOut: Diverse Multi-Future Prediction and Planning for Self-Driving.
- Guaranteed Safety: It maintains high operational efficiency by delaying conservative maneuvers until a specific outcome is confirmed, while ensuring a safe recovery path always exists (Ornia et al. in RACP: Risk-Aware Contingency Planning With Multi-Modal Predictions).
Mirroring the Environment's Scenario Tree
To plan an effective trajectory tree, the ego-agent's branches must mirror the predicted behaviors of the surrounding world. This requires coupling multi-modal prediction models directly with the trajectory optimization process.
When surrounding agents are faced with choices, their potential trajectories form a scenario tree. In Interactive Multi-Modal Motion Planning With Branch Model Predictive Control, Chen et al. show that by constructing an ego trajectory tree that matches the topology of the environment's scenario tree, the planner explicitly accounts for how the ego-agent will react to each specific divergence.
Environment Scenario Tree: [Agent Continues] <---> [Agent Brakes]
^ ^
| |
Ego Trajectory Tree: [Ego Branch A] <---> [Ego Branch B]
This interaction can be modeled with varying degrees of complexity:
- Dynamic Responsiveness: Ivanovic et al. introduce a mixture-of-systems representation in MATS: An Interpretable Trajectory Forecasting Representation for Planning and Control that allows contingency planners to optimize paths while accounting for how other agents will dynamically respond to the robot's actions.
- Joint Optimization: Rather than treating predictions as fixed obstacles, the authors of Interaktive Trajektorienplanung mittels gemischt-ganzzahliger quadratischer Programmierung (Burger et al.) jointly solve for the automated vehicle's path and the predicted movements of surrounding drivers, ensuring the shared initial path segment remains compatible with multiple evolving agent behaviors.
- Adaptive Exploration: In Multimodal Integrated Prediction and Decision-making with Adaptive Interaction Modality Explorations, Li et al. generate optimal trajectory trees by exploring multiple interaction modalities, producing deterministic immediate actions that gracefully handle diverse future evolutions.
Beyond Navigation: Multi-Horizon Backup Plans
While highly popular in autonomous driving, the intuition of branching trajectory optimization extends to broader mission-level safety and survival. For instance, an aerial vehicle might need to balance its primary mission against the risk of a sudden system failure or an unresolvable hazard that requires an immediate abort.
Instead of planning solely for the primary objective, the controller can maintain multiple "virtual" horizons that branch off from the current state toward alternative safe destinations or backup missions.
This concept is formalized by Kim et al. in Backup Plan Constrained Model Predictive Control. By evaluating a primary mission horizon alongside parallel virtual horizons for alternative missions, the controller continuously verifies that a transition to a backup plan is feasible at any single point along the trajectory.
To ensure this switching behavior doesn't destabilize the system, Tao et al. extended this framework in Backup Plan Constrained Model Predictive Control with Guaranteed Stability, proving that a system can continuously assess and prepare for potential mission aborts without sacrificing formal control stability.
By structuring the optimization problem as a tree, whether for navigating a tight intersection or managing an aerial mission, autonomous systems can safely navigate a multi-modal world—acting decisively in the present while remaining fully prepared for the futures that lie ahead.
Key Foundational Work
Decision-Time Postponing Motion Planning for Combinatorial Uncertain Maneuvering (2020) — contributed 2 concept elements to this direction.
LookOut: Diverse Multi-Future Prediction and Planning for Self-Driving (2021) — contributed 2 concept elements to this direction.
Backup Plan Constrained Model Predictive Control (2021) — contributed 2 concept elements to this direction.