A KNOWLEDGE REPRESENTATION FOR CONSTRAINT SATISFACTION PROBLEMS
|Authors:||Croker, Albert E.|
|Publisher:||Stern School of Business, New York University|
|Abstract:||In this paper we present a general representation for constraint satisfaction problems (CSP) and a - framework for reasoning about their solution that unlike most constraint-based relaxation algorithms. stresses the need for a "natural" encoding of constraint knowledge and can facilitate making inferences for propagation, backtracking, and explanation. The representation consists of two components: a generate-and-test problem solver which contains information about the problem variables, and a constraint-driven reasoner that manages a set of constraints, specified as arbitrarily complex Boolean expressions and represented in the form of a constraint network. This constraint network: incorporates control information (reflected in the syntax of the constraints) that is used for constraint propagation: contains dependency information that can be used for explanation and for dependency-directed backtracking; and is incremental in the sense that if the problem specification is modified, a new solution can be derived by modifying the existing solution.|
|Appears in Collections:||IOMS: Information Systems Working Papers|
Items in FDA are protected by copyright, with all rights reserved, unless otherwise indicated.