Graphical models for interactive POMDPs: representations and solutions

Prashant Doshi, Yifeng Zeng, Qiongyu Chen

    Research output: Contribution to journalArticle

    202 Downloads (Pure)

    Abstract

    We develop new graphical representations for the problem of sequential decision making in partially observable multiagent environments, as formalized by interactive partially observable Markov decision processes (I-POMDPs). The graphical models called interactive inf uence diagrams (I-IDs) and their dynamic counterparts, interactive dynamic inf uence diagrams (I-DIDs), seek to explicitly model the structure that is often present in real-world problems by decomposing the situation into chance and decision variables, and the dependencies between the variables. I-DIDs generalize DIDs, which may be viewed as graphical representations of POMDPs, to multiagent settings in the same way that IPOMDPs generalize POMDPs. I-DIDs may be used to compute the policy of an agent given its belief as the agent acts and observes in a setting that is populated by other interacting agents. Using several examples, we show how I-IDs and I-DIDs may be applied and demonstrate their usefulness. We also show how the models may be solved using the standard algorithms that are applicable to DIDs. Solving I-DIDs exactly involves knowing the solutions of possible models of the other agents. The space of models grows exponentially with the number of time steps. We present a method of solving I-DIDs approximately by limiting the number of other agents’ candidate models at each time step to a constant. We do this by clustering models that are likely to be behaviorally equivalent and selecting a representative set from the clusters. We discuss the error bound of the approximation technique and demonstrate its empirical performance.
    Original languageEnglish
    Pages (from-to)376-416
    JournalAutonomous Agents and Multi-Agent Systems
    Volume18
    Issue number3
    DOIs
    Publication statusPublished - 2008

    Bibliographical note

    Author can archive post-print (ie final draft post-refereeing).

    Fingerprint Dive into the research topics of 'Graphical models for interactive POMDPs: representations and solutions'. Together they form a unique fingerprint.

  • Cite this