CSE
CSE
CSE CSE


Defense Event

Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty

Stefan Witwicki


 
Wednesday, December 15, 2010
11:00am - 1:00pm
3725 Beyster Bldg.

Add to Google Calendar

About the Event

When planning optimal decisions for teams of agents acting in uncertain domains, conventional methods involve jointly coordinating all agentsí decisions and, in doing so, are inherently susceptible to the curse of dimensionality, as state, action, and observation spaces grow exponentially with the number of agents. With the goal of extending the scalability of optimal team coordination, this dissertation pursues a fundamentally different approach. Intuitively, to the extent that agents are weakly-coupled, they can avoid the complexity of coordinating their complete policies; they need instead only coordinate their essential influences. In formalizing this intuition, I consider several complementary aspects of weakly-coupled problem structure, including agent scope size, which is the number of an agentís peers whose decisions influence the agentís decisions, and degree of influence, which is the proportion of peer policies that differently-influence the agent. As I derive, exponential reductions in the computational complexity of optimal planning are achieved by exploiting either aspect. Towards this end, I introduce a general class of transition-dependent decentralized POMDPs for which the joint decision model decomposes into local decision models whose nonlocally-dependent transitions may be treated as influences abstracted from peersí policies. Equating influence to transition probability and expressing policy in its dual form gives rise to a bidirectional mapping between detailed policy and abstract influence. In effect, the agent can move back and fourth between the policy space and the influence space, without sacrificing optimality of local behavior, using linear programming. Ultimately, the advantage of working in the influence space is that there are potentially significantly fewer feasible influences than there are policies. Extending prior work on decoupled joint policy search, I develop influence-space search algorithms that, for problems with a low degree of influence, compute optimal solutions orders of magnitude faster than policy-space search. When agentsí influences are constrained, influence-space search also outperform other state-of-the-art optimal solution algorithms. Moreover, by exploiting both degree of influence and agent scope size, I demonstrate scalability, substantially beyond the reach of prior optimal methods, to teams of 50 weakly-coupled transition-dependent agents.

Additional Information

Sponsor(s): Edmund Durfee

Open to: Public