Process planners operate on higher-level entities known as features. An interpretation is a collection of features which describes a part. Since a given part may have many interpretations, the process planner may plan for each interpretation and choose the best based on optimality criteria.
One of the objectives of this research has been to develop a case-based planner that is based on formal techniques and flexible in its reuse of old plans. This objective was achieved in our development of CBPOP, a case-based partial-order planner that reuses pieces of multiple old plans to construct a new plan. Another objective was to optimize the final global plan by combining the feature subplans generated by the case-based planner such that the number of fixture and tool changes was minimized. This objective was achieved through the development of a systematic hierarchical plan merging mechanism.
To generate a process plan for a part, CBPOP generates plans for the features of the part (eg: slots, pockets, holes, etc.) independently. These feature plans are then merged into a global plan for the part using a hierarchical plan merging mechanism which minimizes the number of fixture and tool changes in the global plan.
To develop a formal planning model for case-based process planning, we have combined case-based planning with partial-order planning. Case-based planning provides the utility of plan reuse while partial-order planning provides a formal framework in which plans can be proven correct with respect to the planner's domain knowledge. CBPOP develops a solution by searching the space of plans [1]. A plan is represented as a four tuple, <A,O,L,B>, for Actions (STRIPS-like), Orderings, causal Links, and variable Bindings respectively. Figure 1a shows one snapshot in planspace in which plan P2 is refined to generate plan P5 by the addition of an ordering between actions. Search continues via plan refinement (adding actions and resolving constraints) until a complete solution is found. An example process plan generated by CBPOP for machining a thru-slot is shown in figure 1b.
CBPOP represents both primitive actions and old plans identically as cases. This allows CBPOP to refine plans by seamlessly interleaving primitive actions and old plans; hence, multiple old plans can be used in generating a solution to a single planning problem. Also, this approach obviates the difficult decision of whether to solve from scratch or retrieve and old plan first.
The output of CBPOP is
a set of feature subplans and a set of orderings and constraints between the
subplans. We utilize a hierarchical approach to
merge each of the feature subplans into a more efficient global plan for the
part [2]. The advantage of this approach is that it decomposes
the plan merging problem by exploiting the natural decomposition property
of the process planning domain. Costly fixturing actions are merged first,
exploiting alternative fixturings to minimize the total number of fixture
changes. Then tooling actions are merged to minimize the number of tool
changes within a fixturing.
While the hierarchical plan merging mechanism we have developed is a
general methodology, it also facilitates the use of deep domain knowledge
during the merging process.