Automatic assembly task assignment for a multirobot environment

AUTOMATIC ASSEMBLY TASK ASSIGNMENT FOR A MULTIROBOT ENVIRONMENT C. Del Valle* and E.F. Camacho** *Depa amen o de Lenguajes y Sis emas In o má icos, Uni e sidad de Se illa, 41012 Se illa, Spain ([email p o ec ed]) **Depa amen o de Ingenie ía de Sis emas y Au omá ica, Uni e sidad de Se illa, 4/012 Se illa, Spain Abs ac : This pape p esen s an algo i hm A• o ob aining he "bes " assembly plan o a p oduc in a mul i obo sys em. Toe algo i hm akes in o accoun , in addi ion o he assembly imes, he imes needed o change ools in he obo s. Toe objec i e o he plan is he minimiza ion o he makespan. To mee his objec i e, he algo i hm s a s om he And/O g aph (comp essed ep esen a ion o all easible assembly plans) and he in o ma ion on each assembly ask ( obo and ool needed, and assembly ime). Keywo ds: Flexible manu ac u ing sys ems; assembly obo s; indus ial obo s; a i icial in elligence; op imiza ion p oblems; scheduling algo i hms 1. INTRODUCTION Au oma ic assembly is one o he a eas o manu ac u ing ha has no been ully de eloped in indus y. This is mainly because obo con ol and o -line p og amming ha e no e ol ed as expec ed (Ma ensson, 1990), as esul o he ac ha he assembly p ocess is much mo e complex han p ocesses in o he obo ic applica ions and pa s manu ac u ing. The e o e, un il ecen ly, indus ial obo s we e used p ima ily in simple assembly applica ions. This si ua ion is changing, howe e , and Flexible Assembly Sys ems ha e become a e y impo an issue because o he need o p oduce small lo s o p oduc s, bu he deg ee o lexibili y is s ill low (Boneschansche , 1993). The e a e di e en s ages in he whole p ocess o assembly, such as design o p oduc s and pa s, design o ix u es, g asp selec ion, pa h planning, ine-mo ion planning, senso in eg a ion, e c. One o he mos impo an issues in he whole p ocess is planning assembly asks, whose op imali y will ha e a signi ican e ec on he inal cos o he assembled p oduc (Kusiak, 1990). Toe assembly planning p oblem in ol es he iden i ica ion, selec ion and sequencing o assembly ope a ions, s a ed as hei e ec s on he pa s. Toe iden i ica ion o assembly ope a ions usually leads o he se o all easible assembly plans. The numbe o hem g ows expo nen ially wi h he numbe o pa s, and depends on o he ac o s, such as how he single pa s a e in e  connec ed in he whole assembly, i.e. he s uc u e o he g aph o connec ions. In ac , his p oblem has been p o ed o be NP-comple e in bo h he wo dimensional (Ka aki and Koloun zakis, 1995) añ.d h ee-dimensional (Ka aki, e al., 1995; Wilson, e al., 1995) cases. Two di e en app oaches ha e been used in ob aining assembly plans. A i s , in e ac i e planne s que ied he use o geome ic- easoning in o ma ion (Bou  jaul , 1984; De Fazio and Whi ney, 1987). Mo e ecen ly, planne s wo k au oma ically om a geome  ic and ela ional model o he assembly (Home o de Mello and Sande son, 1991 b) and om a CAD model and o he non-geome ic in o ma ion (Ames, e al., 1995; Romney, e al. , 1995). Wi hin his scope, he ep esen a ion o assembly plans is an impo an issue. Toe use o And/O g aphs o his pu pose (Home o de Mello and Sande son, 1990, 1991a, b) is becoming one o he mos s anda d ways o ep esen ing all possible assembly plans. I can be ob ained by s udying he opposi e p oblem, ha o disassembly, bu main aining he cons ain s o assembly. Mos au oma  ic planne s wo k wi h his s a egy. The esul is a ep esen a ion which is adequa e o a goal-di ec ed app oach. Mo eo e , Home o de Mello and Sande son (1990) and Wol e (1992) showed ha his s uc u e is mo e e icien in mos cases han o he enume a i e ones. An op imum assembly plan is now sough , selec ed om he se o all easible assembly plans. A a ie y o c i e ia has been used o choosing an op ima! one. Fo example, Wol e (1988) combines he a ings ela ed o manipulabili y o subassemblies, ix u e complexi y, and he numbe o di e en . di ec ions om which ope a ions a e pe o med, o comple e a plan. C i e ia including he minimiza ion o eo ien a ion and ix u e equi emen s we e in oduced by De Fazio e al. (1990). Hen ioud (1989) p oposed he aid o an expe abou he ope a ional and logis ic complexi y, and s a egic ad an ages o selec he bes assembly ee (plan). Homem de Mello and Sande son ( 1990) p oposed assigning o he hype a cs o he And/O g aph weigh s ha depend on he complexi y o he assembly asks and on he s abili y o he in e media e sub-assemblies, and using gene ic sea ch algo i hms such as he AO* o ob ain he bes plan. Thei p oposal (1991c) o so ne op imiza ion c i e ia based on maximizing he numbe o di e en assembly sequences encompassed by he assembly plan, and on maximizing he amoun o pa allelism (simul anei y) possible in he execu ion o he assem bly asks, is used in a heu is ic sea ch algo i hm. In ano he way, an algo i hm is p oposed in (Holland, e al., 1992) o a speci ic assembly cell, and o ba ches o p oduc s. This pape p esen s an algo i hm A* (Nilsson, 1980; Pea l, 1984) o ob aining he "bes " assembly plan o a p oduc in a mul i obo sys em. The app oach used he e is ha o Home o de Mello and Sande son (1990; 1991c), bu mo e de ailed in o ma ion o he assembly asks is conside ed. The algo i hm akes in o accoun , in addi ion o he assembly imes, he imes needed o change ools in he obo s. Toe ob jec i e o he plan is he minimiza ion o he o al assembly ime (makespan). To mee his objec i e, he algo i hm s a s om he And/O g aph (com p essed ep esen a ion o all easible assembly plans) and he in o ma ion abou each assembly ask ( obo and ool needed and assembly ime). The pape is o ganized as ollows: Sec ion 2 de- sc ibes he p oblem o assembly- ask assignmen . Toe p oposed algo i hm is desc ibed in Sec ion 3, and so ne o he esul s ob ained a e p esen ed in Sec ion 4. So ne inal ema ks a e made in he concluding sec ion. 2. PROBLEM STATEMENT Toe p ocess o joining pa s oge he o o m a uni is known as assembly. The joining p ocess esul s in he connec ion o one pa wi h pa s al eady assem bled. A sub-assembly is a g oup o pa s ha ing he p ope y o being able o be assembled independen ly o o he pa s o he p oduc . An assembly plan is a se o assembly asks wi h o de ing amongs i s ele men s. Each ask consis s o joining a se o sub assemblies o gi e ise o an e e la ge sub-assem bly. An assembly sequence is an o de ed sequence o he assembly asks sa is ying all he o de ing con s ain s. Each assembly plan co esponds o one o mo e assembly sequences. An And/O g aph is a ep esen a ion o he se o all assembly plans possible o a p oduc . Toe O nades co espond o sub-assemblies, he op node co e sponds o he whole assembly, and he lea nodes co espond o he indi idual pa s. Each And nade co esponds o he assembly ask joining he sub assemblies o i s wo inal nodes p oducing he sub assembly o i s ini ial node. In he And/O g aph ep esen a ion o assembly plans, an And/O pa h whose op node is he And/O g aph op node and whose lea nades a e he And/O g aph lea nodes is associa ed o an assembly plan, and is e e ed o as an assembly ee. An impo an ad an age o his ep esen a ion, used in his wo k, is ha he And/O g aph shows he independence o assembly asks ha can be execu ed in pa allel. Figu e 1 shows an exam ple o his ep esen a ion. And nades a e omi ed. This wo k is cen e ed on he p oblem o choosing he bes assembly plan, ha is one o he And/O ees o he And/O g aph. The majo i y o app oaches used Fig. l. The And/O g aph o he p oduc ABCDE. up o now make his selec ion in a planning phase in which nei he he assembly sys em, no how he assembly asks wi hin i will be ma e ialized, is aken in o accoun . This wo k akes in o accoun he physical ealiza ion o he assembly. I is assumed ha he assembly asks co espondíng o he And/O g aph ha e been e alu a ed sepa a ely, in he sense o es ima ing he e sou ces necessa y o hei ealiza ion ( obo s, ools, ix u es ... ) as well as hei app oxima e du a ion imes. These imes should include an es ima ion o he imes needed o o he ope a ions, such as ans po a ion o pa s and subassemblies. Po an And/O g aph wi h a la ge numbe o nodes his is no an easy ask, and he help o a compu e -aided sys em is necessa y. Toe nodes co esponding o asks which a e no ealizable as he adequa e ools a e no a ail able a e elimina ed om he And/O g aph. Ano he ac aken in o accoun he e, is he ime necessa y o changing he ools in he obo s, which is o he same o de as he execu ion ime o he assembly asks and he e o e canno be dis ega ded as in Pa s manu ac u ing. Fu he mo e, he choice is no limí ed o he assembly plan, bu also speci ies when each ask is o be ca ied ou in o de o míni mize he makespan (so ne asks which could po en ially be ca ied ou in pa allel ha e o be delayed because hey need common esou ces). Toe algo i hm can be used in an o -line manne o ob aining an op imum ini ial solu ion o he assembly p ocess. Howe e , due on one hand o he lexibili y o modi ying he con e gence c i e ia o he algo i hm owa ds a no s ic ly op imum solu ion, and on he o he o he ac ha as he assembly p ocess ad ances he esul ing p oblem becomes smalle , he algo i hm could be applicable on-line o modi y ei he he plan o he ini ial sequence, in o de o co ec he a ia ions wi h espec o he ini ial solu ion. 3. ALGORITHM DESCRIPTION As has been s a ed p e iously, he algo i hm is cen e ed on he choice o an assembly plan o a com ple e p oduc in a mul iple- obo sys em, whe::e he esou ces necessa y o ca ying ou each ask ep e sen ed in he And/O g aph ( obo s, ools ... ) appea as da a, as well as he imes necessa y o hei exe cu ion. As well as he choice o assembly plan, he execu ion o de s o he asks in each obo a e speci ied by an analysis o hei execu ion in pa allel in he assembly sys em gi en. Because o he se -up o he And/O g aph, he as sembly p oblem can be s udied, s a ing om he inal si ua ion and going owa ds he ini ial one. Toe algo i hm has wo well-di e en ia ed pa s: one o hem s udies he sequen ial execu ion o assembly asks, and he o he sol es he pa allel execu ion o assembly asks ( he ep esen a ion h ough he And/O g aph allows a na u al s udy o his s age). This is ac ually he mos complex sec ion, because he execu ion o asks on one side o he global as sembly is no independen o he es , and can in lu ence he execu ion o asks in he o he pa o he assembly. Heu is ic unc ions based on he execu ion o asks aken only om he pa o he ee below he node, and he ime emaining o he use o ools and obo s (supposing he mínimum numbe o ool changes, in o de o main ain he algo i hm as A*) ha e been used in o de o expand he mínimum numbe o nodes and a oid edundan nodes. Because he e is un uppe limí o he makespan, he pa allel algo i hm does no need o inish when he bes expec ed cos is highe han ha limi . Toe algo i hm is used o -line o ob ain an op imum i s assembly plan. Howe e , as he assembly p o cess e ol es, i can be used on-line o co ec he changes which could ha e occu ed du ing he assem bly p ocess, by p uning he And/O g aph o he subassemblies al eady pe o med. Toe op imíza ion c i e ia can easily be changed, acco ding o he pa  icula needs o he applica ion. 3 .1. Sequen ial Execu ion o Tasks An algo i hm A· o sea ch o he global assembly plan can be implemen ed in he ollowing way. Be ginning wi h an ini ial node whose s a e ep esen s he comple e assembly ealiza ion, and he e o e co esponds o he oo node o he And/O g aph (comple e assembly), all i s possible successo s a e gene a ed, whose s a es will ep esen he execu ion a he end o he assembly p ocess o he asks co e sponding o he And nodes coming om he oo node o he And/O g aph. Two ypes o nodes may be gene a ed, depending on he des ina ion O nodes o each chosen And node. I a leas one o hese O nodes co esponds o an indi idual pa , he assembly p ocess will con inue o be sequen ial, and he node esul ing om he expan sion may be ea ed as he ini ial node, whe e he node co esponding o he non- i ial sub-assembly will ake he place o he oo node. I , on he o he hand, he applica ion o he ask s a s om wo sub-assemblies, each wi h a ious pa s, in he esul ing plan (o plans in gene al) he ask a angemen is no o ally speci ied ( a ious possible sequences exis o each assembly plan}, o asks may be ca ied ou in pa allel. The e is also an in e dependence amongs he sub-assemblies, because hey po en ially use he same se o esou ces. Toe ea men o his ype o node has he e o e o be unde aken in a di e en way om hose co espond ing o sequen ial ask execu ion, and his will connec wi h he second pa o his algo i hm. Toe e alua ion unc ion used o he nodes gene a ed in his pa is (n) = g(n) + h(n), (1) g(n) being he ime accumula ed in he execu ion o asks co esponding o he s a e o node n, including he delays in he necessa y ool changes, and h(n) being an op imis ic es ima ion o he emaining ime in which o comple e he global p ocess. (h(n) should be a lowe bound o he emaining ime o he algo i hm o be A·.) Due o he ac ha a ious di e en plans (and he e o e di e en ask se s which would comple e he assembly p ocess) may be eached om node n, a de ailed s udy would be compu a ionally cos ly, and he e o e h(n) = a(n) · min(pJ (2) has been chosen, a(n) being he numbe o asks necessa y o comple e he assembly plan, and p¡ he p ocessing ime o ask i. As can be seen, i is also impossible o de e mine he minimum numbe o ool changes wi hou a de ailed s udy, and he e o e when es ima ing h(n) i is assumed o be ze o. All he assembly ees ( ask p ecedence ees) a e ob ained o he "pa allel" nodes, and a e s udied sepa a ely. Toe unc ion h (n) co esponding o each ee is de ined in he ollowing subsec ion. 3.2. Pa allel Execu ion o Tasks Toe objec i e o his pa o he algo i hm is o de e  mine he o al minimum ime o he execu ion o he p ecedence ees ob ained in he p e ious sec ion. In o de o do his, an algo i hm A* is again used. Toe nodes o he expansion ee now p esen pa ial in o  ma ion abou he execu ion o he assembly p ocess. Conc e ely, a each expansion s ep only one assembly ask is in oduced, and i s p ocessing ime will a ec only one o he wo ks a ions, he same s a e being e ained by he o he wo ks a ions. Toe s a e co esponding o one node o he expansion ee is ep esen ed by using he asks a ailable o in oduc ion in he s a e o he nex s ep, e med "candida es", and hei ea lies s a ing imes, deno  ed es ( J. A he same ime, he las ool used is included o each obo , as well as he inal ime o use. Toe e alua ion unc ion o he nodes ob ained by his algo i hm is simila o (1), being now g(n) = he la ges o he ea lies s a ing imes o candida es(n) and he inal imes o he al eady inished in n wi hou successo s. h(n) = max(h¡(n),hi(n)) (3) h1 (n) =es ima ion o he ime emaining i he in e  dependencies be ween di e en b anches in he ee a e no aken in o accoun . I is looked a only in dep h. hi(n) =es ima ion o ime needed i only he e maining usage imes o he ools in each obo a e aken in o accoun , u he sup posing he numbe o ool changes o be a a minimum. Figu e 2 shows a ask p ecedence ee, di e en expansion nodes and in o ma ion abou hei co e sponding s a es. l is also accompanied by he Gan cha s. Toe heu is ic unc ion h¡(n) can be de ined as ol lows: h¡(n) =max ( hl(n,JJ - (n,JJ ) candida es(n) whe e (n,J) = g(n) -es (n,J) hJ(n,J) = h;'(J) + max ( (l,R;,las ool(RJ - obo s (es (n,J)-las _ ime(RJ), O) h;'(J) = p(J) + max ( h;'(JJ + (l;,R(J),T(J)) ). successo s o J (4) (5) (6) (7) In he abo e exp essions, n is an expansion node, J is an assembly ask, las _ ool(RJ and las _ ime(RJ a e he las ool used in obo R; and he ime o las use espec i ely, and (es (n,J)-las _ ime(RJ) is he exis  ing ime slack. R(J) and T(J) a e he obo and ool necessa y o he execu ion o ask J, and p(J) is i s p ocessing ime. (J,R, T) is he added delay, due o he ac ha he ool T is being used by obo R in ask J and successo s, because o he necessa y ool changes. No ice ha h¡(J) does no depend on he expansion nodes, and hus allows one o calcula e a lowe bound p io o using he A· algo i hm. ......... R1 T1 p•1 . . . . . . . . . . . p-4 . . . . R1 T2 ............ ' ........................ ' . . . . . . . . . . . . . . . . . . ' . . . . . . . . . . ' .... . . . . . . . . . . . . . . ' . . :R2T4 :p-2 J2 R1 T1 J5 p-5 ......... .... p-3 J6 ........... J1 • o J2 • O o R1 • -· 2 4 8 8 10 TIME R2- -· g . o J1 J1 J2 • O J3 • 1 J4 • 1 R1 • T1 • 1 R1 T1 R2. ····-· R2 g . 1 J4 J2 • 8 J3. 3 J6. 4 R1 • T1 -1 R2·T3-3 R1 g . R2 J2 J3. 11 J5 • 8 J6 • 4 R1 • T1 -1 R2 • T4 • 8 R1 T1 g . 11 R2 ... T4 T3 Fig. 2. A ask p ecedence ee, so ne expansion nodes, and hei co esponding Gan cha s. h2 can be de ined as ollows: hi(n) =max ( h;(n,RJ - (n,RJ ) obo s (8) whe e (n,RJ = g(n) -las _ ime(RJ (9) and hln,RJ is he minimum ime o use o obo R; wi hou conside ing he ask p ecedence cons ain s. Fi s simpli ica ion: Each ool is associa ed wi h only one obo . The calcula ion o hin,R) is equi alen o he a elling salesman p oblem, when conside ing he ools no ye used and an ini ial node co espond ing o he las -used ool in he obo R. h;(n,R) = L 1 (J'J + ool-change imes (10) T¡E T(R) wi h 1 (J'J he emaining ime o usage o ool T. Second simpli ica ion: Tool-changing imes do no depend on he ype o ool. hi(n) could be imp o ed by using he ea lies usable ime o R ins ead o using (n,RJ. No ice ha asks no included in n should be conside ed in his case. De ini ion: A ask ; is compa ible wi h [including] ask j i , on including his ask a he ollowing le e!, he s a o ; and ha o i s successo s in he ask p ecedence ee a e no delayed. This de ini ion allows he numbe o expanded nodes o be minimized. The candida es asks compa ible wi h ano he ask included in he nex le e! will be included in successi e le els. The expansion o a node is ca ied ou by he algo i hm shown in Fig. 3. No ice ha he algo i hm can be ex ended o he case whe e he e is mo e han one candida e ool o each assembly ask. A lis o candida e ools has o P ocedu e Expand(n) Le J = {11, ... ,JJ be he s o candida es(n) and EST = {es ,, ... ,es J i s ea lies s a ing imes. es _min = min(es J l he e is jus one ask l¡ wi h es ¡ = es _min lnclude in open a nade whose s a e is ha o n plus J, / he e a e asks no compa ible wi h l¡ Expand(n), es ided o l'= {Jm, wi h lm no compa ible wi h JJ endi else Le NTI, be he numbe o asks no compa ible wi h J,, and Nl1_min = min(Nl7¡), o es ¡=es _min lnclude in open a nade whose s a e is ha o n plus J,, wi h J, such ha Nl1=Nl1_min / NI1_min�O Expand(n), es ic ed o l'= {Jm , wi h Jm no compa ible wi h J J endi endi Fig. 3. Algo i hm o he expansion o nodes. be conside ed when expanding he nodes. A e y simple heu is ic unc ion consis ing o only conside  ing he assembly imes o he emaining asks could be used. A mo e in o med heu is ic unc ion would equi e a mo e complex algo i hm. 4. RESULTS Toe algo i hm has been es ed in a a ie y o si ua ions, conside ing di e en p oduc s uc u es (num be o pa s, numbe o connec ions be ween pa s), di e en ypes o And/O g aphs (numbe o sub assemblies, numbe o assembly asks o each sub assembly), and di e en assembly esou ces (numbe o obo s, numbe o ools). Toe solu ion ob ained o he assembly ask assign men o he lashligh shown in Fig. 4 (Homem de Mello and Sande son, 1990c) is shown in Fig. 5. Toe assembly en i onmen was composed o wo obo s and wo assembly ools pe obo . Toe o iginal com ple e And/O g aph con ains 35 And nodes, 24 O nodes and 37 possible assembly plans, and is no shown o he lack o space. Toe Gan cha s co e sponding o he solu ion a e shown in Fig. 6. 5. CONCLUSIONS An A· algo i hm o ob aining he op imum assembly plan o a mul i obo en i onmen has been p esen  ed. The algo i hm minimizes he makespan o he assembly. To apply he algo i hm, possible assembly asks should be speci ied by an And/O g aph. Toe algo i hm needs he de ini ion o he necessa y ools and an es ima ion o he ime equi ed o each assembly ope a ion. The algo i hm has been es ed wi h p oblems o di e se complexi y. 6. ACKNOWLEDGMENT The au ho s would like o acknowledge CICYT o unding he wo k. Toe au ho s would also like o ex end hei hanks o he anonymous e e ees o hei help ul sugges ions. 7. REFERENCES Ames, A.L., T.L. Cal on, R.E. Jones, S.G. Kau man, C.A. Laguna and R.H. Wilson (1995). Lessons Lea ned om a Second Gene  a ion Assembly Planning Sys em. P oc. 1995 IIINQ U!NS IUIJI IIEA.SCTOR BATTBIY END Fig. 4. P oduc example: a lashligh . 111 IIM. ao L E Fig. 5. T ee solu ion o he p oduc example ob ained om he And/O g aph. TASK CHANGE TASK TASK TASI< R1 31 TOOL 11 4 TASI< CIWIQE � R2 30 TOOL TIME Fig. 6. Gan cha s o he ee solu ion in a wo obo en i onmen . IEEE In l. Symp. on Assembly and Task Plan ning, pp. 41-47. Boneschansche , N. (1993). Plan Gene a ion o Flexible Assembly Sys ems. PhD hesis Del Uni e si y o Technology, Del , Toe Ne he  lands. Bou jaul , A. (1984). Con ibu ion a une App oche Mé hodologique de l'Assemblage Au oma isé: Elabo a ion Au oma ique des Séquences Opé a oi es. These d'é a , Uni e si é de F anche-Com é, Besaneon, F ance. De Fazio, T.L., T.E. Abell, G.P. Ambla d, O.E. Whi ney (1990). Compu e -aided assembly sequence edi ing and choice: Edi ing c i e ia, bases, ules, and echnique. P oc. IEEE In . Con . Sys . Eng., pp. 416-422. De Fazio, T.L. and O.E. Whi ney (1987). Simpli ied Gene a ion o All Mechanical Assembly Se- quences. IEEE J. Robo ics and Au oma ., Vol. 3, No. 6, pp. 640-658. Also, Co ec ions, Vol. 4, No. 6, pp. 705-708. Hen ioud, J.M. (1989). Con ibu ion a la concep ualisa ion de l'assemblage au oma isé: nou elle app oche en ue de dé e mina ion des p ocessus d'assemblage. These d'é a , Uni e si é de F anche-Com é, Besancon, F ance. Holland, W. an, N. Boneschansche and W.F. B ons oo (1992). Task Assignmen in a Flexi ble Assembly Cell Using And/O G aphs. P oc. 23 d /n . Symp. lnd. Robo s. Ba celona, Spain, Oc obe 6-8, pp. 653-658, 642. Homem de Mello, L.S. and A.C. Sande son (1990). And/O G aph Rep esen a ion o Assembly Plans. IEEE T ans. Robo ics Au oma . Vol. 6, No. 2, pp. 188-199. Homem de Mello, L.S. and A.C. Sande son (1991a). Rep esen a ions o Mechanical Assembly Se quences. IEEE T ans. Robo ics Au oma . Vol. 7, No. 2, pp. 211-227. Home o de Mello, L.S. and A.C. Sande son (1991b). A Co ec and Comple e Algo i hm o he Gene a ion o Mechanical Assembly Sequences. IEEE T ans. Robo ics Au oma . Vol. 7, No. 2, pp. 228-240. Home o de Mello, L.S. and A.C. Sande son (1991c). Two C i e ia o he Selec ion o Assembly Plans: Maximizing he Flexibili y o Sequencing he Assembly Tasks and Minimizing he Assem bly Time Th ough Pa allel Execu ion o Assem bly Tasks. /EEE T ans. Robo ics Au oma . Vol. 7, No. 5, pp. 626-633. Ka aki, L., J.C. La ombe and R.H. Wilson (1993). On he Complexi y o Assembly Pa i ioning. ln o ma ion P ocessing Le e s. Vol. 48, pp. 229-235. Ka aky, L. and M. Koloun zakis (1995). Pa i ion ing a plana assembly in o wo connec ed pa s is NP-comple e. ln o ma ionP ocessing Le e s. Vol. 55, pp. 156-165. Kusiak, A. (1990). ln elligen Manu ac u ing Sys ems. P en ice-Hall In e na ional Se ies in Indus ial and Sys ems Enginee ing. Ma ensson, N. (1990). Robo Abili y o he 90's. P oc. 21s ln . Symp. lnd. Robo s. Copenhagen, Denma k, Oc obe 23-25, 1990, pp. 193-198. Nilsson, N.J. (1980). P incipies o/ A i icial ln elli gence. Chenanso Fo ks, NY: Tioga. Pea l, J. (1984). Heu is ics: In elligen Sea ch S a e gies o Compu e P oblem Sol ing. Reading, MA, Addison-Wesley. Romney, B., C. Goda d, M. Goldwasse , G. Ramkuma (1995). An E icien Sys em o Geome ic Assembly Sequence Gene a ion and E alua ion. P oc. 1995 ASME In ema ional Compu e s in Enginee ing Con e ence, pp. 699- 712. Wilson, R.H., L. Ka aki, T. Lozano-Pé ez and J.C. La ombe (1995). Two-Handed Assembly Se quencing. ln ema ional Joumal o/ Robo ic Resea ch. Vol. 14, pp. 335-350. Wol e , J. (1988). On he au oma ic gene a ion o/ plans o mechanical assembly. Ph.D. hesis. Uni . o Michigan. Depa men o Compu e , In o ma ion and Con ol Enginee ing, Sep em be 1988. Wol e , J. (1992). A Combina o ial Analysis o Enume a i e Da a S uc u es o Assembly Planning. Joumal o/Design and Manu ac u ing. Vol. 2, No. 2, June 1992, pp. 93-104.