Preference Elicitation in DCOPs for Scheduling Devices in Smart Buildings

Atena M. TabakhiAAAI 2017 · DOI

Abstract

Efficient energy management in smart buildings requires balancing electricity costs with occupant comfort. This task is often modeled as a Distributed Constraint Optimization Problem (DCOP). However, a significant hurdle in real-world deployment is the uncertainty surrounding user preferences, which are often private and tedious to elicit in full. This paper proposes a framework for strategic preference elicitation within uncertain DCOPs. We introduce two heuristics—Average of the Variance (AV) and Variance of the Variance (VV)—to identify and reveal the most impactful user preferences. Our evaluation on a synthetic Smart Building Devices Scheduling (SBDS) benchmark demonstrates that these targeted elicitation strategies significantly improve scheduling accuracy compared to random baselines, enabling near-optimal coordination with minimal user burden.

Introduction

As smart building technology matures, the challenge shifts from simple automation to complex coordination. In a neighborhood of smart buildings, devices must be scheduled to minimize overall energy costs—often by shifting loads away from peak hours—while respecting the comfort and preferences of residents. This problem is naturally suited for Distributed Constraint Optimization Problems (DCOPs), where agents (buildings) coordinate to optimize a global objective function.

A critical limitation of standard DCOP models is the assumption of complete information. In practice, the "cost" of a resident's discomfort (e.g., running a noisy appliance during a preferred quiet time) is unknown until the user is specifically queried. Because exhaustive preference collection is intrusive and impractical, there is a pressing need for methods that can strategically "elicit" only the most critical information to achieve high-quality schedules.

Methodology

We model the Smart Building Devices Scheduling (SBDS) problem by combining two distinct objectives into a single weighted sum: monetary electricity costs and user discomfort values. The goal is to minimize this combined cost across the entire neighborhood.

To address preference uncertainty, we propose a framework where only a subset $k$ of the total constraints (representing user preferences) are revealed. We introduce two heuristic methods to select which constraints to elicit:

  • Average of the Variance (AV): This heuristic prioritizes constraints that exhibit the highest average variance in their estimated costs. The underlying intuition is that high variance indicates high uncertainty; by resolving this uncertainty, the system gains the most valuable information for optimization.
  • Variance of the Variance (VV): A more sophisticated approach that examines the "uncertainty of the uncertainty." It prioritizes constraints where the variance itself varies significantly across different possible assignments, targeting areas where the potential for error reduction is greatest.

These heuristics are compared against a Random (RN) baseline, which selects constraints for elicitation without any strategic prioritization.

Experimental Setup

The proposed methods were evaluated using a synthetic SBDS benchmark. The simulation environment consisted of 10 buildings, each managing 10 smart devices over a 12-hour time horizon divided into 30-minute increments. To account for the inherent uncertainty in user preferences, the researchers generated 50 different "realizations" of the problem space to calculate the expected error of the resulting schedules.

Results and Discussion

The primary metric for evaluation is the Normalized Error, which represents the gap between the schedule produced with limited information and the "perfect" schedule that would be achieved with 100% preference knowledge.

Normalized Error vs. Percentage of Elicited Constraints (k)

As shown in Figure 1, the Normalized Error decreases for all methods as the percentage of elicited constraints ($k$) increases. The results highlight several key findings:

  • Effectiveness of Heuristics: The proposed heuristic methods demonstrate a clear advantage in reducing scheduling error. By focusing on constraints with high statistical uncertainty, these methods capture the most influential preferences early in the elicitation process, consistently outperforming random selection.
  • Efficiency and Convergence: Even with a limited elicitation budget (e.g., $k=40\%$ or $60\%$), the heuristic methods achieve significantly lower error rates than random selection. As $k$ reaches 80%, the error drops to near-zero levels, suggesting that the vast majority of scheduling quality can be recovered by asking only a fraction of the possible questions.
  • Information Prioritization: The success of these methods confirms that not all user preferences are equally important for global coordination. Identifying "pivot" preferences allows the system to respect user boundaries without causing "survey fatigue."

Conclusion and Future Work

This research demonstrates that strategic preference elicitation is a viable path toward practical smart building coordination. By treating uncertainty as a guide, DCOP-based systems can achieve high efficiency and user satisfaction with minimal data requirements.

Future research will focus on scaling these methods to larger, city-wide grids and incorporating real-world human preference data, which may be more complex than the synthetic distributions used here. Additionally, exploring dynamic preferences—where user needs change based on external factors like weather or time of day—remains an important frontier for making smart buildings truly adaptive.

Summary updated

BibTeX
@inproceedings{tabakhi2017preference,
  author = {Atena M. Tabakhi},
  title = {{Preference Elicitation in DCOPs for Scheduling Devices in Smart Buildings}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11094},
}
Figure