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.5. SPECIFYING A DESIGN PROBLEM

What do we mean by a problem? Or, more formally, how do we specify a design problem?

A design problem specifies the: functions that must be exhibited, constraints that must be satisfied, set of catalogs of available parts, and a set of the designer's preferences represented as a linear, weighted value function. Formally, the design problem is a tuple <required-functions, constraints, catalogs, v()> that describes the desired design in terms of a set of specifications:

  • required-functions is the set of functions desired by the designer
  • constraints is the set of feasibility constraints, with preconditions (and a subset of the constraints define support-function relationships)
  • catalogs is a set of part catalogs
  • v() is a linear, weighted value function that: assigns a real number to a design or part, defines a partial order on the designs or parts, and represents the desirability of the part or design from the designer's perspective

Support-function constraints represent support-function relationships. By definition, support functions are functions that are not included in the list of required functions specified by the designer. These constraints have a precondition that defines when the support functions are required. The support functions, which are not in the list of required functions defined in the problem definition, are contained in the constraint expression.

A solution to the design problem is a set of parts S with the following properties:

  • For each required or support function, there exists a part in S such that the part implements the required or support function
  • The set of parts S is decomposable
  • For each required or support function and each part in S, there is no other decomposable part that has a higher value, i.e., the set of parts S is optimal.

4. TECHNIQUES II: CURRENT METHODS

We now outline two approaches to solving configuration-design problems. One is based on constraint-satisfaction problems, and as such it represents a centralized, nondistributive approach. The second method is a distributed approach in which independent agents solve parts of the design problem, typically in an opportunistic fashion, with guidance provided through a variety of architectures.

4.1. CSP-BASED METHODS

A constraint-satisfaction problem (CSP) is formally defined as a set of variables V with domains D and a set of constraints C defined over the variables that restrict the assignment of values to variables. A solution to a CSP is an assignment of values to variables such that all constraints are satisfied. CSP variables and constraints can have preconditions that define when a variable needs to be assigned or when a constraint needs to be evaluated. We now apply CSPs to configuration-design problems.

The configuration-design problem defined above maps naturally to a CSP. This mapping thus provides a strong theoretical framework for analyzing configuration-design problems and applying results from research in CSPs to solve configuration-design problems, including techniques for achieving consistency and decomposability of a constraint network. To apply the CSP model to configuration-design problems, required- and support-functions map to CSP variables, and feasibility constraints map to CSP constraints. We show an example design network in Figure 6, where V = {f1,1, f1,2, f2,2, f3,1, f3,2, f4,1} and C = {c1, c2, c3, c4}. The variable domains are parts from possibly distributed part catalogs that implement the functions corresponding to the variables. For example, the domain of variable f1,1 is taken from catalog1 and catalog3.


FIGURE 6 Example design network.

The existence of preconditions on the constraint and variables allows the inclusion of support-function relationships and dynamic constraints that are found in configuration-design problems. Given this mapping, a solution to the CSP corresponds to a selection of parts that implements all the required- and support-functions and meets all the constraints.


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.