--- title: "Using a Feature Algebra for Reasoning about Geometric Feature Interactions" authors: - "Raghu Karinthi" - "Dana S. Nau" doi: "" url: "https://ijcai.org/proceedings/1989/195" pdf: "https://ijcai.org/proceedings/1989/0195.pdf" venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence" year: 1989 pages: "1219-1223" track: "Knowledge Representation" keywords: --- # Using a Feature Algebra for Reasoning about Geometric Feature Interactions Raghu Karinthi, Dana S. Nau *Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, pages 1219-1223. ## Abstract C AD -genera t ed obj e cts can be defined in t e rms of th e co mpl et e geom e try of th e part . In automa t ed pro cess planning , th e ge om e try is th e sa me, but th e me aning assoc iat ed with this geo me tri c s tru c tur e is differe nt , and dic tat es a c han ge in th e desc ription . Various solutions have been propos ed to solve thi s in compatibilit y, including automat ed fe atur e e xtra c tion , design by fea tur es , and human-sup ervised fe atur e e xtr actio n . An imp o rt a nt probl em to be addr essed here is ha ndling fea tur e int e ractions . Du e to ge om etri c int e racti o ns among th e ma c hinabl e fe atur es, t here may be several e qually valid fe atur e ink rpr et at io ns for th e s am e part . Thi s pap er describes a n a ut o mati c way of co mputing alte rn a te feat ur e int e rpr e tation s, using a n algebra of f eat ur e int e ractions . Thi s will e nabl e a ut o m a ted pro cess planning s yst ems to decide wh et her various int e rpr e tati ons of a part as a co ll ection of ma c hinabl e fe atur es are feasible for m a nufac turing , and among th e feasible ones , whi ch is th e most appropriat e one for manuf act urin g. Alt e rn a t l' f eat ure int e rpr et a tions a re co mput ed hy p ~' rfo rmin g opera tio ns in th e alge br a. Fu rt he rm ore, vario us pr ovable pr o pe rti es of th e feat ur e a lge br a aid in resolving a. maj or ity of t. he fea tur e int er act io ns with o ut even a pplyin g t.l w ope r at io ns in th e alge br a, t hen' by improving th e e ffi ciency of th e alge br a ic a ppr oac h . ## Full text ## 1 Introduction Machining a met al part consists of t aking a piece of stock and performing various processes or operations on it to ·T his work has been supported in part by NSF Presiden­ t.ial Young Investigator award DCR-83-51463, with matching funds provided·by Texas Instruments and General Motors Re­ search Laboratories, and by NSF Engineering Research Cen­ ters Program Graul. NSFD CDR-88003012 to the ll uiversit.y of Maryland Syst.erns Research Center. . ## Dana S. Nau Department of Computer Science, Institute for Advanced Computer Studies, and Systems Research Center University of Maryland College Park, MD 20742 U.S.A Email: nau@mimsy.umd.edu transform it into the desired part . Each machining pro­ cess acts on a piece of stock and changes its structure in a unique way. Given the CAD description of the ob­ ject., one would like to derive how it can be manufactured or machined (since we talk only of machining processes here). This means arriving at a sequence of processes which when applied to the stock would result in the fi­ nal machinable part . Notice that such a sequence is not unique. Tradi t ionally the designer comes up with the CAD description of the object to be machined , and the process engineer and the N C programmer produce the precise process plan. There has been a lot of progress in deriving process plans from manufacturable features and we have sev­ eral working generative process planners such as XCUT [Brooks et al. , 1987) and SIPS [Nau , 1987) . Several approaches have been proposed for bridging the gap be­ tween Computer Aided Design (CAD) and Computer Aided Manufacturing (CAM) and automatic feature ex­ traction , design by features, and human supervised fea­ ture extraction are among the prominent ones. One of the limitations of these approaches is of multiple feature interpretations, whi ch is discussed in the next paragraph . Due to geometric interactions among the features, there may be sPveral equally valid sets of features de­ scribing t.lw same part. . To produce a good process plan--or , in some casf's, e.vf'n to producf' a procf'ss plan at all ·-·it. may be nf'cessary to use a differPnt interpre­ tat iOn of the part. than the one obtained from the CAD model. T he problem is how to find these alt.ernate inter­ pretations. A machinist solves t his problf'm because of the human ability t.o visua lize an object in three dimen­ sions and by doing geometric reasoning to figure out the interactions. To illustrate the role of feat.urP intNact.ions, let. us con­ sider the part. described in Figure I . In this example, the part. has been described as tlw part. rPsult.ing from sub­ tract ing a hole ht , a slot. s 1 and a slot s2 , in that order out. of a redangular stock. Because of the int.Prac t.ion of h1 wi th SJ and s2, we get. h2 = h1 -* s 1 , h ;~ = h 1 -· s2 , and h4 = h2 - · s2 = h3 -· s 1. T he final set. of ff'atures used for machining would be s 1, s2 and onf' of h1 , h'J , h3 and h4. Whi ch holf' t.o 11se depPnds on issuf's such as cost criteria (whether it is cheaper to make a deep hole or a small hole), feasibility (availability of proper tools to make a deep hole), fixturing criteria (can the part be properly fixtured to make h4 after s1 and s2 have been made, or will it vibrate). Thus one can see that there can be several possible interpretations such as { h1, SJ, s2}, {h2, s1, s2}, {ha, s1 , s2} or {h4, s1, s2} for the same part and having only one of them can be a serious limitation in process planning. Figure 1: ![Image](https://ijcai.org/proceedings/1989/fulltext/195/image_000000_08ee5d87bc8ca99cff35300405b081eba848452947dd0a114202be8dde6bbf58.png) This paper discusses an approach for dealing with this problem, based on an algebra of features. Alternative interpretations of features resulting from feature inter­ actions are provided by means of operations in this al­ gebra. This scheme provides Sf'veral alternative feature representations of a machinable part, given one such rep­ resentation. The rest of the paper is organized as follows: In Sec­ tion 2 we describe the feature algebra. In Section 3 we compare our work with related n~search in this area. Sec­ tion 4 is a discussion of the issues addressed by this re­ search. In Section 5 present the current status of the research and the work we plan to do in the future. ## 2 The Algebra of Features In this section we discuss the domain of features we work with, the operations on features, some properties of the feature algebra and an algorithm that produces multiplP feature interpretations of a part, given one such repre­ sentation. An algebraic structure [Pinter, 1982) in its simplest form is any set, with a rule (or rules) for combining its elements. Let A be any set. An operation * on A is a. rule which assigns to each ordered pair < a., b > of elements of A exactly one element a.* b in A. ## 2.1 Feature Definitions For the purposes of this paper, the only features consid­ ered are a rectangular pocket, a slot and a hole. Further, in this paper we restrict the features to have the normals of their planar faces, to be parallel to the base vectors of our co-ordinate system. In addition to the features, there is a special object called the stock on which all the features are made. Figure 2: ![Image](https://ijcai.org/proceedings/1989/fulltext/195/image_000001_a9ee0ce9a9408eecf359d77af0568179b2d4fcb1120539fb353d22f6efa4d761.png) It is well known that when set theoretic operations such as union, intersection, and subtraction when ap­ plied to two valid n-dimensional objects, the result is not necessarily a valid n-dimensional object.. For example, if two squares touch on one side, their intersection is a sin­ gle line segment, which is not a valid two dimensional object. Requicha and Voelcker[Requicha and Voelcker, 1985) have shown that this difficulty can be overcome by using regularized set operations instead of ordinary set operations. The symbols u·, n·, - · and c* are used to denote regularized union, intersection, subtraction and complementation respectively. Let us denote the initial stock by So. Let h, h, ... f, be the features subtracted out of So, in that order. The part after i features have been defined is denoted by S;. ![Image](https://ijcai.org/proceedings/1989/fulltext/195/image_000002_a745a7ede18f37896f72ff7c1fd978ff2476c2b370c42c2a813f254d8467308a.png) and A face ;z: of a feature J; is said to be open, if J : lwlongs to the boundary of s·, u· J; where s, denot(·s the final part.. A pocket is a rectangular cavity with at least. one of its faces open. A slot is a rectangular cavity with at least one of its faces and two faces orthogonal to it also open. These two faces must be parallel to each other. A hole is simply a cylindrical hole. Figure 2 shows a part. with a pocket, a slot and a holP. Every feature must have at. least. one of its faces in common with of a. face of the stock or some other fea­ ture. These two parameters are called the conta.inmg fa.ce and the containing feature. In other words, the con­ taining feature is the feature having the containing face. At the time of defining any feature the containing face must belong to the boundary of the part at that step. It cannot be interior to the part or outside the part. This condition is more restrictive than the ones given in the previous paragraph, and hence supercedes t.hern. Further , for slots, two faces orthogonal to the contain­ ing face are required to be part of the part boundary at that step. As mentioned earlier, these two faces must be parallel to each other. 1. The initial stock is specified by its location in space and the dimensions along the x, y and z axes. 2. A pocket is specified by four parameters, viz . the containing face, the containing feature, the open fa ce and the depth. The containing face and the containing feature specify the face and the feature in which the pocket is contained. The open face of the pocket is a set of four points in the containing face specifying the face of the pocket that is open and the direction of the normal pointing into the feature. We will call the face of the pocket paral­ lel to the open face as the bottom fa ce. The depth parameter gives the dimension normal to the open face. 3. A slot has the same parameters as a pocket. The two open faces of the slot that are orthogonal to the open face of the slot are called the side faces. 4. A hole is specified by the containing face, the containing feature, the open face and the depth. The containing face, the containing feature and the depth parameters are analogous to those of a pocket . The open face parameter in case of a hole is speci­ fi ed by the center and the diameter of the circle that constitutes the open face of the hole and the dino.c­ tion of the normal pointing into the feature. As in the case of a pocket , the open face of a hole must lie on the containing face. The face parallel to the open face is known as the bottom face. ## 2.2 Operations As the operations on features are defined, one will no­ tice that the operations give meaningful values only for certain pairs of features, thereby causing a conflict with the definition of an operation. This problem is solved by add ing a special element called I NV ALI D to the set of features. Further, by definition, for any operation *· Let D be the domain consisti ng of all the features and the element I N \fALl D. We will now define the operations shortened (denoted by S) , first maximal-ext ension (de­ not . ~~d by M 1 ) and second maJ:imal-t xtension (denoted by M 2) and a bisection functi on B : D ~ 2D . These are bast>d on regularized boolean operations on solids. Tlw mathematical definitions of S, B, M1 and M 2 are based on the characterization of features as semi-algebraic sets. The definitions and the procedures for determining the operat ions are described in [Karinthi and Nau, 1989] Given two features x and y , :~.:Sy and xBy an' com­ put.Pd from J: - * y, provided x - · y can be regarded as a feature or a pai r of features of the same typP as x. If x -* y is a single feature, then x -* y = J~Sy . If ;r -* y is a pair of feat ures, then x -* y = xBy. For example, in Figure l , h1 S s1 = h2 . The first maximal-extension of x in y , d('IJOted as :~.:M 1 y and t.lw second maximal­ ex tPnsion of J' in y denoted by ;r M 2y arP dPtPrmined from I 1(x) n· (x u· y) and I 2(x) n· (x u· y) , subject. to certain conditions. Informally, I 1(x) and I 2(x) are two ways of extending a feature till the boundaries of the stock. Pockets and holes are extended only in the direc­ tion normal to their open and bottom faces. This is done using the I 1 function . On the other hand , slots can be extended both in the direction normal to their open and bottom faces as well as in the direction normal to their side faces. Thus, for any slot x both I 1 ( x) and I 2 ( x) have meaningful values. Referring back to the example in Figure 1, I 1(h.J) = I 1(h2) = h1 and h2M1s1 = h1 . ## 2.3 Properties of the Algebra of Features In this section , certain properties of the algebra of fea­ tures are discussed . The goal is to generate new features from the features one already has, using the operators discussed earlier. During this process, one would not like to generate a feature anew if it can be shown that the same feature has already been generated. llsing the al­ gebraic properties is a significant saving particularly in this domain , because the boolean operations on solids are quite expensive as compared to symbolic comparisons. Several properties regarding the featurf's and their in­ teractions have been proved. Some properties of the fpa­ tures are stated below. The interested readPr is referred to [Karinthi and Nau , 1989] for more details on the prop­ erties and the proofs. Proposition 1 For any threr f eatuns x , y and z , if (x -* y) and (x -* z ) an: also f eatures, then Proposition 2 If x , y , :: and w an f eaturt·s such that x is a hole, z = J:Sy , I 1 (x) = x and w n· y = 0. th f11 the following res ult holds: Proposition 3 If x andy are f eatures and ifi1 ( J:) = x, then ## 2.4 The Features Algorithm In this sect ion, an algorithm which generates various possiblf' fPaturP s~ts w rrl'sponding to a machinabiP part. given one sf't of features corresponding to the part. is described. ln describing the algorithm and an examplP subsequently, WI' will use the notation 0 to dPnote t.he Pmpty sf't. In this algorithm, the variable F contains t.hf' set. of fea.tun' sets generatf'd at. any st.agf', whilP F has t.lw union of all t.hP fPaturf's in F. BeforP the algorithm is executPd , F' is initiali zed to thP start ing set. of features and F is initi alized to bP a set with only onP element , vir. . the sPt F. Ther~ are also two additional variables called CURRENT and NEW. Before entering the al­ gorithm, CURRENT and NEW are initialized to the sets F and 0, rPspect ively. ## while CURRENT f.: 0 do for each feature sPt do for each operator applicable to a pair of features in the feature' set atleast onP of whi ch is in err RRENT do ``` if the resulting feature(s) have NOT already been generated then begin add the feature to F add the feature to NEW end if the feature set is distinct then add the feature set(s) to F. end for end for CURRENT= NEW NEW =0 end while ``` At first glance, the worst case performance of the algo­ rithm might appear to be of exponential complexity, be­ cause of the possibility of combinatorial explosion if there are several mutually-interacting features . However, ge­ ometric locality dictates that each feature will interact with only a few of its neighbors, so there is no reason to believe that significant exponential blowup would ever occur. ## 2.5 Illustrative Example In this section, we will illustrate the working of the alge­ bra of features (and the features algorithm) through an example. This example is the same as the example one discussed in Figure l . The starting set. of features are h1 , s 1 and s2 . We compute, I 1(ht) , I 1(st), I 1(sz) , I 2 (ht) , Iz(st) and Iz(sz). Therefore, we have, In this section, we will study the example, by look­ ing only at the changes that occur from one iteration to the next, without examining all the interactions (like the ont'S which result in already existing features). Obvi­ ously, all the interactions need to be considered because apriori , one does not know, which interactions resu lt in new features and which do not.. At the start of the fea­ tures algorithm the values of thP variables are: Let us examine F and F each time before the outer­ most loop is entered. The value of NEW is 0 each timt' before the outermost loop is entered. After the first. it­ t'ration : In this iteration, h2 and h3 were generated using the S operation, where hz = h1Ss1 and h3 = htSSz. Fur­ thermore, using Equation 1, and and Proposition 3 we conclude that htM 1 s1 = h1, h1M 1 Sz = h1 . Other in­ teractions are considered similarly. After the second iteration : In this iteration, let us say h4 was generated as h4 = h2Ss2 . But notice that h3Ss1 was not. generated as a new feature, say h5 . This is because, from Proposition 1 h3Ss1 = h2Ssz = h4 , which has already been generated. Similarly, while considering h2M 1 s2, using Proposition 2 we infer h2M1s2 = h2. After the third iteration : At this point the loop terminates, because CURRENT = 0. For this exa.mplt', it can bt' shown that summed over the three iterations , a total of 54 possiblt' featurt' interactions are considered. Of these interactions, only thret' result in new ft'at.ures (hz , h3 and h4) . ## 3 Related Work There has been considerable research in automatic fea­ ture extraction and feature-based design over the last ten years. But as mentioned earlier , even though this work is pertinent from the point of view of CAD/CAM integration, very littlt' of it has actually addressed fea­ ture interactions. The remainder of the section describes some of the recent. work that addresses featurt' interac­ tions. Nicholas Ide [Ide, 1987] at the University of Mary­ land developed a fPature based design system integrat­ ing the SIPS process planning system [Nau , 1987] with tlw PADL-2 solid modeler. In Ide's system, the designer starts out with a rPpresentation of a piece of stock, and designs his part hy subtracting various machinable fea­ tures from the stock. Ide's system points out. certain geometric interactions that make a feature impossible to machine. In this system, the kinds of featurt' interac­ tions that. can lead to multiple featurt' interpretations were either not considert'd or not. allowed (for example, a hole was not allowed to intersect any other fea.turt'). Maeda. and Shinohara[Maeda and Shinohara, 1988] have d«:>veloped an rule-based system called ESPER (Ex­ pert. System for Production BngineeR<J) that. does certain kinds of geometric reasoning to account for fPat.ure in­ tPractions. Tht' rules in ESPER can be used not only to recognize features in geometry, but to manipulate the geometry directly. This system aodresses some of t.he non-geometric issues in process planning, but its geo­ m<:'tric reasoning is based on feature para.nwt.ers and is not intPgrat.ed with a. solid modeler. Hayes[Hayes, 1987], has developed a rule-based system called Machinist that detects feature interactions using rules obtained from human experts. This system is writ­ ten in 0 PS5. The system determines time-ordering re­ lations among features by applying the rules. Thus, if certain conditions are satisfied, a rule would tell us that one feature must be machined before another . R.equicha and Vandenbrande [R.equicha and Vanden­ brande, 1988] have proposed the notion of engineering environments (analogous to programming environments) which are tools useful for design and manufacturing-engi­ neers. They are building a system known as the AI/SM test bed, which has geometric reasoning and feature recognition modules combined with a solid modeling and computational geometry modules. This system was not completed as of the above citation, so we do not know of its capabilities in detail , but it appears to us that their approach of combining solid modeling with geo­ metric reasoning is one of the most promising directions for future research in CAD/CAM integration. ## 4 Discussion A methodology for addressing feature interactions using an algebra of features has been described . We believe the following are the significant aspects of the algebraic approach: - I . One of the primary purposes of the feature algebra is to allow consideration of several possible feature alternatives. Based on our discussions with machin­ ists, it appears that a machinable part cannot be interpreted as a unique set. of features. What. seems mort"' i!ppropriate is to consider alternatives and generate plan::; to see which is better (or feasible). The popular approaches addressing the CAD/CAM integration problem (as described in Section 1) have ignored the issue of multiple feature interpretations. 2. The kinds of reasoning done in the ESPER [Maeda and Shinohara, 1988) and Machinist. [Hayes, 1987] systems represent significant. steps in the develop­ ment. of ways to, handle feature interactions. How­ ever, problems arise in trying to extend these sys­ tPms into complete computer-aided manufaeturing systems , because the representation of solid objects is not. sufficient to resolve ambiguities. For example, if the Machinist program decides that somf' hole h needs to be made before some slot s, it does not. rec­ ognir.e that this requires machining a hole of differ­ Pnt dinwnsions than if h were machined after s - and yet such information is necessary in order to know whether it is possible to machine h. In the feature algebra described in this paper , a feature is an un­ ambiguous and complete representation of a physi­ cal solid. Thus , the information missing from Ma­ chinist's rules could be restored by rewriting these rules in terms of operations in the feature algebra. 3. The operations in the algebra are efficient. as com­ pared to boolean operations on solids, becausP, they take advantage of the nature of the features (sim­ ple 24 D shapes) and the naturP of the interactions (orthogonal interactions). Furthermore, the proper­ ties of the feature algebra allow us to resolve many of the interactions without invoking the algebraic operators. This results in further savings in compu­ tations . ## 5 Current Status and Future Work This work constitutes a portion of a larger project whose goal is to develop an integrated system for design and process planning [Nau et al. , 1988] . Other compo­ nents of this project include the Protosolid solid modeler [Vanecek and Nau, 1988] and the SIPS [Nau and Gray, 1986, Nau , 1987] process planning system. Protosolid and SIPS are written in Lisp and run on a Texas Instru­ ments Explorer-II . Having developed the feature algebra, our next step will be to use it as the basis of a feature analysis and translation system to facilitate communi­ cation between Protosolid and SIPS. For example, this will allow SIPS to decide dynamically whether various interpretations of a part as a collection of manufactur­ ing features are feasible for manufacturing, and among the feasible ones, which is the most appropriate one for manufacturing. Currently, a theoretical framework for the algebra is complete, and work is beginning on the feature analy­ sis and translation system. Future work on the algebra includes incorporating a wider set of features and inter. actions than what we have now. In particular, we would like to extend it to model interactions among features that are not at. a right angle to the faces of the stock or other features. This requires new operations and func­ tions to be incorporated into the algf'bra. WP also intencl t.o ·~xtt>11d the algPbra to model the rounded corners of pockets and slots, and tapered holes. ## References 1. Brooks et a/. , 1987) 2. S.L. Brooks, K.E. Hummel , and M.L. Wolf. XCUT: a rule-based expert system for the automatic process planning of machined piece parts. In Symposium on Int egrat ed and Int elligent Manufac- turing , ASME Winter Annual Meeting, Dec 1987. 3. [Hayes, 1987] C. Hayes. Using goal interactions to guide planning. In Procuding.s of fh.c AAAI-87; the Si:r.th. N a tiona/ Co nferenC£ on A r•tificial lntdhgence, pages 224-228, 1987 . 4. Ide, 1987) 5. N. C. Ide. Integration of Process Planning and Solid Modeling through Design by F••aturPs. Mas- ter's thesis, Universit.y of Maryland , College Park , 1987. 6. [Karinthi and Nau , 1989] R. Karinthi and D. S. Nau. 1989. Paper in preparation. 7. [Maeda and Shinohara, 1988] Y. Maeda a nd K. Shino- hara. Geometric reasoning and organized optimiza- tion for automated process planning. In Proceedings of the Seventh. N a.tional Confenna on Artificial In- tcl/igencc , pages 105-110 , Aug 1988. 8. [Nau, 1987] D . S. Nau. Automated process planning us- ing hierarchical abstraction. Texas Instruments Tech- nical .Jo• ur•na/, 39-46 , Winter 1987 . Award Winner , Karinthi and Nau Texas Instruments 1987 Call for papers on Industrial Automation . 9. [Nau and Gray, 1986] D. S. Nau and M. Gray. Sips : an application of hierarchical knowledge clustering to process planning. In Proceedings of the Winter An- nual Meeting of ASME, Anaheim, CA, pages 219-225 , 1986. 10. [Nau et al. , 1988] D. S. Nau, N. Ide, R . Karinthi, G . Vanecek , and Q . Yang. Solid modeling and geometric reasoning for design and process planning. In Proceed- ings of the American Association for Artificial Intelli- gence Workshop on Production Planning and Schedul- ing, pages 1-9, August 1988. 11. [Pinter, 1982] C. Pinter. A Book of Abstract Algebra. McGraw-Hill Book Company, 1982. 12. [Requicha and Voelcker, 1985] A. G. Requicha and H. B. Voelcker . Boolean operations in solid modeling boundary evaluation and merging algorithms. Pro- ceedings of the IEEE, 73(1):30-44, 1985. 13. [Requicha and Vandenbrande, 1988] A. G . Requicha and Jan H. Vandenbrande. Form Features for Me- chanical Design and Manufacturing. Technical Re- portJRIS Z44 , Institute for Robotics and Intelligent Systems , University of Southern California, Los An- geles, October 1988. 14. [Vanecek and Nau , 1988] G. Vanecek Jr. and D. S. Nau . A General Method for Performing Set Operations on Polyhedra. Technical Report. CS-TR-2057 , lJ niversity of Maryland, College Park , 1988.