Generalized Solution Techniques for Preference-Based Constraint Optimization with CP-nets

Computational agents can assist people by guiding their decisions in ways that achieve their goals while also adhering to constraints on their actions. Because some domains are more naturally modeled by representing preferences and constraints separately, we seek to develop efficient techniques for solving such decoupled constraint optimization problems. This paper describes a parameterized formulation for decoupled constraint optimization problems that subsumes the state-of-the-art algorithm of Boutilier et al, representing a wider family of alternative algorithms. We empirically examine notable members of this family to highlight the spaces of decoupled constraint optimization problems for which each excels, highlight fundamental relationships between different algorithmic variations, and use these insights to create and evaluate novel hybrids of these algorithms that a cognitive assistant agent can use to flexibly trade off solution quality with computational time.

Authors

• James Boerkoel
• Ed Durfee
• Keith Purrington Edmund H. Durfee

Keywords

No keywords are indexed for this paper.