Search Swinburne Research Bank
This object has not yet been indexed by the background indexing service.
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.3/202593
|Download PDF (Published version) (Adobe Acrobat PDF, -1 bytes)|
- Efficient heuristic approach to dominance testing in CP-nets
- Li, Minyi; Vo, Quoc Bao; Kowalczyk, Ryszard
- 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 CPnets 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 paper, we propose a heuristic approach, called DT*, to dominance testing in arbitrary acyclic multi-valued CP-nets. Our proposed approach guides the search process efficiently and allows significant reduction of search effort without impacting soundness or completeness of the search process. We present results of experiments that demonstrate the computational efficiency and feasibility of our approach to dominance testing.
- Publication type
- Conference paper
- Research centre
- Swinburne University of Technology
- Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan, 02-06 May 2011 / Kagan Tumer, Pinar Yolum, Liz Sonenberg and Peter Stone (eds.), pp. 353-360
- Publication year
- International Foundation for Autonomous Agents and Multiagent Systems
- Publisher URL
- Copyright © 2011 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). The published version is reproduced in accordance with the copyright policy of the publisher.