Project Abstract

In this project we study planning under uncertainty for groups of cooperating multiagent systems. Developing intelligent robots or other real-world systems that plan and perform an assigned task is a major goal of Artificial Intelligence and Robotics. We develop general methodology and algorithms, and tackle case studies such as multi-robot urban search and rescue.

Planning, or sequential decision-making skills form a crucial component of any intelligent system: how should a system act over time in order to perform its task as well as possible. When a system is part of a team, its performance depends on the actions chosen by its teammates. An important aspect of decision making in a real-world system is the fact that the system should be able to deal with uncertainty from numerous sources. For instance, a major source of uncertainty for a robot are its sensors, which are often noisy and have only a limited view of the environment. A robot is also often uncertain about the effect that executing an action has on its environment. A third source of uncertainty are an agent´s teammates, as, in general, an agent will not be able to predict with full certainty what actions its teammates will perform. Furthermore, one has to consider the communication abilities available to each system and restrictions on available bandwidth or network reliability.

We develop algorithms that allow systems to handle uncertainty in sensors, actuators, communication, and teammate behavior in a principled way. We capture uncertainty in probabilistic models, which allows us to model the sequential decision-making problem as a centralized or decentralized partially observable Markov decision process (POMDP). Decentralized POMDPs (DEC-POMDPs) form a general framework for representing cooperative planning under uncertainty problems. In this project, we focus on the following issues: (1) developing approximate planning algorithms for relevant subsets of the general DEC-POMDP model, (2) examining the tradeoff between centralized vs. decentralized planning algorithms and (3) tackling various communication models. Furthermore, we see how these techniques can be used in case studies.