3 File Edit View Insert Format Tools Draw Dimension Mor. E P|e||JJ *m JflJ_x] JSJ_I let. - vol. 49 (2003) {t. - no. 1 STROJNIŠKI VESTNI K 1 JOURNAL OF MECHANICAL ENGINEERING strani-pages1 - 74 ISSN 0039-2480 . StrojV . STJVAX cena 800 SIT 2. olo~itev zaporedja monta`nih operacij s hevristi~nim sistemom HAP ------- Assembly-Operation Sequence Planning Ra~unalni{ko upravljanje z obdelovalnimi orodji v orodjarni, podprto s simulacijo ------- Simulation-Aided Management of Cutting Tools Company Tool-Making 3. 4. 5. Na~rtovanje izdelovalnih sistemov, podprto s simulacijo ------- Simulation-Aided Planning of Manufacturing Systems Nekaj novih algoritmov za ra~unalni{ko podprto na~rtovanje monta`e ------- Some New Algorithms for Computer Aided Assembly Planning Robotiziran monta`ni sistem kot sodelujo~a ve~delna organizacija ------- A Study of a Robotic Assembly System as a Collaborative Multi-Agent Organization ^ File Edit Environment layout Modeli in a 9770039248001 © Strojni{ki vestnik 49(2003)1,1 © Journal of Mechanical Engineering 49(2003)1,1 Mese~nik Published monthly ISSN 0039-2480 ISSN 0039-2480 Vsebina Contents Strojni{ki vestnik - Journal of Mechanical Engineering letnik - volume 49, (2003), {tevilka - number 1 Uvodnik Editorial Alujevič, A.: 49. letnik Strojniškega vestnika Alujevič, A.: 49th Volume of Journal of Mechanical 2 Engineering Noe, D.: Računalniško podprto načrtovanje 3 Noe, D.: Computer-Aided Planning of the Assembly montažnega procesa Process Razprave Papers Zorc, S., Noe, D.: Določitev zaporedja montažnih 5 Zorc, S., Noe, D.: The HAP Heuristic System for operacij s hevrističnim sistemom HAP Assembly-Operation Sequence Planning Debevec, M., Perme, T., Noe, D.: Računalniško Debevec, M., Perme, T., Noe, D.: Simulation-Aided upravljanje z obdelovalnimi orodji v orodjarni, 16 Management of Cutting Tools in a Tool- podprto s simulacijo Making Company 28 Perme, T.: Simulation-Aided Planning of podprto s simulacijo Manufacturing Systems Kunica, Z., Vranješ, B., Hrman, M.: Nekaj novih algoritmov za računalniško podprto 41 Algorithms for Computer Aided Assembly načrtovanje montaže Planning Jerbič, B., Vranješ, B.: Robotiziran montažni sistem 52 Jerbič, B., Vranješ, B.: A Study of a Robotic kot sodelujoča večdelna organizacija Assembly System as a Collaborative Multi- 63 68 71 72 73 Agent Organization Poročila Reports Strokovna literatura Professional Literature Osebne vesti Personal Events Pisma uredništvu Letters to the Editorial Board Navodila avtorjem Instructions for Authors (sfinsjObJJiMiSicši] i stran 1 glTMDDC © Strojni{ki vestnik 49(2003)1,2-4 © Journal of Mechanical Engineering 49(2003)1,2-4 Uvodnik Editorial ISSN 0039-2480 ISSN 0039-2480 Uvodnik Editorial 49. letnik Strojni{kega vestnika Z majhno zamudo je pred nami prva številka 49. letnika Strojniškega vestnika. Naslednje leto bo jubilejno “L”, saj se bomo pripravljali na srečanje z Abrahamom. Strojniški vestnik je namreč začel izhajati marca 1955. Upamo lahko le, da nas črni oblaki denarnih težav do takrat ne bodo zadušili. Sredstva Ministrstva za šolstvo, znanost in šport so nam v preteklem letu pokrila približno polovico potreb, kolikor znesejo zunanji stroški tiskarne in lektorata. Preostale notranje stroške na Fakulteti za strojništvo v Ljubljani le delno pokrivamo z naročninami in oglasi, vendar je ta “odeja” vsako leto prekratka. Strojniški vestnik ima sedaj razširjen uredniški odbor in mednarodni svetovalni odbor (glej notranjo stran ovitka). Odslej bomo imeli tudi rubriko “Pisma uredništvu”, v kateri bi želeli tudi odmeve na objavljene prispevke v enoletnem obdobju. V letošnjem letniku načrtujemo dvanajst številk, med katerimi jih bo šest tematskih konstrukterstvo, hidrotehnika, avtomobilizem IAT, računalništvo DMMI). Prestalo bomo izpolnili z mešanim gradivom. Člankov nam ne primanjkuje, tudi iz tujine prihajajo, predvsem iz vzhodnih držav. Pri domačih avtorjih naletimo včasih na problem, ali je prispevek prva (izvirna) objava, ali pa gre za ponatis že drugje objavljenih besedil istih avtorjev. Naši recenzenti so praviloma profesorji obeh naših fakultet, kar v večini primerov uspeva. Drugo recenzijo poiščemo v tujini, če gre za objavo izvirnega znanstvenega članka (1.01). Razvid lanskoletnih recenzentov smo objavili v 12. številki preteklega letnika. Dogaja se kar pogosto, kadar kakšen prispevek ocenimo kot strokovni, da vzplamti pri avtorjih, ki prečiščena besedila enostavno odnesejo in v brezhibni angleščini objavijo v tujini. Morda bomo prisiljeni tako nastale stroške zaračunati. Imamo tudi primere, ko je bil članek obljavljen v Strojniškem vestniku, naslednje leto (brez navedbe) s skoraj enakim besedilom in slikovnim gradivom pa v tujini -obe reviji pa sta prejeli “copyright” pravice v pisni obliki. Na koncu naj omenim še zavzemanje za lepšo uporabo slovenskih izrazov. V decembrskem Informatorju ZSIS je izpod peresa g. B. Uratariča izšel vzpodbuden prispevek “Ohranimo slovenska tehnična besedila brez nepotrebnih tujk”, s katerim se skoraj v celoti strinjam in ga bomo ponatisnili že v tej številki. Pri Strojniškem vestniku smo se vsi dosedanji uredniki trudili s slovenskimi izrazi. Celo našega akademika profdr.Janeza Peklenika nam je uspelo prepričati, da ni prav “nacionalna ekonomija”, zakaj bi potem težili s “fretažo”. Poglejte v novi Veliki slovar tujk, kaj je domače. Pred več ko 40 leti nas je prof. Albert Struna učil o torni obrabi in mazanju. Tudi besedo “kontinuum” lahko razdelimo na trdnine in tekočine, pri čemer pa slednje nimajo togosti in podajnosti. Že pesnik je zapisal ... “ga kolne kmet molitve bravši”. Če ste mi zamerili, mi pač odmerite (kazen). Glavni in odgovorni urednik profdr. Andro Alujevič grin^(afcflM]SCLD VH^tTPsDDIK stran 2 Uvodnik - Editorial Ra~unalni{ko podprto na~rtovanje monta`nega procesa Computer Aided Planning of the Assembly Process Načrtovanje montažnega procesa je ključna dejavnost pri razvoju novih in tudi pri prenovi sedanjih montažnih sistemov. V preteklosti smo bili priča ogromnim naporom, ki so bili vloženi v sistemizacijo procesa načrtovanja montaže, v zbiranje in sistemizacijo znanja, potrebnega pri načrtovanju, kakor tudi razvoju orodij za podporo načrtovalcem montažnih sistemov. Pomembni koraki so bili narejeni tudi pri sistemizaciji in optimiranju procesa montaže, uvajanju metod umetne inteligence, pri iskanju optimalnih procesov, razvoju programskih orodij za podporo pri izbiranju komponent montažnih sistemov, pri izdelavi zasnove montažnih sistemov, uvajanju metod simulacije pri ocenjevanju predloženih različic in razvoju virtualne montaže kot metode in orodja za zmanjševanje investicijskega tveganja. Kratki časi pri uvajanju montaže novih izdelkov ob hkratnih zahtevah po zmanjševanju stroškov na vseh ravneh silijo proizvajalce in uporabnike montažne opreme k vedno večji racionalizaciji pri načrtovanju ter uvajanju “optimalnih” montažnih sistemov. Ker so montažni sistemi dragi in je pri njih stopnja tveganja izredno velika, so vnaprejšnje ocenitve delovanja montažnih sistemov, simulacije in virtualne montaže, zaželene in potrebne. Pomembna prednost računalniško podprtega načrtovanja montažnih sistemov je prav možnost kakovostnega ocenjevanja variantnih predlogov montažnih sistemov in na ta način podprta optimizacija. Znanstvene ustanove, univerze in raziskovalni inštituti, še posebej tisti s področja umetne inteligence in uporabe znanja razvijajo računalniške modele, ki bodo v prihodnosti privedli do uporabnih programskih rešitev za avtomatizacijo pridobivanja potrebnih podatkov za načrtovanje procesa montaže iz modela izdelka. Na tej podlagi se razvijajo ekspertni sistemi za iskanje optimalnih zaporedij montažnih opravil, razvijajo se metode simulacije, virtualne montaže, z znanjem podprto konstruiranje izdelkov in podobno. Montažno usmerjeno konstruiranje izdelkov je dandanes ena najintenzivnejših dejavnosti, pri kateri uporabljamo veliko število različnih orodij za podporo ocenjevanja novo nastajajočega izdelka. Namen montažno usmerjenega konstruiranja izdelkov je povezovanje razvoja izdelka, izdelave in odločitvenih kriterijev pri razvoju montažnega procesa. Do danes je bilo doseženo mnogo pri razvoju primernosti izdelkov za avtomatizirano montažo oziroma upoštevanju možnosti avtomatizacije montaže že pri razvoju izdelkov, pri generiranju montažnih opravil iz samega modela izdelka in pri Determining the assembly process is the key activity in the development or re-engineering of an assembly system. In the past, enormous efforts were invested in a systematisation of the assembly-planning process, the collection and systematisation of the knowledge needed for decision making in the planning process, and in the development tools to support experts in the planning process. Important steps have also been made in the systematisation and optimisation of the assembly process itself, involving artificial intelligence methods in searching for the optimum assembly process, the development of tools for assembly systems, the selection of components, the layout in variant designing, and the development of the virtual assembly process as a method and a tool for investment-risk reduction. The short development period for new products and modern demands for the reduction of all costs have forced both the producer and the user of assembly equipment to rationalize the assembly-system planning process and involve “optimal” assembly systems. Because of the high costs of assembly systems and the high degree of risk, an estimation of the working behaviour of an assembly system in advance, using simulations and a virtual assembly process, are not only desired, they are also necessary. The important advantage of computer-aided assembly-system planning is the possibility of a quality estimation of the proposed variants, and in this way offering support to the optimisation process. Scientific institutions, universities and development centres, especially those that are involved in artificial intelligence and knowledge processing have developed computer-aided models that must, in the future, provide us with the useful tools for automated data that are needed for the planning process, gathered directly from product data, i.e. models. For this reason, expert systems that search for the optimum assembly sequences, simulation methods and virtual assembly have to be developed, and product development has to be supported with knowledge of assembly, production, etc. Assembly-oriented product design is today an activity that uses a large number of different tools for an estimation of the generated new product. The aim of assembly-oriented product design is the connection of new-product development with production, i.e. assembly and decisions criteria in assembly-process decisions. We are faced today with a number of solutions in product design for automated assembly, in selecting the assembly operation from product data, and in assembly-operation sequencing determination as a basis for assembly-systems gfin^OtJJlMISCSD stran 3 Strojni{ki vestnik - Journal of Mechanical Engineering določanju zaporedja montažnih opravil kot temelja za načrtovanje montažnih sistemov. Vsekakor je to področje osnova tako imenovanega sprotnega inženirstva in bo v prihodnosti zaposlovalo veliko število strokovnjakov. V tej številki Strojniškega vestnika prvič namenjamo več prostora raziskovalnemu in razvojnemu delu na področju načrtovanja montaže, ki je v zadnjem desetletju intenzivno potekalo v Laboratoriju za strego, montažo in pnevmatiko na Fakulteti za strojništvo Univerze v Ljubljani in na Fakulteti za strojništvo in ladjedelništvo Univerze v Zagrebu. Prikazani prispevki so le del dejavnosti obeh raziskovalnih skupin. Raziskovalno delo je bilo podprto s sredstvi pristojnih ministrstev Republike Hrvaške in Republike Slovenije. Določene raziskave so bile financirane tudi s sredstvi Republike Avstrije. prof.dr. Dragica Noe planning. These questions are the basis for so-called simultaneous engineering, and in the future more and more experts will be involved in searching for the right solutions. In this issue of the Journal of Mechanical Engineering, for the first time more space is given over to research and scientific work in the field of assembly planning, which has been an important area of research in the past ten years in the Laboratory for Handling, Assembly and Pneumatics at the Faculty of Mechanical Engineering, University of Ljubljana, as well as at the Faculty of Mechanical and Naval Engineering, University of Zagreb. The published papers are the results of both research groups. The research ministries in Slovenia and Croatia supported the research work, and the Austrian government also supported some of the projects. Prof.Dr. Dragica Noe grin^(afcflM]SCLD VBgfFMK stran 4 © 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 (SfinsjBJbJJIMlSlCšI] 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 ^BSfirTMlliC | 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 Dimension d.o.f. Oznaka Notation Omejitve Constraints Oblika gibanja Lower pair 1 2 3 Tv Ru Hu,p Tp Cu T Gp So trans(x,0,0) Twix(y) trans(x,0,0) Twix(px) trans(0,y,z) trans(x,0,0) Twix(y/) trans(x,y,z) trans(0,y,z) Twix(y/) TwixWTwiz() Twix^) prizmatična / prismatic rotacijska / revolution vijačna / screw cilindrična / cylindrical ploskovna / plane sferična / spherical 4 Yv,p Xv trans(x,y,z) Twix(px) 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) P2Q b) R, / / i — V v x r '2 ^P ~Z 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. P2 P10 x R21= C = trans(x,0,0) twix(f) —4—-71 x >=0, -cont < 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^(afcflM]SCLD 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 | lgfinHi(š)bJ][M]lfi[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^(afcflM]SCLD 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 c) a) b) 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 Iskanje zaporedja montažnih opravil sestavljata dva logična koraka, ustvarjanje vseh možnih (smiselnih) zaporedij in med njimi iskanje najboljšega zaporedja. V smislu predstavitve vseh možnih montažnih zaporedij (oz problemskega prostora) to pomeni ustvarjanje in potem preiskovanje grafa AND/ OR pri čemer HAP sledi zamisli t i vzvratnega sestavljanja [12] kjer poteka iskanje tako da iščemo zaporedje montažnih opravil od zadnje k prvi - torej od sestavljenega sklopa do osnovnih delov (sl. 3) Pri tem HAP uporablja dve vrsti kriterijev Sestavljivostni kriteriji zagotavljajo sestavljivost danega montažnega zaporedja optimizacijski pa ocenjujejo njeno optimalnost V okviru prvih HAP uporablja geometrijsko sestavljivost in stabilnost v okviru drugih pa modularnost (čim bolj enakomerno sestavljanje prek podsklopov) Rešitev ki jo HAP torej najde je sestavljivo montažno zaporedje ki je najbolj modularno Sam sistem tudi omogoča nadaljnjo dodajanje tako enih kakor tudi drugih kriterijev Ker je celotno iskanje algoritmično zapleteno HAP uporablja različne zamisli ki mu omogočajo da je njegova uporaba vseeno učinkovita ([4] in [6]) , Prva zamisel je ta da je preiskovanje v HAP-u izvedeno na način ki sloni na znanem heurističnem algoritmu AO* kjer oba koraka potekata sočasno oz postopek ustvarjanja in preiskovanja grafa AND/OR poteka hkrati - v skladu s hevrističnim preiskovanjem Pri tem načinu del grafa ki ni zanimiv za preiskovanje (ker postopek preiskovanja kaže da tam ni rešitve) ne ustvarimo kar bistveno prispeva k učinkovitosti celotnega sistema Druga izmed zamisli ki najbolj bistveno pripomore k učinkovitosti HAP-a , pa je način ustvarjanja vozlišč 3.1 Search for the assembly-operation sequence The search for assembly-operation sequence consists of two logical steps: the generation of all possible (feasible) sequences, and the search for the best one. In the sense of representing all possible assembly operations (i.e. the whole problem space) that means generating and then searching the AND/OR graph. In the searching process the HAP follows the so-called concept of backward planning [12], where the assembly-operations sequence planning starts with an assembled product and then goes back to the parts (Figure 3). Two criteria are used in HAP: the feasibility criterion enables the feasibility of the result assembly sequence and the optimization criterion evaluated if the solution is optimal. In HAP the geometrical feasibility and the stability are used for the first, and for modularity the second criteria (to get assembly process through subassemblies) the result of the searching with HAP is the most modular feasible assembly-operation sequence. The system allows further adding of certain criteria. Because the search process is a complex algorithmic process, HAP involves some ideas to enable the effective use of the searching system ([4] and [6]). First, the search for the best sequence is done using the known best-first heuristic algorithm AO*, where both steps, the generating process and the searching AND/OR graph, are executed simultaneously in terms of the heuristic search. In this way the part of the graph, not interesting for search (the searching process shows us there is no solution) is not generated. Because of this the system is more effective. Another idea, which supports the 03-1 f^frj^y^y qp\qn(^[V7j| I stran 12 Ml^FlMHK 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. ^BSfirTMlliC | 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 © Strojni{ki vestnik 49(2003)1,16-27 © Journal of Mechanical Engineering 49(2003)1,16-27 ISSN 0039-2480 ISSN 0039-2480 UDK 658.56:004.94 UDC 658.56:004.94 Izvirni znanstveni ~lanek (1.01) Original scientific paper (1.01) Ra~unalni{ko upravljanje z obdelovalnimi orodji v orodjarni, podprto s simulacijo Simulation-Aided Management of Cutting Tools in a Tool-Making Company Mihael Debevec - Toma` Perme - Dragica Noe V proizvodnih stroških orodjarn pomenijo rezalna orodja, poleg samih obdelovalnih centrov, največji delež stroškov. Po večini slabo urejeno skladiščenje ter slab pregled stanja rezalnih orodij se kaže v premajhni zasedenosti obdelovalnih centrov ter v relativno velikih stroških za rezalna orodja. Z dobro organiziranim in računalniško podprtim upravljanjem obdelovalnih orodij je mogoče te stroške zmanjšati, vendar to se vedno ni dovolj za učinkovito načrtovanje proizvodnje. Zato je namen tega prispevka osvetliti to področje, prikazati koncept računalniškega upravljanja z obdelovalnimi orodji, podprtega s simulacijo (RUOS) in predstaviti glavne značilnosti sistema RUOS, ki je plod raziskovalno-razvojnega dela laboratorija LASIM v sodelovanju s slovensko orodjarno. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: sistem upravljalni, baze podatkov, proizvodnja, simuliranje, mreže Petri) With the exception of machining centres, cutting tools are the most expensive items in the production costs of a tool-making company. Unorganised warehousing and poor monitoring of the condition of the cutting tools are still typical of such companies, and this results in the underuse of machining centres and high costs for the cutting tools. By using well-organized and computerized tool management of the cutting tools it is possible to reduce costs, but for the efficient planning of production this is still not enough. In this article we introduce the concept of Simulation-Aided Tool Management (SATM) and the main features of the SATM system, which was developed in cooperation with a tool-making company. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: management systems, database, production, simulations, Petri nets) 0 UVOD Večina orodjarn, ki izdelujejo orodja za preoblikovanje pločevine in brizganje plastike, ima posamezno proizvodnjo, za izdelavo pa uporabljajo najsodobnejše obdelovalne tehnologije in stroje. Tako se pojavlja vprašanje, kako povezati na eni strani popolnoma posebne proizvodne metode, na drugi strani pa velike stroške proizvodnje tako, da bo proizvodnja čimbolj donosna. Odgovor na to je zagotovo tudi dobro upravljanje s proizvodnimi sredstvi, med katerimi imajo obdelovalna orodja pomembno vlogo, saj so poleg samih obdelovalnih strojev tudi največji strošek. O obdelovalnih orodjih in upravljanju z njimi je bilo že veliko govora, narejenih že veliko raziskav in razvitih že veliko sistemov. Obravnavani so bili tako z organizacijskega ([1] in [2]) kakor s tehnološkega vidika ([3] in [4]), na trgu pa se dobijo tržno dostopni programi za upravljanje z orodji, na primer CoroTAS, TDMeasy, ZOLLER Toolmanager 0 INTRODUCTION Most tool-making companies still have individual methods for producing tools for sheet-metal forming and injection moulding, but for their machining they use the most up-to-date technologies and machines. The question is how to bring together the totally individual methods of production and the high costs of such an industry in such a way that the business is profitable. The solution is an appropriate production-management system in which the machining tools play a very important role, since they represent – after machining centres – the most expensive item in the production costs. There has already been much discussion about the management of cutting tools, a lot of investigations have been made in this area, and a lot of systems have already been developed. The systems were treated from the organizational ([1] and [2]) as well as from the technological point of view ([3] and [4]), and there are many programmes for tool management already available on grin^(afcflM]SCLD VH^tTPsDDIK stran 16 Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management in drugi [5]. Vendar so redke orodjarne, ki so tak sistem uvedle in ga učinkovito uporabljajo v praksi, in to kljub temu, da se v orodjarnah zavedajo, da so stroški za obdelovalna orodja preveliki in da so stroji zaradi neustrezne logistike orodij slabše izkoriščeni. Razlogov za tako stanje je več, glavni pa se kažejo v tem, da so orodjarne tipično posebna proizvodnja s svojimi posebnimi zahtevami in da kupljeni sistemi za upravljanje z orodji ne rešujejo organizacijskih problemov, saj so bolj ali manj namenjeni le upravljanju s podatki o orodjih. Tudi na splošno informacijske tehnologije same ne morejo reševati organizacijskih problemov, lahko pa dobro organiziran sistem podprejo, da je še bolj učinkovit. Pomemben razlog pa je tudi cena komercialno dostopnih sistemov in dejstvo, da ga je treba prilagoditi potrebam posameznih orodjarn in povezati z njihovo znano informacijsko tehnologijo. Da bi osvetlili ta vprašanja predvsem z organizacijskega, se pravi logističnega vidika, in da bi postavili ogrodje sistema za upravljanje z obdelovalnimi orodji, ki bi bil prilagojen potrebam orodjarn, ter ga uvedli v prakso, je nastal projekt Računalniško upravljanje z obdelovalnimi orodji (RUO) [6]. Rezultati tega projekta so bili podlaga za koncept računalniškega upravljanja z obdelovalnimi orodji s podporo simulacije (RUOS), katerega namen v praksi je zmanjšanje stroškov za nakup in vzdrževanje obdelovalnih orodij, povečanje izkoriščenosti obdelovalnih strojev ter s tem povečanje dejanske zmogljivosti orodjarne ob ohranjenih enakih preostalih obratovalnih stroških ter povečanje zanesljivosti izpolnjevanja naročil. 1 KONCEPT RUOS Koncept RUOS je osredotočen predvsem na upravljanje z obdelovalnimi orodji v oddelku z računalniško krmiljenemi centri (RK) obdelovalnimi centri, saj je tam izredno pomembno, da so obdelovalna orodja pripravljena v pravem trenutku in da so s tem stroji čimbolj izkoriščeni, se pravi, dačim več časa delajo in ne čakajo na obdelovance ali orodja. Glede na to, da se vpenjanju ali prevpenjanju obdelovancev na stroju skoraj ne moremo izogniti, pa so lahko orodja že prej pripravljena in shranjena v zalogovniku orodij na samem stroju ali pa v vmesnem skladišču poleg njega. Da bi ugotovili, kako poteka delo, povezano z obdelovalnimi orodji, kakšno je stanje orodne logistike in katere so informacije, povezane z njimi, je bila narejena analiza, katere rezultati so bili podlaga za določitev želenega načina dela. the market: for example, CoroTAS, TDMeasy and ZOLLER Tollmanager [5]. Still, it is hard to find a tool-making company that has introduced a tool-management system into its production in spite of an awareness that the costs of cutting tools are too high, and the machining centres are not used as they could be because of inappropriate tool logistics. There are several reasons for this situation, but the main one is that tool shops tend to be based on individual forms of production that have particular demands. This means that the purchased tool-management system does not solve the organizational problems because these systems are designed only for the management of cutting-tools data. In general, information technologies cannot solve organizational problems; however, they can support a well-organized system in becoming more efficient. An important reason for this also lies in the price of commercially available systems – which is not negligible – and the fact that such a system has first to be adapted to the requirements of a particular production and integrated within existing information technologies. The aim of the project called Computerized Tool Management (CTM) [6] is to help answer some of the questions of organizational, i.e. the logistical, point of view of cutting tools, and to develop the framework of an advanced tool-management system. This system should be adaptable to the needs of tool shops and should be initiated in practice. The results of the CTM project were used as a base for the new concept called Simulation-Aided Tool Management (SATM). The practical aim of SATM is to reduce the purchasing and maintenance costs of cutting tools, to increase the efficiency of machining centres with other fixed production costs (and with that, also the actual capacity of the tool-making company) and to increase the reliability with which orders are accomplished. 1 THE CONCEPT OF SATM The concept of SATM is focused on tool management for CNC machining centres, because in these facilities it is very important that the cutting tools are prepared for machining at the right time, and that the machining centres are used as much as possible, e.g. the cutting tools work most of the time and do not wait on the work-piece or cutting tools. If clamping or re-clamping of the work-piece on machining centres is unavoidable, the cutting tools can be prepared beforehand and stored on the machining centre or in the buffer nearby. To find out the present course of the work and the state of the tool logistics as well as the information connected with them, an analysis was made, the results of which were a basis for the definition of the desired mode of work. | lgfinHi(š)bJ][M]lfi[j;?n 03-1______ stran 17 I^BSSIfTMlGC Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management 1.1 Želeni način dela Na podlagi pogovorov s tehnologi, programerji, operaterji ter vodji proizvodnje in delavnice v orodjarni se je izoblikovalo želeno stanje, ki se da povzeti v naslednjih točkah: - Tehnolog in programer programov števislkega krmiljenja (ŠK) izbirata orodja iz sedanje zaloge orodij, pri čemer so jima na voljo potrebni tehnološki podatki, parametri obdelav iz katalogov, parametri obdelav, ki so bili nastavljeni med samo obdelavo, in stanje, mesto nahajanja in razpoložljivost posameznega orodja. - Izbrana orodja naj bi rezervirali, kar pomeni, da bi za vsak izdelek določili potrebno količino orodij in, če jih ne bi bilo dovolj, bi jih lahko pravočasno naročili. - Poleg števila porabljenih orodij za vsak izdelek naj bi shranjevali tudi podatke o obdelovalnih parametrih, ki so bili predpisani, in njihove morebitne spremembe med samo obdelavo. - Iskanje orodij v kartoteki ali pa v seznamu sedanjih orodij naj poteka tako po njihovih glavnih značilnostih kakor tudi po oznaki orodja in kataloški številki proizvajalca. Za boljši prikaz naj bodo seznami opremljeni s slikami posameznega orodja. - Orodja, ki se ne uporabljajo, naj bodo shranjena na enem mestu, in sicer v osrednjem skladišču orodij (npr. v regalnem skladišču), ki ga upravlja en operater. Operaterji na strojih si jih lahko tudi sami izposojajo, s tem da se sproti zapisuje izdajanje in skladiščenje orodij. - Orodja, ki so določena za uporabo v določenem dnevu, se prej pripravijo, kar lahko naredi operater skladišča. Če pride do obrabe ali loma orodja med obdelavo, lahko to stori tudi operater stroja, če je operater skladišča prezaposlen ali odsoten. - Vsi podatki o lastnostih nastavljenega orodja se zapišejo in vnesejo v krmilnik obdelovalnega stroja, ko se določeno orodje uporabi, ali pa ob polnjenju zalogovnika za orodja. Naštete so le najpomembnejše značilnosti želenega dela z orodji, ki so bile osnova za snovanje sistema za računalniško upravljanje z obdelovalnimi orodji v orodjarni(RUOS). 1.2 Koncept RUOS RUOS je sistem, s katerim načrtujemo, krmilimo in nadzorujemo tok obdelovalnih orodij in njihove informacije v orodjarni. Aktivnosti, ki jih sistem pokriva, so naslednje: - izbira rezalnih orodij in rezalnih razmer, - nakup in skladiščenje sestavljenih orodij ali njihovih delov, - montaža in nastavljanje orodij, ^BSfirTMlliC | stran 18 1.1 Desired mode of work On the basis of many discussions with technologists, programmers, operators and workshop chiefs, the desired conditions were obtained and are listed below: - The technologist and the NC programmer choose the cutting tools from the existing tool store and they have to have at their disposal the required technological data, the machining parameters from catalogues, the machining parameters which were set during machining and the condition, the location and the availability of an individual cutting tool. - The selected cutting tools should be reserved beforehand, which means that the required quantity of each cutting tool should be anticipated and if not enough of them are available in the workshop then they can be ordered in time. - In addition to the number of cutting tools used for each product the machining-parameters’ data that was prescribed should also be stored as well as their eventual changes during machining. - Searching for cutting tools in the card index or in the list of existing tools should be based on their characteristics as well as on the cutting-tool designation and the producer’s catalogue number. For a better review, lists should be equipped with images of individual cutting tools. - Cutting tools that are not in use should be stored at a single location, at the central cutting-tool warehouse (in an automatic shelf warehouse), managed by a single operator. Operators at machining centres can lend cutting tools, but they must note down every time a tool is removed or returned to storage. - Cutting tools that are required for use on a particular day are given a preliminary preparation, and this is the warehouse operator’s duty. If the tool wears out or breaks during machining each machine operator can do the preparation if the warehouse operator is busy or absent. - All data about a particular cutting tool’s attributes are written down and entered in the controller of the machining centre when a defined cutting tool is in use or at a cutting tool’s magazine filling. Only the most significant requirements that contribute to the planning of the system for Simulation-Aided Tool Management (SATM) are included. 1.2 Concept SATM SATM is a system for planning, controlling and monitoring a cutting tool’s flow as well as the information flow in a tool-making company. The system covers activities like: - tool and machining-condition selection, - purchasing and warehousing of the cutting tools and their parts, - assembly and presetting of cutting tools Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management - transport orodij na obdelovalne stroje, - posodabljanje podatkov o obrabljenosti in stanju orodij, - čiščenje, demontaža in pregled orodij in njihovih sestavnih delov, - vzdrževanje razalnih orodij in njihovih sestavnih delov, - ponovno skladiščenje orodij ali njihovih delov. Ker je ta krog uporabe zelo dinamičen, je zanj potrebna računalniška podpora, saj lahko le z njeno uporabo spremljamo dejansko stanje in razpoložljivost posameznega orodja ali delov v orodjarni, kar je za načrtovanje proizvodnje in sprejemanje naročil bistveno. Sistem je zasnovan na splošnem modelu sistema za upravljanje z orodji [5] in obsega bazo podatkov orodnih kart, delov orodij in sestavljenih orodij. Dodatni uporabniški programi skrbijo za uporabniško primeren vnos in iskanje podatkov v bazi, za načrtovanje in krmiljenje poti in terminov orodij v orodjarni ter za nadzor stanja orodij. Sistem je načrtovan sicer za določeno orodjarno, vendar pa je odprt in prilagodljiv katerikoli orodjarni. V konceptu so bile opredeljene, pri razvoju pa so bile vodilne pomembne značilnosti sistema RUOS, te so: - Odprtost, ki omogoča preprosto prilagoditev ali razširitev sistema posebnim zahtevam posameznih orodjarn. - Modularnost, ki omogoča preprosto sestavo želenega sistema (aplikacije za vodenje razvoja orodij in rezalnih razmer, za nadzor obrabe orodij in za napovedovanje razpoložljivosti so posebni moduli, ki se lahko poljubno dodajo osnovnemu modulu). - Uporabniška primernost (uporabniški vmesnik), ki ji je posvečena posebna pozornost, saj je od enostavnosti uporabe (na primer vnašanja in iskanja podatkov) odvisna uspešnost uvajanja sistema v prakso (človeški dejavnik). - Avtomatsko vnašanje podatkov, kjer je to le mogoče. Tako porabi operater na stroju, pri nastavljanju ali montaži orodij in tudi pri skladiščenju kar najmanj časa za vnašanje ali iskanje podatkov. - Sprotni in točni podatki o stanju in mestu orodij v orodjarni, ki se uporabljajo pri načrtovanju proizvodnje in načrtovanju tehnologije (programiranje ŠK). - Integracija nadzora obrabe orodij v sistemu za upravljanje z orodji, saj je to podatek, ki poleg kraja in razpoložljivosti najbolje popiše stanje posameznega orodja v sistemu. - Sistem za napovedovanje uporabe orodij, ki temelji na tehniki simuliranja diskretnih sistemov, saj lahko le z njo na podlagi predvidenega proizvodnega načrta in znanih postopkov obdelave dovolj natančno določimo, kakšno bo stanje sistema v prihodnje. - transport of the cutting tools at machining centres, - updating of information about cutting-tool usage and condition, - cleaning, disassembly and inspection of cutting tools and their parts, - maintenance of cutting tools and their parts, - resume warehousing of cutting tools or their parts. Because this life-cycle is very dynamic, computer support is required. Only with a computer-based system can the actual condition and availability of a particular cutting tool, or its parts, in a tool shop be obtained online. This is essential for production planning and the receiving of orders. The system is designed on a common model of a system for tool management [5], and includes a tool card database, parts of tools and assembled tools. Additional user programs take care of user-type entering and searching data in the database, for planning and course control and tool terms in a tool shop and for monitoring the cutting tool’s condition. The system has been planned for a specific tool-making company, but it is still open and adaptable to any tool-making company. The essential characteristics that were considered and followed during the design of the SATM’s system are: - Openness, which enables simple adaptation or system widening to the specific demands of separate tool-making companies. - Modularity, which enables the simple composition of a desired condition (applications for the history of the cutting tools’ management and machining conditions, monitoring of the cutting tools’ wear and modules for predicting availability, which can be easily connected by an elementary module). - User friendliness (human-machine interface), to which special attention is paid because the efficiency of the SATM system depends on the simplicity of its use (for example, data entering and searching). - Automatic data entry, whenever possible, so that the operator at the machining centre uses the minimum time during presetting or assembly or during warehousing for the entering or searching of data. - Continuous and correct data about the cutting tool’s condition and its place in the tool shop, both of which are used for production planning and technology planning (NC programming). - Integration of tool-wear monitoring into the system for tool management. This is the information, which in addition to location and availability, best describes the condition of a particular cutting tool in the system. - System for predicting a cutting tool’s usage, which is based on the simulation technique of discrete systems. Only with this can we, on the basis of the expected production plan and the known machining procedure, define sufficiently accurately what will be the condition of the system in the future. | lgfinHi(š)bJ][M]lfi[j;?n 03-1______ stran 19 I^BSSIfTMlGC Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management - Vodenje “razvoja” uporabe, obrabe in uporabljenih rezalnih razmer je potrebno tako za kasnejšo analizo toka orodij kakor tudi za analizo in izbiro orodij in rezalnih pogojev. 1.3 Zgradba sistema RUOS Na podlagi želenih lastnosti sistema RUOS je bil razvit osnovni koncept njegove zgradbe, ki temelji na tehniki baz podatkov in simulacije in jo sestavljata dva modula, in sicer: - osnovni modul, ki obsega podatkovno bazo vseh elementov rezalnih orodij, prav tako pa tudi sestavljenih orodij v orodjarni, - modul za napovedovanje razpoložljivosti rezalnih orodij. 1.3.1 Osnovni modul Osnovni modul je dejansko podatkovna baza, ki vključuje vse tehnične podatke, trenutni kraj in trenutno stanje posameznega rezalnega orodja v orodjarni. Modul je urejen tako, da ima vsako posamezno orodje enoznačno določeno prepoznavno številko. Sestavljena orodja so prepoznavna pod prepoznavno številko držala orodja, vsak na novo vnesen del v sistem pa dobi novo še ne uporabljeno prepoznavno številko. Deli, ki so izrabljeni in so zato izločeni iz sistema, “odnesejo” prepoznavno številko (PŠ) s seboj, tako da le-ta ne more biti uporabljena za označitev novih delov. Podatki o različnih elementih orodij, na primer držala, adapterji, svedri, frezala, so shranjeni v različnih preglednicah z namenom, da je struktura podatkov zmanjšana na najmanjšo mero. Poleg teh preglednic je v sistemu ustvarjena preglednica vseh elementov v sistemu, v kateri so shranjeni podatki o PŠ, tipu, stanju ter lokaciji posameznega elementa. Forme in poizvedbe so v osnovnem modulu izoblikovane na uporabniško primeren in učinkovit način. To je mogoče izvesti z uporabniškim vmesnikom, ki vključuje uporabo črtne kode ter posebnih nosil PŠ za vse sestavne dele orodij. Pomemben del osnovnega modula je tudi preglednica vseh sprememb. V tej preglednici se zapisujejo vse spremembe pomembnih značilnosti za vsak sestavni del ali element. Tako je mogoče z uporabo te preglednice pridobiti stanje poljubnega rezalnega orodja v poljubnem trenutku preteklosti. Prav tako ta preglednica zagotavlja podatke o vodenju popolnega razvoja za vsak posamezen element in je pomembna kot vir podatkov za kasnejše analize. 1.3.2 Modul napovedovanja razpoložljivosti Modul napovedovanja porabe orodij temelji na zamisli, ki pravi, če je mogoče iz preglednice ^BSfirTMlliC | stran 20 - Managing the “history” of usage, wearing out and the applied machining conditions are needed for later analysis of the cutting tool’s flow as well as for analysis and selection of the cutting-tools and the machining conditions. 1.3 Developed tools of SATM Based on the desired characteristics of the SBTM system, a conceptual solution has been proposed that is based upon a database and a simulation technique. It consists of two modules: - a basic module that includes a database of all tool elements and parts as well as the assembled tools in the workshop, - a module for predicting the cutting tools’ availability. 1.3.1 Basic module The basic module is actually a database with all the data relating to the technical specification, the location and the temporary condition of the cutting tools in the workshop. It is organised in such a way that each part of the tools has a unique identification (ID) number. The assembled tools take over the identification number of the tool holder and each new part of the tools gets a new identification number. The parts that are worn out and removed from the system take the ID number with them, so it cannot be used for any new parts. The data of different types of parts, such as tool holders, adapters, drills or milling borers, for example, are recorded in different tables, so the data structure is reduced to a minimum. Besides these tables, there is also a table of all the elements in the system, where the ID, type of element, condition and location of the element are recorded. The forms and queries of the basic module are organised in a user-friendly way. With the implementation of barcode readers and special ID holders for all the parts or elements, the human-machine interface is as efficient as possible. The important part of the basic module is the table of all the changes. In this table all the changes to any significant characteristics of every part or element in the database are recorded. In this way, from any state of the database, previous states can be restored. In fact for each element the whole history is recorded and can be implemented for analysis. 1.3.2 Predicting module The predicting module is based on the idea that if any previous state of the tools in the system Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management sprememb dobiti podatke o stanju sistema za poljuben čas v preteklosti, je mogoče za znano preglednico sprememb dobiti tudi stanje v prihodnosti. Iz tega stanja pa je mogoče napovedati razpoložljivost rezalnih orodij v prihodnosti. Toda vprašanje je, kako dejansko dobiti preglednico sprememb vnaprej. Ena od možnosti je z uporabo simulacije, saj je na podlagi poznanega proizvodnega načrta, terminskega načrta, programov ŠK ter obdelovalnih parametrov mogoče “dejansko” proizvodnjo simulirati. Tako je mogoče dobiti podatke o razpoložljivosti in stanju rezalnih orodij za določeno časovno obdobje vnaprej. S simulacijo proizvodnje lahko tako dobimo podatke o potrebnih rezalnih orodjih. Če vsebuje simulacijski model toka elementov v orodjarni tudi tok rezalnih orodij, potem so aktivnosti, ki so potrebne za podporo tega toka, neposredno povezane s can be obtained using the table of changes, then any future state can also be obtained if the recorded changes are known. From this the availability of tools during a particular period in the future can be predicted. However, there is the question of how the table of changes can be obtained in advance. One approach is to implement a simulation technique. If the production plan, scheduling, NC programmes and operating parameters are known, “real” production can be simulated in advance. So the future state of the system can be obtained for the period of time when we want to know the availability and condition of the cutting tools. So the simulated production can be a generator of requirements for the cutting tools. If the simulation model of the part flow on the shop floor is extended with cutting-tools flow, then the activities program ŠK NC program načrtovanje scheduling stanje status RO-ji CTs surovec part izdelek finished part — podatki o RO information about CT NC program . zahteve po RO-jih requirements " of CTs RO-ji CTs ČV RK1 ... RKn HR CNC1 ... CNCn Preglednica sprememb Table of changes 1 Aktivnost Activity ....... ....... ....... ....... ....... Sredstva Resources Sredstva Resources Sredstva Resources ČV HR Sredstva Resources RO - rezalno orodje CT - Cutting Tool ČV - človeški viri HR - Human Resources Sl. 1. Aktivnosti, ki podpirajo tok rezalnih orodij in preglednica sprememb Fig. 1. Activities supporting the cutting-tools flow and the table of changes Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management spremembo podatkov v podatkovni bazi orodij. Ta postopek je dejansko način za ustvarjanje preglednice sprememb (sl. 1), s tem da mora biti v tem primeru simulacijski model povezan ali pa integriran s podatkovno bazo. 2 SIMULACIJA NA PODLAGI RAZŠIRJENIH PETRIJEVIH MREŽ Na trgu je dandanes mogoče dobiti več simulacijskih programov in jezikov, ki pa niso praktični za preprosto uporabo, niti jih ni mogoče preprosto integrirati v sistem podatkovnih baz, kar sta zahtevi koncepta RUOS. Zato je bilo treba razviti poseben modul, s katerim lahko uporabnik transparentno izvaja simulacijo. Jedro tega modula je teorija Petrijevih mrež, saj so le-te na splošno zelo primerno orodje za modeliranje in simulacijo diskretnih sistemov in so tudi zelo dobro matematično podprte. 2.1 Petrijeve mreže Od njihovega nastanka leta 1967 so osnovno teorijo Perijevih mrež nenehno razvijali in razširjali z namenom, da bi lahko z njimi čim bolje popisali in analizirali strukturo in obnašanje diskretnih sistemov ([7] in [8]). Prednost Petrijevih mrež se pokaže predvsem pri modeliranju, saj je to preprosto in močno orodje, ki ima tudi matematično podlago in s katerim lahko razumljivo popišemo strukturo opazovanega sistema. Šibkejša stran pa je analiza dinamičnega obnašanja opazovanega sistema, saj analitične rešitve v praktičnih primerih hitro pridejo do svojih meja. Tako ostane za analiziranje dinamičnega obnašanja diskretnega sistema tehnika diskretne simulacije praktično najbolj sprejemljiva. Sicer je simulacija na podlagi modela aktivnosti (Petrijeve mreže) v praksi najmanj uporabljana, saj naj bi bila počasnejša od simulacije na podlagi modela dogodkov in procesov, je pa za uporabo, pri kateri se med samo simulacijo poleg parametrov spreminja tudi model in pri kateri je potrebno sodelovanje drugih programov ali pa uporabnika, bolj primerna [9]. V bistvu je Petrijeva mreža (PM) usmerjen, obtežen, dvostranski graf z dvema tipoma vozlišč, in sicer z mesti in prehodi (teoretične osnove razširjenih Petrijevih mrež so podane v [10]), v pričujoči uporabi pa lahko mesta uporabimo kot stanje sistema, prehode pa kot aktivnosti, ki vodijo iz enega stanja v drugo. Mesta na vhodu v aktivnost lahko razumemo kot pogoje in mesta na izhodu iz aktivnosti kot posledico izvajanja te aktivnosti. Iz take opredelitve že lahko intuitivno sklepamo, da obstaja formalna povezava med preglednico sprememb, ki je jedro sistema RUOS, in načinom modeliranja s Petrijevimi mrežami. ^BSfirTMlliC | stran 22 needed to support this flow are directly connected with the changing of information in the tool database. In this way the table of changes can also be obtained (Fig. 1). For this, however, the simulation has to be connected or integrated with the tool database. 2 SIMULATION BASED ON EXTENDED PETRI NETS There are many simulation programmes and languages available on the market, but they cannot be so easily integrated into the database system as the SATM concept. For this reason a special module has to be developed that enables a transparent wxecution of the simulation. The core of this module is the Petri nets’ theory, which is a very convenient tool for modelling and simulating discrete systems because it is mathematically well supported. 2.1 Petri nets The basic theory of Petri nets was developed in 1967, and since then it has been constantly developed and enhanced with the aim of using it to describe and analyse the structure and behaviour of discrete systems as well as possible ([7] and [8]). The advantage of using Petri nets is their modelling ability, they are easy to use and are powerful tools that make it possible to describe an observed system’s structure. Their weak point is an ability to analyse the dynamic behaviour of an observed system because of the limitation of analytical solutions for practical cases. The discrete simulation technique is, in practice the most appropriate way to obtain the dynamic behaviour of a discrete system. In practice, the simulation on the basis of the activity model (Petri nets) is not often used because it would be slower than event-or process-based simulations. But in cases when the parameters and model are changing during the simulation process and the interaction of other programmes or users is needed, the activity-based simulation is more convenient [9]. In the basic theory, the Petri net (PN) is a directed, weighted, bipartite graph consisting of two types of nodes, called places and transitions (the theoretical basis of extended Petri nets can be found in [10]). In the present case, places represent the state of the system and transitions represent activities that lead from one state to another. Input places of particular activity can be understood as conditions, and output places of activity as consequences of activity execution. From this definition we can infer intuitively on a formal connection between the table of changes, that is the core of the SATM system, and the modelling method with Petri nets. Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management a) ŠK /NC program ± RK / CNC (i) RK / CNC (i) RK / CNC (i) b) ŠK /NC program O (l) MP (l) ^ obdelava K^ *| obdelava K^ * RO (a) CT (a) O (l) MP (l) uo Of RO (a) RO (b) CT (a) CT (b) O (l) MP (l) O (l) MP (l) RO (b) RO (c) CT (b) CT (c) RO (c) CT (c) RK / CNC (i) O - obdelovanec MP - machninig part RO - rezalno orodje CT - cutting tool Sl. 2. Primer dela obdelave na RK stroju, predstavljen z modelom aktivnosti (a) in modelom Petrijevih mrež (b) Fig. 2. An example of CNC machining, represented by (a) activity model and (b) Petri nets’ model 2.2 PM in preglednica sprememb Preglednica sprememb je dejansko zaporedje aktivnosti v delavnici, ki so povezane s sestavljenimi orodji ali njihovimi elementi. Če pogledamo na primer obdelavo na RK obdelovalnem centru RK(i) z določenim orodjem(j), potem lahko diagram aktivnosti (generični diagram aktivnosti GDA) prevedemo po analogiji GDA-PM [9] v graf Petrijeve mreže (sl. 2) v razširjeni inačici, pri kateri so uporabljeni žetoni objektnega tipa z atributi, ki se med aktivnostjo lahko spremenijo. V preglednico sprememb se zapišejo samo aktivnosti in posledice (stanja na izhodu iz aktivnosti). Za primer modela na sliki 2 je preglednica sprememb prikazana na sliki 3. Izvajanje modela Petrijeve mreže oziroma simulacija poteka tako, da se v določenem trenutku izvede tisti prehod t, ki je takrat omogočen, s tem pa se spremeni stanje M v Mk+1, kar lahko zapišemo z enačbo stanja kot: 2.2 PN and table of changes The table of changes is actually a sequence of activities in a workshop that are related to cutting tools or their parts. For example, the activity diagram (generic activity diagram GAM) for a process on a CNC machining centre CNC(i) with a particular cutting tool (j) can be translated, on the basis of an analogy between GAM and PN [9], into an extended Petri nets’ graph, where an object type of tokens with attributes are implemented and can be modified during activity execution. The table of changes contains records of particular activity, and the changes related to the cutting tools (output places of an the activity). The table in Figure 3 is, for example, a table of changes for the model in Figure 2. The execution of the Petri nets’ model, e.g. a simulation, is carried out by firing the enabled transitions. In a single moment only a transition ti , which is enabled, fires, and so changes the state Mk to a new state Mk+1 , which can be written using the state equation as: Mk = Mk-1 + CT u (1), isfinKJOtJJiMiSicšn i stran 23 glTMDDC Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management aktivnost activity PŠ orodja cutting tool ID atribut 1 attribut 1 atribut 2 attribut 2 ... atribut n attribut n ... ... obdelava () cutting process () orodje j cutting tool j preostala doba trajanja orodja residual life span of cutting tool parametri obdelave cutting process parameters ... mesto v zalogovniku place in tool storage obdelava () cutting process () orodje j cutting tool j preostala doba trajanja orodja residual life span of cutting tool parametri obdelave cutting process parameters mesto v zalogovniku place in tool storage obdelava () cutting process () orodje j cutting tool j preostala doba trajanja orodja residual life span of cutting tool parametri obdelave cutting process parameters mesto v zalogovniku place in tool storage ... ... ... ... Sl. 3. Preglednica sprememb Fig. 3. Table of changes kjer sta C dogodkovna matrika in uk vektor proženja , v katerem so vsi elementi nič razen na i- tem mestu je 1, kar pove, da se je v k-tem proženju izvedel prehod ti. Proženje prehodov se ponavlja, dokler se izvajanje modela ne ustavi. Celoten potek simulacije lahko zapišemo tudi kot zaporedje prehodov: where C is the incidence matrix and uk is the firing (or control) vector with all the elements equal to zero, except for the element on the ith place, which is equal to 1. This represents to execution of the transition ti at k- firing. The firing of enabled transitions is repeated until the execution of the model is interrupted or there are no more enabled transitions. The total simulation course can also be written as a firing sequence: {u1, u2,...ud} (2), ki pripeljejo sistem iz začetnega M0 v končno stanje Md, samo izvajanje pa zapišemo z enačbo stanja kot: that brings the observed system from the initial state M0 to the final state Md. This can be written using the state equation as: Md = Md + CTluk k =1 (3). Preglednico sprememb za celoten model lahko zapišemo kot zaporedje elementov: The table of changes for the entire system can be written as a sequence of components: {{u, M}, {u, M}...{u, M}} (4), kjer nam pove uk, kateri prehod oziroma katera aktivnost se je izvedla v določenem trenutku, M pa stanje po tem izvajanju. Seveda bi bil tak zapis preobsežen in tudi nepotreben, saj nas zanimajo samo aktivnosti, ki povzročijo spremembo stanja na mestih, ki so povezana z orodji oziroma njihovimi elementi (RO(i) na sliki 2). Zato tvorimo podmnožico množice vsem prehodov: where uk represents a transition (activity) that has been executed in the instance k, and Mk represents the conditions (state) after that execution. This type of record is too extensive and unnecessary for the table of changes because the table only has important activities that cause changes to the places that are related to cutting tools or their elements (CT(i) on Figure 2). So a subset of all the transitions is determined as: T ^ {t, t,...t} 12 (5), kjer velja za vsak t, da je vsaj eno vhodno ali izhodno mesto iz P oziroma iz podmnožice množic vseh mest: where for each t it holds that at least one input or output place is from PRO, i.e. from a subset of all the places: PROc{p1, p2,...pm } (6), grin^(afcflM]SCLD VBgfFMK stran 24 Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management kjer velja za vsak p, da so v njem lahko objektni žetoni, ki pomenijo orodja ali njihove elemente. Nadalje lahko opredelimo {v1, v2, ... vl} kot zaporedje, ki ga sestavljajo samo tisti elementi zaporedja {u, u, ... ud}, katerih prehodi t so iz množice T. V preglednici sprememb stanja orodij tudi ne potrebujemo stanja celotnega sistema M, temveč samo stanje izhodnega mesta pePRO prehoda t, ki se je izvedlo v proženju k, kar zapišemo z rk. Iz tega lahko zapišemo preglednico sprememb stanja orodij kot zaporedje elementov: which only places, with object-type tokens that represent cutting tools or their elements can be part of. A further sequence {v , v , 12 l can be de- fined, which contains only elements from the sequence {u1, u2, ... ud}, whose transitions t are from the set T. In the table of changes of the cutting tools’ state, there is no need for a record of the entire system state M, but only the state rk, which describes the condition of the output place pePRO of transition t that has been executed in the firing instance kk. So the table of changes can be determined as a sequence of elements: 11 Ker imajo vsa mesta pe P O kapaciteto 1, kar pomeni, da je lahko v določenem trenutku v takem mestu samo en objektni žeton, je stanje izhodnega mesta rk opredeljeno kar z žetonom oziroma z atributi tega žetona, ki dejansko pomenijo stanje določenega orodja ali elementa orodja. 2.3 Izvajanje simulacije Opisana povezava modela Petrijeve mreže in preglednice sprememb je formalna in tudi matematična osnova za razvoj simulacijskega sistema, s katerim lahko zgradimo model in izvajamo simulacijo, pri čemer se ustvari tudi preglednica sprememb. Jedro sistema je simulacijski programom PN_EXE [9], ki izvaja na teoriji razširjenih Petrijevih mrež osnovan model opazovanega sistema. Za simulacijo delavnice in toka orodij je bil PN_EXE razširjen z objektnimi žetoni in z možnostjo generiranja preglednice sprememb. 3 PRIMERI IN UGOTOVITVE Preizkus delovanja postavljenega koncepta je bil izveden na preprostem primeru iz prakse, ki obsega regalno skladišče orodij in delo operaterja, ki jemlje in vrača orodja v skladišče. Tak preprost primer je bil uporabljen predvsem zato, ker so bili na voljo dejanski podatki o stanju orodij v regalnem skladišču in preglednica sprememb za obdobje treh mesecev, ki jo je v dejanski orodjarni izpolnil za omenjeno obdobje operater sedanjega regalnega skladišča. Za preizkus sta bila izdelana baza podatkov obdelovalnih orodij (kot sistem RUO) in simulacija delovanja opisanega primera (kot modul za napovedovanje razpoložljivosti obdelovalnih orodij). Za bazo podatkov je bil uporabljen MS Access, aplikacija pa je bila napisana s programskim jezikom Visual Basic. Preizkus je bil sestavljen iz ažuriranja baze podatkov obdelovalnih orodij na podlagi prejšnjega {{v1, r}, { v2, r}...{ vl, rl}} ll (7). The capacity of all the places from P is 1, so in a particular place pePRO, only one object’s token can be present at a time. From that the output place condition rk is determined with a token or attributes that actually represent the condition of a particular cutting tool or its elements. 2.3 Executing the simulation The described relationship between the Petri-net model and the table of changes is a formal and also a mathematical basis of the developed simulation system, which is used for model generation and simulation execution, where the table of changes is also obtained. The core of the system is the simulation programme PN_EXE [9] that executes the simulation model of the observed system based on extended Petri nets’ theory. For the workshop and cutting-tools flow simulation the PN_EXE has been extended with object tokens, which represent cutting tools, and have te ability to generate the table of changes. 3 EXAMPLES AND DISCUSSION The SATM concept was tested on a simple practical example that includes a cutting-tools warehouse and an operator that takes cutting tools from and back to the warehouse. This simple example was used as a test bed because we had the actual data about cutting tools in the warehouse as well as the table of changes for a period of three months, which was completed by the operator of the warehouse. For a test, a database of cutting tools (as a CTM system) and the simulation model of the described example (as a module for forecasting the availability of cutting tools) were completed. For the database management system we used MS Access, and the application program were written in the Visual Basic program language. The test was conducted by updating the database of the cutting tools on the basis of the previ- (SfinKjB)bJJ[M]Sl[JLI] I stran 25 glTMDDC Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management stanja ter dejanske preglednice sprememb in nastajanja preglednice sprememb s simulacijo dela operaterja. Glavne rezultate preizkusa in izkušnje, pridobljene pri razvoju sistema RUOS in pri praktični uporabi baze podatkov obdelovalnih orodij v orodjarni (RUO), lahko strnemo v naslednje ugotovitve: - Baza podatkov obdelovalnih orodij se je pravilno ažurirala, saj so bili podatki o obdelovalnih orodjih v bazi enaki dejanskemu stanju orodij v sistemu. To dokazuje uporabnost izdelanega algoritma. - Tudi na temelju simulacije nastala preglednica sprememb je bila enaka dejanski preglednici sprememb, kar potrjuje pravilnost simulacijskega programa glede na postavljeno matematično formulacijo in potrjuje veljavnost modela glede na dejanski opazovani sistem. - Za industrijsko uporabo bo potrebno razviti koncept in algoritme uporabiti na primernejšem informacijskem sistemu kakor je MS Access, tako da ga bo moč integrirati z veljavnimi informacijskimi tehnologijami posamezne orodjarne in tako uporabiti že znane podatke in tudi drugim uporabam omogočiti dostop do podatkov o obdelovalnih orodjih. - Sistem RUOS bo glede na izkušnje s sistemom RUO za regalno skladišče v praksi za uporabnika uspešen le z učinkovitim vmesnikom, saj bo deloval pravilno le, če bo zagotovljeno dosledno vnašanje in ažuriranje podatkov. 4 SKLEPI Koncept računalniškega upravljanja z obdelovalnimi orodji je nastal na podlagi potreb in želenega načina dela v orodjarnah. Kljub njihovi enostavnosti in razumljivosti je orodjarna oziroma njen proizvodni del tako zapleten sistem, da je težko preprosto razviti in vpeljati tak informacijski sistem, ki bi izpolnil vse potrebe in želje. Kljub temu pa rezultati dosedanjega dela pri razvoju sistema RUOS kažejo, da bo mogoče postavljen koncept tudi uresničiti. Seveda pa bo treba imeti za uvajanje sistema RUOS v orodjarne poleg znanja in izkušenj tudi zaupanje potencialnih uporabnikov, da bo njegova uvedba v orodjarnah res reševala problematiko orodne logistike. Zato je treba hkrati z izdelavo industrijske različice sistema RUOS razviti tudi sistem, s katerim se bo lahko prikazalo, da obstaja v orodjarnah veliko pomanjkljivosti, za katere niti ne vejo, ker nimajo o tem ustreznih podatkov, in ki jih je z uvedbo sistema RUOS mogoče odpraviti. ^BSfirTMlliC | stran 26 ous state and the actual table of changes, and by generating the table of changes with the simulation of the operator’s work. The results of the test and the experience gained by developing the SATM system and by practical use of the cutting tools’ database in the tool-shop (CTM) can be summarised as follows: – The database of cutting tools was updated correctly since the data of the cutting tools in the database were the same as the actual state of the cutting tools in the warehouse. This proves the applicability of the elaborated algorithm. – The table of changes generated with the simulation was identical to the actual table of changes, which confirms the simulation program regularity regarding the set of the mathematical formulation and confirms the model validity regarding the actual observed system. – For an industrial application it will be necessary to apply the developed concept and algorithms on a more suitable information platform than MS Access, so that it will be possible to integrate the SATM system within the existing information technologies of a particular tool-shop. In this way the SATM can use the necessary data from other applications and give other applications access to the cutting-tools data. – According to our experiences with the SATM if will only be successful in practice if there is an efficient user interface. In other words, the SATM system will operate properly only if consistent recording and updating of the cutting-tools data is ensured. 4 CONCLUSIONS The concept of computerized tool management was developed on the basis of requirements and the requested way of working in tool shops. In spite of its simplicity and comprehensibility, the tool shop, or its production part, is a very complex system. An informational system that would satisfy all the needs and requests is hard to develop and introduce. In spite of this the results of the SATM system development indicate the possibility of realizing the planned concept. In order to introduce the SATM system in tool shops it will certainly be necessary to make potential users of the SATM system believe will help it them to solve problems of cutting-tool logistics. In parallel with the development of an industrial version of SATM it is necessary to develop a system that will point out the existence of deficiencies in tool shops, which are unknown because of the unsuitable data and which could be easily suppressed by initiating the SATM system. Debevec M., Perme T., Noe D.: Ra~unalni{ko upravljanje - Simulation-Aided Management 5 LITERATURA 5 REFERENCES [1] Butala, P. (1991) Sistem orodij za modularno računalniško integrirane obdelovalne sisteme. Doktorska disertacija, Fakulteta za strojništvo, Univerza v Ljubljani, Ljubljana. [2] Miller, G. (1995) Total tool management: cracking the cost spiral, Machinery and Production Engineering, 153, 3898, UK, 20-21. [3] Muršec, B. F Čuš, J. Balič (2000) Organization of tool supply and determination of cutting conditions. Journal of Materials Processing Technology Vol. 100, Issues 1-3, Amsterdam, 241-249. [4] Maropoulos, P. G. (1996) Integrated tool life prediction and management for an intelligent tool selection system. Journal of Materials Processing Technology Vol. 61, Issues 1-2, Amsterdam, 225-230. [5] Debevec, M. (2000) Logistika obdelovalnih orodij v orodjarni. Diplomska naloga, Fakulteta za strojništvo, Univerza v Ljubljani, Ljubljana. [6] Noe, D., T. Perme, M. Debevec (2002) Računalniško upravljanje orodij RUO-1. Končno poročilo: RR faza projekta, Fakulteta za strojništvo, Univerza v Ljubljani, Ljubljana. [7] Murata, T. (1989) Petri nets: properties, analysis and applications. Proceedings of the IEEE, Vol. 77, No. 4, 541-580. [8] Peterson, L. J. (1981) Petri net theory and modelling of systems. Prentice-Hall International, Englewood Cliffs, ZDA [9] Perme T (1999) Ein neues Simulationskonzept zur rechnergestiitzten Planung von Montagesystemen. Dissertation, Technische Universitat Wien. [10] Perme, T (2003) Načrtovanje izdelovalnih sistemov, podprto s simulacijo. Strojniški vestnik, 49(2003)1, str. 28-49, Ljubljana Naslov avtorjev: Mihael Debevec dr. Tomaž Perme prof.dr. Dragica Noe Fakulteta za strojništvo Univerza v Ljubljani Aškerčeva 6 1000 Ljubljana miha.debevec@fs.uni-lj.si tomaz.perme@fs.uni-lj.si dragica.noe@fs.uni-lj.si Authors’ Address: Mihael Debevec Dr. Tomaž Perme ProfDr. Dragica Noe Faculty of Mechanical Eng. University of Ljubljana Aškerčeva 6 1000 Ljubljana, Slovenia miha.debevec@fs.uni-lj.si tomaz.perme@fs.uni-lj.si dragica.noe@fs.uni-lj.si Prejeto: Received: 22.1.2003 Sprejeto: Accepted: 29.5.2003 Odprt za diskusijo: 1 leto Open for discussion: 1 year (SfinKjB)bJJ[M]Sl[JLI] I stran 27 glTMDDC © Strojni{ki vestnik 49(2003)1,28-40 © Journal of Mechanical Engineering 49(2003)1,28-40 ISSN 0039-2480 ISSN 0039-2480 UDK 658.52.011.56:004.94 UDC 658.52.011.56:004.94 Izvirni znanstveni ~lanek (1.01) Original scientific paper (1.01) Na~rtovanje izdelovalnih sistemov, podprto s simulacijo Simulation-Aided Planning of Manufacturing Systems Toma` Perme Naraščajoča zapletenost sodobnih proizvodnih sistemov zahteva računalniško podprta orodja, s katerimi bo lahko načrtovalec bolje izkoristil svoje znanje, izkušnje, ustvarjalnost in intuicijo. Pomemben del teh orodij je simulacija, saj je le z njo mogoče pridobiti “dejanske” lastnosti izdelovalnih in montažnih sistemov že v fazi njihovega načrtovanja. Glavni del tega prispevka opisuje razvoj simulacijskega paketa (LASIMCO) za računalniško podprto načrtovanje izdelovalnih in montažnih sistemov, prikazana pa je tudi uporaba tega orodja na dejanskem primeru. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: sistemi proizvodni, planiranje računalniško podprto, proizvodnja navidezna, mreže Petri) The increasing complexity of modern manufacturing systems calls for computer-aided planning tools, which can help planners better use their knowledge, experience, creativity and intuition. Only by means of a simulation, which is a significant part of these tools, can the “real” properties of a manufacturing or assembly system be obtained during the planning phase. The main parts of this paper describe the development of a simulation package (LASIMCO) for the computer-aided planning of manufacturing and assembly systems, as well as the use of this tool in a case study. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: manufacturing systems, computer-aided planning, virtual manufacturing, Petri nets) 0 UVOD Računalniško integrirana proizvodnja (RIP - CIM) brez ljudi je samo domišljija, prav tako pa tudi sistem za načrtovanje, ki bi načrtal izdelovalni sistem na podlagi podanih zahtev brez človeške sodelave. Kratica RIP pa ima tudi bolj dejanski pomen, kakor je na primer stalno izboljševanje izdelave. V tem pomenu je treba razmišljati tudi pri razvoju in re-inženiringu izdelovalnih in tudi montažnih sistemov. Tako je pri načrtovanju proizvodnih sistemov v splošnem treba posebno pozornost posvetiti dvema stvarema: stalnemu izpopolnjevanju samih proizvodnih sistemov in orodjem, ki so v pomoč načrtovalcem, da lahko pri svojem delu izkoristijo vse svoje znanje, izkušnje, ustvarjalnost in intuicijo. Tu seveda ni nobenega navodila za razvoj takih orodij, saj ima namreč vsak preizkus svoje dobre 0 INTRODUCTION Computer-integrated manufacturing (CIM) without the need for workers and operators is a mere fiction, so too is a planning system that could design a manufacturing system on the basis of predefined requirements without only human interaction. But the abbreviation CIM can also have a more realistic meaning, like the continuous improvement of manufacturing; and in this sense the design and redesign of manufacturing as well as assembly systems need to be considered. There are, therefore, two main points to focus on: the continuous improvement of manufacturing systems and the planning of tools to assist planners in using all their knowledge, experience, creativity and intuition to accomplish the first objective as successfully as possible. There is no recipe for the development of such tools. Each attempt has its own potential and grin^(afcflM]SCLD VBgfFMK stran 28 Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning in slabe strani. Namen tega prispevka je predstaviti razvoj orodja, ki je zasnovano na zamisli navidezne izdelave in simulacije. Le ta temelji na razširjenih Petrijevih mrežah, ki omogočajo upoštevanje tako logičnih kakor tudi nekaj fizičnih lastnosti pri proučevanju načrtovanega sistema [1]. 1 NAVIDEZNA IZDELAVA IN SIMULACIJA Zamisel navidezne izdelave (NI), ki sta jo prva vpeljala Iwata in Onosato [2], rabi kot zapoved in osnovni okvir za razvoj orodij za načrtovanje izdelovalnih sistemov. Namen zamisli NI je integracija znanih modelov proizvodnje, tehnik analiziranja in oblik predstavitve v povezan, skladen in razumljiv sistem na način, ki omogoča, da se lahko preizkusijo in preverijo nove tehnike in metode načrtovanja in krmiljenja proizvodnje brez uporabe in motenj dejanskega proizvodnega sistema (DPS). Da bi to lahko dosegli, je potrebno imeti napredno znanje o proizvodnji in uporabiti napredne računske tehnike. Interdisciplinarnost je že sama po sebi vsebovana v razvoju NI, ki mora biti prilagodljiv in odprt za simuliranje različnih vrst proizvodnih sistemov na način, ki omogoča izpopolnjevanje tako dejanskega kakor tudi navideznega proizvodnega sistema. Beseda “navidezen” pomeni v bistvu to, da se aktivnosti v informacijskih in izdelovalnih procesih izvedejo v računalniku in z njim, pri čemer so sredstva in material objekti, ki so predstavljeni z informacijami. Glede na zamisel NI je lahko proizvodni sistem dejanski ali pa navidezen, predstavimo ga lahko v naslednji obliki (sl. 1) kot: dejanski fizični podsistem (DFP), dejanski informacijski podsistem (DIP), navidezni fizični podsistem (NFP) in navidezni informacijski podsistem (NIS). Iz teh štirih osnovnih razlag izdelovalnega sistema se lahko sestavijo kombinacije, ki imajo praktični pomen v dejanskem okolju. Kombinacija NFP-DIP je na primer pomembna za postavitev navideznega izdelovalnega okolja (NIO). NFP-DIP dejansko pomeni navidezni izdelovalni sistem (fizično), kjer se izdeluje navidezni izdelek v računalniku na podlagi dejanskih informacij. Pomemben del NI sta simulacija in prikaz rezultatov. Vernost navidezne izdelave je zelo odvisna od natančnosti rezultatov simulacije in privzetju dejanskosti njihove predstavitve. Rezultati simulacije morajo biti natančni in generirani v dejanskem času -načrtovalec mora najti ravnovesje med temi pogoji ob upoštevanju danih računalniških zmogljivosti. Problem je enak pri navidezni resničnosti (NR), ki jo lahko uporabimo tu kot obliko predstavitve. Privzetje dejanskosti pri uporabi NR je povezano z zmožnostjo opreme (računalnik, naglavni prikazovalnik, drawbacks. The aim of this paper is to describe one such attempt, which is based on the concept of virtual manufacturing and a simulation using extended Petri nets, in such a way that the logical as well as some of the physical properties of the investigated system can be considered [1]. 1 VIRTUAL MANUFACTURING AND SIMULATION The concept of Virtual Manufacturing (VM), which was introduced by Iwata and Onosato [2], can serve as an imperative and as the basic framework for the development of planning tools for manufacturing systems. The purpose of a VM system is to integrate the existing manufacturing models, analytical techniques and presentation forms into a coherent system in such a way that new planning and control methods and techniques can be tested and verified without disturbing the real manufacturing system (RMS). In order to achieve this, advanced knowledge of manufacturing is needed and advanced computational techniques have to be applied. Interdisciplinarity is inherent in the development of VM systems, which must be flexible and open enough to simulate different types of manufacturing systems in a way that enables the continuous improvement of real as well as virtual manufacturing processes. The term “virtual” means that the activities within the information and manufacturing process are accomplished by and within a computer, and the resources and material are the objects described and represented by the information. According to the VM concept, the manufacturing system can be either real or virtual and can be presented in the form of a real physical subsystem (RPS), a real information subsystem (RIS), a virtual physical subsystem (VPS) and a virtual information subsystem (VIS) (Fig. 1). From these four basic interpretations of manufacturing systems, combinations can be set up that have a practical significance in a real environment. The combination of a VPS and an RIS is sensible for establishing a virtual manufacturing environment (VME). In effect, VPS-RIS means a virtual manufacturing system (physically) where a virtual product is manufactured by a computer on the basis of real information. Important elements of VM include the simulation and presentation of the results. The “reality” of the VM system is closely connected with the accuracy of the simulation results and the assumption of reality in the presentation. The results of the simulation must be accurate and generated in real time; the designer must find a balance between these conditions within the given computational capacity. The problem is the same in virtual reality (VR), which can be used as a form of presentation. The assumption of reality in the use of VR is connected to the capability of the equipment (computer, head- | lgfinHi(š)bJ][M]lfi[j;?n 03-1______ stran 29 I^BSSIfTMlGC Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning zahteve/ demands načrtovanje procesov/ process planning razvoj/ developing informacijski/ information (re-)dizajniranje/ (re-)designing izdelava/ realisation delovanje/ operating oo < dejanski/ krmiljenje in zaznavanje/ real controlling and sensoring material T <3- energija/ energy B proces izdelave/ manufacturing process ^^T izdelek/ product" sredstva/ resources pred-stavi-tev / re-presen-tat-ion -E^ E metode, algoritmi, znanje in modeli informacijskih in odločitvenih procesov / methods, algorithms, knowledge and models of informational and decision process ± analiza (simulacija)/ analyzing (simulation) J X navidezni/ virtual * model procesov/ process model model izdelka/ product model model tovarne/ factory model fizični/ physical . smer življenjskega cikla/ ^^ tok informacij med dejanskim in navideznim sistemom/ * life-cycle direction ~^ information flow between real and virtual system _ tok podatkov/ ^ data information flow izmenjava podatkov med modeli in simulacijo/ ~^ data exchange between models and simulation * command and status Sl. 1. Fizični in navidezni deli informacijskih in izdelovalnih procesov [3] Fig. 1. Physical and virtual parts of the information and manufacturing processes [3] podatkovne rokavice in drugi vmesniki) za uglasitev uporabnika z navideznim okoljem. Od možnih kombinacij se lahko postavi okolje za navidezno izdelavo, ki ga sestavljajo trije osnovni modeli dejanskega izdelovalnega sistema, in sicer model izdelka, model procesov in model tovarne. Ti modeli se lahko analizirajo s simulacijo, rezultati pa predstavijo v obliki, ki se približuje dejanskosti. 2 RAZŠIRJENE PETRIJEVE MREŽE IN NJIHOVA IZVEDBA Dejanski izdelovalni ali montažni sistem (DIS) se lahko opazuje kot odprto množico osnovnih aktivnosti, ki se izvajajo posamično in ki potrebujejo za to določena sredstva, za katera se potegujejo, ter informacije, ki jih krmilijo. Te aktivnosti so potrebne za pretvorbo materiala z uporabo energije v končni mounted display, data glove and other interface devices) to attune the user to the virtual environment. From the various possible combinations, a VME can be set up containing three basic models of real manufacturing systems (RMS): the product, the process, and the factory model. These models can be analysed by simulation and the results can be presented in a form approaching reality. 2 EXTENDED PETRI NETS AND IMPLEMENTATION The real manufacturing or assembly system (RPS) can be regarded as a bug of separately executed basic activities, which require certain resources that they compete for and information they are controlled by. These activities are needed to transform material, using energy, into the final product. The resources grin^(afcflM]SCLD VBgfFMK stran 30 Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning izdelek. Sredstva, ki omogočajo procese izdelave in montaže, vključujejo opremo, to so na primer obdelovalni stroji, orodja, transportne in strežne naprave, roboti, vpenjalni pripomočki in drugo, ter ljudi, ki delajo in upravljajo s to opremo. Za modele procesov in tovarne, ki morajo opisati izvajanje osnovnih aktivnosti in sredstva, ki so za to potrebna, so na podlagi analogije in zahtev generičnega modela aktivnosti (GAM)[4] in njegovega matematičnega opisa[5], predlagane razširjene Petrijeve mreže (RPM). 2.1 Razširjene Petrijeve mreže Petrijeve mreže so bile razvite v doktorski disertaciji, v kateri je Carl Adam Petri posebno pozornost posvetil opisu vzročnih zvez med dogodki [6]. Različni raziskovalci so glede na svoje zanimanje in uporabo na različne načine opredelili mnogo teoretičnih konceptov Petrijevih mrež. Formalna opredelitev Petijevih mrež [7] z omejeno kapaciteto (mreža stanj/prehodov) [8] in razširjena s prioritetami in časom je podana kot C=(P,T,F,K,W,M,RZ) kjer: P = { p1, p2,.....p } je končna množica mest, T = {t1, t2 ,.....t } je končna množica prehodov, PnT = 0 in PuTV0 FL(PxT)u(TxP) je množica povezav, K: P —»{1,2,3, ...} vsakemu mestu opredeli kapaciteto, W: F—» {...-3,-2,-1, 1,2,3, ...} je utežna funkcija, M: P ^ {1,2,3 ...} je začetna označitev mest, R: T—» {0,1,2,..,9} vsakemu prehodu opredeli proriteta in Z: T ^ {0,1,2,3,..} vsakemu prehodu opredeli čas. Petrijeve mreže so dejansko usmerjen, utežen dvostranski graf, ki ga sestavljajo dve vrsti vozlišč, imenovana mesta in prehodi. Grafično se mesta prikazujejo z krogi, prehodi pa s črto oziroma s pravokotnikom. Mesta se povezujejo s prehodi in prehodi z mesti. Teža teh povezav je pozitivno celo število, kjer pomeni povezava med dvema vozliščema s težo k dejansko k povezav med tema dvema vozliščema. Vsako mesto ima opredeljeno tudi kapaciteto K(p), ki pomeni največje število žetonov, ki so lahko v mestu p naenkrat. Označitev pripiše vsakemu mestu nenegativno celo število in je označena z M. M je stolpični vektor reda m x 1, kjer m pomeni število vseh mest. Če je ne negativno celo število l, pripisano mestu p, potem je mesto p označeno z l žetoni. Grafično so žetoni prikazani s pikami ali s številko. Pravilo, ki pove, kdaj je neki prehod omogočen in se lahko izvede, je pravilo izvajanja in se opiše za RPM takole: .p:={t | (tp) s F} je množica vhodnih prehodov mesta p, p.: = {t | (p,t) s F} je množica izhodnih prehodov mesta p, •t:={p | (p,t) e F} je množica vhodnih mest prehoda t in t.:={p | (t,p)eF} je množica izhodnih mest prehoda t supporting the manufacturing process are composed of equipment, such as machine tools, tools, transport and handling devices, robots, auxiliary devices, etc., and people who operate and work with the equipment. For the process and factory model, which have to model the execution of the basic activities and resources needed for these executions, Extended Petri Nets (EPNs) have been proposed following an analogy and the requirements of the Generic Activity Model (GAM) [4] and its mathematical description [5]. 2.1 Extended Petri Nets Petri nets have been developed in the doctoral thesis of Carl Adam Petri, which described the causal relationships between events [6]. Many of the fundamental concepts of Petri nets were defined by different researchers with different motivations in different ways. A formal definition of a Petri net [7] with a finite capacity (place/transition net) [8] and extended with priority and time is given by as an 8-tuple, C=(P, T, F, K, W, M0, R Z) where: P = { p1, p2,.....p } is a finite set of places, T = {t1, t2 ,.....t} is a finite set of transitions, PnT = 0 and PuTV0 FL(PxT)u(TxP) is a set of arcs, K: P—» {1,2,3, ...} defines the capacity for each place, W: F—» {...-3,-2,-1, 1,2,3, ...} is a weight function, M0: P -» {1,2,3 ...} is the initial marking, R: T—» {0,1,2,..,9} defines the priority for each transition, Z: T ^ {0,1,2,3,..} defines the time for each transition. The Petri net is a directed, weighted, bipartite graph consisting of two types of nodes, called places and transitions. In a graphical representation the places are represented by circles and the transitions by bars or rectangles. Places are connected with transitions, and transitions with places. The weight of the arcs is a positive integer, where a k-weighted arc means k parallel arcs. Each place p has an associate capacity K(p), which determines the maximum number of tokens that p can hold at any time. A marking assigns to each state a nonnegative integer, and is denoted by M. M is an m x 1 column vector, where m is the number of places. If a nonnegative integer l is assigned to place p, the place p is marked with l tokens. In a graphical representation the tokens are represented by dots or a number. The rule for transition enabling and firing is an execution rule, which can be described for an EPN in the following direction. .p:={t | (t,p)eF} is the set of input transitions of place p, p.: = {t | (p,t) e F} is the set of output tansitions of place p, .t:={p | (p,t) e F} is the set of input places of transition t, *:={p | (t,p) e F} the set of output places of transition t. | lgfinHi(š)bJ][M]lfi[j;?n 03-1______ stran 31 I^BSSIfTMlGC Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning Prehod t je omogočen pri določeni označitvi M, če velja: A transition t is enabled under marking M if: \M(p)>W(p,t) " W(p,t)>0 M(p)<\W(p,t)\ " W(p,t)<0 "pe.t: \M(p)0 "pet':{ M(p)>\W(t,p)\ " W(t,p)<0 (1) (2). Enačba (1) pomeni, da označitev vsakega vhodnega mesta prehoda t ne sme biti manjša, oziroma mora biti večja od w(p, t), če w(p, t) ni negativen, oziroma če je negativen. Enačba (2) pomeni, da število žetonov v vsakem izhodnem mestu p od t po izvedbi prehoda t ne sme preseči, oziroma mora biti večje od njegove kapacitete K(p), če w(p, t) ni negativen, oziroma če je negativen. w(p,t) je utež povezave mesta p s prehodom t in w(t, p) utež povezave prehoda t z mestom p. Podmnožica prehodov T c= T je omogočena pri M,če je "ts T’ omogočen pri označitvi M. Če je prehod omogočen, se lahko izvede ali pa tudi ne. To je odvisno od konfliktnih situacij in medsebojnega izključevanja prehodov. Prehod se lahko izvede, če je izpolnjen pogoj: Equation (1) means that the marking of each input place should not be smaller, or have to be smaller, than w(p, t) if w(p, t) is not negative or it is negative, respectively. Equation (2) means that the number of tokens in each output place p of t cannot exceed or have to exceed its capacity K(p) after the firing of t when w(p, t) is not negative or it is negative respectively. w(p,t) is the weight of the arc from place p to transition t and w(t, p) is the weight of the arc from transition t to place p. A sub-set of transitions T c= T is enabled under M, when " te T’ is enabled under M. If a transition is enabled, it may or may not fire. That depends on conflict situations and the mutual exclusion of enabled transitions. The transition may fire if: "p e •ti: p» nT’ = {ti} in/and "p e t»: »pnT’ = {t} ali/or (3) (4). Pogoj (3) pomeni, da ti ni v konfliktni situaciji oziroma nima skupnih vhodnih in izhodnih mest z nobenim prehodom, ki bi bil hkrati omogočen. Pravilo (4) pa pravi, če obstajata dva prehoda, ki sta hkrati omogočena in imata vsaj eno skupno vhodno oziroma izhodno mesto, potem se izvede najprej tisti prehod, ki ima večjo prioriteto R(t). Omogočen prehod se lahko izvede na dva načina, kar je odvisno od časa trajanja prehoda. Prehod s časom trajanja nič (z(t) = 0) se izvede takoj v celoti: M'(p) = M (p) Izvajanje omogočenega prehoda t poteka tako, da se vzame w(p,t) žetonov iz vsakega vhodnega mesta p prehoda t, in da w(t,p) žetonov vsakemu izhodnemu mestu p prehoda t. Prehodi, ki imajo določen čas trajanja (z(t) > 0), se izvedejo v dveh korakih: najprej se izvedejo delno nato pa še do konca. Delno izvajanje prehoda t: Condition (3) means that ti is not in a conflict situation, i.e. it has no common input or output places with any in the same time-enabled transition and (4) means that if two transitions are enabled and have some common input or output places, just the transition with the greater priority R(t) can fire. An enabled transition can fire in two ways, depending on the duration of the transition. Zero-time transitions (z(t) = 0) fire all at once: (5). sicer / else. The firing of an enabled transition removes w(p,t) tokens from each input place p of transition t, and adds w(t,p) tokens to each output place p of transition t. Nonzero-time transitions (z(t) > 0) fire in two steps: first they fire partially and then they fire to the end. Partial firing of transition ti M(p)-W(p,t) " p e»t\t» M(p) + W(t,p) " p ef\»t )-W(p,t) + W(t,p) " p efn»t \M(p)-W(p,t) " pe»t [ M (p) sicer / else. T-’ = Tvj{(ti, z)} (6) (7). grin^sfcflMiscsD VH^tTPsDDIK stran 32 Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning pomeni jemanje w(p,t) žetonov iz vhodnih mest prehoda ti in dodajanje novega elementa (t, z) v T, kjer je T množica delno izvedenih prehodov { i (t1, d1) (t2, d2)....(t, d)} z elementi (tk, dk), tke T in dke {1,2,3...}, kjer je tk delno izveden prehod in dk njen preostali čas do izvajanja do konca. Izvajanje do konca prehoda tk se zgodi, ko je preostali čas nič (dk=0) in Če je za tk izpolnjen pogoj (2). Dejansko se izvedejo do konca prehodi z najmanjšim preostalim časom: means removing the w(p,t) tokens from the input places of transition t and adding one new element (ti, z) to the T, where T is a set of partial firing transitions { i (t1, d,) (t2, d2)....(tn, d)} with elements (tk, dk), tk e T and 1 {1,2,3...}, where t are partially fired transitions and dk are their remaining times to end firing. Firing to the end of transition tk happens when the remaining time dk=0 and when for tk the condition (2) is fulfilled. Practically fires to the end of the transition with smallest remaining time: "(t,d)*T- | tk*t : dk<>d (8). Izvajanje do konca za to omogočenega (2) prehoda ti pri M: Firing to the end of for the end firing enabled (2) transition t under M: M '( p) kjer je: kjer velja za t da " p s .t: M(p) < |W(p,t)| če je W(p,t) < 0 Izvajanje do konca prehoda ti pomeni dodajanje w(ti,p) žetonov vsakemu izhodnemu mestu p prehoda t{% odvzem elementa (tk, d) iz T (11) in odštevanje irf,od d vsem elementom v T-, za katere je izpolnjen pogoj (12). Pogoj (12) pravi, če določen prehod t ni omogočen glede na drugo vrstico pogoja (2), potem se preostali čas d delno izvedenega prehoda t ne more zmanjšati za čas dk. Petrijeve mreže so razširjene s objekti kot posebne vrste žetoni ter s atributivnimi in objektnimi mesti takole: A = {a1, a2,...a} je množica atributov, O = {o1, o2,...0n } je množica objektov, E:O -^vsakemu objektu opredeljuje lastnosti, P LP je podmnožica atributivnih mest, PLP je podmnožica objektnih mest, P onP =0 O : O o-> P u T vsakemu objektu opredeljuje natančno eno objektno mesto oziroma prehod, L: P ^ N 12 vsakemu objektnemu mestu opredeljuje položaj Ea: Sa^vsakemu atibutivnemu mestu opredeljuje atibut , Prehod ima lahko največ eno objektno vhodno mesto in eno objektno izhodno mesto: JM(p) + W(ti,p) " peti. [ M (p) sicer / else. where T-’ = T\{(tk, dk)} (t,d)’ = (t, d - d) za/for "(t,d)GT-’ (9) (10). (11) (12) M(p) < |W(p,t)| falls where for t it holds that "p^ W(p,t) < 0 Firing to the end of transition ti means adding w(t,p) tokens to each output place p of transition ti (9), taking an element (tk, d k) from T (11) and subtracting dk from d of all elements in T, which t fulfils conditions (12). The condition (12) says that if a transition t is not enabled by the second line of condition (2) then the remaining time d of the partially firing transition cannot be decreased for the smallest remaining time d. Petri nets are also extended with objects as a special type of tokens and attributive and object places in the following way: A = {a1, a2,...a} ...set of attributes. O = {o1, o2,...o} ...set of objects E:O -^An defies a characteristic for each object P L P ...subset of attribute places P LP ... subset of object places P onP =0 Os : O o pkjT define for each object one object place or transition L: P -> N12 define a position for each object place E: Sa ^ A define an attribute on an attributive place A transition may have a maximum of one object place as an input and one as an output place: " eT: trnP = {0}v{p} A»tnP = {0}v{p} (13). Prehod z vhodnim ali izhodnim objektnim mestom je omogočen po definicijah (2), (3) in če velja: A transition with object places is enabled by the definition (2), (3) and when: (SfinsjBJbJJIMlSlCšI] I stran 33 glTMDDC Perme T.: Na~rtovanje izdelovalnih sistemov - Simulation-Aided Planning kjer Vp^.nPA3ie{1,2,...n}: Ea(p) = pri(t) where pri: An ^ A; (a1,a2,...,a ^ ai (14), Pogoj (14) pomeni, da ima posamezen objekt vse atribute, ki jih imajo vhodna atributivna mesta prehoda t. Prehod, ki je omogočen, se izvede ter spremeni M v M’ po definicijah (5) ali (6) in (9), pri čemer se spremenijo tudi atributi objekta ei: Condition (14) means that a particular object has, all by the attributive places of transition t, determined attributes. The transition, which is enabled to fire under M to M’ as in definitions (5) or (6) and (9), changes the attributes ei of the object: Vp^Pa: E’(p) = E(p)Cr % 4d ^......1^ ;^:\.jiHz-; :te d) a) začetna usmeritev b) demontiran izdelek in (de)montažne smeri c) vračanje sestavnih delov na prvotna mesta (začetna usmeritev) d) nova usmeritev izdelka e) demontiran izdelek Izognili smo se montaži od spodaj! e) a) The initial orientation, b) Disassembled product and (dis)assembly paths, c) Moving back parts in the positions before disassembly (the initial orientation), d) New product orientation, e) Disassembled product. Assembly from below avoided! Sl. 7 Iskanje najprimernejše usmeritve izdelka Fig. 7. Finding the most convenient orientation for a product (°HH^)i7=rL nnxnnJIarvFn03-1 stran 47 Im3-1 W§©TRQDCL Kunica Z., Vranje{ B., Hrman M.: Nekaj novih algoritmov - Some New Algorithms vsebuje naj največje mogoče število smeri od spodaj navzgor in najmanjše število smeri v nasprotni smeri. Glede na zunanji koordinatni sistem RPN je mogočih šest osnovnih usmeritev izdelka. Vektorje demontažnih smeri razstavimo na komponente in jih primerjamo z osnovnimi usmeritvami izdelka. Število demontažnih smeri daje najprimernejšo usmeritev izdelka, ki ga po potrebi zavrtimo. Pričakujemo, da se osi koordinatnega sistema izdelka ujemajo z osmi zunanjega koordinatnega sistema. 3 RAZPORED ZA ENOPOSTAJNI MONTAŽNI PROCES Strukturiranje prostora je določanje končne lege sestavnih delov po demontaži in nasprotno pred montažo. To je določanje razporeda za bodoči montažni sistem. “Od različnih vidikov razvoja za avtomatizacijo, je posvečeno presenetljivo malo pozornosti razporeditvi sestavnih delov v njihovih zalogovnikih”[11]. Celotna pot montaže tako obsega: - gibanje sestavnega dela iz lege pred demontažo na položaj takoj po demontaži in - gibanje sestavnega dela iz lege po demontaži do položaja v zmontiranem izdelku (omenjena pot se določi med demontažo). Strukturiranje prostora je odvisno od vrste montaže: enopostajna, vrtljiva miza in montažna proga. Vrsta montaže se določi pred začetkom načrtovanja na podlagi zahtevane zmogljivosti, števila variant izdelka, investicijske zmožnosti [12] Prav tako lahko vpliva na izbiro sistema število sestavnih delov njihovega položaja v izdelku in (de)montažne poti. Da bi dosegli enosmerne (celotne) montažne poti, se sestavni deli, ki imajo nepokončne poti, gibljejo po demontažnih poteh. V prvotnem algoritmu je razdalja pomika sestavnega dela definirana z njegovo lego v seznamu demontažnih zaporedij: če je sestavni del na kasnejšem mestu v montažnem zaporedju, bo postavljen dlje od “rastočega” izdelka. Ta zahteva lahko v nekaterih primerih povzroči nepotrebno velike razdalje med sestavnimi deli. Da bi obšli to težavo, definira izboljšani algoritem pomik tD, mm, in najmanjše razdalje med že postavljenimi sestavnimi deli d ,mm: of disassembly paths: it should have the maximum possible number of the bottom-up disassembly paths, and the minimum number of paths from the opposite direction. There are six basic product orientations defined regarding the CAD global coordinate system. The vectors of the disassembly paths are divided into their components, and are compared with basic product orientations. Counting of the disassembly directions will suggest the most convenient orientation, and the product will be rotated, if necessary. In the present implementation, it is expected that the axes of the product’s coordinate system are properly aligned with the axes of the global coordinate system. 3 LAYOUT OF THE ASSEMBLY PROCESS FOR BENCH ASSEMBLY Space structuring is a determination of the final positions of parts after disassembly, and, vice-versa, before assembly. It is a layout design of the future assembly system. “Of the various aspects of design that have been considered for automation, the layout of components within their container has received surprisingly little attention” [11]. So, the complete assembly path of a part comprises: - a motion from the part position before assembly to the position immediately after disassembly, - a motion from the part position immediately after disassembly to the part position required in the product (the path is determined during disassembly). Space structuring depends on types of assembly system: workbench, rotary-table, and line. The type of the assembly system may be determined at the beginning of the planning, on the basis of production volumes, the number of product variants, the investment potential etc. [12]. However, the type of the assembly system may come from the number of parts, the parts’ positions in a product and (dis)assembly paths. In order to achieve a one-directional (complete) assembly path, the parts that have non-vertical paths are translated (moved) using their disassembly paths. In the original algorithm, the value of the part translation is defined by its position in the disassembly sequence list: as the part is later in an assembly sequence, it will be positioned farther from the “growing” product. This premise in some cases may lead to unnecessary large distances among parts. To avoid this situation, the improved algorithm defines the translation tD, mm, and the minimum distance between already positioned parts dmin, mm: t = d = 1,1 R min (2). Lego za sestavne dele z nepokončnimi demontažnimi potmi se določijo iterativno. Tako so razdalje med sestavnimi deli bolj zanesljive. (sl. 8). The position of each part with a non-vertical disassembly path is determined iteratively. In this way, the distances among the parts are more reliable (Fig. 8). grin^(afcflM]SCLD VH^tHMHK stran 48 Kunica Z., Vranje{ B., Hrman M.: Nekaj novih algoritmov - Some New Algorithms SCO 1 c% inn®, 2 a) b) *• y ^ /1 2 x 1 o \^> \ ti/ 0 c) 2 O I (ill //5 -1/ 1 , d) e) II^M) f) O z x a) Lege sestavnih delov takoj po demontaži. b) Postavljen je del 1. Umaknjen je stran od drugih sestavnih delov. c) Postavljen je del 2. Je preblizi delu 1. d) Del 1 je ponovno postavljen (pomika se vzdolž demontažne poti), saj je v listi demontažnih zaporedij pred delom 2. e) Pomikanje dela 1 se nadaljuje tako dolgo, da je razdalja med delom1 in preostalimi dovolj velika. f) Vsi sestavni deli so na končnih legah (pred montažo). a) Part positions immediately after disassembly. b) Part 1 is positioned. It is distanced from the other parts of the product. c) Part 2 is positioned. It is too close to part 1. d) Part 1 is positioned again (moved along its disassembly path) since it is prior to part 2 in the disassembly-sequence list. e) The translation of part 1 continues until the distances between part 1 and the other parts are not large enough. f) All parts of the product are in their final positions (the positions before assembly). Sl. 8. Pozicioniranje sestavnih delov pri izdelku, pri katerem imajo vsi sestavni deli nepokončne (de)montažne poti Fig. 8. The positioning of the parts in the product in which all the parts have non-vertical (dis)assembly paths Naslednja izboljšava je pri sestavnih delih s pokončnimi demontažnimi potmi. Namesto da bi postavili vsak sestavni del posebej, algoritem najprej izračuna najboljše lege (z uporabo optimizacijskega kriterija največjih razdalj med sestavnimi deli), in šele nato izvede pomike sestavnih delov[9]. Če vsebuje izdelek več sestavnih delov z enako prostornino in površino, se ti sestavni deli štejejo za identične (sl. 9-a). Identični sestavni deli so razvrščeni, pri tem upoštevamo primere, ko imajo ti deli tudi iste demontažne smeri. Identični sestavni deli z istimi demontažnimi potmi so postavljeni na skupno lego (sl. 9-c), to omogoča prihranek na prostoru in opremi. The next improvement is made with regard to the parts with the vertical disassembly paths. Instead of the positioning of each part with vertical (dis)assembly paths one by one, the algorithm now first calculates the best positions (with the use of the maximum-distance-between-parts optimisation criterion), and just after that makes the translations of the parts. [9] If a product has several parts that have the same volume and surface area, these parts are considered as identical (Fig. 9-a). The identical parts are grouped together, taking into account whether they have the same disassembly directions. Identical parts with the same disassembly directions are positioned at a unique location (Fig. 9-c), which enables equipment and space savings. Sin^ObJJPsflDslJSD I stran 49 SUMEČ y Kunica Z., Vranje{ B., Hrman M.: Nekaj novih algoritmov - Some New Algorithms a) §§ § y; b) M c) Sl. 9. Lege sestavnih delov: a) po demontaži izdelka, b) pred montažo - po prvotnem algoritmu, c) pred montažo - po izboljšanem algoritmu Fig. 9. The positions of the parts: a) after product’s disassembly, b) before assembly - original algorithm, c) before assembly - improved algorithm 4 SKLEPI IN NADALJNJE DELO Z vidika načrtovanja montaže je vsak izdelek, ki ga je treba zmontirati, mehanizem, ki ga je treba določiti v postopku načrtovanja. Ta mehanizem je na začetku zamisel - montažni načrt, ki bo kasneje preoblikovan v resnično montažno napravo in opremo. Tako je montažni načrt ključni element prizadevanja po integriranju razvoja izdelka, razvoju montažnega sistema (če montažni sistem še ne obstaja) in/ali programiranje montažne naprave in montaže (če montažni sistem že obstaja). Obstoj izdelka v sistemu RPN omogoča definiranje elementov in postopkov za ustvarjanje načrta za avtomatsko montažo. Tako je bil razvit podprt sistem RPN za ustvarjanje načrta za avtomatsko montažo. V tem prispevku so prikazani izboljšani in na novo uporabljeni algoritmi za sistem ustvarjanja načrta montaže. Ti algoritmi se nanašajo na: definiranje zaporedja montaže, strukturiranje prostora za montažni postopek pri enopostajni montaži, usmeritev izdelka, stikanje in obravnavo identičnih sestavnih delov v izdelku. Nadaljnje delo bo usmerjeno v izboljšanje postopkov (avtomatskih in iterativnih), obravnavo načrtovanih variant in njihovo vrednotenje, razvoju montažnih naprav in avtomatsko programiranje in delovanje. 4 CONCLUSIONS AND FURTHER WORK From the assembly-planning point of view, each product that is to be assembled is a mechanism – one that should be recognised during the planning stage. This mechanism is at first an abstraction – an assembly plan, that will later on be transformed into real assembly devices and equipment. In this way, the assembly plan is a key element in the effort to integrate the product design, assembly-system design (if the assembly system does not exist yet) and/or the assembly-device programming and the assembly execution (if the assembly system exists). A product’s existence in a CAD system allows a definition of the elements and procedures aimed at an automatic plan generation. Regarding the former, a CAD-based system for plan generation of an automatic assembly has been developed. In this paper, improved and newly implemented algorithms of the plan-generation system are depicted. These algorithms are related to the following: assembly-sequence defining, space structuring (layout) of the assembly process for bench assembly, product orientation, connectivity, and the treatment of identical parts in a product. Further work will cover the improvement of the generation procedure (automatic and interactive modes), the consideration of plan variants and their validation, assembly device design, automatic programming and execution. grin^(afcflM]SCLD VBgfFMK stran 50 y Kunica Z., Vranje{ B., Hrman M.: Nekaj novih algoritmov - Some New Algorithms 5 LITERATURA 5 REFERENCES [I] Gottschlich, S., C. Ramos, D. Lyons (1994) Assembly and task planning: a taxonomy IEEE Robotics & Automation Magazine, Vol. 1, 4-12. [2] Santochi, M. et al. (1995) STC ‘A‘ Cooperative work on assembly-planning software systems, Annals of the CIRP, Vol. 44, 651-658. [3] Kim, G.J., S. Lee, G. A. Bekey (1996) Interleaving assembly planning and design, IEEE Transactions on Robotics and Automation, Vol. 12, 246-251. [4] Jones, R.E., R. H. Wilson, T L. Calton (1998) On constraints in assembly planning, IEEE Transactions on Robotics and Automation, Vol. 14, No. 6, 849-863. [5] Ye, N, D. A. Urzi (1996) Heuristic rules and strategies of assembly planning: experiment and implications in the design of assembly decision support system, International Journal of Production Research, Vol. 34, 2211-2228. [6] Fujimoto, H., M. F Sebaaly (2000) Anew sequence evolution approach to assembly planning, Journal of Manufacturing Science and Engineering, Vol. 122, No. 1, 198-205. [7] Kunica, Z., B. Vranješ (1999) Towards automatic generation of plans for automatic assembly, International Journal of Production Research, Vol. 37, 1817-1836. [8] Kunica, Z., M. Hrman, B. Vranješ (1999) Algorithmisation of assembly stability check at automatic assembly plan generation, Proceedings of 10th International DAAAM Symposium “Intelligent Manufacturing & Automation: Past-Present-Future”, ISBN 3-901509-10-0, Vienna, 281-282. [9] Hrman, M., Z. Kunica, B. Vranješ (1999) Positions of parts with vertical (dis)assembly paths at automatic assembly system planning, Proceedings of 10th International DAAAM Symposium “Intelligent Manufacturing & Automation: Past-Present-Future”, ISBN 3-901509-10-0, Vienna, 199-200. [10] Homem de Mello, L.S., A. C. Sanderson (1990) And/or graph representation of assembly plans, IEEE Transactions on robotics and automation, Vol. 6, 188-199. [II] Cagan, J., D. Degentesh, S. Yin (1998) A simulated annealing-based algorithm using hierarchical models for general three-dimensional component layout, Computer-Aided Design, Vol. 30, No. 10, 781-790. [12] Boothroyd, G., P. Dewhurst (1991) Product design for assembly, Boothroyd Dewhurst Inc., Wakefield. [13] Zorc, S., D.Noe (1998) Efficient derivation of the optimal assembly sequence from product description, Cybernetics and Systems: International Journal, 29, 159-179. Naslov avtorjev: doc.dr. Zoran Kunica profdr. Božo Vranješ Miljenko Hrman Faculty of Mechanical Engineering and Naval Architecture Univerza v Zagrebu Ivana Lučiča 5 HR-10000 Zagreb, Hrvaška zoran.kunica@fsb.hr bozo.vranjes@fsb.hr miljenko.hrman@fsb.hr Authors’ Address: Doc.Dr. Zoran Kunica ProfDr. Božo Vranješ Miljenko Hrman Faculty of Mechanical Eng. and Naval Architecture University of Zagreb Ivana Lučiča 5 HR-10000 Zagreb, Croatia zoran.kunica@fsb.hr bozo.vranjes@fsb.hr miljenko.hrman@fsb.hr Prejeto: Received: 15.3.2001 Sprejeto: Accepted: 29.5.2003 Odprt za diskusijo: 1 leto Open for discussion: 1 year (SfinKjB)bJJ[M]Sl[JLI] I stran 51 SUMEČ © Strojni{ki vestnik 49(2003)1,52-62 © Journal of Mechanical Engineering 49(2003)1,52-62 ISSN 0039-2480 ISSN 0039-2480 UDK 658.515:007.52:519.65 UDC 658.515:007.52:519.65 Pregledni znanstveni ~lanek (1.02) Review scientific paper (1.02) Robotiziran monta`ni sistem kot sodelujo~a ve~delna organizacija A Study of a Robotic Assembly System as a Collaborative Multi-Agent Organization Jerbi} Bojan - Vranje{ Bo`o Prispevek obravnava načrtovanje večglavega robotiziranega montažnega sistema. Vsak sistem, ki ga je mogoče razstaviti na komponente, lahko obravnavamo kot družbo členov. Taksna zgradba omogoča oblikovanje sodelujočega sistema, ki omogoča nastanek socialne inteligence. Socialno obnašanje je najvišja oblika inteligence, ki omogoča reševanje zelo zapletenih problemov, avtonomno ustvarjanje novih postopkov in učinkovito prilagajanje novim zahtevam. Obravnavani večdelni model temelji na procesnih enotah, ki vsebujejo opremo za prepoznavanje, strategije za reševanje problemov in zmožnost učenja. Sistem ima tako zmožnosti: zaznavanja, prepoznavanja, reševanja problemov, učenja in komunikacije. Uporabljena je okrepljena metoda učenja za vrednotenje delovanja robota in za ustvarjanje novega ali izboljšanje sedanjega znanja. Tako pridobljen vzorec delovanja je spravljen kot izkušnja, ki jo je mogoče uporabiti za reševanje podobnih prihodnjih problemov. Za prepoznavanje podobnosti problemov je uporabljena prilagodljiva mehka senčena (PSMM) nevronska mreža. © 2003 Strojniški vestnik. Vse pravice pridržane. (Ključne besede: montaža robotizirana, sistemi večdeln, člen neodvisni, metode učenja, mreže nevronalne) This paper looks at designing a robotic assembly system as a multi-agent system. Any multi-device system, or any system whose performance is naturally decomposable, can be interpreted as a corporation of agents. Such a scheme comprises the ability to create a collaborative system that can provide the achieving of the social intelligence. Social behavior is the highest form of intelligence, which is able to solve very complex problems, autonomously create new procedures and efficiently adapt to new tasks. The presented multi-agent model is based on processing units that include recognition networks, problem-solving strategies and learning engines. It integrates perception, recognition, problem-solving, learning and communication capabilities. The reinforcement learning method is used here to evaluate the robot is behavior and to induce new, or improve the existing, knowledge. The acquired action (task) plan is stored as experience, which can be used in solving similar problems in the future. To recognize problem similarities we applied the Adaptive Fuzzy Shadowed (AFS) neural network. © 2003 Journal of Mechanical Engineering. All rights reserved. (Keywords: robotic assembly, multiagent systems, autonomous agent, learning methods, neural networks) 0 UVOD Sedanji robotizirani montažni sistemi, tudi če so opremljeni z umetnim vidom in drugimi sistemi zaznavanja, so zelo občutljivi za spremembe izdelka ali postopka. Tudi majhne spremembe v geometrijski obliki izdelka povzročijo občutne spremembe montažnega postopka, zamenjavo geometrijske oblike orodij ali strukture delovnega okolja. Kljub digitalni določenosti avtomatskih sistemov povzroči deterministični kaos nepredvidljiva stanja. Običajno se postopek ustavi, ali pa pride do napačne montaže. Zato je razvoj avtonomnega delovanja robotov ključen za avtomatizacijo montažnega postopka. Od 0 INTRODUCTION Real robotic assembly systems, even those equipped with vision and other perception systems, are still very sensitive to product or process changes. Even small changes in product geometry can imply considerable modifications to the assembly process, an alteration to the tool’s geometry or the structure of the working environment. At the same time, in spite of the digital determinism of automatic systems, deterministic chaos produces unpredictable conditions. It usually stops the process or results in defect assemblies. As a result, the development of autonomous robot behavior is a key approach in assembly-system automation. The planning of intelligent robot behavior can be seen as a kind of grin^(afcflM]SCLD VH^tTPsDDIK stran 52 Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System inteligentnega robota pričakujemo, da se bo obnašal podobno kakor človek, če bo soočen z nepoznanim problemom. Kot prvo se pojavi vprašanje, kako je mogoče zgraditi bazo znanja o nečem, kar je nepoznano, in kako naučiti robota, da bo reševal nepoznane probleme? Edini logični odgovor je: Robota je treba naučiti, da se bo sam učil. 1 ROBOTI Z NEODVISNIM OBNAŠANJEM Neodvisni robot pomeni delovno napravo z določenimi gibalnimi zmožnostmi (premikanje in/ ali gibanje), z uporabo ustvarjalnega sistema načrtovanja, ki se odziva na spremenljivo okolje v dejanskem času. Podana definicija opisuje inteligentnega dejavnika z modelom reagiranja, ki temelji na sklopu verjeti - hoteti - nameravati. Običajno ga imenujemo “softbot”, robot, temelječ na obnašanju ali bitje z zmožnostjo odločanja, “razumno“ bitje. V smislu avtomatske montaže, mora neodvisni dejavnik izkazovati metode prilagajanja in načrtovanja kot odgovor na nedoločeno dinamiko delovnega okolja. Zapletenost intelektualnih mehanizmov kaže, da je želja razviti model umetne inteligence obsojena na neuspeh in razočaranje. Čar inteligence temelji na dolgotrajnem učnem postopku. Naše ustvarjalno vodilo je prevladujoče predvsem v domeni učenja [3]. Kaže, da so modeli učenja bolj pregledni in laže razumljivi, ker jih je mogoče opazovati, v nasprotju s skritimi možganskimi aktivnostmi [2]. Zato je dosti bolj uspešno ustvariti učeči se sistem, ki je sam zmožen razviti pripadajoče intelektualne mehanizme. Sistem te vrste je mogoče učiti ali izuriti, namesto da bi ga programirali. Učenje za izboljšanje zmožnosti in mehka logika so preverjene metode v inteligentni robotiki [7]. Najboljši rezultati so doseženi na področju mobilnih robotov zaradi enostavnosti dvodimenzionalnih problemskih paradigem [1]. V tridimenzionalnem svetu so problemi bolj zapleteni, kakor pri montažnem procesu, ki vključuje prepoznavanje tridimenzionalnega okolja in odločanje (krmiljenje) pri najmanj treh prostostnih stopnjah. 2 MONTAŽNI SISTEM KOT VEČDELNI ROBOTIZIRANI SISTEM Zapletenost avtomatskega montažnega sistema je vsebovana že v pojmu montaža, ki pomeni gradnjo geometrijskih struktur. Zahteva zelo zahtevne gibalne in zaznavne zmožnosti in tudi določen intelektualni potencial za oblikovanje geometrijske oblike izdelka in karakteristike montažne strukture. Sam robot zadovolji le del teh zahtev. Enoročen in skoraj slep robot potrebuje pomoč dodatnih naprav ali drugih robotov za prenos, usmeritev, izbiro položaja in pritrjevanje. Vsi skupaj control system that is expected to endow human-like and autonomous behavior to robots confronted with unknown problems. The questions that arise are as follows: how is it possible to build a knowledge base about something that is not known, and how then to teach a robot to cope with unknown problems? The only logical answer is that the robot should be taught to learn on its own. 1 AUTONOMOUS-BEHAVIOR-BASED ROBOTS An autonomous robot means a working device with a certain motoric capability (motion and/ or moving) that implements a generative planning system which interacts with a changing environment in real time. The given definition actually describes an intelligent agent with an embedded dynamic-reaction model based on belief-desire-intention architecture. It is usually called a “softbot”, behavior-based robot or a decision-making “rational” being. In terms of automatic assembly, the autonomous agents should provide adaptation and planning methods as the answers to the nondeterministic dynamism of the working environment. The complexity of the intellectual mechanism suggests that the aim of developing artificial intellectual models could be a fruitless or disappointing task. The magic of intelligence evolves in a long-term learning process. Our genetic legacy is dominant, particularly in the domain of learning [3]. But, it seems that learning models are more obvious, more understandable, since there is a chance to observe them in contrast to hidden, brain activities [2]. Hence, it is much more effective to build a learning system capable of designing the corresponding intellectual mechanism on its own. A system of this kind can be taught or trained, instead of being programmed, and reinforcement learning, neural networks and fuzzy logic are proven methods in intelligent robotics [7]. The most advanced results are achieved in the area of mobile robots, due to the simplicity of 2D-problem paradigms [1]. In the 3D world the problems can be more complicated; for example in the assembly process, which includes the recognition of 3D scenes and decision making (controlling) based on at least three degrees of freedom. 2 AN ASSEMBLY SYSTEM AS A MULTI-AGENT ROBOTIC SYSTEM The complexity of an automatic assembly system comes from the complexity of the nature of the assembly, which comprises building geometrical structures. It requires very sophisticated motoric and perception capabilities, but also a certain intellectual potential to make conclusions about the geometry of the product and the characteristics of the assembly structure. The robot itself satisfies just a part of these requirements. Single-handed and nearly blind, the robot needs help based on complementary devices, or other robots, for | lgfinHi(Š)bJ][M]lfi[j;?n 03-1______ stran 53 I^BSSIfTMlGC Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System sestavljajo urejen sistem. Določena sestavina je odgovorna za določeno nalogo in je določeno posebno mehanično bitje, odgovorno preostalim vključenim v montažni sistem. Pri vsakem od njih pričakujemo zmožnost odzivanja na spremembe, da prilagodi svojo geometrijsko obliko ali način delovanja. Če gledamo na montažni sistem tako, ga je mogoče razumeti kot nekakšen “socialni način delovanja” oziroma sistem, sestavljen iz sodelujočih posameznikov (členov). Vsak sistem več naprav oziroma vsak sistem, katerega delovanje je mogoče naravno razstaviti, je večdelni sistem. To pomeni, da lahko tudi en sam robot, krmiljen z več programi ali računalniki, ki drug z drugim sodelujejo, izkazuje zapleteno razumno obnašanje. Socialno obnašanje je najvišja oblika inteligence, ki lahko da mnoge prednosti v večdelnih robotskih sistemih. Te prednosti so: - izboljšano delovanje sistema z uporabo vzporednosti pri zaznavanju; - skupno odločanje, utemeljeno na porazdeljenem kriticizmu, prispeva h kreativnemu ustvarjanju idej, kako rešiti nov problem; - zanesljivost, ki je posledica odvečnosti členov in zmanjšanje individualne kompleksnosti 3 MODEL SODELUJOČEGA VEČDELNEGA SISTEMA Glavna parametra večdelnega sistema sta socialna organiziranost in komunikacija. Socialna organiziranost definira strukturo robotske družbe, ki določa sistemsko hierarhijo, odgovornosti členov in njihove vloge: vodje, sodelavce, nasprotnike pomočnike učitelje itn. Socialna organiziranost neposredno vpliva na obnašanje večdelnega sistema. Nekateri roboti bodo sodelovali in pomagali drug drugemu, nekateri bodo iskali druge poti, nekateri bodo skrbeli za varnost členov, nekateri bodo vzpodbujali združevanje ali pa težili k pokrivanju večjih delovnih področij. Razsodna funkcija bo ocenjevala obnašanje vsakega člena in napredek celotnega sistema. Ta pokaže, ali je določeno obnašanje imelo za posledico dobro delovanje in naj se pomni kot pozitivna izkušnja, ali opozori, če je obnašanje povzročilo neželene učinke. Komuniciranje med členi je osnova členske družbe. Brez možnosti komunikacije členi ne morejo oblikovati družbe. Komunikacijski sistem mora definirati: - kdaj komunicirati, - kakšna je vsebina informacije, - kdo je vključen v komunikacijo, - kakšen je doseg komunikacije. Komunikacija mora biti vzpostavljena na podlagi percepcije, vloge in trenutne pozicije/stanja. Na primer, nekaterim členom ni dovoljeno začeti komunikacije, ker niso voditelji ali odgovorni členi; ^BSfirTMlliC | stran 54 transport, orientation, positioning and fixturing. Altogether, they constitute a synchronized system. A particular component is responsible for a particular task, representing certain individual mechanicals being responsible to others combined in the assembly system. Each of them is expected to be able to respond to the change, or adapt their own geometry or course of action. Looking at the assembly system in this way, it can be interpreted as a kind of “social modus operandi” or a system built from collaborative individuals (agents). Any multi-device system or any system whose performance is naturally decomposable is a multi-agent system. This means that even one robot can be controlled by several programs or computers which, collaborating with each other, construct a complex intellectual behavior. Social behavior is the highest form of intelligence, which can provide many advantages in multi-agent robotic systems, such as: - improved system performance by exploiting the parallelism of sensing and action, - collective decision-making based on distributed criticism, contributing to the creative construction of ideas for solving new problems, - reliability, which comes from agent redundancy and the reduction of individual complexity. 3 MODEL OF A COLLABORATIVE MULTI-AGENT SYSTEM The main parameters of a multi-agent system are social organization and communication. The social organization defines the structure of a robotic society, which specifies the system hierarchy, the agent responsibilities and the roles – leaders, followers, opponents, helpers, teachers, etc. The social organization has direct effect on the behavior of the multi-agent system. Some of the agents will follow and help each other, some of them will look for other ways, some will take care of agent security, others will suggest congregation or will tend to cover a wider working area. The arbitration function evaluates the behavior of each agent and the progress of the whole system. It shows when some behavior has resulted in good actions, which should be learned as a positive experience, or alerts when bad behavior produces undesired effects. The communication between agents is the basis of the agent community. Without the ability to communicate, the agents cannot create a community. The communication system must define: - whether to communicate, - what is the information content, - who are the members in communication, - what is the range of communication. The communication should be established on the basis of perception, role and current position/ state. For example, some of the agents may not be allowed to initiate communication because they are not Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System Člen A / Agent A Procesna enota / Processing unit Sistem prepoznavanja / Recognition network Strategija reševanja problemov / Problem-solving strategy Sistem učenja / Learning engine Delovanje / Acti tion podatki o razlagi problemov / information about problem interpretation Sl. 1. Model sodelujočega večdelnega sistema Fig. 1. The model of a collaborative multi-agent system nekateri členi so lahko zunaj komunikacijskega dosega, to pomeni da jim njihovo stanje ali položaj ne daje možnosti, da bi uspešno sodelovali pri reševanju dejanskega problema. Mnogostranost komunikacijskih pravil in njihovih kombinacij daje možnost ustvarjanja zelo zapletenega in ustvarjalnega socialnega obnašanja, kar ima za posledico zelo robusten stroj za reševanje problemov. Slika 1 prikazuje model sodelujočega večdelnega sistema. Vsak člen ima procesno enoto, ki zajema sistem prepoznavanja, strategijo reševanja problemov in sistem učenja. Sistem prepoznavanja podobnih problemov, ki jih je mogoče rešiti s sedanjim znanjem, to je znanjem, zbranim iz izkušenj (primeri rešitev predhodnih problemov). Strategija reševanja problemov je vgrajeno preprosto splošno znanje, ki naj omogoča členu, da problem razišče in najde rešitev. To ni napreden in zahteven razumni mehanizem, ampak primitivni postopek preizkušanja: korak po korak dobro - slabo. Naloga sistema učenja je, da izboljša omenjeno preprosto strategijo reševanja problemov, tako da prilagaja znane postopke in/ali vključuje nove korake. Z ugotavljanjem uspešnosti delovanja jih sistem sprejme ali zavrne. Pozitivno delovanje se zapomni in oblikuje novo paradigmo the leaders or responsible agents; some of the agents might be out of the communication range, i.e. their position or state does not give them a chance to be efficiently used for the solving of the encountered problem. The versatility of the communication rules and their combinations give us the opportunity to create very complex and creative multi-agent social behavior that can roll out the robust problem-solving engine. The Figure 1 illustrates the model of a collaborative multiagent system. Each agent includes the processing unit, which combines the recognition network, the problem-solving strategy and the learning engine. The recognition engine is assumed to recognize similar problems that can be solved with existing knowledge, acquired on the basis of experience (previous problem-solving cases). The problem-solving strategy is the embedded, simple general knowledge, which should enable the agent to explore the problem and find the solution. This is not a sophisticated and intelligent mechanism, but rather a primitive, step-by-step, true-false procedure. The learning engine’s aim is to improve the previously mentioned, simple problem-solving strategy, adapting the existing procedures and/or including new steps. By estimating the success of the actions the engine either accepts or rejects them. The positive actions are (SfinsjBJbJJIMlSlCšI] I stran 55 glTMDDC Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System robotovega obnašanja. To bo predstavljalo model bodočega obnašanja člena v prihodnjih podobnih primerih. Razlaga problemov in sklepi so skupek informacij za nadzor in komunikacijo. Podatki za nadzor so namenjeni za spodbujanje delovanja ali serijo delovanj, ki jih razpoznamo kot obnašanje. Informacija za sodelovanje je izvleček členove razlage problema. Te informacije se pošiljajo in/ali sprejemajo od drugih členov večdelnega sistema ali k njim. Informacija o sodelovanju vzpodbuja ali zavira funkcije, ki zvišujejo ali znižujejo motivacijo člena za določeno delo (pomagaj drugemu členu, vztrajaj pri trenutnem delu, spremeni ali ustavi akcijo itn.). 4 MODEL RAZUMNEGA ČLENA 4.1 Sistem učenja Sistem robotskega učenja mora zagotoviti zajemanje proceduralnega znanja, aktualna pravila za gibanje in postopke pa tudi učenje opisnega znanja o delovnem okolju in strukturah. Začetna predpostavka je, da robot ne ve ničesar. Je “tabula rasa” in ima le nekaj znanja glede določenih strateških splošnih postopkov za doseganje ciljev (prijeti sestavni del prek ovire, vstaviti neurejen del itn.) in o učnih metodah. then recorded,and this forms the new paradigm of robot behavior that will represent the model of the agent’s behavior in future, similar situations. The problem’s interpretation and conclusions represent the control and collaboration set of information. The control data are used to initiate an action, or the collection of actions, which can be recognized as a behavior. The collaboration information abstracts the agent’s problem interpretation. They are transferred and/or received to/from the other members of the multi-agent system. The collaboration information serves as excitatory or inhibitory functions that rise or lower the motivation of the agent to undertake certain action (help another agent, persists in current work, changes or stops the action, etc.). 4 THE MODEL OF THE INTELLIGENT AGENT 4.1 Learning System The robot learning system should enable the acquisition of procedural knowledge – actually, the moving action rules and procedures – as well as learning descriptive knowledge about the structures of the working environment. The starting assumption is that the robot does not know anything. It is a tabula rasa and has only some knowledge about certain strategic general procedures for attaining objectives – grasp work-piece over the obstacle, insert misaligned part and so on – and about the learning method. Izkušnja (načrt delovanja + sestava delovnega prostora) / Experience (action plan + work space structur e) Proceduralno strateško Naključni poskusi / Random attempts znanje & cilji / Procedural strategic knowledge & objectives Približevanje cilju / Approaching the goal Nagrada / .Reward Kazen / Punish Stra teški poskusi / Strategic attempts Snovanje / Synthesize i ______, Shranjenje pritrdilne izkušnje / Store affirmative experience Sl. 2. Zasnova sistema robotskega učenja Fig. 2. The concept of the robot learning system grin^sfcflMiscsD VH^tTPsDDIK stran 56 Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System Slika 2 ponazarja predlagani sistem načrtovanja. Uporabljen je ojačan sistem učenja ([4] in [5]), ki temelji na strateških in naključnih poskusih. Postopek za ocenjevanje in iskanje napak konvergira k želenemu cilju tako, da kaznuje napačno delovanje in privzema uspešno. Ko se približa cilju, je treba zasnovati smiselne ukrepe in jih spraviti v spomin kot nekakšno izkušnjo, ki bo pomagala pri reševanju podobnih problemov v prihodnosti. Podobni problemi so tisti, ki so podobni glede na strukturo delovnega okolja. Ker zbrano znanje predstavljajo postopki, ki se nanašajo na ustrezne prostorske strukture, je robot zmožen delovati po postopkih, za katere je izurjen. Tako naj bi opravil nalogo z najmanjšim številom napak. 4.2 Sistem prepoznavanja Naučeni celotni postopek naj se nanaša na pripadajoč prostorski načrt, ki je zajet s celotnim vizualnim sistemom. Z uporabo celotnega vida je robot zmožen prepoznati spremembe v delovnem prostoru, tako da primerja trenutno sliko z že znanimi paradigmami in se odloči o načinu obnašanja. V primeru podobnih struktur uporabi priučene postopke, v drugih nepoznanih ali bistveno različnih strukturah, mora začeti z iskanjem nove primerne poti. Struktura delovnega prostora ne more biti zapisana kot simbolno kodiran zapis, ker bi to zahtevalo veliko računalniškega spomina za novo ali podobno situacijo. Za obdelavo tako obširne podatkovne baze bi bil potreben znaten čas. Model nevronskih mrež je uspešen način za obdelavo velikega števila vhodov in za njihoo zapomnjanje zgoščeno v obliki sinoptičnih uteži. Za uporabo pri reševanju strukturnih problemov morajo biti nevronske mreže zgrajene tako, da si lahko zapomnijo različne prostorske strukture in prepoznajo podobne. Izraz “podobna situacija” tukaj pomeni situacije, ki jih imamo običajno za podobne, na primer ovire, ki oblikujejo podobna prostorska razmerja, so malo premaknjene ali zasukane, ali pa se malo razlikujejo po obliki. Struktura delovnega prostora je predstavljena v obliki binarne matrike n*m, ki predstavlja vstopni vektor mreže. Ničle pomenijo prazen prostor, enice pa diskretiziran prostor, kjer stoji ovira. 4.2.1 Prilagodljiva senčena mehka mreža (PSMM) Za razpoznavanje prostorskih struktur po definiciji podobnosti je bila razvita PSM nevronska mreža. Postopek učenja razdeli v tri faze: začetek, učenje in delovanje. V fazi začetka uporablja postopek iskanja težišča gruče (ITG) v izogib zlivanja različnih strukturnih kategorij, da zagotovi njihovo Fig. 2. illustrates the proposed concept of the intelligent planning system. It implements the reinforcement learning ([4] and [5]) based on strategic and random attempts. The trial-and-error searching procedure converges on a given goal by punishing a wrong action or rewarding a successful one. After approaching the goal, reasonable actions should be synthesized and recorded as some kind of experience that will help solving similar problems in the future. Similar problems are those that resemble each other with regard to the structure of the work space. Since the gathered knowledge consists of procedures assigned to appropriate space structures, the robot is able to follow the trained procedure, expecting to accomplish the task with a minimum number of faults. 4.2 Recognition system The learned moving procedure should be assigned to a corresponding work-space map acquired by the global vision system. Using the global view the robot is able to recognize changes in the structure of the work space, comparing the current space map with already experienced paradigms, and come to decisions about its behavior. In the cases of similar structures it uses learned procedures, in others, unknown or significantly different structures, it must undertake the searching of a new, appropriate path. Work-space structure cannot be simply recorded as a symbolically coded description, because this would require a large computer memory for any new or similar situation encountered - and it would take a considerable time to search such a large database. The neural network model offers an efficient way to process a large number of input values and to memorize them, condensed as synaptic weights. Applied to the structural assignment problem, the neural network should be designed to memorize distinct work-space structures and to recognize similar ones. The term “similar situations” here denotes situations that are usually considered similar, i.e. situations where obstacles form similar spatial relations, slightly translated or rotated in any direction, or where they slightly differ in shape. The work-space structure is represented as a n xm binary matrix, which is assumed to be a network input vector. The zeros represent empty space and units denote the discrete space where the obstacle resides. 4.2.1 Adaptive fuzzy shadowed network In order to provide recognition of work-space structures, according to the given definition of similarity, the Adaptive Fuzzy Shadowed (AFS) neural network has been designed. It divides the learning process into three phases: initiation, training and working. In the initiation phase it uses the cluster center seeking approach (CCS) to prevent the blending of | lgfinHi(š)bJ][M]lfi[j;?n 03-1______ stran 57 I^BSSIfTMlGC Jerbi} B., Vranje{ B.: Robotiziran monta`ni sistem - A Study of a Robotic Assembly System vhodna plast / input layer skrita plast / hidden layer izhodna plast / output layer Sl. 3. Struktura adaptivne senčene mehke nevronske mreže Fig. 3. Adaptive fuzzy shadowed network architecture uravnoteženo razporejanje in da bi izločil vpliv stopnje predstavitve problema. Algoritem ne sledi popolnoma algoritmu ITG, poznanemu pri [6]. Namesto računanja največje absolutne različnosti (ali najmanjše absolutne podobnosti), računa največjo relativno različnost (najmanjšo relativno podobnost) Sp. Vpliv velikosti ovire v razpoznavo težišča gruče je vključen, tako da upošteva raven ujemanja (število ujemajočih se enic) in velikost ovire (število enic). Vzorec težišča gruče tako predstavlja najbolj značilno strukturo primerkov, ki naj začne mrežo in ne omejuje števila izhodnih nevronov, ki bodo zajeti med učenjem, ki sledi. Arhitektura mreže temelji na treh plasteh nevronov (sl.3 3). Namen skrite plasti je, da spremeni vhodni vektor X, da omogoči prepoznavanje bitno premaknjene ali zasukane situacije (v katerikoli smeri) kot podobno (vzbudi isti izhodni nevron). To je doseženo z dodajanjem sence okoli obrisa ovire. Intenzivnost sence se zmanjšuje z večanjam razdalje od ovire dva ali več ravni globoko, kakor to določa utežnostna funkcija senčenja (enačba 1) za vhodni vektor skrite plasti X*. distinct structure categories, to provide their balanced dissipation and to eliminate the influence of the order of the problem presentation. The algorithm does not completely follow the CCS algorithm known from [6]. Instead of calculating the maximum absolute dissimilarity (or minimum absolute similarity), the maximum relative dissimilarity (or minimum relative similarity) Sp is calculated. The influence of the size of the obstacle on the cluster center identification is thus included, considering the relation between the matching level (the number of matching “1’s”) and the obstacle size (the number of “1’s”). The cluster center patterns actually represent the most distinctive structure samples that must initiate the network, and do not limit the final number of output neurons that will be acquired during the training that follows. The network architecture is based on three neuron layers (Fig. 3.). The purpose of the hidden layer is to modify the input vector X in order to provide the recognition capability of bit-translated or rotated situations (in any direction) as similar situations (triggering the same output neuron). This is attained by adding shadows around the obstacle’s contours. The shadow intensity decreases as the distance from the obstacle increases two or more levels deep as given by the shadowing weight function (Eq. 1) for a hidden-layer input vector X*: u = 1 " (i* = i a j* = j) l1=\i*-i\ a-1 ; l2=\j*-j\ (1), l1\ + l2\ 0