SPIDER attack on a network of POMDPs: Towards quality bounded solutions

Pradeep Varakantham, Janusz Marecki, Milind Tambe, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Distributed Partially Observable Markov Decision Problems (Distributed POMDPs) are a popular approach for modeling multi-agent systems acting in uncertain domains. Given the significant computational complexity of solving distributed POMDPs, one popular approach has focused on approximate solutions. Though this approach provides for efficient computation of solutions, the algorithms within this approach do not provide any guarantees on the quality of the solutions. A second less popular approach has focused on a global optimal result, but at considerable computational cost. This paper overcomes the limitations of both these approaches by providing SPIDER (Search for Policies In Distributed EnviRonments), which provides quality-guaranteed approximations for distributed POMDPs. SPIDER allows us to vary this quality guarantee, thus allowing us to vary solution quality systematically. SPIDER and its enhancements employ heuristic search techniques for finding a joint policy that satisfies the required bound on the quality of the solution.

Original languageEnglish
Title of host publicationGame Theoretic and Decision Theoretic Agents - Papers from the 2007 AAAI Spring Symposium, Technical Report
Number of pages8
Publication statusPublished - 2007
Event2007 AAAI Spring Symposium - Stanford, CA, United States
Duration: Mar 26 2007Mar 28 2007

Publication series

NameAAAI Spring Symposium - Technical Report


Other2007 AAAI Spring Symposium
Country/TerritoryUnited States
CityStanford, CA

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'SPIDER attack on a network of POMDPs: Towards quality bounded solutions'. Together they form a unique fingerprint.

Cite this