Event Location: NSH 1507

Abstract: In many domains, teams of hundreds of agents must cooperatively plan to perform tasks in a complex, uncertain environment. Naively, this requires that each agent take into account every teammates’ state, observation, and choice of action when making decisions about its own actions. This results in a huge joint policy space over which it is computationally intractable to find solutions. In certain problems, however, searching this complete space may not be necessary. Specifically, there are problems in which individual agents usually act independently, but have a few combinations of states and actions in which they share a non-factorable transition, reward, or observation function with one or more teammates.

This thesis focuses on exploiting this structure, along with two other properties that are often present in these cases, to greatly improve planning efficiency. First, while there are a large number of possible interactions between agents, the number of interactions that actually occur in a particular solution instance is often quite small. It is therefore possible to disregard many irrelevant combinations of interactions by dynamically handling only those that arise during the planning process. Second, in the case of intelligent agents, computational power itself is often distributed across the team. Thus, distributed approaches have access to computational resources that grow linearly with team size, making it easier to scale to very large teams.

Taking advantage of these properties, we propose DIMS, a framework in which agents plan iteratively and concurrently over independent local models which are then shaped by the expected observations, movements and rewards of their teammates. By dynamically discovering relevant interactions and distributing computation, planning efficiency is greatly improved, allowing joint solutions to be computed for teams into the hundreds of agents.

Committee:Katia Sycara, Co-chair

Paul Scerri, Co-chair

J. Andrew Bagnell

Edmund H. Durfee, University of Michigan