AI Planning Versus Manufacturing-Operation Planning: A Case Study

1 Introduction

AI planning techniques can potentially be useful in sev­ eral manufacturing domains. However, with the ex­ ception of manufacturing scheduling, previous appli­ cations of AI planning technology to manufacturing (cf. [Famili et al., 1992]) generally have had little im­ pact on manufacturing practices [Ham and Lu, 1988; Nevins and Whitney, 1989; Shah et al. , 1994].

One reason for this difficulty appears to be the dif­ ferent world views of AI planning researchers and manu­ facturing planning researchers. The first author works in both worlds- and his work on manufacturing planning has significantly influenced his research on AI planning, and vice versa-but this influence is not particularly ev­ ident in the publications themselves, because they were written to address two different audiences, who have dif­ ferent ideas of what the important problems are and how they should be solved:

*This work was supported in part by NSF Grants DDM9201779, IRI-9306580, and NSFD EEC 94-02384. Any opin­ ions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessar­ ily reflect the views of the National Science Foundation.

I Also with: National Institute of Standards and Technol­ ogy, Manufacturing Systems Integration Division, Building 220, Room A-127, Gaithersburg, MD 20899.

• Since AI planning researchers are usually more interested in general conceptual problems than domain-dependent details, the AI approach to man­ ufacturing planning has typically been to create an abstract problem representation that omits unim­ portant details, and look for ways to solve the ab­ stract problem. From the viewpoint of the manu­ facturing engineer, these "unimportant details" of­ ten are very important parts of the problem to be solved-and this can lead manufacturing engineers to view AI planning techniques as impractical.
• Manufacturing planning researchers typically want to solve a particular manufacturing problem, and present their research results within the context of this problem, without discussing how the approach might generalize to other planning domains. For AI researchers, this makes it difficult to see what the underlying conceptual problems are, or whether the approach embodies a general idea that can be applied to other problems. This can lead AI plan­ ning researchers to view manufacturing planning as a domain full of ad-hoc, domain-specific programs rather than general principles and approaches.

Some of the issues arising in manufacturing planning are similar to issues investigated in AI planning, and others are distinctly different. Some of the former may amenable to the use of existing AI planning techniques­ and some of the latter may lead to new principles useful in AI planning. However, to investigate such issues, AI researchers will need a better understanding of manufac­ turing problems and concerns, so as to get better ideas of what the interesting generalizations are, and which techniques from AI might best be applied to realistic manufacturing problems.

In this paper we attempt to provide a step in this di­ rection, by describing the planning techniques used in IMACS, a computer system for helping designers pro­ duce designs that are easier to manufacture [S. Gupta et al., 1994b; S. Gupta and Nau, 1995]. IMACS analyzes the manufacturability of proposed designs for machined parts by generating and evaluating operation plans for the proposed design. We discuss similarities and differ­ ences between the techniques used in IMACS and those typically used in AI planning. We also describe how one ofiMACS 's planning techniques (the enumeration of rel­ evant tasks before planning begins) may be useful for AI planning in general-and as an example, we describe how it helps to explain a puzzling complexity result in AI planning.

2 A Case Study: IMACS

IMACS (Interactive Manufacturability Analysis and Cri­ tiquing System) is a computer system for analyzing the manufacturability of machined parts, in order to help designers produce designs that are easier to man­ ufacture. Further information about IMACS, including color images produced using it, are available at http:// www.cs.umd.edu/projects/cim/imacsjimacs.html.

As shown in Figure 1, IMACS evaluates the manufac­ turability of a proposed design by generating and eval­ uating operation plans. Here are two immediate differ­ ences between IMACS and many AI planning systems:

• Unlike most AI planners, IMACS generates more than one plan and evaluates the merit of each plan it generates, to find an optimal plan. To measure plan merit, IMACS uses an estimate of the plan's man­ ufacturing time, as described in Section 2.6. How­ ever, it is straightforward to incorporate estimates of production cost as well [S. Gupta et al., 1994c].
• We are developing ways for IMACS to suggest changes in the design to improve its manufactura­ bility while still fulfilling the designer's intent [Das et al., 1994; 1995]. In AI terms, this means auto­ matically suggesting changes to the goal to make it easier to achieve.

Other differences and similarities are discussed in the following sections.

2.1 Machined Parts

A machined part, P, is the final component created by executing a set of machining operations on a piece of stock, S. For example, Figure 2 shows a socket P0 , and the stock So from which Po is to be produced. Note that the goal to be achieved (i .e., the part to be pro­ duced) is represented not as a set of predicates as is often done in AI planners, but instead as a CAD model (which IMACS represents using ACIS, a solid modeling system from Spatial Technologies Inc.).

An operation plan is a sequence of machining opera­ tions capable of creating the part P from the stock S. Since it would be physically impossible to produce P's exact geometry, designers give design tolerance specifica­ tions (e.g. , see Figure 3) to specify how much variation from the nominal geometry is allowable in any physical realization of P. A plan is considered capable of achiev­ ing the goal if it can create an approximation of P that satisfies the design tolerances.

A workpiece is the intermediate object produced by starting with S and performing zero or more machining operations. Currently, the machining operations consid­ ered in IMACS include end milling, side milling, face milling and drilling operations, on a three-axis verti­ cal machining center. Each machining operation creates a machining feature . Different researchers use different definitions of machining features; as shown in Figure 4, we consider a machining feature to include information about the type of machining operation, the material re­ moval volume (the volume of space in which material can be removed), and the accessibility volume (the volume of space needed for access to the part).

2.2 Feature Extraction

Although much past work on integrating design with manufacturing planning has involved feature-based de­ sign techniques in which users specified designs directly as sets of form features, most researchers have become convinced that a single set of features cannot satisfy the requirements of both design and process planning­ instead, some form of feature extraction is needed. For IMACS, we have developed algorithms to extract ma­ chining features directly from the CAD model [Regli et al. , 1994; S. Gupta et al., 1994a].

There can be many-sometimes infinitely many­ different machining features capable of creating various portions of a given part. Of these, we define a primary feature to be a feature that contains as much of the stock as possible without intersecting with the part, and as lit­ tle space as possible outside the stock . Figure 5 shows examples of primary and non-primary features; for a de­ tailed definition see [S. Gupta and Nau, 1995].

As described in [S. Gupta et al., 1995; Regli et al., 1995], in every operation plan that IMACS will ever want to consider, each machining operation will create either a primary feature or a truncation of a primary feature­ and the number of primary features for a part is always finite (in fact, polynomial). Thus, IMACS's first step is to find the set :F of all primary features for P and S. For example, for the socket Po the set :F contains 22 primary features, a few of which are shown in Figure 6.

In AI terms, machining operations are elementary ac­ tions and machining features are tasks. :F is the set of all tasks that might ever be relevant for achieving the goal. Unlike most AI planners, IMACS finds this set in advance before it begins to generate plans-but as we discuss later , this technique may be useful in a number of AI planning problems.

2.3 Generating Incomplete Plans

Figure 6 shows that the features in :F may overlap in complicated ways, and not all of them are needed to cre­ ate the part (for example, we do not need to machine both s1 and s2). A feature-based model (FBM) is any irredundant subset of features F ~ :F such that sub­ tracting those features from S produces P. For example, Figure 7 shows an FBM, FBM1, for the socket P0 .

In AI planning terminology, an FBM is an incomplete plan: if we can machine the features in it, this will create the part. Since each FBM is a subset of :F, FBM's can be generated using set-covering techniques, but there can be exponentially many FBM's. As an example, for the socket Po, :F contains 22 primary features from which one can form 512 FBM's. In general, we usually will not want to generate all of these FBM's, for only a few of them will lead to good operation plans. Thus IMACS does a depth-first branch-and-bound search to gener­ ate and test FBM's one at a time, pruning unpromising

{b) ordering constraints

:-----seiiipT ----:

i s4 ~:

' ~.

·--- ___________ ___ ..

5

h ~:

setup 3

i

------------------------------- _j

FBM's as described in Section 2.7. For example, IMACS generates only 16 of the 512 FBM's for the socket P0 .

In many of the early generative process planning sys­ tems (e.g., [Chang and Wysk, 1985; Nau and Chang, 1986; Nau, 1987]), the input was a symbolic representa­ tion of P as a set of machining features analogous to a single FBM, with no way to recognize or handle many of the geometric interactions among the features . This prevented such systems from generating realistic process plans for complex parts, in which geometric interactions can make it quite difficult to decide what sets of fea­ tures and machining operations to use, which operations to do when and in which setups, and how to hold the workpiece during each setup.

In one way or another, most recent work on gen­ erative process planning (both by manufacturing re­ searchers and AI researchers) has tried to address these difficulties (e.g., [Kambhampati et a/., 1992; Vanden­ brande and Requicha, 1993; Opas and Miintylii, 1994; S. Gupta et a/. , 1994b; Das et a/., 1994; Hayes, 1995; Britanik and Marefat, 1995]) . However, there are also some recent AI · efforts at process planning that unfor­ tunately do not seem to address such difficulties at all. We suspect one reason for this is that the researchers involved in these efforts lack sufficient familiarity with the problem domain- and Section 4 describes a way whereby we hope to alleviate this problem.

2.4 Resolving Goal Interactions

An FBM is basically a totally unordered plan. To resolve goal interactions, IMACS adds ordering constraints as follows:

• Identify ordering constraints. Due to complex ge­ ometric interactions (accessibility etc.), some fea­ tures must precede others. For example, in Fig­ ure 8, the hole h1 must be machined before the slot s9 in order to achieve reasonable machining toler­ ances and avoid tool breakage.
• Linearize. Next IMACS generates all total order­ ings consistent with the precedences. If no such total ordering can be found, IMACS considers the FBM F to be unmachinable and discards it . Unlike the typical approaches used in AI planners , there would be no point in adding additional operators: they would just create redundant features, and if there is a feasible way to machine the part it will be found among the other FBM's.

(c) process details

• Modify goals. Suppose features f and g overlap, and f precedes g in some total ordering. Then when we machine f, we are also machining part of g. We don't want to machine that same portion of g again later in the sequence, because we would merely be machining air. Thus, IMACS truncates g to remove the portion covered by f . As an example, several of the features shown in Figure 8(a) were produced by truncating the corresponding features in FBMl.
• Unlinearize. Once the truncated features have been produced, several of the resulting FBM's may have identical features but different precedence con­ straints. In such cases the precedence constraints that differ can be removed, translating the total or­ ders into partial orders. For example, Figure 8(b) shows the partial order for the FBM of Figure 8(a) .

2.5 Additional Steps

To obtain an operation plan from the partially-ordered FBM, IMACS uses the following steps:

• Incorporate finishing operations. For faces with tight surface finishes or tolerances, IMACS adds finishing operations, with precedence constraints to make them come after the corresponding roughing operations. Currently, one finishing operation per face is allowed.
• Determine setups. On a three-axis vertical ma­ chining center, features cannot be machined in the same setup unless they have the same approach di­ rection . This and the partial ordering constraints can be used to determine which features can be machined in the same setup, as shown in Fig­ ure 8(b ). Although the specific computations are different, the problem is a special case of what is known to AI researchers as the plan-merging problem [Yang et al., 1992; Foulser et al., 1992; Britanik and Marefat, 1995].
• Determine process details. To select cutting param­ eters such as those shown in Figure 8( c), IMACS uses the recommendations of the Machinability Data Center's handbook [Machinability Data Cen­ ter, 1980]. The maximum recommended cutting pa­ rameters are used, rather than attempting to se­ lect optimal cutting parameters; thus IMACS's es­ timates involve considerable approximation.

As shown in Figure 9, these steps correspond to a task decomposition somewhat analogous to that used in HTN planning [Sacerdoti, 1977; Tate, 1977; Wilkins, 1990; 1988; Yang, 1990; Kambhampati and Hendler, 1992; Erol et al., 1995a; 1994].

Since each FBM can lead to several different opera­ tion plans, IMACS does the above steps inside a depth­ first branch-and-bound search, evaluating the plans as described in Section 2.6 in order to find the optimal op­ eration plan. For example, Figure 8 shows the operation plan IMACS finds for the socket Po.

Total Time: 39 mmutes

2.6 Operation Plan Evaluation

Once IMACS has found an operation plan, it evaluates whether the plan can achieve the design tolerances. To verify whether a given operation plan will satisfy the design tolerances, IMACS must estimate what toler­ ances the operations can achieve. Typical approaches for computer-aided tolerance charting are computation­ ally very intensive, and only consider limited types of tolerances [Ji , 1993; Mittal et al., 1990]. Thus , IMACS simply evaluates the manufacturability aspects of a wide variety of tolerances without getting into optimization aspects, as described in [S. Gupta and Nau, 1995]. As an example, the operation plan shown in Figure 8 sat­ isfies the tolerances shown in Figure 3, and thus is an acceptable way to make Po from So.

If the plan can achieve the design tolerances, then IMACS estimates the plan's manufacturing time. The total time of a machining operation consists of the cut­ ting time (when the tool is actually engaged in machin­ ing) , plus the non-cutting time (tool-change time, setup time , etc.). Methods have been developed for estimat­ ing the fixed and variable costs of machining operations; our formulas for estimating these costs are based on stan­ dard handbooks related to machining economics, such as [Winchell, 1989; Wilson and Harvey, 1963]. As an exam­ ple, Table 1 shows the estimated production time for the operation plan of Figure 8.

2. 7 Efficiency Considerations

As described in [S. Gupta et al., 1994b; S. Gupta and Nau, 1995], IMACS uses a depth-first branch-and-bound search to generate and evaluate FBM's and plans one at a time . By evaluating them as they are being gener­ ated and keeping track of the best one it has seen so far, IMACS can discard FBM's and plans that look un­ promising, even before they have been fully generated. For example, from the 22 primary features shown in Fig­ ure 6 one can form 512 FBM's for the socket P0 , but IMACS generates only 16 of these FBM's. Below are some of IMACS's pruning criteria, which can be thought of as similar to critics in HTN planning:

• IMACS will discard an FBM if it contains features whose dimensions and tolerances appear unreason­ able. Examples would include a hole-drilling oper­ ation having too large a length-to-diameter ratio;

a recess-boring operation having too large a ratio of outer diameter to inner diameter; two concentric hole-drilling operations with tight concentricity tol­ erance and opposite approach directions.

• IMACS will discard an FBM if it appears that there will be problems with work-holding during some of the machining operations. Currently, IMACS's work-holding analysis is based on the assumption that a flat-jaw vise is the only available fixturing device [Das et al., 1994; 1995], but we are cur­ rently developing some more sophisticated fixtura­ bility analysis techniques that allow the use of both vise clamping and toe clamping.
• IMACS will compute a quick lower bound on the machining time required for an FBM or plan, and will discard the FBM or plan if this lower bound is above the time required by the best plan seen so far.

3 Discussion

Since we did not care whether or not we were doing AI planning in IMACS, there are several differences between the techniques used in IMACS and those used in classi­ cal AI planning systems. Some of these techniques may be useful for AI planning. For example, IMACS's tech­ nique of finding all primary features before beginning to generate plans can be generalized as follows :

• Enumerate the set of all tasks that might ever be relevant. Call this set :F.
• Loop:
• Generate an incomplete plan F as a subset of :F
• If the plan F has a goal interaction that can't be resolved via precedence constraints, discard it. (If a promising plan exists, it will be generated in another loop iteration.)
• Flesh out the plan (using task decomposition, crit­ ics, plan merging, etc.)

This technique should be useful whenever it is feasible to enumerate in advance the set :F of all relevant tasks. More specifically, suppose that we can construct :F in polynomial time, and that each task in :F will need to be achieved at most once. Then every plan we will care to consider is a subset F ~ :F, and we can generate these plans nondeterministically in polynomial time. If each goal interaction involves at most a constant number of tasks, then we can determine in polynomial time whether whether there are ordering constraints sufficient to make F a successful plan.

This idea helps to explain a puzzling theoretical problem. In the worst case, planning with STRIPS­ style operators is PSPACE-complete [Erol et al., 1994; 1995b], but the best known example of STRIPS-style planning is blocks-world planning, which is only NP­ complete [N. Gupta and Nau, 1991; 1992]. This discrep­ ancy can be explained by noting that in a blocks-world problem containing n blocks there are only at most 2n possible relevant tasks: for each block b, we might want to move b to the table, and if the goal state contains on(b, c) for some c, then we will want to move b to c.

4 Conclusions and Future Work

IMACS shows that it is possible to address manufactur­ ing planning both realistically and in a principled man­ ner. Our work on IMACS has been well accepted by manufacturing researchers, and we have many ideas for further work on IMACS and on other issues relevant to manufacturing.

Furthermore, some of us (together with Jim Hendler at the University of Maryland) 1 are beginning the devel­ opment of a test bed in which to compare AI and man­ ufacturing techniques. We intend to develop a collec­ tion of manufacturing planning problems and solutions (e.g., designs, plans, and planning systems) , presented in a way that is accessible to AI planning researchers for use as a test set or benchmark set. We hope that this will help AI researchers discover ways to apply AI tech­ niques to manufacturing planning in a realistic manner, and possibly to discover issues arising in manufacturing that may be useful for AI planning in general.