Exploiting model equivalences for solving interactive dynamic influence diagrams

DOI10.1613/JAIR.3461MaRDI QIDQ2887070zbMATH OpenOpenAlexFDO

Authors Prashant Doshi, Yifeng Zeng

Publication date 16 May 2012

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4600

zbMATH Keywords

interactive dynamic influence diagrammodel spacemultiagent settingsequential decision making

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Machine vision and scene understanding (68T45)

Abstract: We focus on the problem of sequential decision making in partially observable environments shared with other agents of uncertain types having similar or conflicting objectives. This problem has been previously formalized by multiple frameworks one of which is the interactive dynamic influence diagram (I-DID), which generalizes the well-known influence diagram to the multiagent setting. I-DIDs are graphical models and may be used to compute the policy of an agent given its belief over the physical state and others models, which changes as the agent acts and observes in the multiagent setting. As we may expect, solving I-DIDs is computationally hard. This is predominantly due to the large space of candidate models ascribed to the other agents and its exponential growth over time. We present two methods for reducing the size of the model space and stemming its exponential growth. Both these methods involve aggregating individual models into equivalence classes. Our first method groups together behaviorally equivalent models and selects only those models for updating which will result in predictive behaviors that are distinct from others in the updated model space. The second method further compacts the model space by focusing on portions of the behavioral predictions. Specifically, we cluster actionally equivalent models that prescribe identical actions at a single time step. Exactly identifying the equivalences would require us to solve all models in the initial set. We avoid this by selectively solving some of the models, thereby introducing an approximation. We discuss the error introduced by the approximation, and empirically demonstrate the improved efficiency in solving I-DIDs due to the equivalences.

Recommendations

• scientific article; zbMATH DE number 2243394
• Monte Carlo sampling methods for approximating interactive POMDPS
• Solving limited memory influence diagrams
• An integrated approach to solving influence diagrams and finite-horizon partially observable decision processes
• Junction Tree Factored Particle Inference Algorithm for Multi-Agent Dynamic Influence Diagrams

Cited in

(9)

• Autonomous agents modelling other agents: a comprehensive survey and open problems
• An integrated approach to solving influence diagrams and finite-horizon partially observable decision processes
• Recursively modeling other agents for decision making: a research perspective
• Making friends on the fly: cooperating with new teammates
• A survey of opponent modeling in adversarial domains
• Junction Tree Factored Particle Inference Algorithm for Multi-Agent Dynamic Influence Diagrams
• scientific article; zbMATH DE number 4189254 (Why is no real title available?)
• A sufficient statistic for influence in structured multiagent environments
• Behavioral model summarisation for other agents under uncertainty

This page was built for publication: Exploiting model equivalences for solving interactive dynamic influence diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2887070)