Return to search

Online Planning in Multiagent Expedition with Graphical Models

This dissertation proposes a suite of novel approaches for solving multiagent decision and optimization problems based on the Collaborative Design Network (CDN), a framework for multiagent decision making.
The framework itself is distributed, decision-theoretic and was originally proposed for multiagent component-centred design. This application is a novel use of the CDN, and demonstrate the generality of the CDN framework for general decision-theoretic planning.

First, the framework is applied towards tackling a multiagent decision problem outside of collaborative design called multiagent expedition (MAE), a testbed problem which abstracts many of the features of real-world multiagent decision-making problems. We formally introduce MAE, and show it to be a subclass of a decentralized partially observable Markov Decision process (Dec-POMDP).

We apply the CDN to the online MAE planning problem. We demonstrate that the CDN can plan in MAE with conditional optimality given a set of basic assumptions on the structure and organization of the agent team. We introduce a set of knowledge representational aspects to achieve conditionally optimal planning. We experimentally verify our approach on a series of benchmark problems created for this dissertation to test the
various aspects of our CDN solution.

We also investigate further methods for scalability and speedup in MAE. The concept of \emph{partial evaluation} (PE) is introduced, based on the assumption that an agent has an intended effect given an agent's action and considers all other effects unintended. This assumption is used to derive a bound for planning that partitions the set of joint plans into a set of fully evaluated and a set of partial evaluated plans. Plans which are partially evaluated can significantly speed up planning in the centralized case.
PE is also applied to the CDN, to both public decisions between agents and private decisions local to an agent. We demonstrate that applying PE to public decisions in the CDN results in either intractable communication or suboptimal planning. When applied to private decisions, we show PE can still be very effective in decreasing planning runtime.

Identiferoai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OGU.10214/3191
Date14 December 2011
CreatorsHanshar, Franklin
ContributorsXiang, Yang
Source SetsLibrary and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada
LanguageEnglish
Detected LanguageEnglish
TypeThesis

Page generated in 0.0019 seconds