Efficient Compilation Approach on Stratified Weighted Bases
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [22]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    To be in accordance with the thinking habits of human and improve the efficiency of reasoning, thisstudy argues to stratify weighted bases. The study shows that the existing compilation approach to non-stratifiedweighted bases can also be applied to COMPILE stratified weighted bases; however, its time and space costs arerelatively high because of redundant information in the compilation results. The paper proposes a novel compilationapproach, which can remove the redundant information in the process of compilation, and presents two optimizationtechniques to further improve the time efficiency. As with the existing approach, re-compiling a stratified weightedbase is not required whenever the weights associated with soft constraints change with time. The approach is testedby compiling random instances into ROBDD-normal bases, and the preliminary experimental results show that thetime and space costs of this approach are lower than the existing approach for most instances.

    Reference
    [1] Chevaleyre Y, Endriss U, Lang J, Maudet N. Preference handling in combinatorial domains: From AI to social choice. AI Magazine,2008,29(4):37 46.
    [2] Wilson N. Efficient inference for expressive comparative preference languages. In: Boutilier C, ed. Proc. of the 21st Int’l Joint Conf. on Artificial Intelligence (IJCAI 2009). AAAI Press, 2009. 961 966.
    [3] Boutilier C, Brafman RI, Domshlak C, Hoos HH, Poole D. CP-Nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research, 2004,21:135 191. [doi: 10.1613/jair.1234]
    [4] Chomicki J. Preference formulas in relational queries. ACM Trans. on Database Systems, 2003,28(4):1 40. [doi: 10.1145/958942.958946]
    [5] Pinkas G. Propositional nonmonotonic reasoning and inconsistency in symmetric neural networks. In: Mylopoulos J, Reiter R, eds. Proc. of the 12th Int’l Joint Conf. on Artificial Intelligence (IJCAI’91). San Francisco: Morgan Kaufmann Publishers, 1991.525 530.
    [6] Pinkas G. Reasoning, nonmonotonicity and learning in connectionist networks that capture propositional knowledge. Artificial Intelligence, 1995,77(2):203 247.
    [7] Coste-Marquis S, Lang J, Liberatore P, Marquis P. Expressive power and succinctness of propositional languages for preference representation. In: Dubois D, Welty CA, Williams M, eds. Proc. of the 9th Int’l Conf. on Principles of Knowledge Representation and Reasoning (KR 2004). AAAI Press, 2004. 203 212.
    [8] de Saint-Cyr FD, Lang J, Schiex T. Penalty logic and its link with Dempster-Shafer theory. In: de Mántaras RL, Poole D, eds. Proc. of the 10th Annual Conf. on Uncertainty in Artificial Intelligence (UAI’94). San Francisco: Morgan Kaufmann Publishers, 1994.204 211.
    [9] Darwiche A, Marquis P. Compiling propositional weighted bases. Artificial Intelligence, 2004,157(1-2):81 113. [doi: 10.1016/ j.artint.2004.04.005]
    [10] Cadoli M, Donini F. A survey on knowledge compilation. AI Communications, 1997,10(3-4):137 150.
    [11] Selman B, Kautz H. Knowledge compilation and theory approximation. Journal of the ACM, 1996,43(2):193 224. [doi: 10.1145/226643.226644]
    [12] Darwiche A, Marquis P. A knowledge compilation map. Journal of Artificial Intelligence Research, 2002,17(1):229 264.
    [13] Cayrol C, Lagasquie-Schiex M, Schiex T. Nonmonotonic reasoning: From complexity to algorithms. Annals of Mathematics and Artificial Intelligence, 1998,22(3-4):207 236. [doi: 10.1023/A:1018939502485]
    [14] Darwiche A. Decomposable negation normal form. Journal of the ACM, 2001,48(4):608 647. [doi: 10.1145/502090.502091]
    [15] Bryant RE. Graph-Based algorithms for Boolean function manipulation. IEEE Trans. on Computers, 1986,C-35:677 691. [doi:10.1109/TC.1986.1676819]
    [16] Coste-Marquis S, Marquis P. On stratified belief base compilation. Annals of Mathematics and Artificial Intelligence, 2004,42(4):399 442. [doi: 10.1023/B:AMAI.0000038313.15152.5c]
    [17] Benferhat S, Kaci S, Berre DL, Williams M. Weakening conflicting information for iterated revision and knowledge integration. Artificial Intelligence, 2004,153(1-2):339 371. [doi: 10.1016/j.artint.2003.08.003]
    [18] Selman B, Levesque HJ, Mitchell DG. A new method for solving hard satisfiability problems. In: Hayes-Roth B, Korf RE, eds. Proc. of the 12th National Conf. on Artificial Intelligence (AAAI’92). AAAI Press/Massachusetts: The MIT Press, 1994. 440 446.
    [19] Lin H, Sun JG. Knowledge compilation using the extension rule. Journal of Automated Reasoning, 2004,32(2):93 102. [doi:10.1023/ B:JARS.0000029959.45572.44]
    [20] Andersen H. An introduction to binary decision diagrams. Technical Report, Department of Information Technology, Technical University of Denmark, 1998. http://www.eng.utah.edu/~cs6100/lectures/lec6/anderson-bdd.pdf
    [21] Darwiche A. New advances in compiling CNF to decomposable negation normal form. In: de Mántaras RL, Saitta L, eds. Proc. of the 16th Eureopean Conf. on Artificial Intelligence, (ECAI 2004). Amsterdam: IOS Press, 2004. 328 332.
    [22] Huang J, Darwiche A. The language of search. Journal of Artificial Intelligence Research, 2007,29:191 219. [doi: 10.1613/ jair.2097]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

赖永,刘大有.一种有效的分层加权库编译方法.软件学报,2012,23(10):2550-2563

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 30,2011
  • Revised:January 17,2012
  • Online: September 30,2012
You are the first2044714Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063