• Sorted by Date • Classified by Publication Type • Sorted by First Author Last Name • Classified by Author Last Name •
L. Chang and Alan K. Mackworth. Knowledge Reuse for Open Constraint-Based Inference. In Proceedings of the Workshop on Knowledge Capture and Constraint Programming, KCCP-07, Whistler, BC, January 2008.
Open constraint programming, including open constraint satisfaction (Open COP) and open constraint optimization (Open COP), is an extended constraint programming framework designed to model and solve practical problems with openworld settings. We extend open constraint programming to the Open Constraint-Based Inference (Open CBI) framework based on the unified semiring-based CBI framework. The Open CBI framework subsumes both Open CSP and Open COP and also provides extensibility to cover more application domains. Furthermore, the Open CBI framework relaxes the assumption of domain value being incrementally discovered and revealed in non-decreasing order of cost, as required in open constraint programming. We have shown that junction tree representations and junction tree algorithms can be applied to handle Open CBI problems. We show in this paper that the junction tree representation is a suitable graphical model to reuse the intermediate computational results to subproblems. We also proposed consistency maintenance algorithms for junction tree to Open CBI problems with domain value addition and removal. We analyze and show that both answering the satisfiability or the optimal weight of the problem and finding total assignment of variables can be achieved in time that is linear in the size of the junction tree, which is fractionally smaller than the time needed to enforce the junction tree consistency from scratch. We also discuss directions of future research in applying graphical models to problems with open-world settings.
@InProceedings{ChangMackworthKCCP07,
author = {L. Chang and Alan K. Mackworth},
title = {Knowledge Reuse for Open Constraint-Based Inference},
year = {2008},
month = {January},
booktitle = {Proceedings of the Workshop on Knowledge Capture and Constraint Programming, KCCP-07},
address = {Whistler, BC},
abstract = {Open constraint programming, including open constraint satisfaction
(Open COP) and open constraint optimization (Open
COP), is an extended constraint programming framework
designed to model and solve practical problems with openworld
settings. We extend open constraint programming to
the Open Constraint-Based Inference (Open CBI) framework
based on the unified semiring-based CBI framework. The
Open CBI framework subsumes both Open CSP and Open
COP and also provides extensibility to cover more application
domains. Furthermore, the Open CBI framework relaxes
the assumption of domain value being incrementally
discovered and revealed in non-decreasing order of cost, as
required in open constraint programming. We have shown
that junction tree representations and junction tree algorithms
can be applied to handle Open CBI problems. We show in
this paper that the junction tree representation is a suitable
graphical model to reuse the intermediate computational results
to subproblems. We also proposed consistency maintenance
algorithms for junction tree to Open CBI problems
with domain value addition and removal. We analyze and
show that both answering the satisfiability or the optimal
weight of the problem and finding total assignment of variables
can be achieved in time that is linear in the size of
the junction tree, which is fractionally smaller than the time
needed to enforce the junction tree consistency from scratch.
We also discuss directions of future research in applying
graphical models to problems with open-world settings.},
bib2html_pubtype ={Refereed Conference Proceeding},
bib2html_rescat ={},
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Apr 23, 2014 19:08:35