A Model of Planning for Plan Efficiency: Taking Advantage of Operator Overlap

1 Introduction

Many planners understand and exploit negative interactions ~tween. goals to organize a plan, but few exploit positive Interactions to a large degree. (A negative interaction hap­ pens when accomplishing one goal hinders accomplishing anoth~r, . and a positive interaction happens when ac­ complis~g one goal helps to accomplish the other.)

One 1mportant use of positive interactions is to make plans more efficient However, relatively little attention has ~n given to P?Sitive interactions. During the mid 70's, the pr1IDary planmng problem was how to automatically generate plans at all, so although early "classical planners" [Flk~s, 1972, Sacerdoti, 1974, Scacerdoti, 1975] considered effiC?Iency to some extent, it was not their primary goal. Durmg the late 70's and 80's, plan efficiency was given a little more attention and a few researchers such as [Wesson, 1977], Wilenski [Wilensky, 1983], and Hammond £H;ammond, 1988] have examined the use of positive inter­ actio~ as a means of achieving it. The pwpose of this p~r 1s to focus on one particular type of positive inter­ action called operator overlap, the special difficulties that it presents, and to describe some behaviors observed in human machinists. for making the search for near optimal plans more effiCient. The real difficulty to be addressed in this paper is not in recognizing that operator overlap can be used to make plans more efficient, but in knowing what factors influence operator overlap, and how can to reduce the search in this very difficult problem of attempting to make near optimal plans.

·nus project was funded by the Machinist Expert Consortium and Air Force Grant Contract #F33615-86-C-5-38.

2 Operator Overlap

There are many ways in which positive interactions can occur.I In particular, this paper focuses on operator overlap: positive interactions that occur when two operators share work. Wilensky's concepts of partial plan overlap and plan overlap "in which the execution of a single action ful­ ~. a number of goals simultaneously,"2 are very similar in spmt to operator overlap.

As an example of plan overlap, suppose one had four errands to run: pick-up cash at grocery store cash machine, drop off letters at the post office, pick-up ice cream at the grocery store, and buy stamps at the post office. The "buy stamps" and "drop off letters" operators can be said to over­ lap in terms of their destination: both are done at the post office. "Pick-up cash" and "pick-up ice cream" also share a destination, the grocery store. If one does the errands in the order they are listed above, one has to go through the effort of getting to the grocery store and the post office twice. However, if one groups "buy stamps" and "drop off letters" together, and "pick-up cash" and "pick-up ice cream" togethe~, then one only has to go to each place once (assummg one has enough cash at the beginning to buy the stamps.)

Operator overlap can be further divided into two kinds: those with temporal dependancies, and those witllout It is this first type of operator overlap that we are concerned with in ~s paper, in which results disappear if not used im­ mediately. For example, the condition of being at the post office goes away if you go to the grocery store between buying stamps and mailing the letters. However, the con­ dition of "having money" will not necessarily change if you ~o some other o~ratio~ between buying stamps and buying 1ce cream. This particular kind presents additional dif­ ficulties because the cost of accomplishing each goal is de­ pendent not only on the operator used to accomplish it, but also on the order of the operators. Wilensky refers to this as

1Wliensky, "Planning and Understanding," Addison-Wesley, 1983, Chapter 10: Positive Goal Relationships, pp. 113-126.

2Wlienski, Planning and Understanding, Addison-Wesley, 1983, p. 119.

"partial plan overlap," although a different name might capture the nature of the problem better. .

Because the cost of an operator is dependent on its order, near optimum integer programming techniques such as those proposed by [Bard, 1989] and [Kusiak, 1985] cannot be adapted to this problem. In those models, it is assumed that the cost of the operation is not dependent on its order in the plan.

3 The Structure of the Machining Problem

In the type of machining problems discussed in this paper, the objective is to start with a rectangular block of metal and to use a three axis vertical computer numeric controlled (CNC) machining center to cut a variety of shapes or features into the block (see figure 1). The part shown has five features: two angles, a slot and two holes. Each hole is tapped (threaded) and chamfered (beveled) on the bottom side (side 4). The taps and chamfers are considered to be sub-features of the holes. The two angles form a 90 degree comer where they meet

To put the machining problem into classical planning terms: each geometric feature or sub-feature: hole, angle, pocket, etc., is a goal. The initial state is a prismatic block of metal. The machining plan must successfully achieve a conjunct of all these goals to make the part. For each goal, there may be a number of methods (operators) that can be used to accomplish that goal. For example, some operators which could be considered for making the angles are shown in figure 2. Each method specifies a methodforfuturing of clamping the part, an orientation of the part, and a tool for cutting it. Each of these methods can be accomplished on the machining center; the machining center can perform a large variety of different types of operations such as drilling, milling, etc., but it can only do one operation at a time.

4 Overlapping Machining Operators

In order to form an efficient machining plan, one must over­ lap the operators that compose the plan as much as possible. As implied earlier, the idea is to shorten the plan by choos­ ing for each goal the operator that overlaps the most with the other operators in the plan. Goals (features) that overlap are grouped together. The length of the plan is roughly minimized when one has formed a minimum number of such overlapping groups.

In any problem domain there is usually a number of ways in which operators can overlap; the primary way in which it happens for CNC machining operators is by sharing fixture set-ups. Ajixture set-up refers to the way in which the part is oriented and clamped before it is cut. Set-up usually accounts for a large portion of the time cost of each operator: sometimes as much of 90% of the time may be spent in setting-up for one machining operation. It is as­ sumed that all other costs are relatively small compared to set-up time, so that minimizing the number of set-up will approximately minimize the total cost of the plan. Although this assumption does not always hold, it is a fairly good rule of thumb. Human machinists use this same heuristic for minimizing the plan cost.

CNC machining operators may also overlap in other ways, such as by sharing the same tool. One can also short­ en the plan by minimizing the number of times the tool must be changed: operators that use the same tool can be grouped together in the plan to avoid having to change the tool. However, it is much more time consuming to change a set­ up than to change a tool, so these other types of overlap are typically considered only after set-up overlap has been con­ sidered. In any domain, it is important to know when the cost of one type of operator overlap consistently dominates another. If such a situatiop occurs, the problem can be decomposed nicely into two nearly independent sub­ problems; first the plan is optimized for the bigger savings (i.e. fixture set-up), second; within each fixture group formed the plan is optimized for the lesser saving (i.e. tool changes) with in each group.

5 A Machining Example of Operator Overlap

The example will be draw from a study of the part shown in figure 1. Let us consider the two features Angle 1 and Angle 2. Angle 1, shown in figure, can be made by any the methods shown in figure 2. Each of these methods represents one possible machining operator that could be used to make Angle 1. (There are many other methods not shown, which will also work.)

Each machining operator is described by an orientation of the part, a set of fixtures, and a set of tool types. The first method, (figure 2.a) the fixture is a sine table tilted at 25.5°, the tool is a face mill, and the orientation with respect to the sine table is: side 2 facing right, and side 1 facing up. Fix­ tures are devices used to clamp work pieces or hold them steady. All of the operators shown in figure 2.a, b and c can be described respectively as:

When forming a plan one must choose only one of these operators for making Angle L Op l.c, which uses the vise, turns out not to be a good choice for this situation, but 1.a and l.b, which both use the sine table, are both reasonable ~hoices .. In fact, if the decision was based only on local informatton, op La would be preferred slightly over op l.b However, the best operator choice should be based on bow it affects the whole plan, not just on what is best for one individual feature.

Let us examine Angle 2 to see how it affects operator choice for Angle 1. The operators that can produce Angle 2 ~ roughly the same as those used for angle 1, except that etther the tool type or the orientation is different

As with Angle 1, the most preferable operator choice for Angle 2 based on local information only is to face mill the angle on a sine table: op 2.b. Thus, if we use only local preferences, we would make a plan in which Angle 1 and Angle 2 ~each made in separate set-ups: Angle 1 would be made wtth op La by face milling with the sine table tilted at.2~.5°, ~d An¥le 2 would be made with op 2.b by face milling wtth the sme table tilted at 64.5 degrees.

However, we can make a more efficient plan by taking operator overlap into account. To overlap, the set-ups must be exactly the same: both must use the same fixture and the same part orientation. Note that two pairs of operators over­ lap; La overlaps with 2.a, and l.b overlaps with 2.b. Each of ~ese overlapping pairs forms a group of two features which share a set-up. All the operators in a group can be combined into ~ new single operator. If operators 1.a and 2.a were combmed they would form the following new operator:

If operators l.b and 2.b were combined they would form the following new operator:

If we ~se ei!her of these new combined operators, we ba':e to stde mill one of the angles, which is locally sub­ opttmal. However, the advantage of being able to combine two set-ups into one far outweighs the disadvantage of side milling one of the angles. So a better (i.e. more efficient) pl!W than the one ~ropo~ above, would use op 3.a: face mill Angle 1, and stde mill Angle 2 on a sine table tilted at 25.SO. So the local operator preference to face mill Angle 2 turned out to be incorrect.

6 Additional Complexities

In the previous section we presented a basic model of ope~or overlap. However, we note two problems. First, the p~cture presented was a much simplified one; there are additlonal temporal constraints that must be considered when operator overlap is integrated into the planning problem as a whole. Secondly, searching for overlapping operators ~ the minimum number of set-ups could be a very expenstve process. The real problem is how to do the search efficiently.

Addressing the first problem: when looking for operator overlap, in addition to checking that operators can share the same set-up, one must also check that temporal constraints do not interfere with grouping of operators. For instance, going back to our errand example where we had to get ~tamps and mail letters at the post office, and get cash and 1ce cream at the grocery store, what if you needed to get money before you buy stamps, and you need stamps to mail the ~etters, and you hav~ to ~o everything else before buying ~e tee cream because 1t will melt, then it may not be pos­ stble to group get cash and get ice cream into one trip to the grocery store. In other words, in order to overlap, not only must two operato.rs share wo.Ik, but it must also be possible to execute them m one conuguous sequence. The point is that any temporal restrictions on the problem must be con­ sidered before deciding what operators can overlap.

Temporal constraints come from at least two sources: operator preconditions and negative interactions between operators. . Having money is a precondition to buying stamps or tee cream, and the fact that the ice cream will melt while you are at the post office is a negative interaction between the buying ice cream and the the time required to execute the other operators. Thus, one needs to look for operator preconditions and negative interactions before do­ ing the overlap analysis shown in the previous section. Finding negative interactions for machining problems is dis­ cussed in more detail in [Hayes, 1987a] and [Hayes, 1987b].

Addressing the second problem, "bow can the search for overlapping operators be done efficiently?" Let us first ex­ plore why searching for operator overlap can be expensive. An obvious but rather inefficient way to look for overlap would be to generate all possible operators for making all features, then look for all pairs of operators that can share set~ups , and then find a minimum set of operator groups. This last step can be quite expensive if there are many fea­ tures could possibly be placed in many groups. The first step ·. generate all possible operators, can also be quite ex­ penstve; there are often many ways to make one particular fea~. In fact, new operators can be created during the ~lanmng process so the number of ways of making a par­ tlcul~ . feature are potentially infinite. For example, machinists often design new tools or fixtures in the course of planning, which is essentially creating a new planning operators. Designing new planning operators is a very time consuming process, but it is often key in generating a short plan; ~e loD:ge.r a mac~t thinks about the problem the more likely 1t ts that be will be able to think up a clever operator that results in a large amount of overlap with other operators. However, it is clearly important to limit the generation of new operators. (A detailed examples of operator design and a more extended discussion can be found in [Hayes, 1989])

Observations of human machinists suggest ways around this problem. First they, do not necessarily take the time to find the plan with the absolute minimal number of set-ups. Secondly, it seems that human machinists rarely generate all of the alternative methods (operators) for producing any particular feature. Most of the applicable operators that could be generated are not useful much of the time. However it is difficult to know in advance which operators to generate and which not to. Going back to our angle example from figure 1, typically it is not useful to side mill an angle, so one might think that one should not generate that operator. However, in this particular case, because Angle 1 and Angle 2 were 90° apart, it turned out to be useful.

It seems that what the machinists are doing is considering a set of commonly used alternat!_ves first. Additional more esoteric operators such as side milling an angle on the sine table, are considered only when "cues" in the problem sug­ gest that they might be useful. In this case, the cue was that the angles were 90° apart. Like esoteric operators, it seems that new operators are not designed unless a cue in the problem or a higher level goal indicates that it might be fruitful to do so.

Observations of human planners support this hypothesis. Three protocols were taken of different expert machinists (each subject in this study had more than 18 years of experience) making plans for the part shown in figure 1. Only one subject noticed that Angle 1 and Angle 2 were 90° apart; and he was the only one to produce a plan in which both angles were done in one set-up. His statements imply that combining the steps was a direct result of noticing the 90° cue:

Subject: "Then because you have me stuck on a ver­ tical machine -- are these two faces 90 degrees from each other? ... Sure looks like 90 degrees to me."

Experimenter: "Yeah. Yeah, 'cause I remember that as being 90 degrees."

Subject: "Then I fmish the part in one more setting. I'm gonna put it up on a sine plate ... clamp it down."

The other two machinists, who did not notice the 90° angle, only considered making the angles by more standard methods. They each produced a plan in which the angles were made in two separate set-ups. These observations seem to indicate that noticing the cue was crucial in leading the machinist to consider non-standard methods.

In some ways this strategy is similar to one employed by Hammond's TRUCKER, "TRUCKER avoids the hard work of conjunctive goal planning unless execution time cues in­ dicate that such planning will be fruitful."3 However, the strategies employed here are not used to avoid planning en­ tirely, but to reduce the search that needs to be done.

These observations can be summarized into the following method:

• For each goal (feature) generate a few com­ monly used, standard operators.
• Use cues in the problem specification to direct search for additional, less standardly used operators, or to indicate when it is useful to design new ones.

3Hammond, et al., Proceedings of AAAI-88, vol. 2, p. 537.

• Add temporal restnct:Ions between operators, produced by operator preconditions and nega­ tive interactions.
• Compare across goals (features) for positive in­ teractions: look for operators that can be grouped together into set-ups. The temporal constraints found in the previous step will sometimes prevent two operators from being grouped together.
• Choose operator groupings that result in the fewest possible number of set-ups. (Machinist uses a greedy algorithm to do this.)

This method is implemented in the Machinist program.

7 Discussion

First, it is important to note that the cues used positive inter­ actions are quite different than those used for finding nega­ tive interactions described in [Hayes, 1987a). The cues used in negative interactions identify an interaction, and suggest an operator ordering that will avoid the interaction, while the cues used in positive interactions are used to to limit the number of operators that need to be considered.

Second, the program's performance was compared against 4 humans ranging in experience from 2 years to 5 years. Each of the machinists and the program were presented with the same 3 parts and asked to produce a plan for it. The average plan length for each machinist and the program are shown below in figure 3. There is no average listed for the two second year machinists because they did not manage to make feasible plans for all three parts. Since the plans were of different lengths, a partial average would not have been meaningful.

1bere are several interesting things to note about this comparison. It is not shown on the graph but the least experienced machinists (the two second year apprentices), tended to make the shortest plans. However, they were short because they left out important steps, and even when they did manage to make a feasible plan it was usually judged by expert machinists to be of poor quality. Most likely it was good luck rather than good design when their plans did work.

1be apprentice of mid-level experience, the third year ap­ prentice, tended to make the longest plans. He was consis­ tently able to make a feasible and reliable plan for all three parts. If the Machinist program contained no efficiency strategies, it would make plans that look similar to those of the third year apprentice; He made no attempt to to combine or merge steps. At his stage of development it was difficult enough for him to make correct plans; it was too complex for him to worry about efficiency issues in addition.

Although the program made slightly longer plans than the fifth year machinist (6.33 steps compared to 6.00 steps on the average) the program's plans were judged to be of better quality by expert machinists. A quality comparison of these same plans was reported in [Hayes, 1987a]. In this study, two expert machinists rank ordered the plan form best to worst in a blind test. The program's plans ranked higher than any of the humans' plans on the average. The point is that length is not the only measure of quality in a plan. Efficiency is important, but a certain degree of robustness must be maintained as well.

Since then the Machinist program bas undergone much development. Another study comparing the program's per­ formance to that of human machinists (i.e. more than 10 years experience) using more complex parts, is currently underway.

8 Conclusions

Operator overlap represents one kind of positive interaction that can be used to improve plan efficiency. The machining domain offers a case study of operator overlap in realistic planing problems. The research reported here describes a particular kind of operator overlap in which the cost of operators are dependent on their order in the plan. Ad­ ditionally, the overlapping portions of the operators must account for the majority of the cost of each operator. This situation arises in many manufacturing problems and in er­ rand running problems where travel times are large.

The idea is to shorten the plan by grouping together operators that overlap. The main difficulty, however, is to find an efficient method of searching for a near optimal set of such groupings. Human machinists have been observed to use a method that reduces the size of the search problem: only commonly used operators are explored, unless a learned cue in the problem tells them that other methods are likely to lead to cost savings through overlap. For example, since the angles were 90° apart, it indicated that the work could be done in one set-up if side milling on the sine table was used.

Finding operator overlap is complicated by the fact that temporal restrictions, created by negative interactions and operator preconditions, must also be considered before deciding which operators can be overlapped.

Additional problem decompositions can be achieved if the problem contains several types of operator overlap where one type almost always gives you a bigger savings than the other type, such as fixture set-up changes and tool changes. Then the problem can be decomposed into two nearly independent subproblems; first the plan is optimized for the bigger savings (i.e. fixture set-up), second, with in each fixture group formed, the plan is optimized for the lesser saving (i.e. tool changes) with in each group.

The planning strategies described here are implemented in the Machinist program. In a comparison with humans it was shown to produce plans that were almost as efficient, and slightly more robust than those of a machinist with 5 years experience.

9 Acknowledgments

A special thanks to Gregg Lebovitz Paul Wright, Dan Bar­ rish, David Bourne, Tom Freund, Dan McKeel and Jim Dil­ linger, for their participation in this project.