Decision-Theoretic Planning Under Anonymity in Agent Populations

Ekhlas Sonu, Yingke Chen, Prashant DoshiJAIR 2017 · DOI

TL;DR

This paper tackles the challenge of decision-theoretic planning in environments with a massive number of self-interested agents. They introduce a novel framework, the "many-agent I-POMDP," that leverages agent anonymity and context-specific independence to drastically improve scalability. This allows for exact planning in scenarios with thousands of agents, a significant leap from previous methods.

What Problem Does This Paper Address?

Planning under uncertainty, especially when multiple agents are involved, is notoriously difficult. The standard framework for this is the Partially Observable Markov Decision Process (POMDP), and its multi-agent extension, the Interactive POMDP (I-POMDP). However, these frameworks suffer from two major "curses": the curse of dimensionality (state space grows exponentially) and the curse of history (search space grows exponentially with planning horizon). When the number of agents becomes very large (hundreds or thousands), these curses become insurmountable, leading to intractable computational complexity. This paper addresses the "curse of many agents" by proposing a method to scale I-POMDPs to populations of thousands of agents, a critical step for real-world applications.

Methods

The core contribution is the many-agent I-POMDP framework. This framework exploits two key problem structures:

  • Frame-Action Anonymity: This assumes that the identity of individual agents within a group (defined by their "frame," e.g., peaceful vs. disruptive protestors) doesn't matter for decision-making, only the counts of agents in each frame performing certain actions. This allows for representing joint actions as "configurations" (counts of actions per frame) rather than individual joint actions, drastically reducing the action space.
  • Context-Specific Independence: This assumes that not all other agents' actions are relevant to a given agent's decision. This structure is modeled using frame-action hypergraphs, which generalize action graphs to handle agent frames and multiple types of dependencies (transition, observation, reward).

To further combat the "curse of history," the authors apply a branch-and-bound scheme to prune the search tree. This involves computing fast, yet tight, upper and lower bounds on the value function, allowing them to avoid exploring branches guaranteed to be suboptimal.

Datasets

The authors introduce and evaluate their methods on three new problem domains:

  • Policing Large Protests: Simulates police managing protests with thousands of participants across multiple sites.
  • Traffic Congestion Control: Models managing traffic flow at a busy intersection with numerous vehicles.
  • Clash of Clans Defense: Simulates defending a settlement in the popular mobile game against invading armies.

These domains are designed to naturally exhibit large agent populations, anonymity, and context-specific independence.

Key Insights and Ideas

  • Structure is Key: The paper powerfully demonstrates that exploiting inherent problem structures like anonymity and context-specific independence is crucial for scaling multi-agent planning. Without these, even modest numbers of agents become intractable.
  • Configurations Over Joint Actions: Representing actions as configurations (counts) rather than explicit joint actions is a game-changer for handling large agent populations.
  • Branch-and-Bound for Horizon: Applying branch-and-bound to I-POMDPs is a novel and effective way to mitigate the curse of history, enabling deeper planning horizons.
  • Real-World Relevance: The chosen problem domains are not just theoretical constructs but reflect real-world scenarios, highlighting the practical applicability of the proposed methods.

Key Results

  • The many-agent I-POMDP framework successfully scales to problems with up to 2,000 agents (protestors or vehicles) within reasonable timeframes (e.g., a 4-horizon plan for policing in under 6 hours).
  • Exploiting anonymity and context-specific independence leads to significant speedups compared to traditional I-POMDPs. For instance, in the policing domain with 5 agents, the speedup is over 100x.
  • The branch-and-bound method consistently outperforms exhaustive search, enabling solutions for problems that would otherwise be computationally infeasible.
  • The expected value of the policy generally decreases as the number of agents increases, indicating that managing larger populations becomes inherently harder.

Limitations and Future Work

  • Prior Belief Requirement: The current method requires a prior belief of the subject agent, making it less suitable for scenarios demanding general solutions for any prior.
  • Independence Assumptions: The belief update assumes independence between observation and state factors, and that these factors are orthogonal. While often satisfied in practice, this is a simplification.
  • Few Frames Assumption: The assumption that a large set of agents is associated with few frames is generally realistic but might not hold in all scenarios.
  • Future Work: The authors plan to explore more problem structures, investigate new approximation algorithms (e.g., using MCTS instead of branch-and-bound), and integrate their work with multiagent simulation platforms to study agent population behavior.

Summary updated

BibTeX
@article{sonu2017decision,
  author = {Ekhlas Sonu and Yingke Chen and Prashant Doshi},
  title = {{Decision-Theoretic Planning Under Anonymity in Agent Populations}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  doi = {10.1613/jair.5449},
}
Figure