# «A Computer Application to Study Engineering Projects at the Early Stages of Development M. H. Gedig M.A.Sc Structural Engineer AGRA Coast Inc. 1515 ...»

4.1 Numeric Constraint-Satisfaction The QES program is able to accept constraints in a number of forms, both qualitative and quantitative. Systems of numeric constraints are formulated as numeric constraint-satisfaction problems. The bounds consistency techniques developed by Lhomme [7], were implemented in QES to solve numeric constraint-satisfaction problems. The details of this implementation within the QES framework will be discussed here.

Consistency techniques are applied to numeric constraint-satisfaction problems by associating a dynamic domain with each variable and by propagating this domain through the constraints.

The domains of variables are represented by intervals, so that as constraints are propagated from one variable to another, the bounds of the intervals are updated dynamically. This procedure can

**be examined more closely using the following example. Consider the system of constraints:**

C2: Y = 2 × X C1: Y = X + 1 Let the initial domains for the variables X and Y be DX = [-∞, +∞] DY = [-∞, +∞].

In the constraint network representation of QES, the constraints and variables may be described graphically as shown in Figure 17. The constraint network contains six expressions: X, Y, 1, 2, X + 1, and 2 × X. In the figure, solid arcs represent arithmetic links, while broken arcs symbolize ordinal relational links.

In the constraint network, changes propagate along relational and arithmetic links. The variable X has an arithmetic link to the expressions X + 1 and 2 × X recorded in its parents field, while the numeric constants 1 and 2 have links to X + 1 and 2 × X, respectively. The expressions X + 1 and 2 × X both maintain a relation link to the variable Y. Suppose the domain DX is updated to [0, 10].

**The following sequence of events transpires:**

The change in DX propagates from X to X + 1 through a parent link of X.

The constraint interval of X + 1 is updated to [1, 11], using the current values of its children.

The change in X + 1 is propagated through a relation link to Y.

Variable Y is updated to [1, 11].

The change in Y causes 2 × X to be updated to [1, 11], because 2 × X shares a relation link with Y.

X is recalculated using the new value of 2 × X and the right child, the numeric constant 2.

The constraint interval of X is updated to [0.5, 5.5] The change in X propagates to X + 1 by way of the arithmetic link.

The domain changes propagate cyclically through the constraint network, and asymptotic convergence toward the solution (X = 1, Y = 2) occurs.

Figure 17: Constraint network representation for numeric constraint problem.

The input for QES for this constraint-satisfaction problem is displayed in Figure 18. As shown, interval constraints are represented by inequality constraints, so that the assignment X = [0, 10] is entered as two constraints; X ≥ 0 and X ≤ 10. The QES program uses the technique of arc B(w)-consistency [7] to solve numeric constraint-satisfaction problems. The solution progresses according to the sequence discussed above, as shown in Figure 19. The consistency algorithm terminates after about 20 cycles through the network, using specified imprecision w of 1.0×10-6.

**As shown the final values for the intervals of X and Y are:**

X = [0.999998, 1.000001] Y = [1.999998, 2.000001]

**Numeric constraint satisfaction:**

Modify X to [0.5,5.5] Modify (X+1) to [1.5,6.5] Modify Y to [1.5,6.5] Modify 2*X to [1.5,6.5] Modify X to [0.75,3.25] Modify (X+1) to [1.75,4.25] Modify Y to [1.75,4.25] Modify 2*X to [1.75,4.25] Modify X to [0.875,2.125]...

Modify X to [0.999998,1.000001] Modify (X+1) to [1.999998,2.000001] Modify Y to [1.999998,2.000001] Modify 2*X to [1.999998,2.000001] Normal termination Figure 19: Solution sequence for numeric constraint problem.

4.2 Constraint Propagation

**In the QES constraint network, three distinct types of constraint propagation are used:**

4.3 Propagation to parents A change in one of the children of an expression requires the expression to be recalculated.

Propagation in this sense is straightforward, given the convenient representation in QES of

expressions as trees. The details of this type of propagation follow directly from interval arithmetic [10]. In the following discussion, the notation of Moore is used for interval arithmetic; an interval is denoted by a capital letter, say X, where X = [ X, X ]. Given the set of basic constraints available in the QES system, Table 3 summarizes the details of the arithmetic.

Note that Table 3 covers only closed intervals. Open and half-open intervals are handled in a similar way.

4.6 Soundness of Interval Methods By using established techniques for dealing with intervals, numeric consistency techniques are able to provide the important guarantee that the correct result will be bounded by the domains of each variable. This is a guarantee, which other methods such as Monte Carlo simulation and hill-climbing techniques cannot provide.

One of the strengths of numeric constraint satisfaction algorithms is they are able to solve interval equations even when a closed-form formula cannot be obtained. A number of numerical simulation techniques may also be applied to solve these types of equations, including Monte Carlo simulation. In Monte Carlo simulation, complex equations are solved by picking at random a value for each variable, which lies within the range of acceptable values for the particular variable. Each term in the equation is evaluated on these particular values, giving one possible value for each term. By iterating random choices, a range of possible values of the terms is found. In this way complex terms can be evaluated even though the value of the variables are not known with certainty. Another method, which may be used to evaluate such expressions, is to use hill-climbing techniques, which seek the maximum and minimum values of each quantity. Neither Monte Carlo simulation nor hill climbing is a sound inferential technique [1]. They generally return a subset of the true range, and thus arbitrarily exclude legitimate possibilities. Experience with hill-climbers has found them to be slow and unreliable [9].

The assurance that the correct result is bounded by the domains of variables comes from a basic property of interval arithmetic [10]. Let y = f(x) define a function where x is within an interval X, and where F(X) is also an interval which has as a lower bound the minimum value of any

**f(x), and upper bound the maximum value of any f(x). This property is stated as:**

∀ x ∈ X, f(x) ∈ F(X).

This result is significant in the context of the soundness of interval analysis techniques. While any other floating-point calculation provides simply an estimate of the correct result of a computation, interval methods guarantee bounds for the correct result.

5 Constraint Inference A number of additional techniques, both qualitative and quantitative, are used to QES to complement constraint propagation. Most of these techniques fall under the category of constraint inference methods, which have been used in systems such as Quantity Lattice [11].

Constraint inference is a way of deriving new constraints from existing ones. Three types of constraint inference used in QES are relational arithmetic, constant elimination arithmetic, and graph search.

5.1 Relational Arithmetic Interval arithmetic sometimes leads to results, which are weaker than would be expected. One such limitation of interval arithmetic is the selection problem. Given the relation X Y, and the assignments X = (0, 1], Y = [0, 1), we should be able to infer that (X - Y) = (0, 1], since X Y. In general, interval arithmetic does not even allow one to determine that X - X = 0. Using interval arithmetic, if X = [1, 2] then X - X = [-1, 1]. Only by knowing that both intervals refer to the same quantity can we infer that the result is [0, 0]. Another limitation of interval arithmetic is that sometimes it cannot increase our knowledge at all. If we are given two quantities X and Y, and all we know is that X = Y + 5 and Y = [-∞, +∞], interval arithmetic leads to the result X = [, +∞]. Although we know that X Y, interval arithmetic is not able to capture this fact. An arithmetic technique called relational arithmetic may be used to compensate for both these deficiencies. Relational arithmetic maintains constraints on the qualitative relationship of an arithmetic expression to its arguments. The axioms of relational arithmetic are given in Table 6.

5.3 Graph Search In order to invoke the axioms discussed above, information about ordinal relations between expressions is required. In some cases it is possible to infer new ordinal relations from a given set of ordinal relations on expressions using a technique called graph search. Graph search is conveniently implemented in a constraint network. Given the relations A ≤ D and D = E, it is possible to deduce that A ≤ E. The transitivity table (Table 8) enumerates the relationships between two inequalities which share a common expression. Entering the transitivity table at the intersection of the row labeled ≤ and the column labeled =, we find the relation ≤. In a constraint network, a simple breadth-first search [i.e. 5] may be used to find a path between two expressions. In the constraint graph, we wish to find the relationship between the expressions A and C, even though they are not directly connected by a relation link.

The search starts at the expression A and proceeds until the expression C is reached. As each expression is visited, the relationship of that particular expression with the variable A is recorded. In the figure, the notation [n: rel] is used to indicate that the relation rel is written at

Figure 20: Constraint network for graph search example.

In some cases, more than one path may exist between two expressions in a constraint network.

If this occurs, the results of each path may be combined to produce a ‘tighter’ result. In Figure20, two paths lead from expression A to expression C. On the third step of the algorithm, the sign ‘≤’ is written at the node E. Traversing the path A-B-E we find that A ≥ E. Combining the relations ‘≤’ and ‘≥’ we may deduce that A = E. If the graph search is able to determine a constraining relation between two expressions, the relation may be cached by adding a new relation link between the two expressions. A subsequent query to the constraint network can use this information to quickly determine the relationship between two expressions.

Constraint inference furnishes techniques, which complement the constraint-satisfaction methods discussed earlier. Systems, which rely only on constraint influence, have a number of limitations however. One of the problems with constraint inference is that it is difficult to control and it often falls into infinite loops. The constraint propagation techniques discussed in connection with constraint satisfaction algorithms are easier to control than constraint inference.

In addition, as new constraints are inferred, it may be difficult to ensure that they will be useful in answering queries to the network.

6 Conclusions This paper has described a computer software application, QES, which may be used to evaluate conceptual and preliminary engineering designs. The application employs a number of qualitative and semi-quantitative techniques to handle physical systems, which are characterized by a high level of uncertainty. QES exploits the constraint network paradigm to perform both qualitative and quantitative reasoning within an integrated framework. Qualitative reasoning, quantitative interval arithmetic, arithmetic reasoning and graph search are complementary techniques which are used to extract a considerable amount of information from uncertain or

incompletely specified input data. These techniques show considerable advantages over other, more commonly used approaches for handling uncertainty in engineering practice.

An important feature of qualitative and semi-quantitative methods is that they allow the engineer the reason with a high level of abstraction. Qualitative equations are capable of representing a class of physical systems rather than one specific system. In the structural example, the corresponding quantitative equations would represent a very specific system, with one set of member lengths and section properties. On the other hand, the qualitative equations represent a large number of physical structures, with a range of materials, section properties, and member geometry.

Qualitative and semi-quantitative methods are useful for evaluating conceptual and preliminary designs, because by reasoning with an

**Abstract**

model, the engineer may perform a sound preliminary evaluation of a physical system without committing to details. All system parameters can be represented using qualitative variables or interval variables that are capable of covering a wide range of possible system configurations. The overall integrity of the proposed system can be confirmed at an early stage in the design, so that sound conceptual design alternatives are retained while unsound alternatives are eliminated.

A wide range of tools is available which are able to perform detailed numerical analysis. These tools generally require input that is specific and complete. The user must commit to a large number of detailed assumptions about the physical system. At the earliest stages of design, the validity of these detailed assumptions is questionable. A considerable amount of time may be required to generate the assumptions and create the detailed model of the system.