AGENTS VIC Meeting

Friday, 25 November 2011 @ 9:30AM.
Coffee, tea and refreshments from 9:15.

University of Melbourne, Rm 5.07, ICT Building (Dept of CSSE), 111 Barry St., Parkville

Minyi Li, Swinburne University of Technology

Efficient Heuristic Approach to Dominance Testing in CP-nets

CP-net (Conditional Preference Network) is one of the extensively studied languages for representing and reasoning with preferences. The fundamental operation of dominance testing in CP-nets, i.e. determining whether an outcome is preferred to another, is very important in many real-world applications. Current techniques for solving general dominance queries is to search for improving flipping sequence from one outcome to another as a proof of the dominance relation in all rankings satisfying the given CP-net. However, it is generally a hard problem even for binary-valued, acyclic CP-nets and tractable search algorithms exist only for specific problem classes. Hence, there is a need for efficient algorithms and techniques for dominance testing in more general problem settings. In this talk, I will introduce a heuristic approach, called DT*, to dominance testing in arbitrary acyclic multi-valued CP-nets. The proposed approach guides the search process efficiently and allows significant reduction of search effort without impacting soundness or completeness of the search process. I will also present some results of experiments that demonstrate the computational efficiency and feasibility of the proposed approach to dominance testing.