© Strojni{ki vestnik 49(2003)1,5-15 © Journal of Mechanical Engineering 49(2003)1,5-15 ISSN 0039-2480 ISSN 0039-2480 UDK 658.515:007.52:519.65 UDC 658.515:007.52:519.65 Izvirni znanstveni ~lanek (1.01) Original scientific paper (1.01) Dolo~itev zaporedja monta`nih operacij s hevristi~nim sistemom HAP The HAP Heuristic System for Assembly-Operation Sequence Planning Samo Zorc - Dragica Noe Del sistema za računalniško podprto načrtovanja montaže je tudi opredelitev zaporedja montažnih opravil. Osnova za računalniško podprto določitev zaporedja montažnih opravil je izdelek in povezave med njegovimi sestavnimi deli. Ker so prostorske povezave med sestavnimi deli izdelka neposredno povezane z geometrijo gibanja sestavnih delov pri sestavljanju, mora imeti zapis zaporedja montažnih opravil osnovo prav v opisu prostorskih povezav med sestavnimi deli. Prostor vseh možnih zaporedij montažnih opravil je predstavljen z grafom AND/OR. Za preiskovanje grafa pri iskanju najboljšega zaporedja, glede na postavljene kriterije, je uporabljen hevristični algoritem AO*. Zaporedje montažnih opravil je ocenjevano z geometrično sestavljivostjo, stabilnostjo in modularnostjo. Za obvladovanje zapletenosti je bil razvit in uporabljen učinkovit algoritem za nastanek in preiskovanje problemskega prostora. Praktični primeri kažejo primernost sistema za načrtovanje dejanskih izdelkov. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: planiranje montaže, zaporedja montaže, grafi AND-OR, algoritmi heuristični) The assembly-operation sequence-determination process is a part of the computer-aided assembly-planning system. Computer-aided assembly-sequence planning decisions are based on the product-assembly description and the relations between parts. The space relations between product parts are directly related to the movement geometry during the assembly process, and so for the assembly sequence determination a description of the space relation between the product parts can be used. The space of all possible assembly sequences is represented by an AND/OR graph. The graph is searched for the best sequence using a variant of the AO* heuristic algorithm. Assembly sequences are evaluated with respect to geometry feasibility, stability and modularity. To cope with the flexibility, efficient algorithms for generating and searching the problem space were developed and used. Empirical evaluations show the system can deal with real-world assemblies. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: assembly planning, assembly sequence planning, AND-OR graphs, heuristic algorithms) 0 UVOD Računalniška podpora je pri načrtovanju postopka montaže in montažnih sistemov vse bolj pomembna. To še posebej velja za razvoj sočasnega inženirstva, kjer bi želeli že v začetni fazi načrtovanja izdelka imeti čim več in čim bolj natančno oceno stroškov, ki jih bo povzročila montaža, in časa, ki bo potreben za izdelavo izdelkov. Sam postopek določitve montažnih opravil in njihovega zaporedja je tako vmesni člen med modeliranjem izdelka (konstrukcijo) in razvojem montažnega sistema. Problemi, ki se pri razvoju orodij za podporo pri načrtovanju montaže pojavljajo so interdisciplinarni, saj se dotikajo umetne inteligence (načrtovanje, modeliranje, 0 INTRODUCTION The use of computer-aided assembly-planning systems is becoming more and more important. This is particularly true of concurrent engineering, where the planner, in the early product-planning phase, requires more information about costs and assembly cycle times in the assembly process. The assembly operation and the assembly-operation sequence-determination process are the link between product modeling (design) and assembly system development. The problems that occur during at the tools’ development for the support of the assembly process and the assembly system planning are mostly interdisciplinary. They are connected with artificial isfFIsJBJbJJIMlSlCšD I stran 5 glTMDDC Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System preiskovanje), analitične geometrije in linearne algebre (trodimenzionalno modeliranje predmetov), strojništva (konstruiranje in modeliranje izdelkov, montažne tehnologije, montažni sistemi), računalništva (računalniška podpora pri posameznih korakih načrtovanja). Pri razvoju sistema načrtovanja zaporedja montažnih opravil je treba uvodoma definirati pojem montažnega opravila, poiskati način predstavitve sestavljenca oziroma izdelka, način predstavitve zaporedja montažnih opravil, izdelati model iskanja optimalnega montažnega zaporedja, definicija kriterijev optimalnosti in njihovega ocenjevanja ter obvladati zapletenosti preiskovanja ([3] in [15]). Razvoj sistema za izdelavo načrta montaže, to je zapisa montažnih opravil in določitve njihovega zaporedja (Heuristic Assembly Planner - HAP) ([1] do [3]), ki bo predstavljen v prispevku, upošteva dognanja o definiciji problema načrtovanja [12] in definicijo prostorskih povezav med sestavnimi deli izdelka na temelju teorije grup ([5] in [10]). Opis izdelka s prostorskimi povezavami je v nadaljevanju osnova za opis montažnih opravil. Za predstavitev zaporedja montažnih opravil so bile pomembne zamisli, ki sta jih predstavila Homen de Mello in Sanderson in analizirala različne znane predstavitve, kot so usmerjeni graf, graf AND/OR in druge [14]. Pokazala sta, da so predstavitve enakovredne po zmožnosti predstaviti vsa zaporedja in v pravilnosti predstavitve. Avtorja sta v svojem delu uporabila geometrični opis kot dodatno informacijo k simbolnemu zapisu sestava in povezav med sestavnimi deli pri preverjanju geometrične sklopljivosti. HAP pa uporablja geometrično informacijo kot osnovo za opis montažnege opravila. Specifična uporaba geometričnega opisa je omogočila, da veliko zaporedij montažnih opravil, zaradi nesklopljivosti sestavnih delov ni narejenih. Tako je mogoče hitreje iskati rešitve tudi za zelo zapletene sestave oziroma izdelke. HAP uporablja lasten algoritem za preiskovanje drevesa stanj na bazi AO* (MREC izvedba, ki sloni na ideji algoritma preiskovanja), izvedba iskanja opravil pa na zamisli vzvratnega načrtovanja, vendar z upoštevanjem kriterija geometrijske sestavljivosti in kriterija stabilnosti. 1 PREDSTAVITEV SESTAVLJENCA - IZDELKA Predstavitev sestavljenca - izdelka je vhodni podatek v sistem načrtovanja montažnega postopka in mora vsebovati predstavitev sestavnih delov in njihovih geometrijskih in topoloških povezav. Pri iskanju montažnega zaporedja natančni opisi oblike sestavnih delov niso potrebni. Treba je le zagotoviti tisto informacijo, ki se nanaša na izbrane kriterije preiskovanja. Za iskanje zaporedja montažnih opravil so pomembne povezave med elementi, kot so smer, način in ^BSfiTTMlliC | stran 6 intelligence (planning, modeling, searching), analytical geometry and linear algebra (3D product modeling), mechanical engineering (product design and modeling, assembly technology, assembly systems), computer science (computer support in particular planning steps). The aim of an assembly-operation sequence-planning system is to find the definition of an assembly operation, the representation of the product assembly, the representation of the assembly-operation sequence as well as the assembly operations, in order to develop the search algorithm for the optimal assembly sequence plan, to find the definition for evaluating functions and to master the complexity of the planning process ([3] and [15]). In the development of an assembly-planning system, the assembly operation and operation sequence (Heuristic Assembly Planner - HAP) ([1] to [3]), described in this article, consider the definition of planning knowledge [12], and represent the problem of the space relations’ definition of the part in the product, based on group theory ([5] and [10]). The representation of an assembly with the space relation is further used for the assembly-operation description. The relevant ideas, presented by Homen de Mello and Sanderson, were important for the assembly-operation sequence presentation [14]. Different known representations, like the directed graph, the AND/OR graph and others, have been analyzed. Authors found that all presentations were equal in terms of capability and accuracy of presentation. In addition, the authors used a geometrical description as additional information to symbolically describe the product and the part in the product in the geometrical feasibility searching process. In contrast, the assembly-operation description in the HAP system will be based on geometric information. Such a specific use of the geometrical description allows us to manage the searching problem. Many of the assembly-operation sequences were not generated because the product was not feasible. The searching process can also be managed faster for complex assemblies, e.g. products. The HAP system, as the searching algorithm, is based on AO* (MREC variant, based on a memory-sensitive recursive searching algorithm). The searching process is based on the “backward planning “ idea, in terms of the geometrical feasibility and stability criteria. 1 PRODUCT – ASSEMBLY PRESENTATION The assembly (product) representation is the input into the assembly-planning process. As such, it must include all the data about the assembly that is needed for planning, like the presentation of product parts and their topological and geometrical relations. We can assume that the exact description of the product and the product parts’ geometry and form were not necessary for the planning process. Only the information connected with selecting the evaluation criteria are important, like the spatial relationship between the Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System zmožnost sestavljanja, ki sestavljenec in njegovo sestavljanje pravzaprav določajo. Prostorska povezava je definirana kot skupek dovoljenih relativnih položajev telesa v odnosu do drugega telesa in dejansko pomeni vrsto giba, ki je potreben, da dva dela med seboj sestavimo, zato je uporabna za definicijo geometrije montažnega opravila. Ker ima prostorska povezava natančno matematično definicijo ([7], [9] in [10]), je primerna za računanje. Za popis sestavljencev so privzete osnovne prostorske povezave (preglednica 1). features of different parts and the direction of part movement during assembling and the assembling ability. The spatial relationship is defined by a set of allowable relative positions of one body with reference to the other, and actually represents a type of move to put two of the parts together. In this way is the definition useful for a geometrical description of the assembly operation. The spatial relationship has an exact mathematical definition and is therefore useful for subsequent computation ([7], [9] and [10]). For a description of the assemblies the basic spatial relationship has been introduced (Table 1). Preglednica 1. Opis osnovnih prostorskih povezav [7] Table 1. Classification of subgroups in the group of relationships [7] Stopnje svobode Oznaka Omejitve Oblika gibanja Dimension d.o.f. Notation Constraints Lower pair 1 Tv trans(x,0,0) prizmatična / prismatic Ru Twix(v|/) rotacijska / revolution Hu,p trans(x,0,0) Twix(px) vijačna / screw 2 Tp trans(0,y,z) Cu trans(x,0,0) Twix(y/) cilindrična / cylindrical 3 T trans(x,y,z) Gp trans(0,y,z) Twix(y/) ploskovna / plane So TwixWTwiz(^) TwixW sferična / spherical Yv,p trans(x,y,z) Twix(px) 4 Xv trans(x,y,z) Twix(t//) Osnovna prostorska povezava je matematično definirana na podlagi teorije grup. Izkaže se, da sestavlja množica vseh preslikav, ki ponazarjajo premike trdnih delov, grupo za množenje. Vsak premik (D) lahko predstavimo v obliki D = trans(v)*Rot(u,j), kjer je trans(v) premočrten premik vzdolž vektorja v e JP in Rot(u,j) vrtenje okrog vektorja u s kotom j (preglednica 1). Vse druge povezave je torej mogoče zapisati z osnovnimi povezavami ter tistimi, ki jih dobimo z opravilom prereza in sestavljanja. a) P2 O b) The spatial relationship is mathematically defined using group theory. It is well proven, that the number of illustrations of rigid body movements consists of a multiplication group. Each basic spatial relationship constitutes the subgroup of a group of all the displacements represented by D = trans(v)*Rot(u,j), where trans(v) is a translation along vector v e JP and Rot(u,j) is a rotation around the vector u, with the angle j (Table 1). Other relationships can be derived from the basic one by using the intersection and composition. R2. Pi0 v\\ R-,= C = trans(x,0,0) twix{f] 7 A x>=0, -dont < f 0), če naj povezava pomeni možen montažni premik (del p2 ne moremo sestaviti od spodaj navzgor). Sestav - izdelek (sl. 2b, 3a) je tako opisan z grafom (sl. 2a, 3b), kjer so vozlišča telesa (sestavni deli) in povezave povezave med njimi. Možni sta dve vrsti povezav. Prva vrsta so tiste povezave med sestavnimi deli, ki so v stiku (Cu med sestavnima deloma p2 in p7, sl. 2), in druge so povezave med sestavnimi deli, ki niso v stiku in definirajo celotno gibanje sestavnega dela (na primer T med sestavnima deloma p2 in p3). To correctly specify the assembly move, the domain of the spatial relationship variables also has to be defined. From Figure 1 we can conclude that the variable x in the relationship R21 has to be greater than or equal to 0 (x=>0), if the relationship is supposed to present a feasible assembly move (part p2 cannot be assembled from below). The assembly (Fig. 2a and 3a) can be described by a graph (Fig. 2b in 3b), where the nodes are bodies (product parts) and the arcs are the relationships between them. There are two types of relationship. The first one is the relationship between the parts, which constrains the local movement of a given part (the relationship defined between parts in contact (Cu between parts p2 and p74, Fig. 2b)) and the second one is the relationship between parts, which constrains the global movement of a given part (the relationship defined between parts that are not in contact (for example T between parts p2 and p3)). a) b) Sl. 2. Testni izdelek in graf povezav - izdelek je za testiranje modela povzet po literaturi [3] in [7] Fig. 2. Test product and relationship graph – Example product is taken for testing from reference [3] and [7] Ker so prostorske povezave podane za značilnosti na sestavnih delih, lahko med sestavnimi deli obstaja več povezav in posamezen sestavni del je lahko v povezavi z več sestavnimi deli v izdelku. Z iskanjem prerezov in sestavljanjem je mogoče najti le eno povezavo med danim sestavnim delom in ostankom. Ta povezava je potem gib, ki je potreben za sestavljanje danega sestavnega dela z ostankom. Če tako dobljena povezava obstaja, je sestavni del sestavljiv, drugače ni sestavljiv. Iskanje zaporedja vključuje preverjanje sestavljivosti (v HAP-u geom. sestavljivost in Since spatial relationships are initially defined between features of two parts, there can exist more than one relationship between two parts. In addition, one part can be related to many other parts in the product. By the use of intersection and composition it is possible to derive only one relationship between a given part and the rest. When such a derived relationship exists, the assembly of the part is feasible, otherwise it is not. Searching for assembly-operation sequences involves testing the feasibility (in HAP, geometrical feasibility and stability) and evaluating the feasible grin^SfcflMISDSD VBgfFMK stran 8 Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System stabilnost) ter preverjanje optimalnosti glede na optimizacijske kriterije (v HAP-u samo modularnost - vzporednost je morda lahko narobe razumljena kot sočasnost sestavljanja več glavnih delov hkrati, modularnost pa pomeni, da se posamezni deli lahko neodvisno sestavijo - vzporedno). Oboje poteka v okviru hevrističnega iskanja skozi graf AND/OR [6], kjer sočasno ustvarimo možne rešitve in jih hkrati tudi preiskujemo, oziroma iščemo optimalno rešitev. Na vsakem koraku se sprva poišče sestavljive možnosti za dani podsklop (v smislu vzvratnega načrtovanja), ki se jih potem po metodi hevrističnega iskanja oceni z optimizacijskimi kriteriji, da dobimo najboljšo možnost. Iskanje se potem s to najboljšo možnostjo nadaljuje naprej. Iskanje zaporedja obsega preverjanje sestavljivosti in stabilnosti ter preverjanje optimalnosti glede na kriterij vzporednosti. Oboje poteka v okviru hevrističnega iskanja skozi graf AND/ OR [6], kjer sočasno ustvarimo možne rešitve in jih hkrati tudi preiskujemo, oz. iščemo optimalno. Na vsakem koraku se sprva poišče sestavljive možnosti za dani podsklop (v smislu vzvratnega načrtovanja), ki se jih potem po metodi hevrističnega iskanja oceni z optimizacijskimi kriteriji, da dobimo najboljšo varianto. Iskanje se potem s to najboljšo možnost nadaljuje [4]. Osnova za testiranje geometrične sestavljivosti so informacije o prostorskih povezavah in testiranje sestoji iz testiranja vrste gibanja, obstoja lokalne ali celotne poti. Testiranje za obstoj lokalne poti pomeni testiranje spremenljivk in povezav, ki so povezane (na primer, dela p6 ni mogoče sestaviti, če sta dela p3 in p51 že sestavljena - sestav [p3, p51] ni sestavljiv s p6 v smislu obstoja lokalne poti (sl. 2)). Stabilnost je treba preveriti za vsak podsestav (ostanek). Ker so v HAP-u sestavni deli obravnavani kot prosto lebdeči predmeti, je stabilnost definirana kot povezanost grafa, ki predstavlja dani podsklop. Modularnost (optimizacijski kriterij) se upošteva tam, kjer se ocenjuje kakovost razstavljencev oziroma išče optimalno zaporedje sestavljanja. Potek razstavljanja oziroma sestavljanja je boljši, če je mogoče izdelek čim bolj enakomerno razstaviti. V resnici je ocena modularnosti (oz. vzporednosti) narejena na osnovi entropije in ima poseben obrazec [4]. Glede na število razstavitev pa smo se že na začetku omejili na dve, torej dani sklop vedno sestavimo natanko iz dveh podsklopov Modularnost pomaga pri tem, da loči med linearnimi zaporedji (vedno samo dodajamo en osnovni del) in bolj modularnimi, pri katerih poskušamo ločeno sestavljati podsklope in jih potem sestaviti v naslednji sklop [4]. 2 PREISKOVANJE IN KRITERIJI OCENJEVANJA Geometrijska sestavljivost pove, ali je mogoče določen predmet geometrijsko sestaviti z drugim sequences, and finding the optimal one according to the optimization criteria. (Only modularity in HAP – parallelism is probably understood as simultaneously assembled parts, the meaning of modularity is that some parts can be, in time and place, independently assembled). Both searching and evaluating are parts of the heuristic search through the AND/OR graph. [6], where simultaneously possible solutions are generated, and at the same time are estimated for an optimal solution. In each step, first all the possible (feasible) assembling ways for a given subgroup (in the backward-planning sense), and in the next step, with a heuristic search, are evaluated with the optimisation’s criterion, to get the best variant. The search process proceeds with the best variant [4]. Finally, we can conclude that searching process consists of feasibility and stability testing, and evaluating the optimality according to the modularity criterion. Both happen in the process of a heuristic search through the AND/OR graph [6], where all possible solutions are simultaneously generated and evaluated, i.e. searching for the optimal one. Testing the geometrical feasibility is based on information represented by the spatial relationship. It consists of testing the type of motion, the existence of a local path and the existence of a global path. Testing for the existence of a local path means testing all the variables in the relationships involved (for example, from the perspective of whether the part p6 can be assembled with parts p3 and p51, Figure 2 a, if both are assembled before, subgroup [p3, p51] is not feasible with respect to the local path existence (Fig. 2)). The stability is checked for each subassembly (rest). In the HAP system, parts are regarded as free-flying object in space, and with this approach stability is defined as the connectedness of the graph representing the given subassembly. Modularity (as an optimizations criterion) is considered, where the quality of the decomposition is evaluated in terms of the optimal assembly sequencing we are looking for. The disassembly, or assembly, process is of higher quality if the product can be disassembled in more subassemblies. In fact, the modularity estimation (parallelism) is based on the entropy, and can be expressed with a formula [4]. Based on the number of the decomposition, the limitation on two subassemblies was taken into account. In fact each subassembly can be put together from two parts, or a part and a subassembly, or two subassemblies can be assembled. Modularity helps us to separate the simple linear sequences from the complex one, where the product is composed from the subassemblies in a parallel position and subassemblies on more levels [4]. 2 SEARCHING AND EVALUATING CRITERIONS A feasibility criterion is used to evaluate, in the generation phase, to find if the given object is I igfinHi(s)bj][M]ifi[j;?n 03-1______ stran 9 I^BSSIfTMlGC Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System predmetom. Pri tem je predmet lahko sestavni del ali podsestav izdelka. Osnova za testiranje geometrijske sestavljivosti so informacije, ki jih pridobimo z opisom izdelka s prostorskimi povezavami in temelji na vrsti montažnega giba, obstoja lokalne poti in obstoja celotne poti. Da bi lahko predmet sestavili, je treba poiskati prerez vseh povezav - gibov, s čimer določimo celotni gib, potreben za sestavitev predmeta. Če ta prerez obstaja, pomeni, da obstaja gib, s katerim lahko realiziramo vse povezave. Če prerez ne obstaja, pomeni, da predmet ni sestavljiv z drugim [3]. Testiranje obstoja lokalne poti pomeni testiranje območja vseh spremenljivk v povezavi. Območja so v splošnem definirana glede na položaj značilnosti fij. In so v splošnem koraki oblike [0, cont], kar pomeni, da je vrednost spremenljivke lahko na razdalji od 0 do neskončno. Ker vrednost spremenljivke določa razdaljo med dvema deloma, je treba zagotoviti, da je vsaj eno območje neskončen trak na realni osi. Območja so definirana glede na položaj značilnosti fij. Z vidika p2 lahko območje za značilnost f21 za povezavo R1 ponazarja gib v osi x na koraku 0 do neskončno x=>0, oziroma x=[0, cont], y=0 in z=0. Pomeni tudi, da je mogoče del p2 sestaviti le od zgoraj (sl. 1). Obstoj celotne poti se z opisom povezave ne more rešiti. Avtorji so za reševanje tega problema definirali “navidezne stike” [5]. Navidezni stiki se definirajo med predmeti, ki sicer niso v stiku se pa celotno omejujejo. Tak postopek je uporabljen tudi v sistemu HAP Navidezni stiki se zapišejo pri opisu izdelka in se testirajo kakor preostale povezave. Stabilnost, kot eden izmed kriterijev pri iskanju najboljšega zaporedja, je definirana kot povezanost sestavnih delov, ki sestavljajo podsestav ali izdelek. To pomeni, da mora biti graf, ki predstavlja sestavljenec - izdelek, v različnih fazah sestavljanja povezan. To zagotavlja, da je podsestav enovit predmet in ga je mogoče prenašati, sestavljati naprej, testirati in drugo. V ocenjevanje primernosti zaporedja montažnih opravil je uveden tudi pojem “modularnost” oziroma “vzporednost”. Cilj tega kriterija je dobiti tista zaporedja, pri katerih poteka čim več montažnih opravil vzporedno. Za zapletene izdelke in možnosti istega izdelka je razvejana struktura montaže mnogo primernejša od verižne. Izdelek je tako razdeljen na module, ki jih je mogoče sestavljati časovno in prostorsko ločeno, nekatere podsklope oziroma module pa vgraditi v različne možnosti. Verižna struktura montaže je značilna le za izdelke z malo sestavnimi deli in je primernejša za montažo v posameznih robotiziranih montažnih celicah in preprostih verižnih montažnih avtomatih. Za ocenitev kriterija vzporednosti je treba poiskati tako funkcijo, ki bo ocenila tisto strukturo capable of assembling with the other one. The object could be a product part or a subassembly. Testing the geometrical feasibility is based on information represented by the spatial relationships, and is based on testing the type of motion, the existence of a local path and the existence of a global path. When an object has to be assembled with an other object, the intersection of all relations has to be establish of all relationships in order that the whole move for an object-necessary move for assembling an object is determined. If the intersection exists, the move for all relations’ accomplishment exists. If the intersection does not exist, the object is not feasible for the other one [3]. Testing the local path existence means testing the domains of all the variables in the relationship involved. Domains are defined in common with respect to the features position fij. And is an interval in form [0, cont], which means that the value of what is available is in the interval from 0 to infinity. Because the variable value defines the distance between two parts, we have to esure that at least one domain is an infinitive band on real axes. From the p2 point of view the domain for the feature f21 and for the relation R1 expresses the move in the x axes in the interval 0 to infinite x=>0, respectively x=[0, cont], y=0 in z=0. This means the part p2 can be assembled only above (Fig. 1). The global path’s existence can be determined but with a feature relationship cannot be solved. Authors defined for solving this problem introduced the »virtual relationship«. [5]. The virtual relationship can be defined between objects, which are connected respectively in touch, but limited to each other in a global way. This approach is also involved in the HAP system. The virtual relationship is written in the product-description phase, and is tested as other relations. Stability, as a decision criterion in searching the best solution, is defined as the connection of parts that consist of the product assembly. This means that the graph representing the given subassembly in a particular assembly phases has to be connected. With this definition, the subassembly as a uniform object can be transported, tested, stored, as well assembled further. The meaning “modularity” is involved for evaluating the assembly-operation sequences. The function of this criterion is to get those sequences involving more simultaneously executed assembly operations. For a complex product and a product in variants is the process with parallel executed operations and the so-called branched structure, which is better than the line structure. The product consists of modules, which can be assembled separately according to time and place. The simple line structure is acceptable for a product with a small number of parts and is dedicated for assembling in robotized cells and a simple, rigid assembly machine. For an estimation of the modularity criterion the formula for evaluating the assembly process structure grin^SfcflMISDSD VBgfFMK stran 10 Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System montaže oziroma tisto zaporedje, kjer so sestavni deli pri montaži bolj enakomerno porazdeljeni v podsestavih. Funkcija, ki ustreza tem zahtevam, je definirana z enačbo: P(D) has to be used. The goal is to find the assembly-operation sequence and assembly structure where the parts in the assembly process are in equal shares and are distributed in the subassemblies. The formula is defined as follows: -Z(ni/n)ln(ni/n) (entropija) (1), kjer so: D - razstavitev sestavljenca, k - 1število elementov (podsestavljencev) razstavitve in n -število elementov v povezanem podsestavljencu, ni - število vseh elementov danega sestavljenca. Vrednost P(D) je najmanjša, ko je število sestavnih delov v podsestavu enako n = n/d (kjer je d največje dovoljeno število i podsestavov v razstavitvi) in je enako P(D) = 1/ln (d). Ta vrednost je nato uporabljena za definicijo hevristične določitve za dani sestavljenec - izdelek, ki je definirana z: HP kjer sta: A - sestavljenec - izdelek, in n - število sestavnih delov v izdelku. Prvi del enačbe pomeni najmanjše število razstavitev za dani izdelek. Drugi del enačbe najmanjšo ceno za posamezno dekompozicijo. Zmnožek obeh delov daje oceno najmanjše cene, za sestavljanje danega izdelka z upoštevanjem vzporednosti. Ker je ta ocena vedno manjša ali enaka dejanski ceni, je pogoj, da algoritem AO* najde optimum, izpolnjen [3]. 3 PREDSTAVITEV MONTAŽNIH OPRAVIL IN NJIHOVEGA ZAPOREDJA Poznanih je več algoritmov za predstavitev vseh montažnih opravil ([4] in [14]). V sistemu HAP pa je bil za opis vseh možnih montažnih opravil (torej problemskega prostora) uporabljen graf AND/OR, ki omogoča izrecno predstavitev vzporednosti in jasno predstavitev iskanja najboljšega zaporedja s strategijo vzvratnega iskanja ([3] in [4]). Graf AND/OR je sestavljen iz povezanih vozlišč OR in AND. Vozlišča OR pomenijo sestavljenec - izdelek, podsestav ali sestavne dele, vozlišča AND pa montažno opravilo. Ker je montažno opravilo definirano kot sestavljanje podsestavov oziroma sestavnih delov in podsestavov, je torej definirano kot seznam podsestavov in sestavnih delov, ki jih je treba združiti. Iz celovitega nabora mogočih montažnih opravil je naloga HAP-a, da poišče tisto zaporedje montažnih opravil, ki bo mogoče in ki ga bo mogoče izvesti v ustreznem času ter po primerni ceni. Preiskovanje grafa in iskanje zaporedij mora tako upoštevati izbrane kriterije sestavljivosti in za možne inačice še optimizacijske kriterije. In equation (1) D is the the decomposition of the product, k is the number of the element (subassemblies) decomposition, and n is the number of elements in the connected subassembly, ni is the number of all the elements of the given part. The value P(D) is a minimum when the number of parts in a subassembly is equal, ni = n/d, (where d is the maximum allowed number of subassemblies in the decomposition), and is equal to P(D) = 1/ln (d). This value is used for a definition of the heuristic estimate for a given assembly part, which is defined as: d-1J {ln(d) 1 (2), where A is the assembly product, and n is the number of parts in the assembly. The first part of the function represents the minimum number of decompositions for a given assembly. The second part represents the minimum price to be paid for a particular decomposition. The product of both parts gives an estimate of the minimum price to be paid for a given assembly with respect to the parallelism. As the estimate is always lower then or equal to the real price, the condition for the AO* algorithm to find the optimum is satisfied [3]. 3 ASSEMBLY OPERATIONS AND THEIR SEQUENCE REPRESENTATION Several algorithms are known for representing assembly operations ([4] and [14]). In the HAP system for all the assembly operations an AND/OR graph was used (with respect to the problem space). The AND/OR graph seems to be the most suitable for showing parallel actions in an assembly process and represents the backward-search strategy more clearly ([3] and [4]). An AND/OR graph consists of interconnected OR and AND nodes. OR nodes represented assemblies, subassemblies or parts, AND nodes represent the assembly operation. In the current implementation the assembly operation is defined as putting subassemblies together, the parts and subassemblies, and it is represented by a list of parts and subassemblies, which have to be put together in the given step. The goal of the HAP system is, from the whole list of possible assembly operations, to select the possible executed assembly-operation sequences, which can be executed in a suitable time period and at a convenient price. The graph search and the sequence determination have to consider the selected criterion of feasibility and for possible alternatives the optimatisation criteria. Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System a) b) c) Sl. 3. Ponazoritev izdelka s sedmimi sestavnimi deli, a - razstavljen izdelek, b - graf prostorskih povezav med sestavnimi deli, c - graf AND/OR ob upoštevanju kriterija sestavljivosti Fig. 3. An assembly consists of seven parts, a - the drawing model, b - relationship graph of assembled parts, c - AND/OR graph showing the feasibility criterion 3.1 Iskanje zaporedja montažnih opravil 3.1 Search for the assembly-operation sequence Iskanje zaporedja montažnih opravil sestavljata The search for assembly-operation sequence dva logična koraka, ustvarjanje vseh možnih consists of two logical steps: the generation of all (smiselnih) zaporedij in med njimi iskanje najboljšega possible (feasible) sequences, and the search for zaporedja. V smislu predstavitve vseh možnih the best one. In the sense of representing all montažnih zaporedij (oz. problemskega prostora) to possible assembly operations (i.e. the whole problem pomeni ustvarjanje in potem preiskovanje grafa AND/ space) that means generating and then searching OR pri čemer HAP sledi zamisli t.i. vzvratnega the AND/OR graph. In the searching process the sestavljanja [12], kjer poteka iskanje tako, da iščemo HAP follows the so-called concept of backward zaporedje montažnih opravil od zadnje k prvi - torej od planning [12], where the assembly-operations sestavljenega sklopa do osnovnih delov (sl. 3). Pri tem sequence planning starts with an assembled product HAP uporablja dve vrsti kriterijev. Sestavljivostni and then goes back to the parts (Figure 3). Two kriteriji zagotavljajo sestavljivost danega montažnega criteria are used in HAP: the feasibility criterion zaporedja, optimizacijski pa ocenjujejo njeno enables the feasibility of the result assembly optimalnost. V okviru prvih HAP uporablja sequence and the optimization criterion evaluated geometrijsko sestavljivost in stabilnost, v okviru if the solution is optimal. In HAP the geometrical drugih pa modularnost (čim bolj enakomerno feasibility and the stability are used for the first, sestavljanje prek podsklopov). Rešitev, ki jo HAP torej and for modularity the second criteria (to get najde, je sestavljivo montažno zaporedje, ki je najbolj assembly process through subassemblies) the result modularno. Sam sistem tudi omogoča nadaljnjo of the searching with HAP is the most modular dodajanje tako enih kakor tudi drugih kriterijev. feasible assembly-operation sequence. The system Ker je celotno iskanje algoritmično zapleteno, allows further adding of certain criteria. HAP uporablja različne zamisli, ki mu omogočajo, da je Because the search process is a complex njegova uporaba vseeno učinkovita ([4] in [6]). Prva algorithmic process, HAP involves some ideas to zamisel je ta, da je preiskovanje v HAP-u izvedeno na enable the effective use of the searching system ([4] način, ki sloni na znanem heurističnem algoritmu AO*, and [6]). First, the search for the best sequence is kjer oba koraka potekata sočasno, oz. postopek done using the known best-first heuristic algorithm ustvarjanja in preiskovanja grafa AND/OR poteka hkrati AO*, where both steps, the generating process and - v skladu s hevrističnim preiskovanjem. Pri tem načinu the searching AND/OR graph, are executed del grafa, ki ni zanimiv za preiskovanje (ker postopek simultaneously in terms of the heuristic search. In preiskovanja kaže, da tam ni rešitve), ne ustvarimo, kar this way the part of the graph, not interesting for bistveno prispeva k učinkovitosti celotnega sistema. search (the searching process shows us there is no Druga izmed zamisli, ki najbolj bistveno pripomore k solution) is not generated. Because of this the system učinkovitosti HAP-a, pa je način ustvarjanja vozlišč is more effective. Another idea, which supports the ^BSfiTTMlliC | stran 12 i Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System AND, oz. možnih razstavitev danega sklopa. Namreč, v danem koraku iskanja alternativ za sestavljanje danega sklopa (npr. [1234567] sl. 3), ne ustvari vseh vozlišč AND temveč samo tista, ki so dejansko sestavljiva (glede na uporabljene sestavljivostne kriterije). Poglavitna zamisel je ta, da ustvarjanje ne poteka po znanem postopku poskusi in popravi (kjer se v osnovi ustvarjajo vse razstavitve, ki se potem testirajo glede na sestavljivost, in tako izločijo nesestavljive), temveč tako, da se uporabi kriterije sestavljivosti (na temelju podatkov podanih v predstavitvi sestavljenca) že pri samem ustvarjanju, tako da že pri prvem koraku dobimo sestavljive inačice ([4] in [6]). S tem potem ni treba ustvariti in tudi ne preverjati velike večine razstavitev, ki v večini primerov sploh niso sestavljive. Testiranje HAP-a je pokazalo, da lahko uporabljene rešitve omogočajo uporabo sistema na dejanskih primerih. HAP effectiveness much more, is the way of generating the AND nodes (possible decompositions of a given subassembly). Namely, in a given step of searching the alternative for assembling of a given subassembly (e.g. [1234567] Figure 3), the HAP does not generate all AND nodes, only those which are really feasible (according to the feasibility criteria). The basic idea is that the generating process does not run in the known trial-and-error method (where all decompositions are generated and then tested according to the feasibility, and selecting these not feasible). The searching process in HAP uses the feasibility criteria (based on information given with the product presentations) already in the generating process, which gives us only feasible alternatives ([4] and [6]). So the numbers of not-feasible decompositions are never generated. 4 UPORABA IN TESTIRANJE 4 IMPLEMENTATION AND TESTING Za preverjanje osnovnih teoretičnih spoznanj in za ekperimentiranje je HAP napisan v PROLOG-u, uporabljen je operacijski sistem OS/2 [6]. Za testiranje The experimental assembly planner is written in PROLOG on the OS/2 operating system. [6]. For testing, artificial products and products from real Začetek /Start: Konec/End: čas / time (19,14,54,0) čas / time (19,37,29,59) Št. vseh OR vozlišč / Num. of all OR nodes: 343 Št. razvitih OR vozlišč / Num. of expended OR nodes: 204 definirani posestavljenci/imposed subassmeblies: ps ([p11, p12, p13, p2, p3, p41, p42, p43, p51, p52, p53, p6, p71, p72, p73, p74, p8], []) [vp1, vp10, vp11, vp12, vp13, vp14, vp15, vp16, vp17, vp2, vp3, vp4, vp5, vp6, vp7, vp8, vp9] -NDEF-[vp1, vp10, vp11, vp12, vp14, vp15, vp16, vp17, vp2, vp3, vp4, vp5, vp6, vp7, vp8, vp9] -Hup-[vp1, vp10, vp11, vp12, vp15, vp16, vp17, vp2, vp3, vp4, vp5, vp6, vp7, vp8, vp9] -Hup-[vp1, vp10, vp11, vp12, vp15, vp17, vp2, vp3, vp4, vp5, vp6, vp7, vp8, vp9] -Hup-[vp1, vp10, vp11, vp12, vp17, vp2, vp3, vp4, vp5, vp6, vp7, vp8, vp9] -Hup-[vp1, vp12, vp17, vp2, vp3, vp4, vp6, vp9] -Tv- [vp1, vp12, vp17, vp2, vp3, vp4, vp6] -Tv-[vp1, vp2, vp3, vp4, vp6] -Tv-[vp2, vp3, vp4] -Tv- [vp3, vp4] -Tv-[vp4]_[p2] -Tv-[vp3]_[p13] -Tv-[vp2]_[p12] -Tv-[vp1,vp6] -Tv- [vp1]_[p11] -T-[vp6]_[p41] -T-[vp12, vp17] -Tv-[vp17]_[p8] -Tv-[vp12]_[p6] -Tv-[vp9]_[p51] -Tv-[vp10, vp11, vp5, vp7, vp8] -Tv-[vp11, vp5, vp8] -Tv-[vp5]_[p3] -Tv-[vp11, vp8] -Tv-[vp8]_[p43] -T-[vp11]_[p53] -T-[vp10, vp7] -Tv- [vp7]_[p42] -T-[vp10]_[p52] -T-[vp15]_[p73] -Hup-[vp16]_[p74] -Hup-[vp14]_[p72] -Hup-[vp13]_[p71] -Hup Sl. 4. Zapis rezultata računanja HAP za primer na sliki 3 Fig. 4. Computing results of HAP for product shown on Figure 3 Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System so upoštevani teoretični in dejanski izdelki ([3] in [4]). Rezultat testiranja je zapis optimalnega zaporedja montažnih opravil in definicija gibov, ki so potrebni za sestavljanje. V zapisu je podan tudi čas računanja in število vseh vozlišč OR in razvitih OR (sl. 4). Sestavljanje gre od desne proti levi - torej od listov h koreninam drevesa. Sestavijo se vedno deli z enakim odmikom. Pri obeh je tudi podan gib oziroma prostorska povezava - PR, s katero ju sestavimo. Začnemo s p2 in p1 (T PR), potem jima dodamo p12 (T ). Neodvisno od tega prej sestavimo p11 in p41 (T) in potem to sestavimo skupaj s prejšnjim sklopom [p2, p12, p13] (T ) itn. HAP tudi omogoča, da uporabnik določi posamezne podsklope, prek katerih želi, da sestavljanje poteka (na primer za podsklope, ki jih potem uporablja kot rezervne dele). V zgornjem primeru na sliki 4 tak podsklop ni bil definiran. 5 SKLEP Računalniško podprto načrtovanje zaporedja montažnih opravil bo ključnega pomena pri vzporednem inženirstvu, kjer je treba že v fazi načrtovanja izdelka napovedati postopek in stroške montaže. Številne raziskave v zadnjem desetletju so pokazale nekaj smeri za mogoč razvoj uporabnih modelov avtomatičnega načrtovanja montažnega postopka in montažnih sistemov. Podan model HAP je eden izmed postopkov, ki prispeva k razjasnjenju nekaterih postopkov pri računalniškem načrtovanju montaže. Značilnost postopka v modelu HAP je v uporabi geometrije sestavljanja v obliki prostorskih povezav, ki so znane konstrukterjem že pri oblikovanju izdelkov. S to informacijo se v modelu izognemo zapleteni numerični analizi lokalne in celotne poti, ki sta potrebni za testiranje geometrijske sestavljivosti montažnega zaporedja. V modelu je uporabljen lasten algoritem za preiskovanje drevesa stanj na bazi AO*, ki že v fazi ustvarjanja razstavitve upošteva geometrijsko obliko sestavljenca. Testiranje na dejanskih primerih je pokazalo, da je algoritem kljub zapletenosti uporaben na dejanskih problemih. Za nadaljnji razvoj modelov računalniškega načrtovanja zaporedja montažnih opravil bodo pri konstruiranju pomembni modeli, ki bodo omogočali avtomatični zapis montažnih opravil neposredno iz modela RPN izdelka z zapisom potrebnih informacij. Za določitev optimalnih zaporedij montažnih opravil pa je treba dodati še dodatne kriterije, ki naj bi povečali uresničljivost in pomembnost rešitev. Taki kriteriji bi lahko bili težnost, smeri sestavljanja, drugačni podsestavi in drugi. Za opis nekaterih kriterijev bo mogoče uporabiti prav natančno geometrično informacijo, ki je bila predstavljena v sistemu HAP. Raziskovalno delo sta podprli Ministrstvi za znanost Slovenije in Avstrije. ^BSfiTTMlliC | stran 14 production were introduced ([3] and [4]). The results, the optimal assembly sequence is written in Figure 4. The report also includes the computing time and the number of all possible OR nodes as well as the imposed OR nodes. Assembling goes from the left to the right – from the leaves to the roots of the tree. The parts with equal distance are assembled. In both examples is the move assembled with the spatial relationship – PR. We started with p2 and p13 (Tv PR), then we added p12 (Tv). Separately, we assembled p11 and p41 (T), and then we assemble together with earlier subassembly [p2, p12, p13] (Tv), etc, HAP also allows the user to determine subassemblies in advance (for example, the subassemblies used for spare parts). In the case in Figure 4 we do not have such subassemblies. 5 CONCLUSIONS Computer-aided planning of an assembly sequence will have a key role in simultaneous engineering when the process and the costs of assembly have to be determined in the product development phase. Numerous research activities in past decades have shown some directions for the development of useful automated assembly process and systems-planning models. The discussed model, HAP, is only one approach for the elucidation of different processes in computer-aided planning systems. The main characteristics of the HAP model are the use of the geometry of assembling in the form of a spatial relationship, which is also known to the designer in the product-modeling phase. This information helps us to avoid complex numerical analysis of the local and global path’ needed for testing the geometrical feasibility assembly in assembly-operations sequence planning. Testing the HAP on real products or assemblies showed us that the search algorithm, in spite of exponential complexity, is useful for real problems. In the HAP system the original algorithm for searching the status tree based on AO* was used. The model considers in the decomposition phase the geometry of the assembly. For the further development of computer-aided assembly-operations planning models it is important to enable an automatic description of the assembly operation from the CAD product model and the needed information in the design phase. To make it more realistic and relevant some additional criteria like gravity and variant subassemblies have to be involved. For a description, some criteria, the exact geometric information, presented in the system HAP, can be used. Research work was supported by Ministries of science of Slovenia and Austria. Zorc S., Noe D.: Dolo~itev zaporedja - The HAP Heuristic System 6 LITERATURA 6 REFERENCES [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] Zorc, S., D. Noe, I. Kononenko (1998) Efficient derivation of the optimal assembly sequence from product description. Cybern. syst, vol. 29, no. 2, 159-179. Zorc, S., D. Noe (1997) Assembly planning using spatial relationships. Manuf. Syst. (Aachen), let. 26, St. 1, 39-43. Zorc, S. (1997) Računalniško podprto načrtovanje zaporedja montažnih operacij, Magistrsko delo, Fakulteta za računalništvo in informatiko, Univerza v Ljubljani 1997. Delchambre, A. (1992), Computer-aided Assembly planning, Chapman&Hall, London 1992. Homem de Mello, L.S., L. Sukhan (1991) Computer-aided mechanical assembly planning, Kluwer Academic Publisher, Massachusetts. Bratko, I. (1990) Prolog programming for artificial intelligence (2nd edition), Addison-Wesley. Thomas,F., C. Torras (1988) A group theoretic approach to the computation of symbolic part relations, IEEE Journal of Robotic and Automation, Vol. 4, No. 6, 622-634. Santochi, M. and G. Dini (1995), Technical Report: STC A framework for the evaluation and selection of assembly plans, Annals of the CIRP, vol. 4(2), 651-658. Celaya, E., C. Torras (1990) Finding Object Configuration that Satisfy Spatial Relationships, Proc. ECAI, Stockholm 1990, 141-146. Thomas, F., C. Torras, A group theoretical aproach to the computation of three-dimensional structures via connectivity graphs, Annals of the CIRP, vol. 38(1), 25-28. Thomas, F., X.F. Zha, Y.E.S. Lim, S.C. Fok (1998) Integrated intelligent design and assembly planning: a survey, Int. J. Adv. Manuf. Technol, 14:50-64. Lee S. (1991) Backward assembly planning with DFA analysis, Homen de Mello L.S., S. Lee: Computer-Aided Mechanical Assembly Planning, Kluwer Academic Publisher, Massachusetts 1991. Zha, X.F., Y.E.S. Lim, S.C.Fok, S.C. (1998) Integrated knowledge-based assembly sequence planning, Int. J. Adv. Manuf. Technol., 14:50-64. Homem de Mello, L.S., A.C. Sanderson (1991) Representations for assembly sequences, L.S.Homem de Mello, Sukhan Lee (ed) Computer-aided mechanical assembly planning, Kluwer Academic Publisher, Massachusetts 1991. Kunica, Z., B. Vranješ (1999) Towards automatic generation of plans for automatic assembly, International Journal of Production Research, Vol 37, 1817-1836. Naslov avtorjev: mag. Samo Zorc profdr. Dragica Noe Fakulteta za strojništvo Univerza v Ljubljani Aškerčeva 6 1000 Ljubljana dragica.noe@fs.uni-lj.si Authors’ Address: Mag. Samo Zorc Prof.Dr. Dragica Noe Faculty of Mechanical Eng. University of Ljubljana Aškerčeva 6 1000 Ljubljana, Slovenia dragica.noe@fs.uni-lj.si Prejeto: Received: 14.1.2003 Sprejeto: Accepted: 29.5.2003 Odprt za diskusijo: 1 leto Open for discussion: 1 year