ORCID
http://orcid.org/0000-0001-5317-8425
Date of Award
Summer 8-15-2021
Degree Name
Doctor of Philosophy (PhD)
Degree Type
Dissertation
Abstract
Constraint-based models offer powerful approaches for describing and resolving many combinatorial optimization problems in a centralized or distributed environment. In such models, the goal is to find a value assignment to a set of variables given a set of preferences expressed by means of cost functions such that the sum over all costs is optimized. The importance of constraint-based models is outlined by the impact of their applications in a wide range of agent-based systems. Many real-life combinatorial problems can be naturally formalized using constraint-based models. Examples of such applications are supply-chain management, roster scheduling, meeting scheduling, combinatorial auctions, bioinformatics, and smart home automation.
The majority of these constraint-based models assume that all constraint costs are specified or known a priori. Unfortunately, such an assumption is impractical, especially in many human-in-the-loop applications, such as scheduling problems where constraints encode the preferences of human users. These constraints may not be fully specified because it is unrealistic to accurately know the preferences of users for all possible scenarios in an application. These constraint costs are only known after they are queried or elicited from domain experts or human users.
This dissertation proposes solutions for further improving the applicability of constraint-based models. These solutions aim for better formalizing and solving optimization problems, requiring human interactions to address the above limitation. Our core contributions are listed as follows:
We begin by introducing the uncertain constraint-based model that represents the uncertainty in users' preferences (i.e., constraint costs) as Gaussian distributions. To solve such a constraint-based model with uncertainty, we propose probabilistic heuristics that select a subset of constraints to elicit and choose those that significantly impact the overall solution quality. The elicitation of these preferences occurs prior to the execution of the search algorithm for an optimal solution.
Human users are likely bothered by repeated elicitations and will refuse to provide an unbounded number of preferences. Hence, as our next contribution, we propose the incomplete weighted constraint satisfaction problems with elicitation costs (IWCSPs+EC) that takes into consideration how much users are bothered by queries. To solve IWCSPs+EC, we offer three parameterized heuristics that allow users to trade off solution quality for fewer elicited preferences and faster computation times. Further, they provide theoretical quality guarantees for problems where elicitations are free.
Finally, we extend IWCSPs to distributed problems and introduce incomplete distributed constraint optimization problems (I-DCOPs). To solve I-DCOPs, we propose an extended version of SyncBB -- a complete search algorithm -- with two parameterized heuristics. These heuristics interleave the elicitation process with the search for an optimal solution. Our proposed heuristics for SyncBB allow users to trade off solution quality for fewer elicited preferences and faster computation times. To improve the scalability of our proposed framework, we offer an extended version of ALS-MGM -- a local search algorithm -- which can solve much larger I-DCOPs. Local search algorithms are computationally much faster and provide sub-optimal or close to optimal solutions. The number of elicited preferences is significantly smaller than SyncBB with heuristics, and its solution quality is not far from optimal.
We apply our proposed model to smart home device scheduling and distributed meeting scheduling applications with partial users' preferences. The empirical results show the significance of our contributions against random methods and the previous state-of-the-art approaches. Our models and heuristics thus extend the state-of-the-art in constraint reasoning to better model and solve agent-based applications with user preferences.
Language
English (en)
Chair
William Yeoh
Committee Members
Roman Garnett, Judy Goldsmith, Chien-Ju Ho, Alvitta Ottley,