Multiagent Planning in Partially Observable Uncertain Worlds

Abstract

Coordinating the operation of a group of decision makers or agents in stochastic environments is a long-standing challenge in AI. Decision theory offers a normative framework for optimizing decisions under uncertainty. But due to computational complexity barriers, developing decision-theoretic planning algorithms for multiagent systems is a serious challenge. We describe a range of new formal models and algorithms to tackle this problem. Exact algorithms shed light on the structure and complexity of the problem, but they have limited use as only tiny problems can be solved optimally. We describe a number of effective approximation techniques that use bounded memory, sampling, and randomization. These methods can produce high-quality results in a variety of application domains such as mobile robot coordination and sensor network management. We examine the performance of these algorithms and describe current research efforts to further improve their applicability and scalability.

Bio: Shlomo Zilberstein is professor of computer science at the University of Massachusetts, Amherst. He received his Ph.D. from UC Berkeley and his B.A. from the Technion. His research focuses on the foundations of automated planning and the development of formal models of rational behavior in situations characterized by uncertainty and limited computational resources. He is a fellow of the Association for the Advancement of Artificial Intelligence. He has received the NSF RIA (1994) and CAREER (1996) awards, and best paper awards from ECAI (1998), AAMAS (2003), IAT (2005), MSDM (2008) and ICAPS (2010). He is the former editor-in-chief of the Journal of Artificial Intelligence Research, former president of ICAPS and a current councilor of AAAI.