u t L} -
WWI”? wwxwfiamwafi tum".
. ., .x

U. 71:.» . . , .. v
‘ , .3...
$10..
$3.
nip.
9. cm g)..€ $25
16.1? ,3.
Sh in.

m.......;. um." .
hmwhfiahu

.7 HR
kg,

:r 1.3
.7
.1.“ 2. f; 3.

. dmnfi
‘ _. 1%.?

5!: .I:

. :21» ,

gme «I . .

‘ It"... 2.;
. . v .. A
!,.i.x¢ax4.s.vlna.. «.5
,. Wuvhfiwbnww‘auu
. .3 w. .,.m..m.wu.tu
’t‘ \ .xflhul.
$.(suu 1 . if, it's...“

. . ;

 

ha.
5 ,

 

. ... ._ .~ ‘ ‘ . . .1 . ‘ .‘tv. .3: a.
hfliéywhr . ‘ . . mutinwfinrfiflu
“rut-.3»). ‘ . . V‘ . , 1. . .. ‘ ‘ .

 

THE‘jrj

2’ fl

This is to certify that the

dissertation entitled

A Framework For Knowledge Acquisition, Representation
And Problem-Solving In Knowledge-Based Planning

presented by

Iliana Martinez-Bermudez

has been accepted towards fulfillment
of the requirements for

Wdegree in Computer Science and
Engineering

6%;

Major professor

Date Méél 7 02le ;
U /

 

MSU is an Affirmative Action/Equal Opportunity Institution 0-12771

 

 

 

LIBRARY

Michigan State
University

 

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

APR ,0 ‘5 3003

 

Wit-46 2? 2303

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 cJCIRCJDateDuepes-pts

 

A FRAMEWORK FOR KNOWLEDGE ACQUISITION, REPRESENTATION AND
PROBLEM-SOLVING IN KNOWLEDGE-BASED PLANNING

By

lliana Martinez-Bermudez

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Computer Science and Engineering

2001

ABSTRACT

A FRAMEWORK FOR KNOWLEDGE ACQUISITION, REPRESENTATION AND
PROBLEM-SOLVING IN KNOWLEDGE-BASED PLANNING

By

lliana Martinez-Bermudez

This research addresses the problem of developing planning knowledge-
based applications. In particular, it is concerned with the problems of knowledge
acquisition and representation - the issues that remain an impediment to the
development of large-scale, knowledge-based planning applications. This work
aims to develop a model of planning problem solving that facilitates expert
knowledge elicitation and also supports effective problem solving. Achieving this
goal requires determining the types of knowledge used by planning experts, the
structure of this knowledge, and the problem-solving process that results in the
plan. While answering these questions it became clear that the knowledge
structure, as well as the process of problem solving, largely depends on the
knowledge available to the expert. This dissertation proposes classification of
planning problems based on their use of expert knowledge. Such classification
can help in the selection of the appropriate planning method when dealing with a
specific planning problem.

The research concentrates on one of the identified classes of planning

problems that can be characterized by well-defined and well-structured problem-

solving knowledge. To achieve a more complete knowledge representation
architecture for such problems, this work employs the task-specific approach to
problem solving. The result of this endeavor is a task-specific methodology that
allows the representation and use of planning knowledge in a structural,
consistent manner specific to the domain of the application.

The shell for building a knowledge-based planning application was created
as a proof of concept for the methodology described in this dissertation. This
shell enabled the development of a system for manufacturing planning -
COMPLAN. COMPLAN encompasses knowledge related to four generic
techniques used in composite material manufacturing and, given the description

of the composite part, creates a family of plans capable of producing it.

ACKNOWLEDGMENTS

I would like to thank my advisor, Dr. Jon Sticklen for his support and
encouragement during my doctoral studies. Without stimulating discussions with
Dr. Sticklen this dissertation would have not been possible. Thanks also to my
dissertation committee Dr. George Stockman, Dr. Clark Radcliffe, and Dr. William
McCarthy for their guidance and support.

I am indebted to my colleagues in the Intelligent Systems Laboratory for
debates we had over the ideas backing this research. I am especially thankful to
Mr. Robert Hawkins and Dr. Timothy Lenz.

The most of the knowledge engineering effort made possible by a kind
contribution of time and practical knowledge of composite processing from Mr.
Roger Kaminski chemical engineer of a Lansing, MI based company Cade Auto
Air. in addition I would like to thank Mr. Gary Wigel VP of Engineering Cade Auto
Air and Mr. John Scanlon President of Cade Auto Air.

i am most thankful to my husband and colleague Oleg Lukibanov, without
his support and help I would be able to start and finish this research.

The part of the research reported here has been supported in part by the
DARPA RADEO program (ONR N00014-96-1-0678), by the NSF Rapid
Prototyping Initiative (NSF MlP-942-0351), and the Technology Reinvestment

Program (eee-9412783 613224).

TABLE OF CONTENTS

LIST OF TABLES ............................................................................................... viii
LIST OF FIGURES ............................................................................................... ix
Introduction ........................................................................................................... 1
1.1. Planning Problem ..................................................................................... 1
1.1.1. Knowledge Based Planning ................................................................ 2
1.1.2. Solution Requirements ....................................................................... 4

1.2. Research Context ..................................................................................... 5
1.2.1. Hierarchical Task Networks ................................................................ 5
1.2.2. Generic Task Approach ...................................................................... 7

1.3. Research Objectives ................................................................................ 8
1.3.1. Application Issues ............................................................................... 9
1.3.2. Organization of the Dissertation. ...................................................... 10

2. AI Planning: Review of Related Research ................................................... 12
2.1. Planning Approaches Based on Search ................................................. 13
2.2. Case Based Planning ............................................................................. 16
2.3. Reflective Planning ................................................................................. 18
2.4. Hierarchical Task Network Planning ....................................................... 21
2.4.1. Knowledge Acquisition Tools for HTN Planning ............................... 23

2.5. Conclusion .............................................................................................. 25
3. Task Specific Approaches in Planning: Review of Related Research ......... 30
3.1. CommonKADS ....................................................................................... 30
3.1.1. The Framework for Representing and Analyzing Planning Methods 31
3.1.2. KADS Based Models for Knowledge Based Planning ...................... 33
3.2. PROTEGE -ll .......................................................................................... 34
3.2.1. Skeletal Plan Refinement ................................................................. 35
3.3. EXPECT Framework .............................................................................. 37
3.3.1. Plan Evaluation and Critiquing .......................................................... 38
3.4. Generic Tasks ........................................................................................ 39
3.4.1. Routine Design ................................................................................. 41
3.4.2. Routine Design Applications in Planning .......................................... 44
3.5. Conclusion .............................................................................................. 48
4. Problem Definition ....................................................................................... 51
4.1. Information Processing Used in Planning ............................................... 52
4.2. Classes of Planning Problems ................................................................ 54
4.3. Problem Statement ................................................................................. 56
4.4. Conclusion .............................................................................................. 57
5. Knowledge Architecture for Planning .......................................................... 59
5.1. A Task Analysis of Class 3 Problems ..................................................... 59
5.1.1. Propose ............................................................................................ 61
5.1.2. Critique ............................................................................................. 63
5.1.3. Modify ............................................................................................... 64
5.1.4. A Control Strategy ............................................................................ 65

5.2. The Problem-Solving Architecture .......................................................... 66

5.2.1. Specialists ........................................................................................ 67
5.2.2. Goal Achieve Specialists .................................................................. 68
5.2.3. Decomposition Specialists ................................................................ 69
5.3. Discussion .............................................................................................. 69
5.3.1. Problem Solving ............................................................................... 69
5.3.2. Knowledge Acquisition ..................................................................... 71
5.3.3. Applicability Issues ........................................................................... 74
5.4. Conclusion .............................................................................................. 76
6. A Software Tool for Developing Planning Applications ............................... 77
6.1. Introduction ............................................................................................. 77
6.1.1. Sample Problem ............................................................................... 78
6.2. Problem Solver Components .................................................................. 78
6.3. Database (DB) ........................................................................................ 79
6.4. Specialists .............................................................................................. 81
6.4.1. Decomposition Specialist ................................................................. 82
6.4.2. Step Specialist .................................................................................. 85
6.5. Problem Solving ..................................................................................... 86
6.5.1. Single Planning ................................................................................. 87
6.5.2. Multiple Planning .............................................................................. 90
6.6. Extension of the GT approach ................................................................ 93
6.7. Conclusion .............................................................................................. 93
7. Intelligent Systems in Composite Manufacturing ......................................... 97
7.1. Concurrent Product/Process Design in the Composites Domain ........... 97
7.2. CAM Systems in Composites ................................................................. 98
7.2.1. ACES ................................................................................................ 99
7.2.2. DSSPreform ................................................................................... 100
7.2.3. Cost modeling for AdvRTM ............................................................ 101
7.2.4. S-APD ............................................................................................ 102
7.2.5. SOCHARIS ..................................................................................... 103
7.3. Comparative Analysis ........................................................................... 105
7.3.1. Application Domain ......................................................................... 105
7.3.2. Solution Approach .......................................................................... 107
7.3.3. Problem Solving Technique ............................................................ 108
7.4. Conclusion ............................................................................................ 109
8. Composite Material Manufacturing Planning: an Application Problem
Statement ......................................................................................................... 1 11
8.1. Composites Manufacturing ................................................................... 113
8.1.1. Layup .............................................................................................. 114
8.1.2. Resin Transfer Molding .................................................................. 115
8.1.3. Resin Infusion ................................................................................. 116
8.1.4. Compression Molding ..................................................................... 116
8.2. Domain Problem Specification ............................................................. 117
8.3. Conclusion ............................................................................................ 119
9. COMPLAN: A Knowledge-Based Application for Composite Material
Manufacturing Planning .................................................................................... 121

vi

9.1. System Implementation ........................................................................ 121

9.1.1. Layup Planning ............................................................................... 124
9.1.2. RTM Planning ................................................................................. 129
9.1.3. Resin Infusion ................................................................................. 131
9.1.4. Compression Molding ..................................................................... 133
9.2. Case Study ........................................................................................... 135
9.2.1. Plan Generation for Layup Process ................................................ 136
9.2.2. Plan Generation for Resin Infusion Process ................................... 138

9.3. Testing COMPLAN ............................................................................... 141
9.4. Future Extensions ................................................................................. 143
9.5. Conclusion ............................................................................................ 144
10. Conclusion ......................... ‘ ....................................................................... 146
10.1 . Contributions to the AI Area ................................................................. 148
10.1.1 .Contribution to KBS ........................................................................ 148
10.1.2.Contributions to Al Planning ........................................................... 149
10.2.Contributions in Composite Material Manufacturing ............................. 150
10.3. Future Research ................................................................................... 150
10.4. Final Remarks ...................................................................................... 153
APPENDIX A .................................................................................................... 163
APPENDIX B .................................................................................................... 167
APPENDIX C .................................................................................................... 176
APPENDIX D .................................................................................................... 183
APPENDIX E .................................................................................................... 191

vii

LIST OF TABLES

Table 1. Examples of Al Planning Systems ........................................................ 29
Table 2. Control Strategy for Planning ............................................................... 66
Table 3. Variables Used in the House Construction Problem-Solver. ................ 80
Table 4. Step by Step Plan Generation for House Construction Problem Solver90
Table 5. Knowledge-Based Systems in Composites Manufacturing ................ 106
Table 6. Functionality of the Knowledge-Based Systems in Composites
Manufacturing ........................................................................................... 1 07
Table 7. Input Data for Sample Problem .......................................................... 135

viii

LIST OF FIGURES

Figure 1. Forward Search in Space of States ..................................................... 13
Figure 2. Plan Space Search .............................................................................. 14
Figure 3. Case-Based Planning .......................................................................... 17
Figure 4. Reflective Planning: MOLGEN’s planning spaces ............................... 20
Figure 5. Hierarchical Task Network Planning .................................................... 22
Figure 6 . Propose-Critique—Modify Method for Planning .................................... 61
Figure 7. Propose Task ...................................................................................... 62
Figure 8. A Task Analysis of Planning Task of Class 3 ...................................... 65
Figure 9 . Taxonomy of the Control Knowledge ................................................. 73

Figure 10. The Hierarchy of Specialists in House Construction Problem Solver 82
Figure 11 . Method Selector for the Build Walls and Roof Specialist in House

Construction PS. ......................................................................................... 83
Figure 12. Method WithWaIlFrame of the specialist Build Walls and Roof in
House Construction PS ............................................................................... 84
Figure 13. Method With Foundation’ of the Specialist Build a House in House
Construction PS .......................................................................................... 85
Figure 14. Step Specialist lnsertBeams of House Construction PS ................... 86
Figure 15. Plan Hierarchy Generated by House Construction PS ...................... 92
Figure 16. An Information-Processing View on Composite Materials
Manufacturing Planning ............................................................................. 118
Figure 17. Problem-Solving Architecture of COMPLAN ................................... 122
Figure 18. Specialist hierarchy for Layup Planning Problem —Solver ............... 125
Figure 19. The Method ‘main’ used by the Top Specialist of the Layup Planning
Problem-Solver ......................................................................................... 126
Figure 20. Method Selection Table for the Preparation Specialist of the Layup
Planning Problem-Solver ........................................................................... 126
Figure 21. An Example of the Method of Curing Specialist in Layup Planning
Problem-Solver ......................................................................................... 127
Figure 22. Autoclave cure Step Specialist Layup Planning Problem-Solver ..... 128
Figure 23. Standard-layup Method of Layup Specialist Layup Planning Problem-
Solver ........................................................................................................ 129
Figure 24. Resin Transfer Molding Planning Specialist Hierarchy .................... 130
Figure 25. Resin Infusion Planning Specialist Hierarchy .................................. 131
Figure 26. Compression Molding Planner Specialist Hierarchy ........................ 133

INTRODUCTION

1. 1. Planning Problem
One could define the planning problem as a problem of finding a

sequence of actions whose execution results in achieving a goal state, given the
description of the initial state in the universe of discourse. Research in Artificial
Intelligence (Al) planning covers different aspects of understanding and
managing the effects of actions in order to enable plan generation, modification
and execution. This dissertation is intended to further develop the Al planning
methodology to support the construction of planning applications.

Traditionally, the problems addressed in Al planning are computationally
hard and lie on the borderline- or beyond - of human cognitive abilities (e.g.
block manipulation or theorem proving). For such problems, little semantic
information is available, and a solution is usually generated by an extensive
search. As a result, a significant amount of research is focused on the design
and analysis of planning algorithms, with an emphasis on the search efficiency.
These algorithms have been successfully applied to a number of real life
problems such as logistics or machining operations planning.

In contrast, this research addresses different kinds of problems - the
problems that are computationally simpler, but require an extensive amount of
knowledge to generate the solution. Examples of these problems can be found in

everyday activities such as shopping or using the telephone, as well as in expert

problem-solving, such as design process planning or business process planning.
These types of problems are referred to hereafter as knowledge-intensive
planning problems.

Traditional planning languages do not support an adequate representation
of the semantically rich knowledge structure used in knowledge-intensive
planning. The success of the application system usually relies on the experience
and ability of the knowledge engineer who codes the knowledge into the
computer program. To facilitate the development of planning systems for
knowledge-intensive problems, attention should be given to the way experts
conceptualize and use problem-solving knowledge. The development of the
representational methodology that allows the capture of the semantic structure of
the planning knowledge in an application is a center of cencem in this
dissertation.

1.1.1. Knowledge Based Planning

One of the main difficulties in the creation of the fielded applications of AI
planning systems is developing and maintaining large knowledge bases. The
research that tackles this problem branches in two directions:

1. Development of tools based on existing representations to support
constructing, debugging, verifying and updating planning knowledge
bases.

2. Development of new knowledge representation methods as a result of

knowledge level analysis of planning problem solving.

A number of researchers inside the AI planning community (desJardins
1994; Chien 1996; Fox and Long 1998; Fox and Long 1999) address the issues
of knowledge representation and acquisition by enhancing existing planning
methods and developing tools for knowledge editing and analysis. Although such
tools can enhance the development of planning systems, the benefits that they
provide are somewhat limited. These tools support domain independent planning
methods, which are universal, weak search methods. Thus, the supported
knowledge representations are bound to knowledge structures that are
theoretically applicable to a wide variety of planning tasks, but poorly suited to
any specific task.

A more general solution to the knowledge acquisition problem will likely
require moving beyond the traditional planning approaches to a task-level
analysis of planning problems. Such an analysis can result in a representational
methodology relevant to a specific planning task that will take advantage of the
underlying knowledge organization of the problem domain to better support
knowledge acquisition

The knowledge-level analysis of planning problem solving has been
attempted by several research groups within the KBS field (Valente 1995; Barros,
Valente et al. 1996; Benjamins, Barres et al. 1996). These analyses resulted in
the development of task-specific architectures for a number of planning tasks.
While this research provided support for the conceptual decomposition of
planning problems, the description of problem-solving behavior is expressed in

terms of generic inferences. Consequently, the actual reuse of problem-solving

knowledge is carried out mostly at the level of basic logical relations. Meanwhile,
there are certain benefits in the use of knowledge structures developed
specifically to capture large granules of knowledge typical to a particular task.
Such use-oriented knowledge representations support more effective transfer of
expert knowledge to a system representation and facilitate knowledge acquisition
and problem solving. Further research along this line will enhance the
development of the fielded applications for knowledge intensive planning
problems.

1.1.2. _So_lution Reggirements

Task-level framework development requires understanding the task
structure gained through the analysis of problem solving. The goal of this
analysis is to identify the vocabulary that can describe the knowledge used to
solve tasks of a particular class. Recognizing the knowledge roles provides
guidance in organizing domain knowledge for solving a particular type of task.
The main objective is to avoid the generality of universal approaches by finding
the knowledge representations that are sufficient to capture the specifics of a
particular task and, on the other hand, which are general enough to be
configured for different application domains.

From the knowledge-level perspective any planning system can be
described by three components: the basic knowledge structures, the organization
of knowledge in the system, and the control knowledge that drives the system.
The basic knowledge structures are the building blocks of the system. They

define the terms in which the knowledge is formulated. The knowledge

organization specifies how fragments of the knowledge are related in the system.
Finally, the control knowledge - the planning algorithm - specifies how to identify
and select relevant pieces of knowledge and how to apply them to generate a
solution.

In order for an approach to model task-level problem-solving behavior
successfully, its three components mentioned above should satisfy the following
requirements. First, the knowledge primitives used should reflect domain
concepts that an expert manipulates in order to generate a plan. Next, the
organization of knowledge should explicitly represent semantic relationships that
are essential to the planning problem solving domain. Finally, the control
knowledge should make use of this semantic information in plan generation,
which allows tailoring the planning algorithm to most effectively exploit the
structure of the domain knowledge.

1.2. Research Context

This research is at the borderline between AI planning and the KBS field -
various studies in these areas influenced it. While the accurate and detailed
account of related work will be presented in Chapters 2 and 3, the following
describes the theories that most influenced the methodology described in this
dissertation.

1.2.1. flrarchicgl Task NeMorks

Hierarchical Task Network (HTN) planning (Wilkins 1988; Erol, Nau et al.
1994; Erol, Nau et al. 1994) allows the incorporation of procedural, plan

generation knowledge into the system. This is in contrast to the majority of Al

planning approaches that limit the domain knowledge by describing states and
actions. The problem solving knowledge in HTN is represented in the form of
task reduction methods that contain prescriptions of how to decompose tasks
that occur during the planning process into simpler sub-tasks.

HTN is the most common approach for developing real world applications.
However, this methodology does not provide a facility that can effectively guide
the process of knowledge elicitation. There are several drawbacks of HTN as
applied to the issues related to knowledge acquisition and management:

- The expert knowledge is stored in a flat rule-base like order. Standard
objections to RBS1 methodology can be raised with respect to HTN, in
particular the difficulties in maintaining large knowledge bases in a flat
RBS.

- The HTN approach does not provide the ability to explicitly represent
the use of the domain control knowledge and existing compiled
problem solving scenarios; instead, this kind of knowledge is hidden
either in an inference engine or cleverly formulated methods within a
flat knowledge base.

Consequently, the success of a particular HTN planning system depends
not only on the quality of the experts’ knowledge, but also on the successful use
of the framework as a programming device. In order to facilitate the knowledge
acquisition process, which is the major part in the development of real world

applications, the basic knowledge representation employed in HTN must be

 

1 RES - Rule-based System

enhanced by more sophisticated structures that are used in planing

problemsolving by human experts.

1.2.2. Generic Task Approach
The Generic Task (GT) Approach (Chandrasekaran 1983;

Chandrasekaran 1986; Brown and Chandrasekaran 1989) resulted from the
analysis of expert problem-solving for a variety of real world problems. This
analysis revealed a set of problem solving strategies or methods that can be
used to solve certain classes of problems, where problems are classified based
on the similarity of their information processing tasks. The pair task/problem
solving method is termed genen'c task. Examples of generic tasks are:
hierarchical classification, routine design, structural matching, and functional
reasoning (Bylander and Mittal 1986; Bylander and Goel 1988; Sticklen and
Chandrasekaran 1985; Chandrasekaran 1993; Hawkins, McDowell et al. 1993;
Josephson and Josephson 1994).

Implemented generic tasks have proven to be useful as prescriptive
models of problem solving. Each task is characterized by the control strategy
required by the task and the set of knowledge representation templates that can
be configured to capture the specifics of a particular domain problem. Central to
GT is the hypothesis that the knowledge should be represented differently
according to its intended use (Chandrasekaran 1986). Although this mode of
knowledge representation can lead to duplication of knowledge stored, it ensures
a more efficient mode of problem solving, since the knowledge in each instance

is represented in a form most suitable for its immediate use. Moreover, such a

use-oriented representation supports more effective transfer of human problem

solving knowledge to a system’s representation.

The GT approach has been applied to develop numerous knowledge-
based applications, most of which have focused on the solutions of design and
diagnosis tasks. The intuition is that the planning domain can also benefit from
the semantically meaningful knowledge representation methods and structured
inference strategies typical of GT systems. The application of GT methodology to
the analysis of the planning task will be the next step in developing a planning
system that provides a mechanism for the exploration and examination of
knowledge as well as for effective system maintainability and reuse.

1.3. Research Objectives

This research focuses on knowledge-based planning, and, in particular, on
the issues of task analysis and knowledge acquisition and representation in
planning. In this problem-solving context, the primary objectives of the research
reported here are the following.

1. To apply the Generic Task methodology to the analysis of planning problem
solving. To develop, based on this analysis, the representational methodology
and an inference mode that allows capturing and using the domain specific
knowledge used in planning.

2. To implement this methodology in a software tool that provides support for
knowledge acquisition and problem solving for knowledge-based planning

applications.

3. To implement, as a proof of principle, a working, knowledge-based system
using the developed methodology and software tool.

1.3.1. Application Issues

The design and manufacturing with composite materials offers an
interesting domain for the application of KBS methodologies. A composite
material is a heterogeneous combination of two or more materials (e.g.
reinforcing elements, fillers and binders) differing in form or composition or on a
macroscale. Composite materials have been named the material of the future —
largely because of the flexibility to custom design a material to the requirements
of a specific application. At the same time this flexibility is often accompanied by
increased design and manufacturing complexity, which requires wide expertise in
the decision making process. However, the engineers and manufacturing
specialists in the domain usually work within narrowly defined sub-areas and lack
a wider knowledge perspective to fully explore the possibilities of composites.
These considerations make this domain especially attractive for the application of
knowledge intensive methods that can be applied to provide wide domain
expertise to support problem solving.

Manufacturing planning with composites will be the focus of the
application of this research work. Manufacturing considerations play a very
important role in composites beginning from the first stages of the design. In part,
this is because many design factors (e.g. geometry, functional requirements,
production rates, and material system) either constrain or suggest specific

composite fabrication technologies. Because the selection of a manufacturing

process can greatly affect both the functional qualities and the cost of the final
product, manufacturing concerns often supercede design concerns. Even for
issues solely concerning manufacturing, the large variety of technological
processes available - each with numerous variations and capabilities - can
complicate the generation of a manufacturing plan or the comparison of
fabrication alternatives for the part.

The knowledge-based system developed as an application of techniques
described in this work generate alternative manufacturing plans, given a
description of a composite part design, requirements specification, and a
specification of the composite material system. The implementation requires the
ability to operate with a large amount of domain expertise, represent different
types of problem solving knowledge and deal with multiple solution alternatives.
This application is valuable for not only composites domain experts, but also will
also acts as a testbed for the ideas in knowledge-based planning which are
developed in the dissertation.

1.3.2. Organization of the Dissertation.

The remainder of this research describes in detail the work undertaken to
achieve the research objectives outlined above. The dissertation includes three
organizational sections: (1) the analysis of related work in planning, the problem
statement and a solution description; (2) the description of the application in
manufacturing planning; and (3) the discussion of the reported research.

Chapters 2 and 3 review the related work in knowledge-based planning,

they contain the analysis of the planning problem as well as issues related to the

10

development of planning systems. These chapters outline two main lines of
research: the work by the planning community and by the KBS community.
Chapter 4 presents the problem statement and requirements for the solution. The
next two chapters detail the solution to the stated problem. Chapter 5 presents
the task analysis of the knowledge based planning and offers a conceptual
knowledge architecture for planning, and Chapter 6 describes a software tool that
implements the proposed knowledge architecture.

An application in composite material manufacturing is described in
Chapters 7 through 9. Chapter 7 gives an overview of other applications in
manufacturing planning and specifically in composites manufacturing. The
analysis of the planning problem in the composites domain is given in Chapter 8,
the application system for composite manufacturing planning is described in
Chapter 9.

Finally, Chapter 10 contains the evaluation of the research presented in
this dissertation with respect to Al and composites domains as well as possible

venues of future research.

11

2. AI PLANNING: REVIEW OF RELATED RESEARCH

With the advancement of computer technology over the last decade there
has been a dramatic increase in interest regarding automated and semi-
automated planning applications for engineering, manufacturing, management,
etc. This increased interest has drawn attention to the research in Al planning.
Classical Al planning is concerned mainly with the generation of plans to achieve
a goal in situations where the state of the world is known. Some important results
have been reached in the design and analysis of planning algorithms; however,
in many cases, the techniques developed in Al planning remain unrealized. The
existing gap between theory and practice in planning has been named one of
challenge problems in Al (Selman, Dean et al. 1996).

This chapter presents an overview of the research in planning and
discusses what should be done to facilitate the development of practical
applications in planning. Table 1 gives a summary on the planners used
throughout this section as examples of various planning approaches.

Section 1 overviews the work related to the design and analysis of
planning algorithms, which traditionally has been the main interest of Al planning.
Sections 2 through 4 describe methods that emphasize the importance of the
domain knowledge in planning and discuss the issues of applying these
approaches to real-life problems. Finally, the conclusion outlines the
contributions of the described approaches and presents the motivation for further

research concerned with knowledge use in planning problem solving.

12

2. 1. Planning Approaches Based on Search
The line of research in Al planning started in the early seventies with the

development of the STRIPS system (Fikes and Nilsson 1971) which was inspired
by the GPS (General Problem Solver) system (Newell and Simon 1963). STRIPS
followed a state space planning approach, where a plan is built through a search
in the space of problem states. Following this approach the planner starts from
the initial state and keeps adding new operators, which expand the current state
until the goal is met. Different inference strategies could be used here, for
example STRIPS uses backward chaining, and TLPLAN (Bacchus and Kabanza
1996) uses a forward-chaining strategy. The algorithm for state space planners is
simple and easy to implement, but it is not guaranteed to produce even a partial

solution because the search is not directed by the goal.

 

 

  
 

Initial State So]ution Plan

 

Figure 1. Forward Search in Space of States

13

 

The alternative to state space planning is plan-space (causal link)
planning illustrated on the Figure 2 (ABSTRIPS (Sacerdoti 1974), UCPOP
(Penberthy and Weld 1992)). A plan is built starting from an empty plan that
contains the initial state and goal by adding new steps to achieve open
preconditions. Sometimes the effects of a newly added step will negate the
preconditions of a step that was added earlier, threatening the previously
established causal link. The methods of resolving such threats are one of the
most important issues in causal link planners.

The goal-directed plan generation inherent to causal link planning makes
this approach more favorable than the state space planning. However, the plan-
space is potentially much larger than state space for some problems — this is a
considerable drawback during the problem-solving process and demands the
development of methods that simplify the search. One of the solutions to this
problem was proposed in the system ABSTRIPS which performed planning in a

hierarchy of abstraction spaces.

 

 

Initial Plan
[M |

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 2. Plan Space Search

14

 

The general planning algorithm that uses abstractions can be described
as follows: given a problem, map it into an abstract space and find a solution,
then refine the abstract solution. This procedure can be applied recursively using
higher and higher abstractions. ln ABSTRIPS, new abstractions are generated by
relaxing some preconditions in the operator specifications. (Knoblock 1990)
reports that abstraction planning can provide an exponential reduction in a
search when the abstraction decomposes the problem into a set of constant size
subproblems; however, a bad abstraction can make the problem exponentially
worse (Backstorm and Jonson 1995). This situation occurs when the abstraction
does not decompose the problem effectively and excessive backtracking takes
place across levels of abstraction.

(Nau, Gupta et al. 1995) point out that the traditional Al planning is
concerned mostly with the development of solutions to abstract problems using
abstract problem representations that omit “unimportant” details that, in fact, are
critical in any real-world situation. The approaches explained in this section limit
the domain knowledge by the description of actions and states. These methods
can be considered weak search methods because the solution is generated
through the search, and no domain knowledge or task-specific knowledge is
used to solve the problem more efficiently. The success of a particular
application depends largely on compatibility of the method to the domain problem
at hand. The search methods are useful in cases when no problem solving-

knowledge is available, and, hence, the search is the only alternative. Usually the

15

search can be successfully applied to problems in limited, simple domains.

However, the majority of real planning problems solved by people requires reach

domain descriptions and extensive knowledge; therefore, the use of search

techniques is not feasible in many cases. The following sections will expound
upon the several planning approaches that use domain knowledge in plan
generation.
2.2. Case Based Planning
In Case-Based Planning, previously generated plans are stored as cases

in memory and can be reused to solve similar planning problems in the future.
That is, the case-based reasoning system stores a library of previous problems
with known solutions. When a new problem is entered in to the system, it
searches the library to find the problems closest to the current problem. The
differences between retrieved and current problems are then identified, and, by
using the available knowledge, the solution of the library case is modified to fit
the current case. Three issues are involved in case-based reasoning:

1. Organization of the case memory, which has to be indexed to allow the
efficient retrieval of cases based on requirements. Usually the memory is
indexed based on the set of features essential for the class of problems
solved by the system.

2. The techniques used to adapt retrieved solutions to meet the requirements of
the new case. This typically involves the application of domain-specific

knowledge used to critique and modify previous solutions.

16

3. Learning‘ the new cases involves recognizing the solutions that avoid

problems and correctly indexing them in the case memory.

 

 

Problem
Statement

 

.0, Solution Plan
__.\ M__..l . Q E
Find Adapt Store

v S New

Case

 

 

 

 

 

Similar olution ,

Problem
e—u—uo—ve

‘/

0.

Case Memory

 

 

 

Figure‘3. Case-Based Planning
The CHEF system (Hammond 1990) is an example of a planning system

which uses case-based reasoning to generate recipes from Chinese cuisine. The
planning starts by retrieving a recipe from the case library that meets most of the
requirements for the requested recipe. Then, the planner applies transformations
such as ingredient substitution, addition, removal, or replacement of the goals or
steps in the plan. The generated plan-recipe is then simulated to predict and fix
problems. Finally, the plan is stored in the case library, which is organized as a
network of goals at different levels of abstraction. An important feature of CHEF
is that it uses two libraries: the library of successful plans is used in plan
generation, and the library of failures is used to predict problems with generated

plans.

17

 

Currently case-based reasoning is most widely applied to metal machining
operations planning (Munos-Avila and Weberskirch 1996; Chang, Lu et al. 1998).
The case library is used to store data about parts and related processes. The
library is indexed based on feature information of the machined components,
such as geometric shape, material, features, etc..

Case-based planning relies on the availability of an initial set of plans
which cover the intended domain. Consequently, case-based reasoning is only
feasible for the domains where such case libraries exist. For these domains, the
approach can save considerable time over planning from scratch (generative
planning), thus offering a potential mechanism for handling intractable problems.
One drawback of case-based reasoning systems has been the need for a highly
structured memory that requires significant domain engineering and complex
memory indexing schemes to enable efficient case retrieval which is not always
achievable.

2.3. Reflective Planning

Reflective planners use meta-knowledge to control plan generation. The
reflective system can be characterized by the ability to control its decision making
process. The system is organized in layers, where upper layers operate with the
problem-solving control knowledge and lower levels operate with the domain
knowledge. The idea was anticipated by (Simon 1963), in his work with Heuristic
Compiler in GPS (General Problem Solver) framework. He proposed that the
problem solving process of the Heuristic Compiler would be governed by GPS.

The problem solving operators used in a task environment are distinguished from

18

domain operators. The GPS would first be applied to the task environment to
manage the application of the domain operators.

The cognitive model of errand planning proposed by (Hayes-Roth and
Hayes-Roth 1979) uses a black board partitioned into several planes. The
executive plane directs resource allocation and the planning strategy; a meta-
plan plane is used to control problem solving behavior; and the three remaining
planes plan the intermediate subtasks of the errand running domain. The model
supports opportunistic planning, where the decisions on various levels of problem
solving are event driven. The knowledge is represented in the form of production
rules, and, while there is no grouping of productions, some productions serve
mainly as control functions and others represent domain-level facts.

The opportunistic planning model proposed by Hayes-Roth is bi-
directional: the bottom-up processing is combined with top-down feedback from
the meta-level. This study shows the important role that control knowledge plays
in planning problem solving. However, as pointed out in (Stefik 1981), the
separation of domain and control knowledge is not enforced in the model. The
production rules are organized as a monolithic set; this, combined with the
unpredictable behavior of planning program, could make the task of developing
and maintaining a knowledge base very complex. However, it is important to note
that the main goal of this research was to model human problem solving as
observed in protocol studies, rather than to study the issues of knowledge

representation.

19

Another example of a reflexive system is MOLGEN (Stefik 1981; Stefik
1981), the system used for planning gene-cloning experiments in molecular
genetics. MOLGEN is based on the hierarchical abstraction algorithm similar to
the ABSTRIBS algorithm, and uses meta-knowledge to analyze the goals and
generate constraints on a possible sequence of operator applications in order to
avoid conflicts between goals. MOLGEN uses a layered control structure similar
to the previously described approaches. There are three layers of control, termed
planning spaces: strategy space, design space and laboratory or domain space.
Domain space operates with knowledge about objects and operations of a
genetic laboratory. The design space contains knowledge about designing plans;
this space models actions of the experiment designer. Strategy space uses the

knowledge about strategy to direct problem solving in design space.

 

 

 

\ Strategy Steps \

Strategy Space

Meta-Planning

fr
\ Design Steps \

 

 

 

 

 

Design Space
. Planning
v
Lab Steps
Laboratory Space

 

Figure 4. Reflective Planning: MOLGEN’s planning spaces

20

 

The research on MOLGEN showed that some of the decisions refer to the
process of problem solving, rather than to the particular problem at hand. That is,
a big part of knowledge used in planning can be best understood as belonging to
meta-levels. While the MOLGEN meta-level is limited by domain independent
strategy operators, the author underlines the greater need in “factoring the
knowledge used in control structure.” This might involve research on the use of
domain-specific control knowledge to enable “reasoning about scenarios.” This
kind of knowledge allows to consider commitments and decisions that were
made on the domain level to define the further direction or strategy of problem
solving.

2. 4. Hierarchical Task Network Planning

Hierarchical Task Network (HTN) planning is the method most commonly
employed in practical planning applications. First used in NOAH (Sacerdoti
1975), HTN planning gained considerable popularity as a number of HTN
planning systems were developed throughout the years: SIPE (Wilkins 1988;
Wilkins 1990), O-Plan (Tate 1990; Currie and Tate 1991; Tate, Drabble et al.
1994), UMCP(EroI, Nau et al. 1994; Erol, Nau et al. 1994). An HTN planning
system has a knowledge base that stores methods, which contain prescriptions
of how to decompose tasks into a set of sub-tasks. When given a task, an HT N
planner chooses an applicable method, instantiates it to decompose the task into
sub-tasks and then uses other methods to decompose the sub-tasks further. This
process continues until directly executable primitive tasks are found. If the

decomposition fails before the primitive tasks are reached, the system will

21

backtrack and try other methods. Formal analyses of HTN planning (Erol, Nau et
al. 1994; Erol, Nau et al. 1994) have proven its soundness and completeness
and have shown that it is strictly more expressive than planning using traditional

STRIPS-style representations.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
   

mmmnm
”6“”ch Imam-4W 1...... ‘
m
m M
Task D Reduction

 

 

 

a.»

Solution Plan

WWI

 

 

 

 

Figure 5. Hierarchical Task Network Planning
The HTN approach allows a considerable reduction in the computational

cost of planning by applying expert task-reduction knowledge. However, there

are several drawbacks of the HTN methodology as applied to the problems with

existent extensive domain knowledge:

1. The expert knowledge is stored in a flat rule-base like order. Standard
objections to RBS methodology can be raised with respect to HTN, In
particular, the difficulties in maintaining large knowledge bases in a flat RBS.
Because the interdependencies between rules are not shown explicitly,

modifying and debugging the knowledge base can become extremely difficult.

22

 

Usually, “a major factor in determining the feasibility of applying Al planning
techniques to real-world problems is the amount of effort required to
construct, debug, verify, and update the planning knowledge base...(Chien
1996). ”

. The HTN approach does not provide the ability to explicitly represent and use
domain control knowledge. The HTN does not have explicit means to
represent the existing compiled problem-solving scenarios; instead, they are
hidden either in an inference engine or cleverly formulated methods within a
flat knowledge base. Consequently, the success of a particular HTN planning
system depends not only on the quality of the experts’ knowledge, but also on
the successful use of the framework as a programming device.

. The HTN techniques do not give a facility or framework that can effectively
guide the process of knowledge elicitation from experts.

The problems noted above should be viewed as difficulties with HTN

systems, but not with the use of task decomposition rules as a method for

expressing planning knowledge. While there is nothing in principal to prevent the

use of rules as an underlying knowledge representation, higher level approaches

are required to overcome the problems discussed above. Several researchers in

the planning community addressed the problems noted above and proposed to

enhance HTN planning systems with relevant knowledge acquisition (KA) tools.

2.4.1. Knowledge Acquisition Tools for HTN Pgming
To support the acquisition and management of specialized knowledge

structures used by the existing planning systems, several KA tools were created.

23

They were designed to facilitate constructing, debugging, verifying and updating
planning knowledge bases. (desJardins 1994) describes the graphical operator
editor developed for the system SOCAP, a prototype military operations planning
system based on SIPE-ll. The operator editor provides a graphical interface for
building and modifying SOCAP planning operators. Methods for checking the
validity of the operators using the type structure of the domain knowledge base
are also provided. The operator editor supports writing operators using an
abstraction language that allows the development of partial operator descriptions.
These descriptions can be refined by an inductive learning tool that uses
feedback from simulation and from the user’s choices during planning.
(McCluskey and Kitchin 1998) describe a different approach to the
development of planning knowledge bases. While most of the approaches are
centered on developing verification tools for traditional operator-centered
representations, McCluskey at. al. propose a new, object-centered encoding of
HTN planning, which, they argue, is more convenient for complex domains. The
approach was implemented in the language OCLh, which emphasizes concurrent
development of the abstract operator set and the specification of the objects that
operators manipulate. An object in OCLh is specified through the set of its valid
sub-states. The objects are organized into sort hierarchies according to
admissible transitions through the sub-states. The planning state in OCLh is
described as a combination of objects’ sub-states. This approach supports the

validation of the model with respect to the domain requirements.

24

The research reported in (Chien 1996) aims to support the verification of
planning domain knowledge using static analysis tools and completion analysis
tools. These tools were developed within the context of the HTN-based
Multimission VICAR Planner system that automates image processing. Static
analysis tools analyze the domain knowledge roles and operators to check if the
pre-specified problem classes are solvable. This is done by fast, run-time
checking using propositional analysis of the rules or off-line knowledge base
analysis to verify domain coverage. Because of computational tractability issues,
the static analysis checks are limited by detecting situations where a faulty
knowledge base causes a top level goal or operator precondition to be
unachievable. The other types of tools are the completion analysis tools used
when the planner fails to generate the plan or if the generated solution is invalid.
Completion analysis tools partially automate the debugging of knowledge bases
by assuming some goals to be achievable. If a problem becomes solvable with
this assumption, the user can focus on the assumed goals in order to isolate the
bug in the knowledge base.

2. 5. Conclusion

The approaches developed in Al planning vary from search-based to
knowledge-based. In order to decide which planning method is more
advantageous in each particular case, the available domain problem-solving
knowledge needs to be determined. The lack of such knowledge will preclude the
use of knowledge-intensive methods, and using the search methods will be the

only feasible alternative.

25

At the same time, many practical problems exist, from planning everyday
activities to expert problem solving, for which the available knowledge exists and
can be used to direct and facilitate the problem-solving process. The application
of search methods for these problems would not allow utilizing the available
problem-solving knowledge. Moreover the search space for many real life
problems is so big that the application of pure search methods is unfeasible. The
need to work applications for this class of problems draws attention to the
knowledge-based methods in planning.

Several knowledge-based approaches to planning were described in this
chapter: case-based planning, reflective planning, hierarchical task network
planning. These approaches can be divided into two groups according to the
view of human problem solving they represent. The case-based planning is
derived from the model of human problem solving proposed by Shank. The
underlying idea is that people use past experience to solve new problems; they
do it by remembering similar past problems and by reasoning about altering the
stored solutions to fit new requirements. The alternative view accepted by
reflective reasoning and HTN approaches exploits humans’ ability to build
generalizations of their empirical experiences. Very often people who continually
face similar situations analyze them and draw generalized conclusions or
“compiled knowledge” that helps them to solve new problems.

The views described above represent two alternative knowledge-based
approaches to problem solving that can be used in different situations. While

both views can be useful for modeling planning reasoning, this dissertation

26

research concentrates on the second view, which emphasizes the problem-
solving expertise resulting from the analysis of previous experience. The
research in reflective planning and HTN planning investigates the issues of
knowledge representation and its use in planning. It also brings out the problems
that occur with knowledge acquisition and knowledge base maintenance when
developing high- scale applications. To solve these problems many researchers
in the planning community have focused their efforts on applying KA methods to
existing planning systems. The tools that have been developed allow creating
and debugging planning knowledge bases, support verification, validation and
testing, and facilitate updates and maintenance. While the knowledge acquisition
tools that support the traditional representations can facilitate the development of
specific applications to some extent, considerable effort is required to map the
domain problem-solving knowledge to the knowledge base when developing a
particular application. Usually, this process requires an Al expert as opposed to a
domain expert (desJardins 1994)because the approaches currently used for
developing planning systems are bound to knowledge structures that are
theoretically applicable for a wide variety of planning tasks but (which) are poorly
suited to any specific task. The conventional planning languages can be
compared to an assembler programming language for writing planning systems
and are rather low level with respect to modeling task-level behavior. It seems
that a more general solution lies in a task-level analysis of planning problem
solving. Such an analysis can result in a representational methodology inherent

for the specific planning task that will leverage the underlying knowledge

27

organization of the problem domain and, therefore, better support knowledge

acquisition and problem solving.

The next chapter gives a general background on Task Specific

approaches and reviews the research related to the task-level analysis of

planning problems.

 

 

Institute Problem

Name Description
STRIPS Uses means-ends analysis to perform state space
(Stanford Research planning.

Generates ordered plans.

 

(Sacerdoti 1974)

Solver)

(Fikes and Nilsson

1971)

ABSTRIPS Introduced the idea of abstraction planning. Constructs
(Abstraction an abstraction hierarchy for a problem space, then uses
STRIPS) the abstractions for hierarchical planning. Abstraction

spaces are constructed by assigning criticalities,
numbers indicating relative difficulty, to the
preconditions of each operator.

Generates ordered plans.

 

NOAH
(Sacerdoti 1975)

First HTN planning system. Uses task decomposition
procedures to build task networks.
Generates partially ordered plans.

 

MOLGEN
(Stefik 1981; Stefik
1981)

Uses abstraction planning similar to ABSTRIPS.
Constraints are used to represent interactions between
sub-problems. Uses meta-knowledge to control the
planning process.

Applied in planning gene cloning experiments in
molecular genetics.

 

SIPE, SIPE —II
(System for
Interactive planning
and Execution )
(Wilkins 1988)

 

 

HTN-based planner.

Uses sort hierarchies to represent operations and
domain knowledge. Reasoning about resources.
Generates partially ordered plans.

Applications: air campaign planning, military operations
planning, oil spill response, production line scheduling,
construction planning, planning the actions of a mobile
robot.

 

 

Table 1. Examples of Al Planning Systems

28

 

O-PLAN (NONLIN)
(Currie and Tate
1991; Tate, Drabble

HTN planning system.
Applications: space platform constmction, satellite
planning and control, construction and house building,

 

et al. 1994) software development, Unix administrator’s script
writing, logistics, non-combatant evacuation operations,
crisis response, air campaimlanning workflow.
CHEFF A case-based planner for recipe retrieval.

(Hammond 1990)

 

UCPOP

Partial order plan space planner. Operates with actions

 

(Penberthy and that have conditional effects and universally quantified

Weld 1992) preconditions and effects. Uses a conservative search
strategy, HTN planning algorithm can be used
alternatively.

UMCP HTN planner.

(Universal Method Used for formal analysis of HTN planning: complexity

Composition analysis, proof of soundness and completeness.

Planner) Application: transport logistics.

(Erol, Nau et al.
1994; Erol, Nau et

 

 

 

al. 1994)

PRODIGY Combines means-ends analysis, backward-chaining

(Veloso, Carbonell search procedure with forward state space search. The

et al. 1995) algorithm uses depth first search and domain dependent
control rules, case-based reasoning, or domain
independent heuristics. Operators are organized
hierarchically in different levels of abstraction.
Generated plans are totally ordered.
Was initially developed to apply ideas of machine
leaminLin planning.

TLPLAN State space planning that utilizes domain-specific

Temporal Logic
Planner
(Bacchus and
Kabanza 1996)

 

search control infon'nation to control simple forward
chaining in order to make the search more goal-
directed.

 

Table 2 (continued). Examples of Al Planning Systems

29

 

3. TASK SPECIFIC APPROACHES IN PLANNING: REVIEW OF RELATED
RESEARCH

Task Specific Architectures (TSA) are based on the common assumption
that human problem solving can be classified into categories of problems, where
each category shares a common problem solving methodology. Task-specific
approaches provide a basis for the development of the second generation of
knowledge-based systems (KBS). In contrast to the first generation KBS that
used general-purpose tools, the second generation of KBS utilizes knowledge
architectures and inference engines that are specific to the task to be solved.

Several schools of thought have emerged over the years
(Chandrasekaran 1983; McDermott 1988; Steels 1990; Wielinga and Schreiber
1994). Although these schools differ in detail, they are based on the common
notion of models of problem solving. This chapter will present the research in
TSA related to the modeling of planning tasks.

3. 1. CommonKADS

The CommonKADS approach (Schreiber, B. J. Wielinga et al. 1994), the
successor of KADS (Knowledge Analysis and Design Support)(Wielinga and
Schreiber 1994), views the development of KBS as a modeling activity.
According to CommonKADS methodology, the development of KBS requires the
construction of a number of models that represent different views on problem-
solving behavior. For example, the construction of the organizational model
requires specifying the business resources, structural units, business processes

and the relationship between these components. Other models recommended for

30

the development of KBS are: tasks model, model of capabilities, model of

communication, model of expertise, and model of design. The central activity in

the process of KBS construction is building the model of expertise, which is

described using following components:

The domain ontologies specify the concepts, properties of concepts, and
relations, etc. of the problem domain. The domain ontology provides a
vocabulary to describe the domain model;

The inference knowledge represents the knowledge-based inferences, which
are performed during problem solving. Inference knowledge is defined by
inference functions (e.g., classification) and knowledge roles, (the domain
knowledge which forms input and output of the inference function). The
inferences are also associated with assumptions on the availability and
various properties of domain'knowledge;

The task knowledge is defined from the functional perspective by specifying
the goals in terms of input/output relations and its control structure. The
control structure represents the decomposition of the task and procedural
ordering on the inferences.

KADS provides the general framework for the analysis of expert problem

solving and the development of knowledge-based systems. The next sections

describe two approaches that leverage the KADS methodology in planning.

3.1.1. The Framework for Representing and Analyzing Planning Methods
(Valente 1995; Barros, Valente et al. 1996; Benjamins, Barros et al. 1996)

describe application of the CommonKADS methodology to model-planning

31

problem solving. The authors propose a problem-solving framework that can help

in constructing planning applications. Using this framework the planning problem

solvers can be configured from reusable components rather than built from
scratch. The library of reusable components is based on the CommonKADS
analysis of some well-known classic planners (e.g., STRIPS, NONLIN).

There are three interconnected groups of components in the library:

. The first group is used to specify how domain knowledge is structured by the
methods. The typical knowledge roles used in problem solving are identified;
these include dynamic roles (current state, goal, plan, etc) and static roles
(state description, plan structure, etc.);

o The second group is used to specify the basic methods used in composing a
planning reasoning strategy and a task-method decomposition structure. The
Propose-Critique-Modify method is recognized by the authors as a top-level
problem solving method for planning and is decomposed into three tasks:
propose, critique, and modify, which are decomposed further until primitive
methods are reached;

. The third group is used to specify the set of problem-solving method features
that can be used to determine the applicability of the method to the domain of
a problem.

The problem solving components are stored in a tool called TINA (Tool in

Acquisition). This tool helps to find an adequate configuration capable of solving

the specific problem is determined by matching the application domain to the

assumptions of problem-solving methods. On the other hand, the tool can be

32

used to generate specific domain requirements, given a particular planner. The
planner is decomposed into its constituent problem-solving methods, and the
assumptions for each method refer to domain requirements.

The TINA tool gives conceptual help in selecting a problem-solving
method adequate to the application. However, the offered guidance is focused on
the domain models, rather than inference models or control knowledge used in
planning.

3.1.2. KADS Based Models for Knowledge Based Planning

One of the key components of CommonKADS is the library of generic
inference models, which can be applied to the task of a specific type. In the
KADS community it is a common practice to construct such inference models
based on existing Al systems. In the planning domain, the KADS methodology
was applied to the two well-known systems: ONCOCIN (Tu, Kahn et al. 1989)
and O_PLAN (Tate, Drabble et al. 1994).

ONCOCIN is a planning system that performs cancer-chemotherapy
administration. The skeletal plan refinement implemented in ONCOCIN was
remodeled using a layered KADS approach to create K-ONCOCIN (Linster and
Musen 1992). The KADS tool was used to remodel the existing system rather
than as a tool in knowledge engineering. K-ONCOCIN adopts the task structure
and problem-solving methods implemented in the original system. The goal of
Linster and Musen’s work was to evaluate the KADS approach on a real-life

application. The K-ONCOCIN model was used to analyze and understand the

33

strengths and limitations of the KADS approach. Unfortunately, the authors failed
to show how the preformed analysis could be reused to create new KBS.

Another example of a CommonKADS application in planning is the
analysis of an HTN-based O-Plan system (Kingston, Shadbolt et al. 1996). The
domain knowledge representation used in O-Plan corresponds closely with the
domain knowledge level of the expertise model in CommonKADS. Consequently,
the authors’ efforts were focused more on deriving generic inference and task
models. The paper points out that these models provide the most assistance to a
KBS developer. The generic inference structures for knowledge planning based
on O-Plan analysis was used to develop a real-life planning application - the
system for management of search and rescue operations.

The research described in this section can be characterized as a system-
driven approach to the analysis of planning problem solving. That is, to identify
generic problem-solving strategies, the KADS analysis is being performed on the
already developed Al systems. Alternatively, the domain driven approach where
a specific problem solving knowledge is acquired from a domain expert and a
viable system is created from scratch can provide valuable insights on planning
problem solving.

3.2. PROTE GE 4!

PROTEGE-ll (Tu, Eriksson et al. 1995) is a methodology and a tool for
generating knowledge acquisition tools. The approach relies on a library of
reusable basic problem-solving methods called mechanisms. Mechanisms can

be configured into more complex methods using a method specification

language. Methods are used for solving tasks, which, in turn, are represented
through their input and output. The method either is recursively decomposable
into a set of subtasks or is a basic method. Each of the subtasks may have more
that one method for its solution. The task decomposition in PROTEGE-ll is
similar to the KADS task-method decomposition. The difference form KADS
approach is that in PROTEGE-ll, mechanisms contain no computational
assumptions about the procedure or the required knowledge.

The PROTEGE-ll approach uses three types of ontologies:

0 Domain ontologies, which model concepts and relations in the problem
domain;

. Method ontologies, which model concepts related to the domain-independent
problem solving methods: input and output, control structure, etc.;

. Application ontologies, which combine domain and method ontologies for
particular applications.

The PROTEGE-ll approach was initially developed to implement skeletal-
plan refinement for designing molecular biology experiments (Friedland and
lwasaki 1985). The skeletal plan refinement was used in several decision support
systems in the medical domain. T_HELPER (Tu, Eriksson et al. 1995) is an
example of a skeletal plan refinement that was used to assist clinicians in the
management of patients infected with HIV.

3.2.1. Skeletal Plan Refinement

Skeletal plan refinement is a problem-solving method that generates

appropriate plans of action by instantiating and refining the predefined generic

35

plan schemata. In practice, the method is used to instantiate a skeletal plan at

multiple time points; therefore, it is called episodic skeletal plan refinement

(ESPR) (Tu, Kahn et al. 1989). Based on a given case, the ESPR method can

generate an execution plan at any given point in time. As time passes and more

data becomes available, an updated execution plan appropriate for the new time
point is generated. Hence, the problem solver that uses ESPR may generate
execution plans each time decisions need to be made.

The ESPR method is decomposed into three main subtasks:

. Proposing plan actions based on a high-level skeletal plan. This task is solved
by the instantiate-and-decompose method, which, in turn, is decomposed
further;

. Identifying problems. The knowledge-based temporal abstraction method is
used to detect temporal inconsistencies;

. Modifying the plan actions based on identified problems. The situation-based-
revision method is used to modify the plan.

Task decomposition implemented in the ESPR method is similar to the
KADS-based decomposition proposed in (Benjamins, Barros et al. 1996), where
the planning process is described as propose-critique-modify.

PROTEGE-ll, similar to the KADS approach, views knowledge as being
independent from its intended use. Knowledge is represented using domain
ontologies, while problem-solving methods are represented separately in the
method ontology. The mapping between the domain data and problem-solving

methods is considered a part of the system development process. However,

36

PROTEGE-ll provides a/the means for explicit encoding of domain-dependent
control knowledge in the control model, which separates it from the KADS
approach. This ability allows leveraging the application domain specifics during
the problem-solving process.
3.3. EXPECT Framework

EXPECT (Swartout, Gil et al. 1999; Valente, Gil et al. 1999) is a
framework for developing knowledge-based systems using self-organized
method libraries. EXPECT’s knowledge base includes:

. Domain knowledge: Domain ontologies and domain facts are represented
using semantic networks;

. Problem solving knowledge: The methods are specified through the capability
description (description of problems that can be solved) and method body
(procedural description of steps for achieving method capability).

EXPECT uses case grammar-style formalism to describe method
capabilities and problem-solving goals. This formal specification allows:

. Building libraries of problem-solving methods that are self organizing;

. Creating a problem solver for a specific task automatically by matching the
goals to description of the methods in the library.

The generation of KBS in EXPECT starts with an initial high-level goal of
the problem solver. This goal is used to find the method in the library with
matching capabilities. The method is then instantiated. If the method’s body

contains sub-goals, the process described above is repeated.

37

3.3.1. Plan Evaluation and Critiguing
(Blythe and Gil 1999) describe the design and implementation of the

system that was developed in EXPECT for plan evaluation and critiquing. The
goal is to perform a domain-independent analysis of the plan structure and the
use of resources. The system was applied in the military domains of air-
campaign planning, Army Course of Actions planning, and Military Transportation
Logistics. The domain knowledge is used only as an input to the problem solvers
in the form of plan and world descriptions, and requirements to estimation. The
problem-solving knowledge is domain independent and explicitly encoded using
the EXPECT procedural language. The system contains a set of small, problem-
solving methods and four ontologies:
. An ontology of planning knowledge is used to specify the plans to be
evaluated;
. An ontology of resources captures different kinds of resources used in
planning tasks;
. An ontology of plan structure specifies relationships between plan
components;
a An ontology of evaluations describes how the evaluation of a plan can be
represented.
The ontologies developed in the system have the potential to be reused in
other applications. In fact, (Valente, Gil et al. 1999) report that the ontology for
representing planning knowledge is being used in the development of the KBS

for generative planning.

38

The EXPEXT approach is similar to the other task specific approaches
described previously: the libraries of problem-solving methods are being
developed based on a functional description of the methods. Unlike other
approaches, the EXPECT framework offers a formal scheme based on case
grammar to describe the capabilities of problem-solving methods. This
framework allows the construction of self-organizing libraries and supports reuse.
Despite the ambitious goals of the EXPECT project, it is difficult to judge its
scalability, since no big problem solvers have been developed yet. It is possible
that unambiguous mapping from an informal task description to a formal
specification can be very difficult or even impossible for the large, complex

problem-solvers.

3. 4. Generic Tasks
The described TSA approaches provide support for the analysis and

description of problem-solving behavior in terms of generic inferences.
Meanwhile, there are certain benefits in using problem-solving components of
larger granularity. Skeletal planning in PROTEGE (Tu, Kahn et al. 1989),
diagnosis (Benjamins 1993), and planning (Barros, Valente et al. 1996) in the
Common KADS framework serve as an example of such task structures.
However, the actual reuse of problem-solving knowledge in Common KADS and
other TSA architectures is realized largely at the level of basic inferences.

On the other hand, the Generic Task (GT) methodology (Brown and
Chandrasekaran 1989; Chandrasekaran and Johnson 1993; Chandrasekaran

and Josephson 1997) was developed specifically to capture large granules of

39

problem-solving knowledge. Capturing such large chunks eases the initial stages

of knowledge acquisition by providing the knowledge engineer with a set of

templates that fit a wide range of domain problems. In addition to providing

guidance in method selection and a conceptual framework for implementation,

the GT approach includes reusable and executable task-level shells that

simultaneously support KA and system implementation. A number of GT core

tasks/methods have been identified:

Hierarchical Classification embodies the identification of a particular situation
as an element in the hierarchy of related situations and their abstractions
given the description of the situation (Bylander and Mittal 1986).

Routine Design (Brown and Chandrasekaran 1989; Chandrasekaran 1990)
and its generalization Multiple Routine Design (Kamel, Sticklen et al. 1994)
involves generating one or more (in the case of Multiple Routine Design)
description(s) of the design by sequentially selecting the values of parameters
to fill out a predetermined design template.

Structured Pattern Matching matches a set of hypotheses against a set of
data that describes the problem state and determines which, if any, of the
hypotheses are suitable (Bylander and Goel 1988).

Functional Modeling (FM) captures role-oriented causal knowledge about how
a “device in the world works.” Unlike the other GT base modules, Functional
Modeling does not have a prescribed inference strategy, although the most

explored use of FM has been to support a type of qualitative simulation.

40

(Sticklen and Chandrasekaran 1985; Chandrasekaran 1993; Hawkins,
McDowell et al. 1993).

. Abductive Assembly of Explanatory Hypotheses constructs the best
explanatory hypotheses for a given situation based on the number of
hypotheses associated with a degree of belief and offers to explain a portion
of the data (Josephson and Josephson 1994).

The GT approach has been applied to develop numerous knowledge-
based applications, most of them were focused on the solutions on design and
diagnosis problems. However, a number of developed applications were devoted
to implementing tasks in the planning domain. “Routine design’ is one of the
generic tasks that was leveraged in the planning applications. The next sections
describe this task in more detail and provide examples of its use to solve
planning problems.

3.4.1. Routine Design

Routine design (Brown and Chandrasekaran 1989) was identified as a
class of design problems with a well-understood and well-structured nature of the
design procedure. The routine design problems are “routinely" encountered
design situations where both the types of knowledge needed and the problem-
solving strategies are known in advance. Once the set of initial input
requirements is given, the designer knows what design attributes must be
specified from past experience and also knows how the final design will look and
operate. Well-defined design choices characterize each stage of the design

process. While the methods used to achieve the design are predefined, the

41

specific course of action necessary for any particular instance of the problem is
not necessarily known in advance, and the result of a routine design can be a
novel design.

Based on the GT analysis of routine design, Brown defined a problem-
solving architecture and representational language called DSPL (Design
Specialists and Plans Language) (Brown and Chandrasekaran 1989). DSPL
supports the development of knowledge-based domain applications for routine
design tasks. Knowledge-based systems developed using DSPL were able to
generate a unique “optimal” design that satisfied input requirements. However,
DSPL does not support the generation of multiple design alternatives that meet a
common set of specifications, which is preferable in many cases. To overcome
this flaw, the language MDSPL (Kamel, Sticklen et al. 1994) was created to
support Multiple Design. The MDSPL inference strategy provides the possibility
of generating multiple designs. The Multiple Design approach uses the same
types of problem-solving agents that are used in Routine Design; therefore, the
following description of the Routine design problem solving architecture is valid
for Multiple Design as well, unless specifically stated.

Knowledge in Routine Design. There are four types of knowledge used
in Routine Design:

. Knowledge about the decomposition of the design problems into a hierarchy
of manageable sub-problems that have minimal design interactions;
. Procedural knowledge in the form of design plans;

. Knowledge about the selection of appropriate design plans;

42

. Knowledge for adjusting the design when a constraint is not satisfied.

The Routine Design is based on the hierarchy of cooperating specialists,
each responsible for an identified part of a complete design. A design specialist
represents a particular piece of design knowledge about some part of the overall
design. The higher-level specialists in the hierarchy typically represent the more
conceptual aspects of the design, whereas the lower-level specialists represent
the more parametric aspects.

In Routine Design, each specialist follows one of a set of pre-specified
plans. Plans contain the problem-solving actions to be followed and are defined
at the time of building a design system. Each plan is associated with a sponsor,
which is typically in the form of a pattem matcher that has the necessary
knowledge to examine the current status of the design and assess the
applicability of the plan. A selector chooses the appropriate plan, according to the
input data received from sponsors. The plan may contain invocations of other
specialists, executing design tasks, or checking data constraints. The design task
consists of steps needed to specify values for the attributes associated with the
design goal of the specialist. In failure situations (e.g., constraints are not
satisfied) the redesigners are invoked, they examine the failure conditions and
prescribe corrective actions or backtracking.

Control Stratggy In Routine Design. Control in the Routine Design
proceeds downward from the top specialist in the design hierarchy. Beginning
with the upper—most specialist, each specialist follows successive steps:

0 Plan selection;

43

. Refinement and critique;
. Redesign.

A plan selector completes plan selection. In Routine Design, a single plan
is selected, and another plan will be attempted only in the case when the
selected plan fails. In Multiple Design, all applicable plans will be executed.
During execution, the design actions specified in the plan are performed. This
may include design refinement steps (computing and assigning specific values to
attributes, invoking sub-specialists to accomplish sub-problems of the design) or
critiquing steps (checking constraints). If a failure occurs during plan execution,
redesigners handle it.

One could see planning as a design activity where planning goals
correspond to design specifications and the plan corresponds to the resulting
design. In many application domains, planning tasks follows well-understood
structured tracks. In such cases, planning could be seen as routine design. The
following section contains examples of planning problems solved through the
application of the routine design approach.

3.4.2. Routine Design Applications in Planning

Mission Planning. The routine design approach was applied in the
system called MPA (Chandrasekaran, Josephson et al. 1987) - a knowledge-
based system for planning in the domain of offensive counter air mission. The
problem of tactical mission planning is decomposed into subproblems, which can
be solved fairly independently, with the exception of resource contention

considerations.

44

The MPA top specialist produces a mission plan based on mission
requirements; it relies on two sub-specialists: base and aircraft. The base
specialist is responsible for selecting an appropriate base using data about the
geographical position of the target, while the aircraft specialist selects an aircraft
type and number based on information about threat types and weather conditions
at the target. The aircraft specialist has three sub-specialists, one for each of
three aircraft types known to the MPA system. Each of these specialists can
select an appropriate configuration for its aircraft type.

The MPA system is able to select the appropriate type and configuration
of aircraft, compute the probability of destruction for the single aircraft, and
determine the number of aircraft to achieve the required probability of
destruction.

Crop Management. Neper Wheat (El-Sheikh, Sticklen et al. 1996) is an
expert system suite developed to support the management of irrigated wheat.
The system combines the GT approach for the planning of wheat management
and a numerical simulation model to predict the crop’s behavior given the
farmer’s circumstances and generated crop management plan.

The planning module in Neper is based on Routine Design problem
solving. It consists of a number of specialists responsible for various aspects of
wheat management: Varietal Selection, Planting Date Selection, Strategic Pest
Management, Pre-plant Tillage, Planting Parameter, Irrigation and Fertilizer
Regime, and Harvest Management. Some of these specialists generate their part

of the solution based on their own knowledge (e.g., Varietal Selection specialist

45

and Planting Date specialist), while others evoke sub-specialists to solve the
problems (e.g., Pest Control Module, Planting Parameters module).

The system is being used successfully for the managing the wheat crops
in Egypt, and was also adapted for rice crop management in Thailand.

Manufacturing Process Design. Socharis2 (Martinez, Lukibanov et al.
1999; Lukibanov and Martinez 2000) is an intelligent manufacturing system that
generates a family of applicable fabrication methods from a conceptual
description of a composite assembly. The system is an integration of GT-based
modules performing three major tasks: creating a skeletal manufacturing plan,
deciding and detailing a technological process for each planning step, and
ranking the generated technological processes.

Socharis employs knowledge about nine generic manufacturing
technologies: hand lay-up, spray-up, resin transfer molding, compression
molding, resin injection molding, resin infusion, filament winding, extrusion, and
pultrusion. The hierarchical classification task is applied to select the appropriate
technological processes for each component in the assembly; after that, a
multiple routine design approach is used to refine the selected technologies to
satisfy the input requirement to the manufactured part. The following paragraph
describes the routine designer that performs the refinement of the Hand Layup
manufacturing process.

The top specialist for Hand Layup uses a number of sub-specialists:

Curing, PrepregWet, Tooling Material, etc. The Curing specialist establishes

46

curing parameters: curing pressure, curing temperature, and method of curing.
The Curing specialist invokes the Cun'ng type specialist that chooses a relevant
curing method (autoclave, press, microwave, oven, or room temperature),
depending on functional requirements, production rate, part thickness, and part
size. Then, the Curing specialist determines curing pressure and temperature
based on the previous result and given resin type. The PrepregWet specialist
uses the resin type, functional requirements, and production rates to estimate the
form of the materiaVresin system (prepreg or wet laminate), and also looks at
the possibility of post curing operations. Next, the Tooling material specialist
selects an appropriate tooling material using production quantity and fiber type as
discriminators for the choice.

The capabilities of the Socharis system were tested by generating sets of
manufacturing plans for both. real-life problems and specifically formulated
challenges. The use of multiple routine design allowed the generation of design
alternatives that can be estimated using a suite for design evaluation, which is a
part of the system.

It was shown by several successful applications that Routine Design and
Multiple Routine Design techniques could be successfully used to perform
knowledge-based planning in various domains. The advantage of using the RD
root in the inherent characteristic of the GT approach is a use-oriented
knowledge representation, which allows performing efficient knowledge

acquisition. In addition, explicit representation and use of domain control

 

2 2 “Socharis” comes from the Greek variant of the name of the ancient Egyptian

47

knowledge implemented in GT architectures provides a mechanism for effective
problem solving.

Another advantage of exploiting the RD methodology for solving planning
problems is that the propose-critique-modify strategy -- a powerful planning
method — is enforced by RD’s control structure. Task analysis of a planning
problem performed in other TSAs frameworks (KADS, PROTEGE) confirms that
a planning task is covered by the structure of the propose-critique-modify
method. However, other TSA approaches do not offer off-the-shelf task-types
that will support generalized knowledge-based planning, while RD (MRD)
language provides explicit means to implement this task.

Nevertheless, the Routine Design approach falls short in several aspects
related to planning. The output of the RD problem-solver is usually in the form of
a set of parameters; whereas, the desirable output for a typical Al planner would
be the ordered sequence of parameterized steps. Consequently, the current
implementation of the MRD shell assumes that the structure of the plan is fixed
and unchanged, which is not always the case.

3. 5. Conclusion

This chapter outlined prevalent task-specific approaches with their relation
to planning problem solving. These approaches can be divided into two groups
based on their position toward knowledge representation. KADS, PROTEGE,
and EXPECT advocate a use-independent domain knowledge representation;

whereas GT has task-specific ontological commitments. Central to GT is the

 

god Seker, a patron of craftsmen.

48

hypothesis that “the knowledge should be represented differently according to its
intended use” (Chandrasekaran 1986). While this mode of knowledge
representation can lead to duplication in the knowledge stored, it also results in
more efficient problem solving, since the knowledge in each instance is
represented in a form most suitable for its immediate use. Moreover, such a use-
oriented representation supports more effective transfer of human problem-
solving knowledge to a system’s representation.

Both groups of approaches address problems of knowledge
representation and knowledge acquisition in planning systems. In an effort to
facilitate the knowledge acquisition process, each of the approaches in the
former group developed sets of knowledge acquisition tools (Knowledge
Workbench in KADS or ProtegeWin in PROTEGE). These tools enable the
system designer to develop task-independent domain factual knowledge
ontologies (or domain ontologies) and populate planing knowledge bases with
rules that are based on these ontologies. Developing such ontologies capitalizes
on the reuse of knowledge that, once encoded, could be reused by different
applications. However, the problem of translating a weak knowledge
representation in the robust and effective knowledge bases may be as hard as
the initial knowledge acquisition.

On the other hand, the processes of knowledge acquisition and system
building are intertwined in task-specific approaches such as Generic Tasks. Such
simultaneousness in the system building process — coupled with an adequate

knowledge representation and effective inference strategy - could definitely

49

facilitate the development of knowledge-based planning systems. Unfortunately,
the planning task was only vaguely addressed in the GT area through tailoring
the Routine Designer to a specific, limited set of planning problems. This
dissertation is aimed to expand the application of GT methods to cover a broader

range of planning tasks.

50

4. PROBLEM DEFINITION

The major topic of this dissertation is planning problem solving, in
particular, the development of knowledge-based systems that perform planning
problem solving. In studying a specific type of problem solving activity, a number
of approaches can be pursued. One of the possible approaches would be to
analyze the existing methods from a knowledge level perspective in order to
understand which methods are the most advantageous in given situations. For
example, the KADS planning framework attempts to facilitate the application of
previously developed planning methods to a new planning problem by analyzing
the assumptions about problem space.

On the other hand, the issue of knowledge-based application development
can be addressed by analyzing the process of problem solving that experts
perform. Such an analysis often results in the development of knowledge
structures that are inherent to the specific task and, hence, are convenient for
mapping the expert’s knowledge into a KBS. This alternative approach was
pursued by the GT school and resulted in the development of knowledge
architectures for tasks such as classification and design. The GT methodology
will be applied 1) to analyze domain and control knowledge used in planning
problem solving by domain specialists and 2) to propose a methodology and a
knowledge architecture that will facilitate the implementation of planning systems.

This chapter gives a definition of the problem and describes the scope of

theoretical problems that are addressed in this dissertation.

51

4. 1. lnformatlon Processing Used in Planning
Planning is a complex activity that covers a wide variety of problems

ranging from planning everyday, mundane activities to military logistics planning.
In general, the search space for real-life planning is extremely large, and domain
expert knowledge is used to facilitate the solution generation process. No single
method exists that can be used for planning. Commonly, the knowledge-intensive
planning activity is decomposed into a number of different processes, each
contributing to a final plan. Each of the processes operates with specific types of
domain knowledge, and the inference strategy and can be characterized by
unique information processing. Some of the commonly used processes were
described in previous chapters; the following is a short summary of these
processes:

. Constraint propagation method limits the knowledge used to generate the
solution to operations allowed in the domain and the set of the constraints.
The problem-solving process can be viewed as a form of problem space
search, where constraints are repeatedly applied to converge to a set that
satisfies the constraints. (See for example (Stefik 1981; Stefik 1981 ))

. In Case-based planning, the knowledge consists of the case library of
previous solutions, indexing criteria, and design modification knowledge.
Case-based planning works by analyzing the goal, retrieving a previously
generated plan that satisfies similar goal, modifying this plan to satisfy the
goal at hand.(See for example (Hammond 1990))

. Task decomposition approach uses the knowledge of how to decompose a

more complex goal into simpler ones and how to compose the solutions of the

52

sub-problems to achieve the initial goal. In this approach, the task
decomposition rules are applied iteratively until primitive steps are reached.
During this process, the plan is generated gradually from more general to
more specific levels of granularity. (See for example (Sacerdoti 1975))

o Skeletal Planning uses precompiled problem-solving scenarios to generate
initial plan skeletons. Given a goal, the plan skeleton is established using one
of the problem-solving scenarios, then the plan skeleton is detailed to satisfy
the requirements.(See fpr example (Tu, Kahn et al. 1989))

The methods enumerated above can be considered building blocks in the
overall functional architecture of planning. They are organized in order from less
knowledge intensive to more knowledge intensive. The use of expert knowledge
usually limits the amount of problem space search required to produce a solution.
The more knowledge that is available, the more likely that problem space
reduction can be achieved. Methods such as skeletal planning allow avoiding
search by applying precompiled problem-solving scenarios. It is important to note
that in each case the dominance of a specific problem-solving process relies on
the availability of the needed knowledge.

To solve a specific problem, usually the combination of several problem- -
solving processes is used. Such a combination will be referred to as the
problem-solving architecture. The same problem-solving architecture can be
used to solve a class of problems if they have similar types of knowledge
available. The major goal of this research is to develop a common problem-

solving architecture for a specific class of planning problems. The following

53

section defines the class of planning problems which are the focus of this
dissertation research in the context of other classes.
4.2. Classes of Planning Problems
The following informal classification of planning problems is based on the
role that expert knowledge plays in the generation of a solution. Each class is
characterized by the nature of available problem-solving knowledge.

Consequently, each class is associated with a set of problem-solving processes

that can be used to solve tasks that belong to that class.

. Class 1. Planning problems will be considered Class 1 if 1) the effective
domain decompositions are not known, and 2) the available domain
knowledge is limited to a set of allowable actions and constraints. An example
of such a problem is maze traversal, where the knowledge about the structure
of the maze is not available up prior to “running” the plan.

. Class 2. Class 2 planning problems are those which have known problem-
solving task-reduction rules However, the overall problem-solving process is
not structured. Many game-playing problems (bridge, backgammon, etc)
serve as examples.

. Class 3. Problems where the problem-solving process is well structured,
while the resulting plan might exhibit flexibility, are considered Class 3.
planning problems. Examples of such plans are cooking recipes and travel
itineraries.

0 Class 4. Class 4 problems are those in which both the problem-solving

strategy and resulting plan have a fixed architecture. In this case, the solution

54

is usually in the form of plan parameters that then fit into the predefined plan
schema. An example of such a plan could be the parameterization of crop
management variables in a predefined general plan.

This classification provides a basis for determining the adequacy of
previously discussed planning methods in relation to a specific problem. The
sufficiency of the planning method in each particular case can be determined by
comparing the problem-solving knowledge available to the representational
capabilities of the planning method. For example, the problems of Class 1 are
usually solved by universal search techniques or constraint propagation
methods. Despite the fact that these methods are not always computationally
effective, these methods provide the most adequate mechanism for representing
problem-solving knowledge.

The universal search methods that solve problems of Class 1 could also
be employed to solve Class 2 problems. However, these methods do not take
advantage of available problem decomposition and, therefore, are not as
effective as HTN planning, which leverages task reduction schemata. In turn, the
HTN approach could be applied to Class 3 and Class 4 planning problems; yet,
HTN planning does not leverage all the available problem-solving knowledge.

Currently, the majority of planning methods are developed to handle the
problems of Classes 1 and 2. In contrast, most of the everyday planning
problems should be related to Classes 3 and 4 that are more knowledge
intensive. In fact, most industrial problems belong to Class 3 or Class 4. In

addition, many problems in Class 2 have subproblems that belong to Classes 3

55

or 4. Hence, a need exists for problem-solving methods that are tailored
specifically for these classes. The Routine Design approach was proposed
specifically as an architecture for solving Class 4 problems. Class 3, however,
has not been addressed specifically; typically, the problems associated with
Class 3 are largely solved through the application of HTN techniques. The HTN
approach does not have explicit an means to represent existing compiled
problem-solving scenarios; instead, they are hidden either in an inference engine
or cleverly formulated methods within a flat knowledge base. Therefore, even
though the HTN approach is applicable to Class 3 problems, a problem solving
architecture tailored specifically for Class 3 of problems can be of high leverage
in planning.
4.3. Problem Statement

The taxonomy of planning problem classes points the way to a hole to a
current planning approaches; there is no methodology for Class 3 planning
problems. The problems of Class 3 are characterized by well-understood and
well-structured problem-solving scenarios. Despite the fact that such problems
have an explicit control structure, they are currently solved largely through the
application of the planning methods based on universal, domain-independent
knowledge structures. These knowledge structures do not support the
representation of the task-specific domain knowledge such as planning
scenarios. The ability to represent this kind of planning knowledge explicitly can

provide a valuable platform for to developing domain applications.

56

The above provides a motivation to concentrate the research efforts on

Class 3 planning problems and apply the generic task viewpoint to the

development of a problem solving architecture for Class 3 problems. Given the

GT nature of such an architecture it can serve as a foundation for building a

framework that supports planning system implementation through task analysis,

knowledge acquisition, and problem solving.
In order to reach this, now refined, goal, the following goals should be
acheved:

1. To perform a GT-based task analysis of Class 3 planning problems. This
analysis should include task-subtask analysis as well as task-level analysis of
the participating problem-solving specialists.

2. To develop a knowledge-level architecture of the task-subtask decomposition.
This includes a definition of information processing as well as an inter-
specialist integration architecture.

3. To implement a software tool in support of the developed methodology.

4.4. Conclusion
To summarize the problem statement it is necessary to list the features of
the principal deliverable of the dissertation research: a planning framework
capable of decomposition and solving Class 3 planning problems.
This framework should encompass the following features:

0 Support of knowledge acquisition and problem solving. The GT

paradigm implies knowledge-level characterization of the task, identification of

knowledge roles, modular decomposition of the task into sub-tasks,

57

description of the task control structure, and explicit control knowledge.
Following these principles and implementing them in the framework provides
a definitive support for knowledge acquisition as well as development of an
explicit representation of control structures used in problem solving.
Modularity. Following the proposed approach the framework should exhibit a
natural modularity: the methods are to be organized within specialists, where
every specialist from the hierarchy can be replaced with another completely
different specialist that performs the same task. This allows the distribution of
knowledge acquisition and problem solving among different specialists, as
well as supports the reuse of other planning systems created in this
environment.

Support of multiple levels of abstraction. The approach is based on an a
priori known hierarchical organization of domain planning knowledge. Hence
the specialists on the higher levels of hierarchy are indeed more abstract than
those below them. The framework should provide means of and vocabulary

for describing the planning process at multiple levels of abstraction.

58

5. KNOWLEDGE ARCHITECTURE FOR PLANNING

The previous chapters describe knowledge-based planning problem and
the set of knowledge-based problem-solving methods which have been applied
to solve it. This chapter is an introduction to a framework that leverages a
general GT viewpoint for the implementation of knowledge-based planning
problems of Class 3 (see Chapter 4.) This chapter is in two parts as follows:

. The first part describes a proposed planning task structure. This description is
based on observation and analysis of human expert problem-solving process.
The task structure incorporates a range of subtasks and methods for each
sub-task; the goal is to lay out the relationship among tasks, applicable
methods, and knowledge requirements for these methods.

. The second part proposes a problem-solving architecture based on the task
analysis. This architecture focuses on detailed analysis of types of knowledge
and control structures, and provides a road map for implementation of the
GT-based planning shell as well as for the knowledge acquisition required to
develop planning domain applications.

The discussion in this chapter focuses on conceptual architecture and is

not concerned with implementation issues, which will be discussed later.

5. 1. A Task Analysis of Class 3 Problems
Several authors have discussed the structure of the general

planning task (Tate, Drabble et al. 1994; Valente 1995; Barros, Valente et al.

1996; Benjamins, Barros et al. 1996). This work revealed a great number of

59

possible methods and subtasks used in planning. Due to this multiplicity, it is
unfeasible to propose a generic problem solving architecture for all four classes
of the planning problems. Alternatively, by following the ideas developed in the
TSA community, it is more reasonable to develop shells that support the
implementation of simpler planning tasks which later could be combined in an
integrated system for a specific domain problem.

Similar to a specialized software package that targets a specific problem
or a specific set of problems. For example, JavaMail API is used for writing e-
mail applications and Servlet API supports writing server-based applications by
combining them together it is possible to write a server-based email application.

Because the proposed classification of a planning problem relies on the
nature of the problem-solving knowledge rather then on the problem statement,
the infonnation-processing task for Class 3 problems does not differ from a
general planning taska. Consequently the structure of a Class 3 task at the top
level is the same as other types of planning tasks. A Class 3 task could be
described through high-level problem-solving methods that are termed as
propose-critique-modify (PCM) (Fig. 6). That is, there are three basic tasks
inherent to Class 3 planning problems: (i) propose plan, (ii) critique plan and (iii)
modify plan. While sharing a top-level task decomposition, different classes of
planning problems impose limitations on the types of available knowledge and,

consequently, on the methods that can be used to realize the high-level tasks.

 

3 The information processing problem for planning can be stated as following:
given the goal and the state of the world generate the plan.

60

 

 

TASK
Planning

METHOD
Propose-critique-modify

SUBTASK SUBTASK SUBTASK
Propose Critique Modify

 

 

Figure 6 . Propose-Critique-Modify Method for Planning

5.1.1. Propose
The subtask of proposing plan refinement takes a set of data that

describes the goals, the state of the world, and the information about the plan
generated so far as an input. The methods that solve this task use the domain
knowledge to map part or all of the specifications to the partial or complete plan
proposals. Two alternative methods can be identified here: Goal-Achievement
Propose and Decomposition Plan Propose, both of these methods rely on well-
defined and well-structured problem-solving knowledge typical of Class 3
problems.

Goal-Achievement Propose selects an operator or a set of operators
whose effect includes the desired goal. This may include parametrizing existing
steps or patterns of steps. An alternative sub method for the Propose task

involves plan refinement through decomposition-planning-composition. Using this

61

 

method, the plan is built by breaking up the overall problem into simpler
problems, solving these problems, and then composing the global solution out of
the solutions for the sub-problems. This method has four sub-tasks: propose

decomposition, propose the order, planning, and compose the solution.

 

 

 

 

TASK
Propose
METHOD METHOD
Goal-Achieve Decomposition
Propose Propose
TASK TASK TASK TASK
Propose Propose Planning Compose
decomposition Order Solution

 

Figure 7. Propose Task
The Propose decomposition task selects an appropriate set of sub-

goals to substitute the initial goal. A number of alternative decompositions might
be available — in which case, a selection has to be made. Therefore the
realization of this task requires the knowledge in the form of d-9{d1,d2,d3,..., dn},
which represents the decomposition of task (I into simpler sub-tasks (d1, d2,
dn), and some additional knowledge that helps select an appropriate
decomposition.

When the decomposition is selected, one of the sub-tasks may be more

limiting than others and have to be solved before other sub-tasks are done. In

62

 

such cases, the ordering of the sub-problems in the decomposition is important.
If such ordering of knowledge is not available, the solution might require
extensive back tracking. Sometimes, it is possible to generate the ordering at the
run time. Noah (Sacerdoti 1975) is an example of a run-time generation of sub-
problem dependencies. Alternatively, Class 3 problem are characterized by well-
defined problem-solving scenarios; thus, each decomposition has a precompiled
order associated with it.

The task planning of the method Propose indicates the recursive nature of
planning problem-solving where the plan is built through an iteration of steps
from general to more specific levels. This task takes the sub-problems generated
by the previous steps as an input and passes the generated plans to the Solution
Composition. -

The task of composing the solution uses knowledge which is similar in
form to the knowledge used by the subtask of ordering sub-problems. The
knowledge is in the form of precompiled nonlinear networks with start and and
nodes, where intermediate nodes correspond to the sub-tasks used in the
decomposition. These networks reflect expertise on how the subparts of the plan
are related in time during plan execution.

5.1.2. 91m

The Critique plan task assesses the plan generated by the plan refinement
task. The assessment involves the analysis of the proposed plan to determine
failures and estimates the quality of the generated plan. One of the methods for

this task is the constraint propagation method. Following this approach, the

63

knowledge is represented in the form of conditions or constraints on the resulting
plan. The constraints may relate to the various characteristics of the plan, from
specification of the steps to the use of the assigned resources. Additionally, the
Critique task can be considered a “generalized version of diagnostic problem”
(Chandrasekaran 1990) that is a problem of mapping from a specific plan to
some estimation metric. This method relies on the knowledge about
dependencies between plan specification and its quality in relation to the other

plans.

5.1.3. Media
The Modify task is invoked for modifying the plan with respect to the result

generated by the Critique plan task. The modification can be accomplished
through backtracking: if the alternative decision points are generated during the
problem-solving process, it is possible to return to these points upon failure and
make an alternative choice from the finite list of generated options. In the
Propose refinement task there were several methods that involved selection;
consequently, there could be different types backtracking: selecting alternative
steps, modifying parameters, altering decomposition, etc. An alternative method
uses plan correction knowledge to analyze failures and prescribe a corrective
action. For example, incrementing the value of step parameter or adding

ordering.

 

 

 

Ch'ticp:

ring.

Goal -Achieve lbcurpoatim (Dammit! Dagmsis '
Propme Propme [1mm antim

TAS§ TAS< TAS( TAS(

Propose Piqaose Plating Carpose
dacmptsitim 0th Sdution

 

 

 

Figure 8. A Task Analysis of Planning Task of Class 3

5.1.4. A Control Strategy

 

Based on a task/method/subtask analysis of the Class 3 planning

task (Fig. 8), it is possible to define a control strategy for this class of planning
problems. Table 2 displays a strategy that specializes the method proposed in
(Chandrasekaran 1990) for general design problem solving. This control strategy
does not give a complete picture of the problem-solving process, because, in
reality, the control strategies are based largely on domain knowledge and are
specific to each application. However, specification of the high-level strategy

provides guidance for building a shell that supports the development of such

applications.

65

 

 

Specify the goal.

Identify the goal-achieve action. If successful, output the plan. If fail, go

to 3.

Identify relevant decomposition method.

For subtasks specified by decomposition method, build sub-plans in

the predefined order, repeating steps 1 through 4.

Compose the plan out of generated sub-plans using the composition

rule specified in the method.

6. Critique the proposed plan - if it is sufficient output it and stop.

7. For each detected insufficiency, backtrack to step 2 or apply plan
correction methods.

8. Go to stg 6.

”-5

PS0

9‘

 

Table 3. Control Strategy for Planning

5.2. The Problem-Solving Architecture
The task analysis proposed in the previous section can be employed to

develop the problem solving architecture (PSA) for a system that implements a
Class 3 planning task. Previous sections map the information-processing
requirements to the methods used in problem solving. The methods used for
proposing plan refinement through decomposition are specific to planning, and,
hence, they require the development of a task-specific knowledge representation
and control structures. At the same time, other methods (such as methods used
for plan critiquing or primitive step selection) are more generic and can be
implemented through reusing existing tools. The research described here follows
the GT paradigm and aims to extend the legacy of the Generic Task Tool Set
(Kamel, Lukibanov et al. 1997). Thus, the problem-solving architecture will reuse
other GT task structures to represent various portions of planning knowledge.
The proposed problem-solving architecture consists of a hierarchical
collection of specialists, where the upper levels of the hierarchy are specialists in

the general aspects of planning, while lower levels deal with specific tasks. The

66

 

hierarchical structure of the problem-solver reflects an expert’s understanding of
the organization cf the application domain. Each specialist in the hierarchy is
associated with a specific sub-task of the overall planning task of the knowledge
based system and has the knowledge required to solve this subtask. This section
describes the structure of planning specialists and discusses the problem-solving
process and the knowledge acquisition methodology which flow from this
problem solving architecture.

5.2.1. Specialists

Each specialist in the system has an assigned task and the problem-
solving knowledge necessary for generating plan(s) for this task. A specialist can
solve its task independently or can use the services of specialists located lower
in the hierarchy of specialists. The root specialist is responsible for the whole
planning problem. It can pass the control to its sub-specialist to generate parts of
the plan. Each of the specialists is a problem-solver by itself and its structure
should reflect the task-subtask architecture described in Section 5.1. Every
specialist solves the sub-tasks of propose plan refinement, critique, and modify.
In order to perform these tasks, specialists use Plan Generation Knowledge and
Plan Validation Knowledge. The Plan Generation Knowledge contains
prescriptions about how to generate the plan for a specialist’s task. Plan
Validation Knowledge is used to examine a generated plan for conflicts, such as
violated causality, inconsistent use of resources, and plan structure problems. In
the case of failed validation, the specialist can backtrack or use re-planning

knowledge to fix the plan.

67

Following the task analysis, the Propose Plan Refinement task can be
implemented by two alternative problem-solving methods: Goal-Achieve Propose
or Decomposition Propose. This dissertation identifies two types of specialists
that correspond with the problem-solving methods above:

. The first type solves its sub-problem by using local knowledge and will be
referred to hereafter as goal-achieve specialists.

. The other type uses goal decomposition knowledge to reference other
specialists below the hierarchy in order to generate the plan. These
specialists will be referred to as decomposition specialists.

5.2.2. Goal Achieve Specialists

The goal-achieve specialists main purpose is to design the plan steps.
The information-processing is performed as follows: given a planning task and
the current state of the plan, the specialist selects an appropriate configuration of
the step and sets the step attributes. The goal-achieve specialist is a leaf-level
specialist in the hierarchy and has no control over other planning specialists. It
does not use the decomposition approach; instead, it can design primitive actions
to achieve its goals. In fact, a goal-achieve specialist can only add steps to the
plan.

The problem solved by goal-achieve specialists is a design task. Any
design approach can be used to solve a general case. However, the architecture
proposed here is based on the assumption that the problem of defining the
planning step is a routine design task; therefore, the goal-achieve specialists will

be implemented as routine design problem solvers.

68

5.2.3. Decomposition Smpialists
Decomposition specialists generate the plans for the assigned goal by

decomposing it into simpler sub-goals and using specialists below the specialists’
hierarchy to generate corresponding sub-plans. The information processing
involves generation of the plan for a given goal and is based on the plan task and
the context of the previous planning decisions made by other specialists. The
compiled problem-solving knowledge is represented in the form of methods.
Each decomposition specialist has a collection of methods for plan generation
and is able to select an appropriate method. Every method represents a possible
decomposition of the goal. It includes the list of the sub-goals along with the
responsible sub-specialists, the constraints on the order in which the sub-goals
should be considered, and the knowledge of how the plan for the main goal
should be constructed from the generated sub-plans. Every method also has
local knowledge expressed in the form of constraints. Constraints are used to
check the applicability of the method to the particular situation and to validate the

ultimate success of method application.

5. 3. Discussion

5.3.1. ProblerrLSOIving
The problem solving proceeds top-down though the specialists’ hierarchy.

First, the top specialist decomposes the problem into the subtasks associated
with the specialists one level down the hierarchy. Then, each subtask is
decomposed further - this process recursively continues until only primitive tasks
are encountered. Each specialist contributes to the refinement of the plan during

decomposition and, consequently, helps build the task network. .

69

Although the construction of the task network is similar to that followed in
the HTN method, the problem-solving process is different. To achieve the newly
emerged goal with the HTN approach, the system considers all the task
decomposition methods from the knowledge base, checks the preconditions and
then applies the methods whose preconditions are satisfied. These methods are
always associated with a specific problem-solving context in which they are
applicable.

The description of a method’s context in HTN is supported solely by a
precondition formalism, generally a Boolean expression. In complex domains, it
is typically difficult to give a complete context description in terms of logic
formulas. This difficulty can result in excessive numbers of applicable methods.
And thus, the number of methods tried and rejected can be greater than
necessary. These leads to extensive backtracking caused by a multiple firing of
methods not appropriate for the current problem-solving context.

In contrast, the described planning framework provides a mechanism to
represent domain contexts through the hierarchy of specialists. If a situation
occurs in different contexts and the distinction between these contexts is
essential to the problem-solving process, then different contexts’ specialists
could be assigned to that goal. Such a separation of the knowledge provides a
simpler and more expressive way to represent the domain structure and the
underlying control knowledge. Conceptually, the advantage gained lies in the
cleaner one-to-one mapping between problem contexts and problem solving

process, as opposed to HTN many-to-one mapping between applicability

7O

predicates and problem solving methods. The context-based planning problem
solving activates a more limited set of specialists at any specific point of time.
Thus, the number of task decompositions considered at any time is considerably
smaller than in the conventional HTN approach. Hence, backtracking and
condition checking are also reduced. All of the factors together lead to
computationally more effective problem solving.

5.3.2. melgdfiAcguisition

The knowledge acquisition process is basically the elicitation of the
expert’s problem-solving knowledge and its incorporation into a knowledge-
based system. The acquisition of knowledge in the hierarchical planning
framework developed here is a twofold process:

1. Building the planning specialist hierarchy, and then
2. For each specialist, specifying the knowledge available to solve the task set
by the specialist.

Building the specialist hierarchy begins with the development of a task
hierarchy. This is based on task-subtask relations in various contexts of the
problem domain. The lower levels of the hierarchy contain more specific tasks,
while higher levels contain more general tasks. One task is the ancestor of
another task in the hierarchy if the decomposition of the former may include the
latter. Each task is associated with a specialist that contains knowledge for
achieving this task. The specialist hierarchy reflects an expert’s understanding of
the conceptual structure of the problem domain, organized, as typical for most

engineering designs, hierarchically.

71

The second step in the knowledge acquisition process is to represent the
planning knowledge of the top-specialist and of each sub-specialist recursively to
the lowest level of the hierarchy. Thus, the knowledge acquisition process is
guided by the framework constraints and directs the user toward building a
planning system via the chain of

Task => Specialist => Method

=>Subtask => Specialist => Method
to lower and lower specialists.

The relevance of the available knowledge representation to the task at
hand is a key issue in knowledge acquisition. The proposed framework supports
representation of the global control knowledge through the specialist hierarchy,
while local, context-related knowledge is concentrated in each specialist. This
provides more flexible knowledge representation than HTN, in which knowledge
is represented as a flat set of decomposition methods with no explicit
representation for global control knowledge exists.

Fig. 9 illustrates the taxonomy of the control knowledge in the proposed
framework. The hierarchy of specialists identifies the highest level of control
knowledge: during the problem-solving process, the control passes through
planning specialists from the top to the lower levels. Local control knowledge is
associated with each specialist. First, the method selection affects the flow, since
different methods will produce different sequences of actions. Second, the.
preconditions and the task order of each method influence the order of sub-

specialists’ initiations.

72

 

 

Control Knowledge

I I

Specialist Hierarchy Specialist's
Control Knowledge

|
I l

Method’s Method Selection
Control Knowledge

l
I I

Task Order Preconditions

 

 

incorporate changes to the knowledge base and detect knowledge bugs. These

Figure 9 . Taxonomy of the Control Knowledge

Another important faset of knowledge acquisition is the ability to

activities depend on the following:

indirect dependencies between tasks connected by the chain of methods are not
represented explicitly. Furthermore, the roles and the importance of the methods

in the problem-solving process are not reflected in the representation. This

The interdependencies between tasks - when changing a chunk of
knowledge, it is useful to know which other pieces of knowledge are affected
by the change, and
The role of the task in the planning process —knowledge of the method’s
contribution to the overall problem solving.

Methods in HTN reflect only local dependencies between tasks, while the

hinders the maintenance of large knowledge bases in HTN.

73

 

The proposed framework addresses the knowledge acquisition problems
enumerated above. The representation of specialists in hierarchies provides a
simple way to describe interdependencies between tasks: the task is dependent
on its descendants and is used by its ancestors. Therefore, if changes are made
to an associated method, then these changes can be traced to all of its ancestors
and descendants. The importance of the task in the planning process is reflected
by its position in the hierarchy: the more important the task is, the higher its
location in the hierarchy.

Both, HTN and the described here Hierarchical Planning approach are
knowledge-directed planning problem solving methods. However, by comparing
their problem solving strategies it is clear that HTN is closer to the pure search
methods than Hierarchical Planning. The reason for that lies in the structuring of
the domain knowledge: set of- rules in HTN versus the hierarchy of planning
specialists in Hierarchical Planning.

5.3.3. Amabilitv ISflS

The proposed hierarchical planning framework aims to tackle planning
problems, which have effective task decompositions, and for which the planning
process follows well-structured scenarios. These problems fall into Class 3 of the
proposed taxonomy of planning problems. In order to determine the range of the
applicability of this framework, two issues must be addressed:

1. The pervasiveness of Class 3 problems are; and

2. The utility of the proposed framework for other classes of planning problems.

74

This research is based on the empirical observation that the problems of
Class 3 are very common in everyday life. Especially in engineering domains,
solution techniques which rely on the domain knowledge directed search are
much more common than those which rely on general search.

However, some planning tasks cannot be brought under the hierarchical
structure in a direct and natural way and, consequently, the framework cannot be
used to solve these problems. Game playing in general is one of the examples
where the described approach cannot be applied. The reason for this is the
unpredictability of the situation and, as a rule, absence of well structured a priory
defined planning strategy. Machining or tooling is another example of a domain
where the described planning method would not work since the in many cases
machining operations are virtually independent from one another. Hence, there is
no structured generic strategy of setting the order of machining operations.

Nevertheless, there are two possible situations when the framework can
be used to generate partial solutions:

1. If there is a Class 3 sub-problem, then the framework can be employed to
generate sub-plans that can be used in the final solution; and

2. If the problem has a compiled problem-solving scheme that directs the
decomposition down but does not reach the bottom level (does not reach
primitive tasks), the framework can be used to generate approximate plans

that later would be refined using other means.

75

5.4. Conclusion
This chapter applied the task level analysis to Class 3 planning tasks.

Such an analysis provides the basis for a correspondent problem-solving
architecture. The elements of this planning problem-solving architecture serve as
a theoretical basis for the implementation of the knowledge-acquisition
framework. The next chapter discusses the implementation of this hierarchical

planning framework in a framework of the GT Integrated Tool Set.

76

6. A SOFTWARE TOOL FOR DEVELOPING PLANNING APPLICATIONS

6. 1. Introduction
The previous chapter describes the problem solving architecture for

planning problems of Class 3. It discusses The structure of problem solving
agents and the control regime were discussed. Based on the theoretical
framework developed, a Hierarchical Planner (HP), a representational shell
followed, that supports implementation, and use of specific planning applications.
The Hierarchical Planner has been implemented in SmallTalk in the VisualWorks
programming environment by extending the GT toolset and sharing some of the
architectural components with other problem solvers that are part of this tool set.
Additionally, HP uses other GT problem solvers within the toolset. This chapter
describes the organization of HP, structure of problem-solving agents, and
control regime employed to generate solutions.

To better understand the HP approach, it is helpful to describe in detail the
process of building the planning application step-by—step. As an example, the
planning problem from the house construction domain will be used. To make the
demonstration of the system specifics quickly approacheble, the problem used in
this chapter is considerably simplified. The following chapters will be devoted to
the development of the full-scale application for the problem from the composites

manufacturing domain.

77

6.1.1. Sample Problem
The goal is to generate a plan for building a house. The house consists of

a foundation, walls and a roof. The system will generate plans for two kinds of
houses: a Russian style but and an American cottage.

The user should select the type of house, wall materials, as well as the
soil type and location where the house will be built. The problem solver will
generate the plan. Possible plan steps include: dig a pit, pour concrete, insert
beams, make the wall frame, build walls, build the roof frame, build the roof. The
steps build walls, dig a pit, and insert beams need to be parameterized. That is,
the build walls step has the parameter WallThickness, the steps dig a pit and
insert beams have the parameter FoundationDepth. The rest of the steps are
assumed to be simple steps without parameters.

Building the problem solver for this problem will proceed through the rest
of chapter. The complete description of the problem solver can be found in
Appendix 1.

6.2. Problem Solver Components

Every Hierarchical Planner consists of three sub-components: Database,
Specialist Hierarchy, and Plan Container. Each of these components plays a
specific role in the problem-solving process. The Database manages all
situational data that describe a case and the interactions with the user. The
Specialist Hierarchy embodies plan generation knowledge distributed between
specialists. Plan Container serves as a medium for keeping track of the plan

being generated and also contains the final result of problem solving.

78

6.3. Database (DB)
The Database performs a three-fold role during the planning process:

It serves as a data storage. The database contains the values of attributes
that are used for decision making or are generated during planning.

It is used to represent knowledge about possible values of attributes. The
database allows the representation of constraints on the attribute values in
the form of a relation to other attributes or defined constants. These relations
can be used to test planning decisions as a part of the validation process.
Additionally, the Database stores the default values that can be used in
planning if the real value of an attribute is unknown

It is used for communication between planning agents. The DB defines the
language of communication by defining the types and possible values of
attributes. Additionally, it is used as a channel of communication, where the
decisions of one planning agent are stored in the DB and can be used by
other agents.

Some knowledge used during planning is not really part of the planning

process and is not actually planning knowledge, but rather, it is knowledge about

the values and types of objects used in planning. Such knowledge is stored in the

Database and is expressed as a constraint on values of variables used in

problem solving.

The Planning database is an instance of a Routine Design (Kamel,

Sticklen et al. 1994) database and provides a subset of capabilities found in an

instance of the intelligent database Generic Task. The database maintains

several types of variables: MultivaluedVar (a variable that could be assigned an

79

array of values), NumericVar (a numeric variable), OneOfVar (a variable whose
value is selected from a predefined list), StringVar (a string variable),
OrdinalOrderVar (a variable whose values can be put in a linear order), and
YesNoVar (Boolean variable) types. Each of the variables is defined as an input
or output variable, or both. The input browser displayed in the beginning of
problem-solving process shows the list of input parameters and allows the user
to input his or her values.

In the house construction example, the problem solver will use only one
type of variable: the OneOfVar variable, which is defined by a list of possible
values. Table 3 shows the list of variables with their legal values. The variables
HouseStyle, State, WallMaterial, and RoofMaterial are defined as input variables;
therefore, the input browser in the beginning of the problem-solver run will
prompt the user to define the necessary values. If values are not defined in the
input browser, the system will query the user at run-time as values are needed

for problem solving.

 

 

 

 

 

 

 

 

 

 

 

Parameter Name input/output Legal Values
HouseStyle input Russian hutl
American cottage
Location input Midwest / North /
Southeast
Soil input Dirt / Sand /
Wetland
WallThickness output Brick/ Board / L s
WallMaterial input Brick / Board / Log_s__
FoundationDepth output Full / Half

 

Table 4. Variables Used in the House Construction Problem-Solver.

80

6. 4. Specialists
The HP problem solver is based on the hierarchy of specialists. This

hierarchy can be viewed as analogous to a group of human specialists, where
each specialist is a supervisor of underlying specialists. When there is a task to
be solved, the supervisor can pass parts of this task to some of his or her
subordinates and ask them to solve it. In HP, the lowest level specialists are step
specialists - they generate the solution to their tasks by designing plan steps.
The higher level specialists are decomposition specialists — they can decompose
their tasks into simpler ones and assign the subtasks to the specialists one level
below in the hierarchy. Their presence in the hierarchy does not mandate their
involvement? in every problem-solving situation. While each decomposition
specialist has its own design set of sub-specialists, predefined during the
problem solver, the sub-specialists who actually will participate in the planning
process are chosen dynamically during problem solving.

A Specialist Hierarchy browser allows the user to create, edit, and explore
the hierarchy of planning Specialists. In the hierarchy (Figure 10), the
decomposition specialists are displayed in dark gray, the Step specialists are in
light gray. From the specialist hierarchy browser, the user can invoke the
individual specialist browser.

Figure 10 illustrates the hierarchy of planning specialists for the House
Construction problem. The highest level specialist (Build a House) decomposes a
task and distributes it among its sub-specialists (Build Foundation, Build Walls
and Roof) which decompose their task further. The lowest level specialists are

responsible for concrete steps that will be added to the final plan. The specialists

81

 

used in the Hierarchical Planner are discussed more specifically in the following

sections.

elation Interface

 

Figure 10. The Hierarchy of Specialists in House Construction Problem Solver

6.4.1. Decomppsition Swialist
The decomposition specialist is a basic building block in a Hierarchical

Classifier problem solver; it is a placeholder for planning methods and a selection
mechanism for choosing among different methods. Each planning method
represents a different way of decomposing the specialist’s task into subtasks that
can be handled by its subordinate specialists. The method selector is responsible
for choosing the method most appropriate in a given problem-solving situation.
The method selector is implemented using the Structural Matcher
(Bylander and Goal 1988) (see also Section 3.4) from the GT tool set. The

knowledge is represented in tabular form, where each row corresponds to a

82

 

 

specific method. The method is selected in the actual values of the problem
solver variables correspond to the values in the table. For example, in the House
Construction problem solver, the specialist Build Walls and Roof has two
methods: WithWaIlFrame and WithoutWallFrame. The method selector
displayed in Fig. 11 chooses the appropriate method based on the value of the
variable House Style. If the input variable HouseStyle is set to be RussianHut,
then the method WithoutWallFrame will be selected; otherwise, if the house style

is AmericanCottage then the method WithWaIlFrame will be selected.

 

 

 

Figure 11 . Method Selector for the Build Walls and Root Specialist in House
Construction PS.

The method in the Hierarchical Planner is defined by its precondition, task
order, and composition rule. A precondition is a set of constraints on the values
of the variables. Preconditions are used to represent a method’s local knowledge
about its applicability. For example, Fig 12 shows the method of WithWaIlFrame
where the precondition for the method BuildBasementFoundation requires that
WallMaterial not be equal to logs, because the use of legs as building material

eliminates the need of a wall frame.

 

 

     

 

~-.. . -=‘ h,-_-...»..J ---,. . n s

    

9 Method BEE?
L , _ .1; 5. . :.. a. .., _ - - - . a. 1,"? "g ,

 

 

 

 

 

 

 

 

I s r . : . 1,,277‘... - .«3,

 

Figure 12. Method WithWaIlFrame of the specialist Build. Walls, and Roof in
House Construction PS

Task Order specifies the sub-tasks and corresponding sub-specialists that
will be used in problem solving and also defines the linear order in which they
must be executed. The composition rule defined how the results generated. by
subordinate specialists can be put together in one plan. The composition rule
browser allows the user to visually build the decomposition methods. For
example, the method above shows that Make a Wall Frame should be done first,
then Build_Wa||s can be performed in parallel with two consecutive tasks: Make
a Roof Frame and Build a Roof.

Sometimes the order in which the tasks are put together in the plan does
not correspond to the order in which sub-plans for the tasks will be generated.
Figure 13 illustrates the methods WithFoundation for the Build a House
Specialist. In this method, the task Build Foundation precedes the task Build
Walls and Roof in the decomposition rule; however, according to the task order,
the sub-plan for Building Walls and Roof will be generated before the sub-plan

for Building Foundation. This sequence is established because the Foundation

 

 

Specialist will use some attributes defined during the plan generation for Build

Walls and Roof.

 

  

:7" “*'*z‘_:-. .23 .\ . .. 3.7:

 

 

 

Figure 13. Method ‘With Foundation’ of the Specialist Build a House in House
Construction PS

6.4.2. Step Specialist
The Step Specialist is responsible for setting the parameters of the

primitive planning steps that can not be decomposed further. The Step specialist
contains the knowledge required to establish the values of the step parameters. It
also contains the list of parameters, the link to the problem solver capable of
generating the parameter values and the mapping table that defines the
correspondence between the step parameters and variables of the referred
problem solver. The generation of parameter values is implemented in
Hierarchical Planning using the Routine Design Problem solver. Figure 14 shows
the Step Specialist Insert Beams, which uses the FoundationDepth Routine
designer to establish the appropriate depth of the house foundation based on the
WallMaterial (input parameter to the system) and WallThickness (established by

another routine designer for the step BuildWalls).

 

 

 

 

 

 

 

Figure 14. Step Specialist lnsertBeams of House Construction P8

6.5. Problem Solving
The problem-solving process in HP begins by creating an empty plan and

querying the user about the values of input variables. The plan generation starts
from the top-level specialist, which selects and applies one or more of its
methods to expand the plan. Every method, in turn, proceeds by checking its
precondition and then by invoking other specialists in the predefined order. If the
step specialist is invoked, it executes the related routine designer to
parameterize the plan step. In this scenario, situations can result in uncertainty
when the decomposition specialist selects more then one method or when the
Routine Designer associated with the Step specialist generates multiple sets of
parameters. This scenario has two possible solutions:

0 In every uncertain situation, always select the first choice, which will result in

the generation of a single plan.

86

. Always consider all possible choices, which will result in multiple plan
generation.

While the second approach will generally be more expensive
computationally than the first approach, the generation of multiple solutions is
preferable for many real word applications. Generally, the goal of the KBS
developer is to make a specific KBS valuable to various users in the domain. As
a result, the domain knowledge tends to be rather user independent.
Consequently, the generation of multiple solutions would allow the application of
a user-specific selection mechanism in choosing the plan preferable to a
particular user. On the other hand, when developing a knowledge-based
application for a known user, it is possible to incorporate all the user-specific
knowledge into the system. HP has the capability to function in both modes,
which makes it useful for creating general purpose planning KBS applications as
well as for developing user-oriented systems.

6.5.1. Single Planning

In order to run the problem solver, the user needs to set up a case in the
problem solver's database before defining the situation for which a solution will
be generated. The case contains the values of the database variables used in
the problem solver. Then, the generation of the plan proceeds as follows:

1) The initial plan is created and is composed of one node: the top specialist’s
task.
2) The top-level specialist is invoked. It requests its selector to choose a method

for pursuing the methods available to that specialist.

87

3)

4)

5)

6)

7)

From the set of selected methods, the first one is invoked.

The method checks its preconditions and, if they are valid, proceeds further. If

the preconditions fail, the next method from the selected set is invoked and

Step 4 is repeated. The failure of all selected methods will lead to the failure

of the specialist.

The method’s composition rule is used to expand the plan by substituting the

task that was in the plan with a network of simpler tasks or steps.

The further generation of the plan proceeds by invoking specialists associated

with the tasks added to the plan. The specialists are called in the sequence

defined by the method’s Task Order. Each specialist will follow one of the

following possible scenarios:

a) The Decomposition Specialist it will repeat Steps 3 through 6.

b) The Step Specialist will execute its routine designer to establish the value
of step parameters.

Failure of the specialist leads to the failure of the method from which the

specialist was called. If the top-specialist fails, the whole problem solver fails,

indicating that no plan to the specified requirements is possible, given the

domain knowledge that is available.

The system also supports the “step by step” variation of a single mode,

where the user can browse the plan after every specialist invocation and trace

the changes that are being added. This feature of HP can be especially

beneficial during the application development stages to help in finding

inconsistencies in the problem-solving knowledge. The Table 4 illustrates the

88

process of generating a single plan in the House Construction problem solver for
the case where HouseStyle = “American Cottage,’ Location = ‘Midwest,’ Soil =
‘Dirt,’ and WallMaterial = ’Board.’ The final plan is represented as a network
where 1.) each node corresponds to a step in the plan and 2.) the direction of the

flow designates temporal order.

 

1.lnitial Plan

 

 

 

 

i
f

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

J
,“. ,1 ' if ‘- .. ‘I’.0 ‘~.--" "I' b {'3' 4 ' t i — ' f
‘ g I I ,I I ‘ . ' ‘

. - ' " _. - - _- ‘X‘ _ - .2 ‘
u 1 - . ‘ - r . r

f . \l I. ‘:‘V~ 77“ I
., . 7

. . . ' ..
. stat MelteAWel Frame - - ~
I. m— , it
1 . _‘ ' c
. a z - , i ’ ‘- _ ‘ ) . . " w'L ‘ ‘. ‘
' J , . - . . I ' . . . i.‘ .
. . , , , ..., . . .. , MekeARoofFrame
i r ‘ . . .‘ -> .. ‘ 4 .A
r a . _ ,,
. . . .- ‘ . , . i e. - . .

I ‘. 1 ' ‘7. I ‘1" .~‘ ' 7 v 7'

I . n u‘ ‘ ‘r' - a . ' '

~ “at" - . n '_.—- u -—u..' ‘na-v- -:as.-. t..- -m -—.—.&‘2: 'HL 1"“. “nah-“5‘. lan- .--.‘.‘.—-r:r- --’- J...» no.- 1—- “(.- "h

 

 

Table 5. Step by Step Plan Generation for House Construction Problem Solver

89

 

 

4. The Routine Designer WallThickness is executed by BuildWa/Is specialist to
determine the parameter WallThickness:
Result: WallThickness = ‘medium.’

 

 

5.The method BasementMethod of specialist Build Foundatiorr

gm" AIM—wm—ml

i FithhConoruo

l

K
L

Resulting plan:

 

 

6. The Routine Designer FoundationDepth is executed by Dig a Pit specialist to
determine the parameter FoundationDepth.
Result: FoundationDepth = ‘full’

 

Table 6 (continued). Step by Step Plan Generation for House Construction
Problem Solver

6.5.2. Multiple Planning
The problem solving in multiple planning follows the control algorithm

similar to that of a single design. However, several differences exist:

. When the decomposition specialist is called on, several methods can be
found to be applicable. In the single mode, only one method of the selected
set is executed for any specialist unless it fails, in which case, another
method is attempted. Alternatively, in multiple planning, all methods selected
by the specialist are attempted and used to generate different plans.

. In single planning, the Step Specialist’s related Routine Designer is executed

in a single mode which allows to generate only single set of step parameter

90

 

values. In multiple planning, the Multiple Routine Designers are used. As a
result, several possible parameterizations can be generated for a single step,
which also results in different plans.

In order to keep track of different solutions as they are generated, the
system generates a plan hierarchy. Each node in the plan hierarchy corresponds
to the application of a method or a Routine designer. If, at some point in problem
solving, several methods are applicable, the plan hierarchy will have a separate
branch corresponding to each of these methods. The branching in the tree can
also result from multiple solutions generated by a routine designer used by a
Step Specialist. In the plan hierarchy, each path from a root to a leaf node
corresponds to a different planning scenario. The leaf nodes contain a final plan
generated using this scenario; the intermediate nodes contain the plans that
were generated at different stages of problem solving.

If the problem solving was successful, the final plans associated with a
leaf node are composed only of planning steps and do not have unexpanded
tasks. In this case, the leaf nodes are shown in green in the plan hierarchy.
Sometimes the specialists responsible for solving tasks in the intermediate plan
fail, which causes the whole scenario to fail. The leaf nodes in this case contain
an incomplete plan, with some tasks remaining unexpanded, such leaf nodes are
represented in pink in the plan hierarchy. Figure 15 illustrates the plan hierarchy
where two scenarios failed and two were successful. The solution shown on this
figure was generated for the case where HouseStyle = “Russian Hut’, Location =

‘southeast’, Soil = ‘wetland’, and WallMaterial = ‘brick’. The leaf nodes that

91

correspond to the successful scenarios have plans that contain only simple steps
(i.e. refined plans); whereas, the final plans for the failed scenarios still contain

non-refined subtasks.

,5 Relation Interlace
, -.__ . w W,

 

 

 

 

Figure 15. Plan Hierarchy Generated by House Construction PS
The Plan hierarchy provides a visual representation of the problem solving

undertaken by the knowledge based system — this visual representation is
especially convenient during application development. First, each node name
denotes the Specialist and its method that was applied to produce the plan

embodied in the node. This denotation allows the user to retrace the sequence of

92

specialist evocations, which can be used to find inconsistencies in the task order
defined in the methods. Second, the user is able to browse the plans related to
every node in the plan hierarchy and obsen/e plan changes caused by the
method application. By browsing the plans, users can find flaws in the
decomposition knowledge of the method.
6. 6. Extension of the GT approach

The described approach widens the applicability of the GT paradigm by
allowing building problem solvers for Class 3 planning tasks. Routine Designers
and Multiple Routine Designers (RD/MRD) could and were successfully applied
to solve Class 4 planning problems (see also Section 3.4.2) where the planning
is reduced to the parameterization of the existing skeletal plan. However,
RD/MRDs can not effectively handle the problems that require some flexibility in
creating plan (such as alternating order of planning steps). This is where HP fits
with its versatility to apply the same specialist in different contexts to produce
plans with different order of steps.

At the same time RD/MRD-based specialists could be of use at the leaf
node level of the HP. The level of constructing primitive steps for a plan.

6. 7. Conclusion I

This chapter describes the tool for the development of knowledge-based
hierarchical planning systems. The tool was developed to support the ideas
presented in this dissertation research. It is a part of the Generic Task Integrated
Tool Set (Kamel, Lukibanov et al. 1997) and allows the integration of the GT-

based problem solvers into the Hierarchical Knowledge-Based Planning

93

Systems. The incorporation of the GT-based problem solvers Routine Designer
and Structured Matcher allows more elaborated reasoning for leaf-level
specialists as well as allows a complex context check at each node of the
specialists’ hierarchy. As an example of GT-based architecture, Hierarchical
Planning promotes modularity in problem-solving knowledge which supports
knowledge acquisition and effective problem solving. The knowledge modularity
can be seen in two different perspectives. First, the knowledge is divided based
on the taxonomy of the domain problem into a set of specialists. Second, each of
the specialists has pieces of knowledge represented in accordance with the
nature and use of the knowledge.

There are also several advantages of the developed tool that are specific
to the development of planning applications:
1) In Knowledge Representation,

a) the tool provides a richer visual representation of the method’s
decomposition knowledge in the form of networks, as opposed to a more
common textual representation in the form of linear rules.

b) the tool supports explicit representation of the sub-task order that reflects
the importance of the subtask in the problem-solving process and helps
avoid a computationally expensive search.

0) the method selection knowledge can be represented locally in the method
as a precondition, as well as outside of the method at the specialist level.

This provides a more flexible method selection mechanism than the

94

approaches where the method selection knowledge is concentrated only

at the method’s level.

2) ln system development and problem solving,

a) the tool supports two modes of problem solving: single planning or
multiple planning. Depending on the purposes of the knowledge-based
application, the user can select the problem-solving mode that is most
appropriate. For a general-purpose application, the multiple planning
mode is more suitable, while the single planning mode would be sufficient
for a user-specific application.

b) it is usually important to be able to track the problem-solving process at
the development stages. Both multiple and single mode support this ability
by providing a ‘step by step’ view in the single planning mode and by
storing the solution tree for the multiple planning mode.

The Hierarchical Planning tool is based on the problem-solving
architecture proposed for the planning problems of Class 3. This prototype
development shell does not include all the elements of the proposed architecture.
For example, it does not explicitly implement the critique task. Currently, some
critique knowledge can be encoded in the method’s preconditions which will
‘critique’ the plan generated at method invocation. Alternatively, the critique can
be done through the use of the attribute relations defined in the database to
check the correctness of the generated step parameters. However, a more

explicit representation of the critique knowledge will be clearly more

95

advantageous. The use of the method post-conditions to validate the result of the
method application is one possible way to solve this problem in the future.

Another future extension of the tool will incorporate the Plan Repair
methods, which are the part of the ‘modify‘ task. Currently, the plan modification
can be implemented only through backtracking. It is important to note, however,
that the need for plan modification can be eliminated when using multiple
problem-solving, because modification knowledge could be included as a part of
the normal generative planning knowledge. Consequently, all possible plans will
be considered during system execution and the “modified” version of the plan
can be generated from scratch instead of being generated as a modification of
the incorrect plan.

In this chapter, I used the House Construction problem to illustrate the
process of the KBS development promoted by the HP tool. The problem has
been considerably simplified for the ease of explanation. Now that I have
explained the details of the approach, it will be useful to demonstrate its
application to a more complicated planning problem. The next part of the
dissertation describes the development of HP problem solver for composite

materials manufacturing planning system.

96

7. INTELLIGENT SYSTEMS IN COMPOSITE MANUFACTURING

The growing popularity of composites in different areas of industry brings
about the need for computer tools that provide support for engineers and
manufacturers. A lack of fundamental understanding along with the substantial
experimental knowledge gathered by the domain experts provides a strong
motivation to use knowledge-intensive methods to develop such tools. This
chapter discusses the importance of manufacturing expertise in the area of
composite materials and gives some examples of related knowledge-based
systems.

7. 1. Concurrent Product/Process Design in the Composites Domain

Polymer composite materials are complex material systems which consist
of a polymer matrix and an incorporated fiber reinforcement. Composites are not
isotropic materials: the fiber orientation and the microstructure define the
functional properties of a product. The flexibility to be tailored specifically for
particular applications is one of the main advantages of composites, but, at the
same time, it also presents a challenge. For traditional materials with isotropic
properties, it is possible to apply simple formulae or tables during conceptual
design to evaluate the functional properties of the product and postpone complex
calculations and manufacturing solutions to later stages. In composites, every
solution made at any point in the product development process is related to three
interacting decision areas: materials design, configuration design and
manufacturing process planning. The presence of three decision areas makes

concurrent design/manufacturing engineering a basic requirement for composite

97

design. As it was noted in (Wilkins and Karbhari 1992): “were it [concurrent
engineering] not established for other fields, it would have been invented for
composites out of necessity.”

The use of intelligent systems that perform manufacturing analysis during
product development can greatly accelerate the design process by reducing the
time spent iterating the design description between the design engineer and the
manufacturing engineer. Usually, the purpose of such systems is to evaluate
different parameters of the potential manufacturing process, identify possible
problems, or recognize design solutions that cannot be effectively fabricated. A
number of intelligent computer tools that support concurrent design for
composites were developed in recent years (Moy, McDowell et al. 1995; Quibble
1998; Lukibanov and Martinez 2000). The following discussion will examine and
compare several intelligent systems that emphasize manufacturing expertise in
design with composites. An analysis of the systems’ architecture and
implementation details provides valuable insights on the problem solving
techniques used.

7.2. CAM Systems in Composites

Tools that support concurrent design can be effectively used during all the
design stages, however the opportunities for reducing process-related costs
decrease as the design moves along the product realization process time-line
(Quibble 1998). Due to this fact, the emphasis of this research is on the
application of Al techniques for building intelligent systems targeted to support

early conceptual design stages.

98

7.2.1. ACES
The ACES (Automated Concurrent Engineering Software) system was

developed from 1993 to 1996 at the Design & Manufacturing Institute (DMI) at
Stevens Institute of Technology (Manoochehri 1994; Webb, Gerdes et al. 1995;
DMI 1998) and is a successor of the system called Designer‘s Apprentice
created earlier at DMI. ACES is a software package developed specifically to
support the design process. The ACES framework was used to implement an
intelligent system for the design of injection molded composite parts; later, the
knowledge base was extended to include knowledge about the Resin Transfer
Molding (RTM). One of the greatest advantages of ACES is that it provides a
seamless integration with CAD software, databases, and engineering analysis
tools — such as flow and structural performance analysis — which simulate
processing conditions and predict part performance.

The knowledge representation is similar to that of rule-based systems. In
ACES, the knowledge base consists of a number of related modules (analogous
to rules) that contain knowledge about different aspects of the design process,
including material selection, part design, process and tooling design, mold
machine selection, and cost estimation. The knowledge in each module is
represented by a set of logically connected algebraic formulae (e.g., costing
model) that define relations between various parameters of the design
configuration, the material system and the manufacturing process. Whenever any
change is added to the design specification, the formulae contained in all
modules will be reevaluated to ensure that the design is satisfactory. Throughout

the design process, ACES will use its knowledge base to evaluate automatically

99

how design changes will impact mold design, processing parameters, cost, etc.
The system gives a design recommendation and reports inconsistencies in the
design. For example, when the engineer chooses a material that satisfies
performance requirements, ACES assesses the selection and informs the user if
the material meets the requirements for cost and processing; suitable
alternatives are recommended if the user's choice was found to be inadequate.

7.2.2. DSSPreform

The DSSPreform (Decision Support System for Preforming) was
developed at the University of Delaware in conjunction with Lanxide Corporation
(Pitchumani, Schwenk et al. 1993; Pitchumani and Karbhari 1994; Pitchumani,
Schwenk et al. 1994). This system was developed to aid in the design and
manufacture of porous preforrns which are subsequently infiltrated with a matrix
material to form ceramic- and metal-matrix composites.

DSSPrefonn consists of three problem solvers: a Material Expert, a
Process Selection Expert and a Process Design Expert. The linearized problem-
solving process begins with determining the material, proceeds to selecting the
process and ends with parametrizing the process. The problem-solving methods
used in DSSPreform are a mixture of a knowledge-based approach and model-
based reasoning. Each expert is comprised of hierarchically organized sub-
specialist modules; the sub-specialists’ knowledge is in the form of rules of
simple empirical models.

The Material Expert contains a group of specialist modules that can define

the composite material in terms of the matrix, the reinforcement, and the

100

reinforcement’s geometry and volume fraction. The Process Selection Expert
uses rules and procedure-based selection strategies to obtain a list of processes
for preform manufacturing. The Process Design Expert contains heuristics and
simple empirical models to carry out the manufacturing process specification.
The models serve to validate the recommendations based on heuristics and to
handle situations not covered by the established heuristic knowledge.

7.2.3. Cfiost modelingfir AdvRTM

AdvRTM is a modification of Resin transfer molding process developed at
Dow-United Technologies Composite Products (Dow-UT) (Quibble 1998). To
enable optimization for an AdvRTM manufactured part during the early stages of
the design, Dow-UT developed an intelligent system for evaluating part design
options, predicting recurring material and labor, and for simulating the
manufacturing cycle.

The system is composed of two main modules: Cost Advantage and
Simulation. The Cost Advantage module is a rule-based system for cost and
producibility analysis. The problem-solving process follows a “step-by-step”
approach that engineers typically use: based on the design concept, the
manufacturing process flow is determined, then labor and tooling requirements
are defined, and finally, the capital requirements are estimated. Along with a cost
analysis, the system provides manufacturing guidance by identifying
unmanufacturable designs or more expensive solutions, and consequently

enables design optimization for cost.

101

The goal of the Simulation module is to evaluate the dynamic environment
of a specific production facility and report the success or failure of a particular
manufacturing scenario. The production facility is described in terms of the
availability of needed capital equipment, personnel skill levels, tooling levels, etc.
The simulation is based on a process model containing a set of modules, each
related to a specific operation within the AdvRTM process. The simulation
process is driven by data-descriptive process sequencing, cycle times found in
the facility, characterization of equipment, and tooling and personnel.

7.2.4. _s-Azg

The S-APD (Systematic Assembly Process Development) approach was
developed at the University of California to support Design for Assembly in the
domain of composite materials (Lee and Hahn 1996; Lee and Hahn 1997; Lee
and Hahn 1997). The purpose of the system is to enable the comparative
analysis of multiple joint design options specific to the assembly of the composite
structure. The types of joining technologies modeled in the system are for
families of discrete fasteners, bonding adhesive formulations, thermoplastic
welds and composite integral fit joints. The composite structures in the system
are represented based on the types of joints used.

The system achieves its functionality by generating a
manufacturing plan and using this plan to estimate the manufacturing resources
required. Based on the description of the assembly configuration, the system
generates an assembly plan to specify the required components and assembly

steps. Each assembly step is associated with a specific joining method and can

102

be achieved by a predefined sequence of generic operations related to this
method. Thus, by systematically defining the operations required for each
assembly, the manufacturing process plan for product assembly is generated.
The generic manufacturing operations in the plan are then specified through
parameterization. Once the manufacturing assembly process is generated, it can
be used for different types of analyses — for instance, the comparative cost
periorrnance analysis.

7.2.5. SOCHARIS

Socharis‘ was developed at Michigan State University between 1996 and
1999 (Martinez, Lukibanov et al. 1999; Lukibanov and Martinez 2000). It is an
intelligent system that generates a family of applicable conceptual manufacturing
plans given a conceptual description of an assembly. Socharis employs
knowledge about nine generic manufacturing technologies used in polymer
composites: hand layup, sprayup, resin transfer molding, compression molding,
resin injection molding, resin infusion, filament winding, extrusion, and pultmsion.
This set of processes covers a large variety of existing technologies, excluding
rare or proprietary processes.

Socharis consists of an integrated architecture that incorporates several
knowledge agents: Fabrication Technology Generator, Joining Technology
Generator, and Technology Estimator. The problem-solving architecture is based

on the Generic Tasks (GT) approach to the development of knowledge-based

 

4 The problem-solving architecture of Socharis was discussed in detail in the
Section 3.4.2
5 Section 3.4 contains detailed description of the Generic Task approach.

103

systems and employs structured knowledge representations and inference
strategies relevant to the system’s functionality. The system problem-solving
strategy includes three major tasks: creating a skeletal manufacturing plan,
deciding and detailing a technological process for each planning step, and
ranking the generated technological processes. The initial manufacturing plan is
generated based solely on the specification of the composite assembly. The
skeletal plan contains sparse information about generic manufacturing steps and
their partial order, i.e., explicitly stated precedence of joining, component
manufacturing and feature addition operations. The next stage involves selecting
the appropriate manufacturing technologies for each component in the assembly,
based on the geometrical and material specification and also involves
establishing manufacturing parameters (curing requirements, tooling
requirements and so on) using component data and information about production
rate, tolerances, etc.

The multiple alternatives for component manufacturing generated by the
system are estimated and ranked using a merit table approach. In order to
implement this approach, a set of critical metrics (e.g., cycle time, tooling
turnaround time, and geometrical repeatability) was selected and linked to a
weighting factor that reflects the importance of the metric to the user. After all of
the metrics are estimated for each of the selected technologies, calculating the
weighted sum of the estimated metrics ranks the alternative technologies, and
the system can recommend the most advantageous manufacturing methods to

the engineer.

104

It is necessary to note that, even if the results of Socharis could be
interpreted as manufacturing plans, the generated plans” detail stops at the level
of determining the parameters of fabricating technologies. The manufacturing
technoldgies are assumed to have fixed, predefined schema that can be
parameterized during the plan generation process but can not be varied. In
practice, however, this assumption does not hold and the same manufacturing
technology can consist of different manufacturing sequences, depending on the
design of the component, material and requirements. Therefore, while Socharis
is useful at the conceptual design stage, it cannot provide a detailed, step-by-
step plan for fabrication sequences.

7.3. Comparative Analysis

Table 5 gives a comparative summary of the systems described above,
when considering the application domain, the goals of the system, and problem
solving techniques employed.

7.3.1. Application Domain

The generality of the application domain varies considerably for the
described systems. For example, the cost estimating system for AdvRTM was
created specifically for the manufacturing process developed at Dow-UT;
DSSPreform was intended to support design with specific types of material
systems and manufacturing process. These approaches assume that the
competent selection of a generic manufacturing method was made in advance,
which is not always feasible. Reducing the number of considered techniques ’

could lead to ignoring advantageous manufacturing solutions. In addition, the

105

number of different design variations that are considered is limited by the specific
constraints on the manufacturing method being used. As a result, such systems
could not be effectively used during the earliest stages of the product
development when design configuration and manufacturing methods are

selected at a very high level of generality.

 

 

 

 

 

 

 

 

 

 

 

System Application Domain Functionality PS method
ACES RTM, Injection Manufacturing analysis based Rule-based approach
molding on design description
DSSPreform Manufacturing of Material selection & process Specialist
ceramics- and design hierarchies;
metal-matrix- specialists use
composites heuristics 8. model-
based reasoniri
Cost Advanced RTM Cost estimation based on Rule based approach
modeling for used at Dow-UT plan generation & Simulation & model based
AdvRTM reasoning
S—APD Joint manufacturing Manufacturability analysis Hierarchical
for composite , based on plan generation & knowledge
assemblies Estimation representation &
model-based
approach
Socharis Composite Manufacturability analysis Integrated Generic
assembly based on alternative plans task approach
manufacturing using generation and estimation
multiple
technologies

 

Table 7. Knowledge-Based Systems in Composites Manufacturing

In contrast, systems such as Socharis and S-APD incorporate more
general and comprehensive domain knowledge and allow the consideration of a
variety of manufacturing processes that can be used from the very beginning of
the design process. However, the lack of specific, detailed knowledge will make

these systems less effective during the later stages of the design.

106

7.3.2. Solution Approach
The functionality of the systems being discussed is presented in more

visible format in Table 6.

 

 

 

 

 

 

 

System Manufacturability Process Plan Plan
analysis selection generation Comparison

AC ES

.1
DSSPreform

V V

Cost
modeling for v v v
AdvRTM
S-APD

v V «I v
Socharis

v V V V

 

 

 

 

 

Table 8. Functionality of the Knowledge-Based Systems in Composites
Manufacturing

The primary purpose of these systems was to provide manufacturing
feedback to the designer; however, this goal can be achieved through different
functionality, as is shown in Table 2. For example, the ACES system supports
manufacturability analysis using precompiled rules; whereas, in the rest of the
systems, manufacturing plan generation is performed before the estimation of
manufacturability factors. Two approaches can be identified here:

. Constraint-based approaches, where the constraints are used to identify
infeasible designs from direct inspection of the design description.

. Plan-based approaches, where the analysis of the manufacturability is based
on the generation of the manufacturing plan for the design.

Although the first approach is attractive because of its simplicity, often
complex interaction among manufacturing operations make it difficult to evaluate

the manufacturability directly from the design descriptions. In these cases, a

107

 

viable alternative is to use the second approach. In addition, the plan-based
approach not only allows the estimation of manufacturability, but also provides a
basis for developing detailed manufacturing plan.

In many composite manufacturing systems that use a constraint-based
approach, the manufacturing technologies are assumed to have fixed, predefined
schema that can be parameterized during the plan generation process. The
assumption ignores the fact that the actual manufacturing technologies, while
following some basic processing stages, have variations that go beyond simple
differences in parameter values. Among the constrained based systems
described, all use predefined process schemata that are parameterized
according to design specifications. More flexible planning techniques would
prove beneficial in many aspects, since a preliminary manufacturing plans can
easily be the basis for more reliable cost estimates for actual fabrication.

7.3.3. Proplem Solving Technigu_e_

The choice of problem-solving techniques used in a knowledge system
defines not only the problem-solving algorithm, but also the knowledge
representation - this is directly related to the system maintainability. DSSPreform
(Schwenk et al. 1994), Socharis ( Lukibanov and Martinez 2000), and S-APD
(Lee and Hahn 1997) use structured, hierarchical knowledge representations that
provide advantages for system maintenance and modification, in contrast to the
other two systems (ACES (DMI 1998) and Cost modeling for AdvRTM (Quibble

1998)) that use rules to represent problem-solving knowledge. The unstructured,

108

flat architecture of rule-based systems complicates all the stages of a system’s
life cycle: knowledge acquisition, debugging, adding changes, etc.

Several of the systems presented employ model-based reasoning as an
auxiliary mechanism. For example, in DSSPreform and Cost modeling for
AdvRTM, model-based reasoning is used to verify the results inferred by using
the rule-based part of the system. Although little objection could be raised
against model-based reasoning in general, in this particular case, the use of
mathematical formulas to describe models is not relevant to the qualitative level
at which a design is often described during early development. Qualitative
function/structure models such as (Sticklen and Chandrasekaran 1985;
Chandrasekaran 1993; Hawkins, McDowell et al. 1993) would be more suitable
to support conceptual design.

7. 4. Conclusion

The systems presented in this chapter are characteristic of the various
facets of research in the composite materials community to leverage
computational methods to support design and manufacturing planning. The
discussion showed several issues that are important to any implementation
which supports design and manufacturing with composites. These issues are
related to the general functionality of the applications and to the Al techniques
employed to support this functionality.

The general goal of the systems described above was to support
concurrent design. This means that throughout the evolution of the design,

manufacturing factors have to be considered. Therefore, to actually support the

109

process of concurrent design, the system must be adaptive to the changing level
of generality within which the design is represented. For example, if the design is
initially described only at the top level, the system will generate only general
manufacturing recommendations. Later, when the design is detailed to a more
specific level, the previously generated recommendations need to be refined to
satisfy the new emerging level of detail. The systems described in this chapter do
not have such flexibility.

Other important considerations are related to Al approaches which are
used to implement the systems. The comparison of the different knowledge
representation techniques that were used shows that a knowledge representation
relevant to the task at hand is one of the most essential conditions to a
successful implementation.

The selection of a planning approach also requires careful consideration.
The plans generated by the system are used for manufacturability estimation,
and as a basis for actual manufacturing plan development. Thus, the correctness
and accuracy of plans directly affect the quality of the designed product. The use
of predefined process configurations does not always produce satisfactory
results, often more flexible planning methods are required.

The following chapter describes the most common manufacturing
processes used to fabricate composite artifacts as well as the intelligent planing
system COMPLAN and the specifics of the manufacturing methods that the
COMPLAN operates with.

110

8. COMPOSITE MATERIAL MANUFACTURING PLANNING: AN
APPLICATION PROBLEM STATEMENT

The previous chapter examined several systems developed by other
authors in the domain of manufacturing with composites. One of the conclusions
is that computer-aided design and manufacturing systems are of particular
importance to the domain of composites. However, there is an evident lack of
manufacturing planning applications in this area. Research in the manufacturing
planning is traditionally aimed at discrete manufacturing, while composite
manufacturing can be more precisely classified as a process-centered
manufacturing.

Discrete manufacturing may be understood loosely by an analogy to the
common concept of assembly line manufacturing. In planning systems intended
for discrete manufacturing, the goal is usually to find the most proper, effective
ordering of manufacturing steps. In contrast, process-centered manufacturing
focuses on the generation of the proper steps-to-follow such that the finished
product will meet the desired qualities.

Metal machining can serve as an example of discrete manufacturing. The
goal of metal machining manufacturing planning is to find the appropriate order of
machining operations. For the most part, geometric features of an individual part
and the knowledge about basic operations drive this planning. The metal
machining planning process can not be structured or described a priori, although

some planning heuristics can be applied. As a result, the goal in discrete

111

manufacturing becomes the development of general and very efficient
algorithms.

In (Gupta, Nau et al. 1994; Nau, Gupta et al. 1995) the authors describe
IMACS (Interactive Manufacturability Analysis and Critiquing System). IMACS
analyzes the manufacturability of the proposed designs for metal machined parts
by generating and evaluating operation plans. An operation plan generated by
IMACS is a sequence of machining operations (milling, drilling, etc.) capable of
creating a goal part from the stock, where the goal part is represented as a CAD
model.

Traditionally, discrete manufacturing was the main topic of research in Al
manufacturing planning. Unfortunately, the results achieved in this field can not
be directly applied to the process-centered planning such as planning for
composites manufacturing. The reason for this that the discrete manufacturing
planning does not make use of a domain-oriented knowledge but rather is based
on a domain independent search techniques.

While the planning steps in composite manufacturing must be configured
and parameterized with respect to the geometry and mechanical requirements of
the part, the planning process in industry is typically driven by heuristics about
manufacturing technologies rather than by part specifications. The composites
domain possesses extensive expertise which makes this domain an ideal
candidate for the application of knowledge-based planning methods. I will use the
problem of composite manufacturing planning as a test bed for the validation of

the planning methodology described in this dissertation approach. Particularly,

112

the shell for building hierarchical planning systems developed as a result of this
dissertation will be used to implement knowledge-based planning of
technological processes for components made of composite materials. This suite
of applications will act here as proof of concept for the theoretical stance taken
earlier.

This chapter describes the basics of composite manufacturing and
formally states the application domain problem of this dissertation.

8. 1. Composites Manufacturing

Modern structural composites are a blend of two or more components,
one of which is made up of stiff long fibers, and the other is binder material. The
matrix holds the fibers in place in the structure and helps to distribute or transfer
the load. Further discussion will focus only of polymer-matrix composites that
constitute the majority of all known composites. The role of the fibers in the
composite material is to provide strength and stiffness. When the fiber and matrix
are joined to form a composite, they both retain their individual properties and
both directly influence the composite material’s final properties. An advanced
composite can be tailored so than the directional dependence of strength and
stiffness matches that of the loading environment.

When the part is designed, the manufacturing process can be selected
based on the fiber architecture“, and the types of fiber and matrix, as well as on

the geometric shape and expected functional properties of the component. Some

 

6 The fiber architecture refers to the way the fibers are positioned in the
composite material. The types of fiber architecture include unidirectional, quasi-
isotropic, chopped, woven, braided .

113

of the manufacturing processes used in composites are simple, one-step
processes (i.e., Injection Molding, Sprayup) while others are continuos processes
(Extrusion, Pultrusion). However, there are processes such as, Layup, Resin
Transfer Molding (RTM), Resin Infusion, Compression Molding, that are
composed of multiple manufacturing steps that have numerous variations
depending on the available manufacturing resources and product specification.
The ability to generate the process plan for such processes becomes a primary
issue and will be addressed in this dissertation. Paragraph below gives a short
description on Layup, Resin Transfer Molding (RTM), Resin Infusion, and
Compression Molding.

8.1.1. Lamp

ln Layup, the material is laid up layer by layer to produce a laminate of the
desired thickness, number of plies and ply orientation. The main steps of this
process are material preparation and placement, debunking, and curing. Usually,
the material used is a prepreg: the material in sheet form that consists of a fiber
system impregnated with resin and partially cured. Sometimes the wet Layup can
be used, in this case, the resin system in liquid form is applied to the
reinforcement during the manufacturing of the components. After the material is
cut and put into the tool, the next step is to remove the excess air and resin from
the material to prevent wrinkles - this process is called debulking. Debulking
usually involves bagging the part and applying pressure; the possible alternatives
to that are: rolling, using a vacuum, applying pressure through a press or

pressure chamber, or using a combination of heat and pressure (the autoclave

114

oven). The next processing stage involves curing the material, which may include
one or several of following steps: b-stage cure, final cure, postcure. The bostage
is the first step in the cure cycle during which the resin is partially cured to the
point where it will not reflow and change shape upon application of further heat.
When the b-cure is applied, the tooling can be removed from the part before
further curing stages, when necessary. The final cure then irreversibly changes
the properties of the resin as a result of a chemical reaction. This reaction can
occur with or without the application of hit and pressure, depending on the resin
type and desired functional properties of the product. The options for final cure
are autoclave, microwave, press, oven, or room temperature cure. The postcure.
through exposing the product to elevated temperatures can be used as the last
step of the process to improve the product’s functional properties.

8.1.2. Resin Tgisfer Moltmg

Resin Transfer Molding (RTM) is the process where resin is transferred or
infused into an enclosed mold in which the reinforcement has been placed, and
then cured to result in a final product. The main stages of RTM include preform,
clamping, resin infusion and curing. During preform the fiber reinforcement of a
mat or cloth is formed to the desired shape; this is done using different methods:
by spraying the chopped fiber into the preform, by stamping, by manually placing
the fabric, or by weaving the desired shape. Then, the tool is closed and resin is
infused into it. The infusion process involves supplying the heated resin under
certain pressure into the mold and monitoring the temperature of the mold itself.

The infusion follows by the curing stage: b-cure, final cure, and post cure.

115

Depending on the resin type, the final cure can be done at room temperature or
at an elevated temperature. In the latter case, external or integral heating method
can be used. The external method requires placing the tooling containing the
product in the in the oven or microwave, or applying heated plates to the tooling.
For integral curing, the tool itself is heated by electricity, steam, or hot oil.

8.1.3. Resin II'ILUSIOI‘I

Resin Infusion is a process similar to RTM. However, instead of a closed
mold, it uses a one-sided mold, which affects the methods that are used to insert
the resin into the fiber reinforcement and the curing methods. The main steps of
Resin Infusion are preforrning (similar to RTM), bagging, infusing the resin, and
curing. After the prefonning, the product is put in the vacuum bag that performs
the role similar the upper side of tool in the RTM method: it holds the fiber
reinforcement in place and directs the resin flow during the resin infusion. In the
resin infusion process, the resin is transferred into the vacuum bag using
negative pressure inside the bag to impregnate the fiber (in RTM, the positive
pressure is applied to resin). The curing process is then similar to that used in
RTM.

8.1.4. Compression Molding

In Compression Molding, the material is first placed in the mold and then
cured by applying closing pressure and heat. The material used is usually in
prepreg form. The process starts with the preparation of the material: cutting the
prepreg using product templates and charging the press by placing the material

inside the tool in the press. This step is followed by curing through applying

116

closing pressure to the manufactured part. Sometimes the elevated temperatures

are used in addition to the pressure depending on the resin type that is being

used. When high functional properties are the part of the product requirements,

the post cure is needed. The postcure in compression molding is achieved by

applying the press to the part a second time or by placing the part in the oven.
8.2. Domain Problem Specification

The planning approach dveloped in this dissertation will be applied to the
problem of composite material manufacturing planning. The typical industrial
scenario for this problem consists of:

1. selecting the generic technological process,

2. proposing the possible plans for the selected technology, and then

3. evaluating the plans in order to choose the best plan.

Figure 16 illustrates the system architecture that would implement this
scenano.

The first module analyses the description of the component and the
requirement in respect to its properties and outputs a list of appropriate
technologies that can be used to manufacture this product. The second module
uses the description of the component and requirements to the final product to
generate the plans for the technologies proposed by the first component. The
technologies are analyzed and evaluated by the third component with respect to
the specific characteristics and preferences of the user and the final plan is

generated.

117

 

 

'Product Requirements
°Component Specification

 

'User Preferences

 

 

Selection of the
Manufacturing Technology

Manufacturing

 

 

 

 

 

 

 

 

Technology ‘ gflaaun’ng
Plan generation ‘
T’fian evaluation and selectiofl

 

 

——-* Plan

 

Figure 16. An Information-Processing View on Composite Materials
Manufacturing Planning

The focus of the domain problem is on the development of the second

planning module that satisfies the following input/output specifications.

The input to the system is given in terms of a conceptual description of the
composite part and its expected properties. It includes functional
requirements, tolerance allowances, production size, as well as the part
description. The part description contains the rough geometry specification
(shape, size, wall thickness, aspect ratio, geometric complexity) and material
specification (resin, fiber, and fiber architecture).

The output of the system should be the family of conceptual manufacturing
plans for manufacturing the part. Each plan is represented as a directed

graph, where nodes of the graph correspond to the basic steps of the

118

 

manufacturing process and edges indicate precedence constraints about the
order of step execution. Each step is defined by its name and can also
include one or more parameters. The parameter values will be defined at the
end of problem solving for all the plan steps.

The system should encapsulate the knowledge of four manufacturing
technologies: Layup, Resin Transfer Molding (RTM), Resin Infusion,
Compression Molding. To facilitate knowledge acquisition and deployment, it is
convenient to build the system out of four cooperating subsystems, each
responsible for the planning of a particular fabrication technique. Such modular
architecture allows for the deployment to be configured to the needs of a specific
user by including only the necessary parts in the target system.

The main requirement for the resulting Knowledge-based planning
application is ease of maintenance, ease of enhancement, and ease of update.
These needs arise because manufacturing with composites is a very dynamic
domain that constantly changes: modifications of existing process are developed,
new processes replace outdated techniques, new raw materials become
available, etc. The use of the Hierarchical Planing methodology facilitates visual
editing of underlying knowledge, refining knowledge from general to specific, and
adding new knowledge to the problem-solvers, as will be illustrated by the
following chapter.

8. 3. Conclusion
By developing the planning system described above, several benefits are

expected as follows.

119

1. Part design time will be reduced because explicit manufacturing knowledge
becomes available to designers. As a result, they can explore different
manufacturing alternatives as well as realize the effects of the design decision
on manufacturing early in the design process. Consequently, the number of
design iterations can be cut.

2. Plans generated by the application will be a basis for a complete
technological blueprint of the manufacturing process reducing the amount of
trial and error - the method used generally in practice. This can significantly
lessen the cost, considering the fact that both composite processing and raw
materials are very expensive assets, and there is a time cost associated with
delays in marketing novel artifacts.

3. The resulting application will incorporate wide domain knowledge and
organize it in a consistent and graphical way. Thus, the system will be
assistance in training students and/or engineers with little or no knowledge
about composite processing.

4. The implemented application used as a technology transfer platform to share
the knowledge about particular manufacturing technologies between both

academia and of industry.

120

9. COMPLAN: A KNOWLEDGE-BASED APPLICATION FOR COMPOSITE
MATERIAL MANUFACTURING PLANNING

In this chapter, I describe COMPLAN - the prototype planning system that
automates the problem solving process for the planning problem for composite
manufacturing as described in previous chapter. COMPLAN implements
manufacturing planning for several composite material technologies: Layup,
RTM, Resin Infusion, and Compression molding. The system was designed to
test the model for knowledge-based planning that was proposed in Chapter 5.

This chapter discusses COMPLAN implementation and problem solving
as well as its role in the suite of knowledge-based systems intended to support
the development of the composite material product from the conceptual design
stages to manufacturing.

The most of the knowledge engineering effort to build COMPLAN was
made possible by a kind contribution of time and practical knowledge of
composite processing from Mr. Roger Kaminski chemical engineer of a Lansing,
MI based company Cade Auto Air. In addition I would like to thank the
contribution to the knowledge content of COMPLAN to Mr. Gary Wigel VP of
Engineering Cade Auto Air and Dr. Jim McDowell President Mad Dog
Composites.

9. 1. System Implementation

COMPLAN implements the portion of the problem-solving architecture for

manufacturing planning described in the previous chapter. The System

architecture includes two modules: Technology Selection, which chooses an

121

appropriate technological process, and Plan Generator, which produces a set of

plans for the selected process.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Input

QQMPW
'Maren'al Features
(re-*2" WPC- fiber Technology Selgctor
arc itecture) , , , , . Cl .
°Geomerrical Features "mum“! :h H 6“ mama“ m"
(shape, aspect ration, Technology Technology
wall thiclmess. etC) —~l_ _. selector] selectox’Z
°Requiremenrs . .

. . List of List of
(frictional p ro)p erttes, Technologies Technologies
to erances, etc Intersection

Technology!
TechnologyZ
Plan Generator Technology N
Hierarchical Planner Hierarchical Planner
Layup RTM
Hierarchical Planner Hierarchical Manner
Resin Infusion Compressnon
Moltm

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 17. Problem-Solving Architecture of COMPLAN
Figure 17 illustrates the problem-solving architecture of COMPLAN. It is

composed of two modules: Technology Selector and Plan Generator. The
technology selection module uses two independent problem solvers to select
applicable technologies based on (1) geometrical features of the component
(shape, aspect ratio, wall thickness, etc.) and (2) material features (type of resin,
fiber architecture). The technology selection problem can be viewed as a

classification problem; both problem solvers are implemented as Hierarchical

122

 

Classifiers’. The results of both problem solvers are the lists of manufacturing
technologies that satisfy all criteria given as input data.

The set of technologies that are being considered by the Technology
Selector includes Layup, Injection Molding, Filament Winding, RTM, Resin
Infusion, Sprayup, Pultrusion, Extrusion, and Compression Molding - all basic
technological processes used in the composites industry. As was noted earlier,
some of these processes are rather simple and do not require extensive
planning. However, I identified four processes (Layup, RTM, Resin Infusion, and
Compression Molding) for which process planning is a necessary requirement
because of the processes’ inherent complexity. If one or more of these
technologies are selected, COMPLAN’s planning module is activated to generate
the appropriate fabrication sequences. The remaining manufacturing processes
require only simple pre-stored manufacturing plans.

The plan generator module consists of four independent HP problem
solvers: Layup Planning, RTM planning, Resin Infusion Planning, and
Compression Molding Planning. These problem solvers are of particular interest
to this research because of the richness of the underlying planning knowledge
that allows rigorous testing of the hierarchical planing methodology developed in
this dissertation. The following sections detail the architecture, information-

processing task, and knowledge content of the problem-solvers listed above.

 

7 Hierarchical Classifier is one of the Generic Task base problem solving methods within the GT
Toolset.

123

9.1.1. Layup Planning
Figure 18 illustrates the specialists’ hierarchy of the Layup Planning

problem-solver. This hierarchy represents the task decomposition of the layup
technology. The top-level specialist is responsible for the whole process - it
relies on its three sub-specialists: preparation, Iayup‘ and curing, which
correspond to the main stages/sub-tasks of the layup technology. Subsequently,
each of these specialists uses its subordinate specialists that correspond to the
sub-tasks which can emerge during problem solving.

The top-level specialist starts the problem solving process by applying its
only method (Fig. 19). According to the method’s task order, the preparation
specialist is called first, then is followed by the curing specialist, and, finally, the
layup specialist. Although in the plan, the layup stage will precede the curing
stage. From the problem solving perspective, it is more important to determine
the method of curing. This affects the decision concerning the necessary steps
for the material layup stage. For example, if a press is to be used for curing, then
the part is not placed in the vacuum bag before curing, but, if autoclave is to be
used, then vacuum bagging is a necessary step in the process.

The preparation specialist is responsible for planning the steps for the
preparation of material and tooling. It includes tool fabrication, template creation,
and material cutting. The preparation specialist has two methods that will be
selected depending on the production size and geometrical complexity of the
product. One of the methods uses the hand-cutting step in the plan, while
another uses the machine-cutting step. Figure 20 illustrates the method-selection

table for the preparation specialist.

124

 

5, “I.

‘”~‘—:

. “an“,
..~,.:~..- d
1rd.
1 '.

 

Figure 18. Specialist hierarchy for Layup Planning Problem -Solver

125

 

 

 

 

 

.:~ ,: .:.- .

.- 7,: _ ‘2. ‘7 . __.’ 1.. 3 a; 7 ._-.-:~: 5.1;; '.‘-- ,h
geese... al.;ésoan: an»... . :5.- Makfimfigecmuy Ws

       

 

 

 

Figure 19. The Method-I‘main’ used bythe Top-Specialist of the Layup Planning
Problem-Solver

During the Preparation planning the tooLpreparation specialist is

independent from the method selected. This is a step-level specialist that uses

Routine Designer layup_tooling_RD to determine Tooling Material and Tool

Complexity. The variable Tooling Material is important for future decision making

in plan generation; it is used in the curing specialist method selection table to

determine the most appropriate-curing cycle.

    

"5 Tble acvelnlerlace

 

 

 

Figure 20. Method Selection Table for the Preparation Specialist of the Layup
Planning Problem-Solver

The full curing cycle includes the b-stage cure, final cure and post cure.

However, the first and the third stages are optional. The necessity of the b-stage

126

 

 

 

cure is determined by comparing the difference between coefficients of the
thermo—expansion of the tooling material and the product matrix material. If there
is a significant difference between the coefficients, then the b-stage is a
necessary step of the process. The necessity of the postcure depends on the
product’s functional requirements and on the resin material used. For some
resins (Chlorendic Resin, DGEBA, etc), the postcure is required to ensure high
functional properties of the final product. Figure 21 shows the curing method that

includes both the b.stage cure and the postcure in the curing cycle.

 

-‘ - -m-‘rri'

  
 
 

Y‘ .,
.7 ‘,~1— - h .
1r ""‘L‘T‘ 5' , ..- (a . m . T“- ... .

W Novella. DOEA m M. «mm

   

A _g; “b.- - —_-_‘

 

 

     

"a. -r 7"...“- H‘filb<‘_\‘v4-u——A~Q..T .--—'- A-~ ,. .. ..-‘.:«-..-—g -. .1“ . .- ”.2 ‘

 

 

 

 

 

Figure 21. An Example of the Method of Curing Specialist in Layup Planning
Problem-Solver

While the b-stage-cure and postcure are optional tasks, the final cure is
always a part of curing. The final cure specialist selects the appropriate curing
method — autoclave cure, microwave cure, oven cure, presses cure, or room cure
— and initiates the corresponding step specialist. For example, if the autoclave-
curing method was selected, the system calls the step-level specialist autoclave
cure. This specialist uses the Routine Designer Iayup_autoclave_FiD to define
the curing pressure and temperature (Fig. 22). Similarly, the step specialists for
other types of curing use corresponding Routine Designers to determine curing

parameters.

127

 

 

 

 

 

 

 

 

After the curing plan is generated, the problem solver starts the planning
of the layup. The layup sub-specialist selects either simple layup or standard
layup, depending on the selected curing method and functional requirements.
Simple layup includes material placement and debulking, while standard layup
requires the vacuum bagging as an additional procedure. If a press is used for
curing, then the simple layup method should be used. This method could also be
used for manufacturing components with low functional requirements; othenlvise,
the standard layup is used. Figure 23 illustrates the standard layup method.

To determine the sequence of steps for vacuum bagging, the bagging
specialist is called after the material placement step in the standard layup
process. The debulk specialist then defines the debulking method (autoclave,
press, pressure chamber, rolling, or vacuum) depending on the functional

requirements and resin material used.

128

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 23. Standard-layup Method of Layup Specialist Layup Planning Problem-
Solver

The cooperative effort of all the described specialists results in a plan for a
part that requires the hand layup manufacturing process.

9.1.2. RTM Planning

Figure 24 illustrates the hierarchy of specialists comprising the Resin
transfer Molding Planning problem solver. It relies on three main specialists that
store knowledge about the three main stages of the RTM technology. These
specialists are: preparation, resin transfer and curing.

The preparation stage involves tool preparation and preform. The step
specialist tool preparation calls the corresponding routine designer to determine
the appropriate tooling material and tool complexity. The tool preparation step is
followed by preforming. During prefonning, the fiber reinforcement is placed into
the tool and preformed to fit the future part shape and desired fiber architecture.
The preform specialist selects one of the methods: braiding, cut-and-place,
directed fiber, stamping, or textile performing. The selection of the preform

method is based on production size and fiber architecture of the part.

129

 

 

 

 

 

 

Figure 24. Resin Transfer Molding Planning Specialist Hierarchy

The resin transfer specialist uses its knowledge to generate a sequence of
steps needed to impregnate the fiber reinforcement with liquid resin. First, the
tool should be closed, or clamped. After that, the resin is supplied into the tool
under pressure. At the same time the tool temperature needs to be monitored to
prevent premature curing.

The curing specialist considers three possible steps: b-stage curing, final
cure, and postcure. As in the Layup process in RTM, the necessity for b-stage
curing is determined by the difference in the therrnoexpansion coefficients
between tooling material and resin material in the part. Consequently, the RTM
curing specialist selects the method containing the b-stage cure when the tooling

material selected previously in the tool preparation step has a thermoexpansion

130

 

coefficient much higher than that of resin. Unlike the b-stage cure, the final cure
step is always a part of the cure cycle. The final cure specialist selects between
two alternative methods: room cure or heat cure. If the heat cure step is added to
the plan. the corresponding heat cure specialist calls the routine designer
RTM_Heat_Curing to determine the curing temperature and heating method,
which can be one of the following: heated plates, oven, electricity, oil, steam,
microwave, or heat blanket. Finally the post cure step can be added to the plan
for some of the resins when high functional properties are required. The
sequential planning process of generating sub-plans for the three main stages of

RTM technology results in a final plan that can be used to manufacture the part.

9.1.3. Resin Infusion

 

 

Figure 25. Resin Infusion Planning Specialist Hierarchy

131

 

At the high level, the Resin infusion process, similar to Layup and RTM,
can be decomposed into three consecutive stages: preparation, resin infusion,
and curing. Corresponding specialists in the specialist hierarchy represent all
three stages (Fig. 25).

Problem solving starts by initiating the curing specialist. Although
preparation and resin infusion precede curing in the final plan, the curing
specialist has the first priority during the plan generation process, because its
decisions influence the preparation and resin infusion specialists. The curing
cycle in Resin Infusion technology consists of the final cure and optional
postcure, which is reflected in problem-solver specialist hierarchy. The final cure
specialist selects the curing method, which can be room cure or heat cure. If heat
cure was selected during problem solving, then the heat cure specialist selects
the most appropriate way of heating (heated tool, microwave oven, oven, or
press) and adds the corresponding step to the final plan. The step specialists
responsible for the heating methods used in Resin Infusion call the routine
designers to define the curing temperature and pressure.

The preparation specialist decomposes its task into tool preparation and
preform and calls subordinate specialists to continue the planning process. The
tool preparation step specialist calls the routine designer to define the tooling
material, tool complexity, and tool heating method (oil, electricity, stem, etc.), if a
heated tool will be used for curing. Next, the preform specialist selects the

preform method.

132

 

The last stage in the problem-solving process involves planning for the
steps to impregnate the fiber reinforcement with resin — the resin infusion
specialist is responsible for this task and uses its three sub-specialists. First, the
bagging specialist generates the sub-plan for bagging. Then, the concurrent
steps supply resin and apply temperature are inserted into the plan.

The problem-solving process results in the complete plan for the Resin
Infusion manufacturing technology.

9.1.4. Compression Molding

The fourth problem solver implemented in COMPLAN encapsulates
planning knowledge about Compression molding technology. The specialist
hierarchy illustrated in Figure 26 represents the specialist hierarchy for the

Compression Molding Planner.

 

Figure 26. Compression Molding Planner Specialist Hierarchy

133

 

The Top specialist uses its three sub-specialists to generate sub-plans for
the three stages of Compression molding: preparation, charging and curing.
Preparation consists of tool preparation, template preparation, and hand or
machine material cutting. During plan generation, the preparation specialist
decomposes its task into corresponding steps. The preparation specialist needs
to decide which material cutting method to use: machine or hand. This is decided
based on production size and geometric complexity of the part. Independently of
which cutting method is used, both tool preparation and template preparation are
always added to the plan. For the tool preparation step, the associated routine
designer defines the tooling material and complexity.

The charging stage follows the preparation stage. The charging specialist
selects the charging method: layup or the ‘wrap-and put’ method using input data
about functional requirements and a component's fiber architecture. Layup
charging is usually selected when high functional properties are required or
special fiber architecture is in the design specification. Otherwise a more simple
‘wrap-and-put method’ can be used.

The curing cycle consists of final curing and alternative posturing. The
final curing is always done using the press in Compression Molding. The final
curing step specialist determines the final curing temperature and pressure. As in
the other described problem solvers, the curing specialist for some resins adds
the posturing to the plan when highly functional properties are expected.

The described problem solving process, if successful, will produce the

conceptual plan for the compression molding manufacturing process.

134

9.2. Case Study
Given the summary of the description of COMPLAN, its problem-solving

architecture and knowledge content, one can now consider how the system will
function in the context of a specific problem. This section demonstrates
COMPLAN’s behavior on one sample problem. Note that this example is not
intended to provide an all-inclusive view of COMPLAN’s capabilities. The
implementation details are presented in the previous section. Additionally, the full
description of the knowledge encapsulated in the system can be found in
Appendix 1.

The user initiates the session with COMPLAN by requesting
manufacturing plans for the given design. The Database, which is responsible for
interactions with the user, requests the specific case data about the design and

design requirements. The user enters the data shown in Table 7.

 

Aspect Ratio Low
Fiber Architecture Special
Fiber Type C-Glass

Functional Requirements Medium
Geometrical Complexity High

 

 

 

Resin Material Chlorendic Resin
Production Samples

Shape Shell

Size Big

Surface Quality High

Tolerances High

Wall Thickness Thin

 

Table 9. Input Data for Sample Problem
At this point, the problem-solving process begins with the selection of the

manufacturing technology. First, Technology Selector 1 generates the following
list of technologies: Compression Molding, Filament Winding, Layup, Pultrusion,

RTM, Resin Infusion. The first list is generated based on the material properties

135

of the design. Then, Technology Selector 2 generates the list of technologies
based on the geometric properties of the design: Layup and Resin Infusion. The
final list of applicable technologies is generated as an intersection of the lists
generated by both Technology Selectors: Layup and Resin Infusion. Problem
solving proceeds by generating manufacturing plans for these technologies.

9.2.1. Meneratjon for Layup Process

The Layup Planning problem solver starts by calling its top-level specialist.
This specialist calls on the preparation specialist, then the curing specialist, and
last, the layup specialist. The preparation specialist generates the plan for the
preparation stage of the process. The steps template preparation, material
cutting, and tool preparation are added to the plan. At that time, the parameters
ToolingMaterial, and ToolingComplexity are defined for the tool preparation step.
The Layup_Tooling_RD establishes the following values: ToolingMaterial =
‘Polymers,’ ToolingComplexity = ‘very high.’

After that, the curing specialist is called to generate the plan for curing.
For the given input, the b-stage cure step is added to the plan. Also, the problem
solver selects three alternatives for the final cure step: microwave, oven, or
press. For each of these alternatives, the planning will proceed separately. As a
result, three different plans are considered from this point on. For each of the
plans, the selected final cure step will call on the related routine designer
(Layup_Autoclave_Cure_RD, Layup_Oven_Cure_RD, or
Layup_Press_Cure_RD) to determine the curing temperature. In each case, the

curing temperature selected is between 50 and150°C.

136

.2.»
..

5:30me @5565. aim; 3 8.9950 wear. metafifiacmz .w cash

r 4: .
5:1...

.1

. 11.4“:- .

 

The plan for the material layup process is generated last by the layup
specialist. The layup process depends on the type of cure that will be used. As a
result, the layup plan generated for the press-cure alternative differs from layup
plans for the autoclave and oven alternatives. In the press-cure case, the
resulting plan consists of material placement and press debulk. In the autoclave-
and oven—cure case the plan consists of material placement, peel ply placement,
breather placement, vacuum bagging, and vacuum debulk.

Table 8 shows three plans generated by the Layup Planning Specialist for
the given input data.

9.2.2. Menerflon for Resinlnfusion Process

Resin Infusion Planning proceeds from the top specialist by calling on the
curing specialist, preparation specialist, and resin infusion specialist. The curing
specialist determines the need in post cure (for a given case the final cure is not
needed) and calls the final cure specialist to generate a plan for the final cure.
The final cure specialist decides whether the heat cure is appropriate and passes
the initiative to the heat cure specialist that selects the heat cure method. For the
given problem, two methods were selected: heated tool or oven cure. Starting
from this problem-solving stage, two plans will be considered: one plan contains
the heated tool cure step for the final cure, and the other contains the oven cure
step. The final cure and oven cure step specialists will call upon corresponding
routine designers (RI_HeatedTooI_Cure_RD and RI_0ven_Cure_RD) to define
the curing temperature. For the given problem, the temperature = 50-150°C for

both curing alternatives.

138

The preparation specialist starts the plan generation by adding a tool
preparation step to the plan and calling the tool preparation specialist, which
executes Rl_Too|Preparation_RD to select the tooling material, determine tooling
complexity, and determine the most suitable tool heating method it a heated tool
is used for final curing. For the plans that are being generated, a polymer tooling
material was selected and the tooling complexity was determined to be very high.
Additionally, for the heated tool cure case, two heating methods were selected:
heat blankets and oil heating methods. At this point, three plans are generated:
one for the oven-cure case, one for the heated tool/heat blankets case, and one
for the heat tool/oil heating case. Each of these plans continues its problem
solving by calling on the preform specialist that selects the preform method. For
each of the plans, the cat-and-place preform method is selected.

Finally, the resin infusion specialist is called, which, in turn, calls on a
bagging specialist that generates the same sequence of steps for each of the
considered cases: peel ply placement, breather placement, and vacuum bagging.
The infusion specialist then adds two more steps to the plans: apply temperature
and supply resin. This concludes the plan generation of Resin Infusion for a
given set of input data. The resulting tree plans are shown in Table 9.

As a result of problem solving, COMPLAN generates six alternative plans
for the given input data. The user can browse these plans and select the one
adequate to his or her specific manufacturing environment. The selected plan
can be used for the estimation of manufacturing resources required and can also

be used as a basis for more specific production planning.

139

6:30QO mcEcmE cease. 53m 3 3.99.60 mcmi 9:292:52 .m 2%...

_w. .L— w.

 

fiv—

140

9. 3. Testing COMPLAN
An important part of this dissertation research is the validation of the

knowledge contained in COMPLAN. In many cases, validating the correctness of
the knowledge-based system requires trying it on a large number of meaningful
inputs and comparing its results against the decisions of domain experts or
examples described in related publications. Consequently, COMPLAN was
tested following this technique.

One example, the tail airfoil for the Boeing unmanned aerial vehicle
(UAV), was described in detail in (Martinez, Lukibanov et al. 1999; Lukibanov
and Martinez 2000) — the results generated by COMPLAN were compared with
those independently generated by a panel of experts (including Mr. Gary Wigel
VP of Engineering Cade Auto Air, Mr. Roger Kaminski chemical engineer Cade
Auto Air, and Dr. Jim McDowell President Mad Dog Composites). The
manufacturing plans generated by COMPLAN not only included all plans
suggested by the engineers, but also included several additional valid
technological alternatives not considered by experts. Upon questioning, the
experts indicated that they did not consider those fabrication variants, as they did
not have access to the proper equipment.

Other experiments were conducted by introducing real-life designs from
the practice of Cade AutoAir" to COMPLAN. The specific examples included an
aircraft engine bell mouth and a nose cone. A bell mouth is the front part of an

aircraft engine cover and is a part that is manufactured using hand layup with

141

autoclave curing. The solutions proposed by COMPLAN included a
manufacturing plan that was analogous to the hand layup-autoclave curing-
based plan used at Cade AutoAir. A nose cone is a part of the engine casting
assembly that is manufactured using hand layup. When a model of the nose
cone was run through COMPLAN, the generated plans were comparable to the
manufacturing sequences used in real life.

The set of examples used to verify COMPLAN capabilities was taken from
recent publications and included a Tiltrotor wing torque box (Clements 1999), a
missile launcher (Editorial 1999), and a z-stiffener for the F-22 (Editorial 1998).
For these models, COMPLAN produced manufacturing plans that consistently
reproduced real-life manufacturing practices.

The results of this study show how relevant the knowledge base and the
problem-solving strategy used in COMPLAN to the aerospace domain. The
performance of COMPLAN was also tested on examples from a variety of other
domains (automotive, sporting goods). The tests included a car quarter panel,
the Dodge Viper windshield surround, and a golf club (among others). In every
example, COMPLAN generated a list of conceptual manufacturing plans that
included those that were actually used to manufacture the product. The validation
experiments described above all show that the knowledge base and problem-
solving strategy in COMPLAN were relevant the manufacturing of polymer

composites in general.

 

8 Cade AutoAir is a Lansing, Michigan-based company that specializes in the
design and production of composite parts for aerospace, automotive and other
applications.

142

9.4. Future Extensions
COMPLAN is a prototype system that can serve as a basis for a more

sophisticated system in composite manufacturing process planning. COMPLAN
can be extended in several directions. The first type of extensions will involve
enhancing a system’s functionality. The existing COMPLAN system implemented
two out of the three elements of the proposed architecture: the technology
selector and planning. Many interesting research issues involve the problem of
plan evaluation and validation. The module performing these functions should be
able to combine generic domain knowledge about plan quality and correctness
with user-specific information relating to the importance of various plan
characteristics. One possible approach will be to use merit tables, where the plan
characteristics will be first assessed based on generic domain knowledge and
then weighted according their‘importance to a specific user. The sum of
resulting values will then represent the merit of the plan to the user, and the plan
with the highest merit will be the best plan for the given user. The merit table
approach was implemented previously in Socharis and proved to be successful.
The program shell for merit table calculations developed for Socharis can be re-
used in COMPLAN. However, the architecture and content of the domain
knowledge required for user-independent plan evaluation, as well as the exact
list of the characteristics that need to be evaluated, remain an open question.

A second extension to COMPLAN involves augmentation of its domain
knowledge by increasing the number of represented technologies and by
detailing the existing knowledge of those technologies. Currently, COMPLAN

covers four basic technologies that require multi-stage planning: Layup, RTM,

143

Resin Infusion, and Compression Molding. This list can be extended by some
less generic new technologies such as SCRIMP, High-speed RTM, Layer
Injection Molding, etc.. These technologies are often experimental or product
specific. Consequently, fewer experts are available either to train the
manufacturing/process engineers or to plan the process. As a result, this
extension of COMPLAN could be of high value.

Detailing the existing knowledge is the other possible expansion of the
COMPLAIN domain knowledge base. Several venues are available for such
detailing: enriching existing specialists to provide finer tuning for existing process
parameters or adding specialists to plan for (or plan based on) additional process
parameters that are not included currently; for example, adding specialists for
setting up temperatures for b-stage curing or b-stage curing methods.

9.5. Conclusion

COMPLAN belongs to the family of knowledge-based tools in the domain
of design and manufacturing with composite materials that was developed in the
Intelligent Systems Laboratory at Michigan State University:

0 COFATE - composite material technology selection (Moy, McDowell et al.
1995M

. COMADE - composite material design (Kamel 1994)

. RAVEN — redesign of assemblies from metal to composite (Zhou, Lenz et al.
1999)

- SOCHARIS - manufacturing process design (Martinez, Lukibanov et al. 1999)

144

These systems were created as a collaboration with many experts from
academia (MSU, University of Utah, and University of Delaware) and industry
(AutoAir Composites/CADE Industries, Lansing, Michigan; Boeing Helicopters,
Philadelphia, Pennsylvania; TacomlUS Army, Detroit, Michigan). They
encapsulate an extensive amount of knowledge in the composites domain, which
covers areas of designing materials for a specific purpose (COMADE,
MADEFAST), selecting an appropriate technology to manufacture a composite
piece (COFATE), re-designing metal structures into assemblies to be largely
composites (RAVEN), and generating a family of manufacturing alternatives for
them (SOCHARIS). COMPLAN has found a niche in a suite of tools that support
design and manufacturing with composite materials. It extends the functionality of
Socharis by not only providing the list of appropriate manufacturing technologies
for a composite artifact, but by detailing the manufacturing plan for it.

The implementation of COMPLAN tested the soundness of the
Hierarchical Planning methodology and the planning extension to the Integrated
Generic Task Toolset (Kamel, Lukibanov et al. 1997). The methodology proved
to be capable of capturing the planning knowledge in a consistent and structured
way that reflected the structure and decision-making strategy of the domain
expert. In addition, the implemented shell for the development of HP-based,
knowledge-based applications adequately completed the research path of this

dissertation.

145

10. CONCLUSION

The primary goal of this dissertation has been to develop a model of
knowledge-based planning. Achieving this goal required determining the types of
knowledge used by planning experts, the structure of this knowledge, and the
problem-solving process that results in the plan. While answering these
questions it became clear, as would be expected on theoretical grounds, that the
knowledge structure as well as the process of problem-solving largely depend on
the knowledge available to the expert. Four classes of knowledge-based
planning problems were identified.

. Class 1. Planning problems will be considered Class 1 if the effective domain
decompositions are not known and the available domain knowledge is limited
to the set of allowable actions and constraints. An example of such a problem
is maze traversal, where the knowledge about the structure of the maze is not
available a priori.

. Class 2. These are the problems where problem solving task-reduction rules
are known. However, the overall problem-solving process is not structured.
Many game-playing problems (bridge, backgammon, etc) are examples.

. Class 3. Problems where the problem-solving process is well structured,
while the resulting plan exhibits flexibility, are considered Class 3 planning
problems. Examples of such problems are cooking instructions and trip

planning.

146

Class 4 problems are the problems where both the problem-solving strategy
and the resulting plan have a fixed unalterable architecture. In this case, the
solution is usually in the form of plan parameters that then fit into the
predefined plan schema. An example of such a plan could be crop
management planning.

This taxonomy of planning problems served as a substantial aid to

understand existing planning methods with different knowledge representations.

This taxonomy also made it clear that an effective approach to Class 3 planning

problems did not exist. This dissertation research focused on the development of

an effective methodology for solving Class 3 planning problems. The specific

research goals were stated as follows:

1.

To perform a GT-based task analysis of the Class 3 planning problems, which
includes a task-subtask analysis as well as a task-level analysis of the
participating problem-solving specialists.

To develop a knowledge-level architecture of the task-subtask decomposition
of Class 3 problems — this includes the definition of information processing as
well as the inter-specialists integration architecture.

To implement a software tool which supports the developed methodology.

To construct a working knowledge-based system using the developed
methodology and software tool.

Working toward these objectives resulted in the development of a task-

specific architecture for Class 3 planning problems and a corresponding

hierarchical planning shell for developing the knowledge-based applications as

147

described in Chapter 6. The problem of planning manufacturing sequences for
composite materials was selected to test the developed approach. The resulting
knowledge-based application suite encapsulates the planning knowledge about
four composite material technologies and is capable of generating valid
manufacturing plans.

The research described in this dissertation in knowledge-based planning
lies on the borderline of two general areas: planning and knowledge-based
systems. The contributions in each of these areas are discussed in addition to
describing their contributions to the application domain. In addition, the place of
the research within the “task specific architecture” arena in general, and the
Generic Task school in particular are described. The chapter concludes with the

discussion of venues for future research.

10. 1. Contributions to the Al Area

10.1.1. Contribution to KBS
The Generic Task methodology was applied to the analysis of planning

problem solving. This result extends the applicability of the GT framework to
planning applications that require not only the fixed plan structure achieved by
multiple routine designer (Kamel, Sticklen et al. 1994), but also variable
arrangement of plan stages, as described in Chapter 5.

A task analysis of planning revealed that several sub-tasks of a Class 3
planning problem could be implemented using existing generic tasks. The
framework that was developed allowed extensive reuse of the existing types of

GT-based problem solvers as an integral part of the Hierarchical Planner. An

148

example of this is the development of COMPLAN described in Chapter 9 which
combines Hierarchical Planning, Structured Matching, and Multiple Routine

Design. This demonstrates the wide reusability of GT-based problem solvers.

10.1.2. Contributions to Al Planning
The HP methodology developed in this dissertation introduces a number

of extensions to some of the techniques currently used in the AI planing -
especially HTN planing. These enhancements specifically support Class 3
planing problems. One such augmentation is the hierarchy of specialists that
reflect the taxonomy of problem domains and make it feasible to modularize the
domain knowledge. This is in contrast to the traditional HTN method in which
knowledge is represented in a flat rule base, which (if applied to the problems of
medium or large size) entails cumbersome maintenance and execution control.
The hierarchical representation of the domain knowledge promotes efficient
application development, execution, and maintenance.

The incorporation of varying problem-solving types into the planning
application is. another distinct outcome of the research reported here. Instead of
using an RBS implementation to represent a plan’s steps, the Hierarchical
Planner utilizes GT-based problem-solvers. This gives more flexibility in the
knowledge representation and allows one to configure different problem-solving
methods to better suit the domain problem at hand, and to better match the
representation to terms understandable to domain experts. This results in more
tailored reasoning at the specialist level, including complex context checks and

multiple result handling.

149

10.2. Contributions in Composite Material Manufacturing
The domain of manufacturing with composite materials is an ideal field for

the application of knowledge-intensive methods. The reason is two-fold. First,
there is no general understanding theory for manufacturing artifacts made of
composite materials, in contrast to the area of metal fabrication. Second,
composite manufacture is driven by a rich body of empirical knowledge.
COMPLAN is a manufacturing planning system for composite components and
was developed as a part of this dissertation research to validate the methodology
of hierarchical planing. COMPLAN includes knowledge about four manufacturing
techniques that require extensive planning. As an input, COMPLAN takes the
description of the composite part and as output produces the detailed
manufacturing plan. COMPLANis a valuable tool along these dimensions:
. During design to extensively explore the design space and to match the
design with the applicable manufacturing method,
. For actual planning to avoid expensive trial-and-error methods, and
o For tutoring the novice specialist in an effort to shorten the time-to-talent
penod.
10.3. Future Research
This research has opened new paths that should be investigated in the
future:
. The use of libraries of Hierarchical Planning problem solvers which will
support the reuse of problem solvers and allow the construction of integrated

planning systems.

150

. The introduction of an evaluation module that will enable ranking the multiple
results of the Hierarchical Planner and simplifying the selection of the most
appropriate solution.

The development of libraries comprised of re-usable knowledge-based
modules is the topic of various research in the KBS community, as well as in
industrial and e-business settings. The problem of developing reusable
knowledge modules in the case of HP can be reduced to the problem of creating
modules that can solve a simple sub-task of a planning problem and integrate
them into a larger planning system. The appropriate solution should take into
consideration problems such as the use of a consistent domain ontology for
problem solvers; the mapping of ontologies of different problem solvers for
modules that use different ontologies; the effective storage and retrieval of
problem solving modules; and the creation of an index for modules. The solution
to some aspects of the integration of disparate units into a fully functional
planning knowledge-based system was suggested in [Lukibanov, 2000 #109].
This approach is based on the application of function-based modeling (FM)
(Sembugamoorthy and Chandrasekaran 1986; Hartman and Chandrasekaran
1995) to the integrated KBS design. Each problem solver is treated as a ‘black-
box,’ i.e. only its functionality and input-output information are considered. The
overall system is then assembled from these black boxes. This approach allows
the prediction of overall system behavior and the trace of the chains of cause and

effect to detect information conflicts.

151

HP-based knowledge-based planning systems in general produse multiple

feasible manufacturing plans for a single artifact design. This situation, while

preferable for exploration of the solution space, could be confusing because all

the results produced by HP are satisfactory. It and it is difficult sometimes to

determine the result that is optimal in a given situation from the output feasible

set of alternatives. Hence, the evaluation and ranking of the available results is

one of the most leveraged future extensions of the HP framework. There are

several research directions that one can pursue to solve the plan evaluation

problem:

Use the merit table approach (Lukibanov and Martinez 2000), an approach
adopted by many engineers to select a particularly good solution out of a set
of feasible alternatives. The core of this approach is in the set of merits of the
solution that are set a priori. Each merit is associated with the weight of its
“importance” to the designer. Each of the alternatives is then given a grade on
a scale of 1 to N for every merit. Next, each solution is awarded a score that
is the sum-product of the weight of the merits and grades of the solution. In
the end, all plans are ranked according to this final numeric result.

Employ an approach developed at the Ohio State University’s Laboratory for
Artificial Intelligence Research (Josephson, Chandrasekaran et al. 1998).
This method allows the user to visually select the most important metrics and
seed out the results that do not pass the optimality criteria by examining the

traces on two-dimensional charts.

152

The directions for future research described above reflect the theoretical
investigation and enhancements of HP methodology. In addition to such
theoretical study, it would be of most importance to apply the approach
developed in this dissertation to other industrial problems beside composite
manufacturing in order to validate its utility. Several candidates are: 1) planning
of stamping sequences of sheet metal components for a vehicle and 2) planning
of assembly and welding operations for a vehicle body parts.

10. 4. Final Remarks

This research addresses the problem of developing planning knowledge-
based applications which perform “Class 3” planning task. In particular, it is
concerned with the problem of knowledge acquisition and representation — the
key issues that remain an impediment to the development of large-scale
knowledge-based planning applications. This work brings together a task-specific
approach to problem solving with HTN ideas to achieve a more robust knowledge
representation architecture. The result research presented here is a methodology
that allows the representation and use of planning knowledge in a well defined
manner.

The shell for building a knowledge-based planning application was created
as an embodiment of the methodology for Class 3 planning problems. This shell
made it possible to visually develop a system for manufacturing planning -
COMPLAN. COMPLAN encompasses the knowledge about four generic
techniques from composite material manufacturing and, given the description of

the composite part, creates a family of plans capable of producing it. COMPLAN

153

in the context of this dissertation acts as a proof of principle system for the
underlying theory: Hierarchical Planning.

COMPLAN as a working prototype, the HP shell tool, and the theory of HP
are all important in the context of developing more reliable and extensible
computer support for planning industrial manufacturing processes. All are
particularly leveraged in manufacturing domains characterized by no, or at least
weak, basic theory, but rich empirical knowledge. But the single most important ,
and perhaps lasting, set of contributions of this research are the task analysis of
planning, the identification of four distinct classes of planning, which emerged
from the task analysis, and the specific identification of the Class 3 planning

problems.

154

BIBLIOGRAPHY

155

Bacchus, F. and F. Kabanza (1996). Using Temporal Logic to Control Search in
a Fonrvard Chaining Planner. New Directions in Planning. M. G. a. A. Milani, IOS
Press: 141-153.

Backstorrn, C. and P. Jonson (1995). Planning with abstraction hierarchies ca_r1
ge exponenm less efficient. lJCAl-95, Quebec, Canada.

Barros, L., A. Valente, et al. (1996). Modeling Planning Tasks. Third International
Conference on Artificial Intelligence Planning Systems, Edinburg, Scotland, AAAI
Press.

Benjamins, V. R. (1993). Problem solving methods for diagnosis. Dissertation,
Amsterdam, Netherlands, University of Amsterdam.

Benjamins, V. R., L. Barros, et al. (1996). Constructing Planners Through
Problem Solving Methods. Knowledge Acquisition Workshop, Banff, Canada.

Blythe, J. and Y. Gil (1999). A Problem-Solving Method for Plan Evaluation and
Critiguing, Banff, Canada.

Brown, D. C. and B. Chandrasekaran (1989). Design Problem Solving:
Knowledge Structures and Control Strategies. San Mateo, California, Morgan
Kaufmann Publishers, Inc.

Bylander, T. and S. Mittal (1986). “CSRL: A Language for Classificatory Problem
Solving.” Al Magazine 7(2): 66-77.

Bylander, T. A. and e. a. Goel (1988). Structured Matching: A Computationally
Feasible Technique for Making Decisions. Technical Report, Columbus, OH,
Ohio State University.

Chandrasekaran, B. (1983). "Towards Taxonomy of Problem-Solving Types.” [fl
Magazine 4(1): 9-17.

Chandrasekaran, B. (1986). “Generic Task in Knowledge-Based Reasoning:
High Level Building Blocks for Expert System Design.” EEE Expert(Fall): 24-30.

Chandrasekaran, B. (1990). “ Design problem solving: A task analysis.” _Al
Magazine: 59-71.

Chandrasekaran, B. (1993). The Functional Representation Language: A
Framework for Reasoning, Technical Report, Ohio State University.

156

Chandrasekaran, B. and T. R. Johnson (1993). Generic Task And Task
Structures: History, Critique and New Directions. Second Generation Expert
Systems. J. P. K. J.M. David, and R. Simmons, Springer Verlag.

Chandrasekaran, B., J. Josephson, et al. (1987). The Generic Task Toolset: High
Level Languages for the Construction of Planning and Problem Solving Systems.
Columbus, OH, The Ohio State University, Department of Computer and
Information Science, Laboratory for Artificial Intelligence Research.

Chandrasekaran, B. and J. R. Josephson (1997). The Ontolggy of Tasks and
Methods. Symposium on Ontological Engineering, Stanford, 0a., AAAI.

Chang, H., W. F. Lu, et al. (1998). Intelligent Case Retrieval and Modification for
machining Process Planninggf Axisvmmetric Part—s. Artificial Intelligence and
Manufacturing Research Planning Workshop, Albuquerque, NM.

Chien, S. A. (1996). Static and Completion Analysis for Planning Knowledge
Base Development and Verification. 3rd International Conference on Artificial

Intelligence Planning Systems, Edinburgh, Scotland, AAAI Press.

Clements, L. (1999). “Focus on Design: Adhesive Bonding Used in Wing Torque
Box for the World's First Commercial Tiltrotor.” High-Perfonnance
Composites(May/June): 80-82.

Currie, K. and A. Tate (1991). “O-Plan: The Open Planning Architecture.”
Artificial Intelligence 52(1): 49-86.

desJardins, M. (1994). Knowledge Development Methods for Planning Systems.
AAAI Fall Symposium on Planning and Learning, New Orleans, AAAI Press.

DMI (1998). Assuring Affordable and Producible Product Design, brochure,
Design & Manufacturing Institute (DMI),Stevens Institute of Technology.

Editorial (1998). “Joint Strike Fighter: Optimizing Composites on the JSF.” High-
Performance Composites(September/October): 42-45.

Editorial (1999). “Alliant Composites Weapons Operations.” High-Perforrnance
Composites(May/June): 1 1.

El-Sheikh, E., J. Sticklen, et al. (1996). Nemr Whegt: Integrating Expert Systems
and Crop Modeling Technolggy. 6th International Conference on Computers in
Agriculture, Cancun, Mexico, American Society of Agricultural Engineers.

Erol, K., D. Nau, et al. (1994). HTN Planning: Complexiy and Expressivigr. AAAI-
94, Seattle, WS, AAAI Press.

Erol, K., D. Nau, et al. (1994). UMCP: A Sound and Complete Planning
Procedure for Hierarchical Task-Network Planning. AlPS-94, Chicago, IL.

 

157

Fikes, R. E. and N. J. Nilsson (1971). “STRIPS: A New Approach to the
Application of Theorem Proving to Problem Solving." Artificial Intelligence 2(3/4):
189-208.

Fox, M. and D. Long (1998). “The automatic inference of state invariants in TIM.”
Journal of Artificial Intelligence Research 9.

Fox, M. and D. Long (1999). Automatic Knowledge Aguisition Support Tools for
Planning. Working notes of the PLANET TCU on Knowledge Acquisition
Workshop, Salford, UK.

Friedland, P. E. and Y. lwasaki (1985). "T he concept and implementation of
skeletal plans.” Journal of Automated Reasoning(1): 161-208.

Gupta, S. K., D. S. Nau, et al. (1994). A methodology for systematic generation
and evaluation for alternative operation plans. Advances in feature based
manufacturing. J. Shah, M. Mantyla and D. S. Nau. North Holland, Elsevier: 161-
184. .

Hammond, K. J. (1990). “Case-Based Planning: A Framework for Planning from
Experience.” Journal of CognitivLScience 14(3).

Hartman, J. and B. Chandrasekaran (1995). Functional Representation and

Understanding of Software: Technology and Application. 5th Annual Dual-Use
Technologies & Applications Conference, IEEE and Rome Lab, Utica, NY, IEEE

Press.

Hawkins, R., J. McDowell, K.,, et al. (1993). Function-Based Modeling and
TroJubleshooti_ng. AAAI Workshop on Reasoning about Function.

Hayes-Roth, B. and F. Hayes-Roth (1979). “A Cognitive Model of Planning.”
ngnitive Science 3: 275-310.

Josephson, J. and S. Josephson, Eds. (1994). Abductive Inference
Computation, Philosophy, Technology. Cambridge, Cambridge University Press.

 

Josephson, J. R., B. Chandrasekaran, et al. (1998). An Architecture for Exploring
Large Design Spaces. National Conference of the American Association of
Artificial Intelligence, Madison, Wisconsin.

Kamel, A., O. Lukibanov, I. Martinez et al. (1997). A Task Specific Architecture

for Conceptual Fabrication Seguence Planning for Structural Assemblies made
from Commsite Materials. Interfaces 1997, Montpellier, France.

Kamel, A., J. Sticklen, et al. (1994). Multiple Design: An Extension of Routine
Design for Generating Multiple Design Alternatives. Artificial Intelligence in
Design’94. J. S. G. a. F. Sudweeks. Netherlands, Kluwer Academic Publishers:
275-292.

158

Kamel, A. M. (1994). Generating Multiple Design Alternatives of Composite
Materials Using a Generic Task Approach. Computer Science. East Lansing,
Michigan State University.

Kingston, J., N. Shadbolt, et al. (1996). CommonKADS models for Knowledge
Based Planning. AAAI-96.

Knoblock, C. A. (1990). Learning abstraction himchies for problem solving.
Eighth National Conference on Artificial Intelligence, Boston, MA.

Lee, D. E. and H. T. Hahn (1996). A Coordinated Product and Process
Development Epvironment for Design for Assembly. ASME Design Engineering
Technical Conferences and Computers in Engineering Conference, Irvine, CA.

Lee, D. E. and H. T. Hahn (1997). Comparative Assembly Cost Performance

Analysis of Joint Technolggies in Composite Structures. ASC Twelfth Technical
Conference, Dearbom, MI.

Lee, D. E. and H. T. Hahn (1997). Generic Modular Operations for Virtual
Manufacturing Process Engineering. ASME Design Engineering Technical
Conferences, Sacramento, CA.

Linster, M. and M. Musen (1992). “Use of KADS to create a conceptual model of
the ONCOCIN task.” _Ignowledge Acguisition 4: 55-87.

Lukibanov, O., Martinez, I., et al. (1998), Metal to Composite Structural
Assemblies: Developing Appropriate Functional Modeling Frameworks for Static
Analysis, Functional Reasoning and Teleological Methodologies. Workshop at
the Fifteenth National Conference on Artificial Intelligence (AAAI 98), Madison,
WI.

Lukibanov, O. and I. Martinez (2000). “ Socharis: The lnstantiation of a Strategy
for Conceptual Manufacturing Planning.” Journal of Artificial Intelligence in

Engineering Design and Manufacturing.

0. Lukibanov, I. Martinez, and J. Sticklen, (2000) ,lntegrated Knowledge-Based
Systems for ,Dfiesign and Manufactgrino with Composite Materials: From Hard-
Coding to Visual Development. ICSSEA ‘2000, Software Engineering and
Applications, 13th lntemational Conference, CNAM, December 5-8, Paris FR.

Manoochehri, S. (1994). An Intelligent function-based design system for iniection
molded plastic parts. ANTEC’94.

Martinez, I., et al. (1998), flinction-based Modeling of Fabrication Plans for
Structural Assemblies, Artificial Intelligence and Manufacturing: Research
Planning Workshop on State of the Art & State of the Practice, Albuquerque, NM.

 

159

Martinez, I., O. Lukibanov, et al. (1999). Augmenting Conceptual Design with

Manufacturing: an Integrated Generic Task Approach. DETC-99/DFM99, Las
Vegas, NV, ASME.

McCluskey, T. L. and D. E. Kitchin (1998). A tool-Supmrted Approach to
Engineering HTN Planning Models. IEEE lntemational Conference on Tools with
AI, Tapei, Taiwan.

McDermott, J. (1988). “Preliminary Steps Towards a Taxonomy of Problem
Solving Methods.” Automated Knowledge Acguisition for Expert Systems.

Moy, B., J. K. McDowell, et al. (1995). Integrated Design and Agile Manufacturing

in Polvmer Matrix Composites: The Role of Intelligent Decision Support Systems.
SAMPE-1995, CA.

 

Munos-Avila, H. and F. Weberskirch (1996). Planning for manufacturing
workpiecespy strong, indexing and replaying plannimgecisions. 3rd
International Conference on Al Planning Systems (AlPS-96), Edinburgh,
Scotland.

 

 

Nau, D. S., S. K. Gupta, et al. (1995). Al Plgnning Versgs Manufacturing-
Operation Planning: A Case Study. IJCAI-95.

Newell, A. and H. A. Simon (1963). GPS: A Program that Simulates Human
Thought. Computers and Thought. R. E. A. Fiegenbaum and J. Feldman,
Oldensburg KG.: 279-293. '

Penberthy, J. S. and D. Weld (1992). UCPOP: A Sound, Complete, Partial-Order
Planner for ADL. Third lntemational Conference on Knowledge Representation
and Reasoning (KR-92), Cambridge, MA.

Pitchumani, R. and V. M. Karbhari (1994). Use of Knowledge-Based Decision

Support System for Rapid, Efficient production Planning, with Applications to
C_eramic-Matrix Composites Fabrication. Annual American Ceramics Society

Conference, Cocoa Beach, FL.

Pitchumani, R., P. A. Schwenk, et al. (1993). A knowledge-based Decision

Support System for the Manufacture of Composite Preforms. 25th SAMPE
Technical Conference, Philadelphia, PA.

Pitchumani, R., P. A. Schwenk, et al. (1994). “An Expert System Approach to
manufacturing Prefonns for Infiltration-Processing of Ceramic- and Metal- Matrix
Composites.” Processing of Advanced Materials 4(3): 155-165.

Quibble, M. D. (1998). Cost Modeling Advanced Resin Transfer Molding at Dow-
U_T. 43rd International SAMPE Symposium, Anaheim, CA.

160

Sacerdoti, E. D. (1974). “Planning in a hierarchy of abstraction spaces.” Artificial
Intelligence 5(2): 1 15-135.

Sacerdoti, E. D. (1975). Planning in a hierarchy of abstraction spaces. IJCAl-75.

Schreiber, A. T., B. J. Wielinga, et al. (1994). “CommonKADS: A comprehensive
methodology for KBS development.” IEEE Expert 9(6): 28-37.

Selman, B., T. Dean, et al. (1996). Challenge problems of artificial intelligence.
AAAI-96, National Conference on Artificial Intelligence, AAAI press.

Sembugamoorthy, V. and B. Chandrasekaran (1986). Functional Representation

of the Devices and Compilation of Diagnostic Problem Solving Systems. Hillsdail,
NJ, Lawrence Erlbaum Associates.

Simon, H. A. (1963). “Experiment with Heuristic Compiler.” J. Assoc. Comput.
Mach. 10(4): 493-506.

Steels, L. (1990). “Components of Expertise.” AI Magazine(Summer): 28-49.

Stefik, M. (1981). “Planning with Constrains (MOLGEN: Part 1).” Artificial
lnteflgence 16: 111-140.

Stefik, M. (1981). “Planning with Constrains (MOLGEN: Part 2)." Artificial
Intelligence 16: 141-170.

Sticklen, J. and B. Chandrasekaran (1985). Use of Deep Level Reasoning in
Medical Diagnosis. Government Symposium in Expert Systems.

Swartout, B., Y. Gil, et al. (1999). Representing Capabilities of Proplem Solving
Methods. IJCAl-99, Workshop on Ontologies and Problem-solving Methods,
Stockholm, Sweden.

Tate, A. (1990). Generating Project Networks. Readings in Planning. J. H. a. A.
T. J. Allen.

Tate, A., B. Drabble, et al. (1994). O-Plan2: An Open Architecture for Command,
Planning, and Control. Intelligent Scheduling. M. Z. a. M. Fox, Morgan-
Kaufmann: 213-239.

Tu, S. W., H. Eriksson, et al. (1995). “Ontology-based configuration of problem-
solving methods and generation of knowledge -acquisition tools: Application of
PROTEGE-II to protocol-based decision support.” Artificial Intelligence in
Medicine 7: 257-289.

Tu, S. W., M. G. Kahn, et al. (1989). “Episodic skeletal -plan refinement based
on temporal data.” Communications of the ACM 32(12): 1439-1455.

161

Valente, A. (1995). “Knowledge level analysis of planning systems.” SIGART
Bulletin 1: 33-41.

Valente, A., Y. Gil, et al. (1999). LIBRA: A Libragy of Knowledge Components for
EXPECT. Knowledge Acquisition Workshop’99, Banff, Canada.

Veloso, M., J. Carbonell, et al. (1995). “Integrating Planning and Learning: The

PRODIGY Architecture.” Journal of Theoretical and Experimental Artificial
Intelligence 7(1).

Webb, D., V. Gerdes, et al. (1995). Computer-Aided proce_ss flaming for Molg
Making. ANTEC'95, Boston, MA.

Wielinga, B. J. and A. T. Schreiber (1994). Conceptual modeling of large
reusable knowledge bases. Berlin, Germany, Springer Verlag.

Wilkins, D. E. (1988). Practical Planning: Extending the Classical AI Planning
Paradigm. San Francisco, CA, Morgan Kaufmann Publishers Inc.

Wilkins, D. E. (1990). “Can AI planners solve practical problems?” Computational
Intelligence 6(4): 232—246.

Wilkins, D. J. and V. M. Karbhari (1992). “Concurrent Engineering in

Composites.” nternational Journal of Materials and Product Technology 6(3):
257-268.

Zhou, K., T. J. Lenz, et al. (1999). A Problem Solving Architecture for Virtual
Protogrping in Metal to Polymer Composite Redesign. ASME-99, Las Vegas, NV.

162

APPENDIX A

163

PROBLEM SOLVER: House Construction

DATABASE

FoundationDepth

OUTPUT VARIABLE

LEGAL VALUES: full, half, unknown

QUESTION: What is the value of variable FoundationDepth?

abuseStxle
INPUT VARIABLE

LEGAL VALUES: American Cottage, Russian Hut, unknown
QUESTION: What is the value of variable HouseStyle?

Location

INPUT VARIABLE

LEGAL VALUES: midwest, north, southeast, unknown
QUESTION: What is the value of variable Location?

Soil

INPUT VARIABLE

LEGAL VALUES: Dirt, Sand, unknown, Wetland
QUESTION: What is the value of variable Sc--?

walluaterial

INPUT VARIABLE

LEGAL VALUES: board, brick, logs, unknown

QUESTION: What is the value of variable WallMaterial?

WIIIThickneel

OUTPUT VARIABLE

LEGAL VALUES: Medium, Thick, Thin, unknown

QUESTION: What is the value of variable WallThickness?

SPECIALIST HIERARCHY
-Build a House

---Build Foundation
...... Dig A Pit

------ Fill With Concrete
------ Insert_Beams
---Build Walls and Roof
------ Biu1d_Walls
------ Make A Wall Frame
------ Build A Roof
------ Make A Roof Frame
SPECIALISTS

Build a House

METHOD SELECTOR:

 

Location Iresult
I
. |WithFoundation
= southeast |Without_Foundation

METHOD: WithFoundation
Task Order: Build Walls and Roof, Build Foundation
Task Relation: Start 9 Build Foundation '9 Build Walls and Roof 9Finish

164

METHOD: Without_Foundation

Task Order: Build Walls and Roof

Task Relation: Start-9 Build Walls and Roof-9Finish
Build Foundation

METHOD SELECTOR:

 

Soil Iresult

|
= Dirt |BasementMethod
? |BeamMethod

METHOD: BeamMethod

Preconditions:
HouseStyle ~= Russian Hut
Location ~= north

Task Order: Insert Beams
Task Relation: Start 9 Insert Beams 9Finish

METHOD: BasementMethod
Task Order: Dig A Pit, Fill With Concrete
Task Relation: Start 9 Dig A Pit 9 Fill With Concrete 9Finish

Dig A Pittstep specialist)
Variables established: , FoundationDepth
Integrated RD: FoundationDepth

3111 With Concreto(step specialist)
Insert Beans (step specialist)

Variables established: , FoundationDepth
Integrated RD: FoundationDepth

 

Build walls and Root

METHOD SELECTOR:

 

HouseStyle Iresult
|
= American Cottage lWithWallFrame
= Russian Hut [WithoutWallFrame

METHOD: WithWallFrame

Preconditions:

WallMaterial ~= logs

Task Order: Make A Wall Frame, Make A Roof Frame, Build A Roof, Build
_Walls

Task Relation:

Build _Wall
Start 9Make A Wall Frame(' 5\
Finish

Make A Roof Frame 9 Build A Roof

METHOD: WithoutWallFrame

Preconditions:

WallMaterial ~= board

Task Order: Make A Roof Frame, Build A Roof, Build _Walls

165

Task Relation:
Start 9 Build _Walls 9 Make A Roof Frame 9 Make A Roof Frame 9Finish

Build 4Wa11e(step specialist)
Variables established: WallThickness
Integrated RD: WallThickness

Make A Well Frene(step specialist)

Build A Roo£(step specialist)

Make A.Roo£ Prane(step specialist)

166

APPENDIX B

167

PFKNBLIDI scumrznuzznnxmn? PIJUWNIBKB

DATABASE

Aspect_Ratio

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown

QUESTION: What is the aspect ratio of the component?

 

cure
LEGAL VALUES: autoclave, microwave, oven, press, rooms, unknown
QUESTION: What is the cure type?

fiberLiet

INPUT VARIABLE

LEGAL VALUES:AS-4 Carbon, Boron, C-Glass, E—Glass, Kevlar-149, Kevlar-
29, Kevlar-49, None, P-100 Graphite, P-SS Graphite, Quartz, S-Glass,
SiC, unknown

QUESTION: What type of fiber is used?

functional reguirenente

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown,

QUESTION: What are functional requirements to the component?

GeometricelComElexity

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What is the geometrical complexity?

preeeure
OUTPUT VARIABLE

LEGAL VALUES: high, low, moderate, unknown
QQUESTION: What is the maximum pressure required by curing process?

production

INPUT VARIABLE

LEGAL VALUES: MassProduction, MediumProduction, Samples, unknown
QUESTION: What is the size of production?

ReeinLiet

INPUT VARIABLE

LEGAL VALUES: 4,4'-MDA-BMI, ABS, ABS/PET, Aluminum, BPA Fumarate Resin,
Chlorendic resin, DGEBA, Epoxidized Phenolic Novolac, Isophthalic
Resin, Metal, Orthophthalic Resin, PA66, PAI, PAS, PBT, PC, PC/ABS.
PC/PBT, PEEK, PEI, PET, Phenolic Novolac Resin, Phenolic Resole Resin,
PMR 15 Monomers, PPO, PPS, PSU, TGETPE, TGMDA, Thermid 600 Oligomers,
unknown, Vinyl Ester Resin

QUESTION: What is the type of resin used?

eize

INPUT VARIABLE

LEGAL VALUES: big, medium, small, unknown
QUESTION: What is the size?

Surfaceguelity

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown

QUESTION: What are the requirements to the surface quality?

168

tggpgrature
OUTPUT VARIABLE

LEGAL VALUES: 150-200, ZOO-300, 25—50, 50-150, unknown
QUESTION: What is the range of temperature required for curing?

Tolerances

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What are the tolerance allowances?

Tool cggplexity
OUTPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown, very high
QUESTION: What is the complexity of the tool?

tooligggiet

OUTPUT VARIABLE

LEGAL VALUES: Aluminum, Cast, Iron, Ceramics, CRP, GRP, Nickel
Electroforms, Polymers, Steel, Tooling Foam, unknown

QUESTION: What is the tooling material to be used?

wall_Thickness

INPUT VARIABLE

LEGAL VALUES: medium, thick, thin, unknown

QUESTION: What is the thickness of the walls of the component?

SPECIALIST HIERARCHY
layup

---curing

------ b-stage

------ final cure
--------- autoclave cure
--------- microwave cure
--------- oven cure
_________ press cure
......... room cure

------ post cure

-—-1ayup*

------ bagging

--------- bag

......... breather
......... peel ply
--------- perforation
--------- vacuum

------ debulk

--------- autoclave debulk
--------- press debulk
--------- pressure chamber debulk
--------- rolling debulk
--------- vacuum debulk
------ materia1_placement
---preparation

------ hand cutting

------ machine cutting
______ template_preparation

169

______ tool_preparation

 

SPECIALISTS

E2222

METHOD SELECTOR:

Wall_Thickness |Aspect_Ratio Iresult
| l

~= thick |~= high Imain

METHOD: main

Preconditions:

resinList in (BPA Fumarate Resin, Chlorendic Resin, DGEBA, Epoxidized
Phenolic Novolac, Isophthalic Resin, Orthophthalic Resin, PEEK, PMR 15
Monomers, PPS,TGMDA, Thermid 600 Oligomers, Vinyl Ester Resin, 4,4'-
MDA-BMI, Phenolic Novolac Resin, Phenolic Resole Resin)

Task Order: preparation, curing, 1ayup*

Task Relation: Start 9 preparation9 layup*9 curing 9 Finish

 

Curing
METHOD SELECTOR:
toolingList |functional requirements |result
| I

~= Aluminum |= high Ifc-pc—method
~= Aluminum |~= high lfc-method
~= Aluminum |= high lfcl-method

= Aluminum |= high lbs-fc-pc-method

= Aluminum |~= high . lbs-fc-method

= Aluminum |= high lbs-fcl-method

METHOD: fc-method
Task Order: final cure
Task Relation: Start 9 final cure 9 Finish

METHOD: bs-fc-method
Task Order: b-stage, final cure
Task Relation: Start 9 b-stage 9 final cure 9 Finish

METHOD: fc-pc-method

Preconditions:

resinList in (4,4'-MDA-BMI,Chlorendic Resin, DGEBA, Epoxidized Phenolic
Novolac, PMR 15 Monomers, Thermid 600 Oligomers)

Task Order: final cure, post cure

Task Relation: Start 9 final cure 9 post cure 9 Finish

METHOD: bs-fc—pc—method

Preconditions:

resinList in (Thermid 600 Oligomers, PMR 15 Monomers, Epoxidized
Phenolic Novolac, DGEBA, Chlorendic Resin,4,4'-MDA-BMI)

Task Order: b-stage, final cure, post cure

Task Relation: Start 9 b-stage 9 final cure 9 post cure 9 Finish

METHOD: fol-method
Preconditions:

170

resinList not-in (Thermid 600 Oligomers, PMR 15 Monomers, Epoxidized
Phenolic Novolac, DGEBA, Chlorendic Resin,4,4'-MDA-BMI)

Task Order: final cure

Task Relation: Start 9 final cure 9 Finish

METHOD: bs-fcl-method

Preconditions:

resinList not—in (Thermid 600 Oligomers, PMR 15 Monomers, Epoxidized
Phenolic Novolac, DGEBA, Chlorendic Resin, 4,4'-MDA-BMI)

Task Order: b-stage, final cure

Task Relation: Start 9 final cure 9 post cure 9 Finish

b-stage (step specialist)
final cure

METHOD SELECTOR:

 

functional requirements |result
l
= low |c-room
~= high |c-microwave
~= high |c-oven
~= low |c-press
~= low |c-autoclave

METHOD: c-room

Preconditions:

resinList in (Thermid 600 Oligomers, PMR 15 Monomers, PPS, Vinyl Ester
Resin, Phenolic Resole Resin, Phenolic Novolac Resin, PEEK,
Orthophthalic Resin, Isophthalic Resin, Chlorendic Resin, BPA Fumarate
Resin, 4,4'-MDA-BMI)

Task Order: room cure

Task Relation: Start 9 room cure 9 Finish

METHOD: c-press

Preconditions:

Wall_Thickness = thin

Task Order: press cure

Task Relation: Start 9 press cure 9 Finish

METHOD: c-oven
Task Order: oven cure
Task Relation: Start 9 oven cure 9 Finish

METHOD: c-microwave

Preconditions:

size ~= big; production = MassProduction

Task Order: microwave cure

Task Relation: Start 9 microwave cure 9 Finish

‘METHOD: c-autoclave
Task Order: autoclave cure

Task Relation: Start 9 autoclave cure 9 Finish

ggtoclave cure(step specialist)

171

Variables established: temperature, pressure, cureType
Integrated RD: layup_autoclave_cure_RD

microwave cure(step specialist)
Variables established: temperature, pressure, cureType
Integrated RD: layup_microwave_cure_RD

oven cure(step specialist)
Variables established: temperature, pressure, cureType
Integrated RD: layup_oven_cure_RD

press cure (step specialist)
Variables established: temperature, pressure, cureType
Integrated RD: layup_press_cure_RD

roan cure (step specialist)
Variables established: , temperature, pressure, cureType

Integrated RD: layup_room_cure_RD

post cure (step specialist)

 

laxgp*
METHOD SELECTOR:

functional requirements |cureType |result

| I

? I: press Isimple layup
= low |~= press Isimple layup
~= low |~= press Istandard layupl
= low |~= press Istandard layup

METHOD: standard layup

Preconditions:

resinList not-in (Vinyl Ester Resin, Orthophthalic Resin, Isophthalic
Resin, Chlorendic Resin, BPA Fumarate Resin)

Task Order: bagging, debulk, material_placement

Task Relation: Start 9 material_placement 9 bagging 9 debulk 9Finish

METHOD: simple layup

Preconditions:

resinList in (BPA Fumarate Resin, Chlorendic Resin, Isophthalic Resin,
Orthophthalic Resin, Vinyl Ester Resin)

Task Order: debulk, material_placement

Task Relation: Start 9 material_placement 9 debulk 9Finish

METHOD: standard layupl
Task Order: bagging, debulk, material_placement
Task Relation: Start 9 material_placement 9 bagging 9 debulk 9Finish

 

22211.22
METHOD SELECTOR:
resinList Iresult
I
? |simp1e bagging
? [standard bagging

172

METHOD: standard bagging

Preconditions:

rxesinList not-in (BPA Fumarate Resin, Chlorendic Resin, Isophthalic
Resin, Orthophthalic Resin, Vinyl Ester Resin)

'Task Order: peel ply, perforation, breather, bag, vacuum

Task Relation: Start 9 peel ply 9 perforation 9 breather 9 bag 9
vacuum 9 Finish

METHOD: simple bagging
Preconditions:

resinList in (BPA Fumarate Resin, Chlorendic Resin, Isophthalic Resin,
Orthophthalic Resin, Vinyl Ester Resin)

Task Order: peel ply, breather, bag, vacuum
Task Relation: Start 9 peel ply 9 breather 9 bag 9 vacuum 9 Finish

Egg (step specialist)
breather (step specialist)
peel 21: (step specialist)
perforation (step specialist)

vacuum.(step specialist)

 

debulk
METHOD SELECTOR :
functional requirements Iresult
I
= low |d-rolling
= medium |d-pressure-chamber
= medium Id-vacuum
= high |d-press
= high |d-autoclave
= low |d-pressure-chamber1
= low |d—vacuuml

METHOD: d-rolling
Preconditions:

resinList in (BPA Fumarate Resin, Chlorendic Resin, Isophthalic Resin,
Orthophthalic Resin, Vinyl Ester Resin)
Task Order: rolling debulk

Task Relation: Start 9 rolling debulk 9 Finish

METHOD: d-pressure-chamber

Preconditions:

size ~= big

Task Order: pressure chamber debulk

Task Relation: Start 9 pressure chamber debulk 9 Finish

METHOD: d-vacuum
Task Order: vacuum debulk
Task Relation: Start 9 vacuum debulk 9 Finish

METHOD: d-press

173

Preconditions :

Wall_Thickness ~= thick

'Task Order: press debulk

Task Relation: Start 9 press debulk 9 Finish

METHOD: d-autoclave
Task Order: autoclave debulk
Task Relation: Start 9 autoclave debulk 9 Finish

METHOD: d-pressure-chamberl

Preconditions:

size ~= big

resinList not-in (Vinyl Ester Resin, Orthophthalic Resin, Isophthalic
Resin, Chlorendic Resin, BPA Fumarate Resin)

Task Order: pressure chamber debulk

Task Relation: Start-9 pressure chamber debulk'9’Finish

METHOD: d-vacuuml

Preconditions:

size = big

resinList not-in (Vinyl Ester Resin, Orthophthalic Resin, Isophthalic

Resin, Chlorendic Resin, BPA Fumarate Resin)
Task Order: vacuum debulk

Task Relation: Start 9 vacuum debulk 9 Finish
autoclave debulk (step specialist)

press debulk (step specialist)

pressure chamber debulk (step specialist)
rolling debulk (step specialist)

vacuum debulk (step specialist)
material_placement (step specialist)

preparation

METHOD SELECTOR :

 

production |Geometrica1Complexity Iresult

I |
= MassProduction |~= High Imachine cutting
= MassProduction I: High |hand cutting
= MediumProduction |~= High Imachine cutting
= MediumProduction |? |hand cutting
= Samples I? |hand cutting

METHOD: hand cutting

Task Order: hand cutting, template_preparation, tool_preparation
Task Relation: Start 9 hand cutting 9 template_preparation 9
tool_preparation 9 Finish

METHOD: machine cutting
Task Order: machine cutting, template_preparation, tool_preparation

174

Task Relation: Start 9 machine cutting 9 template_preparation 9
tool_preparation 9 Finish
hand cutting_(step specialist)

Smachine cuttipL ( step specialist)

tmlate prepa_ration (step specialist)
tool preEation (step specialist)

Variables established: Tool complexity, toolingList
Integrated RD: layup_tooling_RD

175

APPENDIX C

176

PROBLEM SOLVER: RTM Planning

DATABASE

MctJlatio

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown

QUESTION: What is the aspect ration of the component?

Curing temperature
OUTPUT VARIABLE
LEGAL VALUES: 100—200, 200-300, 25-100, unknown
QUESTION: What is the required curing temperature temperature?

£ iherArchitecture

INPUT VARIABLE

LEGAL VALUES: braided, chopped, chopped SM, continous SM,
quasiIsotropic, special, unidirectional, unknown woven,
QUESTION: What is the fiber architecture?

functional rquirements
INPUT VARIABLE
LEGAL VALUES: high, low, medium, unknown
QUESTION: What are the functional requirements?

Geometricalgggplggigx
INPUT VARIABLE
LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What is geometrical complexity?

Beating method

OUTPUT VARIABLE .

LEGAL VALUES: electric heat blanket heated platens microwave no heating
oil oven steam unknown

QUESTION: What is the appropriate heating method?

production
INPUT VARIABLE
LEGAL VALUES: MassProduction’ MediumProduction’ Samples unknown
QUESTION: What is the production size?

resinList

INPUT VARIABLE

LEGAL VALUES: 4,4'-MDA-BMI, ABS, ABS/PET, Aluminum, BPA Fumarate Resin,
Chlorendic resin, DGEBA, Epoxidized Phenolic Novolac, Isophthalic
Resin, Metal, Orthophthalic Resin, PA66, PAI, PAS, PBT, PC, PC/ABS.
PC/PBT, PEEK, PEI, PET, Phenolic Novolac Resin, Phenolic Resole Resin,
PMR 15 Monomers, PPO, PPS, PSU, TGETPE, TGMDA, Thermid 600 Oligomers,
unknown, Vinyl Ester Resin

QUESTION: What is the type of resin used?

s

INPUT VARIABLE

LEGAL VALUES: beam, casting, closed_she11, rotation_figure, shell,
unknown

QUESTION: What is the shape of the component?

sise
INPUT VARIABLE

 

177

LEGAL VALUES: big, medium, small, unknown

QUESTION: What is the size of the component?
Surfaceggality

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown

QUESTION: What is the required surface quality?

Tolerances
INPUT VARIABLE
LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What are the tolerance allowances?

Tool cggplexitx
OUTPUT VARIABLE
LEGAL VALUES: high, low, medium, unknown, very, high
QUESTION: What is the value of variable Tool complexity?

Tooliggggterial
OUTPUT VARIABLE

LEGAL VALUES: Aluminum, Cast, Iron, Ceramics, CRP, GRP, Nickel
Electroforms, Polymers, Steel, Tooling Foam, unknown
QUESTION: What is the tooling material to be used?

wall_Thickness
INPUT VARIABLE
LEGAL VALUES: medium, thick, thin, unknown
QUESTION: What is the wall thickness of the component?
SPECIALIST HIERARCHY
-RTM
---curing
------ b-stage
______ final cure
--------- heat curing
--------- room curing
------ postcure
---preparation
------ preform
--------- braiding
--------- cut-and-place
--------- directed fiber
--------- stamping
--------- textile preforming
______ tool preparation
---resin transfer
...... apply pressure
______ apply temperature

 

------ clamping

------ supply resin

SPECIALISTS

REM

METHOD SELECTOR:

shape Iresult
|

= casting Imain

= rotation_figure [main

= shell Imain

178

METHOD: main

Preconditions:

resinList in (4,4'-MDA—BMI,Vinyl Ester Resin, Thermid 600 Oligomers,
TGMDA, TGETPE, PMR 15 Monomers, Phenolic Novolac Resin, Orthophthalic
Resin, isophthalic Resin, DGEBA, Epoxidized Phenolic Novolac,
Chlorendic Resin, BPA Fumarate Resin)

Aspect_Ratio ~= high

Wall_Thickness ~= thin

Task Order: preparation, curing, resin transfer

Task Relation: Start 9 preparation9 resin transfer 9 curing 9 Finish

 

Curigg
METHOD SELECTOR:
ToolingMaterial lfunctional requirements [result
I |
~= Aluminium |= high lfc-pc method
~= Aluminium |~= high Ifc method
~= Aluminium |= high |fc1 method
= Aluminium |= high lbs-fc-pc method
= Aluminium |~= high lbs-fc method
= Aluminium |= high lbs-fcl method

METHOD: fc method
Task Order: final cure
Task Relation: Start 9 final cure 9 Finish

METHOD: bs-fc method
Task Order: b-stage, final cure
Task Relation: Start 9 b—stage 9 final cure 9 Finish

METHOD: fc-pc method

Preconditions:

resinList in (Thermid 600 Oligomers, PMR 15 Monomers, Phenolic Resole
Resin, Phenolic Novolac Resin, Epoxidized Phenolic Novolac, DGEBA,
Chlorendic Resin,4,4'-MDA-BMI)

Task Order: final cure, postcure

Task Relation: Start 9 final cure 9 postcure 9 Finish

METHOD: bs-fc-pc method

Preconditions:

resinList in (Thermid 600 Oligomers, PMR 15 Monomers, Phenolic Resole
Resin, Phenolic Novolac Resin, Epoxidized Phenolic Novolac, DGEBA,
Chlorendic Resin,4,4'—MDA-BMI)

Task Order: b-stage, final cure, postcure

Task Relation: Start 9 b-stage 9 final cure 9 postcure 9 Finish

METHOD: fcl method

Preconditions:

resinList not-in (Thermid 600 Oligomers, PMR 15 Monomers, Phenolic
Resole Resin, Phenolic Novolac Resin, Epoxidized Phenolic Novolac,
DGEBA, Chlorendic Resin,4,4'-MDA-BMI)

Task Order: final cure

Task Relation: Start 9 final cure 9 Finish

179

METHOD: bs-fcl method

Preconditions:

resinList not-in (Thermid 600 Oligomers, PMR 15 Monomers, Phenolic
Resole Resin, Phenolic Novolac Resin, Epoxidized Phenolic Novolac,
DGEBA, Chlorendic Resin, 4,4'-MDA-BMI)

Task Order: b-stage, final cure

Task Relation: Start 9 b—stage 9 final cure 9 Finish

h-stage (step specialist)

final cure
METHOD SELECTOR:

 

functional requirements lresult
= low Iroom curing method
? |heat curing method

METHOD: room curing method

Preconditions:

resinList not-in (Epoxidized Phenolic Novolac, Phenolic Novolac Resin,
PMR 15 Monomers, TGETPE, TGMDA, Thermid 600 Oligomers, 4,4'-MDA-BMI)
Task Order: room curing

Task Relation: Start 9 room curing 9 Finish

METHOD: heat curing method
Task Order: heat curing
Task Relation: Start 9 heat curing 9 Finish

heat curing (step specialist)
Variables established: Curing temperature, Heating method
Integrated RD: RTM_Heat_curing

roam.curing(step specialist)
ppstcure(step specialist)

preparation

METHOD SELECTOR:
resinList |result

? |preparation method

 

METHOD: preparation method
Task Order: tool preparation, preform
Task Relation: Start 9 tool preparation 9 preform 9Finish

prefomn

METHOD SELECTOR:
production lfiberArchitecture Iresult

 

~= Samples |= braided Ibraiding method
~= Samples |= special Itextile preforming method
~= Samples |= woven Itextile preforming method

180

? |= chopped Idirected fiber method
? |= chopped SM Istamping method
? I: continuos SM Istamping method
~= MassProduction I? |cut-and-place method

METHOD: braiding method
Task Order: braiding
Task Relation: Start 9 braiding 9Finish

METHOD: stamping method
Task Order: stamping
Task Relation: Start 9 stamping 9Finish

METHOD: cut-and-place method

Preconditions:
fiberArchitecture ~= braided
fiberArchitecture ~= chopped

Task Order: cut-and-place

Task Relation: Start 9 cut-and-place 9Finish

METHOD: directed fiber method

Task Order: directed fiber

Task Relation: Start 9 directed fiber 9Finish
METHOD: textile preforming method

Task Order: textile preforming

Task Relation: Start 9 textile preforming 9Finish
braiding(step specialist)

cut-and-placetstep specialist)

directed fiber(step specialist)

stpgping(step specialist)

textile preformigg(step specialist)

tool prgparation(step specialist)

Variables established: Tool complexity, ToolingMaterial
Integrated RD: RTM_tool_preparation_RD

resin transfer

METHOD SELECTOR:
resinList Iresult

? Iresin transfer method

 

METHOD: resin transfer method
Task Order: clamping, apply pressure, supply resin, apply temperature

181

Task Relation:
apply pressure

Start.-> clamping apply temperature Finish
supply resin

gpply pressure (step specialist)

gpplx tggpgrature (step specialist)

sleppipp_(step specialist)

supplx resin (step specialist)

182

APPENDIX D

183

PROBLEM SOLVER: Resin Infusion Planning
DATABASE
ct_Ratio
INPUT VARIABLE
LEGAL VALUES: high low medium unknown
QUESTION: What is the aspect ration of the component?

Curegxpg
OUTPUT VARIABLE

LEGAL VALUES: heated tool microwave oven press room unknown
QUESTION: What type of cure is required?

fiberArchList

INPUT VARIABLE

LEGAL VALUES: braided, chopped, chopped SM, continuos SM.
quasiIsotropic, special, unidirectional, unknown, woven
QUESTION: What is the fiber architecture?

ResinList

INPUT VARIABLE

LEGAL VALUES: 4,4'-MDA-BMI, ABS, ABS/PET, Aluminum, BPA Fumarate Resin,
Chlorendic resin, DGEBA, Epoxidized Phenolic Novolac, Isophthalic
Resin, Metal, Orthophthalic Resin, PA66, PAI, PAS, PBT, PC, PC/ABS.
PC/PBT, PEEK, PEI, PET, Phenolic Novolac Resin, Phenolic Resole Resin,
PMR 15 Monomers, PPO, PPS, PSU, TGETPE, TGMDA, Thermid 600 Oligomers,
unknown, Vinyl Ester Resin

QUESTION: What is the type of resin used?

functional requirements

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown,

QUESTION: What are functional requirements to the component?

 

GeometricalComplexigy

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown

QUESTION: What is geometrical complexity of the component?

Beatinggmethod

OUTPUT VARIABLE

LEGAL VALUES: electric, heat blanket, heated platens, microwave, no
heating, oil, oven, steam, unknown

QUESTION: What is heating method need to be used?

pressure
OUTPUT VARIABLE

LEGAL VALUES: high, low, moderate, unknown
QUESTION: What is the pressure required for curing?

production
INPUT VARIABLE

LEGAL VALUES: MassProduction, MediumProduction, Samples, unknown
QUESTION: What is the size of the production?

size
INPUT VARIABLE
LEGAL VALUES: big medium small unknown

 

184

QUESTION: What is the size of the component?

stdlemberList
INPUT VARIABLE
LEGAL VALUES: beam, casting, closed_shell, rotation_figure, shell,
unknown
QUESTION: What is the shape of the component?

SurfaceQualitx
INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What is the required surface quality?

tggpgrature
OUTPUT VARIABLE
LEGAL VALUES: 150-200, 25-50, 50-150, unknown
QUESTION: What is the required curing temperature?

tolerance
INPUT VARIABLE
LEGAL VALUES: High, Low, Medium, unknown
QUESTION: What are the tolerance allowances?

Tool cggplexitx
OUTPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown, very high
QUESTION: What is the tool complexity?

tooliEEEEterial
OUTPUT VARIABLE

LEGAL VALUES: Aluminum, Cast, Iron, Ceramics, CRP, GRP, Nickel
Electroforms, Polymers, Steel, Tooling Foam, unknown
QUESTION: What is the tooling material to be used?

wall_Thickness
INPUT VARIABLE
LEGAL VALUES: medium, thick, thin, unknown
QUESTION: What is the wall thickness of the component?
SPECIALIST HIERARCHY
—Resin Infusion
---curing
------ final cure
_________ heat cure
------------ heated tool
............ microwave cure
............ oven cure
............ press
......... room cure
------ postcure
_--preparation
------ preform
--------- braiding
--------- cut-and-place
--------- directed_fiber
--------- stamping
--------- textile_preforming
------ tool preparation

185

——-resin infusion*
...... apply temperature
------ bagging
--------- bag
......... breather
————————— peel ply
--------- perforation
......... vacuum
...... suply resin
SPECIALISTS

Resin Infusion

METHOD SELECTOR:
Aspect_Ratio |Wall_Thickness Iresult

~= high I: thin Imain

 

METHOD: main

Preconditions:

resinList in (Orthophthalic Resin, Isophthalic Resin, Epoxidized
Phenolic Novolac, DGEBA, Chlorendic Resin, Thermid 600 Oligomers,
TGMDA, TGETPE, PMR 15 Monomers, BPA Fumarate Resin)

sthemberList ~= closed_shell

sthemberList ~= rotation_figure

Task Order: curing, preparation, resin infusion*

Task Relation: Start 9 preparation 9 resin infusion* 9 curing 9
Finish

 

curing

METHOD SELECTOR:

functional requirements Iresult
I

= high |fc-pc

= high |fc1

~= high |fc

METHOD: fC

Task Order: final cure
Task Relation: Start 9 final cure 9 Finish

METHOD: fc-pc

Preconditions:

resinList not-in (BPA Fumarate Resin,TGETPE,TGMDA,)

Task Order: final cure, postcure

Task Relation: Start 9 final cure 9 postcure 9 Finish

METHOD: fcl

Preconditions:

resinList in (BPA Fumarate Resin, TGETPE, TGMDA)
Task Order: final cure

Task Relation: Start 9 final cure 9 Finish

final cure

186

METHOD SELECTOR:

 

functional requirements Iresult
? |heat cure method
~= low Iroom cure method

Method: heat cure method
Task Order: heat cure
Task Relation: Start 9 heat cure 9 Finish

METHOD: room cure method

Preconditions:

resinList not-in (Orthophthalic Resin, Isophthalic Resin, Chlorendic
Resin, Thermid 600 Oligomers, PMR 15 Monomers, BPA Fumarate Resin)
Task Order: room cure

Task Relation: Start 9 room cure 9 Finish

heat cure

METHOD SELECTOR:

 

functional requirements I production Iresult
I |

= high |~= Samples |press method

= high I? Ioven cure method

= medium I? Ioven cure method

= medium |~= Samples Imicrowave method

= medium I~= MassProduction |heated tool method
= low I? Ioven cure method

= low |~= Samples Imicrowave method

METHOD: heated tool method
Task Order: heated tool
Task Relation: Start-9>heated tool 9 Finish

METHOD: microwave method

Preconditions:

size ~= big

Task Order: microwave cure

Task Relation: Start 9 microwave cure 9 Finish

METHOD: oven cure method
Task Order: oven cure
Task Relation: Start 9 oven cure 9 Finish

METHOD: press method

Preconditions:

Wall_Thickness = thin

Task Order: press

Task Relation: Start 9 press 9 Finish

heated tool (step specialist)
Variables established: , temperature, pressure, cureType
Integrated RD: RI_heated_tool_cure_RD

187

microwave cure(step specialist)
Variables established: , temperature, pressure, cureType
Integrated RD: RI_microwave_cure_RD

oven cure(step specialist)
Variables established: , temperature, pressure, cureType
Integrated RD: RI_room_cure_RD

press(step specialist)
Variables established: , temperature, pressure, cureType
Integrated RD: RI_press_cure_RD

room cure(step specialist)
Variables established: , temperature, pressure, cureType
Integrated RD: RI_room_cure_RD

ppstcure(step specialist)

 

prepgration
METHOD SELECTOR:
resinList Iresult
|
? Iprep method

METHOD: prep method
Task Order: tool preparation, preform
Task Relation: Start 9 tool preparation 9 preform 9 Finish

preform

METHOD SELECTOR:
production IfiberArchList Iresult

 

I I

I
II

~= Samples I= braided Ibraiding
~= Samples I= special |textile_preforming
~= Samples |= woven |textile_preforming
? I: chopped |direct_fiber
? I= continous SM Istamping
? I chopped SM Istamping

|

‘0 II

MassProduction |cut-and-place

METHOD: braiding
Task Order: braiding
Task Relation: Start 9 braiding9 Finish

METHOD: cut-and—place
Preconditions:
fiberArchList ~= braided
fiberArchList ~= chopped
Task Order: cut-and-place
Task Relation: Start-9 cut-and-place'9*Finish

METHOD: direct_fiber
Task Order: directed_fiber

188

Task Relation: Start-9>directed_fiber'9'Finish

METHOD: stamping
Task Order: stamping

METHOD: textile_preforming
Task Order: textile_preforming
Task Relation: Start-9 textile_preforming-9’Finish

Braiding (step specialist)
cut-and-place (step specialist)
directed_fiher(step specialist)
Eggppip!(step specialist)

textile_preforminp(step specialist)

tool prgpgrationlstep specialist)

Variables established: Heating method, Tool complexity, toolingMaterial
Integrated RD: RI_tool_preparation_RD

resin infusion*

METHOD SELECTOR:
resinList Iresult

? Iinfusion method

 

METHOD: infusion method
Task Order: bagging, apply temperature, supply resin
Task Relation:

apply temperature
Start 9 bagging 4 >Finish

supply resin

apply tggpgrature (step specialist)

 

bagging
METHOD SELECTOR:
resinList Iresult
I
? Istandard bagging
? Isimple bagging

METHOD: standard bagging

Preconditions:

resinList not-in (Vinyl Ester Resin, Orthophthalic Resin, Isophthalic
Resin, Chlorendic Resin, BPA Fumarate Resin)

Task Order: peel ply, perforation, breather, bag, vacuum

Task Relation:

Start 9 peel ply 9 perforation 9 breather 9 bag 9 vacuum 9 Finish

189

METHOD: simple bagging
Preconditions:
resinList in (Vinyl Ester Resin, Orthophthalic Resin, Isophthalic

Resin, Chlorendic Resin, BPA Fumarate Resin)

Task Order: peel ply, breather, bag, vacuum

Task Relation:

Start 9 peel ply 9 breather 9 bag 9 vacuum 9 Finish

pgp_(step specialist)
hreather(step specialist)
pgel plx(step specialist)
perforation(step specialist)
vacuumtstep specialist)

supplx resin(step specialist)

190

APPENDIX E

191

PROBLEM SOLVER: COMPRESSION MOLDING PLANNING
DATABASE

égpgct_Ratio

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown

QUESTION: What is the value of variable Aspect_Ratio?

fiberArchList

INPUT VARIABLE

LEGAL VALUES: braided, chopped, chopped SM, continous SM,
quasiIsotropic, special, unidirectional, unknown, woven
QUESTION: What is the fiber architecture?

functional requirements

INPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown

QUESTION: What are the functional requirements to the component?

CemetricalCoapl—exfl

INPUT VARIABLE

LEGAL VALUES: High, Low, Medium, unknown

QUESTION: What is geometrical complexity of the component?

pressure-ksi

OUTPUT VARIABLE

LEGAL VALUES: 0.5—1.5, 1.5-3.5, unknown

QUESTION: What is the range of pressure required for curing?

production

INPUT VARIABLE -

LEGAL VALUES: MassProduction, MediumProduction, Samples, unknown
QUESTION: What is the production size?

resinList

INPUT VARIABLE

LEGAL VALUES: 4,4'-MDA—BMI, ABS, ABS/PET, Aluminum, BPA Fumarate Resin,
Chlorendic resin, DGEBA, Epoxidized Phenolic Novolac, Isophthalic
Resin, Metal, Orthophthalic Resin, PA66, PAI, PAS, PBT, PC, PC/ABS,
PC/PBT, PEEK, PEI, PET, Phenolic Novolac Resin, Phenolic Resole Resin,
PMR 15 Monomers, PPO, PPS, PSU, TGETPE, TGMDA, Thermid 600 Oligomers,
unknown, Vinyl Ester Resin

QUESTION: What is the type of resin used?

Tgppgrature
OUTPUT VARIABLE

LEGAL VALUES: 150-200, 200-250, 250-350, unknown
QUESTION: What is the range of temperature required for curing?

Tool cggplexitx
OUTPUT VARIABLE

LEGAL VALUES: high, low, medium, unknown, very high
QUESTION: What is the complexity of the tool?

tooligfibilt
OUTPUT VARIABLE

LEGAL VALUES: Aluminum, Cast, Iron, Ceramics, CRP, GRP, Nickel
Electroforms, Polymers, Steel, Tooling Foam, unknown

192

QUESTION: What is the tooling material to be used?

wall_Thickness

INPUT VARIABLE

LEGAL VALUES: medium, thick, thin, unknown
QUESTION: What is the thickness of the walls of the component?
SPECIALIST HIERARCHY

Compression Molding

---charging

------ layup

------ wrap-and-put

---curing

------ final curing

------ postcuring

---preparation

------ hand cutting

------ machine cutting

------ template preparation

------ tool preparation

SPECIALISTS
gggpression Moldipp

METHOD SELECTOR:

 

fiberArchList Iresult
= special Imain
= quasiIsotropic Imain

METHOD:main

Preconditions:

Wall_Thickness ~= thick

Aspect_Ratio ~= high

resinList in (Vinyl Ester Resin, PPO, Phenolic Novolac resin, PET,
PC/PBT, PC/ABS, PBT, PA66, Orthophthalic Resin, Isophthalic Resin,
Epoxidized Phenolic Novolac, DGEBA, Chlorendic Resin, BPA Fumarate
Resin, ABS/PET, ABS)

Task Order: preparation, charging, curing

Task Relation: Start 9 preparation9 charging 9 curing 9 Finish

 

chagping
METHOD SELECTOR:
functional requirements IfiberArchList Iresult
I I
~= high I: special Ilayup method
~= high |~= special Iwrap-and-put method
= high I? Ilayup method

METHOD: layup method
Task Order: layup
Task Relation: Start 9 layup 9 Finish

METHOD: wrap-and-put method

Task Order: wrap-and-put
Task Relation: Start 9 wrap-and-put 9 Finish

193

Laxgp (step specialist)

wrpp-and-ppt(step specialist)

 

curing
METHOD SELECTOR:
functional requirements [result
I
~= high Ifc method
= high [fc-pc method
= high |fc1 method

METHOD: fc method
Task Order: final curing
Task Relation: Start 9 final curing 9 Finish

METHOD: fc-pc method

Preconditions:

resinList in (Orthophthalic Resin, Isophthzlic Resin, Phenolic Novolac
Resin, Epoxidized Phenolic Novolac, DGEBA, Chlorendic Resin)

Task Order: postcuring, final curing

Task Relation: Start 9 final curing 9 postcuring 9 Finish

METHOD: fcl method

Preconditions:

resinList not-in (Orthophthalic Resin, Isophthalic Resin, Phenolic
Novolac Resin, Epoxidized Phenolic Novolac, DGEBA, Chlorendic Resin)
Task Order: final curing

Task Relation: Start 9 final curing 9 Finish

final curing(step specialist)
Variables established: pressure-ksi, temperature

Integrated RD: CM_curing_RD

Postcurinp (step specialist)

 

prepgration
METHOD SELECTOR:
production [GeometricalComplexity [result
I I
= MassProduction |~= High [machine cutting method
= MassProduction [= High |hand cutting method
= MediumProduction I~= High [machine cutting method
= MediumProduction I? [hand cutting method
= Samples I? [hand cutting method

METHOD: hand cutting method ,

Task Order: tool preparation, template preparation, hand cutting

Task Relation: Start 9 tool preparation 9 template preparation 9 hand
cutting 9 Finish

METHOD: machine cutting method

194

Task Order: tool preparation, template preparation, machine cutting
Task Relation: Start 9 tool preparation 9 template preparation 9
machine cutting 9 Finish

hand cutting (step specialist)

machine cuttinglstep specialist)

tgpplate preparation(step specialist)

tool preparation(step specialist)
Variables established: Tool complexity, toolingList
Integrated RD: CM_Tooling_RD

195