Decentralized Decision Making and Communication with Anytime Algorithms

24 Jun
Thursday, 06/24/2010 6:00am to 8:00am
Ph.D. Dissertation Proposal Defense

Alan Carlin

Computer Science Building, Room 142

The use of multiple agents for problems in planning domains results in several research challenges, above and beyond the challenges in single-agent applications. One challenge lies in reconciling the two differing types of uncertainty in decentralized environments. Whereas a single-agent is merely uncertain about the environment, multiple agents are uncertain about the state of the environment, as well as one another. In partially observable environments, agents may make observations which correlate to the true state. But it is difficult to reason about these observations, as each agent must also consider the perspective of the other agents as well as its observational evidence, and the number of histories of observations grows exponentially with time. One means of addressing this challenge is through agent communication, but this solution brings its own set of challenges. When should agents decide to communicate with one another? In a partially observable environment, how can one agent reason about the communication policy of the others? In order to address these challenges at runtime, agents must engage in deliberation. But deliberation takes time, and in a decentralized environment, accounting for compute time of other agents becomes another source of uncertainty. Thus, a third challenge is how can agents coordinate with one another at planning time, when each agent is unsure of the amount of time the other agents spend deliberating?

In this thesis proposal, we choose the Decentralized Partially Observable Markov Decision Process (Dec-POMDP), as a testbed decentralized framework for studying the above problems. The Dec-POMDP allows specification of uncertainty in both the environment and of other agents. There is a rich literature of work on constructing high quality solutions to Dec-POMDP problems which represent uncertain environments. We will propose to expand upon this work to address the above challenges in three directions. Our first proposed expansion will include (1) compression methods used to represent agent policies in a compact manner. (2) a novel technique, which unlike previous approaches, is robust to cases where agents {\em miscoordinate} because their beliefs about the world differ. Our second proposed expansion will include novel data structures designed to evaluate the value of communication in decentralized, partially observable environments. Our third proposed expansion will construct a method whereby the first two items can be used for decentralized meta-deliberation, that is, the agents will concurrently consider when to stop planning and start execution.

Advisor: Shlomo Zilberstein