Leadership Inference for Multi-Agent Interactions

Hamzah Khan, David Fridovich-Keil

TL;DR

This paper introduces a formal framework for identifying the "leader" in multi-agent interactions, such as cars negotiating a lane change. By combining a new iterative game-solving algorithm (SILQGames) with a particle filter (the Stackelberg Leadership Filter), the researchers can infer which agent is influencing the other's behavior in real-time, even in complex, nonlinear scenarios.

What Problem Does This Paper Address?

In multi-agent environments like highway driving, agents constantly "negotiate" for space. While we often use simple heuristics to decide who is in charge—like "the car in front is the leader"—these intuitions are often too shallow. An aggressive driver tailgating a cautious one might actually be the "follower" reacting to the front car's pace, or they might be the "leader" forcing the front car to speed up or yield.

Deciphering these dynamics is crucial for autonomous vehicles to predict intent and plan safe maneuvers. The challenge lies in the fact that leadership is a latent (hidden) variable. To model it accurately, we need a mathematical framework that captures how one agent's strategy explicitly influences another's response, especially when dealing with the messy, nonlinear realities of physical motion.

Methods

The authors propose two primary technical contributions:

  1. SILQGames (Stackelberg Iterative Linear-Quadratic Games): Standard game theory often looks for Nash equilibria (where no one wants to change their strategy). However, leadership is better modeled by Stackelberg equilibria, where a "leader" commits to a strategy first, and a "follower" optimizes their response based on that commitment. SILQGames is a novel iterative algorithm that solves these games for systems with nonlinear dynamics and non-quadratic costs by repeatedly solving linear-quadratic approximations.
  2. SLF (Stackelberg Leadership Filter): This is an online Bayesian filter (specifically a particle filter). Each "particle" in the filter represents a hypothesis: either Agent A is the leader or Agent B is the leader. At each time step, the filter simulates what the agents should do under both hypotheses using SILQGames and compares these predictions to actual observations. Particles that match observed behavior are weighted more heavily, allowing the filter to converge on the true leadership state.

Datasets

The paper evaluates the approach using three simulated environments rather than static datasets, as interactive leadership requires closed-loop simulation:

  • Shepherd and Sheep Game: A classic benchmark where one agent (shepherd) tries to influence the position of another (sheep). The authors tested both a standard Linear-Quadratic (LQ) version and a more complex nonlinear version with "log-barrier" costs to simulate boundaries.
  • Passing Scenario: A two-car simulation on a two-way road where one car overtakes another.
  • Merging Scenario: A scenario where two lanes merge into one, requiring agents to negotiate right-of-way.

Key Insights and Ideas

  • Leadership as Strategy Influence: The core "aha" moment is treating leadership not as a spatial property (who is in front), but as a structural property of the optimization problem. The leader is the agent whose objective function is minimized subject to the follower's best response.
  • Handling Non-Convexity: By using iterative approximations, the authors show that Stackelberg solutions can be found for complex driving costs (like avoiding collisions or staying within lane boundaries) that don't fit into simple linear models.
  • Dynamic Shifts: The SLF is capable of capturing "leadership reversals." For example, in a passing maneuver, the leadership probability shifts from the lead car to the passing car as the interaction evolves.
  • Robustness to Model Mismatch: Interestingly, the filter correctly identified leaders in merging scenarios even when the internal models used by the filter didn't perfectly match the ground-truth behavior of the agents, suggesting the framework is robust to the "imperfect" models we often have in the real world.

Key Results

  • Convergence: SILQGames demonstrated consistent convergence across 100 repeated trials in non-LQ scenarios, typically within ~1100 iterations for complex cases.
  • Accuracy: In the Shepherd and Sheep validation, the SLF correctly identified the leader with high confidence, though it required a sufficient "look-ahead" horizon ($T_s$) to distinguish leadership from random noise.
  • Computational Performance: On an AMD Ryzen 9 processor, a single step of the SLF with 50 particles took approximately 0.82 seconds. While not yet "real-time" for high-speed highway driving (which usually requires <100ms latency), it is within reach through parallelization of the particle computations.

Limitations and Future Work

  • Computational Complexity: The current implementation is not yet real-time. The authors note that parallelizing the particle filter is a necessary next step for deployment on actual robots or autonomous vehicles.
  • Known Objectives: The filter assumes we already know the agents' objective functions (e.g., they want to stay in their lane and avoid crashing). In reality, these must often be inferred. Combining this work with Inverse Reinforcement Learning (IRL) to learn objectives and leadership simultaneously is a promising future direction.
  • Scaling to N-Agents: The current work focuses on two-agent interactions. Scaling to $N$ agents is difficult because the number of possible leadership hierarchies grows exponentially.

Summary updated

BibTeX
@article{khan2024leadership,
  author = {Hamzah Khan and David Fridovich-Keil},
  title = {{Leadership Inference for Multi-Agent Interactions}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2024},
  doi = {10.1109/lra.2024.3381469},
}
Figure