Article: A Framework for Sequential Planning in Multi-Agent Settings

[jai...@ptolemy.arc.nasa.gov]

JAIR is pleased to announce the publication of the following article:

Gmytrasiewicz, P. J. and Doshi, P. (2005)
"A Framework for Sequential Planning in Multi-Agent Settings",
Volume 24, pages 49-79.

For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/gmytrasiewicz05a.html

Abstract:
This paper extends the framework of partially observable Markov
decision processes (POMDPs) to multi-agent settings by incorporating
the notion of agent models into the state space. Agents maintain
beliefs over physical states of the environment and over models of
other agents, and they use Bayesian updates to maintain their beliefs
over time. The solutions map belief states to actions. Models of other
agents may include their belief states and are related to agent types
considered in games of incomplete information. We express the agents'
autonomy by postulating that their models are not directly manipulable
or observable by other agents. We show that important properties of
POMDPs, such as convergence of value iteration, the rate of
convergence, and piece-wise linearity and convexity of the value
functions carry over to our framework. Our approach complements a
more traditional approach to interactive settings which uses Nash
equilibria as a solution paradigm. We seek to avoid some of the
drawbacks of equilibria which may be non-unique and do not capture
off-equilibrium behaviors. We do so at the cost of having to
represent, process and continuously revise models of other agents.
Since the agent's beliefs may be arbitrarily nested, the optimal
solutions to decision making problems are only asymptotically
computable. However, approximate belief updates and approximately
optimal plans are computable. We illustrate our framework using a
simple application domain, and we show examples of belief updates and
value functions.

The article is available via:

-- comp.ai.jair.papers (also see comp.ai.jair.announce)

-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/gmytrasiewicz05a.html

-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume24/gmytrasiewicz05a.ps
The compressed PostScript file is named gmytrasiewicz05a.ps.Z

For more information about JAIR, visit our WWW or FTP sites, or
contact jai...@isi.edu

--
Steven Minton
JAIR Managing Editor