Boolean representations can be used to describe physical models. In manufacturing these models must be interpreted into manufacturing operations. Computer Aided Process Planning (CAPP) systems are intended to map design features (geometry) into manufacturing features (operations/processes).
A planning system has been developed to examine Boolean equations, and select manufacturing operations. It does this by examining an equation for known patterns. A set of rules are used to alter the design equation and add steps to the process plan. As planning continues the equation is eventually reduced to a NULL state, at which time the process plan is complete.
Boolean equations are a very powerful form of representation. This representation is often used for the design of digital switching circuits and construction of solid models. While the equation will describe the final geometry or function of a design, it does not provide a process plan (a process plan directs the manufacture of the design), but, this representation can be used to derive a process plan.
We can think of manufacturing as starting with a product that does not exist. Well defined operations add and remove material to slowly transform a workpiece into a final product. At each stage we may stop and examine the part. And, at each stage this part will have a geometry that can be defined with a Boolean equation. If all of the operations from beginning to end are written in a list we would have a list with a NULL state at the top, and through incremental changes to the design equation we would arrive at the final, more complicated design equation. To take the concept one step further, if we look at the process plan in a tree form, we would see the root as the final design equation. Each arc would transform the equation, and add a sequence to the process plan. Each node would represent a design state, and the terminal nodes would be null equations. In addition the arcs leading from the nodes could be AND/OR in form. The AND branches would represent separate parts of the design that are produced separately, or are fully independent features on the design, and are both required. The OR branching is required because every manufacturing operation has alternates. A complete process plan would be the result of a complete subtree where there is a complete subtree with all nodes expanded, and a null term at the terminal leaves.
This form allows a planner to search design space . A search begins at the root node where various equation components are undone or transformed. This leads to a number of AND/OR arcs. These are all kept, and based on cost estimates, one of the subnodes is expanded. This underlying search is best characterized as depth first. Each node is expanded to provide alternative operations in the case that a process plan step fails. The alternatives also provide the opportunity for backtracking when a dead-end is reached.
The planning algorithm also uses a number of other strategies, such as altering the form of the Boolean equation. Another paper in these proceedings describes tools for altering the structure of a Boolean equation . This method has been successfully used to produce process plans for mechanical parts, as well as digital circuits .
It has been stated that Boolean algebra designs are prone to problems because of equation non-uniqueness . This method begins to answer the problem of non-uniqueness by using it to seed the planning routine.
This paper will describe the reasoning system, and then conclude with a brief example that illustrates the method. The author intends to make the reasoning software available, as described in Appendix B. The paper begins with a discussion of process planning systems. Planning systems were used as the target for the work described in this paper, and serve as a good domain for exploring planning with Boolean equations.
Computer Aided Process Planning (CAPP) has had a number of distinct approaches. First, the Variant approach identifies standard part families to derive a set of standard process plans that are filed in a computer . A classification scheme compares new parts with the standard parts to find the best match, the standard process plan for the standard part is recalled and changed to suit the new part . This approach is suited to factories that have distinct part families, and when used has reduced the reinvention of similar process plans. This approach relies on human decision makers to select and update plans but does not use knowledge about process planning. Newer Generative CAPP systems attempted to bring knowledge of the factory into process planning. While this automates decision making, it requires a large scale effort to formalize the knowledge into a set of rules . These systems may be dichotomized as - Variant systems store old plans, and Generative systems do not . Importantly, both of these strategies are required for a planner that will be able to efficiently reuse successful plans when possible, but be able to generate required steps as required. To date there have been well over a hundred CAPP systems documented .
The notable successes for generative CAPP systems all limit planning to a specific manufacturing domain. For example, AUTAP  focuses on turned parts, CUTTECH  is a commercial system that generates process descriptions for machine operations, TOM  deals with holes, etc. All of these planners deal with the low level details of specific process domains, but what is required is a high level process representation that is not as closely tied to a specific manufacturing domain.
Modern CAD design systems use solid (geometric) modeling to create geometrical descriptions of parts. Generally the solid representation makes it possible to create a non-ambiguous model . This has long been recognized in CAPP research as well. One of the earliest developments in the area  used feature recognition based on the relationship of solid primitives. This approach included a part design that was represented as an equation. More recent work continued with attempts to examine the Constructive Solid Geometry (CSG)/Boolean equations to recognize features . Most of this work uses assumption of machined features extracted from base stock. One of the main criticisms of the use of CSG/Boolean equations is the non-uniqueness of the representation . (NOTE: CSG representations use primitive shapes that are joined, or used to cut each other to form new shapes. These operations and primitives can be represented in tree or equation forms.) This non-uniqueness has two forms. First, the distribution of terms in the design tree/equation can vary. To overcome this, many authors have considered rearranging the representation as CSG trees or in equation form . Second, non-uniqueness can result from different sets of defining primitives. To overcome this the approach would only examine the final geometry . It has also been suggested that the equation primitives could be altered to generate the alternative geometries . If the non-uniqueness problem of the solid CSG/Boolean method is to be overcome, a solid modeler will have to be incorporated to include geometrical reasoning . Solid Modeling has many approaches. The most common types in use are CSG and Boundary Representation (B-Rep) (Note: B-Rep models the part faces and their interconnections). The B-Rep models can be derived from the CSG model, while the inverse operation is very difficult , thus CSG is a more general form. In fact most commercial modelers use the CSG operators (union, intersection and subtraction) to create B-Rep models . As the CSG operators are used, the B-Rep model is constructed, and the operators are discarded. When these operators are kept they provide clues as to the construction of the specified part.
A solid modeler for manufacturing has special requirements. As mentioned before, the CSG information is often discarded, but it can be stored concurrently in a Hybrid modeler . In addition the modeler must also consider non-homogenous materials , tolerance information , and attributes not directly related to geometry .
The basic form of equations used in this planner are nested . This means that brackets are used for each operator to explicitly define the scope. In addition each set in the equation, as well as terms, can have additional sets appended. These have been added to allow modifications to reused sets. In addition each of the sets mentioned refers to a list of properties. An example is given below
For the example above, the process plan can be found by looking at the final form. Each term will suggest a manufacturing operation. These possible operations can then be verified or eliminated by looking at the properties of the sets. If an operation is identified, it may be undone, and the new equation may be used for reasoning. This will continue until the plan is complete. The next section gives and example of this.
Examining the equation in general, it would be recognized that ‘tapped_hole’ is a more complex part of the equation, therefore this would be a good place to begin planning. The ‘tapped_hole’ refers to a another equation twice, therefore the planner should reuse the results. At this point we will focus on planning for ‘tapped_hole’. The ‘EQUATION’ refers to a primitive type of set (in fact this is a feature based representation, not a geometry). Seeing that the operation is a ‘~’ NOT operation would lead us to question what is being removed. We would then compare the properties of ‘thread’ against known rule conditions. The only rule that would fire is for the internal thread. This would find that the form is a ‘3/4-10-UNC’ thread. The rule would then replace the sets, and modify the equation to replace the thread with a hole, suitable for tapping. The following form represents the modified components only,
The same pattern as before would be used for this method, and it would be recognized that a cavity is still being cut from the base material. But, this time a rule would fire that recognizes that the hole can be drilled. This leads to the addition of a drilling operation to the process plan steps, and removal of the feature from the design representation. The resulting form would be,
At this point we would recognized that the equation is now somewhat irrational, containing NULL terms. Therefore the main equation will be examined, and it is found that two of the sets used ‘tapped_hole’ and thus refer to completed process plans. These would be added to the main process plan. These two steps would be modified by the addition of the appended sets. Both of the appended sets would specify rotations that would modify both of the ‘tapped_hole’ plans. At this point the design would be modified to compensate for the now completed, and removed tapped holes,
Now, we examine the equation, and find only a single term. This term is examined for other features. We recognize the color attribute as being significant, and decide to deal with it. To do this a painting operation is added to the process plan, and the paint set is deleted from the main equation. At this point the equation now looks like,
Looking at the equation we realize that all that is left is a small block of material. A cutting operation from stock is used to get the basic dimensions, and the stock is called from inventory. The square primitive is removed from the process plan, and equation reverts to a NULL, at this point planning is complete. A process plan for the completed part would be listed in reverse order from the order of planning, as is seen below,
When examining equations we tend to find common forms. These are part of a two step recognition process to identify possible rules. For example, we can look at the equation for ‘( & A B ....( ~ X )....’ and know that X is some form of geometry removed from ‘( & A B ...’. This is markedly different from ‘( + A B .... ( ~ X ) ...’ which could suggest that ‘( + A B ...’ be joined to everything outside ‘X’. It is not the intent of the author to classify these, but instead to provide tools to allow knowledge engineers to classify operations for specific domains. A list of common template elements are given below,
The list can be seen to deal with terms, operators, symbols, and appended symbols. When these are used in the rule set, they locate all possible matches, and then the variables in the template are matched to the variables in the equation. This allows rules to refer to sets in the equation.
This template would result in three matches. In the first match we would catch the ‘&’ term and get the equalities ‘V0 = A, V1 = B, V2 = C’. The second match would be for the ‘~’ operator, and the equalities would be ‘V0 = D’. The final match would be for the ‘+’ operator, and the equalities would be ‘V0 = E, V1 = F’. The equation templates can be built up in this manner to get fairly complex forms of results.
After the templates above have been matched to the equation, they will then suggest rules that are possible matches. The rules have sets of logical conditions that must be satisfied, and actions that will result. Here we will examine the conditions.
The conditions for the rules are expressed in a Boolean equation (also reusing previous data structures) that will refer to the truth of conditions. Each condition has its own form. These are stored as a list of comparisons or operations that must all be satisfied concurrently for the condition to hold true. The conditions refer to variable names such as ‘V0’ from the template matching. A list of common condition statements/comparisons are,
The comparison elements are obvious in intent, but if any of the other operations fail, the condition is ruled negative. For example if the mathematical operation ‘PROERTY_FUNCTION_NUMBER ( DRILL_HOLE height / 20.0 )’ could not find the property ‘height’ in a set ‘DRILL_HOLE’, then the operation would fail, otherwise ‘height’ would take on the new divided result, and the line would be true in the condition.
If a rule has matched, then the results (consequents) will be applied. This is basically a list of instructions that will alter the Boolean equation, add/change sets, and add lines to a process plan. A list of basic operators is given below that will alter the Boolean equation.
The operators that change the equation will affect a new copy of the equation. This is stored as a process planning state. In other words the changes that are made by the rule are for the new design state. Typical changes used are to eliminate terms, or replace them with updated sets. When referring to the location of terms, the rule acts as if the template matched term is the base, and from there the equation addressing scheme described is used.
The sets can be copied, and properties in them may be replaced/deleted/added, to the satisfaction of the new design state. In all cases, so that rules may be reused, each new set created is given a unique name (by appending a number) to prevent conflicts when it is used multiple times. This unique name is used in the design representation, but hidden from the rule.
The planner basically works in two stages. First, the high level planner looks at the main equation, and finds all of the sub-terms, and possibly reused components. It then starts looking at the lowest level components, and tries to find process plans for them. In general terms the high level planner deals with the process plan tree. As each state in design space is to be expanded, the Low Level planner is used to match templates, and check rules. If the low level planner is not able to successfully expand a node, it informs the high level planner. The high level planner will try expanding the next lowest cost node. If the planner become frustrated, and cannot expand a node, it will try changing the form of the Boolean equation. This can seed the planner, and allow it to continue again. One significant note is that this only changes the equation, future work will examine changing the primitives that are used in the equation.
Here we see the basic steps of trying to find a matching equation template, checking the conditions of suggested rules, and performing the results if successful. The planner will continue until it has some minimum number of satisfactory solutions. If no solutions are found the planner becomes frustrated with that design state and returns to the high level planner.
A planning system based on Boolean equations was described. It showed reasoning based on the form of the Boolean equation, followed by examination of the sets referred to in the Boolean equation. The effects of the application of the rules was also discussed.
The simple example provided shows the ability of the method to find process plans. Even more, the intuitive terms used to describe the process suggest that it models the human approach well (a commonly accepted intelligent system).
 Alting, L., and Zhang, H., “Computer Aided Process Planning: The State-of-the-Art Survey”, IIE Integrated Systems Conf. Proceedings, St. Louis, Missouri, 1988. Also appears in the International Journal of Production Research, Vol.27, 1989, pp. 533-85.
 Brun, J. M., “B-Rep to CSG Conversion as a Feature Recognition Process”, in Advanced Geometric Modelling for Engineering Applications, editors, F.-L. Krause, H. Jansen, International GI-IFIP Symposium 89, 1989, pp. 201-214.
 ElMaraghy, W.H., and Jack, H., "Facilitating Rapid Product Realization with an Intelligent CAPP System", Proceedings of IFIP Conference on World Class Manufacturing, Phoenix, Arizona, September, 1993.
 Eversheim, W., Fuchs, H., and Zons, J.H., “Automatic Process Planning with Regard to Production by Application of the System AUTAP for Control Problems”, Proceedings of the 12th CIRP International Seminar on Manufacturing Systems, Belgrade, 1980.
 Okino, N., Kakazu, Y., and Kubo, H., “TIPS-1: Technical Information Processing System, for Computer-Aided Design, Drawing and Manufacturing”, in Computer Languages for Numerical Control, North-Holland, 1973, pp. 141-150.
An ftp site is being set up, and should be available by early 1995. The basic procedure is to ftp to cobra.megan.ryerson.ca, and look in the directory ‘/pub/software/tools/BCAPP’. The contents will be a copy of this paper, as well as more complete function descriptions, examples, and the source code. If the software is desired before this time please send email to ‘firstname.lastname@example.org’.