Research Accomplishments

Workgroup for Intelligent Systems in Design and Manufacturing

Technical Basis

During the past decade we have been exploring the development and application of constraint networks to design and manufacturing problems with great success. This work was driven by a "pull" research approach in which we moved through an annual development cycle that included: concept and underlying mathematics development, modeling environment design and implementation, application problem solving systems built in the modeling environment, and an assessment of what could and could not be done, and what needed to be done. The applications were built by university researchers and by engineers in industry. The assessment of what was needed to solve problems provided by the application builders allowed us to refocus our research activities and priorities to ensure that our results could successfully attack actual engineering problems. Additionally, our target engineering community requested that the system perform well on high-end PCs. Although many groups world-wide have examined the use of constraints in similar contexts, we have had significantly greater success because we based our approach upon a formal mathematical basis and a theorem-prover. The formal mathematical basis is an order-sorted logic (the Concurrent Engineering Logic (CEL). The truth state of a constraint is determined using an arithmetic-based theorem-prover. This approach provides the following advantages.

• We have shown that the approach is mathematically consistent.
• The formal definition of the logic defined the parsing structure needed for syntax checking in the modeling environment.
• The deductive logic system defined how to implement the inferencing mechanism that determines values for unbound variables and allows us to begin problem solving from anywhere in the constraint network. This is called omni-directional propagation and eliminates the chronological solution procedures of other approaches.
• The formal logic includes universal and existential quantification and this has been implemented within the modeling environments.
• The formal basis allows us to show that the software operates correctly.
• The order-sorted logic basis was extended to include a four-valued logic that allows us to utilize a special form of forward and backward checking to reduce the search space as we move toward solutions. This is accomplished by dynamically adding, deleting and relaxing constraints.
• Using a proof-theoretic view of our formal logic system allowed us to seamlessly integrate a commercial relational database system with it and utilize the database's query engine as an extension to our theorem-prover.
• We have proven that the relationships among variables within database tables and among different database tables can be viewed as formal constraints. This allows us to map constraints into database relations and store them in database tables. It allows us to dynamically map a constraint and its bound state into an SQL query on the constraints stored as relations in the database.
• We developed a formal hierarchical decomposition approach that allows us to break up the solution of the design of a printed wiring board into sub-problems that were solved by building independent constraint networks which were combined together to produce a combined solution without rewriting the sub-networks. The integration of the subnetworks into a larger system required only a few hours.
• The database connection allows us to utilize existing product and inventory data in the system design.
• We implemented a genetic algorithm system on top of the constraint system that allows us to produce optimal solutions to these problems.

Taken together, these items allow us to build modeling environments, applications, optimize the solutions, and execute the applications on PCs.

Some Applications

As an example, under contract with IBM, we solved their product configuration problem for their PS/2 PC line which allowed a dial-in customer to design their own PC. The system checked to ensure that the system could be manufactured and determined its price. The solution space was large -- 500 billion possible correct solutions. Modeling the bulk of the problem in the database had the effect of reducing the problem size by 1,300 constraints. This reduction allowed us to run multiple scenarios on a 25MHz 486 notebook PC under OS/2. The forward and backward checking provided solution convergence after only a dozen inputs from the user. The logic basis and database connection allows easy updating of the information by naive users since knowledge of the underlying syntax is not necessary. This system was demonstrated to the President of the IBM PC company. The underlying technical approach is being used by IBM to build electronic sales products.

The formal logic foundation provides a robust modeling environment for a wide variety of problems. Some of the problems solved using this technology include:

• Dynamic QFD system.
• AS/RS system designer with optimization.
• Transmission gear designer with optimization.
• Process planning system for printed circuit boards that checked process plans against existing production facilities.
• A system for designing rotational parts and performing process selection.
• A fastener selection system for designing field maintainable army vehicles.
• Design for testability system for printed circuit boards.
• Turbine blade design example using hierarchical decomposition of constraint networks.
• Project planning system for the U.S. Internal Revenue Service.

Fuzzy Constraint Networks

During the past year we have been exploring the concept of merging fuzzy mathematics with constraint networks. An initial mathematical theory has been developed and an initial fuzzy constraint network system implemented. Using the order-sorted logic basis for our crisp constraint networks allowed us to implement the fuzzy constraint networks by defining additional sorts. System growth based upon a formal foundation provides a flexibility in extending the system. Thus, the fuzzy constraint network is an extension of our prior work. It demonstrates the power of having a formal basis that is extensible. This system has been used to show the following:

• Fuzzy mathematics is applicable to design and can be used to model requirement specifications using linguistic variables.
• Since we now have a gradient from violated to satisfied for our constraints, we can manipulate a constraint satisfaction threshold to produce a compromise solution that balances conflicting constraints.
• The design problem was decomposed into a fuzzy constraint hierarchy using the techniques developed for crisp constraint networks.
• The hierarchical decomposition and the omni-directional propagation provided a mechanism to develop a technique to produce a reduction in imprecision as the design moved from the conceptual phase to the detailed design phase. This precision convergence approach has shown that it is possible to solve the inherent problem of using fuzzy mathematics in design. That problem results from the fact that any operations on fuzzy variables or numbers produces an increase in imprecision. It is now clear that it is possible to utilize this fact to actually produce a decrease in imprecision as a design progresses.
• The imprecision reduction as a design moves from stage to stage is quantifiable. We have shown that in a three stage design hierarchy, we can achieve an imprecision reduction of over 100% and move from highly imprecise requirement specifications to the precise descriptions needed to manufacture the product.
• The precision convergence approach allows us to quantify when the imprecision in a design has been sufficiently reduced to the point that it matches the imprecision inherent in the production process. This gives us a stopping metric for the design iteration cycle, and also a means to map inherent production process variation to its impact on the design. Since we have determined how to relate the design imprecision to the inherent production process variation, the omni-directional propagation that is characteristic of our constraint processing technology allows us to assess the impact that the imprecision inherent in the production process has on a given design. This should allow a designer to identify aspects of a design that are particularly sensitive to variations in imprecision so that a more robust design can be developed.
• The optimization techniques developed for crisp constraints utilizes genetic algorithms and is independent of the inherent set properties of the underlying variables and operators. Thus, this technique should be directly applicable to fuzzy constraints with only a few modifications.
• This initial work identified significant shortcomings of existing approximations for fuzzy operators and resulted in ongoing work to develop new approximations that are more accurate, have quantifiable accuracy, and are linear in compute time requirements. This work has been successful for the product operator and its linear compute time is in sharp contrast to the exponential compute time requirements of the actual product operator. This work indicates that it is possible to use fuzzy technology for large, complex problems.