Embedding Preference Elicitation Within the Search for DCOP Solutions

A key assumption in Distributed Constraint Optimization Problem (DCOP) 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. 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 extend the Synchronous Branch-and-Bound (SyncBB) algorithm to solve I-DCOPs. Our model extends the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.