Thesis: Ph. D., Massachusetts Institute of Technology, School of Architecture and Planning, Program in Media Arts and Sciences, 2016. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 137-145). / 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 agents collaborate to jointly solve a larger task. he ability to quickly and effective solutions in such multiagent systems (MASs) forms an important prerequisite for enabling applications that require flexibility to changes in tasks or availability of agents. his 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 solution of the overall system can be represented with sparsely interacting (i.e., local) value function components that -- if found -- approximate the global solution well. Locality takes on multiple interpretations, from its spatial sense to more general sparse interactions between subsets of agents, and the efficient representation of local effects in large planning problems. Developed in the thesis are computational methods for extracting sparse agent coordination structure automatically in general, cooperative MDPs. Based on novel theoretical insights about factored value functions, the proposed algorithms automate the search for coordination via principled basis expansion in the approximate linear program (ALP). We show that the search maintains bounded solutions with respect to the optimal solution and that the bound improves monotonically. Introduced then are novel solution methods that exploit "anonymous influence" in a particular class of factored MDPs. We show how anonymity can lead to representational and computational efficiencies, both for general variable elimination in a factor graph but also for the ALP solution to factored MDPs. he latter allows to scale linear programming to MDPs that were previously unsolvable. Complex MAS applications require a principled trade-off between complexity in agent coordination and solution quality. he thesis 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. / by Philipp Robbel. / Ph. D.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/105943 |
| Date | January 2016 |
| Creators | Robbel, Philipp |
| Contributors | Cynthia Breazeal., Program in Media Arts and Sciences (Massachusetts Institute of Technology), Program in Media Arts and Sciences (Massachusetts Institute of Technology) |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 145 pages, application/pdf |
| Rights | M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.002 seconds