Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations

Akshat Kumar, Shlomo ZilbersteinIJCAI 2009 · OpenReview

Abstract

Planning for multiple agents under uncertainty is notoriously difficult, with general models like Decentralized MDPs (DEC-MDPs) being NEXP-Complete. This paper identifies a tractable class of problems called Event-Detecting Multi-Agent MDPs (eMMDPs), which model scenarios such as sensor networks tracking stochastic targets. By proving that the reward function for eMMDPs is monotone and submodular, we develop a Locally Greedy Submodular Maximization (LGM) algorithm. This approach provides a guaranteed 2-approximation of the optimal policy and scales linearly with the number of agents. Empirical evaluations demonstrate that LGM consistently achieves 92-95% of optimal performance and handles state spaces exceeding one million states, far surpassing traditional solvers.

Introduction

The "curse of dimensionality" often renders multi-agent planning impossible for real-world scales. However, many practical problems, such as early outbreak detection in water systems or storm tracking via radar networks, share a specific structure. In these scenarios, collaboration is mandatory for confirmation, detection time is critical, and resources are limited. This paper bridges decision theory and combinatorial optimization to provide provable guarantees for these types of problems.

Methodology

The authors leverage three key mathematical concepts to transform an intractable planning problem into a manageable optimization task:

  1. Partition Matroids: The space of possible policies is represented as a matroid, allowing policy selection to be treated as picking items from a set under specific constraints.
  2. Submodularity: The paper proves that the eMMDP reward function exhibits diminishing returns. Adding a sensor to a sparse plan provides more marginal benefit than adding one to a crowded plan. This property is triggered by the fact that rewards for detection never increase over time.
  3. Locally Greedy Submodular Maximization (LGM): Exploiting submodularity, a greedy algorithm is used. For submodular functions over matroids, this approach is mathematically guaranteed to achieve at least 50% (a 1/2-approximation) of the optimal value.
  4. Constraint Optimization (COP): The greedy choice is formulated as a COP to exploit spatial locality, ensuring complexity depends on the interaction graph's induced width rather than the total agent count.

Experimental Setup

The LGM algorithm was evaluated on several synthetic sensor network configurations designed to mimic spatial constraints in real-world deployments:

  • 5P: A small configuration with 3 targets.
  • 11-Helix: A larger chain of sensors with 6 targets.
  • 20D (Dodecahedron): A highly connected 20-node network with 30 edges and 7 targets, representing a state space of 78,125 states.
Sensor network configurations 5-P (a) and 11-Helix (b) used to evaluate the eMMDP framework.

Results and Discussion

The LGM algorithm demonstrated significant improvements over standard heuristics and near-optimal performance in practice.

Performance and Scalability

While the theoretical floor is a 2-approximation, empirical tests showed the algorithm consistently achieved 92% to 95% of the optimal reward. Furthermore, the algorithm successfully solved a problem with one million states in just over an hour, a feat standard multi-agent MDP solvers cannot match.

The LGM algorithm's performance as a percentage of optimal increases with the planning horizon, consistently exceeding the theoretical 50% bound.

Comparison to Heuristics

LGM outperformed "immediate reward" heuristics by 20-30%. By accounting for the stochastic movement of targets rather than just their current position, the algorithm often doubled the performance of simpler greedy approaches.

Conclusion

By identifying the submodular nature of event-detection rewards, this work provides a powerful tool for scaling multi-agent systems. Future work includes extending the model to handle interacting targets, infinite planning horizons, and partial observability of agent states.

Summary updated

BibTeX
@inproceedings{kumar2009event,
  author = {Akshat Kumar and Shlomo Zilberstein},
  title = {{Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=H1NEnQMubH},
}
Figure