Worst-Case Hidden-Vehicle Trajectory Search in Spatiotemporal Occlusion Regions
Researchers propose HC-MTS, a bilevel minimax search that finds worst-case hidden-vehicle trajectories under occlusion, cutting retained hidden-seed counts ~18-22% on Waymo scenarios.
HC-MTS constructs finite hidden-state modes certified by backward witnesses satisfying multi-frame visibility, occupancy, semantic-map, and kinematic constraints, then solves a bilevel minimax problem where an inner oracle maximizes the ego driving score and an outer search minimizes it via legal hidden-vehicle trajectories. Across eight Waymo Open Motion Dataset scenarios, raising the visibility-memory horizon K from 1 to 20 reduces mean retained hidden-seed counts by 18.12% for vehicles, 21.67% for pedestrians, and 18.45% overall. The method identifies six avoidable counterexamples, while no legal collision-producing attacker was found in the remaining two scenes within the finite search budget.
- HC-MTS certifies hidden-state modes via backward witnesses using visibility, occupancy, semantic-map, and kinematic constraints.
- Solves a bilevel minimax: inner oracle maximizes ego driving score, outer search minimizes it with legal hidden trajectories.
- Extending visibility-memory horizon K from 1 to 20 cuts hidden-seed counts by 18.12-21.67% across eight Waymo scenarios.
- Identifies six avoidable counterexamples; no legal collision-producing attacker found in two remaining scenes within budget.
Full article154 words · extracted from arxiv.org · click to collapse
Occlusion creates fundamental uncertainty in autonomous driving. Existing methods often propagate frame-wise hypotheses or optimize ego behavior against prescribed hidden-agent predictions, leaving the worst history-consistent interaction unexplored. We introduce History-Conditioned Minimax Trajectory Search (HC-MTS), which combines temporal occlusion reasoning with response-aware search. First, HC-MTS constructs finite hidden-state modes, each certified by a backward witness satisfying multi-frame visibility, occupancy, semantic-map support, and class-specific kinematic constraints. It then solves a bilevel minimax problem: an inner finite oracle maximizes the ego driving score over destination attainment and ride comfort, while the outer search selects the legal hidden-vehicle trajectory that minimizes this best-response value. Across eight Waymo Open Motion Dataset scenarios, increasing the visibility-memory horizon from K=1 to K=20 reduces the mean per-scenario vehicle, pedestrian, and total retained hidden-seed counts by 18.12%, 21.67%, and 18.45%, respectively. HC-MTS identifies six avoidable counterexamples, while no legal collision-producing attacker is found in the remaining two scenes within the finite search budget.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.20480