PaperlayerView exact revision on arXiv

Source-linked AI summary

Cascaded consensus splitting for multi-branch contingency games

Bastien Lechardoy, Pau de las Heras Molins, Thibault Lahire, Laurent Pautet, David Filliat, David Fridovich-Keil, Georgios Bakirtzis

arXiv:2609.37612v1cs.ROcs.SYeess.SY

TL;DR

Existing contingency games use a single branching time despite intent uncertainty resolving asynchronously, while larger scenario games pose computational challenges. The paper introduces multiple branching times and an ADMM-based scenario decomposition; experiments report higher interaction success and lower mean solve time than the single-branch approach.

  • Problem

    Existing contingency games assume all agents’ intent uncertainty resolves simultaneously, despite confidence about different agents arriving at different times.

    Source: §I · p. 1

  • Method

    The paper introduces multi-branch contingency games and decomposes shared consensus constraints with ADMM so scenario-specific interaction games can be solved in parallel.

    Source: §I · p. 1

  • Results

    Interaction success rises by 42% relative to the conventional single-branch approach, from 66% to 94%, while mean solve time falls from 1.72 to 0.46 s per planning step.

    Source: §I · p. 2, A. Monte Carlo branching structure… · p. 7

  • Takeaways & Limitations

    In the reported experiments, progressively resolving intent uncertainty is associated with higher interaction success and lower mean online solve time than single branching.

    Source: §I · p. 2, A. Monte Carlo branching structure… · p. 7

    Because the trajectory games are nonconvex, the local ADMM guarantee neither ensures convergence from arbitrary initializations nor establishes that the stationary point is a GNE.

    Source: D. Multiplier update · p. 5

Abstract

from arXiv · show

Contingency games enable agents to anticipate and plan for other agents' hypothetical intents by constructing trajectories with a shared prefix and intent-dependent branches. While contingency games capture intent uncertainty, existing formulations rely on a single branching time, oversimplifying interactions in which different agents' intentions are revealed at different times. Moreover, the computational cost of such problems grows rapidly with the number of agents and intents, as all scenario-dependent best responses must be solved jointly. We introduce a multi-branch contingency architecture in which sources of intent uncertainty can be resolved progressively at different branching times, allowing the planned trajectories to adapt to the asynchronous revelation of intents. We also develop an ADMM-based solver that exploits scenario-level parallelism. Experiments on tightly coupled three-agent interactions support that the proposed architecture outperforms the conventional single-branch while achieving a lower mean receding-horizon solve time.

I. INTRODUCTION

Contingency games plan for multiple intent hypotheses by keeping trajectories shared until intent uncertainty is expected to resolve. This paper extends that structure to asynchronous branching and uses scenario-level parallelism to address the resulting computational burden.

I. INTRODUCTION

  • Contingency games construct intent-conditioned trajectories that share a prefix while uncertainty remains unresolved, then diverge to anticipate responses to possible intents.These trajectories must remain compatible with several possible futures while retaining the ability to adapt as behavior reveals intent.Source: §I · p. 1
  • A single branching time assumes all agents’ intents resolve simultaneously, although confidence about different agents may arrive at different times.Early commitment can be dangerous, while later branching can prevent the robot from exploiting observations and yield conservative behavior.Source: §I · p. 1

II. RELATED WORK

  • As agents, intents, or planning horizon grow, centralized optimality systems become larger and can limit practical deployment.The paper builds on scenario-game splitting with ADMM and the approach of Li et al. to exploit parallel computation.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • The proposed architecture adds multiple branching times and reconciles scenario-dependent trajectories over shared segments, retaining consensus only among scenarios still indistinguishable.This allows uncertainty sources to resolve progressively rather than simultaneously.Source: §I · p. 1, §II · p. 2
  • The multi-branch formulation raises interaction success from 66% to 94% and reduces mean solve time from 1.72 to 0.46 s per planning step.Among runs completed by both methods, it also reduces closed-loop cost by 15% and control variation by 26%.Source: §I · p. 2

III. PRELIMINARIES

Trajectory games model agents as strategic optimizers whose objectives and constraints depend on one another. A generalized Nash equilibrium requires every agent’s trajectory to be a best response to the others’ trajectories.

III. PRELIMINARIES

  • Agent indices appear as superscripts, while omitting the superscript denotes the stacked all-agent quantity.The notation defines [n] as the indices from 1 through n.Source: §III · p. 2

A. Trajectory games

  • Each agent’s trajectory comprises its states and controls over the finite planning horizon.Each agent minimizes an individual cost subject to constraints coupled to other agents’ trajectories.Source: A. Trajectory games · p. 2
  • A trajectory profile is a generalized Nash equilibrium when every agent simultaneously solves its best-response problem given the other agents’ trajectories.Source: A. Trajectory games · p. 2

B. Single-branch contingency games

Single-branch contingency games use intent-conditioned scenario trajectories with a common prefix until a shared estimated resolution time. The multi-branch extension relaxes the assumption that all intent uncertainty resolves simultaneously.

B. Single-branch contingency games

  • For each scenario, non-ego agents respond to their assigned intents, while the ego plans across scenario-dependent equilibrium trajectories.The ego maintains a probability distribution over the scenarios.Source: B. Single-branch contingency games · pp. 2–3
  • In the single-branch formulation, every scenario-dependent ego trajectory shares one control prefix until the estimated time when all intent uncertainty resolves.After that time, trajectories may diverge.Source: B. Single-branch contingency games · p. 3

IV. MULTI-BRANCH CONTINGENCY GAMES

  • The multi-branch extension progressively partitions plausible scenarios as separate sources of intent uncertainty resolve at different times.The belief distribution and branching times are treated as fixed estimates within each open-loop planning invocation.Source: B. Single-branch contingency games · p. 3, §IV · p. 3

A. Logical contingency tree and temporal realization

The logical information tree represents which scenarios remain indistinguishable as intents are revealed, while node-specific branching times determine how long their trajectories share controls. Together these structures create nested shared prefixes.

A. Logical contingency tree and temporal realization

  • The information tree determines which trajectories remain in consensus, while each node’s branching time determines how long they share controls.Different intent histories for the same agent may have different branching times.Source: A. Logical contingency tree and… · p. 3
  • The information tree assumes non-ego agents’ intents are revealed sequentially in a fixed ordering.Each node represents a resolved-intent history and the scenarios consistent with it; possible values of the next intent partition that scenario set among child nodes.Source: A. Logical contingency tree and… · p. 3
  • Branching times increase along each root-to-leaf path, and scenario groups inherit earlier consensus constraints while acquiring additional ones.The resulting control prefixes are nested, with progressively smaller scenario groups remaining in consensus until their branching times.Source: A. Logical contingency tree and… · p. 3

B. Multi-branch contingency formulation

The formulation replaces one shared branching prefix with tree-structured consensus constraints, allowing scenario trajectories to remain shared only while intent uncertainty remains unresolved.

B. Multi-branch contingency formulation

  • The method collects ego consensus prefixes across the information tree and defines a consensus residual for each node.The supplied formulation introduces the node and residual sets before constructing scenario-local objectives.Source: B. Multi-branch contingency formulation · p. 3, A. Scenario decomposition · p. 4
  • The caption reports that translating asynchronous structure into consensus constraints yields multi-branch trajectories, linking asynchronous structure to the resulting trajectory form.Source: Figure 2 · p. 4
  • Tree-structured consensus constraints replace the single-prefix constraint, changing only the ego agent’s consensus structure while non-ego scenario problems remain unchanged.This lets scenario responses diverge progressively as uncertainty is resolved.Source: B. Multi-branch contingency formulation · p. 4

V. PARTIAL-CONSENSUS SPLITTING ADMM

  • The solver adapts scenario-based ADMM to preserve cascaded contingent planning while enabling parallel solution of subproblems coupled through shared prefixes.Within each open-loop solve, the belief distribution and branching times are fixed.Source: §V · p. 4

A. Scenario decomposition

  • Dualizing the consensus constraints adds a multiplier-weighted linear term and a rho-controlled quadratic penalty to the augmented Lagrangian; ADMM updates multipliers to drive scenarios toward consensus.The constraints couple otherwise independent scenario-dependent trajectory problems.Source: A. Scenario decomposition · p. 4
  • Each scenario’s local augmented Lagrangian includes one consensus term for every information-tree node on its path, while belief weights its contribution to expected cost.The scenario collects the consensus prefixes and multipliers encountered along that path.Source: A. Scenario decomposition · p. 4

B. Parallel scenario update

At each ADMM iteration, scenario-specific games are updated with consensus prefixes and multipliers fixed, making the scenario problems independent and parallelizable.

B. Parallel scenario update

  • With consensus prefixes and multipliers fixed, all agents simultaneously solve their optimization problems for each scenario; the robot’s objective includes the augmented Lagrangian.Non-ego agents retain their original problems.Source: B. Parallel scenario update · p. 5
  • The solver imposes agents’ first-order KKT conditions and assembles a scenario-specific mixed complementarity problem that depends only on that scenario’s trajectory profile.Consensus variables and multipliers are held fixed during this update.Source: B. Parallel scenario update · p. 5
  • Because different scenarios’ mixed complementarity problems share no decision variables, they can be solved in parallel.Source: B. Parallel scenario update · p. 5

C. Node-dependent consensus update

The solver updates a separate consensus prefix at each branching node, then performs multiplier updates and assesses convergence through primal and dual consensus residuals.

C. Node-dependent consensus update

  • Each node’s consensus prefix is updated independently after scenario trajectories are reconciled before that node’s branching time.The prefix is obtained by minimizing the augmented Lagrangian with trajectories and multipliers fixed.Source: C. Node-dependent consensus update · p. 5
  • Rather than averaging all scenario trajectories into one common prefix, update (13) computes a separate consensus prefix for every branching node in parallel.Source: C. Node-dependent consensus update · p. 5

D. Multiplier update

  • Each multiplier is updated by adding rho times the primal residual associated with its consensus constraint.The update follows the standard unscaled ADMM dual-ascent step.Source: D. Multiplier update · p. 5
  • The method stops when its residual criterion is met or the maximum iteration count is reached; its local nonconvex guarantee requires regular iterates, sufficiently large rho, and summable subproblem errors.The guarantee does not ensure convergence from arbitrary initializations or that the stationary point is a GNE; the returned solution is treated as a stationary equilibrium candidate.Source: D. Multiplier update · p. 5

VI. EMPIRICAL ANALYSIS

The empirical analysis examines asynchronous intent resolution and solver speed in receding-horizon simulations, using a closed-loop procedure that repeatedly updates beliefs and branching times.

VI. EMPIRICAL ANALYSIS

  • The experiments examine whether multi-branching improves performance when intent uncertainties resolve asynchronously and whether its ADMM solver runs faster than the single-branch counterpart.A proof of concept also considers a more complex geometry than the three-agent scenario.Source: §VI · pp. 5–6

A. Closed-loop simulation framework

  • At each simulation step, the planner estimates ordered branching times, solves a game over horizon T_plan, and applies the first control from the robot’s root prefix.Episodes end at the robot’s goal, a collision, or the simulation horizon T_sim.Source: A. Closed-loop simulation framework · p. 6
  • Non-ego agents apply controls from their ground-truth intent optimization, producing noisy observations that update beliefs and branching times for the next step.Source: A. Closed-loop simulation framework · p. 6
  • The joint belief over intent combinations is updated with Bayes’ rule by comparing noisy observations with predicted states, using a Gaussian mixture model for observation likelihoods.The predictions are associated with each scenario.Source: A. Closed-loop simulation framework · p. 6
  • For each compatible scenario, the estimator finds the earliest predicted time when an agent’s intent is sufficiently resolved, selects the latest such time, then recursively estimates branching times for remaining agents.Resolution is evaluated using normalized entropy and a prescribed threshold.Source: A. Closed-loop simulation framework · p. 6

B. Numerical setup

The setup combines receding-horizon execution with a paired three-agent Monte Carlo protocol. It evaluates interaction success, progress efficiency, comfort, and online solve time.

B. Numerical setup

  • The Julia implementation solves local MCPs concurrently and weights consensus residuals by conditional intent beliefs rather than a uniform average.The reported experiments use eight Julia threads on an Apple silicon processor with eight performance cores.Source: B. Numerical setup · p. 6
  • At each time step, the robot executes the first open-loop action and selects one branch when the next branching time is imminent.The other branches are then discarded.Source: Figure 4 · p. 6
  • Online solve-time measurements exclude symbolic construction, compilation, and the initial cold-start solve; solver structures are reused across trials.Within each episode, prior controls and primal variables are shifted forward, while terminal controls and ADMM multipliers start at zero.Source: B. Numerical setup · p. 6

C. Experimental protocol

  • The protocol adds a delayed second human agent, creating asynchronous interactions and information gains in a robot-and-human road-crossing scenario.It samples 100 paired receding-horizon simulations, balancing the four intent combinations and varying initial positions, distances, and motion delay.Source: C. Experimental protocol · pp. 6–7
  • Success requires passing both agents without safety violations; efficiency and comfort are compared only on runs completed by both methods.Comfort is RMS variation in consecutive normalized ego controls, while computational performance is mean online solve time per step; metrics include 95% confidence intervals.Source: C. Experimental protocol · p. 7

VII. RESULTS

In three-agent Monte Carlo simulations, the multi-branch formulation improves interaction success and trajectory measures relative to the single-branch structure. It also reduces mean receding-horizon solve time.

A. Monte Carlo branching structure comparison

B. Qualitative failure analysis

The analysis links failures to tightly coupled successive interactions and identifies behavioral and solver-related failure modes. It also reports a larger overtaking demonstration and broader Monte Carlo conclusions.

B. Qualitative failure analysis

  • Failures arise when interactions are close in time and space, especially with delayed motion or opposing intents; the adaptation window must allow effective reaction.Lateral initial positions and distance to the first agent show reduced correlation to failure.Source: B. Qualitative failure analysis · p. 7, Figure 6 · p. 7
  • Failure modes include stalled progress from overconservative slowing and safety violations when ADMM convergence is insufficient near feasibility boundaries.The robot may stop when earlier controls did not sufficiently anticipate the second interaction, leaving no feasible passing trajectory.Source: B. Qualitative failure analysis · p. 7
  • Single branching also fails in most difficult cases through premature commitment or overly conservative trajectories, while multi-branching does not dominate every simulation.The single-branch formulation either commits before there is sufficient certainty about the second interaction or produces an overly conservative trajectory.Source: B. Qualitative failure analysis · p. 8

C. Overtaking scenario analysis

  • With four uncertain traffic agents and 16 joint intent scenarios, multi-branching completed the overtaking maneuver safely in 58 steps; single-branching did not finish within the simulation horizon.The demonstration used branching times (5, 7, 9, 11) and 25 ADMM iterations per replanning step; median online solve time was 2.14 s.Source: C. Overtaking scenario analysis · p. 8, Figure 7 · p. 8

VIII. CONCLUSION

  • Across 100 Monte Carlo cases, success rose 28 points over, with a 0.46 s average online solve time per receding-horizon step.Among simulations both methods completed, ego cost fell 15% and control variation fell 26%.Source: §VIII · p. 8
  • The solver follows the information tree, decomposes scenario games for parallel computation, and progressively reconciles trajectories over shared segments.The conclusion reports an average online solve time of 0.46 s per receding-horizon step across 100 Monte Carlo cases.Source: §VIII · p. 8
Loading 2609.37612v1…