On the Integration of CP-nets in ASPRIN

Mario Alviano, Javier Romero, Torsten SchaubIJCAI 2019 · DOI

TL;DR

This paper introduces an extension to the ASPRIN framework for integrating Conditional Preference Networks (CP-nets) into Answer Set Programming (ASP). This allows for more expressive representation of user preferences, combining qualitative CP-nets with other preference types and enabling more sophisticated reasoning over complex knowledge bases.

What Problem Does This Paper Address?

Answer Set Programming (ASP) is a powerful paradigm for knowledge representation and reasoning, but it often produces multiple solutions (answer sets). When these solutions need to be ranked based on user preferences, existing ASP mechanisms like weak constraints primarily handle quantitative preferences. Representing qualitative preferences, especially those that depend on combinations of other features (e.g., "I prefer a convertible car, but only if it has a dark paint job"), is challenging. Conditional Preference Networks (CP-nets) are a natural way to express such qualitative, conditional preferences using "ceteris paribus" (all else being equal) rules. However, integrating CP-nets directly into ASP frameworks has been a gap. This paper addresses this by extending ASPRIN, a flexible ASP preference framework, to seamlessly incorporate CP-nets.

Methods

The core contribution is the integration of CP-nets into ASPRIN through several key methods:

  • Preference Program for CP-nets: A novel ASP program is developed that reifies CP-nets. This program, when instantiated with a CP-net and two interpretations (potential solutions), is consistent if and only if the first interpretation is preferred to the second according to the CP-net. This program is used by ASPRIN's iterative sat-unsat search algorithm to find optimal answer sets.
  • Approximation for Acyclic CP-nets: For acyclic CP-nets, the paper proposes an approximation using poset (partially ordered set) preference relations. This allows leveraging existing, highly optimized ASP solvers for preference reasoning. This approximation is based on an expansion function that maps CP-nets to a domain of auxiliary atoms.
  • Linear-Time Dominance Testing for Tree-Shaped CP-nets: For the specific and tractable case of tree-shaped CP-nets, a linear-time algorithm (TREEDT) is adapted and implemented. This significantly speeds up dominance testing for this important subclass of CP-nets.

Datasets

Not discussed in the paper. The paper focuses on the integration of CP-nets into a reasoning framework and uses examples to illustrate the methods.

Key Insights and Ideas

  • Bridging Qualitative and Quantitative Preferences: The integration of CP-nets in ASPRIN is crucial for handling real-world scenarios where users have both qualitative (e.g., "I prefer X over Y") and quantitative (e.g., "minimize cost") preferences. ASPRIN's ability to mix these makes it more versatile.
  • The Power of Approximation: Approximating complex preference structures like acyclic CP-nets with simpler ones (posets) is a powerful technique. It allows existing, efficient solvers to handle more complex problems, trading off exactness for computational feasibility.
  • Algorithmic Specialization for Tractable Cases: Recognizing that tree-shaped CP-nets are computationally easier to handle, the paper leverages specialized algorithms (TREEDT) to achieve linear-time dominance testing, demonstrating a practical approach to optimizing performance for specific problem structures.
  • Reification as a Unifying Mechanism: The paper highlights how reifying CP-nets into ASP facts (using preference programs) allows them to be treated uniformly within the ASPRIN framework, enabling combinations with other preference types.

Key Results

  • The paper successfully integrates CP-nets into the ASPRIN framework, providing a mechanism to express and reason with qualitative, conditional preferences within ASP.
  • An approximation technique for acyclic CP-nets using posets is developed, enabling the use of existing ASP solvers for preference reasoning.
  • A linear-time algorithm for dominance testing of tree-shaped CP-nets is presented, offering significant performance improvements for this class of problems.
  • Experimental results (Figure 5) suggest that for larger CP-nets, the linear encoding for tree-shaped CP-nets and the poset approximation for acyclic CP-nets are necessary for practical performance, often outperforming other methods. Timeouts were observed for many larger instances, indicating the computational challenges.

Limitations and Future Work

  • Scalability for Large CP-nets: While improvements are shown, the experiments indicate that for CP-nets with hundreds of atoms, performance can still be an issue, with many timeouts observed. This suggests that further optimizations or more advanced approximation techniques might be needed.
  • General CP-net Dominance Testing: The paper notes that dominance testing for general CP-nets is PSPACE-complete, and while approximations and specialized algorithms are provided, efficient handling of arbitrary cyclic CP-nets remains a challenge.
  • Future Work: The authors suggest that the developed techniques are a step towards a more comprehensive preference reasoning system. Future work could explore further optimizations, more sophisticated approximation strategies, and broader integration with other reasoning paradigms. The paper also hints at the possibility of introducing "don't care" atoms for more nuanced preference specifications.

Summary updated

BibTeX
@inproceedings{alviano2019integration,
  author = {Mario Alviano and Javier Romero and Torsten Schaub},
  title = {{On the Integration of CP-nets in ASPRIN}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/207},
}

Loading related content...

Figure