Constraint Propagation with N-ary Semiquantitative Relations.

Abstract

An approach for semiquantitative constraint propagation using both simple and complex nodes is presented. Each node has a label consisting of the union of a negative interval and a positive interval. Compared to simple interval labels, this representation provides significant increase in expressiveness, with only a moderate increase in complexity. In addition to simple nodes (variables), there are complex nodes, representing dimensionless products of variables. Previous efforts have focused on reasoning only with independent complex nodes; other nodes can be expressed as suitable algebraic expressions of independent nodes. The approach followed here involves the use of all irreducible complex nodes; these nodes are the simplest possible, in that they cannot be broken into smaller complex nodes. Since irreducible nodes are not necessarily independent, they are related by implicit constraints. The number of nodes and the number of implicit constraints are polynomial in the size of the problem. The coexisting layers of simple and complex nodes can be manipulated to limit the propagation: Labels on complex nodes are only propagated if they contain information that is not already provided by the simple nodes. This effectively reveals those complex nodes that bear interesting labels. These representation and reasoning choices are suited to engineering domains in which many dimensional kinds of variables are present and dimensionless ratios of variables are significant in defining the state of a system.