Value-Based Planning for Teams of Agents in Stochastic Partially Observable Environments
Frans A. Oliehoek · Amsterdam University Press eBooks · 2010
1. Operate in a highly dynamic environment and to cope with the changes in the environment.2. Support reasoning with uncertainty, reasoning with risks and reasoning in the absence of knowledge, necessary because of the chaotic nature of the real world.In particular, the system should be able to reach a set of (determined) 1 Multiagent SystemsThe field of MASs is a broad interdisciplinary field with relations to distributed and concurrent systems, artificial intelligence (AI), economics, logic, philosophy, ecology and social sciences (Wooldridge, 2002).The sub-field of AI that deals with principles and design of MASs is also referred to as 'distributed AI'.Research on MASs is motivated by the fact that it can potentially provide (Vlassis, 2007;Sycara, 1998):• Speedup and efficiency, due to the asynchronous and parallel computation.• Robustness and reliability: the whole system can undergo a 'graceful degradation' when one or more agents fail. Planning with Outcome UncertaintyThe MDP is a framework for sequential decision making of a single agent at predetermined points in time, i.e., it is a discrete time model.The extension of the MDP to continuous time is called a semi-Markov decision process (SMDP).Also in control theory much research has considered continuous time settings (Sontag, 1998).In order to solve such continuous time settings, however, time is discretized Multiple AgentsAlthough POMDPs provide principled treatment of state uncertainty, they only consider a single agent.In order to deal with the effects of uncertainty with respect to other agents, this thesis will consider an extension of the POMDP framework.We also note that this type of uncertainty may be mitigated through communication.Under the stringent assumptions of instantaneous, cost-and noise free communication, they can be discarded altogether, and the problem reduces to a POMDP (Pynadath and Tambe, 2002b).However, in general these assumptions are too strong and deciding when to communicate what becomes part of the problem.Chapter 3 considers various assumptions with respect to communication delays in MASs.The main focus of this thesis, however is the truly decentralized, non-communicative setting.As it turns out, the framework we consider for these non-communicative MASs can also model communication with a particular cost that is subject to minimization (Pynadath and Tambe, 2002b;Goldman and Zilberstein, 2004) and the non-communicative setting can be interpreted as the special case with infinite cost.In a MAS each agent can be considered separately.In this case, which we refer to as the subjective perspective of a MAS, each such agent maintains an explicit model of the other agents.This is the approach as chosen in the recursive modeling method (RMM) (Gmytrasiewicz and Durfee, 1995;Gmytrasiewicz, Noh, and Kellogg, 1998) and the interactive POMDP (I-POMDP) framework (Gmytrasiewicz and Doshi, 2005).A difficulty in these approaches, however, is that the other agents also model the considered agent, leading to an infinite recursion of beliefs regarding the behavior of agents.Moreover, the number of possible models of other agents is infinite.Even though there might be solutions to these problems (Rathnasabapathy, Doshi, and Gmytrasiewicz, 2006;Zettlemoyer, Milch, and Kaelbling, 2009), we feel that this approach is more appropriate for systems with self-interested agents.The assumption in this thesis is that planning takes place in an off-line phase, after which the plans are executed in an on-line phase.In the decentralized setting, however, this statement deserves some clarification.In the on-line phase the computed plan is executed in a completely decentralized way: each agent knows only the joint policy as found in the planning phase and its individual history of actions and observations.The planning phase, however, can be viewed in two ways.First, we can think of a centralized computer that computes the joint plan and consequently distributes these plans to the agents, who then merely execute the plans on-line.In this view the agents are reactive and all the intelligence comes from the centralized computer.The second view is that each agent runs the same planning algorithm in parallel and therefore each agent computes the same joint plan from which it executes its individual component.In this view the planning phase is decentralized too and the agents are decision theoretic.This thesis will not consider decentralization of computation of plans in order the provide an increase in efficiency, i.e., methods that break up the planning problem in sub-problems which are then distributed and processed in parallel.Although such methods are of great interest, the centralized-planning case assumed in this thesis presents enough challenges by itself. ApplicationsBecause of the complexity of multiagent decision making under uncertainty, research has been forced to restrict itself to toy problems, as there are no real-life