The task in the manufacturing process planning domain is to find a plan to manufacture a set of parts. We implemented a PbR translation of the domain specification in [55]. This domain contains a variety of machines, such as a lathe, punch, spray painter, welder, etc, for a total of ten machining operations. The operator specification is shown in Figures 18 and 19. The features of each part are described by a set of predicates, such as temperature, painted, has-hole, etc. These features are changed by the operators. Other predicates in the state, such as has-clamp, is-drillable, etc, are set in the initial state of each problem.
As an example of the behavior of an operator, consider the polish operator in Figure 18. It requires the part to manufacture to be cold and that the polisher has a clamp to secure the part to the machine. The effect of applying this operator is to leave the surface of the part polished. Some attributes of a part, such as surface-condition, are single-valued, but others, like has-hole, are multivalued. Note how the drill-press and the punch operators in Figure 18 do not prevent several has-hole conditions from being asserted on the same part. Other interesting operators are weld and bolt. These operators join two parts in a particular orientation to form a new part. No further operations can be performed on the separate parts once they have been joined.
The measure of plan cost is the schedule length, the (parallel) time to manufacture all parts. In this domain all of the machining operations are assumed to take unit time. The machines and the objects (parts) are modeled as resources in order to enforce that only one part can be placed on a machine at a time and that a machine can only operate on a single part at a time (except bolt and weld which operate on two parts simultaneously).
|
|
We have already shown some of the types of rewriting rules for this domain in Figures 7 and 10. The set of rules that we used for our experiments is shown in Figure 20. The top eight rules are quite straightforward once one becomes familiar with this domain. The two top rules explore the space of alternative orderings originated by resource conflicts. The machine-swap rule allows the system to explore the possible orderings of operations that require the same machine. This rule finds two consecutive operations on the same machine and swaps their order. Similarly, the rule object-swap allows the system to explore the orderings of the operations on the same object. These two rules use the interpreted predicate adjacent-in-critical-path to focus the attention on the steps that contribute to our cost function. Adjacent-in-critical-path checks if two steps are consecutive along one of the critical paths of a schedule. A critical path is a sequence of steps that take the longest time to accomplish. In other words, a critical path is one of the sequences of steps that determine the schedule length.
The next six rules exchange operators that are equivalent with respect to achieving some effects. Rules IP-by-SP and SP-by-IP propose the exchange of immersion-paint and spray-paint operators. By examining the operator definitions in Figure 19, it can be readily noticed that both operators change the value of the painted predicate. Similarly, PU-by-DP and DP-by-PU exchange drill-press and punch operators, which produce the has-hole predicate. Finally, roll-by-lathe and lathe-by-roll exchange roll and lathe operators as they both can make parts cylindrical. To focus the search on the most promising exchanges these rules only match operators in the critical path (by means of the interpreted predicate in-critical-path).
|
The six bottom rules in Figure 20 are more sophisticated. The lathe+SP-by-SP rule takes care of an undesirable effect of the simple depth-first search used by our initial plan generator. In this domain, in order to spray paint a part, the part must have a regular shape. Being cylindrical is a regular shape, therefore the initial planner may decide to make the part cylindrical by lathing it in order to paint it! However, this may not be necessary as the part may already have a regular shape (for example, it could be rectangular, which is also a regular shape). Thus, the lathe+SP-by-SP substitutes the pair spray-paint and lathe by a single spray-paint operation. The supporting regular-shapes interpreted predicate just enumerates which are the regular shapes. These rules are partially specified and are not guaranteed to always produce a rewriting. Nevertheless, they are often successful in producing plans of lower cost.
The remaining rules explore bolting two parts using bolts of different size if fewer operations may be needed for the plan. We developed these rules by analyzing differences in the quality of the optimal plans and the rewritten plans. For example, consider the both-providers-diff-bolt rule. This rule states that if the parts to be bolted already have compatible holes in them, it is better to reuse those operators that produced the holes. The initial plan generator may have drilled (or punched) holes whose only purpose was to bolt the parts. However, the goal of the problem may already require some holes to be performed on the parts to be joined. Reusing the available holes produces a more economical plan. The rules has-hole-x-diff-bolt-add-PU, has-hole-x-diff-bolt-add-DP, has-hole-y-diff-bolt-add-PU, and has-hole-y-diff-bolt-add-DP address the cases in which only one of the holes can be reused, and thus an additional punch or drill-press operation needs to be added.
As an illustration of the rewriting process in the manufacturing domain, consider Figure 21. The plan at the top of the figure is the result of a simple initial plan generator that solves each part independently and concatenates the corresponding subplans. Although such plan is generated efficiently, it is of poor quality. It requires six time-steps to manufacture all parts. The figure shows the application of two rewriting rules, machine-swap and IP-by-SP, that improve the quality of this plan. The operators matched by the rule antecedent are shown in italics. The operators introduced in the rule consequent are shown in bold. First, the machine-swap rule reorders the punching operations on parts A and B. This breaks the long critical path that resulted from the simple concatenation of their respective subplans. The schedule length improves from six to four time-steps. Still, the three parts A, B, and C use the same painting operation (immersion-paint). As the immersion-painter can only process one piece at a time, the three operations must be done serially. Fortunately, in our domain there is another painting operation: spray-paint. The IP-by-SP rule takes advantage of this fact and substitutes an immersion-paint operation on part B by a spray-paint operation. This further parallelizes the plan obtaining a schedule length of three time-steps, which is the optimal for this plan.
We compare four planners (IPP, Initial, and two configurations of PbR):
The initial plan generator uses a divide-and-conquer heuristic in order to generate plans as fast as possible. First, it produces subplans for each part and for the joined goals independently. These subplans are generated by Sage using a depth-first search without any regard to plan cost. Then, it concatenates the subsequences of actions and merges them using the facilities of Section 3.4.2.
We tested each of the four systems on 200 problems, for machining 10 parts, ranging from 5 to 50 goals. The goals are distributed randomly over the 10 parts. So, for the 50-goal problems, there is an average of 5 goals per part. The results are shown in Figure 22. In these graphs each data point is the average of 20 problems for each given number of goals. There were 10 provably unsolvable problems. Initial and PbR solved all 200 problems (or proved them unsolvable). IPP solved 65 problems in total: all problems at 5 and 10 goals, 19 at 15 goals, and 6 at 20 goals. IPP could not solve any problem with more than 20 goals under the 1000 CPU seconds time limit.
Figure 22(a) shows the average time on the solvable problems for each problem set for the four planners. Figure 22(b) shows the average schedule length for the problems solved by all the planners, that is, over the 65 problems solved by IPP up to 20 goals. The fastest planner is Initial, but it produces plans with a cost of about twice the optimal. IPP produces the optimal plans, but it cannot solve problems of more than 20 goals. The two configurations of PbR scale much better than IPP solving all problems and producing good quality plans. PbR-300 matches the optimal cost of the IPP plans, except in one problem (the reason for the difference is interesting and we explain it below). The faster PbR-100 also stays very close to the optimal (less than 2.5% average cost difference).
Figure 22(c) shows the average schedule length for the problems solved by each of the planners for the 50 goal range. The PbR configurations scale gracefully across this range improving considerably the cost of the plans generated by Initial. The additional exploration of PbR-300 allows it to improve the plans even further. The reason for the difference between PbR and IPP at the 20-goal complexity level is because the cost results for IPP are only for the 6 problems that it could solve, while the results for PbR and Initial are the average of all of the 20 problems (as shown in Figure 22(b), PbR matches the cost of these 6 optimal plans produced by IPP).
Figure 22(d) shows the average number of operators in the plans for the problems solved by all three planners (up to 20 goals). Figure 22(e) shows the average number of operators in the plans for the problems solved by each planner across the whole range of 50 problems. The plans generated by Initial use about 2-3 additional operators. Both PbR and IPP produce plans that require fewer steps. Interestingly, IPP sometimes produces plans that use more operations than PbR. IPP produces the shortest parallel plan, but not the one with the minimum number of steps. In particular, we observed that some of the IPP plans suffer from the same problem as Initial. IPP would also lathe a part in order to paint it, but as opposed to Initial it would only do so if it did not affect the optimal schedule length. Surprisingly, adding such additional steps in this domain may improve the schedule length, albeit in fairly rare situations. This was the case in the only problem in which IPP produced a better schedule than PbR-300. We could have introduced a rewriting rule that substituted an immersion-paint operator by both a lathe and spray-paint operators for such cases. However, such rule is of very low utility (in the sense of [55]). It expands the rewriting search space, adds to the cost of match, and during the random search provides some benefit very rarely.
This experiment illustrates the flexibility of PbR in specifying complex rules for a planning domain. The results show the benefits of finding a suboptimal initial plan quickly and then efficiently transforming it to improve its quality.
