Location

MIT Media Lab, E14-633

Description

Many problems of economic and societal interest in today's world involve tasks that are inherently distributed in nature. Whether it be the efficient control of robotic warehouses or delivery drones, distributed computing in the Internet of Things, or battling a disease outbreak in a city, they all share a common setting where multiple, distributed agents collaborate to jointly solve a larger task. The ability to quickly find effective solutions in such cooperative multiagent systems (MASs) holds great promise for enabling future applications that require flexibility to changes in tasks or availability of agents.
This thesis contributes to the understanding and efficient exploitation of "locality" for the solution of general, cooperative multiagent Markov Decision Processes (MDPs). To achieve this, the proposed approximation architectures assume that the global solution of the overall system is amendable to representation with sparsely interacting (i.e., local) value function components that–if found–approximate the global solution well. Locality takes on multiple interpretations in the thesis, from its immediate spatial sense to more general sparse interactions between subsets of agents, and the efficient aggregation of local effects in large planning problems. A key result are computational methods for extracting sparse agent coordination graphs in general MASs automatically, while maintaining bounded solutions compared to the optimal value function.
Complex MAS applications generally require a principled trade-off between complexity in agent coordination and solution quality. Robbel's results enable bounded approximate solutions to large multiagent control problems–e.g., disease control with up to 50 agents in graphs with 100 nodes–for which previously only empirical results were reported.

Host/Chair: Cynthia Breazeal

Participant(s)/Committee

Jonathan P. HowMykel J. Kochenderfer