Years of process planning research has lead to a number of successful approaches, which include the existing Computer Aided Process Planning (CAPP) systems that can be described as experts for specific manufacturing processes. This has created a need for high-level process planners that simultaneously considers multiple manufacturing technologies.
A process planner called BCAPP (Boolean CAPP) is described. It uses a Boolean algebra based design representation to develop a high level process plan. The system then relies on other process planners to do detailed (low level) planning and estimate time standards for each operation. Some additional features of interest in this system are; generation of alternative operations, the use of cost estimates, new technologies are easily incorporated, uses hierarchical planning techniques are used to reduce the search space, and it is capable of recovering from plan failures.
Computer Aided Design (CAD) systems take direction from a user that direct the construction and analysis of a geometrical model. At present, the geometrical model of the product is preserved, while the steps of creation are discarded. When the steps of creation are preserved they provide clues about the manufacture of a product. A product definition was developed that maintains the definition steps, as opposed to explicit geometry using Boolean equations and sets. The Boolean equations allow the basic operations found in solid modellers, such as subtraction, intersection, union, and assembly. The sets carry the fundamental information about the geometry, such as shape, dimensions, position and orientation. This approach allows attributes to be assigned that are difficult to associate with traditional CAD models.
The Boolean equations of the design representation can be converted to a set of production steps to form the basis of a process plan. (The process plan is not unique for a design equation. Each design equation and its sets are not unique to a specific design ). The fact that these plans are not unique is often seen as a problem when using these methods. However, when process planning, the process plan will vary as conditions of production equipment and other essential resources change. This dictates that the process planner be able to consider alternate plans, as is done in any successful planning approach. The non-uniqueness of the design representation is used to allow the Artificial Intelligence (AI) planning routines to generate alternative operations. The planner will find alternatives from a single equation, and if unsatisfied it will request equivalent Boolean equations that will be generated using the rules of Boolean algebra. A similar approach was used by Lee .
The planning algorithm uses a number of strategies to search for locally optimal solutions. In general the operation of the planner is of the form i) equation pattern recognition, ii) condition evaluation of implicated sets, and iii) application of best match rules.
A design embodies structures, especially those related to function. These physical constructs have design features that range from basic geometrical primitives (e.g. box shape), to complex features (e.g. counterbored holes), to highly abstract properties (e.g. color). The full range of these design features are simultaneously used in most designs. For example, a countersunk screw is a cylindrical shaft (primitive) with a threaded shaft (feature) and a cone (primitive) with a slot (primitive) cut out. The screw is brass colored (abstract) for aesthetic reasons.
The extensive list of existing solid modelling techniques  address the designs on a primitive level very well. Complex features can also be modelled well, but these can be difficult to recognize once the object is modelled. Abstract features can be associated with the models if they can be linked to faces, vertices, edges, etc. A concurrent representation of modelled geometry and abstract design are needed for a good design representation. The design method chosen is a generalization of the CSG (Constructive Solid Geometry) model. And, being CSG-like, it can be used to produce a boundary representation (B-Rep) model . The basic elements of the representation are sets to hold information and Boolean equations to apply them. The set membership is not specified at this time, and can be eventually matched to the rules selected. This statement can be emphasized by the use of the method to represent both mechanical parts, and digital circuits .
The use of Boolean equations instead of CSG trees allows access to the well understood laws of Boolean algebra, and allows simplification of the complex operators in CSG (e.g. subtraction). Further extensions have been incorporated to allow more practical modelling. First, a nested equation form was used to clarify operator scope for the user, and to formalize the data structures. This form is shown in Figure 1 below, and can be seen to be equivalent to an expression that is not nested (i.e. it only involves the addition of parenthesis). Second, additional set properties can be appended to sets or terms in the equation. This allows reuse of sets when designing, or the addition of abstract properties to groups of geometrical features. This handling of groups is not easily done in other representation methods and causes great problems when modelling tolerances and other abstract properties.
We can see how B is different from A and C: During planning we would first look for certain algebraic forms in the equation. In this case the general form ‘( & X0 X1 X2 ....... ( ~ Y1 ) ....’ suggests Y1 is removed from ‘( & X0 X1 X2 .....’. Here we see that B is to be removed from A. In the second phase the sets A and B must be examined. If B was a simple hole with dimensions only it would probably be drilled. This would also rely on the geometric validity of the operation (i.e. the centre line of the drilled hole must be normal to the surface). In this case B contains the property ‘tapped = 5/8-11-UNC’ which would fire a rule for cutting threads. The results of the rule application would be the addition of a tapping operation to the process plan, and the replacement of set B with a new set.
The planning would then continue, and this time B1 will be recognized as a simple drilled hole. (We shall address the recognition process in the next section.) The drilling rule would be applied, and a drilling operation added to the process plan. The equation term containing B1 would now be deleted and the design equation would become,
The planning would continue with the recognition of removed hole C. This time when C and A are examined the basic drilling rule would not fire because of the tolerance, but a reaming rule would. This rule would add a reaming operation to the process plan, and replace set C with an updated set.
Finally, the equation matches a simple primitive template. This fires a stock cutting rule and a process step for stock cutting is added and the NUT equation is reduced to NULL. (If the nut tolerances existed a milling operation might have been added.)
The previous section described the method in general, ignoring many of the underlying technical issues. The following sections are targeted at explaining how some of the complicated tasks have been accomplished.
In the previous example, sections of the equation were “recognized”, and these recognized terms in the expression were subsequently examined with rules. A simple pattern matching scheme was used to extract these terms. Simplistic templates are used to identify useful forms in the equations. Some template elements and a few example templates are given below.
The templates are only conditional, and are not very sophisticated, but are sufficient to recognize most equation patterns (future work is required). After templates are matched, they suggest rules for comparison. This also explains the use of variables in the template. For example, in Figure 3 the variable A0 is A, A1 is B, and B0 is C. When rules are selected they refer to A0, A1 and B0, and the sets A, B, and C are indirectly examined.
The algorithm for finding template matches will examine all possible combinations in the equation. When the algorithm is complete all possible matches will have been found. These templates allow pruning of the search space, and high level extraction of possible processes. The templates also allow a single rule to be fired for alternate templates thus reducing redundancy.
While the templates suggest possible processes, they are not sufficient. To ensure the equation and sets satisfy the conditions, simple if-then production rules are used. The rules examine the properties in the sets, and if all rule conditions hold, the actions are performed. The actions typically include equation modification, creation of new sets, and creation of process plan steps. As the actions transform the design, the process plan is expanded, and the design is reduced. A set of design rules are seen later on, some of the operator actions are described below.
The example rule file shown below has four main components; equation templates, rule conditions (antecedents), and rule results (consequents). The ‘equation_form’ shown has the equation template, and rules that it may fire when matches occur. The ‘rule’ definitions have a condition equation and results to fire when the equation is valid. The equation is a simple logical expression that refers to the truth of the ‘condition’ definitions. The conditions allow simple calculations, database references, and compares. Finally the ‘result’ definitions describe functions that may be performed. In general the results alter the equations, add new sets and properties, specify estimated costs of operations, and add operations to the process plan.
The large number of possible solutions makes the direct application of rules infeasible, leading to the conclusion that a pruned search space is required. In addition, the temporal nature of the problem suggests that a planner is best suited to the problem. The planner uses a hierarchical two-step application of template pattern matching, and then rule checking.
After application of the rules, many possible processes can be identified after the matching phase, and estimated costs can be used to choose between them. Also, certain techniques have been used to approach the non-linear and time variant nature of the plans. One approach involves backtracking. As the plan is developed, a tree of plan steps is completed. If a blind alley is encountered, or a plan step becomes invalid because conditions in the factory change, the planner will go back and try alternate operations. All of the alternate steps are contained in the process plan, so that a scheduler can make use of alternate plans when required. A second technique that deals with plan sequence non-linearity is the manipulation of the Boolean equations. When the planner is unable to find enough valid operations for a specific production state, it will simplify, or randomly change the equation. Eventually other manipulation strategies will be enabled for the Boolean equations. Essentially by reseeding the planner, we can now get around solutions locked in a certain goal, much as a random walk technique would in traditional optimization problems. Two flow charts are given in Figures 5 & 6 that outline the basic strategies of the planners.
The results presented here have been chosen to illustrate the diverse planning capabilities of BCAPP. The first product described is an advertising paperclip in the form of an oversized clothespin. In this design there are some interesting features.
• The plan uses drilling operations for holes on the clip half, but drilling would fail because the bit would deflect. This will be overcome when solid modelling capabilities are added (currently being investigated).
Another test case was examined for a radically different type of planning. In this case it was for the assembly of a digital circuit. The circuit is a simple digital to binary converter. To do this a design was entered, and a new set of rules was developed. In this case the rules used OR gates, and were able to develop all of the gate selections, and connections.
Observing the process plan will illustrate that the plan is complete, although the circuit is not efficient in the use of components. One oddity is that while the plan is complete and correct, it is backwards. This is a result of the backward planning approach.
The current implementation is done in C++, and the core of the planner runs under MS-Dos and UNIX. The time for plan execution is generally a few seconds, up to half a minute for the clothes pin example. The software uses dynamic memory allocation, and has used less than half a megabyte for either of the test cases described here.
The planner described here only uses Boolean reasoning to determine plans, but work being done now will lead to addition of a solid modeller to allow geometrical reasoning. There are also other areas that will require future work. These are,