Abstract

The Distributed Constraint Optimization Problem(DCOP)formulation is a powerful tool to model cooperative multi-agent problems, especially when they are sparsely constrained with one another. A key assumption in this model is that all constraints are fully specified or known a priori, which may not hold in applications where constraints encode preferences of human users. In this thesis, we extend the model to Incomplete DCOPs (I-DCOPs), where some constraints can be partially specified. User preferences for these partially-specified constraints can be elicited during the execution of I-DCOP algorithms, but they incur some elicitation costs. Additionally, we propose two parameterized heuristics that can be used in conjunction with Synchronous Branch-and-Bound to solve I-DCOPs. These heuristics allow users to trade-off solution quality for faster runtimes and a smaller number of elicitations. They also provide theoretical quality guarantees for problems where elicitations are free. Our model and heuristics thus extend the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.

Committee Chair

William Yeoh

Committee Members

Ayan Chakrabarti Chien-Ju Ho

Comments

Permanent URL: https://doi.org/10.7936/04rd-ed64

Degree

Master of Science (MS)

Author's Department

Computer Science & Engineering

Author's School

McKelvey School of Engineering

Document Type

Thesis

Date of Award

Spring 5-2020

Language

English (en)

Download

Included in

Engineering Commons

Share

COinS