Multi-branch planning improves agent interactions with faster solve times
Cascaded consensus splitting for multi-branch contingency games
Robotics
Summary
Planning how multiple agents act together is tricky because they may reveal their intentions at different times. The authors create a system that lets agents plan with multiple points where they consider new information, instead of just one. This makes the plans more flexible and better suited for complex situations involving several agents. Their approach also uses a special solver that breaks the problem into smaller parts that can run in parallel, speeding up calculations.
What this means in practice
- •For autonomous vehicle developers: Enable multi-agent driving scenarios to adapt plans as each vehicle's intentions become known at different times, improving coordination and safety.$Commercial implications: Allows building advanced autonomous driving systems that handle complex, unpredictable traffic interactions by progressively updating planned routes.
- •For robotics system integrators: Improve robots working closely with humans or other robots by handling asynchronous decision updates efficiently, reducing planning delays.
Authors
Bastien Lechardoy, Pau de las Heras Molins, Thibault Lahire, Laurent Pautet, David Filliat, David Fridovich-Keil, Georgios Bakirtzis
Abstract
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.