FREE ELECTRONIC LIBRARY - Abstract, dissertation, book

Pages:     | 1 | 2 || 4 |

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

-- [ Page 3 ] --

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


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.

Pages:     | 1 | 2 || 4 |

Similar works:

«Account of NOLEN RACING, Benalla, Vic (As Agent). Lot 51 (Plus GST) BAY OR BROWN COLT Stable C 6 Foaled 6th October 2008 Branded : nr sh; 70 over 8 off sh Sire Redoute's Choice Danehill NADEEM Shantha's Choice 2003 Candide Sound Reason Country Flower Dam Langfuhr Danzig SACRED HILL (NZ) Sweet Briar Too 1999 Tanaquil Marscay Sister Grace NADEEM (AUS) (Bay 2003-Stud 2007). Joint top colt on The 2005-06 Australasian 2YO Classification. 2 wins at 2, A$747,500, MRC Blue Diamond S., Gr.1, VRC...»

«THE IMPACT OF THE THREAT OF VIOLENCE ON SELECTED SCHOOL DISTRICTS IN TEXAS A Record of Study by MARTHA ANN NEELEY Submitted to the Office of Graduate Studies of Texas A&M University in partial fulfillment of the requirements for the degree of DOCTOR OF EDUCATION August 2003 Major Subject: Educational Administration THE IMPACT OF THE THREAT OF VIOLENCE ON SELECTED SCHOOL DISTRICTS IN TEXAS A Record of Study by MARTHA ANN NEELEY Submitted to Texas A&M University in partial fulfillment of the...»

«Gebrauchsanleitung Titrations-Probenwechsler TW alpha plus Operating Instructions Titration Sample Changer TW alpha plus Mode d'emploi Changeur d’échantillons TW alpha plus SCHOTT Gebrauchsanleitung Wichtige Hinweise: Die Gebrauchsanleitung vor der ersten Inbetriebnahme des TitrationsProbenwechslers TW alpha plus bitte sorgfältig lesen und beachten. Aus Sicherheitsgründen darf der Titrations-Probenwechsler TW alpha plus ausschließlich nur für die in dieser Gebrauchsanleitung...»

«Urbanization and the Development of Gender in the Arabic Dialects MUHAMMAD AL-SHARKAWI (Wayne State University, Detroit) Abstract This article makes the claim that the difference between Bedouin and urban dialects of Arabic in gender representation in the plural is a function of the urbanization process the urban dialects of Arabic went through in the 7th century in the conquered territories. Contact-induced linguistic processes of koineization and structural simplification in the newly...»

«Change Your Brain, Change Your Life The Breakthrough Program for Conquering Anxiety, Depression, Obsessiveness, Anger, and Impulsiveness Daniel G Amen Three Rivers Press New York Looking Into Worry and Obsessiveness: The Cingulate System Functions of the Cingulate System ability to shift attention cognitive flexibility adaptability movement from idea to idea ability to see options ability to go with the flow ability to cooperate. Traversing longitudinally through the central deep aspects of the...»

«Does the LIBOR reflect banks’ borrowing costs? July 21, 2010 Abstract The London Interbank Offered Rate (Libor) is a vital benchmark interest rate to which many trillions of dollars of financial contracts are tied. Recently observers have expressed concerns that the Libor may not accurately reflect average bank borrowing costs, its ostensible target. We argue that if banks have incentives to alter the rate, as opposed to simply reporting costs, they will bunch their quotes around...»

«Max-Planck-Institut für demografische Forschung Max Planck Institute for Demographic Research Konrad-Zuse-Strasse 1 · D-18057 Rostock · GERMANY Tel +49 (0) 3 81 20 81 0; Fax +49 (0) 3 81 20 81 202; http://www.demogr.mpg.de MPIDR WORKING PAPER WP 2007-013 MARCH 2007 Gibt es eine zunehmende bildungsspezifische Polarisierung der Erwerbsmuster von Frauen? Analysen auf Basis der Mikrozensen 1976-2004 Michaela Kreyenfeld (kreyenfeld@demogr.mpg.de) Dirk Konietzka (konietzka@demogr.mpg.de) Esther...»

«Marriage Preparation 2. Skills Training for those planning their own course Introduction During over thirty years of church ministry, I prepared numbers of men and women for marriage. I am still in touch with a few of them and rejoice to hear news of their happiness. But like most vicars, I occasionally received a letter from a firm of solicitors which began, We are acting for. who was married in your church. Please would you kindly send us a certified copy of the entry in the Marriage...»

«Naveen Goela, 2014 CONTACT DETAILS 1. Emails: ngoela@alum.mit.edu, 2. Website: http://eecs.berkeley.edu/~ngoela/ 3. Telephone: 617-447-3184 4. U.S. Citizen ENGINEERING, RESEARCH, SYSTEMS DEVELOPMENT 1. Theory: Network/Graph Signal Processing, Statistics/Coding Theory, Network Science, Machine Learning, Computer Vision. Please see list of publications.2. Practice: Medium to Large-Scale Deployed Software Systems, Distributed Software Systems. Please see my projects and systems built under Work...»

«eNEWS October 2013 In This Issue Dear Certified WBEs and Friends, Decades of Excellence Due to the government shutdown, the past few weeks have been very challenging for some of our Newly Recertified Companies certified companies. Those with government contracts have discovered invoice payments Special Thanks and Link to Event withheld as our government shut down. I appreciate Video their contacting me to share this issue with NWBOC which initiated a press release sent last week and Project...»

«“Fellowships of Joy”: Angelic Union in Paradise Lost Stephen Guy-Bray Since its first publication, many readers of Paradise Lost have been struck by the fact that Milton’s Adam and Eve have sex before the Fall – or, to use Milton’s terminology, that they perform ‘the Rites / Mysterious of connubial Love’ (IV.742-3). 1 In conjunction with his emphasis on the tender closeness of Adam and Eve, Milton’s appreciative depiction of prelapsarian human sexuality would seem to establish a...»

«Version 4.0 Base Handbook Copyright This document is Copyright © 2013 by its contributors as listed below. You may distribute it and/or modify it under the terms of either the GNU General Public License (http://www.gnu.org/licenses/gpl.html), version 3 or later, or the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/), version 3.0 or later. All trademarks within this guide belong to their legitimate owners. Contributors Jochen Schiffers Robert Großkopf Jost...»

<<  HOME   |    CONTACTS
2016 www.abstract.xlibx.info - Free e-library - Abstract, dissertation, book

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.