# «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 ...»

Inequalities are an important means of capturing fundamental qualitative distinctions, without sacrificing the expressive capabilities of algebraic expressions. Relation links represent the ordinal relation between two expressions. The relationLink data structure, shown in Figure 6, contains three fields: one for each expression and another for the ordinal relation.

relation data members name type =,,, ≤, ≥, ≠, ?

value

Figure 7: Graphical representation of an equation.

As an example of relation links, consider the equation A + (B × C) = 0. This equation is depicted in Figure 7, where the relation link is shown as the dotted arc between the number zero and the expression node labeled ‘+’.

3 Qualitative Analysis In QES, the domains of qualitative variables consist of a finite set of intervals. The most common set represents the domain of signs {[-∞, 0), [0, 0], (0, +∞]}, which may be abbreviated by {-, 0, +}. The domain of signs will be used to look at how QES solves constraint equations which are expressed as qualitative variables. The tree structure of expressions is exploited in the solution procedure, which uses constraint-satisfaction methods.

Each of the nodes of the constraint network may be considered a constraint. This representation of a constraint network is different to that given by Mackworth [8]. In Mackworth’s network, the variables in the constraint-satisfaction problem are the nodes. Loops represent unary constraints on a variable and directed arcs indicate binary constraints. In solving constraints consisting of equations, this representation is unsuitable, because equations can consist of more

**than two variables. The simple example given earlier, A + (B × C) = 0, involves three variables:**

A, B, and C. For this reason, the alternate representation of Freuder [3] is used. In this system, nodes represent constraints, while arcs are used to link constraints having common variables.

QES uses a constraint synthesis process to build up successively higher levels of consistency in the constraint network.

The structure of the expression tree provides a convenient framework in which to construct and solve constraints. Constraints are built up from variables in an incremental fashion, following

If we add the additional constraint F2 0, the values - and 0 can be removed from the domain of F2. The expression F1 + F2 will be constructed first. Addition is a constraint, which is satisfied if the values assigned to the arguments are consistent with the result shown in the qualitative addition table, Table 1. Note that in Table 1, the character ‘?’ represents a complete lack of information about the result. Multiplication, subtraction, division, negation and reciprocal functions can all be defined as constraints, similar to addition. To find the variable assignments, which satisfy the addition constraint, the Cartesian product of the domains of the child expressions is generated, and the corresponding value of the sum is determined according to Table 1.

Figure 10: Constraint network with expression links added.

In Figure 10, all possible combinations of the domains of F1 and F2 are shown in the table under the node for expression F1 + F2. The sum of the two values is shown in the left column of the table. A similar table is generated for the expression F1 - F3. The left-hand column of each table contains the elements of the domain set for the constraint expression, while the right-hand column holds the values of the arguments of the expression.

The next step in solving the system of constraints is to enforce the equality constraint, which will constrict the domains of the two expressions F1 + F2 and F1 - F3. As discussed earlier, relation links represent ordinal relations between expressions. Two relational links are added to the constraint network, as shown in Figure 11, linking the two expressions to the constant expression zero. The constraint interval of a constant expression is always equal to the domain, which is [0, 0] in this case. The interval [0, 0] is intersected with the constraint interval of the expressions F1 + F2 and F1 - F3. Since the constraint interval of each is initially [-∞, +∞], their new values are [0, 0]. To enforce the constraint at the two expressions, the constraint interval is further intersected with each element of their domains. When intersection results in the empty set, the domain element is deleted.

The updated domains are shown in Figure 11, which shows that F1 + F2 has one legal instantiation while F1 - F3 has three. At this point, node consistency has been achieved at the two expression nodes F1 + F2 and F1 - F3. Note that a relational link also exists between the variable F2 and the constant zero. For clarity, this link is not shown in Figure 11.

Figure 11: Constraint network after node consistency procedure.

The two expressions F1 + F2 and F1 + F3 now contain partial solutions to the problem. These partial instantiations must be combined to find the complete solution. The simple approach is to find all combinations of the domains of the two expressions, which correspond to consistent assignments of variables. A more efficient method is employed by QES, which uses the concept of arc consistency. In QES arc consistency is enforced on pairs of equations. The simple arc consistency AC-1 [8], is used here. QES maintains a list of all equations in the system using the equationSystem data structure (Figure 8). Each time an equation is created, it is made consistent with each of the existing equations. If elements in the domain of an expression are deleted when arc consistency enforced between two expressions, the procedure is repeated until no further deletions are necessary. In the example problem, the expression F1 + F2 is first added to the equationSystem structure. Since it is the first equation to be added, no deletions are performed.

The second expression is then added, and the two equations are made arc consistent. The uppermost box in Figure 12 represents the equationSystem structure with its links to each of the equations.

Looking at expression F1 - F3, one of the instantiations involves the assignment F1 = 0 and another involves F1 = +. The domains corresponding to these two assignments are deleted, because the only valid assignment for F1 in the expression F1 + F2 is F1 = -. Because deletions have occurred, the two expressions are checked for consistency again. Since no further deletions are possible, the arc consistency procedure is halted. The complete solution to the problem is found by simply merging together the domains of the two binary expressions. This results in the

**single legal instantiation:**

F1 = F2 = + F3 = -.

Although this problem has one solution, this is not generally the case when systems of qualitative constraints are concerned. If the additional constraint on F2 (F2 0) had not been added, there would be three legal instantiations instead of one.

3.1 Example from Structural Analysis An example of qualitative analysis from the field of structural mechanics is given in this section.

This example illustrates some of the practical implications of qualitative analysis, as well as some refinements that may be made.

Figure 13: Pin-jointed structure.

The pin-jointed plane structure model shown in Figure 13 will be studied using qualitative analysis techniques. In the figure, the boxed numbers are the element labels and the other

numbers are the node labels. The parameters of this model are the lengths (L1, L2, L3, L4) and axial stiffnesses (EA1, EA2, EA3, EA4 ) of each of the four members, as well as the nodal displacements at the upper left node (∆X2, ∆Y2), and the upper right node (∆X3, ∆Y3). The horizontal displacements ∆X2 and ∆X3 are considered positive if to the right, and the vertical displacements ∆Y2 and ∆Y3 are positive if upward. A horizontal force, which acts to the right, is applied at the upper left node. One of the uses for such a model would be to estimate the deflected shape of the structure. This is the objective of the qualitative analysis.

The qualitative equations, which relate the nodal displacements to the material properties and

**geometry of the structure, are given as follows:**

These qualitative equations are very similar to the usual quantitative equations. The difference is that positive numeric constants have been omitted. Positive constants may be eliminated from products, because the positive sign value acts as the identity for multiplication in the domain of signs.

The input for QES, which is used to solve this problem, is shown in Figure 14. The QES program accepts input in a format that is quite similar in form to the problem specification that has been given here. The variables in the problem are defined as dx2, dx3, dy2, and dy2, which have their obvious counterparts in the notation used here. The output produced by QES is shown in Figure 15. The analysis produces four solutions to the problem, the first of which is

**the correct solution:**

∆X2 = + ∆Y2 = 0 ∆X3 = + ∆Y3 = -.

** Figure 14. QES input for pin-jointed structure.**

The result of this analysis is a typical result in qualitative analysis: multiple solutions are generated but the ‘correct’ solution to the problem is always contained in the set of solutions.

The other solutions are not, strictly speaking, incorrect, because they are correct solutions to the qualitative model. A qualitative model is usually a generalization of an associated quantitative model. The process of generalizing a quantitative model allows solutions, which do not satisfy the quantitative equations. One of the prime sources of weakness in qualitative predictions derives from the weakness of the qualitative addition function. Looking at Equation 3, the assignment ∆X2 = -, ∆X3 = - causes the term (∆X2 - ∆X3) to evaluate to ?. Since the sign ?

represents the interval [-∞, +∞], this combination of assignments satisfies Equation 3, even though such values would not satisfy the corresponding qualitative equation. As mentioned previously, the qualitative addition function introduces uncertainty, which tends to propagate through systems of qualitative equations.

One way of strengthening the conclusions drawn by qualitative analysis is to make some use of ordinal relations between qualitative variables [2]. Ordinal relations may be used to reduce the uncertainty caused by the qualitative addition operator. Whenever qualitative addition results in the sign ?, three new cases may be generated to reflect different possible ordinal relations between the arguments involved in the addition operation (Table 2).

|∆X2| |∆X3| In the previous problem, qualitative analysis lead to a fairly clean, informative solution, considering the minimal amount of specific information that was furnished as input. It is important to note that, in general, a qualitative analysis produces more than one solution.

Increasing the number of variables in a problem leads to a rapid increase in the number of combinations, which must be considered, and also, an increase in the number of solutions. The following problem illustrates this concept.

Figure 16: Structural frame model.

An analysis of the system of Equations 7 through 12 using QES resulted in a total of 189 different solutions. This result shows that increasing the number of qualitative variables in the problem leads to considerably weaker qualitative predictions. In this case, the added complexity

of the equations certainly has a detrimental impact on the analysis. In particular, the equations in this example include more complex sums than in the previous example. Even when ordinal relations are considered in the analysis, the number of solutions increases to 266, in contrast with the previous problem where the number decreased. The use of ordinal relations increases the number of combinations, which must be considered, but the additional information simply does not cause enough of the assertions to be refuted. Although the 189 solutions resulting from simple qualitative analysis is less than the total number of possible combinations of six variables, each having three values (36 = 729), we gain little practical insight into the problem.

Even though more sophisticated improvements than the use of ordinal relations may be applied to qualitative analysis, it is worthwhile to consider the application of pure qualitative analysis to engineering practice.

In the previous two examples from structural analysis, very little information was specified about the various quantities in the problems. In most problems in engineering, partial knowledge about quantities takes the form of partial numerical values. This observation suggests that, for an engineering application at least, it is more beneficial to pursue a formulation involving partial numeric information, rather than to seek refinements to the pure qualitative representation. This was the direction taken with the QES program. The implications of reasoning with partial numeric information are discussed in the next section.

4 Semi-Quantitative Analysis In QES, partial quantitative information is incorporated using the interval representation.

Integers are a simple, compact and flexible means of representing uncertainty or partially specified numeric information. Since intervals may also be used to represent qualitative information, it is possible to develop a unified framework for representing and reasoning with qualitative and semi-quantitative knowledge. This was the approach used in the QES program, which is meant to support engineering decision-making at different stages of a project: from the initial stages, where qualitative information is more prevalent, to the later stages, which are characterized by primarily quantitative information.