_a~lr¢ - 4,4,“. v 4.. |Nul~>'l-"~ 3‘ ,_ .‘ww “mew—é. Mr 4.--‘.._‘- - w—aa’}: 4-4". {-4 -‘ ':--»‘- . 4‘ 0‘5“?" .2‘ Jim—.3? "r 4 ' “’4‘“ 4%“ y. a; v V ww‘ .w—4 a. 8 “EM: ,. ”Ettfif‘tfi‘a . n 4‘ p. u. - m 4 ‘ 25 ‘ _ :b' wk: ‘ Mga'fiffi" 4‘ g .5 $3: 9“ mmrmmé' M" 4:34“. ' -‘ _,, > 4 ,a ’. :9 v :94. "pr-:4.“ f 7 MM. ., "4 r 4 t ,5“ '" s z :3. t ‘3 H 4' , fl ,. , ‘ .4 X‘ ' g. a , v- - 3 , .> < H - s ‘ ’ 5 WA. I “x; 4‘9 "‘9‘" $543.“? “‘3‘"? ‘ In- 59%;” «”1513 I 3 ‘ “‘k 152' Y .3 v' - ‘ v ”-r ’nfifi‘afi‘rm.‘ 6‘3“ ' .,J l v ”fifg‘t'c .134, 443. .‘ ”w '5‘?“- .a.«.$‘§‘»’&3 , 'x . - » ¢ 73h..- 3M" V ‘ A" g. 5, ‘ s. “L...“ I 4 ‘3' - '91»- :4 Va; ‘“ . - “9:3” , , "'uo‘n. amt —4..-;~ gvfim ‘ (k. n “1-143‘5‘11“ , 3" . - . ’V-A.) -_ €~ 4 I r". ,5" l - " if: 7v: ‘1 - ‘...' w , ’ . age 44.3% 4’ .4» " - ‘ ,. 1..“ ‘ 44 141534 I . y ‘ '\ ‘ l‘ ‘ ‘ ‘ l . a ‘0‘- ‘ . ‘a “34' was; was”; ~L° 44. 2 ‘V ' ““4"” " 'nwfirfi .4» ' ‘99:... 5‘81” \ . jinx...“ $11453 “‘fwi‘" A3,? .. ~.. {4 1* 44435333 1 M .. a it 433%” n. “:réw u .' V .7» . ,4ng Mr": 4.4 .19." ‘ :“f fifigfigi ‘Ar’gw-gx ul“ ‘- I ’u 4 urn. - #3.!“ , L wfifi‘gi‘55‘i‘zcé" ‘5‘ all J ‘ z "4 u .- .131 ‘ a _ . 4 a Fm'na“ " xs ‘1 ' ""‘ =14 ‘1 ' T2? 3!. ‘ .. . 5:434:43? 41544" 4 ’m.4,%4j““§ifé‘fgzirv “" , 4444531343 . ' ”"133 V . _ a 7g!" a 3;}: may, .' fl! _ , _ 7 - 94‘ .. " 'iii‘“???w “'0 . ‘4 A I 4 ‘KrJ an“ \AC ‘4.“ u i, 34:11: A “Rm... . “5.4351: Vii-533$” ."J' ‘ . . . f“ s Q 5 ¥ ' -w- -. f .. ' M‘ A. , «ml-fin: I: "‘1‘ I «f . ‘ 3r , 4 WWI-'33 “’31 k ‘1 53;; ‘ “2‘: ' ‘ "'- ml " a'v-g ,V .W- 4 ,3 ‘ 4 5-3 3‘33er ' . 9" ggfiw 4 3“2‘ ‘ 2. , “I - ';v (.4 ('1‘ )5" . ‘41- .' Wig” “E“ :4 4‘“ :9” 2,“ H1731 » - ‘ "A1. 5-“ «rs-t" ”2:34;” A ’0 “- IGAN mm 5383-} ‘1’ :37 F "I.“ Th -‘ i. m ‘ mes ;3;’£3 R 1 3 ma. :4. isr¢{f‘unlv$?51wuaaA ' mm W Ml l u i SH! l H . . 43% H 1 u ““‘ll““l _ 10,-: u7"£'l_";'i‘. 3575:”: -r ,1. llll Filth-.auwin .. : 31 93 00779 3072 -¢ L... 5‘9 ' 4-A‘- -. This is to certify that the dissertation entitled Computer Aided Process Planning: Task Representation and Sequencing presented by Joseph M. Miller has been accepted towards fulfillment of the requirements for Doctoral degree in Computer Science ‘ 33% V Major professor Date 75L}? lfi‘lO MSU is an Affirmative Action/Equal Opportunity Institution 0-12771 PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before die due. DATE DUE DATE DUE DATE DUE MSU It An Afflrmdive Action/Equal Opportunity Institution Wanna-9.1 Computer Aided Process Planning: Task Representation and Sequencing By Joseph Michael Miller A DISSERTATION Submitted to Michigan State University in Partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1990 Abstract Computer Aided Process Planning: Task Representation and Sequencing By Joseph Michael Miller Process planning is a combination of art and engineering concerned with organizing manufacturing operations to turn raw materials into a product. The computer offers the process planning task increased potential for standardization, optimization, and more rapid response to changes in part design or in the manufacturing conditions on the fac- tory floor. This thesis investigates the representation and sequencing of tasks in process planning. Unfortunately, a large number of possible process plans can make finding efficient plans very difiicult. An Automated Assembly Planning with Fasteners (AAPF) system is described that uses geometric reasoning to derive feasible assembly sequences based on the geometric data present in a CAD model. AAPF is the first automated assembly planning system to pay attention to individual fasteners. It automatically derives which components in a product are held together by which fasteners, and uses this connectivity information and the type, size, orientation, and location of fasteners to aid in determining eflicient assem- bly plans. An algorithm is presented that acts as an oracle in determining the number of possi- ble task orderings using a precedence graph representation for a set of tasks and pre- cedence constraints. The Oracle uses three subgraph reduction patterns to find the exact number of possible task orderings for a class of N—fold graphs or an upper and lower bound on the number of orders for all other precedence graphs. An analysis of the Ora- cle algorithm shows that an exact answer or bounds on the number of possible orders is calculated in 00/2 * E) time and 0(V2) space. A CAPP system for Concurrent Design and Evaluation (CDE) is proposed but not implemented. CDE takes advantage of the Oracle algorithm and two interactive design critics to help find eflicient process plans. Although some components of the CDE sys- tem exist, others require additional research into diflicult problem solving areas such as: path and grip planning, determining stability of objects, and incorporating inspection and testing into plans. Publication Information Earlier versions of parts of this dissertation have appeared in the following publications: 1) 2) 3) 4) 5) 6) "Precedence Constraints and Tasks: How Many Task Orderings ?", Joseph Miller, George Stockrnan, 1990 IEEE International Conference on Systems Engineering, August 9-11, 1990, Pittsburgh, Pennsylvania, pages 408-411. "The Number of Linear Extensions in a Precedence Graph", Joseph Miller, George Stockrnan, 1990 IEEE International Conference on Robotics and Automation, May 13-18, 1990, Hyatt Regency, Cincinnati, Ohio, Vol. 3, pages 2136-2141. "Determining Search Space Size in Precedence Graphs", Joseph M. Miller, George C. Stockman, First Great Lakes Conference, October 18-20, 1989, Western Michi- gan University, Kalamazoo, Michigan. "Computer-Aided Process Planning: An Introduction and Overview", Joseph Miller, George Stockrnan, PRIP Lab Technical Report No. PRIP-89-3, February 1989, pp. 62. "A utomated Assembly Planning with Fasteners", Joseph Miller, Richard Hoffman, 1989 IEEE International Conference on Robotics and Automation, May 14-19, 1989, Registry Resort Scottsdale, Arizona, Vol. 1, pages 69-74. "WoodMaster: A Process Planner for Wooden Objects Made up of Block and Cylindrical Components", Joseph Miller, Case Center Technical Report, April 1988, pp. 65. iv To my parents, and my wife, Bev ACKNOWLEDGEMENTS I wish to thank my thesis advisor Professor George Stockrnan for his time, effort, guidance, and the occasional canoe outing. Without his direction and encouragement this endeavor would not have been possible. Many thanks are due to my committee members Professors Erik Goodman, William McCarthy, and Anthony Wojcik for their guidance and support. Special thanks to Dr. Goodman for directing me during an independent study course on Computer Aided Process Planning and for making the facil- ities of the Case Center available to me. I also wish to thank Dr. Wojcik for supervising me during an independent study course on Artificial Intelligent Languages. Over the course of my studies at Michigan State I received help and direction from Drs. Dubes, Esfahanian, Geske, Hsu, Ni, Jain, Sticklen, and Thceryan. Additionally, I gratefully ack- nowledge all the other faculty members who have made my educational experience both worthwhile and interesting. Many kudos to H. R. Keshavan and Richard Hofl‘man at the Northrop Research and Technology Center for their support and help -- especially, during my summer internship in 1988. I thoroughly enjoyed and academically benefited from my Northrop experience. I appreciated the thought provoking discussions, snail mail, and e-mail correspondence that I had with Thomas DeFazio, Rick Homnan, Luiz Homem de Mello, Peter Winkler, Jan Walter, and Yifei Huang. This thesis was greatly enhanced by their feedback and helpful hints. Of course, the responsibility for the contents of this dissertation remains with me. This research has been supported in part by the National Science Foundation grant #CDA-8806599, the Northrop Research and Technology Center, and Michigan State University. Special thanks to the Department of Computer Science for supporting me with a Graduate Assistantship throughout my educational experience and for the occa- sional travel funds that allowed me to present my research results and attend various conferences. I appreciate Dr. Anil J ain’s support and encouragement during my years as a PRIP lab System Manager. Over my academic career I was fortunate to qualify for a three year Distinguished Dean’s Fellowship and several G.T.E. Fellowships which relieved me from the worry of how to pay my bills and allowed me to concentrate more fully on my research. I must acknowledge the support and kinship of all former and current graduate stu- dents at Michigan State, especially Rick Hofirnan, Gongzhu Hu, Bruce McMillin, Sei- Wang Chen, Patrick Flynn, thyng Lee Hoffman, Farshid Farrokhnia, Deborah ‘Iiytten, Narayan Raja, Greg Lee, Arun Nanda, Tim Newman, Eugene Wallingford, Mahmoud Pegah, John Kern, and Satish Nadabar. The weekly PRIP and AI/KBS meetings gave me an opportunity to learn more about the fascinating wealth of information in these areas. Additionally, the occasional Chocolate Cake party or trip to the M.S.U. Dairy Store for ice cream helped to make graduate life more bearable. Many special thanks to Dave Marks for carrying out and improving the system management of the PRIP lab facilities. Last but foremost, I acknowledge the love and support of my parents, family and especially my wife, Bev. Additionally, I thank my father, Dr. Raymond Miller (the origi- nal "Dr. Miller"), for being such a positive role model. Finally, I acknowledge the many opportunities and blessings I have received directly and indirectly from my relationship with the Lord who truly made all of this possible. vii Table of Contents List of Tables .................................................................................................................. xii List of Figures ................................................................................................................ xiii Chapter 1. Introduction ............................................................................................. l 1.1. What is Process Planning -- -- - - -- - ......... .............. 2 1.2. The Manufacturing Cycle .................................................................................... 5 1.3. Approaches to CAPP ........................................................................................... 6 1.3.1. The Variant Method of CAPP ................................................................... 6 1.3.2. The Generative Method of CAPP ............................................................. 9 1.3.3. Assembly Planning .................................................................................... 10 1.4. The Organization of the Thesis ........................................................................... 11 Chapter 2. Computer Aided Process Planning ...................................................... 14 2.1. Process Planning Systems ................................................................................... 15 2.1.1. A Variant Approach: CAPE -- 16 2.1.2. A Generative Approach: DCLASS - - - - -- 16 2.1.3. An Expert System (AI) Approach: PROPLAN ....................................... 18 2.1.4. The WoodMaster Process Planner - ......... - -- 20 2.2. Assembly Planning .............................................................................................. 22 2.3. Representations for Process Planning ................................................................ 24 2.3.1. Importance of Solid Modeling and Representation ......... 24 2.3.2.1F-THEN Rules - -_ - ........ - 28 2. 3. 3. Frames ................................................ - 29 2. 3. 4. AND/OR Graphs - ...... - - ...... - .......................... 30 2. 3. 5. Decision Trees and Precedence Graphs ................................................... 35 2.4. Parallels to Disciplines 1n Computer Science - - 37 2.4.1. Artificial Intelligence ........... - - - - - -- - 38 2. 4. 2. Expert Systems and Process Planning ...................................................... 39 2.4.3. Operating Systems and Scheduling Theory .............. 42 2.4.4. Natural Language and VLSI Design - - -- -- - -- - 43 2.5. Diflicult Problems in Process Planning - - - -- - 45 2.5.1. The Knapsack Problem“ ...... - ......... -- .......... 45 2.5.2. The Equal Execution Time Scheduling Problem ..................................... 45 2.5.3. Search Combinatorics Problems ............................................................... 46 viii 2.5.4. Concurrent Design Issues .......................................................................... 48 2.5.5. Assembly Planning Problems - - - - ........ - 49 2.5.6. Geometric Representation and Reasoning -- - 50 2.5.7. Summary of Chapter 2 -- ..... -- ..................... 52 Chapter 3. Assembly Planning - - -- - ........................ 53 3.1. Introduction -- ............ . 54 3.1.1. Previous Work - ......... 54 3.1..2 Automatic Assembly Planning with Fasteners ........................................ 58 3.2. Approach .......... - ....... -- ............... 59 3.2.1. Assumptions - - - - - - - - 60 3.2.2. Overview of the AAPF Algorithm - 61 3.2.3. Disassemblyin AAPF - - - - - - . 64 3.3. Experimental Results ........................................................................................... 67 3.3.1. Models Used -- - -- - - 68 3.4. Evaluation of Process Plans - - - 71 3.4.1. Manufacturing Operation Time Costs - - -- ...... 72 3.4.2. Discussion of Evaluated Process Plans -- - ......... . 74 3.5. Summary of Chapter 3 -- -- - ...... -_ 76 Chapter 4. Representing and Sequencing Constrained Tasks ............................ 79 4.1. Motivation .............. -- ............................. 79 4.2. Background .......................................................................................................... 83 4.3. Representation ...................................................................................................... 86 4.3.1. AND (A), OR (V), and 5 Relationships ................................................... 86 4.3.2. Precedence Graph Representation ............................................................ 88 4.3.3. N-Fold Graphs ............................................................................................ 88 4.4. Subgraph Replacement ........................................................................................ 90 4.4.1. Series Replacement ................................................................................... 92 4 ..4 2. Parallel Replacement ................................................................................. 92 4 ..4 3. N Patterns ................ .................. 93 4. 5. Determining the Number of Task Orderings .................. 95 4.5.1. Assumptions ..... - ...... -- ............... 95 4.5. 2. Preprocessing a Precedence Graph ....... 96 4. 5. 3. The Oracle Procedure rs an Algorithm ...... - - -- - - 97 4. 6. Examples - - - -- ......... - - ................ 97 4.61 WeekdayTasks-- -- ----.-- - - - .......................... 98 4. 6. 2. Gearbox Assembly ..................................................................................... 99 4. 6. 3. Pen Assembly - - - - ...... . .......................... 99 4. 6. 4. Mechanical Mouse Assembly ................................................................... 101 4.6.5. Door Mechanism Subassembly ................................................................. 103 4.7. Handling more than N-Fold Graphs ................................................................... 104 ix 4.7.1.Graph'I‘ransformation- -- - - -- . 105 4.7.2. Subgraph Replacement .............................................................................. 106 4.8. Summary of Chapter 4 - . - - 107 Chapter 5. The Oracle Algorithm -- - - ............................................... 108 5.1. Representation and Initialization ........................................................................ 108 5.1.1. Graph Initialization - . . ...... - - 109 5.1..2 Insuring that the Graph rs Connected ....................................................... 110 5.1.3. Removing Redundant Constraints 111 5.1.4. Uniqueness of the Reduction Patterns and Resulting Answer ................ 114 5.2. Serial and Parallel Reduction Stage ....... - .......... 116 5.2.1. Merging of Two Vertices in Series - - - 117 5.2.2. Checking for Two Vertices in Parallel ...... - -- - ............. 118 5.2.3. Merging of Two Parallel Vertices ............................................................. 121 5.3. N Reduction Pass ................................................................................................. 121 5.3.1. Checking for N Patterns in the Graph ...................................................... 123 5.3.2. Merging an N Pattern of Vertices ............................................................. 124 5.3.3. Checking for Further Parallel/Series Merges .......................................... 126 5.4. Upper and Lower Bound Estimates - - - .............. 126 5.4.1. Lower Bound .......... _ -- -- .................... 127 5.4.2. Upper Bound .............................................................................................. 131 5.4.3. Lower and Upper Bound Estimates .......................................................... 133 5.5. Overall Complexity of the Oracle Algorithm .................................................... 134 5.6. Performance of the Oracle Implementation ....................................................... 135 5.6.1. Correctness of the Oracle Program Code ................................................. 136 5.6.2. Percentage of N-fold and Simple-fold Graphs ........................................ 139 5.6.3. Experimental Run Time for the Oracle .................................................... 143 5.7. Summary of Chapter 5 ............ - - - .................................... 146 Chapter 6. Concurrent Design and Evaluation ..................................................... 148 6.1. Process Planning Domain and Environment ...................................................... 149 6.1.1. Product Domain - - - - - -- 150 6.1.2. Factory Environment ................................................................................. 151 6.2. The Concurrent Design and Evaluation System - - -- _ . - 152 6.2.1. Information Storage and Data Structures ................................................. 155 6.2.2. Factory and Domain Specific Database ................................................... 156 6.2.3. Solid Modeling Package _ - ........ - ................. . ........... - _ 157 6.2.4. Interactive Assembly and Process Planning Critics - 159 6.2.5. Process and Assembly Planning modules -- - - -- -- - - 160 6. 2. 6. Oracle Module .............. - - 162 6. 2. 7. Search [Evaluation / Simulation .............................................................. 162 6.3. The Oracle Software - ....... ...... . ........................................ 163 6.3.1. Current Implementation of the Oracle ..................................................... 164 6.3.2. Extensions - - ....... - ...................... 164 6.4. CDE: Theoretical Research and Implementation Issues ................................... 165 Chapter 7. Conclusion, Discussion and Areas for Future Research ................... 168 7.1. Summary of Thesis -- ............... 168 7.2. Contributions of the Thesis ................................................................................. 171 7.3. Discussion and Areas for Future Research ........................................................ 172 Appendix I: Sample Input and Output from the AAPF System ........................... 176 Appendix 11: Evaluation of Process Plans ................................................................. 178 Appendix III: Comparison of the Oracle to Enumeration ..................................... 189 Bibliography ................................................................................................................... 191 xi List of Tables Table 3-1: Automated Assembly Planning with Fasteners ........................................... 55 Table 3-2: Object Table and Run Times - .......... ................................. 68 Table 3-3: Manufacturing Operation Time Costs - - -- . - - -- 74 Table 3-4: Comparison of Process Plan Manufacturing Times .................................... 75 Table A-1: The Oracle vs. Enumeration for Selected Example Graphs ...................... 189 Table A-2: The Oracle vs. Enumeration of Unconstrained Tasks ................................ 190 Table A-3: The Oracle vs. Enumeration of Nested Simple Fold Graphs .................... 190 List of Figures Figure 1-1: Raw Materials —> Final Product ................................................................. 2 Figure 1-2: Example of a Process Plan (Route Sheet). ................................................ 3 Figure 1-3: Rotationally Symmetric Part [Lind83] ....................................................... 8 Figure 2-1: Rotational part representation used by PROPLAN [Phil85] .................... 19 Figure 2-2: Spatial Occupancy Enumeration for a 'llrbe .............................................. 25 Figure 2-3: Constructive Solid Geometry ..................................................................... 26 Figure 2-4: Volume swept by an area ............................................................................ 27 Figure 2-5: Boundary Representation - - - .......... 27 Figure 2-6: All 35 Possible Car Assembly States ......................................................... 32 Figure 2-7: Toy Car AND/OR Assembly Graph ........................................................... 33 Figure 2-8: Example of Decision Tree & Precedence Graph Sizes - - - -- 36 Figure 2-9: Information flow among the four modules in an expert system ............... 40 Figure 2-10: Block with four holes in it. ...................................................................... 46 Figure 3-1: Object Models Assembled by AAPF ......................................................... 70 Figure 3-2: The Mouse Assembly -- _ - - -- - - - - ..... . ................ 70 Figure 3-3: Manufacturing Environment Model ............... - -- - .................. 73 Figure 4-1: A linear list of vertices - - - - - - ........... 89 Figure 4-2: The Three Oracle Replacement Patterns ................................................... 91 Figure 4-3: Formula 2 for an N shaped graph ............................................................... 94 Figure 4-4: The three possible divisions for Figure 4-3 b ............................................ 95 Figure 4-5: Weekday Morning Tasks ............................................................................. 98 Figure 46: Gear Box Example ...................................................................................... 99 xiii Figure 4-7: Bourjault Pen Example [Bour84] - ....................... 100 Figure 4-8: Mouse precedence graph (1 of 2) ............................................................... 101 Figure 4-9: Mouse precedence graph (2 of 2) ............................................................... 102 Figure 4-10: One of Several Precedence Graphs for a Door Mechanism ................... 103 Figure 4-11: Graph Identity ............................................................................................ 105 Figure 5-1: Redundant edge removal ............................................................................ 112 Figure 5-2: Series and Parallel Vertices .......... ..................... 116 Figure 5-3: Tough cases for the CHECK_PARALLEL algorithm .............................. 120 Figure 5-4: An N shaped pattern of vertices ................................................................. 122 Figure 5-5: 0( I V l2) tests are not required using the test in step 2 ............................. 125 Figure 5-6: Lower Bound Transformations ................................................................... 128 Figure 5-7: Lower Bound Transformations ................................................................... 129 Figure 5-8: Upper Bound Constraint Removal Heuristic ............................................. 132 Figure 5-9: Lower and Upper Bound Estimate Examples -- -- . -- - . ............... 133 Figure 5-10: % of N-fold and Simple-fold graphs in a Random Sample .................... 142 Figure 5-11: Oracle CPU Time for Random Graphs (Decision Problem) .................. 144 Figure 5-12: Oracle CPU Time for Random Graphs (Exact Values and Bounds) 145 Figure 6-1: Integrated Design of Product and Manufacturing System [Nevi89] 150 Figure 6-2: CDE System Interaction Diagram .............................................................. 153 xiv Chapter 1 Introduction Process planning is a combination of art and engineering concerned with organizing manufacturing operations to turn raw materials into a product. Process planning requires the application of manufacturing knowledge, including knowledge about machines, tools, geometry, physics, manufacturing procedures, and costs associated with manufacturing the product. The computer offers increased potential for standardization, optimization, and more rapid response to changes in part design or in the manufacturing conditions on the factory floor. Products should be designed with manufacturability in mind, and ideally, fwdback from the process planning task would be incorporated into the final design. An overview of computer-aided process planning (CAPP) is given in this chapter. Process planning can be performed in many different domains such as composite parts, plastics, sheet metal, or discrete metal parts. Automatic process planning systems are developed for specific domains and for a given factory environment. After defining pro- cess planning, the role of CAPP in Computer Integrated Engineering is discussed. Next the manufacturing cycle is outlined to show how process planning is of critical impor- tance in creating a profitable product. Section 1.3 reviews the two main approaches used in computer-aided process planning. Variant process planning is currently the most common method since it builds upon existing databases of parts that are organized into classes based on group technology (GT) codes. The generative approach encodes the knowledge of a process planner into a set of rules that are used to automatically generate a process plan from a part description. 1.1. What is Process Planning Process planning involves taking product specifications, usually an engineering drawing (or as of late, the information in a CAD model), and producing a set of manufac- turing plans. Process plans are usually created by a process planner who is typically a production engineer or an expert machinist with many years of experience. The final process plan contains the steps necessary to transform raw materials into the desired pro- duct. O ,4 Process Planning 4 / RAW MATERIALS Figure 1-1: Raw Materials —) Final Product In general process planning is a complex activity and there is no guarantee of an optimal manufacturing plan being produced. An optimal process plan is least costly in terms of the time or money required to produce the desired part. A goal of computer- aided process planning is to produce optimal process plans automatically, given a pro- duct design. However, compromises are made to allow a small amount of human inter- vention, and suboptimal but usable process plans often result. Computers are being used with increasing frequency in this domain to maintain consistency in the detail and quality of process plans and to optimize the resulting manufacturing plans at either an individual product level or global factory level. 3 Process planning is one stage in Computer Integrated Engineering (CIE). CIE is the use of CAD/CAM technology to integrate the engineering functions of product design, specification, and production [Rich86]. Computer-aided process planning can actually help bridge the traditional gap between Computer Aided Design (CAD) and Computer Aided Manufacturing (CAM). Not only is the process planning problem of important practical interest to CIE, but it is of theoretical interest in computer science because it requires both ordinary computer power and high-level heuristic decision-making. The task of process planning is complex; no general purpose automatic process planners have been built. Even human experts are limited to particular domains by the large amount of knowledge and experience needed Process Plan (Route Sheet) M NO. 4 2 PW mm" are ”NEW“: Author oe Date Operatism . Setup. No. Descrrptron Machrne Descrrptron 10 Cut 3"x3" stock to 4" Band Saw #2 Stock in 8" clamp 15 Tina to 3" diameter Lathe #4 Stock in 4" Chuck 20 Drill 1/4 "center Multi-spindle Drill Use 2000 rpm 1/4" steel bit hole Stock in cylinder clamp Figure 1-2: Example of a Process Plan (Route Sheet). A concrete goal of Computer-Aided Process Planning is to automate as much as possible the creation of a process plan or route sheet from the description of a product. For example, in process planning for discrete metal parts, a route sheet or process plan gives the detailed routing or processing steps that are applied to a set of raw materials to 4 create the desired product. More specifically, it contains information on the machines, tools, speeds, feeds, and other machining information to be used in changing the raw materials into the final product. Figure 1-2 shows an example process plan for a cylindri- cal part. Process planning bridges the gap between the product design and manufacturing stages. Automation of the process planning step is important for several reasons: 0 More human process planners are required in the U.S. than are currently available [Chan85]. The routing sequences can be standardized for similar parts. More eflicient (less costly) process plans can be produced. The productivity of process planners can be increased. Other application programs and simulation steps can be incorporated into the pro- cess planning task [Groo80]. Automating the process planning stage and integrating it with the other manufacturing stages helps to reduce costs and increase productivity. Standardization of process plans through automation can minimize the number of difl‘erent process plans for similar parts. Situations where many suboptimal process plans are in service occur more often in a factory environment without the centralizing effects of automation. For example, in a factory setting, a total of 42 difi‘erent routings, covering 20 difi’erent machines, had been developed for various sizes of a relatively simple part called an ’expander sleeve.’ The reason given for the large number of routings was that eight or nine manufacturing engineers, two planners, and 25 NC part programmers had made the 42 nonstandard plans. "Upon analysis, it was determined that only two difl‘erent routings through four machines were needed to process the 64 difi‘erent part numbers" [Groo80]. Group technology is a classification and coding system for identifying similar parts by their code numbers and is used to index existing plans. It can help avoid dupli- cation of efl’ort and use of less efiicient routings when used in computer-aided process planning to identify similar types of parts. 1.2. The Manufacturing Cycle An overview of the manufacturing cycle is beneficial to see how process planning fits in and how it can be used to improve the manufacturing cycle. Generally the follow- ing groups are active in the manufacturing cycle [Groo80]: 1) sales and marketing 2) product design and engineering 3) manufacturing engineering/process planning 4) industrial engineering 5) production planning and control 6) manufacturing 7) quality control 8) shipping and inventory control The initial call to make a product comes from the sales and marketing department. This is the result of marketing predictions or the requests of customers. The product design and engineering group will use the part specifications and requirements to come up with a detailed design for new products. Feedback from the other groups on the ease of manufacturing, maintenance, and cost helps determine a viable design. By automating the process planning task it is possible to take the specifications of a design and to quickly provide the design and engineering groups with a set of projected production times and costs for the product. This fwdback allows the designers to improve the design for manufacturability and profitability. Manufacturing engineers are responsible for creating the process plan for the designed part. The tools and fixtures needed to manufacture the part are also specified at this time. The industrial engineers determine the work methods and time standards for the individual production operations [Groo80]. Production planning and control formu- late a master schedule of quantities and delivery dates for the products being manufac- tured in the factory. The master schedule is used in material requirements planning (MRP) to determine the raw materials needed for the factory to produce goods. The other main task of the production planning and control group is production scheduling and maintaining the schedules despite dynamic problems on the shop floor. 6 The manufacturing group produces the final products from the initial raw materials. Quality control is responsible for checking the quality of the product as it is transformed from raw materials into the final product. The final step in the manufacturing cycle for a product involves the maintenance of inventory levels and shipping schedules to meet customer demands. For the interested reader the book by Chang and Wysk [Chan85] is a good introduction to CAPP systems with additional emphasis on the manufacturing, design, and process engineering functions. Concurrent design of products and processes is discussed by Nevins and Whitney [Nevi89]. 1.3. Approaches to CAPP Currently, two main approaches are used in CAPP [Phil85]. The variant approach has a library of stored process plans that have been used in the past. This database of stored parts and process plans is searched to find a process plan for a part that is of a similar type and physical geometry. Ideally, the process plan for the similar part will be close to a good process plan for the new part. In contrast to the variant method is the generative approach. Old or similar process plans are not used in the generative approach. The generative approach creates plausible process plans based on knowledge of the machines in a factory, the raw materials avail- able, and knowledge of which machines can create certain features. Each generated plan is evaluated according to a cost function so that an optimal solution or set of the most eflicient process plans can be identified 1.3.1. The Variant Method of CAPP In variant process planning the process plan for a similar part is used as a template to create the process plan for a new part. Typically, an experienced user is needed to help the computer form a process plan from this template. The most popular variant sys- tems are CAPP, Miplan, and AUTOPLAN [Bere86]. 7 A common misconception is that most parts are made in large manufacturing batches. However, the Department of Labor estimates that 75% of all metalworking in the U.S. is done in lot sizes of 50 or less [Lind83]. Thus, a variety of difi‘erent parts are made in the typical job shop. An important aspect of variant planning is the use of group technology codes to categorize parts into groups. This can help avoid creating process plans from scratch for parts that are only slightly different from parts in the database. Parts are usually grouped by physical geometry, production features, or from production flow analysis to group parts with similar operation sequences. Different physical and/or production features are encoded into a digital code that describes relationships and simi- larities among parts in the database. The code can be hierarchical with successive digits having meaning dependent on the preceding digits, or it can be a chain code with each digit representing a given feature independent of the other digits. A combination of these two schemes is generally more flexible and can be used by all groups involved in the manufacturing cycle. The purpose of a code is to serve as an index and grouping func- tion for a database of parts. Many coding and classification schemes have been developed to suit individual company and machine shop needs. A few of the more popular systems include the Opitz, CODE, and MICLASS systems [Lind83]. All three of these codes use both hierarchical and chain coding components to categorize parts. The basic Opitz coding system con- sists of nine digits which hold both physical geometry and manufacturing data. These digits hold information as follows: Digit Description 1 rotational/nonrotational part classes 2 main shape 3 rotational machining 4 plane surface machining 5 additional holes, teeth and forming 6 dimensions 7 material 8 original shape of raw material 9 accuracy Figure 1-3: Rotationally Symmetric Part [Lind83] In addition to these 9 digits another 4 digits may be added for particular applications and job shop dependencies. The CODE system consists of eight digits with each digit taking on one of the 16 hexadecimal code values. For example, the part shown in Figure 1-3 is encoded as 13388D72. The eight digit code 13388D72 is broken down as follows: Digit Description : Value 1 basic shape : cylinder = 1 2 concentric parts or parts diameters : multiconvex cylinder = 3 3 center hole type : a single blind hole = 3 4 non-center holes : bolt circle (2 holes) = 8 5 grooves or outside threads : threaded on one end = 8 6 combination of concentric variations, flats, slots, and protrusion features : sum of concentric variations (1), slots (4), and flats (8) = 13 (D) major outside diameter : falls in range of 1.2" - 2.0" = 7 overall length of 1.5" : falls in range of 1.0" - 1.6" = 2 ooq MICLASS has 12 digits in its universal code with up to 18 additional digits avail- able to tailor the code to the individual company. MICLASS is set up so that the code for 9 a part can be generated by a computer that asks the user a series of 8 to 20 questions about the part. The work part attributes coded in the first 12 digits of MICLASS are as follows [Groo80]: Digi Description 1 main shape 2 and 3 shape elements 4 position of shape elements 5 and 6 main dimensions 7 dimension ratio 8 auxiliary dimension 9 and 10 tolerance codes 11 and 12 material codes These codes are used not only in retrieving and storing similar parts and process plans in a database, but also by many other users in the CIM environment. 1.3.2. The Generative Method of CAPP Generative process planning uses machining and roofing knowledge along with pro- perties of the raw materials to determine candidate process plans. Each generated pro- cess plan is evaluated to find its cost to choose the best process plans. Numerous combi- nations of machining operations may be considered and the most appropriate operations chosen using heuristics. Variations of promising formats are tried in hopes of finding an optimal solution. Heuristic cost functions play a key role in narrowing the large range of possible plans to a workable set of good possibilities. A few of the generative systems are CADCAM, Acaps, CIMS/PRO, CPPP, Autap, and DCLASS [Chan85, Rich86]. Berenji has designated a third class of process planners: Artificial Intelligence based process planners, which are actually a subset of the generative class [Bere86]. They use AI techniques and the encoded knowledge of human expert process planners to generate the final process plans. This class includes the planners: Gari, Tom, PROPLAN, TOLTEC, and I-Ii-Mapp [Desc8l, Mats82, Phil85, Tsat87, Bere86]. Generative systems do not require the use of group technology; how- ever, the benefits of group technology to many other production engineering functions 10 make it an essential element in the manufacturing environment [Berr84]. Proofs of optimality exist for the generative approach only when it is used in a res- tricted "ideal" search space. In realistic situations no such guarantee exists for either the variant or generative approach. If the problem space can be set up in such a way as to facilitate an optimal search algorithm on an ideal search space, such as A ‘ , gradient des- cent or alpha-beta search, then it may be possible to find an optimal process plan for a particular criterion function [Nils80]. Some tools and representation schemes from the AI domain can be used to aid the process planning task. For example, AND/OR graphs, inheritance properties, and frames have been used in some CAPP systems. Similarly, many other AI techniques are useful in attacking the process planning problem. One of the most prevalent problems in automatic process planning is that of large search spaces. The use of knowledge or heuristics about the problem domain is one way that difficult search problems have been handled in the past. Expert system shells are often used in creating process planners to handle the large amount of domain-specific knowledge. These topics are discussed in Chapter 2. 1.3.3. Assembly Planning Assembly planning is an integral part of process planning. Products with more than one subpart must be assembled. The assembly, machining, and processing steps may be intermixed for some products. The sequencing of the these steps is very important in creating an efficient process plan. Assembly planning requires a computer representation of the components to be assembled. This information may be in the form of CAD data and/or a high-level representation (such as a part mating graph) of the components and their connective relationships. Often geometric reasoning techniques are used along with CAD data to determine valid assembly trajectories for subparts. 11 The general task of assembly planning involves determining not only the order of assembly for a set of n parts, but also finding valid grip points, dealing with the reality of gravity, part tolerances, and path planning. Optimal path planning in three-dimensions, even among polyhedral objects, is itself a problem which is known to require significant resources [Shar86]. This is only one of many challenging problems that CAPP presents to computer science. Chapter 3 discusses assembly planning in more detail. 1.4. The Organization of the Thesis The remainder of this dissertation and its contributions are outlined below: Chapter 2 surveys difierent types of CAPP systems. These examples illustrate some of the representational and computational difficulties involved in creating process plans automatically. The advantages and disadvantages associated with a spectrum of 3—D representation schemes are given along with other useful representations such as IP- THEN rules, frames, precedence graphs, and AND/OR graph representations. More intelligent and more powerful feature based geometric modelers and expert systems are necessary before CAPP can take an important place in the overall manufacturing cycle. It is shown that brute force search over alternative operations is intractable, and that heuristics such as scripts are helpful in organizing common subsequences of operations [Nau86]. The effects of gravity, fixturing considerations, and the necessity of avoiding unwanted collisions between machines and materials stretch our existing knowledge of common-sense and geometric reasoning. Chapter 3 addresses the lack of research dealing with individual fasteners in the automated assembly planning literature. The representation of fasteners and planning for fastener application is of critical importance in creating optimal assembly plans. Addi- tionally, most assembly planning systems require supplemental information on the rela- tionships between various subparts. These issues are addressed by the Automated Assembly Planning with Fasteners (AAPF) system. AAPF accommodates fasteners and 12 automatically determines feasible disassembly sequences based on the geometric data of the product. Under the assumptions of rigid subparts and no interior nor exterior forces, the reverse of a disassembly sequence is a valid assembly sequence. A mechanical mouse can be assembled in over 58 million difierent ways. Finding an optimal solution is not an easy task. Many different orderings exist for the set of tasks to be performed; some are much more desirable than others. Using a more practical assembly evaluation function than the heuristics and assumptions made by the AAPF system shows that although AAPF can produce good assembly sequences for some products, its lack of knowledge about fixturing constraints caused the mechanical mouse assembly solution to require 50% more time than an eflicient assembly sequence that accounted for fixturing constraints. Other process planning examples of good and bad process plans show an execution time difference of up to 100%, indicating the value of being able to find the efficient process plans in the large set of possible plans. Chapter 4 investigates the number of different sequential orderings for a set of tasks to be performed subject to a set of precedence relations. In machining, assembly, and general task planning, it is beneficial to know how many difi‘erent task orderings are pos- sible so that an efficient solution can be found in the most appropriate way. Although small search spaces can be enumerated, larger search spaces require heuristics and search techniques to limit the number of solutions evaluated to find a good solution in a timely manner. In general, determining the number of orderings for a set of tasks and constraints is intractable. To facilitate solving this problem, precedence graphs are used to represent the tasks and constraints. An Oracle graph reduction algorithm is presented that can quickly handle a class of graphs called N-fold graphs. N-fold graphs can be evaluated precisely using the three subgraph reduction patterns defined in this chapter. Arguments on the correctness for each of the three subgraph formulas are provided. After giving a set of precedence graph examples, several techniques are described for increasing the number of graphs that can be handled precisely. 13 Chapter 5 characterizes the Oracle algorithm and reveals implementation details. The uniqueness properties of the three subgraph replacement patterns and that of the final result for the number of possible orders for N-fold graphs is shown. A derivation of the time and space complexity [Horo89] for each part of the Oracle algorithm concludes that 0(V2 * E) time and 0(V2) space are required. The lower and upper bound estimating procedures are outlined for non-N-fold graphs and proofs of correctness are given. Empirical results on the percentage of graphs that the Oracle algorithm can handle exactly show that the algorithm can exactly evaluate most graphs with either a small or very large number of edges. Both an upper and lower bound on the number of possible orders is returned for graphs that cannot be evaluated exactly. Simulation results for the Oracle algorithm on random graphs show an 0(V2) time complexity for the range of graphs tested. Chapter 6 describes a CAPP software package for Concurrent Design and Evalua- tion (CDE) of products. Many of the components for this software package have been implemented here at M.S.U. or at other universities and industries. A single integrated package is described, but not implemented, which will aid in the design, manufacturing, and process planning tasks. Areas for future research in creating the proposed CDE sys- tem are discussed. Chapter 7 concludes with a discussion of the contributions of this thesis, answered and unanswered questions, and areas for future work. Chapter 2 Computer Aided Process Flaming Several process planning systems are studied to illustrate some of the diflicult prob- lems that arise in CAPP. The variant CAPE system is useful for standardizing parts, fixtures, and routings in process plans. CAPE uses group technology to connect its different modules and functions together and to enable similar parts to be easily identified, stored, and accessed. A generative system called DCLASS is discussed that enabled a 3:1 increase in productivity for sheet metal process planning. Unfortunately, when the DCLASS system was expanded to handle simple rotational parts, the lack of a good representation scheme made the system difficult to use. In fact, the designer quickly became frustrated with the large number of questions that DCLASS asked about the rotational part being created. Unlike the DCLASS implementation, an AI based process planner called PRO- PLAN performs well on a set of simple rotational parts. Using a CAD database, the sys- tem derives the information necessary to create process plans for rotational parts. Key to the success of the PROPLAN program is the representation used to transform the prob- lem from a three-dimensional problem to a two-dimensional one. This points out the importance of finding an appropriate representation for the planning problem. The WoodMaster system uses constructive solid geometry (CSG) representations of wooden products and a knowledge base consisting of machining information and the factory environment to determine a process plan. Determining the feasibility of machining operations or optimizing a sequence of operations is a difi‘nult task. 14 15 Assembly planning is needed whenever two or more subparts make up a product. A large body of literature addresses the assembly planning and designing for assembly problems. However, the field of automated assembly planning is still in its infancy. Determining eflicient assembly sequences is diflicult due to the three-dimensional nature of the assembly environment and the combinatorial explosion of the number of possible assembly sequences for N subparts. As with many issues in computer science, the representations used in CAPP are extremely important. Significant problems are posed in the areas of knowledge represen- tation, geometric modeling and reasoning, planning, combinatorics, and searching for eflicient solutions. Often several solid modeling schemes are used in CAPP so that the most appropriate representation can be used for a given subproblem. The most common three-dimensional representation methods are discussed and then used to represent a cylindrical tube. Manufacturing knowledge and expertise can often be efliciently represented using IF-THEN rules, frames, scripts, precedence graphs, and AND/OR graphs. The benefits and drawbacks of these representation schemes are discussed since they are currently used in many of the automated manufacturing and assembly planning systems. Many of these representation schemes are borrowed from computer science. Artificial intelli- gence, VLSI design, operating systems and scheduling theory all have benefited from and can contribute to CAPP. 2.1. Process Planning Systems Examples of the variant, generative, and artificial intelligence approaches to pro- cess planning are investigated to illustrate different aspects of process planning. Com- plex computer processing, data extraction, decision, and representation issues arise in process planning even for simple parts. It is important to find good representations for object geometry, the factory environment, process planning expertise, and the 16 intermediate results obtained from applying machining operations to raw materials. 2.1.1. A Variant Approach: CAPE The Computer-Aided Production Engineering (CAPE) system developed by the Garrett Turbine Engine Company [Berr84] is a variant system based on group technology part codes. Any given part belongs to both a routing family and a drawing family. A routing family contains plans with similar machining sequences. When new technology or manufacturing methods are introduced into the plant, it is possible to change all pro- cess plans in a routing family at the same time. The drawing family contains parts with similar geometric properties. This information is useful in processing queries of similar parts. For example: the part in Figure 1-3 is identified with the code 13388D72. Similar parts can be found by querying the database with the value 13388D72 or by specifying a subset of these digits such as 13?88D72 to find similar parts without worrying about the type of center hole in the part (3rd digit). Geometric details are stored in the Part Description Program (PDP), along with sur- face tolerances, finishes, and other non-geometric data. Great effort is placed on using standard fixtures, routing, and tooling wherever applicable to reduce set-up time, change- over time, and stock inventory. The power of CAPE lies in its modularity and expanda- bility. 2.1.2. A Generative Approach: DCLASS A number of CAPP systems use expert system technology to automate the task of process planning. DCLASS is a decision-making and classification system developed at Brigham Young University. It uses a hierarchical representation scheme to store the pro- duct domain, factory environment, and other process planning knowledge. The DCLASS system was first used to handle sheet metal parts, and later extended to handle a class of simple rotational parts. Even though working with sheet metal may produce a three- l7 dimensional part, from an engineering point of view it can be thought of as a two- dimensional problem [Rich86]. DCLASS queries the user via menus about the part to be created. Information about the raw materials to be used for the part such as its shape, number of holes, slots, and other part features are obtained in this manner. Similarly, other process information (such as heat treatment or painting) is obtained to create a pro- cess plan. The knowledge base in DCLASS is contained in hierarchical decision trees that are used to represent logical groupings of information. The decision trees are used as production rules by a forward chaining inference engine to produce the process plan for the part. After eight months of development, a system for sheet metal parts was tested in a manufacturing environment. DCLASS generawd a process plan for a part and then allowed the human process planner to modify the plan to improve its quality. A produc- tivity increase of 3:1 was realized in the sheet metal process planning efl‘ort itself [Rich86]. Another benefit of the generative process approach was an increase in the con- sistency of detail and correctness of the process plans. In several instances, design flaws or mistakes in the design specifications were discovered when the specifications called for an operation that didn’t appear on the selection menu presented to the user. For example, since no painting of aluminum was performed in their job shop, such an option would not appear as a valid choice in the user’s display menu, [Rich86]. Without the program the human process planner would have written the plan by hand. If the human process planners forgot that painting couldn’t be done on aluminum, they would have created an improper process plan that may not have been noticed until it reached the fac- tory floor. The next step in the development of DCLASS was to create a system for a small subset of simple rotational parts. Unfortunately, the number of special features (such as traverse holes, bevels, chamfers, threads, countersinks, counterbores, spherical ends, tapers, and knurls) in such parts was large. 80 many questions were asked of the users 18 that they became annoyed and frustrated. The number of parameters associated with more complex parts and their production made further attempts at generative process planning with DCLASS infeasible. If a CAD model were available, it may have been possible to derive the answers to many of the system’s questions from the CAD data. Both the PROPLAN and WoodMaster systems described below work directly from the CAD data to free the designer from being asked for this information again. Another problem encountered was the development and maintenance of the complex decision logic used in DCLASS. Changes in the factory environment or in a class of parts that are addressed by the system must be reflected in the hierarchical decision structure. It takes time and careful thought to change the decision making logic in such a way as to ensure the continued validity of the resulting process plans. 2.1.3. An Expert System (AI) Approach: PROPLAN Although DCLASS was found to be inadequate for simple rotational parts, the PROPLAN system proved to be less demanding on its users [Phil85]. PROPLAN is an example of a knowledge-based approach to generative process planning that creates pro- cess plans from CAD data to be used in a CAM environment. This system avoids the difficulties associated with asking the user for all the part specifications by deriving this information from a CAD database containing the part. PROPLAN is capable of analyz- ing the part geometry in its internal symbolic form to come up with a logical sequence of Operations to be performed on some raw material to produce the final result. The result- ing process plan specifies what machines and tools (drill bits, cutters, saw blades) should be used, what type of coolant is needed, and the speed, feed, and depth of cut for each operation. PROPLAN is also capable of explaining the line of reasoning it used to come up with the final process plan. This is helpful for developing and debugging the expert system and knowledge base. The system can be changed to accommodate different machinery and different types of tools. 19 INITIAL STATE: Material to be removed or Area to be removed from grid FINAL STATE: No material left or Area in grid = NIL x <. . . .....E...............E eeeeeeeeeeeeeeeee ihtecerfiael ooooo i 3 : profile I ......................... : : Pal“t : .............. external ........... Figure 2-1: Rotational part representation used by PROPLAN [Phil85] PROPLAN was implemented for a subset of rotational parts. Tianslation routines were used to convert part geometry from the CAD database representation to the internal symbolic representation used by PROPLAN. Part geometries were specified in terms of their internal and external profiles and additional features such as holes, slots, or key- ways. Internally, this information was represented as a part tree consisting primarily of the locations of profiling lines and arcs. One problem with using a computer to create process plans is due to the computer’s ineptness at organizing data by itself. From the representation of a part in a CAD database it is extremely difficult for the computer to know that a certain set of surfaces or lines represents (for example) a 1/4 inch hole that must be drilled. Therefore, a high-level understanding of the part geometry is required to create process plans. Higher-level part features such as holes, grooves, and adjacent surfaces must be represented in a format that can be easily manipulated and ’understood’ by the decision logic in the expert system. (This is a strong motivation for the "feature- 20 based" CAD systems under development today.) PROPLAN represents the task of material removal as a two-dimensional graph that shows the area that must be removed to process the part. This area is then subdivided into fixed-size sectors, rectangles, and triangles by drawing vertical and horizontal lines at every point of the profile segments [Phil85]. The fixed size of the sectors is deter- mined by the arnount of material that can be removed in one pass by a specific machine and tool type. Operations such as turning a part on a lathe to remove a layer of material are viewed as removing a rectangle from the internal two—dimensional grid representa- tion of the part. This simplification allows the three-dimensional problem to be viewed as a two-dimensional area removal process. Process plans were developed for several parts by PROPLAN and then compared to the process plans currently being used in a factory environment. The plans were similar; however, some difl'ered because of local constraints existing in the factory that were not accounted for in the expert system. Human process planners tend to describe operations at different levels of detail depending on how they feel -- for example, rushed, tired, etc. The computer-generated process plans had a more consistent level of detail than those from the human process planners. This is desirable at times to make sure the resulting product meets desired standards. The amount of detail is specified in the knowledge base of the expert system and could be increased or decreased as desired. The results did show that the system was efiicient and had the potential for practical application [Phil85]. 2.1.4. The WoodMaster Process Planner The WoodMaster system successfully creates a process plan for wood objects made up of block and cylinder primitive objects requiring hole making, lathe, or cutting opera- tions [Mi1188]. An infinite number of possible objects can be defined using the CSG model even though the geometric primitives are simple. A more useful program could be created with the addition of code, primarily in the form of machine and stock 21 specification tables, for other tools and stock materials. However, to create a viable industrial product more reasoning power is also required. The time taken by WoodMaster to create these process plans is comparable to the time taken by a human expert. It required 8 1/2 minutes and 15 minutes of computer time to create process plans for the pencil holder and toy car designs respectively. WoodMas- ter was designed as a graphical demonstration of process plan creation. WoodMaster first reads a part definition file. This file contains CSG data for block, sphere, cylinder, and tube-type object primitives as well as three types of fastener primi- tives. After the primitive object data is read in, it is entered into the I-DEAS 3-D object modeling system and displayed. WoodMaster then scans the table of primitives sequen- tially for objects. For each object the program determines a process plan for creating the basic primitive shape (block, cylinder, or tube) of the proper dimensions. WoodMaster finds a piece of stock material with the correct dimensions to create each subpart and then checks the tool specification database to find which tools can produce each feature in the subpart. Other process plan details such as assignment of specific machines to per- form the tasks, routing of materials, and detailed tooling parameters are not created by WoodMaster. A graphics window is used to display each part as it is being processed. All voids are checked to see if they intersect the object]. Intersecting voids correspond to material removal operations. Although many operations are used in a job shop (drilling, boring, milling, planing, reaming, etc.), only drilling, lathe work, and cutting operations are implemented in WoodMaster. To extend the number of available operations, additional code (in the form of data tables) corresponding to those operations can be added to WoodMaster. Once all voids are checked for intersection and processed, remaining unprocessed objects are processed. 1 A void is a negative primitive implying the boolean dilkrence operation. 22 In order to create a working process planner for wooden objects several simplifying assumptions were made. 1) WoodMaster assembles the objects in the order they appear in the input data to avoid assembly planning problems such as considering how to grip the parts to be assem- bled. 2) The efl'ect of gravity upon partial assemblies is not considered. 3) Only cutting, hole making, and lathe operations are needed to produce the indivi- dual parts of the object. Even with such a restricted world of objects, many of the hard processing and deci- sion making problems that appear in more complicated object domains arise. Problems such as the feasibility of performing a given operation and optimization of operation order occur at varying levels in the process planning task. 2.2. Assembly Planning Much work has been done since the early 1960’s on analyzing the process of assem- bly and in assembly line balancing [Akag80, Reym87]. The general assembly planning problem is treated in [Brod87, Hutc90, Lieb77, Loza76, Nevi89, Popp90, Sand90, Woo87], and examples showing a large number of possible assembly sequences are given in Section 4.6 of this thesis. One of the pioneers in the areas of Automatic Assembly and Design for Assembly is Geofi‘rey Boothroyd. He has investigated the methods and economics of automated assembly [Boot82]. Designing products for assembly can reduce part counts by 35 to 40% with significant reduction in assembly time. For exam- ple, the Pro-Printer dot matrix printer by IBM was designed for ease of assembly. The Pro-Printer requires three minutes to assemble and has 40% fewer parts than its predeces- sor, which required 30 minutes to assemble. In assembling the product there may be many possible orderings; some are very 23 ineflicient and only a few orders may be "optimal". The assembly problem requires modeling how to grip objects, along which directions the assembly motions will be, and determining whether or not parts will intersect during assembly. As mentioned earlier, in the toy car example, it is impossible to place both wheels on the axle and then try to put this assembly into the car body. This fact is hard to determine without simulating the assembly motions and seeing that a collision between a wheel or the axle and the car body will occur with this assembly order. For human process planners, some of this is common sense, but for computers it requires geometric reasoning and knowledge. AI researchers are finding out that common sense is diflicult to impart to programs. Apply- ing chunks of expert human knowledge to the process planning problem can constrain the total number of relevant operations [Tsat87]. The literature dealing with the automatic determination of assembly sequences has just recently begun to emerge. However, the roots leading to automatic assembly plan- ning systems can be found in work done in the areas of geometric representation [Requ80, Requ82, Kemp87], planning [Ste81a, Ste81b, Laug86, Cama87, Dona87], and artificial intelligence [Rich83, Wins84]. hTe assembly planning process is often carried out in a hierarchical fashion due to its complexity. This hierarchy is often broken down into assembly-level planning, task- level planning, manipulator-level planning, and joint-level planning [Huan90]. Huang and Lee have created an Automatic Assembly Planning System that consists of five modules: world database, simulated world model, knowledge acquisition mechanism, planning knowledge base, and assembly planner. CAD objects are first entered as CSG primitives and then transformed into B-rep which is used for all subsequent geometric reasoning operations. Their system automatically generates "an assembly plan subject to the resource constraints of a given assembly cell" and is designed to improve "the flexi- bility and productivity of flexible manufacturing systems" [Huan90]. 24 Research in geometric reasoning about gravity, stability, and reducing the computa- tional burden associated with the assembly planning of free form B-rep objects is under way by Hofl’man [Hof90a, Hof90b]. In certain industries, such as the aerospace industry, B-rep formats (which are needed for their aerodynamic properties) are essential because they allow free-form surfaces to be used. The BRAEN automatic assembly planning sys- tem is one of the few systems to reason about the effect of gravity and stability of assem- bly using purely geometric information [Hof90a]. Due to the complexity of the stability problem, the approximation methods used by Hofl‘man are suflicient but not necessary for detecting instability of subparts. Heuristics are used to guide the search for promising removal directions and distances. Chapter 3 investigates automatic assembly planning with fasteners in more detail. 2.3. Representations for Process Planning As the previous discussion on the expert system planner PROPLAN pointed out, the representation used can often turn a diflicult problem into one that can be tackled by an automatic process planner. This section reviews general methods of representation that can be used in process planners. After discussing the importance of representation in solid modeling, the subsequent sections discuss IF-THEN rules, frames, and the use of precedence and AND/OR graphs in the domain of process planning. Some similarities between the computer science disciplines of artificial intelligence, operating systems, and scheduling theory are made to point out how process planning can benefit from the theory and representations used in computer science. 2.3.1. Importance of Solid Modeling and Representation Central to the idea of process planning is the representation of real world objects inside computers. This is necessary in order for the expert system to know what three- dimensional object the process plan should create and assemble. A useful representation 25 scheme should have a way to determine if a certain representation is invalid. A represen- tation is invalid if it refers to an object that is not three-dimensional. For example, a straight line with no thickness (diameter) associated with it is an invalid three- dimensional object. Useful representations are also unambiguous. An ambiguous representation refers to more than one solid. Another desirable, although unnecessary property of a representation, is that there be only one way to represent a given solid. This is referred to as representational uniqueness. There are many difi‘erent schemes for representing solid objects. In the following representation schemes a figure shows how a tube would be represented. Some of the unambiguous schemes are: spatial occupancy enumeration, constructive solid geometry, swept volumes, and boundary representations [Requ80]. Top View Side View Figure 2-2: Spatial Occupancy Enumeration for a 'Ilrbe 1) Spatial Occupancy Enumeration - Specifies an object by a set of volume elements located at fixed grid points. The representation is unambiguous, unique, and easy to vali- date. However, for describing parts to be machined this representation is verbose, difficult to use to precisely model curved objects, and difficult to manipulate because of the many primitives. The representation of a tube shape (below) shows that curved sur- faces are approximated as closely as the cube-shaped elements allow. To get a better 26 approximation smaller volume elements would have to be used. This can lead to bulky definitions for objects. /\© m V Outer Diameter Cylinder Inner Diameter Cylinder O 0 Figure 2-3: Constructive Solid Geometry 2) Constructive Solid Geometry (CSG) - Solids are represented as an ordered binary tree of Boolean constructions or combinations of solid components via regularized set operations. This scheme is unambiguous, nonunique, and generally easy for both crea- tion and validation of object representations. CSG is one of the more promising representations for mechanical parts because it can easily represent most regular parts, has syntactically guaranteed validity, and is easy to use. 3) Swept Volumes - Specifies an object in terms of a cross sectional area that is translated through space along a specified vector. The volume swept out by the cross sectional area defines the three-dimensional object. This representation is useful in colli- sion detection and material removal operations. For example, in machining a part, the material removed is the intersection of the volume swept out by the cutting tool, inter- sected with the volume of the part. 27 Cross sectional area Figure 2-4: Volume swept by an area End Surface 81 End Surface 83 ---------------------- 73:". -----——--—-----------?~-\-\-\ - Outer Surface 82 / Inner Surface 84 Figure 2-5: Boundary Representation 4) Boundary Representations - A set of faces (surfaces) bounding the occupied volume are specified. Each face is defined by a set of bounding edges and vertices or by using another surface representation, for example, plane, sphere, B-spline patch, etc. Boundary representation schemes are unambiguous if faces are represented unambigu- ously, but generally are not unique [Requ80]. Validity is computationally hard to deter- 28 mine. However, boundary representations are useful in displaying different views of a part and in representing the relationship between difl'erent surfaces and edges. Since they can be derived from CSG representations (which are easy to validate, etc.), they can be used as an aid to a CSG representation scheme. The most commonly used geometric representations are CSG and B-rep. Both have a potentially large domain. CSG has syntactically guaranteed validity as well as being concise and easy to create [Requ80]. CSG and boundary representations are used in PADL2 to represent any solid bounded by any combination of arbitrarily oriented cylindrical, planar, spherical, and conical faces. To represent an even wider range of unsculptured and sculptured parts, several representation schemes could be used. How- ever, changing from one representation to another can be very difficult to perform (if not impossible). Certain geometrical questions are more easily answered in one representa- tion scheme than in another (and may even be impossible to answer in some representa- tions). Thus, the use of one main representation scheme and several auxiliary representa- tion schemes may be necessary to achieve a higher degree of versatility and efliciency. 2.3.2. IF-THEN Rules Often expert human planners approach the task of process planning with knowledge chunks similar to IF-THEN rules. The following is a simple example in process plan- ning [Brdy87]: IF {hole to be made has a small tolerance value} THEN [1) Drill initial pilot hole on lathe, 2) Ream hole to final radius and tolerance} This is an oversimplification of how to drill holes with small tolerance values. Perhaps boring would be more cost and time efficient than reaming. Human process planners often explain their decisions in terms of more complex rules than this example, yet their rules follow the same basic format: IF [SET OF PRECONDITIONS HOLD} THEN {PERFORM A SET OF TASKS AND OPERATIONS} 29 This type of representation can handle many problems and is the most frequently used building block in commercial expert systems today. Rules should only be used where feasible. Computational problems may result in deciding which rule to apply (fire) if many rules can apply to (are triggered by) a particular state of problem solving. If the task can be described by IF-THEN rules and the number of rules that must be active at one time is small, then the use of rules may be a good choice. Such production rules represent compiled knowledge from the human expert and can allow for eflicient decision-making. 2.3.3. Frames The natural way to approach a problem is not always through IF-THEN rules. Sometimes a hierarchical approach is a more appropriate way to view the problem. Hierarchical planners distinguish between important considerations and details [Ste81a, Ste8lb]. Using a hierarchical approach can help reduce the exponential search problem associated with rule-based methods by refining down from high-level abstract states toward the details that bring about the desired abstract states. Frames are a way to organize knowledge hierarchically. Frames are templates with slots associated with different characteristics of an Object, action, etc. For example, a hole drilling frame could be set up as [Nau86]: (def twist_drill (operation make_hole) (cost 1) (min_diameter 0.1) (max_diameter 2.0) ) This could signify that a twist drill can be used to perform a make-hole operation, it costs 1 unit to perform, and can be used for holes ranging between 0.1 and 2.0 units in diame- ter. The operation value describes that twist drill is a sub-class of the make-hole class of operations, which itself may be represented by a superfrarnc higher up in the hierarchy. Mst drill would inherit default values and Other information from the make_hole 30 definition. This frame, as well as others with an operation type of make_hole, would be considered whenever a hole was needed in the finished product. In Patrick Winston’s AI book, frames are used to aid in dealing with natural language understanding of news stories [Wins84]. They simplify the search task consid- erably. "Frames are important because they inform us about common situations, those involving common sense knowledge, by telling us what assumptions to make, what things to look for and what ways to look." [Wins84]. Frames organized into a hierarchy allow exploitation of relationships not explicitly available in single production rule based sys- tems. The usefulness of frames in the process planning domain has been shown [NaCh85, Nau86, Tsat87]. For example, a process planner for metal parts using removal operations written in Prolog is discussed in [NaCh85]. Unlike other frarne-based reasoning systems where the problem-solving knowledge that manipulates the frames is made up of rules, frames are used in [NaCh85] to encode the problem-solving knowledge as well. This allows for the problem to be solved in a hierarchical manner with only the relevant frames being considered for application. 23.4. AND/OR Graphs AND/OR graphs are often used in A1 applications as goal trees and to store alter- nate plans. The goal is at the root of the graph and may have many levels of nodes below it. The levels alternate between AND levels and OR levels with all the nodes on one level being connected to the previous level with the same AND- (or OR- ) type edge. This representation can be helpful in solving the process planning problem. AND/OR graphs can represent how goals and sub-goals fit together. This simplifies the processing of user queries on how goals were achieved and why they were attempted [Wins84, Nils80]. 31 This representation could also be helpful in storing the final process plan where AND/OR graphs can be used to compactly represent all possible assembly sequences. Traditionally, a fixed sequence assembly ordering or precedence graph was used to hold the assembly sequencing information. A fixed sequence assembly order explicitly specifies a single assembly sequence, and a precedence graph represents several assem- bly orders implicitly by representing the constraints between pairs of Objects that are to be assembled or between tasks to be performed. The AND/OR graph representation allows for efficient planning algorithms that can use alternative assembly sequences according to dynamic conditions in the factory environment. The scheduling efiiciency of AND/OR graphs was found to be better than fixed sequence and precedence graph representations [Home86]. We now illustrate how AND/OR trees can be used to represent assembly sequences. Figure 2-6 shows the 35 possible assembly states of a toy car, which consists of four wheels, two axles, and a body. The car can be assembled in 184 difierent sequences if all seven parts are considered as unique. Although 35 states are shown, 22 states are dupli- cate states, and only 13 are distinct states, assuming symmetries are equivalent. For example, the second row in Figure 2-6 shows four difi°erent assemblies. However, since all tires are similar components, all four states are actually "permutations" of one state consisting of the car body, one axle with two wheels and one axle with one wheel. Only one unique assembly state is needed to represent these four states. Figure 2-7 shows the 13 unique assembly states and the AND/OR graph connec- tions that represent all the 14 unique ways to assemble the toy car. Arcs connect a state to its subassemblies that must be assembled to create that state. Two subassemblies are always assembled at once; this is denoted by two arcs sharing a common origin to desig- nate them as AND operations that must be done to create the previous state. Whenever a choice of assembly sequences exists, different sets of arcs for each assembly sequence are used. For example, state S 6 in Figure 2-7 can be assembled two different ways. 32 #OprS 11 M I E Figure 2-6: All 35 Possible Car Assembly States Assembly operation al or a2 can be performed to create state S 6. Assembly operation a2 creates S 6 by inserting the axle and wheel subassembly (state S 5) into the car body. State S5 must be previously created by assembling an axle and wheel together, both of which are basic assembly units. If this AND/OR representation is kept on-line in a manufacturing environment, it would be possible to assemble the toy car as quickly as possible dependent on the order $12 /. . E ”E / WE“ //\'\/ ME = Q ”VB. 3 S4 A Sl $2 ll Toy Car AND/0R Assembly Graph 34 in which car parts or tools become available. Assuming a car body and axle were the first parts to become available, the system could start at the leaf nodes of the AND/OR tree representing the axle and car body to see if they shared a common parent state. In this example state S 4 could be created from the car body and axle. If the next object available were another axle, the system could see if state S 4 and an axle have common parents. They both have state S7 as common parents, so the second axle could then be assembled with state S 4 to create state S 7. Continuing in this fashion allows parts to be assembled as they become available at a station instead of relying on a fixed assembly sequence. If no assembly sequence is possible, then no intersection of direct parents can be found, and the system must wait for another part. A set of all the possible process plans stored this way has two main advantages over the sequential and precedence storage methods. 1) All process (assembly) plans are represented in one graph; a search for the least costly process plan can be done by searching this graph given a set of factory machines, raw materials, and machining costs. As new materials, manufacturing methods, or tools become available, the Optimal process plan sequence can be found by using an AO“ or similar search technique [Home86]. 2) On the factory floor, scheduling and raw material delays Often hold up operations. By having many or all process plans available, a computer could check to see if production could be continued using a different sequence with the available parts until the needed parts arrive. Keeping the process plan representation in an AND/OR graph format can also benefit flexible manufacturing workstation assembly. If parts arrive at varying times or are present in a bin with difl‘erent parts overlapping each other, the system can select a valid assembly sequence (if one exists) for the parts that are most easily accessible. This can cut down on the quantity of parts that must be moved and stored, thus speeding up the assembly sequence. 35 2.3.5. Decision flees and Precedence Graphs In assembly planning the tasks to be performed consist of the steps necessary to join subassemblies together in creating the final product. Determining which tasks must be done before other tasks can be very time consuming. Given l connections (liaisons) to be made in an assembly, Bourjault outlined a method requiring at least 202 + I) yes or no questions to be answered by the user in order to determine the precedence constraints among assembly operations [Bour84]. Following this line of work, De Fazio and Whit- ney propom a method where exactly 2*! questions are asked of the user. These ques- tions require one of two responses: a) nothing restricts the assembly step, or b) a pre- cedence relation between logical combinations or liaisons explicitly defining the pre- cedence constraints for the given liaison [DeFa87]. Given N tasks to be performed with M constraints, it is possible to represent all valid orderings in a decision tree. Decision trees are referred to as Bourjault trees in the assembly plan representation survey by Wolter [Wolt90]. The vertices in a decision tree represent states, and the edges between vertices represent state transitions through the application of a particular task. For example: given a set of tasks (A, B, C, D, E} and the set of precedence constraints {A0 vertices and M20 directed edges. Each task i (1 S i S N) is represented as a vertex V, in the pre- cedence graph. A precedent constraint between two tasks (say, i < j (i must precede j)), is represented as a directed are from V, to V]. in G [Horo76]. Figure 2-8 b shows the pre- cedence graph for 5 tasks {A, B, C, D, E} and the precedence constraints {A signs reversed. 5) XSY : Requires the evaluation of two possibilities, one with X V1) is an N-fold graph. V0 has as parents the parents of V, and V1 has children that were the children of V,. 3) the result of removing a single vertex in an N—fold graph and replacing it with a parallel pattern (as defined in the next section) is an N—fold graph. 4) the result of removing a single vertex in an N-fold graph and replacing it with an N pattern (as defined in the next section) is an N-fold graph. 5) nothing else is an N—fold graph. A few other definitions are in order: parent vertex - A vertex i will have a vertex j as its parent if their is a directed edge from vertex j to vertex i. Equivalently, the task(s) at vertex j must be performed before the task(s) at vertex i can be performed child vertex - A vertex i has a vertex j as its child if a directed edge exists from vertex i to j. The task(s) at vertex i must be performed before the task(s) at vertex j. ancestors - The ancestors of a vertex i are the parents of vertex i and the parents of those parents, etc. For every ancestor vertex j ofi there exists a directed path from j to i. predecessor vertex - Another term for an ancestor of a vertex. descendants - Analogous to ancestors, a descendant j of vertex i is a child of i or a child of a child etc. For every descendant vertex j ofi there exists a directed path from i to j. successor vertex - Another term for a descendant of a vertex. vertices in series - Two or more vertices are said to be in series if they form a linear list of vertices as defined in the previous section. 90 vertices in parallel - Two or more vertices are considered to be in parallel if they have the same parents and same children vertices. 4.4. Subgraph Replacement The Oracle algorithm can handle all N-fold graphs exactly by using all three of the subgraph replacements (Figure 4-2): series, parallel, and the N pattern [Mil90b]. The Oracle algorithm replaces occurrences of the three subgraph patterns of vertices as defined in the following subsections with a single composite vertex. Replaced vertices may themselves be composite vertices. By repeatedly reducing a graph using the three subgraph replacement patterns, the Oracle algorithm can reduce all N-fold graphs into a single vertex representing all the original vertices in the graph with the exact number of possible task orderings for all the tasks”. During each reduction step the Oracle keeps track of how many tasks have been collapsed into a composite vertex and how many task orderings are possible among all the tasks represented by a single composite vertex. For graphs that cannot be reduced to a single vertex representing all the tasks, an upper and lower bound on the number of possible orderings is computed The serial and parallel patterns are the smallest possible subgraphs of two or more vertices that can be used for subgraph reduction. The series and parallel patterns can be used to generate the class of series parallel graphs that appears in the mathematics litera- ture. No unique acyclic subgraphs with non-redundant edges can be made using only three vertices. For example, a linear chain of three vertices Vl —) V2 —) V3 is not a unique subgraph since it can be made by combining two serial patterns. The N pattern was chosen as a replacement pattern because it was a small unique subgraph and it con- tains a cross link from vertex V1 —> V 4 (as in Figure 4-2). This cross link joins two series ‘1 The tasks could be assembly, manufacturing, or from any generic task planning problem. e.g. the Oracle algorithm could be used in any problem with tasks and precedence relations - the algorithm is not restricted to the fields of Computer Aided Process Planning or Artificial Intelligence. 91 patterns that are in parallel with each other. An earlier version of our algorithm con- tained an X pattern which is an N pattern with an additional edge from V2 to V3. How— ever, this X pattern is not unique because it can be reduced using two parallel patterns on (V1,V2) and (V3,V4) before reducing the resulting composite vertices using the serial pat- tern. /60 \ I \ I ~ ” ’l : \ I : ‘\ ~A-A' l ‘ ’ \ l5 v 8 V l, a a) Series ,” i x b) Parallel ; \I, ‘sl c) N pattern Figure 4-2: The Three Oracle Replacement Patterns When the precedence graph is created, each vertex represents a single task. To keep track of how many tasks are represented by a single vertex or composite vertex, each vertex is assigned two values: 1) N[V‘.] for the number of tasks represented by the vertex, and 2) O[Vi] for the number of possible orderings among the tasks represented by this vertex. At the start of the algorithm every vertex i represents a single vertex, so N[V‘.] = 1 with a single possible ordering of the one task, and O[Vi] = 1. The graph is reduced by replacing occurrences of the three subgraphs with composite vertices that have values of N[Vc] equal to the number of vertices that have been reduced into the composite vertex, and O[Vc] being the number of possible orderings of the tasks represented by the composite vertex. 92 4.4.1. Series Replacement As shown in Figure 4-2 a, two vertices V1 and V2 are in series, indicating vertex V2 must follow vertex V1. Vertex Vl must have a single outgoing arc (constraint) to V2. Vertex Vl may have many incoming arcs but only one outgoing arc. Similarly, vertex V2 can only have one incoming are (from V1), but may have many outgoing arcs. We can replace vertices V1 and V2 in a precedence graph with a composite vertex V c that has the incoming arcs of V1 and outgoing arcs of V2 and the following values for the number of constraints and possible task orderings: N[Vc] = N[Vl] + N[V2] O[Vc] = O[V1] * O[V2] Clearly, any order represented by V1 can precede any order represented by V2, so the combined number of orders is the product of the orders possible for V1 and V2. 4.4.2. Parallel Replacement Figure 4-2 b shows two vertices V1 and V2 in parallel”. Both vertices must have the same predecessors and successors. The predecessor and successor vertices may have any number of incoming and outgoing arcs unrelated to V1 and V2. The tasks represented by vertex V1 and vertex V2 can be performed in any combination of orders as long as the task ordering within V1 and V2 is not disturbed We create a composite vertex Vc with the same predecessor and successor vertices as V1 (V2) and the number of tasks and task orderings is calculated as: N[Vc] = N[V1] + N[V2] Och] = B(NIV1].N[V2]) * 0W1] * 0W2] Note: B(x,y) denotes the binomial of x,y = (x+y)! / (x! * yl). ‘2 Although only a single common parent and single common child vertex are shown for the parallel and N replacement patterns, multiple parents and/or children are permitted. 93 The O[V1] and O[V2] terms account for the number of possible orderings within each set of vertices V1 and V2. Given two fixed orderings for the vertices represented by V1 and V2, the binomial term returns the number of possible combinations of the two sets of ordered vertices [Well72]. The parallel subgraph pattern uses a number of orders for- mula similar to the W2 equation that Homem de Mello uses in evaluating the number of task orderings in an AND/OR assembly tree [Home89]l3. 4.4.3. N Pattern The subgraph of vertices V1, V2, V3, and V 4 shown in Figure 4-2 c forms an N pat— tern in the precedence graph. Note that similar to the parallel case, V1 and V2 must have the same predecessors, and V3 and V4 must have the same successors. The predecessor and successor vertices may have any number of unrelated incoming and outgoing arcs. Similar to the parallel case, the N pattern can be replaced with a composite vertex V6 with: N[Vc] = NlVl] + N[V2] + N[V3] + N[V4] 1) IfN[V1] is minimum owe] = (B(NIV4]+N[V2].N[V31+N[V1]) - ELEV" B(NIV4l-1.N[V3l+i) * B(NlVll-iNIVzl» * O[V1] * O[V2] * O[V3] * O[V4] 2) IfN[V?] is minimum owe] = (2,132 B(NlVll-INVzl-i) * B(NIV3].N[V4l+i)) * om] * 0W2] * 0W3] * om] 3) IfN[V?] is minimum owe] = (21‘: 3 B(NlV4l-1.N[V3l-i) * B(NIV21N[V1]+i)) * OlVll * 0W2] * 0W3] * 0W4] 4) 1mm 41 is minimum owe] = (B(NIV1]+N[V3].N[V2]+N[V4]) - 2.3:?" B(NlVll-l.N[V21+i) * B(NIV4l-i.N[V3D) * 0W1] * otvzt *- otv3] * O[V4] The four formulas for O[Vc] are useful in reducing the time complexity of the algo- rithm by a factor of IVI as discussed in Chapter 5. All of the formulas are equivalent and ‘3 OrwemENDvertexhasbeenaddedmdreAND/ORueedreresuldngprecedemegraph can be handled exactly by the series and parallel reduction patterns. 94 I K GD (9 <9 i l V1 V2 C?\C§) V” =J(?\ (*1 ® (9 ‘O V i i V3 'i V4 ©\ /® ®\ 1'09 0 end O end a) N shaped graph b) v1_4 and the dividing vertex b A total of 53 Possible Orders Figure 4-3: Formula 2 for an N shaped graph are based on the choice of a dividing vertex for the derivation of the number of order- ings. Formulas 2 and 3 are similar in that they both directly calculate the number of allowed permutations of the vertices. For example, Figures 4-3 and 4-4 show how for- mula 2 is applied using the successor vertex (V14) in V1 to divide the vertices into two sets of vertices. Figure 4-4 shows all three possible divisions of the vertices using VM to create two sets of vertices which can each be executed as two parallel lists of vertices. One set of vertices must occur before V1 4 and the other set of vertices must occur after Vld . With the vertices divided into two sets the number of possible orderings in each set is calculated using the parallel binomial formula. The two resulting values are multi- plied together since vertex V14 separates these two groups of vertices serially. The N formula sums the number of orders for each of the three subgraphs to obtain 53 possible orders for the graph in 4-3 a. This result requires a total of IV2I+1 calculations for the . V summation 2:2, 2]. In a similar fashion to formula 2, formulas 1 and 4 calculate the number of orders possible for two serial sets of vertices (V1 and V3) and (V2 and V4) as if they were in 95 201”“ see ...» 5? ®\ /@ ,9; [O m“ / @e©¢@e0\ e ease—ed) ere—e @«e—ee \ / \ / 0 end 0 end 0 end a) 1st Possibility b) 2nd Possible Division 0) 3rd Possible Division 18 total orders 20 total orders 15 total orders Figure 4-4: The three possible divisions for Figure 4-3 h parallel (without the V1 —-> V 4 constraint) before subtracting from this value the number of orderings not allowed due to the constraint Vl —) V 4. 4.5. Determining the Number of Task Orderings The Oracle algorithm works from the set of tasks to be performed and the pre- cedence constraints among these tasks. The set of tasks and precedence constraints is represented as a set of precedence graphs. Each precedence graph is preprocessed as described in Section 4.5.2 and then evaluated using the Oracle subgraph replacement algorithm. The number of possible task orderings for a general set of precedence con- straints is the sum of the orders for each precedence graph. Upper and lower bounds are returned for non-N—fold graphs. An outline of the method is shown in Section 4.5.3. 4.5.1. Assumptions 1) The set of tasks to be performed and the precedence constraints among the tasks are known. 2) If operations must be performed in parallel they are assigned to a single task (vertex) so they are counted as a single parallel task. To allow for parallel task execution the 96 S relationship could be used between tasks to indicate that the tasks may be per- formed at the same time or that one task may precede the other. 3) A small number of complex precedence relationships AND, OR, and S are present. (A large number of such complex precedence relationships can create a very large number of precedence graphs to be evaluated.) 4.5.2. Preprocessing a Precedence Graph The Oracle algorithm assumes that redundant constraints have been removed from each precedence graph. Given the set of tasks {A, B, C] and precedence constraints {A V. produces (001,) * ow,» * 00/3) or 00/1) * (00/2) * 00',» depending on the order in which the serial vertices are reduced Obviously, the resulting values are the same due to the commutative property of multiplication. 116 5.2. Serial and Parallel Reduction Stage The first graph reduction stage replaces all the serial vertices by a single vertex and merges all parallel vertex patterns into a single composite vertex (which may then enable other merges). The algorithm uses a READY[] list to keep track of which vertices can be processed next. Each original vertex is processed only once. However, after a parallel combination occurs the resulting composite vertex is also visited The order in which the vertices are visited is the same as that of a topo-sort algorithm. This algorithm assumes that all redundant constraints have been removed as described in Section 5.1.3. v t r gO‘? “O l \ ’1’ I \\\ I” \\\ I | \‘ : V’ v i Nc= N1+N2 V t " Nc= N1+N2r v t a) Series Oc= 01 * 02 b) Parallel CC = B(N1,N2) all 01 s. 02 Figure 5-2: Series and Parallel Vertices This stage reduces all series and parallel graph constructs. Figure 5-2 shows two vertices in series and two vertices in parallel. 1) Initialization a) Create an array U_P[] to represent how many Unevaluated Parents exist for each vertex. This is initialized to be the number of parents of each vertex (NPARENTS[i]). b) Create an array called MEETI] which is initially an empty list (NIL) for all i ver- tices. The MEET[] array of lists is used to keep track of vertices that may be in parallel. MEET[i] lists may be non-nil during this stage IF and only IF more than a single parent exists for vertex i (0S i -1). 117 c) Start checking for serial/parallel patterns at the START vertex. Set READY[] = START 2) Do steps a-c while the READY[] list is NON-EMPTY a) Take a vertex off of the READY[] list and call it NEXT-V. Set READY[] to be READY[] without the NEXT-V vertex. b) If NEXT-V has a single parent (NPARENTS[NEXT—V] = l) and that parent has a single child (NCHILDREN[parent of NEXT-V] = 1) then NEXT —V and PARENT-NEXT-V are in series and can be reduced into a single vertex using SERIES_REDUCE(PARENT-NEXT—V,NEXT—V); otherwise continue on with step c). c) ForeachCHILDinCHILDREN[NEXT-V]doi-ii i) Decrement the value of U_P[CHILD] by one. ii) If NPARENTS[CHILD] > 1 then a parallel merging MAY be possible Call CHECK_PARALLEL(NEXT-V,CHILD) Else if U_P[CHILD] = 0 then add CHILD to the READY[] list. Series reduction requires O(IVI + IEI) ~ O(IEI) time since each vertex and edge is visited/looked at a fixed number of times and a single series reduction step takes O(l) time. The CHECK_PARALLELO algorithm requires ouv I2 * IEI) time in the worst- case since it may be necessary to perform O(lVl * IEI) comparisons with a worst-case time complexity of O(IVI) time per comparison. On average, the number of compares necessary will be closer to O(IEI) since most vertices will have a small (nearly constant) number of other incoming edges to be checked Additionally, the O(IVI) time per com- parison will be closer to O(l) as discussed in the Section 5.2.3 leaving a typical time complexity closer to O(IEI). The space complexity is O(IVI * IEI) since each vertex has a merge list. The whole graph will have at most B such merge lists of O(IVI) size each. 5.2.1. Merging of Two Vertices in Series Algorithm: SERIES_REDUCE(PARENT-NEXT-V,NEXT—V) This algorithm performs a series reduction on the vertices PARENT-NEXT-V and NEXT-V vertices in the precedence graph representation. Figure 5-2 a shows two ver- tices in series. Steps 1 and 2 calculate the number of tasks represented by the resulting combined vertex and the number of possible task orderings allowed among the tasks at 118 the combined vertex. The NEXT-V vertex is efiectively combined with the PARENT- NEXT-V vertex to produce a composite vertex which replaces PARENT-NEXT-V in the precedence graph. The CI-IILDRENfl and PARENTSD pointers are modified to ’remove’ NEXT-V from the precedence graph after the serial merge has been performed 1) N[PARENT-NEXT-V]=N[PARENT-NEXT—V] + N[NEXT-V] 2) O[PARENT—NEXT-V]=O[PARENT-NEXT-V] * O[NEXT—V] Steps 3 and 4 efl’ectively delete the merged NEXT-V vertex from the pre— cedence graph. The vertex PARENT-NEXT-V will then represent both of these combined vertices. 3) CHILDREN[PARENT-NEXT—V] = CHILDREN [NEXT -V] NCHILDREN[PARENT-NEXT—V] = NCHILDREN [NEXT -V] 4) For each CHILD in the new CHILDREN [PARENT-NEXT—V] list DO Substitute PARENT-NEXT-V in for NEXT-V in the PARENTS[CHILD] list. The series reduction code requires a constant amount of time to replace two serial vertices by a single vertex. Its time complexity is O( 1) and no additional space is required since the composite vertex is stored in the location where the NEXT-V vertex was stored 5.2.2. Checking for Two Vertices in Parallel Algorithm: CI-IECK_PARALLEL(NEXT—V,CHILD) This algorithm checks to see if the NEXT-V vertex can be merged in parallel with one of the other parents of the CHILD vertex. If no merge of NEXT-V with another parent of CHILD is possible, this routine adds a sublist of merging information to the list MEET[CHILD]. Parallel merges are performed when detected and then the combined vertex is placed on the READY[] list for further evaluation. When this algorithm is invoked the NEXT-V vertex is one of several vertices in the graph that have the CHILD vertex as one of their children. Thus, the NEXT-V vertex might be merged via a parallel reduction with one of the other parents of CHILD. The vertex NEXT-V can be merged with one of the other parents of CHILD (say OTHER- 119 PARENT) IF and ONLY IF NEXT-V and OTHER-PARENT have the same parent and children vertices. In order to detect possible parallel merges this algorithm uses the information stored in the MEET[] list at the CHILD vertex. The MEET[CHILD] list may be NIL indicating that the other parents of CHILD have not yet been evaluated, or MEET[CHILD] may contain a sublist of information for each parent of the CHILD ver- tex that has been evaluated, but not merged with another parent of CHILD. The sublist information of each parent that has been visited will consist of three parts. For example the sublist for the NEXT-V vertex is ((PARENTS[NEXT-V]) (CHILDREN[NEXT-VD (NEXT-V». In order for two vertices to be in ’parallel’ with each other they must have identical PARENTS[] and CHILDRENU lists. Note: The PARENTS[] and CHILDREND lists could be sorted during the REDUNDANT EDGE REMOVAL STEP (by increasing index order) to make this comparison relatively efficient, or bit maps could be used to simplify this equality test. Note: At this point all vertices in series directly above and below the NEXT-V vertex will have been reduced 1) Set PAlol‘AILEL-FOUND = NIL. No parallel vertices have been found that can be merg 2) For each sublist in MEET[CHILD] check to see if the PARENTS[NEXT-V] and CHILDREN [NEXT-V] are exactly the same as the PARENTS[] and CHILDREN[J lists in the other MEET[CHILD] sublists. If a match is found, then set PARALLEL-FOUND equal to that sublists 3rd element (i.e. the index of the vertex that NEXT-V will be merged with) and go on to Step 3. If all the sublists in MEET[CHILD] have been checked and no match is found then continue with Step 4 3) Call the parallel merge algorithm to merge the NEXT -V and PARALLEL-FOUND vertex. PARALLEL_MERGE(NEXT—V,PARALLEL—FOUND). Place NEXT-V back on the READY[] list since it is now a composite vertex (and some serial or ' more parallel merges may now be possible). Increment U_P[CHILD] by one since NEXT-V was placed back on the ready list for reconsideration. 4) Add a sublist to MEET[CHILD] containing (PARENTS[NEXT—V] CHILDREN[NEXT-V] NEXT-V) to be used in future parallel merge checking steps. IF NO MERGE WAS possible and U_P[CHILD]=0 then add CHILD to READY[]. Each call to CHECK_PARALLELO has a time complexity based on the local graph topology and how many processed, yet unmerged sibling vertices of NEXT-V have saved their merging sublists in the MEET[CHILD] list. Over all possible O(IEI) calls to 120 CHECK_PARALLEL the total number of possible checks is O(IVI*IEI). If bit maps are used to test for similar PARENTS[] and CHILDREN [] values for NEXT-V and its siblings then the amount of time spent on each check is O(l) for IVI S machine word size. However, in general the time is O(IVI) giving a worst-case complexity of O( IV I2 * IEI) as illustrated in Figure 5-3. Note that most cases will require closer to O(IEI) calls to CHECK_PARALLEL and only a small (nearly constant) number of other siblings will need to be checked In addition, the time for each comparison can usually be made in O(l) time using the NCHILDREND and NPARENTSD values to screen for obviously non-parallel vertex pairs. 9 G) G) o, 6 ® CD \ l/ “...... \l / . 3+2 = 5 Compares = END END 60 + 6 66 Compares a) 6Task Case b) 12 Task Example Figure 5-3: Tough cases for the CHECK_PARALLEL algorithm 121 5.2.3. Merging of Two Parallel Vertices Algorithm: PARALLEL_MERGE(V1,V2) The parallel merge algorithm PARALLEL_MERGE(V1,V2) merges the tasks represented by vertex V1 and V2 and combines them into a single composite vertex V1 (i.e. overwrites the old V1 vertex information to save space). Figure 5-2 b shows two vertices in parallel. The number of tasks and the number of task orderings represented by V1 and V2 is combined and the results stored in V1. Vertex V2 is efi‘ectively removed from the precedence graph by deleting references to V2 from its parents and children vertices. l) N[Vl] = N[Vl] + N[V2] 2) O[Vl] = B([N[V1],N[V2])] * O[Vl] * O[V2] Where B(x,y) is the binomial of x,y = (x+y)! / (x! * y!) Now remove references to the merged V2 vertex. 3) For each PARENT in PARENTS[VZ] Remove V2 from CHILDREN [PARENT] 4) For each CHILD in CHILDREN[V 2] Remove V2 from PARENT S[CHILD] The parallel merge code requires time proportional to the number of incoming and outgoing edges to replace two vertices in parallel by a single vertex. Its time complexity is O(IEI) for all parallel merges and no additional space is required since the composite vertex is stored in the location where the V2 vertex was stored 5.3. N Reduction Pass If the graph can be reduced using only series and parallel reductions as described in Section 5.2 then the graph will have been reduced into a single composite vertex with the correct number of orders O[] stored at the remaining vertex. If this is the case, we exit with the exact number of possible orderings known. Otherwise, we attempt to reduce the remaining vertices using the N pattern described in this section. After an N pattern is 122 applied it is possible that further series or parallel reductions may be possible. Figure 5-4 shows an N type pattern. Note that vertex V4 has exactly two parents; this fact is used in searching for N patterns in the graph. To reduce N patterns the follow- ing steps are performed 1) Set CHECK-N-LIST to be empty (NIL). 2) For every remaining vertex I in the graph If NPARENTS[I] > 1 and MEET[I] <> NIL then add I to CHECK-N-LIST At this point all the vertices with more than one uncombined parent will be on the CHECK-N—LIST. These CHECK-N-LIST vertices in the graph are candidate positions for N type patterns of vertices. Figure 5-4: An N shaped pattern of vertices 3) Set FOUND-ONE = TRUE 4) DO WHILE FOUND-ONE = TRUE a) FOUND-ONE = FALSE b) FOR each I in CHECK-N-LIST do i-ii i) N_TEST(I) to see if I corresponds to a ’V4’ vertex in an N pattern. If an N pattern is found - it is reduced by N_TEST() into a single vertex. N_TEST() then performs a local check to see if any serial or parallel reductions are possible. All such local series and parallel reductions are performed before continuing. ii) If N_TEST(I) was true set FOUND-ONE = TRUE and REMOVE I from CHECK-N-LIST c) IF FOUND-ONE = TRUE then start over with a) OTHERWISE EXIT 123 This stage reduces all N patterns into single vertices and after each N-reduction it performs all possible parallel and serial reductions before continuing. It would be possi- ble to check for several other patterns besides the N pattern in a similar manner if desired Steps 1 and 2 of this N checking algorithm require O(IVI) time and space since each vertex is checked whether or not it is a possible candidate for the location of a V3 vertex in an N pattern. The CHECK-N-LIST will have O(IVI) entries, at most one for each ver- tex except the START vertex. Steps 3 and 4 will be re-executed on unmerged possible V4 vertices if an N pattern is reduced during a single pass since it is possible that nested N patterns may exist and an N pattern can only be detected and reduced IF all the N pat- terns contained inside of it have been reduced It is highly unlikely that many nested N patterns will occur in set of say 20 tasks since approximately 4 vertices/tasks are required for an N pattern. Step 4 may be executed O( I V l2) times if multiple passes through the set of CI-IECK-N-LIST data are needed. Note: This time complexity could be reduced to O(IVI) with some preprocessing to process the more deeply nested N patterns before try- ing to reduce the outer N patterns. However, reducing the complexity of this step will not reduce the overall complexity of the Oracle algorithm. Each one of the vertices on the CHECK-N-LIST are checked with the N_TESTO algorithm giving a worst-case com- plexity of O(V3) since each N_TESTO algorithm requires at most O(IVI) time to check for similar PARENTfl and CHILDREN [] vertices. 5.3.1. Checking for N Patterns in the Graph Algorithm: N_TEST(CHECK-VERTEX) This algorithm performs a check to see if CHECK-VERTEX is a vertex correspond- ing to vertex V4 in Figure 5-4. If an N type pattern is found it calls REDUCE_N_PATI'ERN(V1,V2,V3,V4) to reduce the N pattern into a single vertex. 124 REDUCE_N_PA’ITERN() also checks the graph locally around the reduced composite vertex to see if any parallel or series reductions can be performed. The variables V1 through V4 refer to labeled vertices in Figure 5-4. 1) V4 = CHECK-VERTEX(assume this is true) 2) If NPARENTS[V4] <> 2 then EXIT (no N type found). 3) At this point two parents of V4 exist. One parent MUST have two children, the other parent MUST have one child (V4). IF NOT then EXIT (not an N-type). 4) Vl = the parent vertex with two children. V2 = the parent vertex with a single child (V4). If PARENTS[Vl] <> PARENTS[VZ] then EXIT (not an N-pattern). 5) V1 has two children, one being V4. Call the other child V3. If NPARENTS[V3] <> 1 then EXIT (no N pattern found). If CHILDREN [V 3] 0 CHILDREN [V4] then EXIT (not an N pattern). 6) The vertices V1, V2, V3, and V4 make up an N-pattern so now we call the REDUCE_N_PATTERN algorithm with REDUCE_N_PA’ITERN(V1,V2,V3,V4). The algorithm requires at most O(IVI) time for each call since the algorithm may have to compare the PARENTS[] and CHILDRENfl data to determine if an N pattern exists and to merge the N pattern into a single vertex. 5.3.2. Merging an N Pattern of Vertices REDUCE_N_PA'ITERN(V 1 ,V2,V3 ,V4) This algorithm reduces the N pattern specified by vertex indices V1, V2, V3, and V4 into a single vertex. It then calls the CLEAN_PARALLEL_SERIALO algorithm to recursively merge parallel and series patterns that can be merged after the N pattern was reduced to a single vertex. The four vertices V1, V2, V3 and V4 are reduced into a sin- gle composite vertex which is stored at vertex V4’s position in the graph. References to V1, V2, and V3 are removed from the precedence graph so that the precedence graph reflects the merge operation. 1) N[V4] = N[Vl] + N[V2] + N [V3] + N[V4] 2) In order to keep the worst-case calculation complexity from becoming O(N 2) we use one of the four order formulas given in Section 4.4.3 to keep the complexity at O(IVI) for this calculation step (over all N type reductions -- not just a single 125 application). 3) Now we change the precedence graph so that references to V1, V2 and V3 are removed while V4 takes their place. a) PARENTS[V4] = PARENTS[VI] b) For each INDEX in PARENTS[V4] Remove V1 and V2 from CHILDREN[INDEX] Add V4 to CHILDREN [INDEX] c) For each INDEX in CHILDREN[V4] Remove V3 from PARENTS[INDEX] 4) Call CLEAN_PARALLEL_SERIAL(V 4) to clean up any parallel and series pat- terns that now may be able to be reduced in the local vicinity of the V4 vertex. Four Nested N Patterns Figure 5-5: 0( I V I2) tests are not required using the test in step 2 This algorithm requires at most O(IVI) time to merge all N patterns of vertices. The O(IVI) complexity is due to the O[] formulas used in in step 2 which iterates from i=0 to min(lV1l, |V2|, lV3l, IV4I). By iterating over the smallest set of vertices the overall com- plexity of this step is reduced to O(IVI) instead of 0( | V l2) for all N-reductions in the graph which could occur in Figure 5-5 if only a single formula were used. 126 5.3.3. Checking for Further Parallel/Series Merges Algorithm: CLEAN_PARALLEL_SERIAL(VERTEX) This algorithm recursively reduces parallel or series patterns that can now be reduced as a result of an N pattern reduction being performed 1) REDUCTION-FOUND = TRUE 2) While REDUCTION-FOUND = TRUE do a) REDUCTION-FOUND = FALSE b) CHECK-PARALLEI..(VERTEX) IF any parallel reductions were performed set REDUCTION-FOUND = TRUE c) IF VERTEX has a single parent (NPARENTS[VERTEX] = 1) AND the parent of that vertex has a single child (NCHILDREN [parent of VERTEX] = 1) then VER- TEX and PARENT-VERTEX are in series and can be reduced into a single vertex using SERIES_REDUCE(PARENT—VERTEX,VERTEX) otherwise GOTO step a). Set: REDUCTION-FOUND = TRUE. VERTEX = PARENT-VERTEX This algorithm requires O(IVI) time for the while loop in step 2. This loop is exe- cuted at most O(lVl) times since it loops through only if a successful merge for a series or parallel vertex combination occurred Each series of parallel reduction reduces the number of vertices in the graph by one each time through the loop so at most O(IVI) passes may occur. Each pass may require O(V) comparisons of parent/children vertices giving rise to O( l V I2) time complexity. No additional space is required. 5.4. Upper and Lower Bound Estimates If the graph has been reduced into a single composite vertex via the application of the previous stages we can exit with the exact number of possible orders being the O[] value of the remaining vertex. However, if this is not the case, then a LOWER and UPPER bound on the number of possible task orderings is calculated as described in this section. These calculations are performed by two separate simplifying algorithms, one which always produces a lower bound on the number of possible task orderings, and the other which always produces an upper bound on the number of task orderings. 127 Both the Lower and Upper bound algorithms use the precedence graph that was created by the application of the N pattern reduction stage. For both the lower and upper bounds the graph is simplified using certain heuristics which are guaranteed to underesti- mate or overestimate the number of possible task orderings. Several difl’erent heuristics may be applied depending on the graph topology. If the resulting simplified graph can be reduced using the series, parallel, and N type patterns then the algorithm exits with this final value. However, if even the simplified graph cannot be reduced exactly, then the I algorithm makes a final pass reducing all the remaining vertices either serially for a lower bound or using the parallel reduction pattern to obtain an upper bound on the number of possible task orderings. 5.4.1. Lower Bound In order to find a lower bound on the number of task orders the LOWER_BOUND() algorithm simplifies the precedence graph using heuristics that can only produce a lower bound on the number of orders. These heuristics were developed by the author for appli- cation to a precedence graph in the hopes that the resulting simplified graph can be evaluated exactly using the series, parallel and N pattern reductions. Even after the simplifications have been applied it is possible that the remaining graph cannot be evaluated exactly. In this case we make the simplifying assumption that the remaining vertices are all in series. Combining the remaining vertices as if they were in series gives a lower bound on the number of possible task orderings and will reduce any remaining vertices into a single vertex containing a lower bound on the number of possible order- ings. The lower bound algorithm is applied to each parallel subgraph in the reduced pre- cedence graph that results after the series, parallel, and N patterns have been applied to the original precedence graph. If the START and END vertex are removed from the pre- cedence graph, then one or more connected sets of vertices remains. Each connected set 128 of vertices is a parallel subgraph. Estimates (or exact values) for the number of orders are found for each subgraph before the parallel subgraphs are recombined This allows for the bounding values of the parallel subgraphs to be revised by adding in compensa- tion values for each edge that is deleted or pair of vertices merged serially before the result of the parallel subgraph is combined with other parallel subgraphs. Simplifying heuristics are applied to the graph at vertices with an in degree greater than one to reduce the graph complexity at these key points. Recall that vertices with an in degree greater than one are positions where either parallel merging or N type patterns could be used. Algorithm: LOWER_BOUND(PARALLEL-SUBGRAPH-DATA) 1) Set CHECK-LIST to be empty (NIL). 2) For every remaining vertex I in the graph If NPARENTS[I] > 1 and MEET[I] <> NIL then add I to CHECK-LIST. O START /O START oi \@ <9 \@ w AN. ®\ /® \Oém 0 END b) Modified to an N shape a) Near N shape : 11 orders possible 3 orders possible Figure 5-6: Lower Bound Transformations At this point all the vertices with more than one uncombined parent will be on the CI-IECK-N-LIST. We then apply the following heuristics to each vertex on the CHECK-N-LIST. 129 3) For each I on CHECK-LIST: a) Reduce semi-series17 vertices such as vertex 4 in Figure 5-6. For J in PARENTS[I] If NPARENTS[J]=1 and NCHILDREN[J]=1 then Change graph so that PARENTS[I] = Add PARENTS[]] and PARENTS[I] lists - J index CHILDREN[J] = CHILDREN[I] N [J] = NU] + NH] 0U] = 0U] * O[I] If N_TEST(J) is TRUE then get the next I value and start over at Step a, oth- erwise proceed to step b. b) Add constraints to serialize parallel segments. For example, given the precedence graph shown in Figure 5- 7 a, edges are added to create the precedence graph shown in Figure 5-7 b. This allows the vertices (a, b, c} to be combined rn parallel before being combined serially with the parallel combination of vertices (d, e}. By adding constraints, two disjoint sets of vertices are created such that all the ver- tices in one set must precede all the vertices in the other set. It is important to check and maintain ancestor lists for the graph so that a cycle is not added to the graph during this stage. START O START END a) W shaped graph: 16 orders possible b) W shape with added constraints 14 orders possible Figure 5-7: Lower Bound Transformations 4) 117 Series, Parallel & N pattern merge algorithms on the resulting simplified graph. If the simplified graph can not be reduced to a single vertex then Merge all remaining vertices using the series formula. 5) After the parallel subgraph has been evaluated, the number of orders stored at the remaining vertex is increased by one for each pair of vertices that was merged in a semi-series fashion, and one for each edge that was added to the graph. Report the resulting lower bound stored at the only remaining vertex in the graph. ‘7 All vertices in series have already been merged so additional constraints keep a series merge from being possible. 130 Step 5 is an attempt to at least partially compensate for the number of simplifications made to the graph. For each edge that was merged in a semi-series fashion a parallel merge with at least one other vertex was overlooked, cutting the number of possible orders by at least one. A closer bound could be obtained by taking into account a lower bound on the number of vertices that could have been merged in parallel. This would require the ancestor lists to be kept up to date each time a simplification was made to the graph so that a comparison of the the ancestors at vertex I and .I could be performed Similarly, the bound on the number of orders can be increased by at least one for each edge deleted from the graph. Adding an edge to the graph is only performed if the vertices were uncomparable before the edge was added Thus adding the edge reduces the number of possible orders by at least one. Developing useful heuristics to apply is an area for future research. Since we can have at most IVI vertices that are difficult to merge, it would be possible to spend O(IVI*IEI) time investigating different heuristics for each vertex without changing the overall order of the Oracle algorithm. For example, another heuristic that could be used in step 3 is to look locally around each CHECK-LIST vertex to see if changing a con- straint would allow series, parallel, or N-type merges to further simplify the graph. Changingaconstraintl—rJ-iKtoL-il—rKorI—)J—-)L(whereLisadescendent of I and an ancestor of K) will produce a graph with a smaller number of possible order- ings by restricting vertex I even more. Perhaps such a constraint movement would alleviate the merging problem and produce a better bound After moving a constraint, it would be necessary to check for any redundant edges created by such a move. For exam- ple, in Figure 5-6 moving the constraint 1 —) 4 to 3 -> 4 and removing the redundant con- straint 3 -) END (which was created by moving the constraint 1 —> 4) from the graph would create a parallel pattern which could then be evaluated The heuristics given in this section always underestimate the number of possible task orderings. The heuristic in step 3 a merges two vertices as if they were in series, 131 when in fact additional parents of vertex I would have allowed for a larger number of possible orderings. Adding constraints as in step 3 b reduces the number of possible ord- erings by restricting some orders from occurring. After the heuristics are applied the series, parallel, and N type merging sequence is tried again. At this point any vertices remaining are reduced using the series formula which underestimates the number of pos- sible orderings to insure that the resulting estimate is a lower bound on the number of orders. The lower bound algorithm requires O(IEI) time to create the CHECK-list and reduce semi-series vertices (steps 1, 2, and 3a). Step 3b requires O(IVI*IEI) time to check the ancestor lists of each vertex being considered for additional constraints to make sure a cycle does not occur in the graph. Since step 4 calls up the series, parallel, and N- reduction algorithm it requires 0( IV I2 * IEI) time and 0( l V I7) space to perform. Thus, this lower bound estimation algorithm has an overall complexity of 0( IV I2 * IEI). 5.4.2. Upper Bound An upper bound on the number of possible task orderings can be obtained by apply- ing heuristics to the graph resulting from the first application of the serial, parallel, and N pattern merging algorithms. The UPPER_BOUND() algorithm outlined below is used to find an upper bound on the number of possible task orderings. As in the case of the lower bounds a few graph simplifications are applied to vertices with an in-degree of two or more. By selectively deleting constraints and/or combining vertices in parallel we are guaranteed to produce a graph representing more task orderings than the original graph. If the resulting simplified graph can be reduced into a single vertex by applying the serial, parallel, and N pattern reductions a second time, then we report the resulting upper bound Otherwise, all vertices remaining in the graph after the second reduction pass will be combined together using the parallel vertex formula to find an upper bound on the number of possible task orderings. 132 Algorithm: UPPER_BOUND(GRAPH-DATA) 1) Set CHECK-LIST to be empty (NIL). 2) For every remaining vertex I in the graph If NPARENTS[I] > 1 and MEET[I] <> NIL then add I to CHECK-LIST At this point all the vertices with more than one uncombined parent will be on the CHECK-LIST. We then apply the following heuristics to each vertex on the CHECK- LIST. 3) For each I on CHECK-LIST: This step selectively removes incoming constraints at vertex I in an attempt to make the graph an N-fold graph. It removes all but one of the incoming constraints that come from a parent vertex with more than one child. The algorithm tries to remove constraints that will increase the number of possible task orderings as little as possible. This is performed using a local graph topology check. @/:i:\@ ®/:\@ l l (ifs/d (in 6% a) Non-N-fold Graph b) Modified Graph 66 possible orders 74 possible orders Figure 5-8: Upper Bound Constraint Removal Heuristic For example, Figure 5-8 a shows a non-N-fold graph and Figure 5-8 b shows the heuristically altered graph that is an N-fold graph. All but one of the incoming edges to vertex e that are from vertices with two or more children are deleted Try the Series,Parallel & N pattern merge algorithms on this simplified graph. 4) If the simplified graph was not reduced to a single vertex then Merge the remaining vertices using the parallel formula 5) For each edge deleted from the graph decrement the resulting bound on the number of possible orders by 1. Since only non-redundant edges are in the precedence graph, removing an edge makes the two vertices incomparable and increases the number of possible orders by at least one. This compensation could be more accurate if both the ancestor and descendent information for individual vertices is maintained in the graph. Deleting an edge can possibly create a much larger number of incomparable edges, this fact could be noted and the resulting increase in the number of orders could be compensated for in the final bounding value. Report the resulting upper bound stored at the only remaining vertex in the graph. 133 Note: Instead of deleting constraints as in step 3, problem constraints could be selectively loosened (analogous to the lower bound suggestion for tightening the con- straints). ChangingaconstraintI—iJ-sKtoL—il->K(whereLisanancestorofI)or I —) J —) M (where M is a descendent of K) will produce a graph with a larger number of possible orderings by adding more valid positions for vertex J in the final graph. Any redundant edges created by moving constraints must be removed before evaluating the graph- 5.4.3. Lower and Upper Bound Estimates a) lower bound < actual < upper bound b) lower bound < actual < upper bound 10,584 < 12,096 < 14,364 49,392 < 64,512 < 90,972 Figure 5-9: Lower and Upper Bound Estimate Examples Figures 5-6 through 5-9 give examples of the lower and upper bound heuristics and their effects on the number of possible orderings. The bounding values provide ball park numbers for how many orders are possible for the given graphs. When estimating heuris- tics are used for small parts of the precedence graph being evaluated these heuristics pro- duce good bounds (for example Figure 5-9). Even when several estimates are necessary (such as in 5-9 b) the results can be good enough to decide roughly how many orders are possible. However, it is difficult to characterize the bounding values and to quantitatively predict their behavior on all graphs. This is due to the fact that the quality of the result- 134 ing bounding values depends highly on the local graph topology. Depending on the local graph topology a range from ball park to very tight bounding values can be obtained Ideally, extensions to the Oracle algorithm would allow even more graphs to be evaluated exactly, thereby reducing the nwd for using bounding values. (as discussed in Sections 4.7 and 5.6) However, future research into closer bounds and in rating the local performance of estimating heuristics would improve the closeness of the bounds. Using a branch and bound algorithm based on the goodness of the various local heuristics would allow the best of several heuristics to be applied for individual edges and to improve the final bounding values. 5.5. Overall Complexity of the Oracle Algorithm Theorem 5.3: The Oracle has the following properties: 1) The exact number of task orderings is returned for N-fold graphs. 2) An upper and lower bound on the number of task orderings is returned for non- N-fold graphs. 3) The Oracle terminates for all possible input graphs in O(V2 * E) time with an exact value or bounds. 4) The Oracle requires O(Vz) space. The time complexity of the Oracle algorithm can be obtained by analyzing each of its disjoint parts. The complexity of the following stages can be thought of as being exe- cuted in series, so the largest time complexity of the parts is the time complexity of the Oracle algorithm. 1) Graph Initialization: The most time consuming initialization algorithm is for redundant edge removal. O(IVI * IEI) time is required to remove redundant edges. 2) Series & Parallel Reduction: O( I V l2 * IEI) time to check for parallel vertices. 135 3) N—Pattern Reduction: ct l v I3) time. 4) Upper and Lower Bound Heuristics: The number of orders for non-N-fold graphs is bounded above and below by two bounding values. This process requires 0( IV I2 * IEI) time since after the relatively quick reduction heuristics are applied, the series, parallel, and N-pattern reduction algorithms are called again. Each of the four categories listed above have time complexities of O( l V I2 * IEI) (or smaller). The space complexity for the algorithm is O(IEI) to store the graph (remember that IEI > IVI). However, if bit-vectors are used for the comparison operations the space complexity becomes 0( IV l2). If bit vectors are used and the original number of vertices is small (IVI < word size of the computer) then the time complexity for the Oracle algo- rithm becomes O(IVI * IEI). The next section discusses the experimental results obtained from using the Oracle algorithm. 5.6. Performance of the Oracle Implementation The Oracle algorithm has been developed over the last 1.5 years. During the con- ceptual development of the Oracle algorithm several difi‘erent Common Lisp implemen- tations of the Oracle algorithm were coded on Sun 4 machines running Unix. Two significant versions of the Oracle algorithm were published [Mil90a, Mil90b]. The first version was capable of exactly determining the number of task orderings for the class of series parallel graphs (called simple fold graphs in [Mil90a]) and returning a single esti- mate for non-simple fold graphs. Appendix III compares the performance of the simple fold Oracle program with an enumerative approach for counting the number of different task orderings. The Oracle program significantly outperforms the enumerative approach. The Oracle prograrrr returns exact values or an estimate for the number of possible task orderings much more quickly than the enumerative program. In addition, the Oracle pro- gram has a low order polynomial run time, whereas the enumerative approach requires time proportional to the number of different task orderings (which can rise exponentially 136 with the number of tasks). The current version of the Oracle algorithm can handle N-fold graphs (which is a superset of simple fold graphs) and it also outperforms enumerative approaches as did the simple fold version of the Oracle algorithm discussed in Appendix III. The results presented in this section are for the current N-fold version of the Oracle algorithm which is implemented in Common Lisp. The performance of the N-fold Oracle program was obtained for a Sun 4/390 with 32MB of memory running under the Unix operating sys- tem. The Oracle algorithm is useful since it can determine the number of possible task orderings without enumeration for the class of N -fold graphs. Additionally, bounding values are provided for non-N-fold graphs. A class of labeled graphs with random edges was investigated to demonstrate the percentage of graphs that the Oracle algorithm could handle exactly without resorting to bounding values. As the number of vertices and number of edges are increased, the percentage of N-fold graphs falls ofi‘ quickly. How- ever, when either the number of vertices or number of edges is held fixed and the other varied, the percentage drops ofi' quickly before rising back up again. In addition, plots of the cpu time required by the Oracle algorithm to produce exact values for N-fold graphs or to determine upper and lower bounds for non-N-fold graphs indicate that the Oracle algorithm has an O(IV I2) run time. 5.6.1. Correctness of the Oracle Program Code Two major versions of the Oracle algorithm, an enumeration routine, and random graph testing routines have been implemented in Common Lisp and used on Sun 4 workstations running the Unix operating system. A total of 10,000 lines of Lisp code, comments and data make up these four different sets of software as described below. 1) Simple fold Oracle code: The first version of the Oracle algorithm consisted of 1200 lines of Lisp code and another 1300 lines of test data describing precedence graphs. The simple fold Oracle algorithm is described in [Mil89b], which also includes a 137 listing of the code and precedence graph data structures tested 2) Enumeration code: A modified topological sort routine was created to enumerate pre- cedence graphs in order to a) verify the correctness of the Oracle results, and b) compare the enumeration run times against the performance of the Oracle program as shown in Appendix III. It consists of 400 lines of code. 3) N-fold Oracle code: The latest version of the Oracle algorithm (described in this thesis) is implemented in 4000+ lines of Common Lisp code which includes display graphics and interactive editing code. The display graphics code uses Common Windows routines to interface to the X-11 windowing system running on Sun 4 workstations. The graphics code draws and modifies the precedence graphs as they are being entered by the user, or updates the graphics display as the precedence graph is evaluated by the N-fold or simple fold Oracle routines. The interactive editing code allows the user to enter, edit, and graphically modify a precedence graph using the three button mouse of the workstation. 4) Random graph testing code: The N-fold Oracle algorithm was tested on several mil- lion random graphs (as defined in the next section) to determine the experimental run time of the N-fold Oracle algorithm. The 2500 lines of Lisp code generate ran- dom acyclic graphs with a specified number of vertices and edges. After the ran- dom graphs are created they are evaluated by the N-fold Oracle routines. The inter- nal Lisp run time required for the N-fold routine to find a solution is monitored and averaged over all the random graphs tested Verifying that all 10,000 lines of code do indeed produce the correct output for all possible inputs (according to the definition of each algorithm) would be a very difibult and time consuming task. Since, it was impractical to formally verify the code, many steps were taken to verify partial results and the final output from the different routines. Some of these verification procedures were: 138 1) The Lisp code was created in a hierarchical, structured format to aid in developing and testing individual routines to help insure that the routines performed as expected. 2) Numerous hand checks for the output of the difl’erent routines were performed 3) For a large number of test cases, the enumeration routine results were compared to the results of both the simple and N-fold Oracle routines to make sure that all three of the programs agreed on the number of possible task orderings for simple fold pre- cedence graphs. 4) Several internal program consistency checks were performed in both of the Oracle routines. For example, since both of the Oracle routines perform graph reductions, a count of the total number of vertices removed (reduced) from the graph is kept. If the total number of removed vertices ever exceeded IVI-1 (IVI = No. of vertices) then a descriptive error message was printed and the program run terminated These internal consistency checks were very helpful in debugging the initial pro- gram implementations of the algorithms. 5) The lower and upper bounds produced by the N-fold Oracle routines were checked by hand In addition, when the N—fold Oracle produces a lower and upper bound the bounds are checked against each other to insure that LOWER_BOUND S UPPER_BOUND. During the testing of several million random graphs this test always succeeded Although this does not indicate that the lower and upper bounds did indeed bound the actual value of the number of possible task orderings for all the graphs tested, it indicates that the results are at least plausible. 6) Results were checked against published results from others. The hierarchical and structured program development, numerous independent verifications of the program output, and internal consistency checks all point toward a correct implementation of the algorithms. Although these steps do not guarantee or 139 prove the correctness of the algorithm implementations, they do contribute to the high confidence of the author that the program implementation for each of the algorithms is indeed correct. 5.6.2. Percentage of N-fold and Simple-fold Graphs Unfortunately, no sufliciently large body of manufacturing tasks and precedence relations is available for testing the Oracle algorithm. Given the lack of suflicient real manufacturing test data it would be desirable to test the Oracle algorithm on all possible precedence graphs with, say N vertices and M edges. However, up to M = N*(N—1) unique directed edges can be added to a graph with N vertices. Thus, a total of N choose M = N! / (M! * (N - M)!) different graphs with N vertices and M directed edges can be created For even fairly small values of N and M (say 10 or 15) the number of different graphs to be tested is prohibitively large. In order to determine how effective the Oracle algorithm is in returning exact values for precedence graphs, randomly generated precedence graphs were investigated Acy- clic random labeled graphs with N vertices and M directed edges were investigated Only acyclic random graphs are of interest”, since no task orderings are possible in graphs with cycles. Four different data sets of graphs were investigated with the values for N = lverticesl and M = ledgesl being varied or held constant as described below: a) No. Vertices = No. Edges, both varied from 5 to 80. b) No. Vertices = 2 * No. Edges, No. Edges varies from 3 to 40. c) No. Vertices varied from 5 to 80, No. Edges = 15. d) No. Edges varied from 5 to 80, No. Vertices = 15. A random labeled graph with N vertices and M edges is constructed starting with N labeled vertices and no edges. Randorrrly selected edges are added one by one such that ‘3 Atopological stxtcandetectprecedence graphswith cyclesin0(lVl+lEl)timeandspace. 140 no duplicate edges are added to the graph and no cycle is created by the addition of an edge. The Oracle algorithm is applied to a large number of randomly generated acyclic graphs as described in the next two sections. The percentage of randomly generated graphs that are N-fold graphs was obtained experimentally for a large number of random graphs from each of the four difl'erent classes of graphs. N-fold graphs can be evaluated exactly by the Oracle algorithm. Thus, if a large percentage of graphs in a class are N-fold graphs then the Oracle algo- rithm will produce exact results for most of the graphs in that class. An earlier version of the Oracle algorithm could only handle a subset of N-fold graphs called simple fold graphs [Mil90a]. To illustrate the improvement of the current Oracle algorithm over the previous one, the number of simple fold graphs was also counted Additionally, the improvement suggests that adding a few more reduction patterns to the Oracle algorithm can further increase the percentage of graphs that can be handled exactly. Figure 5-10 shows the percentage of N-fold graphs (N data points) and simple-fold graphs (S data points) for the four data sets. Figure 5-10 a shows that as both the number of vertices and edges are increased at the same rate, the number of graphs that can be evaluated exactly falls off sharply. This is due to the graph structure becoming more and more complicated, so that the series, parallel, and N patterns cannot reduce the whole graph. Figure 5-10 b shows that for less constrained graphs the percentage of N-fold graphs falls ofi‘ more slowly. Additionly, the difference between the percentage of graphs that are N-fold and simple-fold graphs is readily apparent. These two graphs indicate that the ability of the Oracle algorithm to exactly evaluate graphs falls ofi when the number of vertices and edges becomes large. The use of subassemblies and scripts in process planning can help keep the number of different vertices in the graph to a reason- able number, thereby allowing the Oracle algorithm to exactly evaluate a large percen- tage of graphs without having to resort to bounding values. 141 The effects of varying either the number of edges or the number of vertices while keeping the other variable fixed is shown in Figures 5-10 c and d. For a fixed number of edges (or vertices) a large variation in the percentage of N—fold graphs can be found when difierent numbers of vertices (or edges) occur in the precedence graphs. Figure 5-10 c shows that the percentage of N-fold graphs varies as the number of vertices is increased in graphs with a fixed number of edges. The percentage of N-fold graphs starts out at 100 percent for six vertices and drops ofi quickly until it bottoms out around 18 vertices before rising back up again. A similar result holds for varying the number of edges while keeping the number of vertices fixed as shown in Figure 5-10 (I. When a small number of vertices and a large number of edges are placed in a graph (such as the first data point in data set c, or the tail end of data set d) the graph has many redundant edges. If unique edges are continually added to a small number of vertices (in an acyclic graph) a point is reached when no more edges can be added without causing a cycle in the precedence constraints to occur. A complete directed graph (a graph with a single directed edge between every pair of vertices) is called a tournament [Hara69]. If we further restrict the tournament to be acyclic, then only a single possible ordering of the vertices exists. After the redundant edges are removed from an acyclic tournament a single linear chain of vertices remains. When all the redundant edges are removed from graphs with a large number of edges and a small number of vertices, the non-redundant edge graphs are likely to be N-fold graphs -- or in the extreme case of acyclic tourna- ments -- represent a single possible ordering. Graphs with a large number of vertices and only a few edges are likely to consist mostly of unconstrained vertices along with a few sets of vertices in subgraphs with a small number of constraints. Such graphs can often be reduced using the parallel, series, and N-fold reduction patterns since they are so simple and not cluttered with criss- crossing edges. This explains the gradual increase in the percentage of N-fold graphs for the last part of data set c and the quick falling off of the percentage of N-fold graphs for % of Graphs that are N-fold and Simple Fold Graphs % of Graphs that are N-fold and Simple Fold Graphs 1(1) 100 I d l as \. s) . Essen—s—s-s-s 20 40 60 80 a) No. Vertices = No. Edges U I F 7 40 60 80 c) No. of Vertices (15 Edges) 142 % of Graphs that are N—fold and Simple Fold Graphs % of Graphs that ae N-fold and Simple Fold Graphs § 44 \ SN a .\\ N S\ 8' \ N S \ N s I \ s\i \S N\ 8 r \ 3N\ 85.8 N\N a ‘S~s:§:§ 20 40 60 80 b) No. Vertices = 2 "' No. Edges 8 I , _ .. N NN §,§ J ,~’. 8 W N g / / N S s . / / S I ”/ ... /s ‘q rt/ I /S 8 ‘ S N5 // \st SS O 20 40 60 80 d) No. of Edges (15 Vertices) Figure 5-10: % of N-fold and Simple-fold graphs in a Random Sample 143 the first 5-15 edges in data set (1. 5.6.3. Experimental Run Time for the Oracle The Common Lisp implementation of the N-fold Oracle algorithm was timed on a Sun 4/390 with 32MB of memory (running Unix 4.0.3) for each class of random labeled acyclic graphs that was discussed in Section 5.6.2. The experimental run time for the Oracle algorithm to determine exact values for N-fold graphs or to determine that the graph is not an N-fold graph is shown in Figure 5-11 for each class of random labeled acyclic graphs (a decision problem). Each graph shows a run time of O( IV l2) time com- plexity. Portions of the graph show nearly linear relationships between the number of vertices (edges) and run times. In fact, least squares fitting shows that the run times appear to be closer to lanl * IVI time than IV l2. This might be due to the lisp compiler optimization of the various searching operations used in the Oracle algorithm. Figure 5-12 shows the run time for the Oracle algorithm to determine the exact values for N-fold graphs and return bounds for all non-N-fold graphs. The run times shown in Figure 5-11 did not include the time taken to return the upper and lower bounds for non-N-fold graphs (which is included in Figure 5-12). Figure 5-12 a shows that the Oracle only requires one half second on average to determine the number of different task orderings or bounds for 80 tasks and 80 vertices. Out of the 100,000 random graphs tested with 80 tasks and 80 vertices the maximum time required to return an exact value or bounds was 1.1 seconds. For such a large number of tasks and constraints the number of possible task orderings can be up to of 79! ~ 10‘". Obviously, trying to enumerate such a large number of different orders is computa- tionally intractable. Whenever, a large number of tasks (i.e. more than 40) are to be per- formed, some method for reducing the number of tasks should be considered to avoid potentially enormous search spaces. For example, subassemblies, hierarchical planning, or subgoals could be used to cut down on the number of possible orderings. The Oracle CPU time in milliseconds CPU time in milliseconds I“) 120 80 20 150 100 144 I U I 20 4O 60 a) No. Vertices = No. Edges 20 40 60 c) No. Vertices (15 Edges) I? ii i so i 3% Ii i3 80 150 100 30 2O 20 40 60 80 b) No. Vertices == 2 " No. Edges 2O 40 60 80 d) No. Edges ( 15 Vertices) Figure 5-11: Oracle CPU Time for Random Graphs (Decision Problem) CPU time in milliseconds CPU time in milliseconds IN 100 145 200300400500 a) No. Vertices = No. Edges 40 .i 20 c) No. Vertices (15 Edges) 40 60 80 CPU time in milliseconds CPU time in milliseconds / § . . / + ’4- + ++ c V Y T 20 40 60 80 b)No. Verticess2‘No. Edges + ’+ 8 « +\ + a a + + / \ . +. ' 3 a g + 20 4O 60 80 d) No. Edges (15 Vertices) Figure 5-12: Oracle CPU Time for Random Graphs (Exact Values and Bounds) 146 algorithm could be helpful when it is impossible to reduce the number of difi‘erent tasks by allowing the user to keep adding constraints to the set of tasks until the number of pos- sible plans becomes manageable. Although the Oracle algorithm is a low order polynomial time algorithm, the time required to determine bounds for non-N—fold graphs is approximately three to five times as long as the time required to determine the exact number of orders for N-fold graphs. This explains the apparent deviation from the expected low order polynomial increases in run time as shown in Figures 5-12 c and d. In Figures 5-12 c and (1 either the number of edges or vertices remains fixed, while the other parameter is varied The small knee in the CPU time plot of Figure 5-12 c and the much more pronounced knee shown in Figure 5-12 d is due to the large percentage of non-N-fold graphs in the knee areas relative to neighboring points in the plots. Since determining the bounds for non-N-fold graphs takes longer than determining exact values for N—fold graphs, points in the graph that have a larger percentage of non-N-fold graphs than neighboring points will require a disproportionately larger amount of CPU time. 5.7. Summary of Chapter 5 The graph representation, initialization, processing, and evaluation stages of the Oracle algorithm were outlined in detail. The three reduction formulas were stated and it was verified that they reduce N-fold precedence graphs while exactly evaluating the number of orders possible. Estimating heuristics were described that produce lower and upper bounds on the number of possible orders for acyclic precedence graphs. These heuristics were applied to several graphs demonstrating their use in evaluating non-N- fold graphs. An overall 0( I V I2 * IEI) time and O( I V I2) space complexity for the Oracle algo- rithm was derived, and supported by simulation runs. Several classes of random labeled acyclic graphs were used to experimentally determine the percentage of these graphs that 147 are N-fold graphs which can be exactly evaluated by the Oracle algorithm. The Oracle algorithm is best at exactly handling graphs with a small or large number of edges rela- tive to the number of vertices, since many of these graphs are N-fold graphs. The author conjectures that everyday manufacturing precedence graphs will be more amenable to the Oracle algorithm than random labeled acyclic graphs. This is based on the observa- tion of assembly and manufacturing problems in which the precedence constraints are often of a local nature, typically with some large objects or key tasks dividing the the resulting precedence graph into parts. For example, in the AAPF system, parts with a large cross section are more likely to have constraints than parts with small cross sec- tions when ray casting techniques are used along a particular removal direction. How- ever, in random graphs every edge is equally likely -- creating less clustering of con- straints around key vertices and reducing the chance of finding separate subgraphs to be evaluated independently. Comparing the improvement of the current Oracle algorithm to its predecessor that could only handle simple-fold graphs indicates that an even larger percentage of graphs might be evaluated in polynomial time using additional reduction patterns. The experimental run time for evaluating the number of possible task orderings was shown to be 0( l V l2) for four classes of randomly generated labeled acyclic graphs. Chapter 6 Concurrent Design and Evaluation A CAPP system is proposed for Concurrent Design and Evaluation (CDE) that can aid the human designer in producing cost effective designs. The CDE system is intended for concurrent design and evaluation of products using feedback from interactive process and assembly planning modules. The CDE system is intended to capture all the salient features of concurrent process planning in a single package and can be developed using the technology available today. This chapter can serve as a high—level blueprint for an implementation of a design and evaluation CAPP system that interactively aides the human designer in producing designs that can be efliciently produced in a specific factory environment. All CAPP systems are highly dependent on the process planning domain and fac- tory environment. A CAPP system can only be built after a specific domain and manufacturing environment is identified The manufacturing environment and product domain create a framework which grounds the process and assembly planning tasks. Concurrent design of the product with feedback from the manufacturing stage allows the resulting design to be optimized with regards to the plant facilities and standard machin- ing procedures in order to produce a less costly product. The CDE system is composed of the following independent data or program modules: a feature-based modeler and database for gathering information on the part being designed; a factory database including information on the machines, tools, and machining parameters; an assembly planner; a process planner; interactive assembly and 148 149 process planning design critics; the Oracle algorithm; search and evaluation routines; and a robust simulation package. A designer would interact with the feature-based modeler and the various CDE modules to produce a design that could be efiiciently created in the flexible manufactur- ing environment which is modeled in the factory environment database. The current Oracle software package can be extended to be more effective in a CAPP package such as CDE. Several difliculties exist for the development of the CDE system and must be overcome before all the potential benefits of the proposed CDE system can be realized 6.1. Process Planning Domain and Environment The process planning function depends heavily on the manufacturing environment and domain [Chan85]. Since a general process planning system would have to handle all possible product types: discrete metal parts, plastics, wood, composites, sheet metal, etc., it is likely that the trend for creating domain-specific CAPP systems will continue. Obvi- ously, the process planning task depends on the machines available in the factory that can create various machining features. A process planning system must have accurate knowledge of the machines and tools available on the shop floor along with the machin- ing parameters and limits for the difl‘erent processing and assembly functions in order to create efiicient process plans. The nature and complexity of the process planning task requires appropriate knowledge representation techniques for the domain-dependent and factory-specific knowledge. Although a CAPP system should store data useful for all the departments as described in Section 1.2, the description in this chapter is limited to the functions inside the dashed box shown in Figure 6-1. Figure 6-1 is adapted from the book by Nevins and Whitney on Concurrent Design of Products and Processes [Nevi89]. 150 Ideas, Market Studies] I Selling Price and A No Production Cost Targe ‘ Redesign .' I I I I I I I I I I I I I I I I I I I I I I I I l I I I I I I I I J Manufacturin Concurrent Design Product and Evaluation r----- I I I I I I I I I I I I I I I I l I I l I I I L Prediction of Production Cost 7 No i Yes Manufacturing System nstruction Installatio Manufacturing System Operation i Continual Comparison to Goals and Redesign of System and Product Figure 6-1: Integrated Design of Product and Manufacturing System [Nevi89] 6.1.1. Product Domain An interesting domain for the CDE system would be discrete metal parts. A data- base of raw materials available for manufacturing the products is necessary to help deter- mine the feasibility and cost of creating difi‘erent product features and components. This database would include information on the various dimensions and material types of rod, bar, and other stock materials as well as the available fastening agents. This information would have to be readily available to other modules in the CDE system such as the interactive quick checking process planning module. For example, if the designer 151 specified an axle diameter of 0.9" for a lawn mower and bar stock of 0.8" and 1.0“ diame- ter were available, then the quick checking process planning module might suggest to the designer that an alternative diameter of stock be used to avoid unnecessary machining or processing steps. The type and/or size of available fastening agents should also be kept in a global database. This would inhibit the designer from calling for non-existent screw lengths or trying to use fasteners that would not have the bonding strength necessary to hold the subparts together as called for in a design. Although the CDE system can warn the human designer about potential problems, the human designer should be able to override the warnings. For example, the designer may decide to order a new size of fastener or to create a new fastener in order to produce better designs. The interactive process plan- ning module would try to help minimize the different types or sizes of fasteners used. Additionally, ease of assembly must be balanced with other fastener issues. The interac- tive process planner may suggest the use of rivets rather than screws to fasten parts together if the designer specified that the parts are unlikely to be disassembled during the life of a product. 6.1.2. Factory Environment A minimal configuration of machine tool capabilities should include the four basic machining processes: turning, drilling, milling, and shaping, which can theoretically pro- duce any contour on a workpiece [Gr0083]. Ideally, a large array of operations would be represented in the manufacturing database to conform to a typical job shop. A larger set of machines and processes are [GrooSO]: machines: lathe, turret lathe, chucker, manual drill, NC drill, milling, shaper, planer. processes: bore, cutofi', grind (surface, exterior or interior cylinder, centerless), broach, deburr, polish, buff, clean, paint, plate, assemble, inspect, package. 152 A modular construction of the factory environment database is desired so that entries can easily be added, modified, or deleted as new processes become available or conditions on the factory floor evolve. The capabilities, tools, costs, and other factors associated with each machine must be stored so that the CDE system can find the most appropriate machine to create the features present in a part. Boothroyd investigates the performance and economics of six different assembly systems ranging from operator assembly lines without part feeders, to an automatic Universal assembly center [Boot82]. A flexible manufacturing environment for the CDE system could include assembly cells with a set of part magazines to hold the parts and fasteners that comprise the product and two three-degree-of-freedom robots for assem- bling the product on a work carrier. The work in progress could be moved among machining and assembly cells using Automated Guided Vehicles (AGVs). Special work carriers are useful in orienting and transporting the parts and subassemblies from station to station. 6.2. The Concurrent Design and Evaluation System The CDE system is intended to aid the human designer in producing designs that can be manufactured efficiently in a specific flexible manufacturing environment. As with any interactive computer package, the user interface is of key importance. The sys- tem must be easy to use with the product design, evaluation, and planning functions integrated into a single package. A menu-driven, graphical, window-based environment is desired to allow all of the CDE modules to be easily accessed and used. Figure 6-2 shows the main components or modules in the CDE system. Adjacent modules in the figure share data and commands depending on the state of the design and user requests. The three—dimensional feature-based modeler is at the heart of the CDE system. The product design features, tolerances, material type, intended use, and other desired performance attributes are kept in the three-dimensional feature-based modeler 153 Factory Database: Machines, Tools, Raw Materials, Machining Interactiv Paramete Interactive Assembly Planning Criti Assembly Planner Search Techniques Evaluation Routines Figure 6-2: CDE System Interaction Diagram database. Periodically, as the human designer is creating the product design, the interac- tive assembly and process planning modules check the current design for possible design flaws. Any potential problems found by the periodic design critics are highlighted in the feature-based modeler display window so that the human designer can decide whether or not modifications are necessary to improve the manufacturability of the product. An additional function of the CDE system would be to categorize and save the part being designed for future reference. This could be performed using part classification codes or with the designer specifying the part type and function using predefined categories. If a part being designed is similar to a previously designed part, the CDE sys- tem can bring this fact to the attention of the designer so that a variant approach to the design and process planning tasks can be chosen. 154 A process and assembly plan can be developed using the assembly and process planning tools once the design has been entered. These tools use the factory database of machines, tools, and machining or assembly parameters to help determine an efiicient process plan for the product. At the beginning of the design phase (and for various sub- planning problems), the process or assembly planning modules can call up the Oracle algorithm when a fixed set of tasks is to be performed subject to precedence constraints. The tasks to be performed are derived from the features and geometry of the part by the assembly or process planning modules. However, the precedence constraints may be interactively entered by the designer and/or derived by the assembly and process plan- ning modules. When the Oracle algorithm is invoked, a graphics window displays a graph or graphs with vertices representing the various tasks to be performed and directed edges between vertices representing precedence constraints. The designer can then add or delete constraints as desired in order to reduce the number of alternative possibilities or to increase the size or flexibility of a set of possible task orderings. Based on the number of possible task orderings for the various subplanning or planning problems, the system can recommend various search techniques to find an efiicient plan. In addition to using different search techniques, the alternate plans can be evaluated at different levels of detail. For example, plans could be evaluated based on the actual robot arm motions and machine tool paths. At any time during the planning stage the designer may request a graphical simula- tion of the machining or assembly steps for a particular plan. Previewing the machining or assembly steps can give the designer insights into ways to improve the manufactura- bility of the products, or it may highlight some invalid assumptions or constraints that had been placed on the planning problem. The interactive nature of the CDE system would allow the human designer to sift through a large search space of possible process plans in order to find a set of the most promising process plans. Each one of the best process plans could be evaluated in detail and ranked according to the predicted cost. This set of 155 rated process plans could be stored along with the product design for use on the manufac- turing floor. Additionally, each part and product would be coded for future reference so that it could be called up again if a similar part is designed at a later date. 6.2.1. Information Storage and Data Structures An important issue in the development of the CDE system is to decide what infor- mation is necessary for the design, evaluation, and process planning tasks and how this information should be stored in the various CDE modules. Without actually developing the CDE system for a specific domain and factory environment, it is impossible to deter- mine exactly what knowledge must be embodied in the CDE system and how this infor- mation should be stored. However, some general information categories and appropriate knowledge representation schemes for these difi‘erent categories can be identified. The general information to be stored and used by each of the main CDE modules is: Factory Database Module: Holds information on machines, tools, raw materials, machin- ing paramenters, and processing techniques. Additionally, machine and tool geometry should be stored for use in detailed simulations. This compiled informa- tion must be kept up to date as factory conditions or manufacturing technology changes. 3-D Feature Based Modeler: Geometric product information is stored in CSG, B-rep, and other geometric formats. Part features and other attributes or characteristics can be stored in property lists (e.g. material type, part connectivity). Relations between parts in the product (such as wheels fitting loosely over axles) should also be stored as relational part attributes. All of this information is entered by the user or derived from user supplied information. Interactive process planning critic: Expert process planning information is stored in rules which can be applied to the geometric and attribute data for the product being designed. 156 Interactive assembly planning critic: Assembly planning rules of thumb are stored in rules (similar to the interactive process planning critic). Process Planner Module: Could store process planning knowledge in both procedural and rule based formats as appropriate. Assembly Planner Module: Stores assembly planning expertise in procedural and rule based formats. Oracle algorithm: Receives the set of tasks to be performed and the precedence con- straints fiom the assembly or process planner modules that invoke the Oracle. The designer would be able to interactively change the set of tasks and/or constraints to aid in creating a desired number of different task orderings. Simulation Package: Requests factory environment and machine geometry data from the Factory Database. Receives part geometry from Feature Based Modeler and machine/robot movement information from assembly or process planner modules. Simulation module may be used to act as a detailed evaluation routine. Search Techniques and Evaluation Routines: Search techniques would require a set of tasks and constraints or some other appropriate search domain to be investigated. The search and evaluation routines may also require product geometry and attri- butes from the Feature Based Modeler. Factory environment, machining parame- ters, and costs can be obtained from the Factory Database as needed. 6.2.2. Factory and Domain Specific Database All CAPP systems are specific to a particular domain of part/product types and include assumptions about the factory environment, machines available, and methods of creating various features. Section 6.1 described the importance of the factory and domain-specific environments and discussed the type of data that should be kept in the factory environment database. The machine, tools, machining parameters, and resources 157 available for creating various parts must be made available to the assembly planning, process planning, evaluation and simulation packages in order to ground the CAPP sys- tem in the real-world. For example, plans can not be evaluated or rated without knowledge of the raw materials, machining processes, and tools available for manufac- turing the final product design. 6.2.3. Solid Modeling Package The solid modeling package is the heart of the CDE CAPP system. It must be capa- ble of interfacing to other languages, expert systems, databases, and decision making programs. To facilitate the process planning task and to share the design data, a central and consistent method for representing part features, tolerances, material type, etc. must be available. Feature-based modelers are just now becoming available with more sophis- ticated systems under development. One way to make this data available to other modules would be to place the data in a standard data exchange format. Due to the expressiveness and information richness of the proposed Product Data Exchange Specification (PDES) standard, it would be the best choice for sharing CDE design data with other external display and processing modules. However, the PDES standard is under development, and only recently has the first draft of the specification been put for- ward. It is unlikely the PDES standard will be available and stable enough to be incor- porated into the proposed CDE system in the near future. Thus, using the current Initial Graphic Exchange Specification (IGES) standard is the best remaining option for con- veying geometric data to difl’erent reasoning or display modules outside of the CDE sys- tem. As an alternate to using a standard such as IGES to share information, the geometric and attribute data could be requested by the planning, simulation, and evaluation modules from the feature-based modeler as needed. For example, if the solid modeling representation of the product being produced is readily available to the process and 158 assembly planning modules, then very little if any information must be asked of the user. The solid modeling package should have an internal programmable interface that can be programmed to call and receive data or commands from programs outside of the solid modeler. For example, if the designer has added another part to the product being designed, the solid modeling program could call up the incremental process and/or assembly planning critics. These process and assembly planning critics would use expert system production rules to check for potential design problems that may cause unneces- sary machining or assembly expense. This should enable problems to be caught early in the design stage. Ideally, keeping the product design and specification information readily available in the solid modeling/product description database would keep out-of-date information from being used when the manufacturing engineer or marketing people reference the product data. One problem with relying on blueprints and other paper information is that old copies of the blueprints can be mistaken for the current blueprints. Additionally, storing and retrieving blueprints and other paper documentation can be difficult for large job shops or projects. For example, the sister cruise ships SS Constitution and SS Independence took some 80 tons of blueprints to describe [Kuth83]. Managing and keeping such a large amount of blueprints up to date is a difiicult task. In addition, having the geometric and part attribute information in a central location helps to free the designer from having to enter data twice. For example, having the features of the product readily available to the process planning module reduces the nwd to question the human designer about tolerance values for a feature if the user has already entered this data. If tolerance data is needed by the process planning module and it is not in the design data, then the needed data can be requested through an appropriate call to the feature-based modeler. The solid modeling window would be called up by such a request and the surface or feature that requires additional tolerance data would be highlighted. The response of the user would then be entered directly into the 3-D 159 database for future reference. 6.2.4. Interactive Assembly and Process Planning Critics Periodically during the design, creation, and editing stage, the interactive process and assembly planning modules would check the design for potential design errors or defects. For example, the interactive planner would highlight a planned hole if it were too close to the edge or if it would be difficult to machine to the desired tolerance. The user could request information on highlighted potential problems as desired. The interac- tive assembly and process planning design critics act as a back seat manufacturing planner that can be set to check the design at different intervals. These interactive feasi- bility critics attempt to eliminate some of the redesign cycles that occur when the designer and manufacturing engineer discuss a given design. Potential problems the interactive process planning critic would check for: 1) Feature difficult to machine. Another surface may be restricting access or clearance above the surface to be machined. 2) Feature is too small or large to be made with current machines and tooling. 3) Part needs special machining and/or fixturing. For example, a thin sculptured part may be too delicate to withstand typical machining and fixturing forces. 4) Requested component is only slightly difl'erent from available raw materials. The designer may wish to change the component size to a readily available component or change the part dimensions according to raw material in stock. 5) Hole too close to the edge of a part (may break through) or hole has too high of a tolerance. Examples of potential problems or inefiicient designs that may be detected by the assembly planning critic: 160 l) Overlapping tolerances between pairs of mated parts. For example, calling for the insertion of a 1" diameter metal rod with an outer surface finish tolerance of :t 0.01" into a 1" :l: 0.01" hole could result in rods that became jammed during insertion. 2) Lack of sufiicient chamfering for a part to be inserted into a hole. Sufiicient chamfer- ing is particularly helpful when an automated assembly cell is being used. 3) Need for an intricate or large number of different fixtures. For example, highly sculp- tured objects or strange part shapes that do not have a good base part with planar surfaces for ease of positioning and fixturing are potential problems. Also, if many different assembly directions are necessary to add parts to a product during assem- bly, then the subassembly may have to be flipped or rotated periodically during assembly -- possibly even requiring difi'erent fixtures for each rotation. 4) The parts being assembled are too small or too large to be handled by the available assembly cells, (may require special tooling.) 5) Using a large number of different types and sizes of fasteners may require additional part magazines or increase the number of tooling changes necessary to assemble the product. Additionally, calling for fastener sizes or types not usually stocked would be flagged due to extra ordering and inventory costs. 6.2.5. Process and Assembly Planning modules The process and assembly planning modules are invoked after the human designer has entered a tentative design. These modules use the geometric and feature-based infor- mation along with the attributes of the product design to determine eflicient process and assembly plans for the current design. These modules would have to determine appropri- ate fixturing devices and setups, either interactively with the designer or automatically using a fixturing expert module [Boer88, Eng186]. A hierarchical approach to finding efficient plans is useful in decreasing the complexity of the assembly and process plan- ning tasks. A total of five difl’erent command levels are described in [McLe83]: facility, 161 shop, cell, work station, and equipment. At each level, knowledge about commonly used subsequences of commands could be applied to help limit the number of difi’erent sub- sequences of tasks that need to be checked. The concept of using scripts for subse- quences was discussed in Section 2.4.4. For example, creating a high tolerance 1/2" hole could be accomplished using one of the following subsequences of operations: (drill, ream), (drill, hone), or (core, ream). In order to help control the number of possible options available at the different levels, a combination of top down and bottom up plan- ning may be helpful. The process and assembly planning modules should incorporate computer-aided inspection and testing steps into the final process plan to verify that key components and subassemblies are within the desired specifications. The tasks to be performed and the precedence relations among the tasks can be derived by the assembly and process planning modules for some of the process planning subproblems. However, some of the precedence constraint knowledge is difiicult to determine automatically and should be entered by the designer [Bour84, DeFa87, Huan89]. The assembly and process planning modules can call the Oracle algorithm to get an idea of the search space size whenever a set of tasks is to be performed subject to precedence constraints. Once the size of the search space is known, appropriate search and evaluation techniques can be chosen based on the number of possible orderings. For example, the high-level machining and assembly steps could be evaluated to determine approximate costs for moderately sized search spaces or in order to get rough cost esti- mates for a plan. However, large search spaces may require some type of heuristic search to cut down on the number of different task orderings to be evaluated. A large search space can be investigated to find the most promising alternatives, and then a detailed simulation of the most promising alternatives can be used to choose the most promising plan. 162 6.2.6. Oracle Module The Oracle algorithm is called up by the assembly and process planning modules when a set of machining or assembly tasks has been decided upon and a set of pre- cedence constraints restricts the possible task orderings. For example, given a primary assembly direction”, precedence constraints on the assembly of the components in a product can be derived based on potential collisions between parts during the assembly. If the assembly of part A along the primary assembly direction would cause a collision with parts B and C if parts B and C were already assembled, then the precedence con- straints A < B and A < C would be indicated. Any valid assembly sequence along the primary assembly direction must not violate any of these derived precedence constraints. Other precedence constraints can be obtained from the designer as discussed by [Bour84, DeFa87, Huan89]. This process of gleaning the precedence constraints from the user could be facilitated by having the feature-based design and machining informa- tion on line in the CDE package. The designer could use the CDE system to explore alternatives in applying or removing precedence constraints to the assembly or process planning tasks and have the Oracle algorithm determine how many different task order- ings were possible for each alternative. Depending on the intentions of the designers, they could increase the flexibility of the set of plans or reduce the number of possible sequences to restrict the search space so that it would be less costly to find the most eflicient solutions. 6.2.7. Search / Evaluation / Simulation A tool box of possible search and evaluation routines should be available in the CDE system. Some search techniques to consider are heuristic searches, A . , branch and bound. beam search, and other alternative search methods for difierent search domains. ‘9 One of Boothroyd’s rules for Product Design for Assembly is to try and build the product in a layered fashion with each part being assembled from above [Boot82]. 163 The heuristic search category would include a variety of different domain-dependent heuristics that prune the search space using simplifying assumptions -- which may result in a suboptimal answer. Although using an A. search technique with an admissible evaluation function is guaranteed to find an optimal solution (with respect to the evalua- tion function), it may require a large amount of time and/or memory to conduct the search. Different evaluation functions could be applied in evaluating partial or complete process plans. These evaluation functions could rate high-level plans or evaluate plans in detail down to actual robot arm motions and grasping positions for a specific simulated factory environment. Either the human designer or assembly and process planning modules would select the type of search and/or level of evaluation used in searching for efficient process plans. In addition to the evaluation functions, typical analysis of designs such as finite element analysis should be available in the CDE system to verify certain properties of the designs. The simulation package in CDE should be able to represent the factory environ- ment: machines, robot arms, fixturing, and the product being machined or assembled. Showing a simulation of a proposed assembly or process plan may give the designer ideas on how to improve the design and aid in the selection of alternative plans. Colli- sion detection between objects in the environment and subassemblies or machines in motion is desired in order to validate proposed process plans. Verification of the validity and cost of different process plans can save time and efl’ort by keeping infeasible or inefiicient process plans from being attempted in the factory only to find out about the plan deficiencies at that time. 6.3. The Oracle Software The current Oracle software has been an aid in the interactive investigation of the number of sequential orderings represented in precedence graphs. The experiments and 164 results on the number of possible task orderings presented in Chapters 4 and 5 were obtained using this software package. The Oracle package is implemented in Common Lisp and uses the Common Windows graphical interface to access the X windows environment for entering and displaying precedence graphs. Additional code can be invoked to test the Oracle algorithm on sets of randomly generated precedence graphs. 6.3.1. Current Implementation of the Oracle The Oracle software is an interactive, window-based, menu-driven graphical pack- age for representing, displaying, and investigating the number of different sequential ord- ers represented in a precedence graph. The Oracle software has been developed, extended, used, and tested for over a year. The code is well documented and modular so that various subroutines or functions can be easily modified or replaced. The package allows a user to quickly draw a precedence graph on the screen using the mouse and to investigate the number of different sequential orderings represented by the graph. Ver- tices and directed edges are added to or deleted from the graph using a mouse and several modifier keys. Menu choices exist for running the Oracle algorithm, enumerating the number of possible task orderings in the graph, changing the display scale (to accom- modate larger graphs), and saving or recalling previously defined graphs. Several other choices allow for testing and verifying proposals and statements made by other research- ers. 6.3.2. Extensions The Oracle algorithm can be enhanced and extended to maximize its usefulness for the proposed CDE CAPP system. The proposed extensions are: 1) An additional routine should be added to translate from general precedence con- straints to a set of precedence graphs that can be evaluated individually. Currently, this step is done by hand. Each one of the resulting precedence graphs could be 165 displayed in different parts of the graphics window (which is scrollable) or the graphs could be displayed one at a time as they are evaluated or investigated. 2) Adding several more reduction patterns to the Oracle to increase the set of graphs that can be handled exactly. 3) The graph identity shown in Figure 4—11 could be intelligently applied to graphs in order to exactly solve a larger class of graphs. Unfortunately, every application of this identity increases the number of precedence graphs to be investigated so it must be carefully applied. 4) Investigate the possibility of enumerating small non-N-fold subgraphs with less than eight vertices in order combine the result exactly with other N—fold subgraphs and produce better bounds and a larger percentage of exact answers. 5) The upper and lower bounding values could be improved as described in Section 5.4. This method would require keeping the ancestors and descendents of each vertex up to date as the graph is evaluated. Then, whenever a simplification heuristic is applied, the resulting upper or lower bounds can be made closer to the actual values. 6.4. CDE: Theoretical Research and Implementation Issues Some aspects of implementing the CDE system will require additional research efl’ort to overcome the current limitations and assumptions made in addressing various CAPP tasks. The CDE system could serve as a testbed for developing and comparing different methods for solving various subproblems of CAPP. This is one reason for the modular design of the proposed CDE system. As the system is being developed the difl’erent modules can be treated as black boxes with known inputs and desired outputs. Based on the assumptions and coding tasks finished at any given time, the other CDE modules can be developed and tested individually or with other partially or fully imple- mented components. 166 Some difficult theoretical issues that require additional research to create a robust CDE system are given below. In addition, references are given for each category to serve as pointers to some of the literature that partially addresses or discusses the difficulty of research in that area. 1) Ongoing research is progressing in the areas of feasible path and grip planning for robot manipulators. Current algorithms are very time consuming and do not pro- duce optimal plans for complex environments [Dona87, Fers86, SharS6, Sand90]. 2) Fixture design and selection of setups to constrain parts during the assembly and machining stages is difficult to automate [Boer88, Eng186]. 3) Correctly determining the stability of arbitrarily shaped subassemblies is intractable in general, but some special cases can be handled [Palm87, Hof90a]. 4) Finding optimal plans and schedules given a large number of alternative plans is difi‘nult. This is especially true when it is computationally expensive to evaluate each of the possible alternatives accurately [Sand90, Fox85, Whit88]. Homnan has recently deve10ped reuse theorems that can be applied to deduce some freedoms of motion for new assembly states from previous calculations rather than computing everything again [Hof90b]. 5) Reasoning about uncertainties in the assembly environment and determining robust recovery plans is a diflicult problem [I-Iutc90]. 6) Investigating how tolerances afi'ect finding eflicient and even feasible assembly plans is an area of ongoing research [Sand90]. Some parts of the proposed CDE system already exist and should not require addi- tional research, but instead require a good deal of implementation efl‘ort. Software ven- dors are starting to market feature-based modelers that would work quite well in a system such as CDE. However, the problem of getting these commercial packages to interface with the other modules in CDE may be diflicult. 167 Implementation is not always easy. Combining existing theory and knowledge to create a result that is greater than the sum of its parts can be diflicult. Although the U.S. has been known for producing new ideas and good research, it is not as well known as other countries at creating eflicient implementations which take advantage of the time and cost savings that are possible using existing technology and methods. In a competi— tive industrial environment creativity is essential, but it is equally important (if not more so) to put ideas into action in order to gain a competitive advantage. Many search techniques are known and only need to be implemented for the CDE framework. However, determining which techniques are best suited for the difl'erent types of search spaces arising in the CDE system is an area for further investigation. Although some evaluation techniques have been discussed by various researchers, the development of accurate evaluation functions may be difiicult. Various packages exist for simulating motions in a 3-D environment but are not without assumptions and limita- tions. If an appropriate simulation package for the CDE system does not come bundled with a feature-based modeler, then additional work may be required to create a useful system for simulating the machining and assembly environments. Chapter 7 Conclusion, Discussion and Areas for Future Research The future for computer-aided process planning seems bright. Good progress has been made in many areas such as restricted part type CAPP systems, knowledge engineering, geometric solid modelers and the current development of feature-based modelers. As the ranks of expert human process planners continue to decline, the need for CAPP systems will grow. Much more research needs to be done in trying to build more general CAPP systems and integrate CAPP into the CAD/CAM environment, as discussed in Chapter 6, so that the transition from the design of the product to its manufacture is smoother and more free from unnecessary human intervention. A good system would also be able to explain how the final process plan was constructed. Knowledge engineering plays a key role in this development. 7.1. Summary of Thesis The survey of variant, generative, and artificial-intelligence-based process planning systems showed that there are many diflicult representation and processing issues involved in CAPP. This thesis has investigated the varied costs associated with different process plans and the number of feasible process plans. There are many similar com- binatoric and geometric reasoning tasks that occur in both the manufacturing and assem- bly planning domains of CAPP. Some difficult processing problems were investigated in the development of an Automated Assembly Planning with Fasteners (AAPF) system that reasons about fasteners and the assembly planning task. 168 169 The AAPF system works directly from the CAD model of the product to be assem- bled [Mi189a]. In order to avoid a combinatoric explosion of possible assembly sequences, the AAPF system assumes that no internal or external forces occur during the assembly process, and therefore, the reverse of a disassembly sequence is a valid assem- bly sequence. Starting with an assembled product, finding a disassembly sequence is much easier than finding an assembly sequence because the number of feasible removal directions for each of the parts in a product being disassembled is limited by the other parts in the assembly. Additionally, if the disassembly can be accomplished with each step consisting of the complete removal of a part from the assembly (monotonic assem- bly), then no dead end states can be reached that require backtracking. However, dead end states can occur if an assembly planner tries to find a valid assembly sequence start- ing with all the parts disassembled. To the best of our knowledge, the AAPF system was the first system to derive fastener and component connectivity from geometric information to determine which components were held together by which fasteners. Additionally, it was the first system to reason about individual fasteners and to use heuristics based on fastener type, size, and location in an attempt to derive efiicient disassembly plans. Although these heuristics were designed to produce efficient assembly plans, the heuristics did not model fixturing constraints. When the AAPF plans were evaluated according to both fastener and fixtur- ing constraints, the results were mixed: some plans were efiicient and others required more time than hand-generated plans that accounted for fixturing. At least two difi’erent process plans were evaluated at a high-level for each of several difl‘erent objects. The evaluations show that ineflicient plans can require up to 100% more time than efficient plans to produce a product in a flexible manufacturing environment. The large variance in the time required to manufacture and assemble a product under different plans indi- cates the importance of searching for an efficient plan. Unfortunately, many feasible process plans may exist, making the selection of an efficient plan a difficult task. 170 Difl’erent heuristics, search techniques, and evaluation functions can be used to help overcome the problem of a large number of possible solutions. For example, if we know that many possible task orderings exist, then heuristics can be used to prune the search down to the most promising sequences. Less accurate heuristics may even be necessary in cases when an extremely large number of feasible orders exists. However, if we know that a small number of orderings exist, then each solution can be evaluated in detail to find the most eflicient sequences. Using heuristics on small search spaces risks pruning an optimal sequence from further consideration. Additionally, varying levels of detail can be used to evaluate alternative plans depending on the number of different orders possible. The number of possible task orderings can also be used to select the most flexible set of assembly or machining plans from alternate sets of plans that use different fixturing devices or approach directions. The set of plans or operations with the largest number of possible sequential orderings would tend to have more flexibility than a smaller set of feasible task orderings. For example, having a large number of alternative assembly sequences available is beneficial when individual components arrive at random times because fewer buffering operations are needed [Home90]. The general problem of determining the number of possible task orderings for a set of tasks and precedence constraints has been shown to be #P-complete (sharp-P- complete) [Wink90]. This indicates that the problem is intractable today and will remain intractable until someone can show that the NP—complete class of problems can be mapped to the class of P problems in polynomial time (considered very unlikely). Thus, the approach taken in this thesis was to find a class of planning problems that can be evaluated exactly in polynomial time and to calculate upper and lower bounds for all other problems in polynomial time. To facilitate determining the number of possible task orderings, a precedence graph representation G=(V,E) is used. Tasks to be performed are represented by vertices (V) in the graph, with precedence constraints being represented 171 as directed edges (E) between vertices. An Oracle algorithm was described in Chapter 4 that can determine the number of task orderings for a class of N-fold graphs and produce upper and lower bounds for non- N-fold graphs. The Oracle algorithm was shown to have 0( l v I2 . E) time and 0( I v :2) space complexity. Simulation results show that the Oracle exhibits an O( I V I?) run time behavior for several classes of random graphs. The Oracle uses three unique subgraph patterns to successively merge vertices in the precedence graph representation while keeping track of the number of possible orderings as each subgraph pattern is applied. The upper and lower bound calculations take advantage of several heuristics that are guaranteed to produce results that overestimate or underestimate the number of possible task orders. A CAPP system for Concurrent Design and Evaluation (CDE) of products is pro- posed but not implemented, which would use the Oracle algorithm to aid the designer and manufacturing engineer in finding an efiicient process plan. The main modules and interactions between these modules is investigated to show how various representation and processing issues could be handled. An example is given to show how the system would be useful in guiding the designer to produce a product design that can be manufac- tured and assembled efficiently in a flexible manufacturing environment. 7.2. Contributions of the Thesis The main contributions of this thesis are: 0 Investigating the importance of modeling and reasoning about fasteners in the assembly planning domain through the development of the Automated Assembly Planning with Fasteners (AAPF) system. 0 Emphasizing the large variances possible in manufacturing and assembly times for a product depending on the process plan developed. 172 0 Demonstrating that a large number of feasible process plans may exist, even for simple products, and that it is desirable to know how many feasible plans exist to help in finding an eflicient plan. 0 Developing the graph representation for a set of constrained tasks and transforma- tions which reduce complex graphs into simpler graphs. 0 Creating and analyzing an Oracle algorithm that quickly determines the number of possible task orderings for a set of tasks and precedence constraints. Exact values are returned for N-fold graphs and upper and lower bounds on the number of order- ings are returned for non-N-fold graphs. 0 Describing a practical CAPP system for concurrent design and evaluation of pro- ducts which uses information on the number of possible task orderings to aid the human designer and manufacturing engineer in producing eflicient process plans. 7.3. Discussion and Areas for Future Research The Automated Assembly Planning with Fasteners system did not account for fixturing and stability constraints. Fixturing constraints and the stability of subassemblies are difficult to address in CAPP, but progress is continually being made. Recent CAPP systems or assembly planners addressing fixturing problems are: [Boer88, Wolt89, Huan90]. Determining whether or not components in an assembled configuration will be stable20 is a very difi‘cult problem to solve. An assembled configuration can be an actual product assembly or a collection of objects positioned in three-dimensions (perhaps stacked upon or leaning against other objects). Palmer has shown that even in two— dimensions, determining whether or not a given configuration of polygons is stable under 2° Foracollection ofobjects tobeconsidered stable, the objects mustbeable to stay inplace (i.e., without falling to the ground due to gravity) even when a small force is exerted on some of the objects. An egg balanced on one of its ends is not considered to be stable. 173 certain conditions is generally intractable [Palm87]. Since a collection of polygons in two-dimensions can be extruded to form three-dimensional objects, this result indicates that under certain conditions it will be intractable to determine the stability of 3-D objects. In the realm of CAPP systems, Hofl'man has implemented an instability test in his assembly planning system that is suflicient but not necessary for detecting instability [Hof90a]. Difficult problems remain for CAPP in the areas of motion planning and collision detection. A valid assembly sequence requires additional information on valid grip points, stability and fixturing issues, part tolerances, and path planning. Optimal path planning in three-dimensions, even among polyhedral objects, is itself a problem which is known to require significant resources [Shar86]. Automatically determining disassembly sequences is difficult when arbitrary translation directions and rotations are allowed due to the infinite number of choices for the direction and rotation of components during the assembly process. Additional problems occur in determining how far to move a com- ponent in any one direction before changing directions when multiple sequences of trans- lations and rotations are necessary in creating an assembly plan. Removal direction and distance heuristics such as those implemented by Hofl'man are able to overcome some of these difiiculties in automated assembly planning for complex objects [Hof90a]. The Oracle algorithm exactly determines the number of possible task ordering for N-fold graphs and returns upper and lower bounds for all other graphs. Several methods are available for increasing the number of graphs that can be handled exactly. The most obvious choice is to investigate using other reduction patterns in addition to the series, parallel, and N shaped reduction patterns. Additional patterns that may be useful include a W shaped pattern and an N pattern with a vertex along the diagonal edge of the N. These new patterns must be studied to determine how they would affect the overall time complexity of the Oracle algorithm and the percentage of graphs it could exactly handle. 174 Figure 4-11 shows a graph identity that can also be used to increase the set of graphs that can be evaluated exactly by removing edges that are diflicult to evaluate. This is accomplished by creating two subproblems that can be solved independently. In a parallel environment each of these subproblems could be given to different processors and the results combined when each processor finishes. Another method to increase the number of graphs that can be handled exactly is to enumerate small subgraphs of vertices that are non-N-fold graphs. If the subgraphs are of size IVI S 7, then at most 5040 order- ings would have to be evaluated. The resulting values for these subgraphs could then be combined with the remaining vertices using the reduction patterns. As mentioned in Section 5.4, the upper and lower bounds can be made closer if both the ancestors and descendents of each vertex are kept up to date during the graph reduc- tion process. This would enable a more accurate count of the number of possible orders that are being lost or added depending on the graph simplification heuristic used. These tighter estimates would require additional code but would not increase the overall com- plexity of the Oracle algorithm. The Oracle was tested on a class of random graphs due to the lack of a large data- base of manufacturing and/or assembly tasks and constraints. This leads the author to wonder, "What is the nature of typical manufacturing tasks and constraints ?" Is it likely that real manufacturing graphs may have a higher percentage of N-fold graphs than ran- dom graphs with the same number of vertices and edges ? Could it be that 60% of typi- cal automobile products correspond to N-fold graphs, but only 40% of graphs occurring in aerospace manufacturing tasks are N-fold graphs ? A study of the topology of manufacturing precedence graphs may suggest a set of additional reduction patterns which would increase the number of graphs that could be handled exactly by the Oracle algorithm. Additionally, such a study may indicate some fundamental properties of manufacturing or assembly tasks that may be helpful in identifying potential subassem- blies in a product. 175 The field of CAPP should blossom in four to six years as engineering students gra- duate into the work force with a good grasp of how to use and apply computers and knowledge engineering to process planning and manufacturing. The availability of more versatile modeling and representation schemes would allow CAPP systems to go from raw product design and specification data to a complete and efficient process plan. Solu- tion of the process planning problem for large search spaces, especially when efiicient or ’optimal’ plans are desired, requires careful thought and application of an appropriate search technique and representation. Chapter 6 describes the major components of the proposed CDE CAPP system for concurrent design and evaluation of products. The CDE system should be helpful in finding eflicient process plans when many different plans exist. Although some of the components for the CDE system exist, other components need to be researched, developed, and enhanced to create a versatile CAPP system. Appendices Appendix I: Sample Input and Output from the AAPF System Partial Input Data File for the Mouse Model ..; "- M0d¢2 LISP; Syntax: Common-lisp; Package: USER; Base: 10 -e- 3; F116: SEVER2>iw>oaf>data-mouselisp Joseph M. Miller Aug. 23, 1988 ; List #1 Optional comment lists ; 1st sub list is the object name ((Partial Symbolics Mouse Definition) ; 2nd sub-list contains the names for each of the parts in the object ("black plastic case" "center mouse button" "right roller ball" "right roller holder") : 3rd sub-list contains names for each of the fasteners ("right case screw" "right roller screw") ) ; end of the comment list ; List #2 Set of objects (plus and minus primitives of type sphere, ; cone, cylinder, and block are possible) that make up the mouse assembly ;primitive + parameters rotation translationspositive/ ; about x,y & 2 along x,y, & 2 negative type ; Outer black mouse case and 3 mouse button holes defined (((box 2. 8 0.1 l .7 0.0 0.0 0.0 0. 0- 1.15 0.0 p) ; Top of outer black case (box0.80.10.3 0.00.0 0.0 -0..7-1.1500 n); center mouse button hole (box 0.8 0.1 0.3 0.0 0.0 0.0 -0. 7 -1.15 -0. 55 n); closest mouse button hole (box 0. 8 0.1 0.3 0.0 0.0 0.0 -0. 7 -l.15 0.55 n); farthest mouse button hole (box 0.1 1.2 1.7 0.0 0.0 0.0 -1. 35 -0. 6 0. 0 p) ; left short side of box (box 0.1 0.2 0.2 0.0 0.0 0.0 -1.35 -0. l 0. 0 n); hole for mouse cord (box 0.1 1.2 1.7 0.0 0.0 0.0 1.35 -0. 6 0. 0 p); right short side of box (box 2. 8 1.2 0.1 0.0 0.0 0.0 0. 0 -0. 6 0.9 p); farther long side of box (box 2. 8 1.2 0.1 0.0 0.0 0.0 0. 0 -0. 6 -0. 9 p); closer long side of box (cylinder 0.4 0.1 0 90.0 0.0 0.0 -l.17 -0. 9 -0. 3 p); leftmost screw boss (cylinder 0.4 0.1 0 90.0 0.0 0.0 0.71 -0.9 0. 26 p); rightmost screw boss ((box 0.75 0.2 0.25 0.0 0.0 0.0 -0 7 -1.18 0. 0 p) center mouse button (box0.750.050.40 0.00.000 -07-1.07 00 p) (coneO..2010.05 90.00000 -065-0.99 00p) ()(sphere 0.17 0 0 0.0 0.0 0.0 -0. 8 —0. 145 0. 5 p) ;right roller ball ((cone 0.5 0.1 0.25 90.0 0.0 0.0 -0. 8 -0. 35 0. 5 p) ;right roller pillar (cone 0.220.150.20 90.00000 -0.8 -0.21 0.5n) ) ) ; List #3 Contains the FASTENER information. ;primitive + parameters rotation translations positive] ; about x,y & 2 along x,y, & 2 negative type ( ((screw(0.060.010.01.0.8)00 90...00000 0.71-0.45 0.26 p)) ()(screw (0.040.030.00 .) 270.00.00.0 -0.8 -0.55 0.5 p)) ”0‘ t—Iu—t C § OH 7.». Cb N. O O 176 177 Disassembly Sequence for the Mouse Model ((START-OF-DISASSEMBLY) (REMOVING SCREW FASTENER (right case screw) ACCESS ((X l) (X- ) (Y 1) (Z 1) (Z -1))) (REMOVING SCREW FASTENER (left case screw) ACCESS ((X l) (X- ) (Y 1) (Z 1) (Z - ))) (REMOVING (Black plastic case) FROM ((Y- 1))) (REMOVING (center mouse button) FROM ((X l) (X -1) (Y -1))) (REMOVING (left mouse button) FROM ((X l) (X- ) (Y ) (Z 1))) (REMOVING (right mouse button) FROM ((X l) (X- ) (Y 1) (Z 1)(Z -l))) (REMOVING (base) FROM ((Y 1))) (REMOVING (left roller ball) FROM ((Y 1))) (REMOVING (right roller ball) FROM ((Y 1))) (REMOVING (main tracking ball) FROM ((Y 1))) (REMOVING (circuit board support) FROM ((Y 1) (Z 1) (Z -1))) (REMOVING (mouse cable) FROM ((X -1) (Y 1) (Y -1) (Z 1) (Z -1))) (REMOVING SCREW FASTENER (left roller screw) ACCESS ((X l) (X -1) (Z 1) (Z -l))) (REMOVING (left roller holder) FROM ((X -1) (Y 1) (Z -1))) (REMOVING SCREW FASTENER (rig ht roller screw) ACCESS ((X 1) (X -1) (Z 1) (Z -l))) (REMOVING (n troller holder) FROgM ((X -1) (Y 1) (Z 1) (Z-1))) (REMOVING SgREW FASTENER (main roller screw) ACCESS ((X 1) (X- 1) (Z 1) (Z-1))) (REMOVING (tracking ball housing) FROM ((X l) (X- 1) (Y 1) (Z 1) (Z-1))) (gaggovmc FINAL PART (circurt board with mouse switches) FROM ((X -l) (X 1) (Y -1) (Y 1) (Z -l) (DISASSEMBLY COMPLETE» *** Note: Possible disassembly directions are given for each removal operation above. e.g., The list ’((X -1) (Y 1)) indicates that the part being removed can be removed along the negative X direction, or the positive Y direction without the component(s) being removed interfering with any of the components remaining in the object. Appendix 11: Evaluation of Process Plans Each Plan in this appendix is evaluated at a high level for two different robot arm speeds in the factory environment discussed in Section 3.4.1. A summary of the results presented here appears in Section 3.4.2. In practice, plans that scored highly according to this high level evaluation function would be evaluated in more detail to determine more precisely the projected time cost of each plan. The high level evaluation function rates each machining or assembly operation based on both a fixed amount of time and the time required for the robot arm to move an average distance necessary for each opera- tion. ;‘ge distances and times for each machining and assembly operation are given in table - . Overhanging Board Assembly Sequences 'I\vo alternate assembly sequences for the overhanging board assembly are shown below. AAPF produces the optimal assembly sequence (01). The second assembly sequence was created by hand and requires a large number of reclamping and tool chang- ing operations. A significant difi‘erence of 65% or 76% more time is required for the second assembly sequence depending on the robot arm speed. Overhanging Board Assembly Sequence ol Derived by AAPF (Optimal) Time Cost for Plan Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER 2) 5. 0 5. 0 Reclamp INITIAL-FIXTURE 3) 5.0 3.5 Fetch & Assemble BLOCKB 4) 5.0 3.5 Fetch & Assemble BLOCKZ 5) 5.0 3.5 Fetch & Assemble BOLT3 6) 5.0 3.5 Fetch & Assemble BOLTZ 7) 5.0 3.5 Fetch & Assemble BLOCKl 8) 5.0 3.5 Fetch & Assemble BLOCKO 9) 5.0 3.5 Fetch & Assemble BOLTl 10) 5.0 3.5 Fetch & Assemble BOLTO 11) 5.0 5.0 Reclamp SUBASSEMBLY 12) 4.5 3.0 Tool Change to NUT-DRIVER 13) 5.0 3.5 Fetch & Fasten NUTO 14) 5.0 3.5 Fetch & Fasten NUTl 15) 5.0 3.5 Fetch & Fasten NUTZ 16) 5.0 3.5 Fetch & Fasten NUT3 17) 4 5 3.0 Tool Change to GRIPPER 18) 4.0 2.5 Move Assembly TO-OUTPUT-BIN (D \l U) m u) U1 Total assembly times 178 179 Inefficient Overhanging Board AssemblLSequence 02 Derived byjland Time Cost for Plan Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER 2) 5. 0 5. 0 Reclamp INITIAL-FIXTURE 3) 5.0 3.5 Fetch & Assemble BLOCK3 4) 5.0 3.5 Fetch & Assemble BLOCKZ 5) 5.0 3.5 Fetch & Assemble BOLT3 6) 5.0 5.0 Reclamp SUBASSEMBLY 7) 4.5 3.0 Tool Change to NUT-DRIVER 8) 5.0 3.5 Fetch & Fasten NUT3 9) 4.5 3.0 Tool Change to GRIPPER 10) 5.0 5.0 Reclamp SUBASSEMBLY 11) 5.0 3.5 Fetch & Assemble BOLT2 12) 5.0 5.0 Reclamp SUBASSEMBLY 13) 4.5 3.0 Tool Change to NUT-DRIVER 14) 5.0 3.5 Fetch & Fasten NUT2 15) 4.5 3.0 Tool Change to GRIPPER 16) 5.0 5.0 Reclamp SUBASSEMBLY 17) 5.0 3.5 Fetch & Assemble BLOCKl 18) 5.0 3.5 Fetch & Assemble BLOCKO 19) 5.0 3.5 Fetch & Assemble BOLTl 20) 5.0 5.0 Reclamp SUBASSEMBLY 21) 4.5 3.0 Tool Change to NUT-DRIVER 22) 5.0 3.5 Fetch & Fasten NUTl 23) 4.5 3.0 Tool Change to GRIPPER 24) 5.0 5.0 Reclamp SUBASSEMBLY 25) 5.0 3.5 Fetch & Assemble BOLTO 26) 5.0 5.0 Reclamp SUBASSEMBLY 27) 4.5 3.0 Tool Change to NUT-DRIVER 28) 5.0 3.5 Fetch & Fasten NUTO 29) 4.5 3.0 Tool Change to GRIPPER 30) 4.0 2.5 Move Assembly TO-OUTPUT-BIN 144 111.5 Total assembly times 180 Mechanical Mouse Assemny Sequences Three assembly sequences for the mechanical mouse are evaluated below. The evaluation of the assembly sequences includes fixturing constraints which AAPF did not consider. This is why the AAPF solution (m3) is very inefiicient compared to the other two assembly sequences which were generated by hand. Each assembly sequence is evaluated for two different robot arm speeds of 1.0 and 2.0 feet/sec respectively. The second and third assembly sequences were created by hand and require less assembly time since minimizing the number of reclamping (re-fixturing) steps was a goal of the hmnhmnhmflteqmmmes Efficient Mouse Assembly Sequence ml Derived by Hand Time Cost for Plan Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER 2) . . Reclamp PARTIAL-ASSEMBLY 3) . . Fetch & Assemble TRACKING-BALL-HOUSING 4) . . Fetch & Assemble LEFT-ROLLER-HOLDER 5) . . Fetch & Assemble RIGHT-ROLLER-HOLDER 6) . . Fetch & Assemble CIRCUIT-BOARD 7) . . Tool Change to SCREW-GUN 8) . . Insert Screw MAIN-ROLLER-SCREW 9) . . Insert Screw RIGHT-ROLLER-SCREW 10) . . Insert Screw LEFT-ROLLER-SCREW 11) . Tool Change to GRIPPER 12) . Fetch & Assemble RIGHT-MOUSE-BUTTON Fetch & Assemble CENTER—MOUSE-BUTTON Fetch & Assemble LEFT-MOUSE-BUTTON Fetch & Assemble BLACK-PLASTIC-CASE Reclamp PARTIAL-ASSEMBLY ....s U) uhthNth'lUlUlUIUlU'IUlUlUlUlUltbNNNthIUIU'IU'IUI OUTOOU'IOOOOOOOOOOOU'IOOOU'IOOOOO Noamwwwwwwwwmwwwwwmmmwwwwwm U'IOOOOUIUIUIUIUIUIOU'IU'IUIUIOOOOOUIU'IU'IUIO 17) . Fetch & Assemble MOUSE-CABLE 18) . Fetch & Assemble CIRCUIT-BOARD-SUPPORT 19) . Fetch & Assemble LEFT-ROLLER-BALL 20) . Fetch & Assemble MAIN-TRACKING-BALL 21) . Fetch & Assemble RIGHT-ROLLER-BALL 22) . Fetch & Assemble BASE 23) . . Tool Change to SCREW-GUN 24) . . Insert Screw LEFT-CASE-SCREW 25) . . Insert Screw RIGHT-CASE-SCREW 26) . . Tool Change to GRIPPER 27) . Move Assembly TO-FINISHED-BIN H I-' O‘t 01 m 0‘) 01 Total assembly times 181 Mediocre Mouse Assembly Sequence m2 Derived by Hand Time Cost for Plan Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 5.0 5.0 Reclamp PARTIAL-ASSEMBLY 2) 4.5 3.0 Tool Change to GRIPPER 3) 5.0 3.5 Fetch & Assemble CIRCUIT-BOARD 4) 5.0 3.5 Fetch & Assemble TRACKING-BALL-HOUSING 5) 5.0 5.0 Reclamp PARTIAL-ASSEMBLY 6) 4.5 3.0 Tool Change to SCREW-GUN 7) 2.0 2.0 Insert Screw MAIN-ROLLER-SCREW 8) 4.5 3.0 Tool Change to GRIPPER 9) 5.0 5.0 Reclamp PARTIAL-ASSEMBLY 1 0) 5 . 0 3 . 5 Fetch & Assemble LEFT-ROLLER-HOLDER 11) 5.0 5.0 Reclamp PARTIAL-ASSEMBLY 12) 4.5 3.0 Tool Change to SCREW-GUN 13) 2 0 2 . 0 Insert Screw LEFT-ROLLER-SCREW 14) 4 5 3.0 Tool Change to GRIPPER 15) 5.0 5.0 Reclamp PARTIAL-ASSEMBLY 16) 5.0 3.5 Fetch & Assemble RIGHT-ROLLER-HOLDER 17) 5 0 5 . O Reclamp PART IAL-ASSEMBLY 18) 4.5 3.0 Tool Change to SCREW-GUN 19) 2.0 2.0 Insert Screw RIGHT-ROLLER-SCREW 20) 4.5 3.0 Tool Change to GRIPPER 21) 5 O 3.5 Fetch & Assemble RIGHT-MOUSE-BUTTON 22) 5.0 3.5 Fetch & Assemble CENTER-MOUSE-BUTTON 23) 5.0 3.5 Fetch & Assemble LEFT-MOUSE-BUTTON 24) 5 0 3 . 5 Fetch & Assemble BLACK-PLASTIC-CASE 25) 5 . 0 5 . O Reclamp PART IAL-ASSEMBLY 26) 5 O 3.5 Fetch & Assemble MOUSE-CABLE 27) 5 0 3.5 Fetch & Assemble CIRCUIT-BOARD-SUPPORT 28) 5.0 3.5 Fetch & Assemble LEFT-ROLLER-BALL 29) 5.0 3.5 Fetch & Assemble MAIN-TRACKING-BALL 30) 5.0 3.5 Fetch & Assemble RIGHT-ROLLER-BALL 31) 5.0 3.5 Fetch & Assemble BASE 32) 4.5 3.0 Tool Change to SCREW-GUN 33) 2.0 2.0 Insert Screw LEFT-CASE-SCREW 34) 2.0 2.0 Insert Screw RIGHT-CASE-SCREW 35) 4.5 3.0 Tool Change to GRIPPER 36) 4.0 2.5 Move Assembly TO-FINISHED-BIN 159.5 123.5 Total assembly times 182 Inefficient Mouse Assembly Sequence m3 Derived by AAPF Time Cost for Plan Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4 5 3.0 32) 33) 34) 35) 36) 37) 38) U'IOOOOOUIUIU'ICDOU'IU'IU'IUIUIUIOOOOOUIOOOOOU‘OOOOOU‘U‘O N O tbthNtme'lUlUlUlUlUlUlUlUlUlUlUlththlUlUlththlUlU'IbNthlUlUIUI OU‘IOOUIOOOOOOOOOOOOOUIOUIOOOUIOUIOOOUIOUIOOOO NWNNNMWWWWWWWWWWWWWNLDMWUwNLOU'IWUIWNWUIWWUI H ON \O 01 ...r 00 co 0'! Tool Change to Reclamp Fetch & Assemble Fetch & Assemble Reclamp Tool Change to Insert Screw Tool Change to Reclamp Fetch & Assemble Reclamp Tool Change to Insert Screw Tool Change to Reclamp Fetch & Assemble Reclamp Tool Change to Insert Screw Tool Change to Reclamp Fetch Fetch Fetch Fetch Fetch Fetch Reclamp Fetch & Assemble Fetch & Assemble Fetch & Assemble Fetch & Assemble Reclamp Tool Change to Insert Screw Insert Screw Tool Change to Move Assembly Assemble Assemble Assemble Assemble Assemble Assemble mmmmmm GRIPPER PARTIAL-ASSEMBLY CIRCUIT-BOARD TRACKING-BALL-HOUSING PARTIAL-ASSEMBLY SCREW-GUN MAIN-ROLLER-SCREW GRIPPER PARTIAL-ASSEMBLY RIGHT-ROLLER-HOLDER PARTIAL-ASSEMBLY SCREW-GUN RIGHT-ROLLER-SCREW GRIPPER PARTIAL-ASSEMBLY LEFT-ROLLER-HOLDER PARTIAL-ASSEMBLY SCREW-GUN LEFT-ROLLER-SCREW GRIPPER PARTIAL-ASSEMBLY MOUSE-CABLE CIRCUIT-BOARD-SUPPORT MAIN-TRACKING-BALL RIGHT-ROLLER-BALL LEFT-ROLLER-BALL BASE PARTIAL-ASSEMBLY RIGHT-MOUSE-BUTTON LEFT-MOUSE-BUTTON CENTER-MOUSE-BUTTON BLACK-PLASTIC-CASE PARTIAL-ASSEMBLY SCREW-GUN LEFT-CASE-SCREW RIGHT-CASE-SCREW GRIPPER TO-FINISHED-BIN Total assembly times 183 ThyChmIWousstuw TWO process plans were derived by hand for the toy car model that was used by the WoodMaster planner in Section 2.1.4 (see Figure 1-1). Both efficient and wasteful sequences are given to show that significant differences in costs can occur. The bad plan c2 requires nearly 100% more time to complete than does the efficient plan c1. Efficient Process Plan c1 for the Car Model Derived by Hand Time Cost for Plan Process/Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 5.0 5.0 Reclamp STOCK-FIXTURE 2) 4.5 3.0 Fetch & Fixture 1/4-INCH-STOCK 3) 4.5 3.0 Tool Change to CIRCULAR-SAW 4) 2.0 2.0 Make Cut 1/4-INCH-AXLE1 5) 2.0 2 0 Make Cut 1/4-INCH-AXLEZ 6) 4.5 3.0 Tool Change to GRIPPER 7) 4.0 2.5 Move Assembly REMOVE-STOCK-MATERIAL 8) 4.0 2.5 Move Assembly AXLEl-TO-BUFFER 9) 4.0 2.5 Move Assembly AXLEZ-TO-BUFFER 10) 4.5 3.0 Tool Change to GRIPPER 11) 5.0 5.0 Reclamp STOCK-FIXTURE 12) 4.5 3.0 Fetch & Fixture 2-INCH-STOCK 13) 4.5 3.0 Tool Change to CIRCULAR-SAW 14) 2.0 2.0 Make Cut 4-1/21NCH-WHEEL 15) 4.5 3.0 Tool Change to GRIPPER 16) 4.0 2.5 Move Assembly REMOVE-STOCK-MATERIAL 17) 5.0 5.0 Reclamp CLAMP-WHEEL 18) 4.5 3.0 Tool Change to 1/4-INCH-DRILL 19) 2.0 2.0 Drill Hole 1/4-INCH-HOLE-IN-WHEELS 20) 4.5 3.0 Tool Change to GRIPPER 21) 5.0 5.0 Reclamp 4-WHEELS 22) 4.5 3.0 Tool Change to CIRCULAR-SAW 23) 2.0 2.0 Make Cut 1/21NCH-WHEEL1 24) 2.0 2.0 Make Cut 1/ZINCH-WHEEL2 25) 2.0 2.0 Make Cut 1/21NCH-WHEEL3-&-4 26) 4.5 3.0 Tool Change to GRIPPER 27) 4.0 2.5 Move Assembly WHEELZ-TO-BUFFER 28) 4.0 2.5 Move Assembly WHEELB-TO-BUFFER 29) 4.0 2.5 Move Assembly WHEEL4-TO~BUFFER 30) 5.0 5.0 Reclamp WHEELl 31) 5.0 3.5 Fetch & Assemble AXLEl 32) 4 0 2.5 Move Assembly WHEELl-AXLEl-TO-BUFFER 33) 4 5 3.0 Fetch & Fixture WHEELB-FROM-BUFFER 34) 5.0 3.5 Fetch & Assemble AXLEZ 35) 4 0 2.5 Move Assembly WHEEL3-AXLE2-TO-BUFFER 36) 5.0 5.0 Reclamp STOCK-FIXTURE 37) 4.5 3.0 Fetch & Fixture 4Xl-BOARD-STOCK 38) 4 5 3.0 Tool Change to CIRCULAR-SAW 39) 2.0 2.0 Make Cut 4X1X10-BODY 40) 41) 42) 43) 44) 45) 46) 47) 48) 49) 50) 51) 52) 53) 54) 55) 56) 57) N U) th'lU'lU'lUlUlthNthlUltbthIobbN OOOOOOUIOOUIOOU'IU'IOOUIO ...—I (II ...s \l Nwwmwwwmwwmwwwmwww U'IU'IU'IOUIU'IOOOOOUICOOUIOO 03 O 184 Make Cut Tool Change to Move Assembly Reclamp Place Tool Change to Fetch & Assemble Reclamp Tool Change to Drill Hole Drill Hole Tool Change to Fetch & Assemble Fetch & Assemble Reclamp Fetch & Assemble Fetch & Assemble Move Assembly 4X1X4-BODY GRIPPER REMOVE-STOCK-MATERIAL CAR-BODY PUT-GLUE-ON-CAR-BODY GRIPPER CAR-TOP CAR-BODY-AND-TOP 5/16-INCH-DRILL 5/16-INCH-AXLE-HOLE1 5/16-INCH-AXLE-HOLE2 GRIPPER AXLEl-WHEELl-BY-INSERT AXLEZ-WHEEL3-BY-INSERT SUBASSEMBLY WHEELZ-BY-FORCE-FIT WHEEL4-BY-FORCE-FIT MOVE-OUT-FINAL-ASSEMBLY Total assembly times Bad Process Plan c2 for the Car Model Derived by Hand Time Cost for Plan Process/Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER 2) 5.0 5.0 Reclamp STOCK-FIXTURE 3) 4.5 3.0 Fetch & Fixture 2-INCH-STOCK 4) 4.5 3.0 Tool Change to CIRCULAR-SAW 5) 2.0 2.0 Make Cut l/2-INCH-WHEEL1 6) 4.5 3.0 Tool Change to GRIPPER 7) 4.0 2.5 Move Assembly REMOVE-STOCK-MATERIAL 8) 4.0 2.5 Move Assembly WHEELl-TO-BUFFER 9) 5.0 5.0 Reclamp STOCK-FIXTURE 10) 4.5 3.0 Fetch & Fixture 4X1-BOARD-STOCK 11) 4.5 3.0 Tool Change to CIRCULAR-SAW 12) 2.0 2.0 Make Cut 4X1X10-BODY 13) 4.5 3.0 Tool Change to GRIPPER 14) 4.0 2.5 Move Assembly REMOVE-STOCK-MATERIAL 15) 4.0 2.5 Move Assembly CAR-BODY-TO-BUFFER 16) 5.0 5.0 Reclamp GET-WHEEL-CLAMP 17) 4.5 3.0 Fetch & Fixture UNFINISHED-WHEELl 18) 4.5 3.0 Tool Change to 1/4-INCH-DRILL 19) 2.0 2.0 Drill Hole 1/4-INCH-HOLE-IN-WHEEL1 20) 4.5 3.0 Tool Change to GRIPPER 21) 4.0 2.5 Move Assembly WHEELl-TO-BUFFER 22) 5.0 5.0 Reclamp GET-CAR-BODY-CLAMP 23) 4 5 3.0 Fetch & Fixture CAR-BODY 24) 4 5 3.0 Tool Change to 5/16—INCH~DRILL 2 0 2.0 Drill Hole 5/16-INCH-AXLE-HOLE 26) 27) 28) 29) 30) 31) 32) 33) 34) 35) 36) 37) 38) 39) 40) 41) 42) 43) 44) 45) 46) 47) 48) 49) 50) 51) 52) 53) 54) 55) 56) 57) 58) 59) 60) 61) 62) 63) 64) 65) 66) 67) 68) 69) 70) 71) 72) 73) 74) 75) 76)‘ 77) O O O O O O O O O O O O O O O O O OUIUIOOUIOU'IUIOOUIOUIU'IOOOUIOU'IUIOOU'ICU!0001001010001OOU‘IOUILDOOOUIOUIUIOOUI NtbubU'l-bthtbthU‘ltbbNtbthl-bebbNtbtb-U'ItbthNthltbthtbthltbthlobthtbobUltbbth-btbulbb wwwmwwmwwmmwmwwmwawwwmmwwwmwwwwwmmwmmwwwwmmmwmwwmmw OOOOUIOOOOOUlOOOOOUIUIOOOOOU‘IOOOOUIOOOOOUIOOUIOOOOOUIUIOOOOOUIO 185 Tool Change to Move Assembly Reclamp Fetch & Fixture Tool Change to Make Cut Tool Change to Move Assembly Move Assembly Reclamp Fetch & Fixture Tool Change to Make Cut Tool Change to Move Assembly Reclamp Tool Change to Move Assembly Reclamp Fetch & Fixture Tool Change to Drill Hole Tool Change to Move Assembly Reclamp Tool Change to Drill Hole Tool Change to Move Assembly Reclamp Fetch & Fixture Tool Change to Make Cut Tool Change to Move Assembly Move Assembly Reclamp Fetch & Fixture Tool Change to Make Cut Tool Change to Move Assembly Reclamp Fetch & Fixture Tool Change to Drill Hole Tool Change to Move Assembly Reclamp Fetch & Fixture Tool Change to Make Cut GRIPPER CAR-BODY-TO-BUFFER STOCK-FIXTURE 2-INCH-STOCK CIRCULAR-SAW 1/2INCH-WHEEL2 GRIPPER REMOVE-STOCK-MATERIAL WHEELZ-TO-BUFFER STOCK-FIXTURE 4X1-BOARD-STOCK CIRCULAR-SAW 4X1X4-BODY GRIPPER REMOVE-STOCK-MATERIAL CAR-TOP GRIPPER CAR-TOP-TO-BUFFER GET-WHEEL-CLAMP UNFINISHED-WHEELZ 1/4-INCH-DRILL l/4-INCH-HOLE-IN-WHEEL2 GRIPPER WHEELZ-TO-BUFFER CAR-BODY 5/16-INCH-DRILL 5/16-INCH-AXLE-HOLE GRIPPER CAR-BODY-TO-BUFFER STOCK-FIXTURE 2-INCH-STOCK CIRCULAR-SAW l/ZINCH-WHEEL GRIPPER REMOVE-STOCK-MATERIAL WHEEL3-TO-BUFFER STOCK-FIXTURE 1/4-INCH-STOCK CIRCULAR-SAW l/4-INCH-AXLE GRIPPER AXLEl-TO-BUFFER GET-WHEEL-CLAMP UNFINISHED-WHEEL3 1/4-INCH-DRILL l/4-INCH-HOLE-IN-WHEEL3 GRIPPER WHEEL3-TO-BUFFER STOCK-FIXTURE Z-INCH-STOCK CIRCULAR-SAW 1/2INCH-WHEEL3 186 GRIPPER REMOVE-STOCK-MATERIAL WHEEL3-TO-BUFFER STOCK-FIXTURE 1/4-INCH-STOCK CIRCULAR-SAW 1/4-INCH-AXLE2 GRIPPER AXLEZ-TO-BUFFER GET-WHEEL*CLAMP UNFINISHED-WHEEL 1/4-INCH-DRILL 1/4-INCH-HOLE-IN-WHEEL GRIPPER WHEEL-TO-BUFFER WHEEL-FIXTURE WHEELl AXLEl-BY-FORCE-FIT AXLE-WHEEL-TO-BUFFER CAR-BODY-FIXTURE CAR-BODY CAR-TOP BODY-TOP-TO-BUFFER WHEEL-FIXTURE WHEEL3 AXLEZ-BY-FORCE-FIT AXLE-WHEEL-TO-BUFFER CAR-BODY-FIXTURE CAR-BODY AXLEl-WHEELI WHEELZ-BY-FORCE-FIT AXLEZ-WHEEL3 WHEEL4-BY-FORCE-FIT MOVE-OUT-FINAL-ASSEMBLY 78) 4.5 3.0 Tool Change to 79) 4.0 2.5 Move Assembly 80) 4.0 2.5 Move Assembly 81) 5.0 5.0 Reclamp 82) 4.5 3.0 Fetch & Fixture 83) 4.5 3.0 Tool Change to 84) 2.0 2.0 Make Cut 85) 4.5 3.0 Tool Change to 86) 4.0 2.5 Move Assembly 87) 5.0 5.0 Reclamp 88) 4.5 3.0 Fetch & Fixture 89) 4.5 3.0 Tool Change to 90) 2.0 2 0 Drill Hole 91) 4.5 3 0 Tool Change to 92) 4.0 2.5 Move Assembly 93) 5.0 5.0 Reclamp 94) 4.5 3.0 Fetch & Fixture 95) 5.0 3.5 Fetch & Assemble 96) 4.0 2.5 Move Assembly 97) 5.0 5.0 Reclamp 98) 4.5 3.0 Fetch & Fixture 99) 5.0 3.5 Fetch & Assemble 100) 4.0 2.5 Move Assembly 101) 5.0 5.0 Reclamp 102) 4.5 3.0 Fetch & Fixture 103) 5.0 3.5 Fetch & Assemble 104) 4.0 2.5 Move Assembly 105) 5.0 5.0 Reclamp 106) 4.5 3.0 Fetch & Fixture 107) 5.0 3.5 Fetch & Assemble 108) 5.0 3.5 Fetch & Assemble 109) 5.0 3.5 Fetch & Assemble 110) 5.0 3.5 Fetch & Assemble 111) 4.0 2.5 Move Assembly 465.5 348 5 Total assembly times 187 Block with 6 Holes - Two Process Plans Several machining and assembly sequences are given for the creation of a block with 6 holes in it (similar to the block shown in Figure 2-10). Both of the process plans were derived by hand to show that the inefiicient plan b2 requires over 100% more time to complete than does the efficient plan bl. Efficient Process Plan b1 for the Block Derived by Hand Time Cost for Plan Process/Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER - 2) 5.0 5.0 Reclamp INITIAL-FIXTURE 3) 5.0 3.5 Fetch & Assemble BLOCK 4) 4.5 3.0 Tool Change to 1/2DRILL 5) 2.0 2.0 Drill Hole HOLE-1 is 6) 2.0 2.0 Drill Hole HOLE-2 7) 2.0 2.0 Drill Hole HOLE-3 8) 4.5 3.0 Tool Change to GRIPPER 9) 5.0 5.0 Reclamp BLOCK 10) 4.5 3.0 Tool Change to 1/2DRILL 11) 2.0 2.0 Drill Hole HOLE-4 12) 2.0 2.0 Drill Hole HOLE-5 13) 2.0 2.0 Drill Hole HOLE-6 14) 4.5 3.0 Tool Change to GRIPPER 15) 4.0 2.5 Move Assembly REMOVE-FINISHED-BLOCK 53.5 43 0 Total assembly times 188 Bad Process Plan b2 for the Block Derived by Hand Time Cost for Plan Process/Assembly with Robot Arm Speeds Operation of 1.0 and 2.0 ft/sec Description 1) 4.5 3.0 Tool Change to GRIPPER 2) 5. O 5. O Reclamp INITIAL-FIXTURE 3) 5.0 3.5 Fetch & Assemble BLOCK 4) 4.5 3.0 Tool Change to l/2DRILL 5) 2.0 2.0 Drill Hole HOLE-1 6) 4.5 3.0 Tool Change to GRIPPER 7) 5.0 5.0 Reclamp BLOCK 8) 4.5 3.0 Tool Change to l/2DRILL 9) 2.0 2.0 Drill Hole HOLE~4 10) 4.5 3.0 Tool Change to GRIPPER 11) 5.0 5.0 Reclamp BLOCK 12) 4.5 3.0 Tool Change to 1/2DRILL 13) 2.0 2.0 Drill Hole HOLE-2 14) 4.5 3.0 Tool Change to GRIPPER 15) 5.0 5.0 Reclamp BLOCK 16) 4.5 3.0 Tool Change to 1/2DRILL 17) 2.0 2.0 Drill Hole HOLE-5 18) 4.5 3.0 Tool Change to GRIPPER 19) 5.0 5.0 Reclamp BLOCK 20) 4.5 3.0 Tool Change to 1/2DRILL 21) 2.0 2.0 Drill Hole HOLE-3 22) 4.5 3.0 Tool Change to GRIPPER 23) 5.0 5.0 Reclamp BLOCK 24) 4.5 3.0 Tool Change to 1/2DRILL 25) 2.0 2.0 Drill Hole HOLE-6 26) 4.5 3.0 Tool Change to GRIPPER 27) 4 . 0 2 . 5 Move Assembly REMOVE-FINISHED-BLOCK 109.5 87 0 Total assembly times Appendix III: Comparison of the Oracle? to Enumeration Table A-1 shows run time data for examples processed by the first version of the Oracle algorithm as described in [Mi189b, Mil90a]. The Oracle algorithm was coded in Common Lisp and the run times are for a Sun 4/330 running Unix. The enumeration algorithm is a modified topo-sort algorithm that uses backtracking to find every valid ord- ering of the tasks. Any enumeration algorithm will require at least time proportional to the number of orderings possible. The run times for enumeration are roughly propor- tional to the total number of orders and are dramatically higher than the Oracle run times. Table A-1: The Oracle vs. Enumeration for Selected Example Graphs Data No. tasks, No. of Oracle? Enumeration set constraints ordersi: run time run time Morning ex 8 , 5 1120 4.9 msec 495 msec Desk Lamp 8 , 6 336 5.3 msec 180 msec Toy Car 12 , 11 99792 7.4 msec 62100 msec Door Lock 14 , 15 308880 10.7 msec 231000 msec Strainer 31 , 30 7.5 x 10” 63.9 msec intractable t The Oracle Algorithm calculated the exact number of orders possible for every example in this table. The Oracle was also tested on several structured synthetic data sets. Some of these results are shown in Tables A-2 and A-3 [Mil89b]. Table A-2 shows the results for tasks without any precedence constraints. These trivial cases have a total of N factorial different orderings as the Oracle correctly determined. Any enumeration algorithm would have an exponential time complexity for this type of problem so no enumeration algo- rithm run times are given. The results in Table A-1 and Table A-2 combined show that for even a modest number of loosely constrained tasks performing the enumeration of all TAlthoughthetablespresentedinthisappendixwerederivedusingthefirstversionofthe Oracle algorithm (described in [Mil89b, Mil90a]), the behavior of both versions of the Oracle algorithm is similar, so all the conclusions in this appendix hold for the current version of the Oracle algorithm as well. 189 190 sequences is impractical. Table A-2: The Oracle vs. Enumeration of Unconstrained Tasks No. of No. of No. of No. of Oracle? vertices tasks constraints ordersi: run time 5 5 0 120 4.5 msec 10 10 O 3.6 million 9.4 msec 15 15 o 1.3 x 1012 18.7 msec 20 20 o 2.4 x 1018 37.8 msec 4o 40 o 8.2 x 10“7 77.3 msec Table A-3 shows the results of the Oracle algorithm on seven different graphs con- taining nested simple folds. The first graph in the table consists of two vertices in paral- lel, each with the same parent and child (a single simple fold). The graphs 2 through 9 were created by randomly replacing edges in the previous graph by two vertices in paral- lel to create a nested simple fold. Table A-3 demonstrates that the first version of the Oracle algorithm works in low order polynomial time for simple fold graphs. Table A-3: The Oracle vs. Enumeration of Nested Simple Fold Graphs Data N = No. M = No. of Total number Oracle'l' set of tasks constraints of orders: run time 1st 4 4 2 3.2 msec 2nd 6 7 8 4.7 msec 3rd 8 10 48 7.2 msec 4th 14 19 96768 14.8 msec 5th 28 40 1.0 x 1015 38.5 msec 9th 168 250 2.9 x 16““ 520.0 msec 1’ The first version of the Oracle algorithm was used for these tables [Mil90a]. Enumeration run times are not given since they would be proportional to the number of different task orderings. t The Oracle Algorithm calculated the exact number of orders possible for each table entry. Bibliography [Aho72] [Aho74] [Akag80] [Alte86] [Arda87] [Atki86] [Bere86] [Berr84] [Boer88] Bibliography A. V. Aho, M. R. Garey, and J. D. Ullman, The Transitive Reduction of a Directed Graph, Siam I. Computing, Vol. 1, No. 2, June 1972, pages 131- 137. Alfred Aho, John Hopcroft, Jefl‘rey Ulrnan, The Design and Analysis of Com- puter Algorithms, Addison-Wesley, Reading, Massachusetts, 1974, 470 pages. Fumio Akagi, Hirokazu Osaki, Susumu Kikuchi, The Method of Analysis of Assembly Work Based on the Fastener Method, Bulletin of the JSME, Vol. 23, No. 184, October 1980, pages 1670-1675. Richard Alterman, An Adaptive Planner, 5th National Conference on Artificial Intelligence (AAAI-86), Philadelphia, Pennsylvania, August 11-15 1986, pages 65-69. David Ardayflo, Donling Jing, Matthew Hays, Prototype Expert Systems for Engineering Design and Manufacturing Automation, Proc. SAE/ESD Com- puter Graphics 1987, SAE/ESD, April 7-9 1987 Cobo Hall Detroit, pages 207-222. M. D. Atkinson, H. W. Chang, Extensions of Partial Orders of Bounded Width, Congressus Numerantium, Vol. 52, 1986, pages 21-35. Hamid Berenji, Behrokh Khoshnevis, Use of Artificial Intelligence in Automated Process Planning, Computers in Mechanical Engineering, Sep- tember 1986, pages 47-55. Gayle L. Berry, Computer-Aided Production Engineering the Integration of CAPP, Engineering and Manufacturing, Proceedings of Autofact #6, Anaheim, California, October 1-4 1984, pages 14—1 to 14-9. J. Boerrna, H. Kals, FIXES, a System for Automatic Selection of Set-Ups and Design of Fixtures, Annals of the CIRP, Vol. 37, No. 1, 1988, pages 443-446. 191 [Boot82] [Bour84] [Brdy87] [Brod87] [Brow82] [Cama87] [Chan85] [Chan89] [Crow84] [DeF387] [Desc81] [Dixo86] 192 Geofl'rey Boothroyd, Corrado Poli, and Laurence E. Murch, Automatic Assembly, Marcel Kekker, Inc., New York, 1982, 378 pages. A. Bourjault, Contribution a une Approche Methodologique de I’Assembly Automatise: Elaboration Automatigique des Sequences Operatoires, PhD Thesis, University of Franche-Comte, November 1984. Herb Brody, CAD Meets CAM, High Technology, May 1987, pages 12-18. Steven Brodd, A Strategy Planner for NASA Robotics Applications, (Workshop) on Spatial Reasoning and Multi-Sensor Fusion, Goddard Space Flight Center, Lanham MI), October 1987, 13 pages. Christopher Brown, PADL-Z: A Technical Summary, IEEE Computer Graph- ics and Applications, Vol. 2, No. 2, March 1982, pages 69-84. L. Camarinha-Matos, Plan Generation in Robotics, Robotics, Vol. 3, No. 3 & 4, September-December 1987, pages 291-328. Tien-Chien Chang, Richard A. Wysk, An Introduction to Automated Process Planning Systems, Prentice-Hall, Inc., Englewood Clifi‘s, New Jersey, 1985, 230 pages. Kuo-Chu Chang, Robert Fun g, Node Aggregation for Distributed Inference in Bayesian Networks, IJCAI-89 Eleventh International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publishers, Inc., Detroit Michigan, August 20-25 1989, Vol. 1, pages 265-270. James Crowley, A Computational Paradigm for Three Dimensional Scene Analysis, Technical Report from the Robotics Institute, CMU, No. CMU- RI-TR-84-11, April 1984, 18 pages. T. De Fazio, D. Whitney, Simplified Generation of All Mechanical Assembly Sequences, IEEE Journal of Robotics and Automation, December 1987, Vol. 3, pages 640—658. Yannick Descotte, Jean-Claude Latombe, GAR]: A Problem Solver that Plans How to Machine Mechanical Parts, Proceedings of the Seventh Inter- national Joint Conference on Artificial Intelligence, August 24-28 1981, Vol. 2, pages 766-772. John Dixon, Artificial Intelligence and Design: A Mechanical Engineering View, 5th National Conference on Artificial Intelligence (AAAI-86), Phi- ladelphia, Pennsylvania, August 11-15 1986, pages 872-877. [Dona87] [E03186] [Fers86] [Fox85] [Gare79] [Groo80] [Groo83] [Habi87] [Hara69] [Hera87] [Hof89a] 193 Bruce R. Donald, A Search Algorithm for Motion Planning with Six Degrees of Freedom, Artificial Intelligence, Vol. 31, 1987, pages 295-353. Paul Englert, Paul K. Wright, Applications of Artificial Intelligence and the Design of Fixtures for Automated Manufacturing, IEEE Proceedings of the International Conference on Robotics and Automation, April 7- 10 1986, Vol. 1, pages 345-351. F. Ferstenberg, K. K. Wang, J. Muckstadt, Automatic Generation of Optim- ized 3-Axis NC Programs Using Boundary Files, IEEE Proceedings of the International Conference on Robotics and Automation, April 7-10 1986, Vol. 1, pages 325-332. B. R. Fox, K. G. Kempf, Opportunistic Scheduling for Robotic Assembly, IEEE International Conference on Robotics and Automation, IEEE Com- puter Society, 1985, pages 880-889. Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, WH. Freeman and Company, New York, 1979, 340 pages. Mikell Groover, Automation, Production Systems, and Computer-Aided Manufacturing, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1980, 601 pages. Mikell P. Groover, Fundamental Operations, IEEE Spectrum, Vol. 20, No. 5, May 1983, pages 65-69. M. Habib, R. H. Mohring, On some Complexity Properties of N-Free Posets and Posets with Bounded Decomposition Diameter, Discrete Mathematics, Vol. 63, 1987, pages 157-182. Frank Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969, 274 pages. Sunderesh Heragu, Andrew Kusiak, Analysis of Expert Systems in Manufac- turing Design, IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-17, No. 6, November/December 1987, pages 898-912. Richard L. Hoffman, Automated Assembly in a CSG Domain, IEEE Intema- tional Conference on Robotics and Automation Conference, Scottsdale Arizona, May 14-18 1989, Vol. 1, pages 210-215. [Hof89b] [Hof90a] [Hof90b] [Home86] [Home89] [Home90] [Horo76] [Horo89] [Huan89] [I-Iuan90] [Hutc90] [Kak86] 194 Richard L. Hofiman, Assembly Planning for CSG Objects, Technical Report #NRTC-8916, Northrop Research and Technology Center, May 1989. Richard L. Hoffman, Assembly Planning for B-Rep Objects, Proceedings of the 2nd International Conference on Computer Integrated Manufacturing, Rensselaer Polytechnic Institute, Troy NY, May 21-23 1990, pages 314-321. Richard L. Hoffman, Automated Assembly Planning for B-rep Products, To appear: IEEE International Conference on Systems Engineering, Pittsburgh PA, August 9-11 1990. Luiz Homem-de-Mello, Arthur C. Sanderson, AND I OR Graph Representa- tion of Assembly Plans, CMU Report, No. CMU-RI-TR-86-8, Camegie- Mellon University, Pittsburgh, Pennsylvania, April 1986, 18 pages. L. S. Homem de Mello, Task Sequence Planning for Robotic Assembly Car- negie Mellon University Ph.D. Thesis, May 1989, 212 pages. L.S. Homem de Mello, A. C. Sanderson, Evaluation and Selection of Assem- bly Plans IEEE International Conference on Robotics and Automation, Cin- cinnati, Ohio, May 13-18 1990, Vol. 3, pages 1588-1593. Ellis Horowitz, Sartaj Sahni, Fundamentals of Data Structures, Computer Science Press, Inc., Woodland Hills, California, 197 6, 564 pages. Ellis Horowitz, Sartaj Sahni, Fundamentals of Computer Algorithms, Com- puter Science Press, Rockville, Maryland, 1989, 626 pages. Y. F. Huang, C.S.G. Lee, Precedence Knowledge in Feature Mating Opera- tion Assembly Planning, IEEE International Conference on Robotics and Automation, Scottsdale, Arizona, May 14-18 1989, Vol. 1, pages 216-221. Y. F. Huang, C. S. G. lee, An Automatic Assembly Planning System IEEE International Conference on Robotics and Automation Cincinnati Ohio, May 13-18 1990, pages 1594-1599. Seth A. Hutchinson, Avinash C. Kak, Spar: A Planner that Satisfies Opera- tional and Geometric Goals in Uncertain Environments, AI Magazine, Vol. 11, No. 1, Spring 1990, pages 30-61. A. Kak, K. Boyer, C. Chen, R. Safranek, and H. Yang, A Knowledge-Based Robotic Assembly Cell, IEEE Expert, Spring, 1986, pages 63-83. [Kemp87] [K087] [Kuth83] [Laug86] [Licb77] [Lind83] [Loza76] [Maki88] [Mats82] [McLe83] [Mill88] [Mil89a] 195 Alfons Kemper, Mechtild Wallrath, An Analysis of Geometric Modeling in Database Systems, ACM Computing Surveys, Vol. 19, No. 1, March 1987, pages 47-91. Heedong Ko, Kunwoo lee, Automatic Assembling Procedure Generation from Mating Conditions, Computer-Aided Design, Vol. 19, No. 1, January- February 1987, pages 3-10. Mike Kutcher, Eli Gorin, Moving Data, not Paper, Enhances Productivity, IEEE Spectrum, Vol. 20, No. 5, May 1983, pages 40-43. C. Laugier, P. Theveneau, Planning Sensor-Based Motions for Part-Mating Using Geometric Reasoning Techniques, Proc. 7th European Conf. on Artificial Intelligence, July 1986, pages 494-506. L. Lieberman, M. A. Wesley, AUTOPASS: An Automatic Programming Sys- tem for Computer Controlled Mechanical Assembly, IBM Journal Research and Development, July 1977, pages 321-333. Roy Lindberg, Processes and Materials of Manufacture, Allyn and Bacon, Inc., Boston, 1988, 849 pages. T. Lozano-Perez, The Design of a Mechanical Assembly System, M.I.T. Artificial Intell. Lab., Rep. TR-397, December 1976. Hiroshi Makino, Nobuyuki Fujita, Assembly of Blocks by Autonomous Assembly Robot with Intelligence (ARI), Annals of the CIRP, Vol. 37, No. 1, Tokyo, Japan, August 22-27 1988, pages 33-36. K. Matsushima, N. Okada, T. Sata, The Integration of CAD and CAM by Application of Artificial Intelligence Techniques, CIRP Annals, Vol. 31]], 1982, pages 329-332. Charles McLean, Mary Mitchell, Edward Barkrneyer, A Computer Architec- ture for Small-Batch Manufacturing IEEE Spectrum, Vol. 20, No. 5, May 1983, pages 59-64. Joseph M. Miller, WoodMaster: A Process Planner for Wooden Objects Made up of Block and Cylindrical Components, Case Center Technical Report, April 1988, 65 pages. Joseph M. Miller, Richard L. Hoffman, Automatic Assembly Planning with Fasteners, IEEE International Conference on Robotics and Automation Conference, Scottsdale Arizona, May 14—18 1989, Vol. 1, pages 69-74. [Mil89b] [W908] [Mil90b] [Myru33] [NaCh85] [Nau86] [Nevi89] [Nils80] [Palm87] [Phil85] [P099901 196 On the Number of Linear Extensions in a Precedence Graph, Joseph M. Miller, George C. Stockrnan, Michigan State University, Department of Computer Science, Technical Report #PRIP-89-7, 62 pages. Joseph Miller, George Stockrnan, On the Number of Linear Extensions in a Precedence Graph, IEEE International Conference on Robotics and Auto- mation, Cincinnati Ohio, May 13-18 1990, pages 2136-2141. Joseph M. Miller, George C. Stockrnan, Precedence Constraints and Tasks: How Many Task Orderings, To appear in IEEE International Conference on Systems Engineering, Pittsburgh Pennsylvania, August 9-11 1990, pages 408-41 1. M. Myrup Andreasen, S. Kahler, T. Lund, Design for Assembly, IFS (Publi- cations) Ltd. and Springer-Verlag, Berlin, New York, 1983, 189 pages. Dana Nau, Tien-Chien Chang, Hierarchical Representation of Problem- Solving Knowledge in a Frame-Based Process Planning System, Production Engineering Conference at ASME Winter Annual Meeting, November 1985, Miami Beach, pages 65-71. Dana Nau, Michael Gray, Hierarchical Knowledge Clustering: A New Representation for Problem Solving Knowledge, 5th National Conference on Artificial Intelligence (AAAI-86), March 1986, 8 pages. James L. Nevins, Daniel E. Whitney, editors, Concurrent Design of Products & Processes, McGraw-Hill, New York, 1989, 538 pages. Nils Nilson, Principles of AI, Book chapters 7 and 8, Tioga Publishing Co. Palo Alto CA, Palo Alto CA, 1980, pages 275-357. Richard Stuart Palmer, Computational Complexity of Motion and Stability of Polygons, Cornell University Ph.D. Thesis, UMI Dissertation Service, 1987, 128 pages. R. Phillips, C. Mouleeswaran, A K nowledge-Based Approach to Generative Process Planning, AUTOFACT, November 6 1985, pages 10-1 - 10-15. Robin J. Popplestone, Yanzi Liu, Rich Weiss, A Group Theoretic Approach to Assembly Planning, AI Magazine, Vol. 11, No. 1, Spring 1990, pages 82- 97. [Requ80] [M082] [Reym87] [Rich83] [Rich86] [Riva84] [Rych88] [Sand90] [Scha77] [Seda87] [SekiS8] [Shar86] [Stan86] 197 Aristides Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, Computing Surveys, Vol. 12, No. 4, December 1980, pages 437- 464. A. Requicha, H. B. Voelcker, Solid Modeling: A Historical Summary and Contemporary Assessment, IEEE Computer Graphics and Applications, IEEE, March 1982, pages 9-24. G. Reyman, Design of Assembly Systems, The International Journal of Advanced Manufacturing Technology, Vol. 2, No. 3, August 1987, pages 13-21. Elaine Rich, Artificial Intelligence, McGraw-Hill, New York, 1983, 436 pages. John Richardson, Implementing an Expert System for Process Planning, Society of Manufacturing Engineers Conference, March 1986, Paper No. 860339, pages 43-50. Ivan Rival, Linear Extensions of Finite Ordered Sets, Annals of Discrete Mathematics, V0123 1984, pages 355-370. Michael D. Rychener, editor, Expert Systems for Engineering Design, Academic Press, Inc., 1988, 306 pages. Arthur C. Sanderson, Luiz S. Homem de Mello, Hui Zhang, Assembly Sequence Planning, AI Magazine, Vol. 11, No. 1, Spring 1990, pages 62-81. Roger Shank, Robert Abelson, Scripts, Plans, Goals and Understanding, Lawrence Erlbaum, Hillsdale, N.J., 1977. S. Sedas, S. Talukdar, A Disassembly Planner for Redesign, Tech. Rep. EDRC-05-16-87, Engineering Design Research Center, Carnegie Mellon University, May 1987, 6 pages. Yukiko Sekine, John J. Mills, Generation of Assembly Sequences in Assem- bly Process Planning, AAAI-88 Workshop on Manufacturing Planning and Scheduling, St. Paul, August 1988, 4 pages. Micha Sharir, Amir Schorr, On Shortest Paths in Polyhedral Spaces, Siam J. Computing, Vol. 15, No. 1, February 1986, pages 193-215. Richard P. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole, Monterey, CA, Vol. 1, 1986, 306 pages. [Ste81a] [Ste81b] [Take83] [T11084] [Tsat87] [Well72] [Whit88] [Wins84] [Wink90] [Wolt89] 198 Mark Stefik, Planning with Constraints, (MOLGEN: Part I ), Artificial Intel- ligence, North-Holland Publishing Company, Vol. 16, No. 2, 1981, pages 1 1 1-139. Mark Stefik, Planning and Meta-Planning (MOLGEN: Part 2), Artificial Intelligence (An International Journal), North-Holland Publishing Company, Vol. 16, No. 2, 1981, pages 141-169. H. Takeyama, H. Sekiguchi, T. Kojirna, K. Inoue, T. Honda, Study on Automatic Determination of Assembly Sequence, Annals of the CIRP, Harro- gate, England, Vol. 32, No. 1, August 22-27 1983, pages 371-374. Robert Tilove, Vadim Shapiro, Mary S. Pickett, Modeling and Analysis of Robot Work Cells in Roboteach, GM Research Publication, No. GMR-4661, GM, March 27 1984, 33 pages. Costas Tsatsoulis, R. Kashyap, Using Dynamic Memory Structures in Plan- ning and its Application to Manufacturing, Technical Report, Purdue Engineering Research Center for IMS, No. TR-ERC 87-9, West Lafayette, Indiana 47907, July 1987, 157 pages. Mark B. Wells, Elements of Combinatorial Computing, Pergamon Press, New York, 1971, 258 pages. Daniel Whitney, Thomas De Fazio, Richard Gustavson, Stephen Graves, Kurt Cooprider, Charles Klein, Mancheung Lui, Suguna Pappu, Computer Aided Design of Flexible Assembly Systems: Final Report, Charles Stark Draper Laboratory Technical Report No. CDSL-R-2033, January 1988, 100 pages. Patrick Winston, Artificial Intelligence, Addison-Wesley, Reading Mas- sachusetts, 1984, 524 pages. Peter Winkler, Graham Brightwell, Counting Linear Extensions Is #P- Complete, DIMACS Technical Report 90-49, Rutgers University, July 1990, 18 pages. Jan Wolter, On the Automatic Generation of Assembly Plans, IEEE Intema- tional Conference on Robotics and Automation Conference, Scottsdale Arizona, May 14-18 1989, Vol. 1, pages 62-68. [Wolt90] [Woo87] [Wu86] [Yama87] 199 Jan Wolter, A Survey of Enumerative Data Structures for Assembly Planning, Technical Report 90-006, Computer Science Department, Texas A&M University, March 1990, 32 pages. Tony Woo, Automatic Disassembly, Proc. SAE/ESD Computer Graphics 1987, SAE/ESD, Cobo Hall Detroit, April 7-9 1987, pages 163-166. Ching-Farn Wu, Anthony S. Wojcik, Lionel M. Ni, CMOS Circuit Represen- tation, Verification and Synthesis Using Automated Reasoning, MSU Techni- cal Report, No. MSU-ENGR-86-022, MSU, November 19 1986. 57 pages. Seiji Yamada, Norihiro Abe, Saburo Tsuji, Construction of a Consulting Sys- tem from Structural Description of a Mechanical Object, IEEE International Conference on Robotics and Automation, March 1987, pages 1413-1418.