Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


3.3. CONSTRAINTS

Constraints are fundamental to the design problem since they restrict the allowed part combinations to what is allowed by the laws of physics. (Note that we are expressing a somewhat controversial view here that constraints are physically-based and "hard," while traditionally "soft" constraints such as cost are preferences that are subsumed into and expressed in value functions.) Constraints define a network that describe relationships among all the parts in the design and they can be used for two purposes: evaluation and propagation. In evaluation, constraints determine whether or not the current assignment of values to design attributes is physically allowed, or feasible. In propagation, constraints infer the values of unassigned design attributes, given the values of assigned design attributes, potentially restricting future assignments. Constraint propagation is very useful in design because it can detect the infeasibility of an assignment before all design attributes are assigned values. This reduces thrashing, or pursuing an assignment that will eventually be found to be infeasible (Mackworth, 1977).

In Figure 4 we display an illustrative constraint between the horsepower of the selected motor (motor.hp) and the minimum horsepower required by the selected machine unit (machine-unit.min_hp).

We show the constraint network for our example in Figure 5. The constraints represent feasibility constraints between the motor horsepower and machine-unit allowed horsepower, and a feasibility constraint specifying the maximum total weight. A solution to the problem is a selection of a motor and machine-unit satisfying the constraints that the horsepower value of the selected motor lies between the minimum and maximum allowed horsepower values of the selected machine-unit, and that the total weight be no more than 2760 lb. These constraints are represented by the expressions:

  • machine-unit.min_hp [lte] motor.hp
  • motor.hp [lte] machine-unit.max_hp
  • machine-unit.weight + motor.weight [lte] 2760

One difficulty that arises in configuration-design problems is that the set of constraints necessary to evaluate the evolving design changes as parts are selected to implement functions. Some knowledge-based design systems address this problem by allowing human designers to add or retract constraints as the design progresses. Our definition of constraints includes a precise specification of when the constraint is to be evaluated in the form of a predicate precondition.


FIGURE 4 Example of constraint.

Constraints are used in a variety of ways to propagate the effects of an assignment to a design attribute in order to evaluate specific design decisions. In configuration design, parts are selected to implement functions; the constraints are then used to propagate the effects of how that decision affects other design attributes. If constraint violations result, a previous part selection is retracted and another selection is made. Such a backtracking process can be minimized by providing a definition of propagation functions and then using the constraints themselves to guide the selection of parts to implement functions.

Formally, a constraint is a relation defined over a subset of the attributes that restrict the attribute domains. The set of attributes over which the constraint is defined is the set of the constraint's arguments. There are two functions associated with a constraint. A constraint-evaluation function maps from an attribute assignment to the Boolean values T or F. If the assignment maps to T, then the assignment satisfies the constraint (the assignment is feasible); if the assignment maps to F, then the assignment violates the constraint (the assignment is infeasible). The constraint-propagation function maps from an assignment of domain values for all but one of the constraint's arguments to the domain of the remaining argument. This function restricts the domain of the remaining argument, given the assignment of domain values to all other attributes.


FIGURE 5 Example of a constraint network.

In many configuration-design problems, constraints are defined over attributes that are not catalog attributes. For example, a designer is often interested in the total weight of a design, that is, the sum of the weights of individual parts. We represent these attributes as state variables that are defined as functions over some set of catalog attributes and other state variables. The state-variable function determines the value of the state variable for given values of a set of attributes.

A precondition is a relation defined over a subset of the attributes that define the conditions under which a constraint is active. The set of attributes over which the precondition is defined forms the precondition's arguments. The precondition-evaluation function maps from an attribute assignment to the Boolean values T or F. If the assignment maps to T, then the assignment satisfies the precondition and the constraint is active; if the assignment maps to F, then the assignment violates the precondition and the constraint is inactive.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.