DOI: 10.15477/SZE.MMTDI.2015.001
Ballagi Áron Fuzzy szituációs térképek és alkalmazásuk intelligens mobil robotok kooperációjában és kommunikációjában Doktori értekezés
Témavezetők: Dr. Kóczy T. László egyetemi tanár, az MTA doktora Széchenyi István Egyetem Automatizálási Tanszék Dr. Pozna Claudiu Radu egyetemi tanár Széchenyi István Egyetem Informatika Tanszék
Széchenyi István Egyetem Infrastrukturális Rendszerek Modellezése és Fejlesztése Multidiszciplináris Műszaki Tudományi Doktori Iskola Győr, 2014
DOI: 10.15477/SZE.MMTDI.2015.001
Köszönetnyilvánítás Ezúton fejezem ki köszönetemet témavezetőimnek, Kóczy T. László és Pozna Claudiu professzor uraknak a kutatásaim támogatásáért, az iránymutatásért, és a kellő időben nyújtott inspirációért. Köszönöm a tanszéki kollégáimnak a jó tanácsokat és a kutatási környezet biztosítását. Végül, de nem utolsó sorban, szeretnék külön köszönetet mondani családomnak a türelmükért, a szeretetteljes hátérért és támogatásért.
ii
DOI: 10.15477/SZE.MMTDI.2015.001
Tartalomjegyzék
1.
2.
BEVEZETÉS. A KUTATÁS TÁRGYA ÉS CÉLKITŰZÉSE ............................................................ 7 1.1.
EXPLICIT KOMMUNIKÁCIÓ .................................................................................................... 8
1.2.
ADAPTÍV KOMMUNIKÁCIÓ ................................................................................................... 8
1.3.
SZAKÉRTŐI RENDSZERRE ÉPÜLŐ KOMMUNIKÁCIÓ ...................................................................... 9
1.4.
IMPLICIT KOMMUNIKÁCIÓ .................................................................................................. 10
1.5.
FUZZY KOMMUNIKÁCIÓ ..................................................................................................... 12
FUZZY ÉS FUZZY SZIGNATÚRA MÓDSZEREK ÁTTEKINTÉSE .............................................. 15 2.1.
FUZZY RENDSZEREK ALAPJAI ............................................................................................... 15
2.1.1.
Fuzzy halmazok ...................................................................................................... 15
2.1.2.
Műveletek, relációk és következtetés fuzzy halmazokon ....................................... 18
2.1.2.1. Fuzzy komplemensek ..................................................................................................... 18 2.1.2.2. Fuzzy metszetek ............................................................................................................. 20 2.1.2.3. Fuzzy uniók ..................................................................................................................... 21 2.1.2.4. Fuzzy relációk ................................................................................................................. 22 2.1.2.5. Fuzzy szabályok .............................................................................................................. 23 2.1.2.6. Mamdani‐típusú fuzzy következtető rendszerek ........................................................... 23 2.1.2.7. Takagi‐Sugeno‐típusú fuzzy irányítási rendszerek .......................................................... 28
2.2.
FUZZY KÖVETKEZTETŐ ALGORITMUSOK BONYOLULTSÁGA ......................................................... 29
2.2.1. 2.3.
3.
A komplexitás csökkentésének lehetőségei ........................................................... 29
FUZZY SZIGNATÚRÁK ......................................................................................................... 31
2.3.1.
Fuzzy halmaz szignatúrák ...................................................................................... 33
2.3.2.
Műveletek fuzzy szignatúrákon .............................................................................. 34
ÚJ MÓDSZEREK ÉS MEGKÖZELÍTÉSEK A KOMPLEX STRUKTURÁLT ADATOK LEÍRÁSÁRA .. 35 3.1.
FUZZY SZITUÁCIÓS TÉRKÉP ................................................................................................. 35
3.1.1.
Kétdimenziós fuzzy szituációs térkép ..................................................................... 35
3.1.2.
Fuzzy szituációs térkép jelölésrendszere ................................................................ 38
3.1.3.
Műveletek fuzzy szituációs térképen ...................................................................... 39
3.1.3.1. Fuzzy szituációs térképek legnagyobb közös struktúrája, Fuzzy szituációs térkép struktúrájának, felbontásának módosítása (Zoom) ........................................................................................ 40 3.1.3.2. FSM komplemense ......................................................................................................... 41 3.1.3.3. FSM‐ek metszete ............................................................................................................ 42 3.1.3.4. FSM‐ek uniója ................................................................................................................ 43
3.1.4.
Kiterjesztett fuzzy szituációs térkép ....................................................................... 43
3.1.5.
A fejezethez kapcsolódó tézisek ............................................................................. 45
iii
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.6.
Következtetés fuzzy szituációs térkép alapú rendszerekben (általánosított
Mamdani‐módszer) ............................................................................................................................ 46 3.1.6.1. FSM alapú szabálybázis .................................................................................................. 46 3.1.6.2. Illeszkedési mérték számítása ........................................................................................ 47 3.1.6.3. Következtetés ................................................................................................................. 51
3.1.7.
A fejezethez kapcsolódó tézisek ............................................................................. 51
3.1.8.
Fuzzy szituációs térkép dimenzió növelése............................................................. 52
3.1.8.1. Többdimenziós fuzzy szituációs térkép .......................................................................... 52 3.1.8.2. Többrétegű fuzzy szituációs térkép (Multilayer – FSM) ................................................. 52
3.1.9.
A fejezethez kapcsolódó tézisek ............................................................................. 55
3.1.10. Fuzzy szituációs térkép csomópontjainak belső kapcsolatrendszere .................... 56 3.1.10.1. Fuzzy gráfok ................................................................................................................. 56 3.1.10.2. Fuzzy szituációs térkép csomópontok kapcsolatainak leírása fuzzy gráfokkal ............. 57
3.1.11. A fejezethez kapcsolódó tézisek ............................................................................ 61 4.
ÚJ MÓDSZEREK INTELLIGENS KOMMUNIKÁCIÓ ÉS KOOPERÁCIÓ MEGVALÓSÍTÁSÁHOZ . 62 4.1.
ROBOTOK KOOPERATÍV FELADATVÉGZÉSE .............................................................................. 62
4.1.1.
Az együttműködés feltételei ................................................................................... 62
4.1.2.
A kommunikáció mint az együttműködés alappillére ............................................ 63
4.1.3.
Kontextusfüggő rekonstruktív kommunikációra épülő robotkooperáció ............... 67
4.1.3.1. Egy robotkooperációs feladat ........................................................................................ 68 4.1.3.2. Robotok kooperációs vezérlése ..................................................................................... 72
4.1.4.
Kísérleti robotkooperációs rendszer ....................................................................... 97
4.1.4.1. Kooperációs környezet és eszközök ............................................................................... 97 4.1.4.2. Kooperációs rendezési példa szimulált környezetben ................................................. 100
4.1.5. 5.
A fejezethez kapcsolódó tézisek ........................................................................... 102
ÖSSZEFOGLALÁS ÉS KITEKINTÉS .................................................................................. 103
IRODALOMJEGYZÉK ............................................................................................................. 105 SAJÁT PUBLIKÁCIÓK ............................................................................................................. 113 A.
MELLÉKLET ................................................................................................................. 116 A.1.
A MUNKATERÜLET ......................................................................................................... 116
A.2.
KHEPERA ROBOTOK ........................................................................................................ 116
A.2.1.
KHEPERA ROBOTOK SZENZORRENDSZERE ............................................................................ 118
A.3.
MUNKATÉRBEN LÉVŐ TÁRGYAK AZONOSÍTÁSA, LOKALIZÁLÁSA ................................................. 120
iv
DOI: 10.15477/SZE.MMTDI.2015.001
Ábrák jegyzéke 1. ÁBRA EGY TIPIKUS SZAKÉRTŐI RENDSZER SEMATIKUS VÁZA [14] .............................................................................. 10 2. ÁBRA A SZAKÉRTŐI RENDSZER MINT KOMMUNIKÁCIÓS CSATORNA [14] .................................................................... 10 3. ÁBRA FUZZY KOMMUNIKÁCIÓS CSATORNA [22] ................................................................................................... 12 4. ÁBRA. TAGSÁGI FÜGGVÉNY ALAKOK ................................................................................................................... 16 5. ÁBRA. EMBEREK MAGASSÁGÁT JELLEMZŐ FUZZY HALMAZOK................................................................................... 17 6. ÁBRA. ZADEH‐FÉLE (STANDARD) FUZZY MŰVELETEK ............................................................................................. 19 7. ÁBRA. FUZZY KÖVETKEZTETŐ RENDSZER VÁZLATA ................................................................................................. 24 8. ÁBRA. ILLESZKEDÉSI MÉRTÉK MEGHATÁROZÁSA .................................................................................................... 25 9. ÁBRA. SZABÁLY KÖVETKEZMÉNYE ...................................................................................................................... 26 10. ÁBRA. TELJES MAMDANI‐KÖVETKEZTETÉS ........................................................................................................ 27 11. ÁBRA. PÉLDÁK DEFUZZIFIKÁCIÓRA ................................................................................................................... 28 12. ÁBRA FUZZY SZIGNATÚRA FASTRUKTÚRÁS ÁBRÁZOLÁSA ....................................................................................... 32 13. ÁBRA. FUZZY HALMAZ SZIGNATÚRA ................................................................................................................. 34 14. ÁBRA FUZZY SZITUÁCIÓS TÉRKÉP ..................................................................................................................... 35 15. ÁBRA FUZZY SZITUÁCIÓS TÉRKÉP MINT TÖBBDIMENZIÓS SZIGNATÚRA ..................................................................... 36 16. ÁBRA A) FUZZY SZITUÁCIÓS TÉRKÉP ALRÁCSAI, B) ALAPTÉRKÉP STRUKTÚRA, C) MÁTRIXOS LEÍRÁS .................................. 37 17. ÁBRA RMAX = 3 FUZZY SZITUÁCIÓS TÉRKÉP STRUKTÚRA ......................................................................................... 39 18. ÁBRA A LEGNAGYOBB KÖZÖS STRUKTÚRA KERESÉSÉNEK FOLYAMATA ...................................................................... 48 19. ÁBRA A LEGNAGYOBB KÖZÖS TÉRKÉP STRUKTÚRA ............................................................................................... 49 20. ÁBRA TÖBBRÉTEGŰ FUZZY SZITUÁCIÓS TÉRKÉP ................................................................................................... 53 21. ÁBRA FUZZY ÉL GRÁF .................................................................................................................................... 57 22. ÁBRA FUZZY CSÚCS GRÁF ............................................................................................................................... 57 23. ÁBRA A) FSM RÁCSPONT ÉL TAGSÁGI ÉRTÉKEK, B) ÉL TAGSÁGI ÉRTÉKEK KÉT RÁCSPONT KÖZÖTT ................................... 58 24. ÁBRA FUZZY SZITUÁCIÓS TÉRKÉP KAPCSOLATI GRÁFJA .......................................................................................... 59 25. ÁBRA AZ XIJ GYÖKÉR‐RÁCSPONTRA FELVETT KAPCSOLATI GRÁF............................................................................... 60 26. ÁBRA KITERJESZTETT FUZZY SZIGNATÚRA AZ XIJ‐RE .............................................................................................. 60 27. ÁBRA KOOPERATÍV RENDEZÉSI FELADAT ............................................................................................................ 69 28. ÁBRA DOBOZ ÉS ROBOT JELÖLÉSEK .................................................................................................................. 70 29. ÁBRA ROBOT MOZGATÁSI POZÍCIÓK ................................................................................................................. 70 30. ÁBRA KOOPERATÍV TOLÁSI ÉS FORGATÁSI KOMBINÁCIÓK ...................................................................................... 71 31. ÁBRA MEGÁLLÍTÁSI KOMBINÁCIÓK .................................................................................................................. 71 32. ÁBRA A RENDEZÉSI FELADAT MUNKATERE ......................................................................................................... 73 33. ÁBRA AZ Ak T , L,U LEHETSÉGES RENDEZÉSI ALAKZATOK............................................................................... 73 34. ÁBRA RENDEZÉSI FUZZY SZITUÁCIÓS TÉRKÉP ...................................................................................................... 74 35. ÁBRA KEZDETI SZITUÁCIÓS TÉRKÉPEK: A) R0 MESTER‐ROBOT CRISP TÉRKÉPE, B) SZOLGA‐ROBOTOK NEUTRÁLIS TÉRKÉPE .... 75 36. ÁBRA AZ ELEMEKHEZ KAPCSOLT FUZZY ÉLEK ...................................................................................................... 77
v
DOI: 10.15477/SZE.MMTDI.2015.001
37. ÁBRA ÁLTALÁNOS FUZZY ÉL‐VEKTOR ................................................................................................................ 78 38. ÁBRA RENDEZÉSI ALAKZATOK ......................................................................................................................... 85 39. ÁBRA RI ROBOT ÁLLAPOTÁT ÉS SZÁNDÉKÁT LEÍRÓ SZIGNATÚRA .............................................................................. 91 40. ÁBRA BJ DOBOZ ÁLLAPOTÁT LEÍRÓ SZIGNATÚRA ................................................................................................. 94 41. ÁBRA KÍSÉRLETI ROBOTKOOPERÁCIÓS RENDSZER BLOKKVÁZLATA ........................................................................... 97 42. ÁBRA SZIMULÁCIÓS KERETRENDSZER ............................................................................................................... 99 43. ÁBRA RENDEZÉS FEDÉLZETI KAMERA KÉPPEL .................................................................................................... 100 44. ÁBRA RENDEZÉSI FELADAT LÉPÉSEI ................................................................................................................ 101 45. ÁBRA KHEPERA III. ROBOT ........................................................................................................................... 116 46. ÁBRA KHEPEREA ROBOT IR ÉRZÉKELŐI ............................................................................................................ 118 47. ÁBRA IR ÉRZÉKELŐK KARAKTERISZTIKÁJA ......................................................................................................... 119 48. ÁBRA UH ÉRZÉKELŐK KARAKTERISZTIKÁJA ....................................................................................................... 120 49. ÁBRA A QR‐KÓD FELÉPÍTÉSE ........................................................................................................................ 121 50. ÁBRA ROBOT QR‐KÓD JELÖLÉSE ................................................................................................................... 121
vi
DOI: 10.15477/SZE.MMTDI.2015.001
1. Bevezetés. A kutatás tárgya és célkitűzése Az ember gépépítési törekvései a fejlődésük során legtöbbször egy olyan szintre jutottak el, ahol az adott eszköz használhatósága megkövetelte más eszközökkel való aktív „együttműködését”, az egymás képességeit kiegészítő használatot. A robottechnikára fokozottan jellemző ez az igény már a kezdeti idők óta, mivel robotokat elsősorban emberi munka kiváltására, segítésére építették, ahol az alkotó együttműködés alapvető. Napjaink legizgalmasabb és legdinamikusabban fejlődő robottechnikai irányzata a szervizrobotok és a személyi robotok (PR), az embert valamilyen módon segítő, kiszolgáló, esetleg szórakoztató gépek területe [1]. Ezen a területen az intelligens együttműködés elvárása alapkövetelményként jelentkezik. A kollaborációs feladatokat megoldó algoritmusok területén a számítási intelligencia módszerek jelentenek áttörési lehetőséget. Az együttműködés mindig igényel valamilyen szintű intelligenciát. A kooperációban résztvevő ágenseknek három fő tulajdonsággal kell rendelkezni:
együttműködésre való képesség,
együttműködésre való hajlandóság,
hatékony kommunikáció a többi résztvevővel.
Az első két feltétel gépek esetén jól kezelhető, bár magas szintű mérnöki munkát igénylő kérdés. A harmadik pillért, a kommunikációt már szinte természetesnek érezzük, annyira átszövi az életünket, „infrastrukturális alapszolgáltatásnak” tekintjük. Valóban, a kommunikációs rendszerek megléte, azok igénybevétele, a műszaki megoldások mindennaposak és ezek a robottechnikában, szűkebben a mobil robottechnikában is meglévő, jól kidolgozott részrendszerek. Mivel a hatékony kooperáció egyik legfőbb pillére a résztvevők közti kommunikáció és ennek minősége, egyértelműsége meghatározó a kooperáció végrehajtása tekintetében, ezért az együttműködő rendszerek kommunikációja élesen kidolgozott és meghatározott alrendszerként van jelen. Hagyományosan a merev protokollra épülő explicit kommunikációs rendszert használják.
7
DOI: 10.15477/SZE.MMTDI.2015.001
1.1. Explicit kommunikáció Explicit kommunikációról beszélünk, ha az információközlés egy dedikált kommunikációs csatornán keresztül és egyértelműen definiált szimbólumokra épülő üzenetekkel történik. Általában, ha a kommunikációt emlegetjük, főleg ha gépekről van szó, akkor ez az explicit kommunikáció jut eszünkbe. Valóban, jelenleg a legelterjedtebb metódusról van szó, ami a vezeték nélküli hálózatok árcsökkenésével robbanásszerűen terjedt el az eszközeinkben. Az esetek nagy többségében a multi-robot rendszerek alapvető kommunikációs képességei is ezen az alapon állnak. Kutatások sorát találhatjuk e témakörben,
melyek
egy
része
az
explicit
kommunikáció
fontosságát
és
kihagyhatatlanságát igyekszik igazolni [2], míg mások éppen ennek továbbfejlesztésén, rugalmasságának növelésén dolgoznak [3-12]. Tulajdonképpen az explicit kommunikáció legnagyobb hátránya a rugalmatlansága, az alacsony hibatűrő és bizonytalanságkezelő képessége, és a természetes emberi gondolkodástól való távolsága. Ezen hiányosságok kiküszöbölésére több irányba indultak kutatások. A dinamikus üzenetértelmezés [7, 12] a rugalmasságot növeli. A [10]-ben fuzzy logikai elemek felhasználásával növelik a vezeték nélkül kommunikáló szenzorhálózatok hibatűrését, robusztusságát. A gépek explicit kommunikációs módja általában az ember számára nehézkesen követhető, unalmas, kevés intelligenciát tükröz, és egyáltalán nem, vagy csak nehézkesen képes kezelni a bizonytalanságot. Ezért a közelmúltban több olyan kutatási irány alakult ki, melyek a gép-gép és ember-gép kommunikációt, és ezzel a kooperációs lehetőségeket, intelligensebbé,
emberközelibbé
teszik.
Kommunikáció-technika
szempontból
a
következő fő irányzatokat különböztethetjük meg:
1.2. Adaptív kommunikáció A kilencvenes évek elején folytak kísérletek az MIT Mesterséges Intelligencia laboratóriumában olyan együttműködő mobil robotokkal, amelyek között speciális, úgynevezett adaptív kommunikáció volt [13]. Az adaptív kommunikáció ebben a rendszerben azt jelentette, hogy a robotok rendelkeztek egy rögzített szimbolikus szókinccsel, amire menet közben építették fel és tanulták meg a saját nyelvüket az egyes feladatokhoz igazodva. Az adaptív kommunikáció így alkalmassá tette a robotokat egy minden résztvevő által elérhető közös tudásbázis létrehozására.
8
DOI: 10.15477/SZE.MMTDI.2015.001
Az adaptív kommunikációnak több hátránya is van. Egyrészt igényli az explicit kommunikációs vonalak meglétét, másrészt nem garantálja, hogy a robotok által alkotott nyelv a feladat optimális megoldását segíti elő. Az így kialakított „saját nyelv” hajlamos lokális értelmezési tartományok csapdájába esni, ezért alapvetően nem alkalmas bonyolult kooperációs feladatok kezelésére.
1.3. Szakértői rendszerre épülő kommunikáció Whitaker és Östberg [14] szerint a szakértői rendszerek kommunikációs csatornáknak is tekinthetők, amelyek a szakértők és a felhasználók között épülnek ki. A hagyományos szakértői rendszer értelmezésre látunk egy példát az 1. ábrán, ahol két diszkrét komponensre épül a rendszer: 1. A szakértelmet modellező tudásbázisra, 2. a következtető gépre, mely logikai operációk sorozatát végzi a tudásbázison. A másik alternatív megközelítés [14] a szakértői rendszert a tudástranszferhez használt kommunikációs csatornaként értelmezi (2. ábra). Az 2. ábrán jól látszik, hogy a szakértőtől a végfelhasználóig vezető út olyan kommunikációs csatorna, melyen az információ folyam három fő részre osztható: 1. tudásgyűjtés, 2. szakértői rendszer konstruálása, 3. konzultációs folyamat. Ennek a kommunikációs csatorna értelmezésnek egyértelműen látszik az előnye, a felhasználó gyorsan, tanulás és hosszas keresés nélkül juthat fontos szakértői információkhoz, még akkor is, ha a szakértő közvetlenül nem elérhető számára. Kommunikációs oldalról tekintve az ilyen típusú rendszerek nagy problémát hordoznak magukban, ez az inkrementális információvesztés vagy torzulás, mely a forrás és a végfelhasználó közötti kommunikációs úton történik. Ez a hiba gyakorlatilag nem küszöbölhető ki, és akár súlyos félreértésekhez, nem egyértelmű állapotokhoz is vezethet.
9
DOI: 10.15477/SZE.MMTDI.2015.001
1. ábra Egy tipikus szakértői rendszer sematikus váza [14]
2. ábra A szakértői rendszer mint kommunikációs csatorna [14]
1.4. Implicit kommunikáció Implicit kommunikációról beszélünk, ha maga a környezet szolgál az információ átvitelre [15]. Jó példa az implicit kommunikációra az alábbi: Tekintsünk két robotot (R1 és R2) melyek közösen nyírják egy területen a füvet. Tegyük fel, hogy mindkettő meg tudja különböztetni a már lenyírt és a még nyíratlan füvet. R2-nek nem kell megkérdeznie R1-től, hogy hol nyírta már le a füvet. Tény, hogy sem R1nek, sem R2-nek nem kell nyomon követnie ezeket az információkat, ezt maga a környezet tárolja. R1 és R2 vágási folyamatának előrehaladását a környezeten keresztül kommunikálják. Ez az implicit kommunikáció [16]. 10
DOI: 10.15477/SZE.MMTDI.2015.001
Az implicit kommunikáció egyik érdekes tulajdonsága, hogy nem lehet „kikapcsolni”, vagyis elkerülhetetlen. Ezt könnyű megérteni az előző példa alapján, ha az egyik robot végzi a munkáját, nem tudja megakadályozni az információ transzfert, mert nem rejtheti el, hogy hol nyírta már le a füvet. Zebrowski alapján az implicit kommunikáció előnyei egyértelműek [16]:
Egyszerűség. Gyakran automatikusan történik az implicit kommunikáció.
Robusztusság.
Kevésbé vagy egyáltalán nem függ a kommunikációs hálózatoktól és mechanizmusoktól.
Másrészről, az implicit kommunikáció korlátai is könnyen beláthatók:
Kicsi a környezet információtároló képessége.
Csak egyszerű információk közölhetők ilyen formán.
A robotok érzékelési képességei korlátozzák és bizonytalanná tehetik az információátvitelt.
A robot kooperációs feladatokban az implicit kommunikáció széles körben kutatott és gyakorlatban is alkalmazott, mint alternatív kommunikációs megoldás [17-20]. A legnagyobb sikert elért rendszereknél a robotok valamilyen „általános” érzékelőjét
(pl. erőmérő, távmérő, stb.) használják fel implicit kommunikációs
csatornaként. Talán a legismertebbek az erő-visszacsatolásos kooperatív tárgymozgató rendszerek, ahol kettő vagy több robot mozgat valamilyen nehéz tárgyat, és a megfogójukon elhelyezett erőérzékelőn fellépő erőhatások (húzóerő, nyomóerő) hatására változtatják a pozíciójukat. Itt különösen nagy problémát jelent a mozgások kölcsönös szinkronizációja, mely egy külön kutatási terület. Ezek az alternatív kommunikációs megoldások [13-16] a kollaborációs döntések támogatására csak bizonyos körülmények között, általában jól meghatározott feladatokra alkalmazhatók. Rugalmasságuk kicsi, az implicit kommunikáció korlátai miatt nehezen általánosítható. Biztató eredményeket explicit és implicit kommunikációs csatornák szinergiájától várhatunk [21], ami tulajdonképpen az emberi kommunikációnak is sajátja. Az előzőekben ismertetett kommunikációs módszerek esetében, főleg az implicit kommunikáció bizonytalanság kezelő képességének és így alkalmazhatóságának kiterjesztésére a fuzzy kommunikáció adhat megoldást. 11
DOI: 10.15477/SZE.MMTDI.2015.001
1.5. Fuzzy kommunikáció A fuzzy kommunikáció megnevezést használjuk azokra, az egyébként esetenként nagyon eltérő kommunikációs eljárásokra, ahol a bizonytalanságokat fuzzy módszerekkel kezelik. A fuzzy kommunikáció egyik legnagyobb előnye, hogy képes nyelvi kifejezésekkel dolgozni, ami az ember mindennapi életében használt kommunikáció alapeleme. Ezeket a nyelvi elemeket tömör, kódolt üzenetekben továbbítja. Lássunk egy példát: Az üzenet: „Ma meleg van, valószínűleg holnap forróság lesz.” A példában szereplő mondatot könnyen értelmezni tudja az ember, bár a benne szereplő nyelvi szimbólumok nem tökéletesen meghatározottak. A fuzzy kommunikáció Pedrycz szerinti [22] alapsémája a 3. ábrán látható.
3. ábra Fuzzy kommunikációs csatorna [22]
Az ábrán látható emberek közötti információ átadás alapvető eleme a kódkönyv, amit minden résztvevő birtokol. Ez a kódkönyv úgy is tekinthető, mint egy megosztott tudásbázis, amely az értelmezhető nyelvi üzeneteket tartalmazza. A két résztvevőt nevezzük adónak és vevőnek, akik rendelkeznek legalább egy olyan kódkönyvvel, amelyben az aktuális információcseréhez szükséges kifejezések szerepelnek, és ezek alapján képesek az üzenet hatékony kódolására és dekódolására. Az előbbiek alapján a fuzzy kommunikáció két fontos alapeleme [22]:
A fuzzy kódoló: kódolja a bemeneti információkat.
A fuzzy dekódoló: dekódolja az átküldött üzenetet.
12
DOI: 10.15477/SZE.MMTDI.2015.001
A fuzzy információk kódolását és dekódolását a fuzzy következtető rendszerekből már jól ismert módon illeszkedési mérték meghatározásnak és defuzzifikálásnak is szokták nevezni. A fuzzy kommunikációval részletesebben foglalkozom a 4.1.2. fejezetben. Az előbbiek alapján is látható, hogy a napjainkban kommunikáció nem számít extrém feladatnak, mégis az információ sérülékenysége, a torzulások, zavarok miatt vagy egyszerűen a részben meghatározott szimbólumokból adódó információhiány félreviheti, sőt blokkolhatja a kooperációs képességet. Ezért az információhiányos kommunikáció problémáját én egy fontos és érdekes kutatási területnek tartom, és a következőkben ezzel foglalkozom. A kutatásaimban arra a kérdésre kerestem a választ, hogy megoldható-e a résztvevők közti explicit kommunikáció nélkül egy olyan feladat, melyhez robotok együttműködése szükséges. A megoldást alapvetően a fuzzy kommunikációs modell kiterjesztésében kerestem. Ezen a területen belül is a kódkönyvek kialakításának és használatának módjait, és ezek feladatvégzési képességre gyakorolt hatását vizsgáltam. Érezhető, hogy a rendelkezésre álló kódkönyv alapvetően meghatározza a kommunikáció sikerességét és hatékonyságát. Az ember nagyon hatékonyan és automatikusan képes kezelni a saját kódkönyveit. Ezért a számítási intelligencia módszerek egyik fontos kutatási területe a kódkönyvek kialakítása, módosítása, a tanulási folyamatok kidolgozása. A ködkönyveknél a fő problémát a komplex rendszerek modellezése, bonyolult és nem egyértelmű adatok kezelése jelenti [23-27]. Ezen a területen a fuzzy logikát és fuzzy modellezést széles körben alkalmazzák [28-40]. A komplex feladatok egyre bonyolultabb fuzzy szabályrendszerrel kezelhetők, mely a számítási és tárkapacitás-igény rohamos növekedését okozza, végül kezelhetetlenné téve a rendszert. Számos módszer létezik a szabálybázis komplexitásának csökkentésére [41-57], ezekhez hasonlóan a fuzzy szignatúra módszer is hatékonyan alkalmazható hierarchikusan strukturált adatok tömör leírására [58-60]. Az értekezésben leírt kutatásaim kiinduló pontja a fuzzy szignatúra kódkönyvekre épülő
kontextusfüggő
robotkörnyeztre
való
rekonstruktív adaptálása
volt.
kommunikációs A
algoritmusok
kontextusfüggő
[22,
rekonstruktív
61] fuzzy
kommunikáció egyfajta kiterjesztése az implicit kommunikációs eljárásoknak [15, 16]. 13
DOI: 10.15477/SZE.MMTDI.2015.001
A kommunikációs rendszereken tett vizsgálódásaimat egy konkrét robot kooperációs feladatra szűkítettem, ahol egy robot csoportnak (3 robot) együttműködve kell elvégeznie egy rendezési feladatot. A feladat érdekessége abban rejlik, hogy az együttműködést explicit kommunikáció nélkül, egymás és a környezet megfigyelésével kell végrehajtaniuk. Részletes leírás a 4.1.4. fejezetben olvasható. A kutatás során kidolgoztam egy, a feladat szempontjából az egyszerű fuzzy szignatúránál hatékonyabb leírási módszert: a fuzzy szituációs térképet. A fuzzy szituációs térkép, mint több dimenziós geometriai struktúrával rendelkező szignatúra képes tömör formában tárolni a komplex információkat, miközben a hiányzó adatok kezelését is megoldja. Javaslatot tettem a többrétegű fuzzy szituációs térkép bevezetésére, mellyel elkerülhető a dimenziónövelésből adódó exponenciális komplexitás növekedés. Kidolgoztam a fuzzy szituációs térkép belső adatkapcsolatainak kezelési metódusát is. Kutatási eredményeim kipróbálására és igazolására létrehoztam egy szimulált robotkooperációs környezetet, mely egy valós rendszer hű modellje. A környezet széles körben alkalmas bonyolult robot kooperációs feladatok modellezésére és integrálására különböző algoritmusfejlesztő eszközökbe (pl. Matlab, VirCA [62]).
14
DOI: 10.15477/SZE.MMTDI.2015.001
2. Fuzzy és fuzzy szignatúra módszerek áttekintése 2.1. Fuzzy rendszerek alapjai A logikus döntések és irányítások gépi megvalósításának alapeszköze a matematikai logika és azon belül is a Boole féle kétértékű logika. A klasszikus alapokra épített rendszerek mindaddig jól működnek, amíg „egyértelmű” jól definiált szimbólumokkal és helyzetekkel van dolguk. A bizonytalanság modellezésére viszont nagyon csekély mértékben és nehézkesen alkalmazhatók. Ezt már korán érzékelték a téma kutatói és több kísérlet is történt az „igaz” és „hamis” két értékének árnyalására, vagyis a többértékű logikák bevezetésére. Elsőként a háromértékű logikák alkalmazása merült fel, majd azok általánosításaiként az n-értékű (Lukasiewicz) logikáké is [63]. Sok olyan állítás van, melyről nem lehet élesen eldönteni, hogy igaz-e vagy hamis, hanem csak valamilyen mértéket lehet rendelni az igazságtartalmához. A bizonytalanság oka lehet az ismeretek határozatlansága, hiánya és/vagy a nem egyértelmű információk. Nyilvánvalóvá vált, hogy ha bonyolult feladatok megoldására alkalmas intelligensebb eszközöket szeretnénk létrehozni, úgy érhetünk el jobb eredményt, ha az emberi logikához jobban közelítő módon írjuk le a rendszerek viselkedését. Ez a gondolat vezette el az 1960-as években L.A. Zadeh-t a fuzzy logika alapjainak letételéhez [64]. A fuzzy logika a hagyományos logika kiterjesztése. A fuzzy logikai változó a 0 és az 1 érték között tetszőleges értéket vehet fel, a 0 jelöli a „teljesen hamis” állítást, az 1 pedig a „teljesen igaz”-at. Ilyen értelemben a 0.5 érték jelenti a „félig igaz” állítást, és például a 0.9 a „majdnem igaz”-at. A hagyományos logikai műveletek is kiterjeszthetők fuzzy logikára, ám a Boole algebra axiomatikus tulajdonságai csak részben őrizhetők meg. Definiálhatunk fuzzy halmazokat, fuzzy produkciós szabályokat és következtető rendszereket is létrehozhatunk. A következőkben a fuzzy halmazokat, a fuzzy halmazokon értelmezett alapműveleteket, a fuzzy relációkat, a fuzzy szabályokat és a fuzzy következtető rendszereket tekintem át.
2.1.1. Fuzzy halmazok A hagyományos halmazelméletben valamely X alaphalmaz egy A halmazát megadhatjuk például a karakterisztikus függvénye segítségével, amely minden olyan x
15
DOI: 10.15477/SZE.MMTDI.2015.001
alaphalmazbeli értékhez 1-et rendel, amelyik eleme az A halmaznak, a többi x értékhez pedig 0-t: 1, ha x A 0, ha x A.
A x
(1)
Legyen X x egy (hagyományos értelemben vett) alaphalmaz (univerzum). Minden egyes x X alaphalmazbeli érték egyértelműen vagy eleme az A halmaznak vagy pedig nem eleme az A halmaznak. A fuzzy halmazok folyamatossá teszik a két halmazhoz tartozás közötti átmenetet, egy halmazhoz való tartozás illetve nem tartozás között tetszőleges átmenetet megengedve. A fuzzy halmazok határa tehát nem éles (crisp), hanem elmosódott. Az A fuzzy halmaz az X alaphalmazon az úgynevezett tagsági függvénnyel adható meg [64]. A tagsági függvény minden egyes x X alaphalmazbeli értékhez egy, a [0,1] intervallumból vett értéket rendel aszerint, hogy az adott x érték mekkora mértékben eleme (tagja) az A fuzzy halmaznak:
A : X 0,1 ,
(2)
ahol µA az A fuzzy halmaz tagsági függvénye, mely egyértelműen megadja a halmazt, ha magát az X alaphalmazt ismerjük. Gyakorlati célokra különféle alakú tagsági függvényeket szoktak definiálni. A gyakorlati alkalmazások céljából a műszaki rendszerekben leginkább a szakaszonként lineáris, elsősorban háromszög, a trapéz és egyes alkalmazásokban a Gauss-görbe alakú tagsági függvények terjedtek el. Az 4. ábrán a „kb. 5” valós fuzzy szám leírását láthatjuk különféle alakú tagsági függvényekkel.
4. ábra. Tagsági függvény alakok
A háromszög alakú esetben csak az x = 5-nél kapunk 1-es tagsági értéket, a trapéz alakúnál az 5-nél kicsit kisebb és az 5-nél kicsit nagyobb értéket is 1-es értékűnek vesszük, míg a Gauss görbénél elvileg még a távoli valós számok sem kapnak pontosan 0 értéket. Ez a koncepció tehát kiválóan alkalmazható mérési bizonytalanságok, zajok megfelelő 16
DOI: 10.15477/SZE.MMTDI.2015.001
kezelésére is. Az ábrán látható tagsági függvények paramétereinek különböző beállításaival megfelelően finom átmenetet lehet elérni a 0-ás és az 1-es érték között. A 5. ábrán emberi magasságokat láthatunk fuzzy halmazokkal jellemezni. Három kategóriát különböztethetünk meg: „alacsony”, „középtermetű” és „magas” halmazokat. A tagsági függvények ebben a példában trapéz alakúak. Az ábrán jól látszanak a fuzzy megközelítés előnyei a hagyományos kétértékű logikával szemben. Kétértékű esetben éles lenne az átmenet, a 164 cm-es ember 1-es értékkel lenne „alacsony”, a 166 cm-es pedig 0 mértékkel (egyáltalán nem) számítana „alacsony”-nak. Fuzzy halmazokkal az átmenetet sokkal finomabban lehet megadni.
5. ábra. Emberek magasságát jellemző fuzzy halmazok
Egy A fuzzy halmaz magján azt a crisp halmazt értjük, mely az alaphalmaz azon elemeit tartalmazza, amelyeknek a tagsági értékük az A fuzzy halmazban 1: core A x X A x 1 .
(3)
A halmaz tartója pedig a pozitív tagsági értékű alaphalmazbeli elemeket jelenti: supp A x X A x 0 .
(4)
Az A fuzzy halmaz α-vágata valamely 0,1 értékre azokat az alaphalmazbeli elemeket tartalmazó halmaz, amelyek tagsági értéke az A fuzzy halmazban legalább α: A x X A x .
(5)
Ha az egyenlőséget nem engedjük meg, akkor a szigorú α-vágat definíciójához jutunk. Egy fuzzy halmaz konvex, ha minden α-vágata konvex. Az A fuzzy halmaz
17
DOI: 10.15477/SZE.MMTDI.2015.001
magassága a tagsági függvényének legnagyobb felvett értéke, vagy ha az nem értelmezhető, akkor a tagsági értékek felső határa: h A sup A x .
(6)
x X
Egy fuzzy halmaz akkor normális, ha a magassága 1.
2.1.2. Műveletek, relációk és következtetés fuzzy halmazokon A hagyományos halmazelméletben értelmezett három alapműveletet végtelen sokféleképpen lehet általánosítani a fuzzy halmazok elméletében. A legelterjedtebbek a klasszikusnak számító Zadeh-féle definíciók [64]. Egy X alaphalmazon értelmezett A fuzzy halmaz Zadeh-féle komplemense A , ahol minden x X értékre:
A x 1 A x .
(7)
Az A és B fuzzy halmazok Zadeh-féle metszete:
A B x min A x , B x ,
(8)
Zadeh-féle uniója pedig:
A B x max A x , B x .
(9)
A Zadeh-féle műveletek illusztrációi a 6. ábrán láthatók. Ha a tagsági függvényérték csak 0 és 1 lehet (crisp eset), akkor a hagyományos komplemens, metszet és unió műveleteket kapjuk vissza. A három alapművelet sok egyéb módon is definiálható. Néhány általánosan elfogadott alap axiómát azonban mindig ki kell elégíteniük ezeknek a műveleti definícióknak. 2.1.2.1. Fuzzy komplemensek A fuzzy komplemens képzés az egyváltozós c : 0,1 0,1 függvénnyel adható meg. A függvénynek a következő két axiómát kell teljesítenie: 1. axióma.
c 0 1 és c 1 0 ( peremfeltételek ).
2. axióma.
a, b 0,1 esetén, ha a b, akkor c a c b ( monotonitás ).
18
DOI: 10.15477/SZE.MMTDI.2015.001
6. ábra. Zadeh-féle (Standard) fuzzy műveletek
Ezeken kívül még általában a következő enyhébb (3a), vagy erősebb (3b) axiómát is meg szokás követelni a komplemenstől: 3a. axióma.
c folytonos függvény.
3b. axióma.
a 0,1 re c c a a , vagyis c involutív.
(3b teljesülése esetén 3a biztosan kielégül.) Mind a három (illetve négy) axiómának eleget tevő, két általános komplemens osztály, a Sugeno- és a Yager-féle komplemens. A Sugeno-komplemens alakja [65]: c a
1 a , 1 a
ahol 1, . 0 esetén a Zadeh-féle komplemenst
(10) kapjuk. A Yager-
komplemens általános alakja: 1
c a 1 a ,
(11)
ahol 0, . 1 esetén itt is visszakapjuk a Zadeh-féle komplemenst. 19
DOI: 10.15477/SZE.MMTDI.2015.001
2.1.2.2. Fuzzy metszetek A fuzzy metszetképzés általánosított műveletét egy geometriai valószínűségi analógia alapján (trianguláris) t-normának nevezzük, és a következő kétváltozós függvénnyel adjuk meg: t : 0,1 0,1 0,1
(12)
A t-normára vonatkozó axiómák [63]: 1. axióma.
a 0,1 re t a,1 a ( peremfeltétel ).
2. axióma. a, b, c 0,1 re b c ből következik , hogy t a , b t a, c ( monotonitás ).
3. axióma.
a, b 0,1 re t a, b t b, a (kommutativitás ).
4. axióma.
a, b, c 0,1 re t a, t b, c t t a, b , c ( asszociativitás ).
5. axióma.
t folytonos függvény.
6a. axióma.
t a, a a ( szubidempotencia ), vagy
6b. axióma. t a, a a (idempotencia ). 7. axióma.
Ha a1 a2 és b1 b2 , akkor t a1 , b1 t a2 , b2 ( szigorú monotonítás ).
A leggyakrabban használt t-normák a Zadeh-félén kívül az algebrai szorzat: t a, b ab,
(13)
t a , b max(0, a b 1),
(14)
a, ha b 1, tmin a, b b, ha a 1, 0, egyébként.
(15)
a korlátos különbség:
és a drasztikus metszet:
20
DOI: 10.15477/SZE.MMTDI.2015.001
2.1.2.3. Fuzzy uniók A fuzzy unióképzés műveletét a t-normával való duál kapcsolata miatt tkonormának (vagy másként s-normának) nevezzük és szintén kétváltozós függvénnyel adjuk meg: s : 0,1 0,1 0,1
(16)
A t-normához hasonló axiómákat követelünk meg az s-normától is [63]: 1. axióma.
a 0,1 re s a , 0 a ( peremfeltétel ).
2. axióma. a, b, c 0,1 re b c ből következik , hogy s a, b s a, c ( monotonitás ).
3. axióma.
a, b 0,1 re s a, b s b, a ( kommutativitás ).
4. axióma.
a, b, c 0,1 re s a, s b, c s s a, b , c ( asszociativitás ).
5. axióma.
s folytonos függvény.
6a. axióma.
s a, a a ( szuperidempotencia ), vagy
6b. axióma.
s a, a a (idempotencia ).
7. axióma.
Ha a1 a2 és b1 b2 , akkor s a1 , b1 s a2 , b2 ( szigorú monotonítás ).
A leggyakrabban használt s-normák a Zadeh-félén kívül az algebrai összeg: s a, b a b ab,
(17)
s a, b min(1, a b),
(18)
a , ha b 0, smax a , b b, ha a 0, 1, egyébként.
(19)
a korlátos összeg:
és a drasztikus unió:
A t- és s-normák alkalmas megválasztásával, illetve ezek együttes felhasználásával különböző mértékű szubjektivitást tudunk belevinni a halmazműveletekbe, mivel érvényesek a következő korlátok:
21
DOI: 10.15477/SZE.MMTDI.2015.001
tmin a, b t a, b min a, b
(20)
max a, b s a, b smax a, b .
(21)
illetve
Ilyenkor az egyenlőtlenségek baloldalai jelentik a „pesszimista”, a jobboldali pedig az „optimista” szemléletmódot. A fuzzy operátorok közül a Dombi operátorok megközelítése az egyik legérdekesebb, mely operátorokkal az alapműveletek sajátos egységben szemlélhetők. A Dombi operátorokkal részletesen a [66, 67] foglakozik. 2.1.2.4. Fuzzy relációk A két vagy több halmaz elemei közötti kapcsolat mértékét fuzzy relációkkal írhatjuk le. Ez a fogalom a klasszikus (crisp) reláció fogalmát általánosítja, amelynél két vagy több elem közötti kapcsolat vagy fennáll, vagy pedig nem. A fuzzy relációt a halmazokhoz hasonlóan a tagsági függvénnyel adhatjuk meg:
R x ,, x : X 0,1 , 1
n
(22)
ahol X X1 X 2 X n , a relációban szereplő alaphalmazok Descartes-szorzata. Az n alaphalmaz Descartes-szorzatával képzett halmaz egy x elemének részsorozata egy y elem
y x akkor,
ha y j x j minden j J -re, J n , ahol y y j j J a
jJ X j halmaz eleme és J n . Egy X 1 X 2 X n halmazon értelmezett fuzzy
relációnak egy szűkebb Y halmazcsaládra vett projekcióját (vetületét) a R Y y max R x
y x
(23)
összefüggés alapján határozhatjuk meg. A projekció bizonyos értelemben vett inverzének tekinthető a hengeres kiterjesztés:
R X Y x R y
(24)
minden x -re, amelyre y x . Egy R fuzzy reláció valamely projekcióinak hengeres lezártja:
cylP x min P X Y x i
iI
i
i
(25) 22
DOI: 10.15477/SZE.MMTDI.2015.001
ahol Yi az a halmazcsalád, amelyen a Pi projekció definiálva van. 2.1.2.5. Fuzzy szabályok A fuzzy halmazok segítségével természetes emberi nyelven könnyen lehet szabályokat megfogalmazni. Egy fűtési rendszerben például mondhatunk egy olyan szabályt, hogy „Ha kicsit hideg van és a hőmérséklet süllyed, akkor közepesen fűts”. Ha ezután definiáljuk a hőmérsékletre, a hőmérsékletváltozásra és a fűtésre vonatkozó tagsági függvényeket, akkor fuzzy szabályhoz jutunk. Az egy bemenetű, egy kimenetű egyszerű fuzzy szabály alakja: R: Ha x = A akkor y = B. ahol x X a bemeneti változó, y Y a kimeneti változó, X a bemeneti változó alaphalmaza, Y a kimeneti változó alaphalmaza. A és B nyelvi változók. Az A az R szabály antecedense (premisszája), a B pedig az R szabály konzekvense (konklúziója). Több bemenetű, egy kimenetű fuzzy szabály általános ún. Mamdani-féle (ortogonálisan dekomponált) alakja [68]:
R : Ha x1 A1 és és xn An akkor y B. ahol x x1 , , xn a bemeneti értékek vektora, x j X j , X X 1 X 2 X n az n-dimenziós alaphalmaz, A A1 , An az antecedens halmazok vektora, A X , y Y a kimeneti változó, Y a kimeneti változó alaphalmaza, B a konzekvens halmaz, B Y . A szabály alkalmazásának feltétele, hogy az összes bemeneti változó pozitív mértékben essék a megfelelő antecedens halmazba. Több kimenetű szabályok esetén a kimenetek függetlenek egymástól, ezért az ilyen szabályok dekomponálhatók a fentivel megegyező alakú egy kimenetűre, csökkentve ezzel a számítási igényt. 2.1.2.6. Mamdani-típusú fuzzy következtető rendszerek A fuzzy halmazok elmélete felhasználható bonyolult, analitikus módon nem modellezhető rendszerek kezelhető leírására. Fuzzy szabályok segítségével az emberi gondolkodáshoz hasonlító következtető rendszerek hozhatók létre. A fuzzy rendszer vázlata a 7. ábrán látható. Az illeszkedési mértéket meghatározó egység a megfigyelést hasonlítja össze a szabályok feltételrészeivel. Ennek alapján a következtető gép valamilyen következtetési algoritmussal meghatározza a kimeneti fuzzy halmazt. Többféle 23
DOI: 10.15477/SZE.MMTDI.2015.001
következtetési módszer ismert, gyakorlati alkalmazásokban legelterjedtebb a Mamdanimódszer [68]. A kimenetet defuzzifikációs egységgel alakítja át éles (crisp) értékre.
7. ábra. Fuzzy következtető rendszer vázlata
A szabálybázis tartalmazza a problémát leíró szabályokat, melyek a következő Mamdani féle egyszerű alakban írhatók le [68]: Ri : Ha x1 A1,i és és xn An ,i akkor y Bi ,
ahol x x1 , , xn a bemeneti vektor, y a kimenet, Ai A1,i An ,i az antecedens halmazok vektora, Bi pedig a konzekvens halmaz az i. szabályban. A szabályokat alkotó nyelvi változóknak olyan fuzzy halmazokat kell tartalmazniuk, melyek együttesen legalább α-vágataik uniójával lefedik a változó alaphalmazát, azaz bármely bemenetre van olyan fuzzy halmaza a változónak, mely (ahol 0.5 ) tagsági értékű az adott bemenetre vonatkozóan (sűrű α fedettség). Vagyis, ha egy nyelvi változó lehetséges értékei az A1 An fuzzy halmazok, akkor x X -re i 1, n , hogy Ai x teljesül valamely pozitív ε-ra (ε lefedettség). Ez azért szükséges, hogy minden megfigyelésre legyen olyan szabály, amely alapján a rendszer képes valamilyen következtetést meghozni. 2.1.2.6.1. Az illeszkedési mérték meghatározása A következtetés elején meghatározásra kerül, hogy az adott bemenet mennyire illeszkedik a szabályokra. A megfigyelésvektor minden egyes eleme összehasonlításra kerül mindegyik szabály feltételrészének ugyanezen komponensével. Legyen A* az ndimenziós megfigyelésvektor. 24
DOI: 10.15477/SZE.MMTDI.2015.001
Az illeszkedési (tüzelési) mérték a j. dimenzióban az i. szabályban:
w j ,i max min A x j , Aj ,i x j xj
j
(26)
(8. ábra), ahol A j ,i x j az i. szabály j. dimenziójának tagsági függvénye.
8. ábra. Illeszkedési mérték meghatározása
Ha a megfigyelés crisp vektor, akkor a fenti összefüggés a következőre egyszerűsödik: x∗ állapot (helyzet-) vektor esetén, a j. dimenzióban az illeszkedés mértéke: w j ,i Aj ,i xj .
(27)
Miután minden dimenzióban meghatározásra került az illeszkedés mértéke, az eredő kiszámítása történik az egész antecedensre vonatkozóan. Egy szabály alkalmazhatóságának (érvényességének) a mértékét antecedense minden egyes dimenziójának illeszkedési mértéke együttesen befolyásolja. Egy Ri szabály tüzelési mértéke a szabály antecedensei illeszkedési mértékeinek a minimuma lesz: n
wi min w j ,i .
(28)
j 1
A wi értéke azt adja meg, hogy az Ri szabály mekkora mértékben befolyásolja a következmény előállítását az A* megfigyelés esetén. 2.1.2.6.2. A következtetés Miután egy megfigyelésre minden egyes Ri szabályhoz meghatározásra került, annak wi tüzelési súlya, a szabályhoz tartozó következtetés előállítása történik. Ez a szabály konzekvensének wi-vel való „csonkolásával” (azaz halmazmetszetével) történik. A szabályhoz tartozó következtetés:
B y min wi , B y i
i
(29) 25
DOI: 10.15477/SZE.MMTDI.2015.001
(9. ábra). A teljes szabálybázishoz tartozó következtetést az így kapott Bi következtetések uniójaként állítható elő: r
B y max B y ,
i 1
i
(30)
ahol r a szabályok száma, uniónak pedig a Zadeh-féle műveletet használtuk.
9. ábra. Szabály következménye
A 10. ábrán a teljes következtetés látható egy éles bemenetre. A Mamdanikövetkeztetésen kívül a gyakorlatban használatos más műveleteken alapuló eljárás is. Az elterjedt Larsen-módszernél [69] csonkolás helyett a tüzelési súllyal történik a következmény szorzása, azaz a Zadeh-féle művelet helyett algebrai metszet alkalmazható:
B y max wi B y . r
i 1
i
(31)
2.1.2.6.3. Defuzzifikáció A következtetés eredőjeként a B* fuzzy következményhalmazt kapjuk. Legtöbbször azonban egy rendszer kimeneteként nem fuzzy halmazt várunk, hanem éles értéket, mely konkrétan megadja a beavatkozás mértékét vagy módját. Ennek értelmében meghatározandó az az éles kimenet, amely a következtető gép által eredményezett fuzzy halmazt a legjobban jellemzi.
26
DOI: 10.15477/SZE.MMTDI.2015.001
10. ábra. Teljes Mamdani-következtetés
Ez az eljárás a defuzzifikáció, melyre számos módszer ismert az irodalomban [70]. Az egyik a geometriai középpont módszer (COA), melynél a kimenet a következőképpen számítható ki:
yCOA
B y ydy
yB
yB
(32)
B y dy
Ennek hátránya, hogy bonyolult alakú B* következmény esetén az integrál nehezen számolható. Egyszerűbb a hasonló elven alapuló, igen elterjedt súlypont módszer (COG):
r
yCOG
i 1 yB r
B y ydy
i 1 yB
i
B y dy
.
(33)
i
Ezt egyszerűbb számolni, mert itt az egyes Bi részkonklúziók külön integrálhatók. Viszont az átlapolódó területeket többszörösen veszi figyelembe. Egy másik defuzzifikációs eljárás a középső maximum módszer (COM), mely a legnagyobb tagsági értékkel rendelkező kimenetek közül a legnagyobb és a legkisebb y érték átlagát adja vissza eredményként. A magasság módszer is a fontosabb defuzzifikációs technikák közé tartozik. E módszer lényege, hogy mindegyik részkonklúzió legnagyobb tagsági értékű y
27
DOI: 10.15477/SZE.MMTDI.2015.001
értékeinek közepeit a részkonklúziók magasságaival súlyozva számítja a defuzzifikált y-t. A COG és a COM módszer összevetését illusztrálja a 11. ábra.
11. ábra. Példák defuzzifikációra
2.1.2.7. Takagi-Sugeno-típusú fuzzy irányítási rendszerek A Mamdani-típusú fuzzy rendszerekhez képest alternatívát jelentenek az olyan rendszerek, amelyekben a szabályok konzekvense nem fuzzy halmaz, hanem valamilyen y f x függvény. A szabályok általános alakja az ilyen típusú rendszerekben: Ri : Ha x1 A1,i és és xn An ,i akkor yi f i x1 , , xn ,
ahol xi , i 1, n a bemeneti változók, fi pedig n-változós függvény. Ha fi konstans, akkor (nulladrendű) Sugeno, ha a bemenetek lineáris függvénye, akkor Takagi-Sugeno (vagy elsőrendű Sugeno), ha pedig magasabbrendű függvény, akkor Takagi-Sugeno-Kang (vagy általános Sugeno) fuzzy rendszerről beszélünk [71]. A következtetés menete hasonló a Mamdani-típusú rendszerekéhez, azaz először a szabályok illeszkedési mértékét határozzuk meg az adott megfigyelésre. Az illeszkedési mértékek alapján a kimenet könnyen számítható:
w y y w r
i 1 r
i 1
i
i
r i 1
wi f i xi , , xn
i
r
w i 1 i
.
(34)
Nulladrendű Sugeno esetben, amikor a kimenetek konstansok (ci), az eredő kimenet még egyszerűbb alakú:
w c . y w r
i 1 r
i 1
i
i
(35)
i
28
DOI: 10.15477/SZE.MMTDI.2015.001
A Sugeno típusú rendszerek előnye, hogy nincs szükség defuzzifikációs lépésre, így a kimenet gyorsabban számítható. A Mamdani- és Takagi-Sugeno-típusú rendszerek határértékben ekvivalens voltát tárgyalja [72].
2.2. Fuzzy következtető algoritmusok bonyolultsága A számítási algoritmusok legfontosabb jellemzői között vannak a tárigény és futási időigény, melyek a hardver szemszögéből az algoritmus „bonyolultságát” jellemzik. Mivel a fuzzy logika egyik legfőbb felhasználási területe az irányítás, ahol a kvázi valósidejű működés alapfeltétel és a számítási kapacitások korlátosak (pl. egy robot fedélzeti számítógépe), a szabályrendszer bonyolultsága és a következtetés időigénye fontos kérdés. Az alapvető, szabálybázis alapú, fuzzy irányítási algoritmusok [68, 73, 74] bonyolultságának vizsgálatához határozzuk meg, hány szabály szükséges a k dimenziós
X X1 X 2 X k bemeneti alaphalmaz teljes ε-lefedéséhez (ε > 0). Legyen az egyes Xi bemeneti halmazok lefedéséhez felhasznált fuzzy halmazok száma legfeljebb T. Ekkor az alaphalmaz teljes ε-lefedéséhez R O T k
(36)
szabály szükséges, amely rendkívül magas érték, amennyiben k értéke nem kicsi. Még abban a szélsőséges esetben is, amikor állapotváltozónként mindössze két nyelvi változót adunk meg, a teljes lefedéshez 2k, azaz exponenciális nagyságrendű szabályszám szükséges.
2.2.1. A komplexitás csökkentésének lehetőségei A klasszikus fuzzy következtető eljárások bonyolultságát először Kóczy vizsgálta [75, 76]. Gyakorlatilag, a számítási időigény exponenciális növekedése miatt a hagyományos fuzzy irányítási rendszerek csak maximum 5 – 10 bemenetet tudnak kezelni. Ez a tény jelentősen korlátozza a fuzzy irányítási algoritmusok valós idejű alkalmazhatóságát bonyolult, sokdimenziós feladatok megoldására. A problémát az is fokozza, hogy a fuzzy algoritmusokat alapvetően matematikailag nem ismert rendszerekhez alkalmazzák, és éppen ezért nincsen kidolgozott matematikai háttér a szabályok számának és helyének valamilyen optimális kritérium szerinti meghatározására. A matematikai modell hiányában sokszor a szükségesnél jóval több 29
DOI: 10.15477/SZE.MMTDI.2015.001
antecedens halmaz kerül felhasználásra, ami bár jobb közelítést eredményezhet, ám ezáltal nagymértékben nő a szabálybázisban lévő fölösleges információ. Így, az egyre jobban elterjedő és egyre szélesebb problémakörben alkalmazni kívánt fuzzy következtetésen alapuló eljárások számítási idő- és tárkomplexitásának csökkentése fontos kérdéssé vált, ami a 90-es évek elejétől egyre több kutatót sarkall alternatív redukciós eljárások kidolgozására [63]. A redukciós módszerek jellegük alapján két fő csoportba sorolhatók. Az elsőbe azok az eljárások tartoznak, melyek olyan új vagy módosított következtetési módszert alkalmaznak, amelynek számítási bonyolultsága kisebb. Ebbe a csoportba tartozik a Zadeh-féle eljárás kompakt alaphalmazon működő változata [75, 77]. Másik megoldás a Stoica által javasolt, szakaszonként lineáris nyelvi változók esetén alkalmazható módszer, mely α-vágatokként számítja közvetlenül a defuzzifikált eredményt, s így jelentősen csökkenti az időigényt [78]. Szintén csökkentett számítási eljárás a Yu és Bien által javasolt minimum távolságalapú eljárás [79]. A komplexitás csökkentésének másik módja a szabályok (r), illetve a nyelvi változók (T) számának, összefoglalóan a szabálybázisnak a redukálása. Amint azt korábban említetem, a szabályszám minimumának elvi alsó korlátja 2k, ami ugyan továbbra is exponenciális kifejezés, de még így is jelentősen csökkenthető az időigény, különösen akkor, ha a redukció előtt T értéke nagy volt. További lehetőség a kitevő (k) csökkentése az esetleges redundáns állapotváltozók elhagyásával, illetve összevonásával. Ebbe a csoportba tartozó eljárások elsősorban nem új következtető algoritmusok, hanem
a
már
behangolt
szabálybázisok
információtartalmának
tömörítésére,
redundanciájuk megszüntetésére alkalmas módszerek. Ezen eljárásoknak akkor van nagy jelentőségük, ha a szabálybázis előre elkészíthető, alkalmazása közben további hangolást nem igényel, és így a tömörítés után már kisebb memória- és számításkapacitással rendelkező módszerekben is alkalmazhatók. Ebbe a csoportba sorolható a Bruinzel és munkatársai által ismertetett módszer, melynek célja egyes bemeneti változók összevonása [80]. Szinguláris értékfelbontáson (SVD) alapuló információtömörítő módszert javasol a szabálybázis redukálására Wang és munkatársai [81], és Yam [82] eljárása Sugeno-típusú irányítás esetén. Ezen eredmények tetszőleges szabálybázisra történő általánosítása található az [83-86] munkákban. Szintén szinguláris értékfelbontáson alapul a különlegesen nagy szabálybázisok tömörítését elvégző algoritmus [87], amely csak az aktuálisan tüzelő szabályokhoz kapcsolódó információkat csomagolja ki futás közben, 30
DOI: 10.15477/SZE.MMTDI.2015.001
amivel lényegesen csökkenti a tárigényt. Kedvező esetben a módszer alkalmazásával kiiktatható a háttértárból történő adatbeolvasás, s mivel a legtöbb számítógépes architektúrán az operatív memóriában tárolt információ sokkal gyorsabban elérhető, ezáltal a futási idő is számottevően csökkenhet. A szabálybázisredukciós-módszereken belül külön figyelmet érdemel a szabályok hierarchikus rendezését javasoló technika, amelyet először Sugeno alkalmazott a vezetőnélküli helikopter vezérlőrendszerének irányítására [88, 89]. Mindkét csoportba besorolhatóak a fuzzy szabályinterpolációs algoritmusok. Az első fuzzy szabályinterpolációs eljárást Kóczy és Hirota javasolta [41, 42, 90]. További fuzzy szabályinterpolációs metódusok és interpolációval kapcsolatos kutatások találhatók a [50, 91-101] művekben. A fuzzy szignatúrát, mint a vektor értékű fuzzy halmazok általánosítását [58], struktúrájából adódó hierarchikus felépítése alkalmassá teszi a következtető algoritmusok bonyolultságának csökkentésére.
2.3. Fuzzy szignatúrák A Zadeh által 1965-ben bevezetett fuzzy halmazok [64] kiterjesztéseként vezette be 1967-ben Goguen az L-fuzzy halmazokat [102], amelyek tagsági függvénye abban különbözik az eredeti fuzzy halmazokétól, hogy az X alaphalmaz minden eleméhez egy L, tetszőleges, (részben rendezett) háló egyik elemét rendeli hozzá:
AL : x L,
x X
(37)
Az L-fuzzy halmazok speciális eseteként vezette be Kóczy 1980-ban a vektor értékű fuzzy halmazokat [103], amelyek olyan speciális L-fuzzy halmazok, ahol (37)-ben az L részben rendezett háló az n-dimenziós fuzzy vektorok egy hálója, azaz L 0,1 . A n
vektor értékű fuzzy halmazok az X alaphalmaz minden eleméhez fuzzy értékek egy vektorát rendelik hozzá egyetlen érték helyett. Ezzel az alaphalmaz elemeiről többlet információ tárolható. A fuzzy szignatúra bevezetése [58] a vektor értékű fuzzy halmazok általánosításaként, azzal a kiterjesztéssel élve történt, hogy az alaphalmaz egy eleméhez rendelt vektor minden eleme lehet egy tagsági érték, vagy önmaga is lehet egy további
31
DOI: 10.15477/SZE.MMTDI.2015.001
vektor. Ezt a kiterjesztést iteratívan folytatva, akár m mélységű szignatúrák is létrehozhatók (38).
0,1 0,1 k , As : x xi i 1 , xi x ki kij , x X ij x x ij ijl l 1 j 1
(38)
A fuzzy szignatúrák struktúrája (a definícióban szereplő) egymásba ágyazott vektorokként, és a szemléletesebb fastruktúrás alakban is ábrázolható. A fastruktúrás alakban, a definícióban szereplő minden egyes beágyazott vektort a fastruktúra egy részfája írja le (12. ábra).
12. ábra Fuzzy szignatúra fastruktúrás ábrázolása
A 12. ábrán látható struktúra leírható a számításokban jobban kezelhető beágyazott vektorokkal (39): x11 x12 x 21 x221 x x222 x223 x23 x31 x32
T
(39)
A fuzzy szignatúrák tekinthetők úgy, mint speciális, több dimenziós fuzzy adatok tárolására alkalmas szerkezetek. Ebben az egyes dimenziók összefüggnek abban az 32
DOI: 10.15477/SZE.MMTDI.2015.001
értelemben, hogy a változók egy részcsoportja közösen határoz meg egy jellemzőt egy magasabb szinten. Így a komplex és jelentősen összefüggő adatokról a struktúra segítségével többlet információ tárolható. Az ilyen módon strukturált adatok valamilyen összevetése (pl. hasonlósági mérték számítása) is hatékonyabban elvégezhető a struktúra figyelembevételével. Sokszor a szakértők rendelkezésére álló információk kissé különböző struktúrával írhatók le, és ráadásul az éppen aktuális megfigyelés struktúrája is eltérő lehet. Mégis, a szakterület szakértői ez alapján meghozzák döntéseiket. A szignatúrák segítségével ezeknek a strukturális eltéréseknek a kezelésére is lehetőség nyílik. Éppen ebben, az eltérő struktúrájú szignatúrák kezelésében rejlik a fuzzy szignatúrák jelentős előnye. Továbbá, a szignatúrák segítségével a feladatról alkotott modell hierarchikus rendszerbe szervezhető [104], ami nagyon hasonló ahhoz, ahogyan az emberi szakértők gondolkodnak. Ezáltal olyan területek modellezésére lehetnek alkalmasak a fuzzy szignatúrák, mint például az orvosi döntéshozatal támogatása, ahol maguk az orvosok is nagyon sok és sokféle információ figyelembevételével hozzák meg döntéseiket. Sokszor előfordul az, hogy az adatmodell egyes elemeiről nincs elérhető információ. A hagyományos adatbányászati módszerek az ilyen adatokat az adatszűrés lépése során eldobják, mivel az a módszer nem tudja kezelni a hiányzó adatokat. Viszont a fuzzy szignatúrákkal modellezett esetekben az ilyen adatokat nem kell törölni a rendelkezésre álló adathalmazból, a fuzzy szignatúrák jelentősége ebben nyilvánul meg, hogy képesek kezelni az eltérő struktúrájú elemeket, azaz ha a struktúrából néhány adat hiányzik.
2.3.1. Fuzzy halmaz szignatúrák Az előző alfejezetben, a (38) definícióval megadott fuzzy szignatúra valójában a fuzzy szingleton szignatúra, mivel a struktúra levelein fuzzy tagsági értékek (szingletonok) szerepelnek. A fuzzy halmaz szignatúrák felépítése nagyon hasonlít az előző alfejezetben bemutatott fuzzy szingleton szignatúrák felépítéséhez. A kétféle fuzzy szignatúra struktúrája teljesen megegyezik (mindkettő ugyanúgy egymásba ágyazott vektorokból áll). A különbség abban mutatkozik meg, hogy a struktúra egyes levelein tárolt fuzzy tagsági érték helyett egy fuzzy halmaz (egy tagsági függvény) található, amint az a 13. ábrán 33
DOI: 10.15477/SZE.MMTDI.2015.001
látható. A fuzzy halmaz szignatúrában a leveleken szereplő tagsági függvényekkel szemben támasztott egyetlen követelmény az, hogy az alaphalmazuk a [0,1] intervallum legyen.
13. ábra. Fuzzy halmaz szignatúra
A dolgozatban fuzzy szignatúra elnevezést vagy a FS rövidítést fuzzy szingleton és fuzzy halmaz szignatúrák esetén is használom, így nem teszek különbséget a két típus között.
2.3.2. Műveletek fuzzy szignatúrákon A fuzzy szignatúrákon elvégezhető műveletek az 2.1.2. fejezetben bemutatott fuzzy halmazokon értelmezett műveletek kiterjesztéseiképpen definiálhatók [58]. A kiterjesztés során az alapelv az, hogy az adott műveleteket a fuzzy szignatúra levelein kell elvégezni, és az eredmény maga is egy fuzzy szignatúra. Ezeket a műveleti definíciókat Kóczy dolgozta ki kollégáival a 90-es években [58]. A szignatúra műveletek struktúrára kiterjedő változatainak sorát kutatótársaimmal alkottuk meg, melyek részletei a [60] műben olvashatók.
34
DOI: 10.15477/SZE.MMTDI.2015.001
3. Új módszerek és megközelítések a komplex strukturált adatok leírására 3.1. Fuzzy szituációs térkép A fuzzy szituációs térkép (Fuzzy Situational Map – FSM) olyan kiterjesztett fuzzy szignatúra, mely alkalmas bonyolult, akár több dimenziós sík vagy térbeli rendszerállapotok leírására és kezelésére olyan esetekben is, ahol az információk részlegesek, torzultak vagy zajosak. Az FSM két-, három- vagy akár n dimenziós is lehet. Először a legegyszerűbb kétdimenziós (2D) fuzzy szituációs térkép (14. ábra) tulajdonságait ismertetem. j 1
2
1
x11
x12
...
...
x1w
2
x21
x22
...
...
...
...
...
...
...
...
...
...
...
...
...
xh1
...
...
...
xhw
w
xij 0,1
i 1,..., h j 1,..., w
...
i
...
h
14. ábra Fuzzy szituációs térkép
3.1.1. Kétdimenziós fuzzy szituációs térkép A kétdimenziós fuzzy szituációs térkép tekinthető egy olyan geometriai rácsnak, melynek minden csomópontjában egy fuzzy tagsági érték, vagy kiterjesztett esetben fuzzy halmaz van. A fuzzy szituációs térkép rácsként (14. ábra), illetve mátrixos formában is ábrázolható (40).
x 011 FSM x021 x031 x041
x012
x013
x111 x121
x112 x211 x 221 x231
x212 x222 x232
x022 x032
x023 x033
x024 x034
x042
x043
x044
x213 x223 x233
(40)
35
DOI: 10.15477/SZE.MMTDI.2015.001
Az egyes csomópontokban lévő fuzzy tagsági értékek egy fuzzy szignatúra egyegy elemeként is értelmezhetők, így a fuzzy szituációs térkép egy többdimenziós és kötött struktúrájú fuzzy szignatúraként is leírható (15. ábra). Ezt az értelmezést követve elmondhatjuk, hogy a fuzzy szituációs térkép minden csomópontja egy további fuzzy szituációs térkép lehet, és ezt a kiterjesztést iteratívan folytatva akár z mélységű (finomságú) fuzzy szituációs térkép is létrehozható minden egyes csomópontban. Az egyes csomópontok felbontásának finomsága független egymástól. Ezt a mélységi kiterjesztési műveletet felbontás-növelésnek (Zoom-in) neveztem el. A 16. ábra mutat egy példát a mélységi kiterjesztésre az egyes rácspontokban.
x1
x
x1 x2 x3 x4
x2 x
x3 x4
x1
x21 x22 x23 x24
x2 x
x3 x4
x1
x21 x22 x23 x24
x2 x241
x
x242 x243
x3 x4
x21 x22 x23 x24
x241 x242 x243
x244 x244
x2431 x2432 x2433 x2434
15. ábra Fuzzy szituációs térkép mint többdimenziós szignatúra
Az egyes csomópontok és a hozzájuk tartozó alrácsok (növelt felbontású rácsok) összefüggnek abban az értelemben, hogy az alrácsok részcsoportjai közösen határozzák meg az egyel magasabb szint (szülő) valamely jellemzőjét. Ezzel a struktúrával az egyes csomópontoknál jelentős többletinformáció tárolható, és csak a szükséges mértékű felbontásokban feldolgozható, ami a számítási igényt nagymértékben csökkentheti. A fuzzy szituációs térkép még az egyszerű fuzzy szignatúráknál is tömörebb módon képes adatokat leírni többdimenziós hierarchikus struktúrába rendezve. A legnagyobb felbontásnál már csak fuzzy tagsági értékek vagy fuzzy halmazok lehetnek a csomópontokban, ez a mélység a szignatúrák levél szintjének felel meg. A teljesen kibontott, minden csomópontban a legfinomabb felbontást tartalmazó (z = max(z)) fuzzy szituációs térképet hívom alapstruktúrának vagy alaptérképnek. Az alapstruktúrából kiindulva a fuzzy szignatúrákhoz hasonlóan, valamilyen fuzzy művelettel (leggyakrabban valamilyen aggregációs művelettel) hozhatunk létre kisebb felbontású struktúrákat. Egy finomabb felbontású részrácsból így tudunk létrehozni egy
36
DOI: 10.15477/SZE.MMTDI.2015.001
szülő csomópontot, mely egy magasabb szinten lévő, de durvább rács része. Ebben a csomópontban a rács mélysége eggyel csökken.
a. x111
x011
x012
x013
x112
x211 x212 x213 x121
x221 x222 x223 x231 x232 x233
x021
x022
x023
x024
x031
x032
x033
x034
x041
x042
x043
b.
x 011 x021 x031 x041
x111 x121
x112
x012
x013
x022 x032
x023 x033
x211 x212 x 221 x222 x231 x232 x024 x034
x042
x043
x044
x213 x223 x233
x044
c.
16. ábra a) Fuzzy szituációs térkép alrácsai, b) alaptérkép struktúra, c) mátrixos leírás
Bár az aggregációs műveleteknél általánosabb fuzzy műveletek is használhatóak lennének a szülő csomópontok fuzzy tagsági értékének a gyermekrácsból való kiszámításához, én mégis valamilyen aggregációval állítom elő ezeket az értékeket, mivel az aggregációs operátorok egyszerűen használhatóak és a feladat bemutatására alkalmasak. Mivel a fuzzy szituációs térképeket összetett adat kezelésre hoztam létre, ezért az olvashatóság és tömör formában való leírhatóság kedvéért kidolgoztam egy jelölésrendszert is.
37
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.2. Fuzzy szituációs térkép jelölésrendszere Ahogy az előző fejezetben is láthattuk az FSM-ek leírása beágyazott mátrix formában a legegyszerűbb, ahol minden egyes szint leírható a saját mátrixával, melyet beágyazhatunk a szülő mátrixba. Felbontási szint (z): egy-egy csomópontban kibontott alrácsok szintjét jelzi. Értéke a maximális felbontásig (alap FSM) növekedhet, és csomópontonként eltérő lehet. Ennek értékét módosítja a zoom funkció:
1 z max( zi ), z, zi , i 1,, n
(41)
ahol az n a csomópontok száma. Maximális felbontás, a beágyazhatóság mélysége (Rmax): a legnagyobb felbontáshoz tartozó z érték, az alap FSM legfinomabb felbontású rácspontjának a beágyazottsági mélysége (42):
Rmax max( zi ), i 1,, n
(42)
Rácspontok jelölése: az egyes rácspontok jelölése a következő alakú: xp
h, w
ahol
h, w
(43)
az aktuális rácsponthoz tartózó alrács méretét jelöli (magasság,
szélesség), mely értelmezhető a leíró mátrix sor- és oszlopszámaként is. Ha h w 1 , akkor az aktuális rácspontnak nincs alrácsa, vagyis egy szignatúra levél, mely egy fuzzy tagsági értéket tartalmaz. A p az x saját illetve szülő rácspontjainak pozíció vektora, beágyazottsági mélysége, illetve a leírómátrixban elfoglalt pozíciója. Ezzel a jelölés rendszerrel egyértelműen meghatározható az egyes rácspontoknak a struktúrában való elhelyezkedése, és így iteratívan leírható az FSM teljes struktúrája. Ahhoz, hogy jobban megértsük az általam bevezetett jelölés rendszert nézzünk egy példát. A 17. ábrán egy Rmax 3 beágyazottsági mélységű (maximális felbontású) fuzzy szituációs térkép struktúra látható.
38
DOI: 10.15477/SZE.MMTDI.2015.001
Rmax 3
17. ábra Rmax = 3 fuzzy szituációs térkép struktúra
Ezt a struktúrát a következő mátrixokkal írhatjuk le: (1,1) x111 z 1: (1,1) x121
(2,2) x112 (1,1) x122
(1,1) x211,112 z 2 : (1,1) x221,112
(1,1) x212,112 ( 2,2) x222,112
(1,1) x311,222 z 3 : (1,1) x321,222
(1,1) x312,222 (1,1) x322,222
(44)
A teljes fuzzy szituációs térképet leíró beágyazott mátrix:
FSM
Rmax 3
(1,1) x111 x (1,1) 121
(1,1) x211,112 (1,1) x221,112
(1,1) x312,222 (1,1) x322,222
(1,1) x212,112 (1,1) x311,222 (1,1) x321,222 (1,1) x122
(45)
3.1.3. Műveletek fuzzy szituációs térképen A fuzzy szituációs térképen végezhető műveletek létrehozásánál a fuzzy halmazműveleteket vettem alapul [64, 68, 73, 74, 105] és terjesztettem ki szituációs térképre. Ahhoz, hogy szituációs térképeken műveleteket, illetve összehasonlításokat tudjunk végrehajtani, a struktúrájukat, felbontásukat sok esetben át kell alakítani. Ez elsősorban a kétoperandusos műveleteknél fordulhat elő, melyek csak azonos szituációs térkép struktúrákon hajthatók végre. Ha a műveletben résztvevő FSM-ek nem azonos struktúrájúak, akkor első lépésként meg kell határozni a legnagyobb közös struktúrát.
39
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.3.1. Fuzzy szituációs térképek legnagyobb közös struktúrája, Fuzzy szituációs térkép struktúrájának, felbontásának módosítása (Zoom)
A fuzzy szituációs térkép előnye az adatok többdimenziós hierarchikus struktúrába való rendezése. Ez a struktúra határozza meg a fuzzy szituációs térkép alapú megfigyelések kezelhetőségét. A megfigyeléseknél előfordulhat, hogy az alapstruktúrából (alaptérképből) egyes csomópontokhoz tartozó elemek nem állnak rendelkezésre, így a megfigyelés struktúrája kis mértékben eltérhet az alapstruktúrához képest. Ezekben az esetekben, hogy az összehasonlítás, és így a következtetés mégis kivitelezhető legyen, valamilyen struktúra- más néven térképfelbontás-módosító operátorok használatára van szükség. A térképstruktúra módosításához a fuzzy alapműveleteknél bevezetett aggregációs operátorok használhatók oly módón, hogy az érintett alrácsot redukálja a szülő csomópontjára. Ekkor, ezen a ponton a térkép felbontása csökken, vagyis egy lépésben a mélysége eggyel csökken. Ezt a redukciót csak a teljes alrácsra lehet végrehajtani, adott rácspontban részleges felbontás-csökkentésre nincs lehetőség. A szülő csomóponthoz rendelt fuzzy tagsági értékek az alatta lévő gyermek alrács fuzzy tagsági értékeinek aggregálásával számítható ki. Ezt a redukciós folyamatot csak akkor lehet végrehajtani, ha az aggregálandó alrács minden csomópontja levél, tehát nem tartalmaz további alrácsokat. Amennyiben az alrács valamely csomópontja maga is szülője egy al-alrácsnak, akkor első lépésként ezt az al-alrácsot kell aggregációval redukálni a szülő csomópontjára. Az al-alrács redukciója után az így kialakult alrács redukciója is végrehajtható. Ezt a rekurzív folyamatot írja le a (46).
(1,1) x111 x0 x(1,1) 121
(1,1) (1,1) x211,112 x212,112 (1,1) ( 2,2) x111 (1,1) 112 x112 (1,1) x x x (1,1) 0 222,112 221,112 x121 (1,1) x122
(1,1) 0 x0 x112 x0 (46) (1,1) x122
A fuzzy szituációs térkép definíciójából következően az egyes finomabb felbontású alrácsok határozhatják meg az adott magasabb szinten lévő szülő csomópont értékét, így minden alrácshoz külön, egymástól független aggregációs operátort rendelhetünk. Természetesen az alkalmazott aggregációs operátor nagymértékben befolyásolja a redukció eredményét, ezért a kiválasztása, specifikálása döntő szerepű a következtetésben. A redukcióval, a felbontás csökkentésével információt is vesztünk, de a rész- vagy hiányos adatok ellenére működőképes összehasonlításokat és következtetéseket nyerünk.
40
DOI: 10.15477/SZE.MMTDI.2015.001
Ezeket az operátorokat is egyenként jelzem minden csomópontban, mivel elvileg minden egyes pontnál más és más operátort is használhatnánk. xp h , w
(47)
ahol ⨁ az aggregációs operátor. Például a (45) szituációs térkép leírása a következőképpen módosulhat:
FSM
Rmax 3
(1,1) x111 x (1,1) 121
(1,1) x211,112 1 (1,1) x221,112
(1,1) x212,112
x (1,1) 2 311,222 (1,1) x321,222 (1,1) x122
(1,1) x312,222 (1,1) x322,222 1 2 max
(48)
A redukciós műveletek mellett lehetőség van a kisebb felbontású térképrács kiterjesztésére egy nagyobb felbontású rácsra. Strukturálisan ez a művelet egyszerűen elvégezhető, viszont a rácspontokban lévő adatok kiterjesztése, például valamilyen interpolációval, további részletes vizsgálódást kívánna elsősorban a komplexitás növekedésének kérdésében. Mivel Kóczy és Hirota fuzzy interpolációs kutatásaiban [4143, 90] egyértelműen bizonyították, hogy a redukciós műveletek hoztak jobb gyakorlati eredményeket, ezért én a fuzzy szituációs térképek esetére nem végeztem a kiterjesztésre vonatkozó méréseket. Ezek a vizsgálatok a későbbiek folyamán elvégezhetők. 3.1.3.2. FSM komplemense
Egy fuzzy szituációs térkép komplemensén azt, az eredetivel strukturálisan azonos szituációs térképet értjük, melynek levél rácspontjain a kiindulási FSM azonos rácspontjainak az alkalmazott komplemens operátor által létrehozott komplemensei szerepelnek. Az alkalmazható komplemens operátorok a már ismert fuzzy operátorok (lásd: 2.1.2.1. fejezet) valamelyike lehet. A Zadeh-féle Standard komplemens kiterjesztett képlete:
FSM
A
x 1 (1,1) i, j
FSM A
x (1,1) i, j
(49)
Példaként tekintsük az adott FSMA szituációs térképet, és állítsuk elő a Zadeh-féle Standard komplemensét (50).
41
DOI: 10.15477/SZE.MMTDI.2015.001
0,8 FSM A 0,5
0, 7 0,3 0, 6 0, 4 0, 2 0,3 0,5 0, 4
0, 2 FSM A 0,5
0,3 0, 7 0,8 0, 4 0, 6 0, 7 0,5 0, 6
(50)
3.1.3.3. FSM-ek metszete
Két fuzzy szituációs térkép metszete a szituációs térképek levél rácspontjain egy bináris operációval állítható elő (51) a fuzzy halmaz metszeteknél alkalmazott operátorokkal (t-normák, 2.1.2.2. fejezet). A fuzzy szituációs térképek struktúrájának azonosnak kell lenni a metszet számíthatóságához. Amennyiben nem azonos a struktúrájuk, a legnagyobb közös struktúrát elő kell állítani, ahogy azt a 3.1.3.1. fejezetben leírtam. t : 0,1 0,1 0,1
(51)
A Zadeh-féle Standard metszet fuzzy szituációs térképekre kiterjesztett változata így a következőképpen határozható meg: FSM
A FSM B
x min 1,1 i, j
FSM A
x , 1,1 i, j
FSM B
x , 1,1 i, j
(52)
Példa az FSM metszetre: 0,8 FSM A 0,5
0, 7 0,3 0, 2 0, 6 0, 4 0,3 0,5 0, 4
0, 2 FSM B 0,5
0,3 0, 7 0,8 0, 4 0, 6 0, 7 0,5 0, 6
0, 2 FSM A FSM B 0,5
0,3 0,3 0, 2 0, 4 0, 4 0,3 0,5 0, 4
(53)
42
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.3.4. FSM-ek uniója
A fuzzy szituációs térképek unióképzés műveletét, hasonlóan a fuzzy halmaz unió képzéshez a t-normával való duál kapcsolata miatt t-konormának (vagy másként snormának) nevezzük, és szintén kétváltozós függvénnyel adjuk meg (54) (részletek a 2.1.2.3. fejezetben): s : 0,1 0,1 0,1
(54)
A műveletet itt is azonos struktúrán a levél rácspontokra lehet és kell elvégezni. Amennyiben a fuzzy szituációs térképek struktúrája nem azonos, első lépésként a legnagyobb közös struktúrát kell meghatározni. A (55) képlet írja le a Zadeh-féle Standard unió műveletét. FSM
A FSM B
x max 1,1 i, j
FSM A
x , 1,1 i, j
FSM B
x , 1,1 i, j
(55)
Az unió műveletre mutat példát az (56). 0,8 FSM A 0,5
0, 7 0,3 0, 6 0, 4 0, 2 0,3 0,5 0, 4
0, 2 FSM B 0,5
0,3 0, 7 0,8 0, 4 0, 6 0, 7 0,5 0, 6
0,8 FSM A FSM B 0,5
0, 7 0, 7 0,8 0, 6 0, 6 0, 7 0,5 0, 6
(56)
3.1.4. Kiterjesztett fuzzy szituációs térkép A fuzzy szituációs térkép bonyolult, akár több dimenziós sík vagy térbeli rendszerállapot leírására és kezelésére használható, így természetes, hogy komplex hierarchikus, több alrács-szinttel rendelkező szituációs térképek felírása lehet szükséges. Minél összetettebb, beágyazottabb egy szituációs térkép struktúrája, annál valószínűbb, hogy az egyes rácspontokhoz tartozó alrácsok hatását a kisebb felbontású aggregát részrácsokra, és ezen keresztül a teljes FSM-re finomítani kell.
43
DOI: 10.15477/SZE.MMTDI.2015.001
Az alrácsok hatásának befolyásolására vezettem be a rácspontokhoz rendelhető relevanciasúlyokat. A fuzzy szituációs térkép minden egyes rácspontjához rendelt relevanciasúly megadja, hogy egy rácspont mennyire releváns a felette lévő, szülőrácspont alrácsában, mely a fuzzy szignatúrás analógiát használva a szülő részfájának tekinthető. Az egyes rácspontok súlyai a [0,1] intervallumban értelmezettek, és nem szükséges, hogy egy alrácsban az utódok (alrács rácspontjai) súlyainak összege 1 legyen. A relevanciasúly a struktúrát nem befolyásolja. A súlyérték megadása nem kötelező, ha nincs megadva, akkor automatikusan 1-es értékű relevanciasúllyal számolunk. A 0 értékű relevanciasúly a rácspont, és a hozzátartozó alrácsok figyelmen kívül hagyását jelenti. Az előzőekben leírt jelölésrendszert kiegészítve minden rácsponthoz megadhatjuk ν relevanciasúlyt (57), ha értéke 1, akkor nem szükséges jelölni. xp , h , w
(57)
A relevanciasúlyok meghatározása sokkféleképpen történhet. További szakértői tudás vehető figyelembe vele a leírandó szakterületről, tanulás által dinamikusan módosítható, fix függvény kapcsolatból számítható, stb. Gyakorlati szempontból a relevanciasúlyok az aggregáció számítási műveleteit befolyásolják, hasonlóan a [106, 107]-ben leírt súlyozott aggregációs operátorokhoz. Példaként az (59) mutatja a (58)-ban megadott súlyozott fuzzy szituációs térkép 222 , 2 (2,2) rácspontjának aggregált értékét. A számítás menetére mutat példát a (60) és a x222,112
(61), ahol 222 0,5 311 0,8 és 321 0,9 , a többi relevanciasúly értéke 1.
111 (1,1) x111 FSM x121 (1,1) 121
211 (1,1) x211,112 1 (1,1) 221 x221,112
312 (1,1) x312,222 322 (1,1) x322,222 1 2 max
212 (1,1) x212,112
x 311 (1,1) 2 311,222 321 (1,1) x321,222 122 (1,1) x122
311 (1,1) 312 (1,1) 321 (1,1) 322 (1,1) 222 , 2 (2,2) x222,112 311 x311,222 2 312 x312,222 2 321 x321,222 2 322 x322,222
(58)
(59)
44
DOI: 10.15477/SZE.MMTDI.2015.001
0, 7 0,3 0,8 0,8 max 0,5 0, 6 0, 2 max FSM A 0,9 0,3 0,5 0, 4
0.5,max x222,112
0, 4 0,5
0,8 0, 6 0, 48 0, 4 0, 4 0,5 max 0,5 max 0,5 0, 48 0, 24 0,9 0,3 0, 27 0,5 0,5
(60)
(61)
3.1.5. A fejezethez kapcsolódó tézisek
1. tézis.
Javaslatot tettem a fuzzy szituációs térkép definíciójára, mint több dimenziós térbeli struktúrával rendelkező fuzzy szignatúrára. A fuzzy szituációs térkép hatékony leírásához komplex jelölésrendszert vezettem be. Javaslatot tettem a fuzzy szituációs térképeken alkalmazható fuzzy halmazműveletekre, továbbá kiterjesztettem a fuzzy szituációs térkép fogalmát relevanciasúlyok bevezetésével, s megadtam ezek használatának módját a javasolt halmazműveletekben. [B1‐21]
1.1. altézis. Definiáltam a Zadeh‐féle standard műveletek fuzzy szituációs térképekre használható változatait. Struktúra módosító eljárást dolgoztam ki a többoperandusú fuzzy szituációs térkép műveleteknél szükséges legnagyobb közös struktúra létrehozásához.
45
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.6. Következtetés
fuzzy
szituációs
térkép
alapú
rendszerekben
(általánosított Mamdani-módszer) Kóczy és Tamás kiterjesztette az 1975-ben publikált Mamdani-féle következtetést [68] a fuzzy szignatúra szabálybázisokra [108-110]. Ezt a módszert alapul véve dolgoztam ki a fuzzy szituációs térképekkel történő szabályépítés és következtetés eljárását. Az általánosított módszer és az eredeti Mamdanimódszer között jelentős eltérés csak az első lépésben van, ahol a megfigyelés (A*) és az egyes szabályok feltétel részei (Ai) közötti illeszkedési mérték meghatározása történik. A Mamdani-módszer részletes leírása a 2.1.2.6. fejezetben olvasható. 3.1.6.1. FSM alapú szabálybázis
A fuzzy szituációs térkép alapú szabálybázisok megadásánál mindenképpen szükség van az alapstruktúra rögzítésére, amely meghatározza a szabálybázisban szereplő összes fuzzy (halmaz vagy szingleton) szituációs térkép struktúráját. A struktúrán felül az alapstruktúrában rögzítésre kerülnek a térkép egyes rácspontjaihoz tartozó aggregációs operátorok és relevanciasúlyok. A fuzzy szituációs térkép alapú szabálybázisokat fuzzy szituációs térképekre épülő szabályok alkotják. Ezen szabályok a következőképpen általánosíthatók az eredeti, haakkor típusú fuzzy szabályok formájából:
Ri : Ha x Ai akkor y Bi ahol Ai jelöli az i. szabály antecedensét (feltételrészét), amely egy fuzzy szituációs térkép. Bi az i. szabály konzekvense (következménye), amely, mint a hagyományos fuzzy szabályoknál, továbbra is fuzzy halmaz. Az A* megfigyelés szintén fuzzy szituációs térkép, amelyet a megfigyelt értékekből, azok alaphalmazainak a [0,1] intervallumra történő normalizálása után lehet felépíteni. A szabály antecedensben és az aktuális megfigyelésben szereplő fuzzy szituációs térképek alapstruktúrája azonos, a tényleges struktúrák azonban eltérhetnek. Előfordulhat, hogy vagy a szabály feltétel részének szituációs térképéből, vagy magából a megfigyelésből hiányzik egy-egy levél-rácspont vagy részrács. Ez azt jelenti, hogy az 46
DOI: 10.15477/SZE.MMTDI.2015.001
információ az adott tárgyterületről nem eléggé részletes, és az ebből a tudásból felépített struktúra egyes részrácsokban további, részletekre vonatkozó hasznos adatot nem tartalmaz. 3.1.6.2. Illeszkedési mérték számítása
A fuzzy szituációs térképek illeszkedési mértékének számítása három lépésre bontható: a legnagyobb közös struktúra meghatározása, illeszkedési szituációs térkép felépítése, és az illeszkedési mérték számítása. 3.1.6.2.1. Legnagyobb közös struktúra meghatározása Két azonos alapstruktúrájú, de részben különböző aktuális struktúrájú fuzzy szituációs térképek összehasonlításához meg kell állapítani e két szituációs térkép legnagyobb közös struktúráját, majd a szituációs térképeket (egyiket vagy mindkettőt) erre a közös struktúrára kell redukálni. A két szituációs térkép közös struktúrája az a legnagyobb felbontású részrács, amelyre mindkét szituációs térképet redukálni lehet, valamely redukciós (aggregációs) funkció segítségével. A gyakorlatban ennek a közös struktúrának a megtalálásához szélességi keresés (BFS) használható [111-113]. A keresés első lépéseként felvesszük az FSM gyökér struktúráját a keresési sorba (Q). Majd, mint aktuálisan vizsgált rácspontot (RPakt) vesszük a keresési sor első elemét. Mindkét szituációs térképnél (FSM1, FSM2) megvizsgáljuk az adott rácsponthoz tartozó alrácsok méretét (h és w indexek). Abban az esetben, ha az alrácsok mérete (felbontása) megegyezik és az alrácsban lévő elemek indexelése is azonos (a hordozott információ azonos szituációs pontra vonatkozik), akkor az aktuális rácspont bekerül a közös struktúrába és az alrácsait a keresősor végére írjuk. Amennyiben h = 1 és w = 1, vagyis a rácspont egy levél, akkor a közös struktúrába bekerül, de a keresést ezen a ponton nem folytatjuk tovább. Ha az alrácsok mérete (felbontása) nem egyezik meg, akkor az alrácsai aggregálásával legalább az egyik rész-térkép rács struktúráját redukálni kell az adott rácspontban. Az algoritmus folyamatábrája a 18. ábrán látható.
47
DOI: 10.15477/SZE.MMTDI.2015.001
Amikor a Q keresési sorban az elemek elfogynak, megkapjuk a keresett legnagyobb közös struktúrát. Ekkor mind a megfigyelés, mind a szabály antecedensének szituációs térképét, a közös alapstruktúrában rögzített aggregációs operátorok és relevanciasúlyok felhasználásával az előállított legnagyobb közös struktúrára kell redukálni. A redukció után kapott megfigyelés és az i. szabály antecedens fuzzy szituációs térképeket jelöljük
A( r ) és Ai( r ) -el.
BFS
Q ← FSM z=1
RP akt ← Q első eleme
|FSM1(RP akt)| == |FSM2(RP akt)|
n
n
Q üres ?
i
END
i
h = 1 és w = 1 ?
i
StruktMax ← RP akt
n
Q ← FSM1(RPakt)
18. ábra A legnagyobb közös struktúra keresésének folyamata
A 19. ábra és a (62)-(64) egy példát mutatnak a legnagyobb közös struktúrára alakításra. A példában csak a struktúra a lényeges, a csomópontok aktuális értéke az illeszkedési szituációs térkép meghatározásakor kerülnek kiszámításra (lásd a következő fejezetben).
48
DOI: 10.15477/SZE.MMTDI.2015.001
w 1
2
3
4
w 5
6
7
8
1
2
3
4
w 5
6
7
8
1
1
1
1
2
2
2
3
3
3
4
4
h
3
4
5
6
7
8
4
h
h
5
5
5
6
6
6
7
7
7
8
8
8
A szabály antecedens szituációs térképe (Ai)
2
A megfigyelés szituációs térképe (A’)
A legnagyobb közös térkép struktúra (Mi)
19. ábra A legnagyobb közös térkép struktúra
@1 ( 2,2 ) x111 (1,1) (1,1) x211,111 x212,111 Ai (1,1) (1,1) x221,111 x222,111 (1,1) x121
x1122 @3 ( 2 ,2 ) x212,112 (1,1) (1,1) x311,212 x312,212 x (1,1) (1,1) (1,1) 211,112 x321,212 x322,212 (1,1) (1,1) x222,112 x221,112 (1,1) x122
x1111 (1,1) (1,1) x211,111 x212,111 (1,1) (1,1) x221,111 x222,111 A (1,1) (1,1) x211,121 x212,121 (1,1) (1,1) x221,121 x222,121 @ 4 (1,1) x121
@ ( 2,2 )
(62)
x112 (1,1) (1,1) x211,112 x212,112 (1,1) (1,1) x221,112 x222,112 (1,1) x122
(63)
(1,1) (1,1) (1,1) (1,1) x211,111 x211,112 x212,111 x212,112 (1,1) (1,1) (1,1) (1,1) M i x221,111 x222,111 x221,112 x222,112 (1,1) (1,1) x121 x122
(64)
@ ( 2 ,2 )
@ 2 ( 2,2 )
3.1.6.2.2. Illeszkedési szituációs térkép felépítése A közös struktúra meghatározása után a szabály antecedens és a megfigyelés szituációs térképének levél csomópontjai azonos rácspontokban helyezkednek el. Az ilyen, azonos rácspontokban elhelyezkedő leveleket összetartozó-leveleknek nevezzük. Az illeszkedési szituációs térkép (Mi) struktúrája megegyezik az i. szabály antecedens térképének és a megfigyelés szituációs térképének legnagyobb közös 49
DOI: 10.15477/SZE.MMTDI.2015.001
struktúrájával. Az illeszkedési szituációs térkép lp-vel jelölt levelén lévő értéket úgy kapjuk meg, hogy a két szituációs térkép szintén lp-vel jelölt, összetartozó-levelein tárolt értékek között meghatározzuk az illeszkedést (65).
lp levélre M i lp W A( r ) lp , Ai( r ) lp ,
(65)
ahol a W xp , yp függvény adja meg az összetartozó-leveleken tárolt értékek illeszkedési
mértékét.
Két
fuzzy
szituációs
térkép
illeszkedési
mértékének
meghatározásához, az egyszerűen alkalmazható Zadeh-féle művelethármast (komplemens (c), minimum (t-norma), maximum (s-norma)) használom (66).
W x p , y p s t xp , y p , t c x p , c y p
max min x , y , min 1 x ,1 y p
p
p
p
(66)
A (67)-(69) mutatnak a (64)-ben lévő közös struktúrára egy illeszkedési példát.
Ai( r )
A( r )
(1,1) (1,1) (1,1) (1,1) x211,111 x211,112 x212,111 x212,112 (1,1) (1,1) (1,1) (1,1) x221,111 x222,111 x221,112 x222,112 (1,1) (1,1) x121 x122
(67)
(1,1) (1,1) (1,1) (1,1) y211,111 y211,112 y212,111 y212,112 (1,1) (1,1) (1,1) (1,1) y221,111 y222,111 y221,112 y222,112 (1,1) (1,1) y121 y122
(68)
(1,1) (1,1) (1,1) (1,1) W x211,111 , y211,111 , y212,111 W x211,111 (1,1) (1,1) (1,1) (1,1) M i W x221,111 , y221,111 , y222,111 W x222,111 (1,1) (1,1) W x121 , y121
(1,1) (1,1) (1,1) (1,1) W x211,112 , y211,112 , y212,112 W x212,112 (1,1) (1,1) (1,1) (1,1) W x221,112 , y221,1 12 W x222,112 , y222,112 (1,1) (1,1) W x122 , y122
(69)
3.1.6.2.3. Illeszkedési mérték számítása az i. szabályra Az i. szabály illeszkedési mértékét úgy kapjuk meg, hogy az előző fejezetben (3.1.6.2.2) felépített illeszkedési szituációs térképet (Mi) egy fuzzy tagsági értékre redukáljuk, más szóval kiszámítjuk a fuzzy szituációs térkép gyökér tagsági értékét. A redukciót a szabály alapstruktúrájához rögzített, a struktúra egyes rácspontjaihoz tartozó aggregációs operátorokkal, és a rész-rácsok relevancia súlyainak használatával végezzük. Az i. szabály és a megfigyelés közötti illeszkedés mértékét a továbbiakban wi-vel jelölöm.
50
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.6.3. Következtetés
Miután meghatároztuk az illeszkedési mértéket w1 , , wr a szabálybázis összes szabálya Ri , i 1, , r és a megfigyelés A között, a végső következtetés az eredeti Mamdani-módszerhez hasonlóan számítjuk. Először előállítjuk mindegyik szabályhoz a hozzá és az adott megfigyeléshez tartozó következtetést Bi , oly módon, hogy az i. szabály következmény fuzzy halmazát csonkoljuk a szabályhoz kiszámított illeszkedési mértékkel (70). B
i
y min B y , wi yY
(70)
i
A teljes szabálybázishoz és az adott megfigyeléshez tartozó eredő következtetést
B
az egyes szabályokhoz tartozó következtetések Bi uniójaként állíthatjuk elő (71). r
B y max B y i 1
A
fuzzy
szituációs
térkép
alapú
i
következtetések
(71) eredményeképpen,
hagyományos Mamdani-módszerhez hasonlóan egy fuzzy halmazt
B
a
kapunk.
Amennyiben egy éles (crisp) következtetésre van szükségünk, akkor, mint a klasszikus fuzzy következtető rendszereknél, valamilyen defuzzifikációs módszert kell alkalmaznunk az aktuális éles érték kiszámításához.
3.1.7. A fejezethez kapcsolódó tézisek
2. tézis.
Kidolgoztam a Mamdani‐féle következtetés fuzzy szituációs térkép alapú szabálybázisokra kiterjesztett módszerét. Javaslatot tettem a fuzzy szituációs térkép alapú szabálybázisok felépítésére, és módszert adtam a fuzzy szituációs térképek illeszkedési mértékének kiszámítására. [B22‐29]
2.1. altézis. Kidolgoztam a legnagyobb közös struktúra meghatározásának algoritmusát különböző struktúrájú fuzzy szituációs térképek illeszkedési mértékének számításához.
51
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.8. Fuzzy szituációs térkép dimenzió növelése 3.1.8.1. Többdimenziós fuzzy szituációs térkép
Az előző fejezetekben a kétdimenziós fuzzy szituációs térképek tulajdonságait, rajtuk végezhető műveleteket mutattam be. Könnyen belátható, hogy ezek a tulajdonságok és műveletek egyszerűen kiterjeszthetők háromdimenziósra. Mind grafikusan, mind mátrixos formában kezelhető ez a szituációs térkép kiterjesztés, és a gyakorlat számára is jól értelmezhető, használható (pl. 3D-s robot feladatok leírása, rendezési feladatok, stb.). A dimenzió növelésnek elvi határa nincsen, de a háromnál nagyobb dimenziószámú fuzzy szituációs térképek gyakorlatban való felhasználhatósága csekélynek tűnik. A Kóczy által kidolgozott, klasszikus fuzzy következtető eljárásokra alkalmazott módszerrel [75, 76] számolható a fuzzy szituációs térkép alapú következtető eljárások bonyolultsága is. A dimenziónövelés exponenciálisan növeli a számítási kapacitás igényét. Természetesen a számítási bonyolultság a szabályok számával is exponenciálisan növekszik [75, 76]. Gyakorlat szempontjából a számítási kapacitás igényének ilyen mértékű növekedése nagyon lecsökkenti az n-dimenziós fuzzy szituációs térkép használhatóságát. Bizonyos feladatokban, így a mobil robotok kooperációs feladatában is, a kétdimenziós leírás nem mindig elegendő, illetve az információk hatékonyan nem sűríthetők be két (esetleg három) dimenzióba. Ezt a problémát legegyszerűbben úgy képzelhetjük el, hogy egy-egy rácspontban több független vagy egymástól függő, a következtetést befolyásoló adat van. Ilyenkor a dimenzió növelése (az adatok megfelelő szétválasztása) kézenfekvő megoldásnak tűnhet. Az általam vizsgált mobil robot kooperációs és kommunikációs feladatokban előforduló problémák információszükségletének reprezentálására a hagyományos n-dimenziós fuzzy szituációs térkép használata redundáns, pazarló és szükségtelen kapacitásigény növekedéssel járna. Ezért egy új módszert dolgoztam ki, mely részben alkalmas a dimenziónövelés elkerülésére és a réteg-rácsokban lévő adatok közti összefüggések leírására, miközben áthidalja a számítási problémákat. Ez a többrétegű fuzzy szituációs térkép. 3.1.8.2. Többrétegű fuzzy szituációs térkép (Multilayer – FSM)
A többrétegű fuzzy szituációs térképet (MFSM), mint „egymásra helyezett” kétdimenziós fuzzy szituációs térképeket lehet elképzelni (20. ábra). Az egyes rétegek a 52
DOI: 10.15477/SZE.MMTDI.2015.001
kétdimenziós fuzzy szituációs térképnél leírt műveletekkel kezelhetők, így akár párhuzamos feldolgozás is lehetségessé válik.
20. ábra Többrétegű fuzzy szituációs térkép
Többrétegű FSM esetén mindig van egy mester réteg, mely a fő szituációs térképet tartalmazza és a többi réteget hordozza, mint plusz információkat tartalmazó vagy módosító szituációs térkép alrétegeket, melyeket réteg szituációs térképeknek neveztem el. A többrétegű FSM struktúráját mindig a mester szituációs térkép határozza meg. Ez azt jelenti, hogy a mester és a réteg szituációs térképek alapstruktúrájának meg kell egyeznie, vagyis a réteg szituációs térképekből, redukciók és zoom funkciók segítségével mindig előállítható a mester szituációs térkép struktúrája. A struktúra módosítás az 3.1.3.1. fejezetben és a következtetést leíró 3.1.6. fejezetben tárgyalt módszerekkel azonos módon történik itt is. A rétegek közötti kapcsolat, egymásra gyakorolt hatás csak az azonos indexű rácspontokban értelmezett (72). Közvetett hatásuk természetesen lehet más rácspontokra is. A különböző rétegekben lévő, azonos indexű rácspontok háromféle kapcsolatban állhatnak egymással:
irányított függőség,
kölcsönös függőség,
(részleges) függetlenség.
Irányított függőségről beszélünk, ha az egyik réteg valamely rácspontja hatással van egy másik réteg rácspontjára, de visszafele nincs hatása a második rácspontnak az elsőre. Például egy navigációs feladatnál az akadályok adatait tartalmazó réteg szituációs 53
DOI: 10.15477/SZE.MMTDI.2015.001
térkép bizonyos rácspontjai hatnak az útvonaltervezés rétegére, az viszont nem hat az akadály rétegre. Kölcsönös függőség esetén a rétegek egyes rácspontjai kölcsönösen hatnak egymásra. Ebben az esetben jóval bonyolultabb összefüggéseket kell leírni, mint a másik két esetben. Sokszor további, irányítottan összefüggő rétegekre való bontás vezet a gyakorlatban is alkalmazható megoldáshoz. Az előző példánál maradva, ha többféle optimalizálási réteget használunk az útvonaltervezésnél, pl. egyet időre és egyet fogyasztásra, akkor ezek a rétegek kölcsönös függőségben álló rácspontokat tartalmazhatnak, melyek kezelése komplex számításokat igényel. Független, illetve részlegesen független rétegekről beszélünk, ha nem hatnak egymásra a vizsgált réteg szituációs térképek rácspontjai, vagy csak néhány pontban állnak kapcsolatban. 3.1.8.2.1. A rácspontok rétegek közti kapcsolása A rétegek közti szituációs térkép struktúra egyeztetés után a réteg szituációs térképek levél csomópontjai azonos rácspontokban helyezkednek el. A rétegek közti rácspont kapcsolatok, hatások, nagyon sokfélék lehetnek a feladattól függően. Egész egyszerű súlyozási, skálázási kapcsolatokon keresztül a bonyolult függvény kapcsolatokig minden elképzelhető. Fuzzy szituációs térképeknél a súlyozási és más fuzzy operátorokra épülő módszereket alkalmazok. Az MA többrétegű fuzzy szituációs térkép lp-vel jelölt levelén lévő érték az Ai és Aj réteg szituációs térképek szintén lp-vel jelölt, összetartozó-levelein tárolt értékek között végrehajtott Con (Connection) függvény eredményeként kapható meg (72). Ezek a levelek lehetnek redukció eredményei is.
lp levélre MA lp Con Ai lp , A j lp , i 1, , n; j 1, , n; i j , (72)
ahol n a rétegek száma és a Con xp , yp függvény adja meg az összetartozóleveleken tárolt módosított értékeket. 3.1.8.2.2. Többrétegű fuzzy szituációs térkép előnyei Az n-rétegű fuzzy szituációs térképek sok gyakorlati előnnyel rendelkeznek az n-dimenziós nem rétegzett szituációs térképekhez képest. 54
DOI: 10.15477/SZE.MMTDI.2015.001
Az n-rétegű fuzzy szituációs térkép feldolgozható, mint n darab kétdimenziós szituációs térkép, így a számítási igényük drasztikusan csökkenthető. Ráadásul több processzoros vagy több magos rendszerben rétegenként jól párhuzamosítható is ez a művelet. A réteges felépítés tervezhető modulárisra is, mely azt jelenti, hogy az egyes rétegek kivehetők, cserélhetők a szituációs térképben. Ezzel egy, a fuzzy szabálybázishoz hasonló rugalmasságú leírót hozhatunk létre. Az egyes rétegek (szabályok) kivétele, módosítása nem „omlasztja” össze a teljes rendszert, vagyis bizonyos rétegek hiánya nélkül is működőképes maradhat a szituációs térkép. A többrétegű fuzzy szituációs térkép modularitási tulajdonsága nagyon rugalmassá teszi a felhasználhatóságát, és lehetőséget biztosít a folyamatos fejlesztéshez, még autonóm és adaptív esetben is. Tanuló rendszerek alapja lehet. Ezt biztosítja a rétegek közti függőség-függetlenség meghatározása is, egyes rétegek csak bizonyos esetekben hatnak más rétegek működésére.
3.1.9. A fejezethez kapcsolódó tézisek
3. tézis.
A mobil robotok kooperációjával és kommunikációjával kapcsolatos gyakorlati feladatok tanulmányozása közben felismertem, hogy számos, a gyakorlatban előforduló probléma információszükségletének reprezentálására az n‐dimenziós fuzzy szituációs térkép használata redundáns, pazarló, és szükségtelen megoldás lenne. Kimutattam, hogy a fuzzy szituációs térkép használatával ilyen esetekben látszólag megvalósuló exponenciális bonyolultságnövekedés elkerülhető az általam javasolt és definiált „többrétegű fuzzy szituációs térkép” alkalmazásával, és módszert adtam a többrétegű fuzzy szituációs térképek réteg‐rácsai közötti függőségi viszonyok és kapcsolatok leírására. [B13, B30‐33]
55
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.10. Fuzzy szituációs térkép csomópontjainak belső kapcsolatrendszere Eddigiekben a fuzzy szituációs térképet mint multidimenzionális kiterjesztett fuzzy szignatúrát tekintettük. A fuzzy szituációs térkép további előnyös tulajdonsága, hogy nem csak a külső információkat képes jól feldolgozható hierarchikus strukturált formába rendezni, hanem az egyes csomópontok egymásra gyakorolt hatásait is képes figyelembe venni. Ez azt jelenti, hogy az egyes csomópontok a szomszédos csomópontokkal kapcsolatban állnak, és pillanatnyi értékük, változásuk hatással lehet szomszédjaikra, megváltoztathatják azok értékeit. Ezek a hatások lehetnek irányítottak, illetve kölcsönösek is, és a teljes szituációs térképre vagy annak csak egy-egy alrácsára hathatnak. A fuzzy szituációs térképek belső összefüggéseinek leírást a fuzzy gráfok elméleti alapjaira építettem [114-123], figyelembe véve, hogy ezek a kölcsönös függőségek rendkívül összetettek lehetnek, így a feldolgozásuk is nagy számítási kapacitást igényelne. Ennek kiküszöbölésére új módszert dolgoztam ki, mely a problémának megfelelő, könnyen feldolgozható fuzzy vektorokat, fuzzy szignatúrákat hoz létre a fuzzy szituációs térkép aktuális alrácsából. 3.1.10.1. Fuzzy gráfok
A fuzzy gráfok alapjait Rosenfeld fektette le 1975-ben [114]. A hagyományos gráfelméletből ismert struktúrák, a gráfelméleti fogalmak közül sok a későbbiek során került átvételre, illetve átdolgozásra a fuzzy gráfok területére [116-123]. Kóczy a [124]ben mutatta be a fuzzy csúcs gráfok elméleti hátterét és alkalmazási lehetőségeit. Ezt a gráf struktúrát, illetve a fuzzy csúcs és él gráfok kombinációját alkalmazom bizonyos megkötésekkel a fuzzy szituációs térképek belső kapcsolatrendszerének leírására. Alapvetően két nagy csoportja van a fuzzy gráfoknak: a fuzzy él gráfok és a fuzzy csúcs gráfok. Fuzzy él gráfról beszélünk, ha egy adott G komplett gráfon felveszünk egy F fuzzy gráfot, úgy, hogy minden éléhez egy fuzzy tagsági érték kapcsolódik a [0, 1] intervallumban. A μe megadja az e él F gráfba való tartozósának (jelenlétének) tagsági értékét. Tehát ha a μ = 0, akkor nincs az él F-ben, ha μ = 1, akkor pedig „élesen” (crisp) szerepel az F gráfban, az intervallum összes többi értéke valós fuzzy élt jelent. A 21. ábra mutat egy példát a fuzzy él gráfokra (F1). 56
DOI: 10.15477/SZE.MMTDI.2015.001
1.0 0.3 F1
0.2
1.0 ≡
0.5
0.3
0.0
0.2
0.5
0.0
F1'
21. ábra Fuzzy él gráf
Fuzzy csúcs gráfok esetén adott egy tetszőleges (crisp) G referencia gráf. Az F fuzzy gráfban a G minden egyes csúcsához (vertex) egy fuzzy tagsági érték van rendelve, mely a csúcs gráfhoz való tartozásának erősségét jelzi. Minden él, mely két csúcsot köt össze (V1, V2), kap egy számított tagsági értéket a V1 @ V2 képlet alapján, ahol a @ egy összekötő operátort jelöl, az esetek többségében ez valamilyen t-norma. Egy fuzzy csúcs gráfot (F2) mutat a 22. ábra. F2
0.3
0.3 @ 0.5
0.5
0.4 22. ábra Fuzzy csúcs gráf
A fuzzy él és csúcs gráfok kombinációja is elképzelhető [114], ahol mind az élekhez, mind a csúcsokhoz rendelhetők fuzzy tagsági értékek. A gyakorlat számára ez már meglehetősen komplikált modell, ritkán használják. 3.1.10.2. Fuzzy szituációs térkép csomópontok kapcsolatainak leírása fuzzy gráfokkal
A fuzzy szituációs térkép csomópontok belső kapcsolatainak a leírásához a fuzzy él és csúcs gráfok módosított változatát dolgoztam ki. Vegyük az A egyszerű kétdimenziós fuzzy szituációs térképet, mely akár lehet egy redukált térkép is. Az A csomópontjaiban fuzzy tagsági értékek vannak, a csomópontjai levél-rácspontok (14. ábra), melyeknél egyszerűsített xij rácspont tagsági érték jelölést használok, ahol i 1,, h; j 1,, w a rácspont indexe. Tekintsük az xij rácspont kapcsolati lehetőségeit a szomszédos rácspontokkal. A 23.a. ábrán látható, hogy a ponthoz kapcsolható lehetséges négy élhez külön-külön tagsági érték rendelhető hozzá. A iji 1, j tagsági érték az xij és a xi 1, j rácspontok közti irányított él 57
DOI: 10.15477/SZE.MMTDI.2015.001
tagsági értéket jelenti, ahol i 2,, h; j 1,, w . A másik három él tagsági érték is hasonlóan adható meg. Két szomszédos rácspont között az élek tagsági értéke a következőképpen értelmezhető (23.b. ábra):
ha iji , j 1 0 és iij, j 1 0 , akkor az xij és xi , j 1 rácspontok között nincs él,
ha iji , j 1 0 és iij, j 1 0 , akkor az xij és xi , j 1 rácspontok között irányított él vagy út van, mely csak az xij xi , j 1 irányba járható ( xij hat xi , j 1 -re, de xi , j 1 nem hat xij -re),
ha iji , j 1 0 , iij, j 1 0 és iji , j 1 iij, j 1 , akkor az xij és xi , j 1 rácspontok között két irányított él vagy út van xij xi , j 1 vagy xi , j 1 xij , mindig a bejárási iránytól függ, hogy melyik él tagsági értéket használom,
ha iji , j 1 0 , iij, j 1 0 és iji , j 1 iij, j 1 , akkor az xij és xi , j 1 rácspontok között a kapcsolat kölcsönös, egy él tagsági értékkel leírható.
A 24. ábra egy h x w méretű fuzzy szituációs térkép belső kapcsolati gráfját mutatja. Már nem túl nagy méretű szituációs térkép esetén is meglehetősen bonyolult kapcsolati gráfok szükségesek, melyek feldolgozása – különösen kölcsönös kapcsolatok esetén – nagy számítási teljesítményt igényel.
iji 1, j
iji , j 1
iji , j 1 iji 1, j a.
ii,j1,1j
iji 1, j
iji , j 1
iji , j 1 iij, j 1
ii,, jj12
ii,j1,1j
iji 1, j b.
23. ábra a) FSM rácspont él tagsági értékek, b) él tagsági értékek két rácspont között
Mivel a célom komplex adatkapcsolatok hatékony leírása, ezért a következő megkötésekkel, illetve struktúraformázási lépésekkel egyszerűsítem a feldolgozást:
egyszerű gráfokat használok, se hurkok, se párhuzamos élek nincsenek,
minden egyes vizsgálati lépésben kijelölök egy gyökér-pontot, a gráf leírását ehhez a ponthoz, mint referenciához viszonyítva végzem, 58
DOI: 10.15477/SZE.MMTDI.2015.001
az élek tagsági értékének irányítottsága megőrződik, de csak a referenciapontból induló utakat veszem figyelembe,
ij 0 tagsági értékű éleket törlöm a gráfból.
1112
1211
1213
1121
1222
11 21
12 22
2122
2221
11,ww1 12ww
2223
2131
hh11,1 hh12
h , w 1 hw
h 1, w hw
24. ábra Fuzzy szituációs térkép kapcsolati gráfja
Az előbbiekben leírtak alapján tekintsük xij rácspontot a vizsgálat gyökérpontjának. Tegyük fel, hogy bizonyos él tagsági értékekről tudjuk, hogy 0 értékűek, ekkor 25. ábrában látható xij központú gráfot kapjuk. Minden egyes rácspontra felvehetünk egy ilyen, illetve ehhez hasonló gráfot, mely tulajdonképpen az eredeti fuzzy szituációs térkép rész-térképe lesz. Így minden pont leírható a csúcs tagsági értékével xij , és a belőle kiinduló 4 darab él tagsági értékből képzett eij vektorral (73).
Vij xij , eij (73) iji 1, j i , j 1 eij iji 1, j , i 1, , h; j 1, w ij i , j 1 ij
59
DOI: 10.15477/SZE.MMTDI.2015.001
ii1,1, jj 1
ii1,1, jj 1
iji 1, j
iji 1, j
25. ábra Az xij gyökér-rácspontra felvett kapcsolati gráf
Az így létrehozott kapcsolati gráfból már egyértelműen meghatározható egy leíró struktúra, egész pontosan egy kiterjesztett fuzzy szignatúra. Az 25. ábrát tekintve a következő fuzzy szignatúrával tudjuk leírni az xij gyökér-pontot:
iji 1, j
xi 1, j 1
ii1,1, jj 1
xi 1, j 1
xi 1, j
xij
iji 1, j
ii1,1, jj 1
xi 1, j
26. ábra Kiterjesztett fuzzy szignatúra az xij-re
Ez a szignatúra egy adott struktúrában egyértelműen leírja a környező pontok hatását a vizsgált xij pontra. Az él tagsági értékeknek ij döntő szerepe van a fuzzy szituációs térképek belső struktúráinak kialakításában és a csomóponti hatások közvetítésében.
60
DOI: 10.15477/SZE.MMTDI.2015.001
3.1.11. A fejezethez kapcsolódó tézisek
4. tézis.
A fuzzy szituációs térkép rácspontjai között lévő belső kapcsolatrendszer leírására fuzzy irányított gráf alapú eljárást dolgoztam ki. [B18‐21]
4.1. altézis. A komplex összefüggések egyszerűsítéséhez és a feldolgozhatóság biztosításához javaslatot tettem a fuzzy szituációs térkép rácspontjaira felvehető gráfok fuzzy szignatúrákká alakításának eljárására.
61
DOI: 10.15477/SZE.MMTDI.2015.001
4. Új
módszerek
intelligens
kommunikáció
és
kooperáció
megvalósításához 4.1. Robotok kooperatív feladatvégzése A modern robottechnikával szemben támasztott elvárások egyre inkább a gépek önálló, emberi beavatkozást nélkülöző működését követelik meg. Ezt a követelményt a gépeknek úgy kell teljesíteniük, hogy közben fizikailag egyre közelebb kerülnek az emberhez. A fenti elvárások teljesítéséhez elkerülhetetlen a gépek közötti vagy emberrel való együttműködés képessége. A hatékony kooperációnak egyik legfőbb pillére a résztvevők közti kommunikáció. Ennek minősége, egyértelműsége meghatározó a kooperáció végrehajtása tekintetében. A kutatásaimban arra a kérdésre kerestem a választ, hogy megoldható-e a résztvevők közti explicit kommunikáció nélkül egy olyan feladat, melyhez robotok együttműködése szükséges.
4.1.1. Az együttműködés feltételei A kooperációs feladatokat megoldó algoritmusok területén a számítási intelligencia módszerek alkalmazása új lehetőségeket kínál fel, mivel az együttműködés mindig igényel valamilyen szintű intelligenciát. Az együttműködésnek három alappillére van: 1. kooperációra való képesség, 2. kooperációra való hajlandóság, 3. hatékony kommunikáció a résztvevők között. Az első két pillér jól körülírható irányítási feladatokat jelent. Bár a kommunikáció sem számít extrém feladatnak napjainkban, mégis az információ sérülékenysége, a torzulások, zavarok miatt vagy egyszerűen a részben meghatározott szimbólumok miatt keletkező információhiány félreviheti, sőt blokkolhatja a kooperációs képességet. Ezért az információszegény kommunikáció problémáját én egy fontos és érdekes kutatási területnek tartom és a következőkben ezzel foglalkozom.
62
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.2. A kommunikáció mint az együttműködés alappillére A dolgozatom bevezető fejezetében már tárgyaltam a különböző kommunikációs megközelítéseket, köztük megemlítettem a fuzzy kommunikációt is, ahol a bizonytalanságok kezelése fuzzy módszerekkel végzik. Fuzzy kommunikáció esetén az információ átadás alapvető eleme a kódkönyv, amit minden résztvevő birtokol. Ez a kódkönyv úgy is tekinthető, mint egy megosztott tudásbázis, amely az értelmezhető nyelvi üzeneteket tartalmazza. A két résztvevőt nevezzük adónak és vevőnek, akik rendelkeznek legalább egy olyan kódkönyvvel, amelyben az aktuális információcseréhez szükséges kifejezések szerepelnek, és ezek alapján képesek az üzenet hatékony kódolására és dekódolására. Az előbbiek alapján a fuzzy kommunikáció két fontos alapeleme [22]:
A fuzzy kódoló: kódolja a bemeneti információkat.
A fuzzy dekódoló: dekódolja az átküldött üzenetet.
A fuzzy információk kódolását és dekódolását, a fuzzy következtető rendszerekből már jól ismert módon illeszkedési mérték meghatározásnak és defuzzifikálásnak is szokták nevezni. A fuzzy kommunikációnak sokféle, akár ellentmondó, értelmezése is létezik. Flaherty gazdasági környezetet vizsgálva azt a megállapítást tette, hogy a kommunikációnak mindig pontos és hatékony információ hordozónak kell lennie [125]. Ellenkező esetben az információ hiányt hamis vagy legalább is torz, feltételezett információkkal töltik ki. Egy példa erre az esetre: A cég új igazgatója a gazdasági vezetőt zárt ajtók mögött tartott megbeszélésre hívja. Eddig ezek a megbeszélések nyíltak voltak. Aztán több ilyen tárgyalás történik és még előjegyzésben is van néhány. Minden tárgyalás után a gazdasági vezető újabb és újabb megvonásokat jelent be a dolgozóknak. Lassan a többi dolgozó elkezd beszélgetni a már ismert és a feltételezett további megvonásokról. A gazdasági vezetőt egy munkatársa megkérdezi, hogy mi a gond, mi folyik itt? A gazdasági vezető a főnökségre hivatkozva nem ad ki információt. A munkatárs pánikszerűen új munkát kezd keresni, ezzel elindul a többiek között is a bizonytalanság lavinája.
63
DOI: 10.15477/SZE.MMTDI.2015.001
A fenti jó példa a valódi fontos információk hiánya esetén fellépő bizonytalanságra. Az új vezető viselkedése nem értelmezhető a dolgozók eredeti „kódkönyve” alapján, és így a [22] szerint a fuzzy kommunikáció szabálybázisa nem érvényes az új szituációra. A dolgozók a saját fiktív információikkal helyettesítik a hiányt, ami félreértésekhez, végül katasztrofális döntésékhez vezethetnek. Japánban, Yokohamában működött 1989 és 1995 között a „Laboratory for International Fuzzy Engineering Research (LIFE)” kutatási központ. A LIFE, mint az alkalmazott fuzzy kutatások spirituális központja, Flahertyhez [125] képest egy egészen más, pozitív megközelítésben világít rá a fuzzy elemek használatára a tömör és effektív emberi kommunikációban. Egy eset példaként (a LIFE prezentáció [126] és Kóczy alapján [61]): Tanaka igazgató úr hétfőn új titkárnőt kap, Sato kisasszonyt. Mikor Tanaka úr megérkezik az ebédből, hívja Sato kisasszonyt és a következő beszélgetés zajlik köztük: ̶
Legyen szíves hozzon nekem egy teát. ̶
Hideget vagy meleget parancsol? ̶
Meleget, legyen szíves. ̶
Fekete vagy zöld tea legyen? ̶
Inkább fekete. ̶
Kér bele cukrot? ̶
Köszönöm, nem. ̶
És tejet? ̶
Azt sem. Köszönöm.
Sato kisasszony ezek alapján elkészíti a teát. Kedden ebéd után az igazgató újra hívja a titkárnőjét: ̶
Kérhetek egy csésze teát?
̶
Hogyne, fekete teát megint? ̶
Igen. ̶
Cukor és tej nélkül? ̶
Igen, köszönöm
Most már sokkal kevesebb kérdés vezetett a titkárnő azonos akciójához. Szerda, ebéd után: 64
DOI: 10.15477/SZE.MMTDI.2015.001
Kérhetnék… ̶ ̶
A szokásos teáját? ̶
Igen.
Csütörtökön megérkezik Tanaka úr az ebédből, Sato kisasszony kérdezi: Készíthetem a szokásos teáját? ̶ ̶
Igen, köszönöm.
A hétfői beszélgetés egy kérésből, majd néhány kérdésből és informatív válaszból áll (összesen 9 mondat). Csütörtökön már nem kell kérés és csupán két mondat elég ugyanahhoz az eredményhez, amihez hétfőn még 9 mondat kellett. Ebben az esetben a kódkönyv tanulással épül fel, ami végül egy nagyon hatékony, tömör fuzzy kommunikációhoz vezet. Ebben a példában a kódkönyv formálisan a következőképpen írható le [61]: „Ha Tanaka úr ebéd után megérkezik (T), akkor ő forró (H) fekete teát (B) szeretne inni tej és cukor nélkül M , S .” Logikai jelekkel:
T B & T H & T M & T S . Ameddig a kódkönyv helyes marad (Tanaka úr nem változtat az ivási szokásain), addig ez az egyszerű formális modell használható lesz. Ez természetesen csak egy a sok kódkönyv közül amit a Sato kisasszony „tárol”, így más kontextusban egy másik kódkönyvet használhat, amely ott optimálisabb kommunikációt eredményez. Léteznek olyan általános háttér információk is melyek a kódkönyvet általánosíthatják, illetve a tanulási folyamatot gyorsíthatják és egyszerűsíthetik. A teás esetnél maradva például: „Ebéd után az emberek gyakran isznak kávét, teát, vizet vagy valamilyen üdítőt.”, „Létezik fekete és zöld tea”, „A teát isszák hidegen és melegen is”, „A kávét, teát néha cukor nélkül isszák”, stb. A természetes nyelvünkben használt nem egzakt határozószók, jelentés módosítók, mint például a gyakran, néha kifejezések gépi leírására javasolta Zadeh a Precisiated Natural Language használatát[127], mint olyan eszközt mely képes modellezni a komplex imprecíz problémákat, mind a mindennapi élet mind pedig az alkalmazott tudományok területén. 65
DOI: 10.15477/SZE.MMTDI.2015.001
Az előző beszélgetések egy lehetséges folytatása: Egy nap Sato kisasszony felteszi a szokásos ebéd utáni kérdését: Készíthetem a szokásos teáját? ̶ ̶
Nem, ma jobban szeretnék egy kávét. ̶
Presszót vagy hosszú kávét kíván? ̶
Presszót ̶
Cukorral? ̶
Köszönöm, nem. ̶
Tejet kér bele? ̶
Igen azt kérek. Köszönöm.
Ebbe az estben a kódkönyv a következő kiegészítéseket kapja: „Ha Tanaka úr megérkezik ebéd után (T), akkor általában forró fekete teát (B) iszik tej és cukor nélkül M , S , néha viszont egy presszó kávét (E) egy kis tejjel (M) cukor nélkül S .” Formálisan leírva:
(T[usually] B &T[usually] H &T[usually] M &T[usually] S , T[sometimes] C &T[sometimes] E &T[sometimes] M &T[sometimes] S ) vagy még tömörebben egy strukturált formában:
(T[usually] B&T[sometimes] E; B H &M &S; C E&M &S ) Ezek a kódkönyv-elemek jól leírhatók PNL-el, fuzzy logika illetve fuzzy halmazok használatával. A fenti példa folyamata és folytatása, változatlan kontextus mellett, a meglévő elemek törlése nélkül további elemekkel bővíti a kódkönyvet. Általában kijelenthető, hogy az ehhez hasonló, emberi interakcióban a kódkönyvek soha nem tekinthetők teljesnek és véglegesnek [61]. Mindkét példában kettő vagy több ember közti kommunikáció, vagyis emberember kommunikáció volt, ahol az információk hiányosak illetve nem teljesek. A meglévő csekély információ alapján kell az eredeti tartalmat létrehozni, amely a második esetben, a kódkönyv alapján sikeresen rekonstruálható. Hasonló kommunikációs csatornát lehet nyitni ember-gép és akár gép-gép kapcsolatban is, ahol a résztvevők csak az információ „vázát” vagy a „megközelítő vázát” 66
DOI: 10.15477/SZE.MMTDI.2015.001
küldik át. A kérdés, hogy ilyen fajta kontextufüggő rekonstruktív fuzzy kommunikáció alkalmazható-e a mérnöki tudományokban és a gyakorlatban. Kutatásaim fő irányát ennek a kérdésnek a megválaszolására, és a robotkooperációs alkalmazások területén való használatának kidolgozására és igazolására szántam.
4.1.3. Kontextusfüggő
rekonstruktív
kommunikációra
épülő
robotkooperáció A gyakorlatban az együttműködési feladatok nagyon nagy csoportját alkotják a tárgyak kezelésének, mozgatásának problémái. Nagy súlyú, illetve különleges alakú vagy méretű tárgyak mozgatása, a folyamat algoritmizálása nehéz feladat. Ennek egy klasszikus példája az úgynevezett „zongora hordozók problémája” [128], ahol a cél a zongora (nehéz, nagy, különleges alakú tárgy) optimális úton való eljutatása egyik pontból a másikba úgy, hogy közben se a zongora se más a környezetben ne rongálódjon meg. A feladat elvégzése precíz legalább kétszintű hierarchikus irányítást igényel, ahol a felső szint a tárgy optimális mozgatásának, célba jutatásának kezelését, míg az alsó szint az akadálykerülést, mozgásokat, a tárggyal való kontaktust irányítja. Ha mi, emberek ütközünk ilyen feladatokba, szinte automatikusan a közös, együttműködő megoldásokat keressük, segítséget kérünk. A robottechnika is ebbe az irányba fejlődik és mind bonyolultabb kooperációs feladatok intelligens megoldását tűzi ki célul. A robotkooperációs algoritmusok fejlesztésére és kipróbálására a „zongora hordozók problémája” alapján, de annál egyszerűbben modellezhető és kivitelezhető, a tudományos és a gyakorlati körök által is széles körben elfogadott módszert szokás alkalmazni. Ez a módszer, valamilyen tárgynak egyedi vagy kooperatív módon történő célirányos mozgatása, illetve rendezése. Széles szakirodalma van az úgynevezett „doboz mozgatási” (tolás, forgatás) problémának, amivel jól modellezhetők a tárgyak kezelésének nagy témakörei [2, 129-136]. Az algoritmusok kipróbálására én is egy hasonló tárgymozgatási problémára épülő robotkooperációs feladatot dolgoztam ki. Felépítését tekintve a LIFE laboratóriumban megalkotott rendszert vettem alapul, de teljesen más megközelítésben oldottam meg a feladatot. A LIFE laboratóriumban Terano professzor vezetésével, 1989-ben elkezdődött egy robotkooperációs kísérletsorozat [126]. Egy szobában van néhány azonos méretű 67
DOI: 10.15477/SZE.MMTDI.2015.001
téglalap alakú asztal. Ezek az asztalok különböző formákba rendezhetők, pl. T-alak, Ualak, stb. Az aktuálisan kívánt formát egy robotcsoport rakja ki, egy asztalt legalább két robot mozgat. Az aktuális feladatot csak egy robot ismeri, a többi robot megpróbálja kitalálni a cél alakzatot. A robotok explicit módon nem kommunikálhatnak egymással. Ezekkel a feltételekkel, ha a robotok rendelkeznek a többiek szándékának „megsejtésére” alkalmas algoritmusokkal, elméletben képesek a fenti probléma megoldására. Terano csoportja értékes részmegoldásokig jutott. 4.1.3.1. Egy robotkooperációs feladat
A vizsgált probléma egy raktárban lévő m darab tárgy (doboz) elrendezése egy adott pozícióba és alakzatba. A rendezést n robotból álló csoport végzi. A dobozok méretüknél és tömegüknél fogva csak két robot által mozgathatók (tolás, forgatás). A feladat sémája a 27. ábrán látható. A dobozokból kialakítható struktúrák a résztvevők számára adottak, de a tényleges feladatot csak a „Mester” (R0) robottal közöljük, a többi robot induláskor erről nem kap információt, és sem egymással sem az R0-al közvetlenül nem tudnak kommunikálni. Minden robot azonos kódkönyvvel rendelkezik, mely leírja az aktuálisan lehetséges dobozkonfigurációkat. A robotok képesek egymás, és az R0 viselkedését megfigyelni és feldolgozni. A robotokra olyan intelligens kooperációs algoritmusokat dolgoztam ki, melyekkel képesek a „szándék megsejtésére” (intention guessing), és a kódkönyvre alapuló kontextusfüggő rekonstruktív, más néven fuzzy kommunikációt alkalmazva megbirkózni a fenti problémával. A következőkben ismertetem a kísérleti rendszer elvi és gyakorlati felépítését, illetve bemutatom a kidolgozott és alkalmazott algoritmusokat. Tekintsünk egy raktárt (robot munkatér vagy aréna), ahol Ri : R0 , R1 , , Rn n darab n 3 intelligens robotból álló robot csoport végez rendezési feladatokat a véletlenszerűen elhelyezkedő B j : B1 , B2 , , Bm dobozokon.
68
DOI: 10.15477/SZE.MMTDI.2015.001
B3
B1
B4
B2
B4
B3
B5
R1 R2
B1
R0
R1
B2
B5 R0 R2
27. ábra Kooperatív rendezési feladat
A lehetséges kirakható alakzatok: Ak : A1 , A2 , , Ap , melyek közül egyet kell összeállítani a dobozok mozgatásával, a következő feltételeket teljesítve:
R0 mester-robot tudja, és csak ő tudja a cél feladatot, az elvárt rendezési formát,
a többi robot Ri , i 0 nem ismeri az aktuális célt, de tudja, hogy milyen alakzatokat lehet kirakni,
a többi robot Ri , i 0 tudja, hogy R0 a mester,
minden robot képes megfigyelni a környezetét és a többi robot viselkedését.
bármelyik Bj doboz két robot által tolható vagy forgatható.
A feladat végrehajtásához le kell rögzíteni a vonatkoztatási rendszereket is. A raktárban a földrajzi vonatkoztatási rendszerhez hasonlóan a szélrózsa irányait különböztetem meg, az északi irányt fixen felfele mutatónak véve. Az angol kezdőbetűket használva, óramutató járásával egyező irányba haladva 90°-os lépésekkel a következő jelölések adottak: N – észak, E – kelet, S – dél, W – nyugat. A dobozokhoz viszonyítva is szükség van egy lokális referencia rendszerre. A raktárhoz hasonlóan a szélrózsa jeleit használom itt is, óramutató járásával azonos pozitív körbejárási iránnyal N B , E B , S B , WB , ahol NB a doboz „első oldala”. A jelölés rendszert a 28. ábra mutatja.
69
DOI: 10.15477/SZE.MMTDI.2015.001
28. ábra Doboz és robot jelölések
A dobozok mozgatásához a robotok oldalanként két-két pozíciót vehetnek fel, így összesen nyolc pozíció lehetséges. A pozíciókat Prb D, T -vel jelölöm, ahol r a robot száma, b a doboz száma, D a doboz oldala ahol a robot érinti N B , E B , S B , WB és T a fordítási pozíció, vagyis a robot milyen irányba fordítja a dobozt, mely az angol kifejezésekből CC vagy CW értéket vehet fel. A pozíciók leírására a 29. ábrán láthatunk példát.
Pi j N B , CC
Pi j N B , CW
29. ábra Robot mozgatási pozíciók
Két (esetleg három) robot a pozíciójuk alapján kooperációs kombinációkat alkothatnak, melynek jele C rb, p , q , ahol a r, p és q a kooperációban résztvevő robotok számai (q csak a megállítási kombinációban szerepel), b pedig az aktuális doboz száma. A kombinációk két vagy három pozícióból alkothatók (30. ábra). Párhuzamos mozgatási kombinációról beszélünk, ha két robot azonos oldalon, de különböző forgatási pozícióban vannak, ennek jele: Crb, p P , ahol P a push angol szóra utal. Forgatási kombináció akkor áll elő, ha a két robot szemközti oldalon diagonálisan, tehát azonos forgatási pozícióban érintik a dobozt. A forgatás lehet Crb, p CW vagyis óra járásával azonos irányú (clockwise) vagy azzal ellentétes irányú Crb, p CC (counterclokwise), ahogy az 30. ábra mutatja.
70
DOI: 10.15477/SZE.MMTDI.2015.001
P1 j N B , CC j C1,2 P P2j N B , CW
P1 j N B , CC j C1,2 CC P2j S B , CC
P1 j N B , CW j C1,2 CW P2j S B , CW
30. ábra Kooperatív tolási és forgatási kombinációk
A két alapkombináción kívül létezik még egy ideiglenes kombináció is, ez a megállító kombináció. A megállító kombináció az egyetlen olyan állapot, melyben 3 robot vesz részt. Akkor jön létre, ha egy robot úgy gondolja, hogy a másik kettő a feladat szempontjából rossz kombinációban van. A 31. ábra mutat erre egy példát ahol, az R3 észreveszi, hogy R1 és R2 egy már helyén levő dobozt akar elmozdítani. Ilyenkor a harmadik robot, a másik kettővel „szemben” lévő valamelyik pozíciót veszi fel. A példában az R3 a P3 j S B , CW pozíciót igyekszik felvenni, de felvehetné P3 j S B , CC pozíciót is, ezzel megakadályozza a doboz elmozdulását és jelzi a többieknek a véleményét. Tulajdonképpen ez a megállítási kombináció az egyetlen aktív módja annak, hogy a mester-robot (R0) közvetlenül befolyásolja a többiek műveleteit.
P1 j N B , CC j P2j N B , CW C1,2,3 ST P3 j S B , CW
P1 j N B , CC j P2j N B , CW C1,2,3 ST P3 j S B , CC
31. ábra Megállítási kombinációk
71
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.3.2. Robotok kooperációs vezérlése
Az adott kooperációs feladatot tekintve a robotok intelligens vezérlése és döntéshozatali rendszere funkcionálisan három nagy részre osztható:
Stratégiai szint. Itt történik a feladat megoldásához szükséges legfelsőbb szintű döntés. Ebben a rétegben a teljes feladatot egységében veszi tekintetbe az intelligens vezérlő. Például, itt dönti el a robot, hogy melyik formáció kirakását végzi. A stratégiai döntések az alatta lévő rétegekre közvetlen hatással vannak.
Taktikai szint. A kiválasztott stratégiai célok megoldásához szükséges taktikákat kezeli. Részfeladatokat dolgoz fel, és a cél eléréséhez szükséges lépéseket
fekteti
le.
Stratégiai döntéseknél
dinamikusabb,
gyors
feldolgozást igénylő szint. Itt dől el, hogy melyik dobozt, milyen irányba mozgatják.
Végrehajtás szintje. A robot tényleges mozgatását, útvonaltervezést, akadálykerülést vezérli. A taktikai célok gyakorlati megvalósításának kivitelezése történik ezen a szinten. Az irányítás legalsó része, valós idejű vagy azt nagyon megközelítő működést igényel, így bonyolult algoritmusokat nem hajthat végre.
A dolgozatomban a végrehajtási szint funkcióival nem foglalkozom, stratégiai és taktika döntéstámogató algoritmusok fejlesztését mutatom be. E két döntési szint egy széles határsávval kapcsolódik egymáshoz, így nem mindig különül el élesen egymástól. Tulajdonképpen nem is szükséges az éles szétválasztás a vizsgált feladatban, mert a stratégia is, az alkalmazott fuzzy szituációs térképek tanuló, adaptálódó tulajdonsága miatt elég dinamikusan változhat. A két szint „fuzzy” határa, a döntési kérdések alapján érezhető lesz, még ha nem is teszek erre mindig utalást. Elsőként az általam kidolgozott stratégia döntéstámogató algoritmusait mutatom be, melyek nagyrészt a korábban, a 3. fejeztben, már bemutatott fuzzy szituációs térképekre épülnek. Másodszor a taktikai szinthez tartózó, az egyes objektumokat leíró fuzzy szignatúrákat és az objektumokhoz kapcsolódó (taktikai) döntések mechanizmusát ismertetem.
72
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.3.2.1. Stratégiai döntések Stratégiai szinten dől el, hogy a robot milyen fő cél érdekében kooperál a többiekkel, konkrétabban, hogy milyen aktuális rendezést kell megvalósítani. A rendezési feladat kiindulásaként minden robotnak meg kell adni a lehetséges formákat, amikbe a dobozok rendezhetők. Tekintsük a 32. ábrán látható munkateret, ahol 5 darab doboz vár rendezésre és 3 robot végzi el a kooperatív rendezési feladatot. Az R0 a mester-robot (piros) az R1 és R2 a két szolga-robot (zöld). A lehetséges rendezési Ak T , L, U formátumok a 33. ábrán láthatók.
B4
B3
B1 R1
B2
B5 R0 R2
32. ábra A rendezési feladat munkatere
A1
A2
A3
33. ábra Az Ak T , L,U lehetséges rendezési alakzatok
A robotok fuzzy szituációs térképekben írják le a környezetüket, illetve a feltételezett célalakzatot. Ez a szituációs térkép akár a teljes munkatér, vagy annak egy részterülete, a célterület lehet. A szituációs térképek felbontása a dobozokhoz, illetve a robotokhoz igazított vagy redukált, így minden rácspontja egy 0,1 intervallumon 73
DOI: 10.15477/SZE.MMTDI.2015.001
értelmezett fuzzy tagsági értéket tartalmaz. A rendezési stratégia szempontjából a robotnak azt kell eldöntenie, hogy melyik alakzatot kell kirakni, illetve, hogy melyik rácspontban kell doboznak lennie. Így a döntéshozó rendszerének meg kell különböztetnie olyan pontokat, ahova dobozt kell raknia, ahol egyáltalán nem lehet doboz, és olyan pontokat, ahol a kettő között valamilyen „fuzzysággal” fogadja el azt (34. ábra):
Ha xij 0 , akkor az i, j pozícióba nem kerülhet doboz.
Ha xij 1 , akkor az i, j pozícióba mindenképp dobozt kell helyezni.
Ha xij 0,1 , akkor az i, j pozícióba xij tagsági értékkel fogadható el a doboz.
Ha xij 0.5 , akkor az i, j pozíció semleges állapotban van. Abban az esetben, ha fuzzy szituációs térkép összes rácspontja xij 0.5 értéket vesz
fel, akkor semleges vagy neutrális rendezési térképről beszélünk. A fuzzy szituációs térképek az egyes robotokban dinamikusan változnak a dobozok rendezettségének megfelelően. Mivel az R0 mester-robot pontosan tudja a rendezés célját, így a feladatot leíró szituációs térképe crisp, csak 1 és 0 értékű pontokat tartalmaz (35.a. ábra). 0
0.6
0.7
0
0
0
0.7
1
0.7
0
0.7
1
0.7
0.6
0
0
0
0.6
0
0
0
0
0
0
0
34. ábra Rendezési fuzzy szituációs térkép
A feladat indításánál az R0 mester-robot megkapja a feladatot leíró szituációs térképet, esetünkben az A3 U , és a tárgyak cél pozícióit a munkatérben. A szolgarobotok memóriája neutrális fuzzy szituációs térképet tartalmaz a kezdeti lépésben, ahogy a 35.b. ábra mutatja. Természetesen ez a neutrális térkép nem alapfeltétel, lehet olyan rendszerünk, ahol korábbi tudás alapján már valamilyen előre kialakított fuzzy szituációs térképpel rendelkeznek a szolga-robotok is. Első lépésként a mester-robotnak egy szolga-robot segítségével kell elhelyeznie az első dobozt a célpozíció valamelyik cellájában. Ez az aktiválási pont a szolga-robotok 74
DOI: 10.15477/SZE.MMTDI.2015.001
stratégiai tervezési algoritmusainak beindításához. Előzetes ismeretek alapján le kell fektetni a lehetséges struktúrákat és azokon belül az egyes dobozok helyzetét.
0
0
0
0
0
0.5
0.5
0.5
0.5
0.5
0
1
1
1
0
0.5
0.5
0.5
0.5
0.5
0
1
0
1
0
0.5
0.5
0.5
0.5
0.5
0
0
0
0
0
0.5
0.5
0.5
0.5
0.5
0
0
0
0
0
0.5
0.5
0.5
0.5
0.5
a.
b.
35. ábra Kezdeti szituációs térképek: a) R0 mester-robot crisp térképe, b) szolga-robotok neutrális térképe
Tekintsük az Ak alakzat méretét mint a k alakzatban levő elemek számát, ahol Ak
k 1,, n
jelöli az alakzatokat és n a létrehozható alakzatok száma. Jelen példában
feltételezem, hogy minden alakzatban azonos m = 5 számú elem van (74). Ak m, k 1, , n
(74)
Ettől a ponttól kezdve többféle stratégiai döntéstámogató algoritmus használható. Kétféle alapstratégiát dolgoztam ki. Az első a lokális vagy fuzzy szituációs térkép élmátrixára épülő módszer, a második a teljes alakzatokat figyelembe vevő globális fuzzy szituációs térképet használó algoritmus. 4.1.3.2.1.1. Rendezési döntések lokális fuzzy szituációs térkép él-mátrixával A döntéshozó rendszer lokális fuzzy szituációs térkép él-mátrixát használó módszernél az alakzatokban résztvevő egyes elemek szomszédsági viszonyait veszi figyelembe. Az alakzatokat, mint fuzzy gráfokat tekinti, ahol az élek (kapcsolatok) és azok tagsági értékei kerülnek kiértékelésre, ezekből építi fel az aktuális fuzzy szituációs térképeket. A robot minden egyes alakzathoz létrehoz egy crisp szituációs térképet, melynek leírása kapcsolati- vagy él-mátrixszal történik. A szituációs térkép csomópontok belső kapcsolatainak leírását a 3.1.10. fejezetben mutattam be. Az él-mátrix sorai az egyes
Bj
j 1,, m
elemeket (dobozok), az oszlopai pedig az elemekhez kötött koordinátairányokat 75
DOI: 10.15477/SZE.MMTDI.2015.001
– úgy, mint N B , EB , S B és WB – jelentik. Az m 4 méretű él-mátrixban lévő értékek az egyes elemek (dobozok) kapcsolatait jelentik a koordinátairányoknak megfelelően. Az élmátrix
felépítését
a
(75)
írja
le.
Az
adott
alakzathoz
rendelt
él-mátrix
koordinátairányoknak megfelelő pontjai 1 értéket vesznek fel, ha abban irányban van elem és 0 értéket, ha nincs. Ezzel az él-mátrix egyértelműen leírja az alakzat szomszédsági viszonyait.
B1 E Ai B j Bm
NB EB SB WB eB1 , NB eB1 , EB eB1 ,SB eB1 ,WB eB2 , NB 0 ha D irányba nincs él (75) eB j , D D NB , E B , SB ,WB 1 ha D irányba van él eBm ,WB eBm , NB
A (75) alapján a példában szereplő alakzatok él-mátrixai a következőképpen írhatók le (76):
0 0 E A1 0 1 1
1 0 0 1 1 1 0 0 1 0 1 0 0 0 0
0 0 E A2 0 0 1
1 1 0 0 1 0 1 1 0 1 1 0 1 E A3 0 0 0 0 1 1 0 1 0 0 0 0
1 0 0 1 1 1 0 0 0 0
(76)
Ezek az él-mátrixok leírják az egyes alakzatokhoz tartozó szituációs térkép rácspontok közötti kapcsolatokat (a dobozok szomszédsági rendszerét). Mivel a robot nem „tudja”, hogy melyik alakzatot kell összeállítani, azt sem tudja, hogy melyik él-mátrixot kell használnia, ezért létre kell hozni a fuzzy szituációs térképhez tartozó globális élmátrixot. A szituációs térkép globális él-mátrixa E A tartalmazza az összes lehetséges alakzat elemeinek kapcsolati (él) fuzzy tagsági értékét (77). n
ΕA ahol EAi
i 1,,n
E i 1
Ai
n
(77)
az egyes alakzatok szituációs térképének él-mátrixai és n az
alakzatok száma. Az E A globális él-mátrixban levő értékek eA ( k ,l ) a (78) alapján számolhatók. 76
DOI: 10.15477/SZE.MMTDI.2015.001
n
e A ( k ,l )
eA1 ( k ,l ) eA2 ( k ,l ) eAp ( k ,l ) n
e i 1
Ai ( k ,l )
n
, k 1, , n; l 1, , 4
(78)
A (77) és (78) felhasználásával a feladat globális szituációs térképének él-mátrixa a (79) szerint alakul. Az egyes pontokból (dobozokból) kiinduló éleket, és azok fuzzy tagsági értékét a 36. ábra mutatja, az e 0 fuzzy tagsági értékű élek nincsenek feltüntetve.
1 0.6 0 0 1 0.3 1 E Ai 0 E A i 1 0 0.3 0.3 1 3 0.6 0 0.3 0.3 1 0 0 0 3
B1
1
1
0.6
B2
1
0.3
1
B3
0.3 0.3
0.3
(79)
0.6
1
B4
B5
0.3
36. ábra Az elemekhez kapcsolt fuzzy élek
Ha a robot egyértelműen tudná azonosítani a vizsgált elemet (dobozt), a (79) alapján a rendezés optimális számú iterációs lépéssel elvégezhető lenne, csak a B4 esetén nincs „egyértelmű” szomszédsági él (36. ábra). A lehetőségek leírásához további számítások szükségesek, mivel a robot nem tudhatja, hogy a most helyére került elem (doboz) valójában melyik. A döntéshez egy általános fuzzy él-vektor hozható létre az elemek él-mátrixából, amely az egyes irányokhoz rendelt fuzzy éleket tartalmazza. e Dir eN B , eEB , eSB , eWB m
eD
D N B , EB , S B ,WB
e i 1
A i,D
(80)
m
ahol m az alakzatokban lévő elemek száma. A példában szereplő adatokat behelyettesítve a (80)-ba a következő él-vektort kapjuk (81)(37. ábra): e Dir 0.33, 0.46, 0.33, 0.46
(81)
77
DOI: 10.15477/SZE.MMTDI.2015.001
0.33
0.46
B?
0.46
0.33 37. ábra Általános fuzzy él-vektor
A
következő
elhelyezendő
doboz
legelfogadhatóbb
pozíciójának
meghatározásához a legnagyobb tagsági értékű adatot választja ki a szolga-robot az élvektorból. Abban az esetben, ha nem egyértelmű a helyzet, több azonos tagsági értékű él van, valamilyen másik szabály segítségével el kell döntenie a következő elem helyzetét. Példaként alkalmazhatja az egyszerű „balról-jobbra, fentről-le” szabályt, mellyel a robot képes az azonos fuzzy tagsági értékek feloldására. Ezeknél a „segédszabályoknál” fontos a tanulás, és az előzetes tapasztalatok beépítése, gyakorlatilag a kódkönyv optimalizálását ezek a szabályok segítik elő. A következő elemet az előző E B „keleti” oldalához mozgatják a szolga-robotok. Amennyiben ez a pozíció elfogadható, vagyis az R0 mester-robot nem vesz fel megállító pozíciót, vagy nem akarja eltávolítani a dobozt a helyéről (lásd: 4.1.3.1. fejezet), akkor a fuzzy szituációs térképet az aktuális állapothoz igazítják a robot vezérlők. Az eddig elhelyezett elemek (a, b) biztos résztvevői a konfigurációnak. A robot vezérlőnek a és b elemekre kell felvenni egy-egy új él-mátrixot, illetve él-vektort, a következő szabályok szerint:
az él-mátrix sorai közül törli azokat, melyekben az adott irányban a szomszédság már biztos, de a mátrix 0 értéket tartalmaz, vagyis a kizárható elemeket (dobozokat) elveti,
továbbiakban nem veszi figyelembe azt az oszlopot (irányt), ahol már biztos szomszédja van, a mátrix oszlopszámának megőrzése miatt ezeket az oszlopokat 0-val tölti fel.
Az így átalakított él-mátrix alapján, kiszámítható az új-élvektor, melyet a robot iteratívan alkalmaz az előzőekben vázolt döntési mechanizmusban. Az iterációs lépések addig zajlanak, míg nem történik egy hibás lépés az alakzat kialakításában, vagy a célalakzat el nem készül.
78
DOI: 10.15477/SZE.MMTDI.2015.001
1 0.6 0 0 1 0.3 1 0 0 0.6 0 0 Ea 0 0.3 0.3 1 0 0 0.3 1 0.6 0 0.3 0.3 0 0 0.3 1 1 0 0 0
(82) ea 0 0 0.44 0.66
Hibás lépés esetén egy újabb robot (általában az R0) csatlakozása három robotos megállítási kombinációt hoz létre (lásd: 0. fejezet). Ekkor a kiválasztott pozíciót „tiltja” a döntési algoritmus, vagyis az aktuális él-mátrixból törli azokat a sorokat (lehetséges dobozok), melyeknél nem nulla fuzzy tagsági érték szerepel az adott oldalon. Példaként a c dobozt a nyugati oldalára (WB) akarják helyezni a szolga-robotok, de ez nem jó pozíció, a mester-robot megállítja a mozgatást. A megállítás után a szolga-robotok vezérlője törli az él-mátrix második és harmadik sorát, így egyértelművé válik, hogy a vizsgált elem a B1 doboz és már csak déli szomszédja lehet. 0 0 0.6 0 E a 0 0 0.3 1 0 0 0.6 0 0 0 0.3 1
(83)
Az 1. táblázat a példában leírt rendezési feladat fő lépéseit foglalja össze. A döntéseknél a szolga-robotok csak az elemek közti lokális kapcsolatokat veszik figyelembe.
79
DOI: 10.15477/SZE.MMTDI.2015.001
1. táblázat Rendezési feladat lokális fuzzy szituációs térkép felhasználásával A robotok munkatere
Fuzzy szituációs térképek
Él-mátrixok
R1
Első lépésben a robotok a tengelyekkel párhuzamos
R0
B2
irányba forgatják a dobozokat. R2
Mester
B4
R1
B1
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
R0
B3
Szolga
B2
R2
B5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
1 0.6 0 0 0 1 0.3 1 E A 0 0.3 0.3 1 0.6 0 0.3 0.3 1 0 0 0
80
DOI: 10.15477/SZE.MMTDI.2015.001
A robotok munkatere
Fuzzy szituációs térképek
Él-mátrixok
0
0.33
0
0
0
0.46
1
0.46
0
0
0
0.33
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0.2
0
0
0.66
1
1
0.43
0
0
0.44
0.3
0
0
0
0
0
0
0
0
0
0
0
0
B4 B1 R1
B1
R0
B3
R2
B2
B5
B4
R0
B1
B3
B2
B2 R2 R1
B5
1 0.6 0 0 0 1 0.3 1 E A 0 0.3 0.3 1 0.6 0 0.3 0.3 1 0 0 0 e D 0.33, 0.46 , 0.33, 0.46
0 Ea 0 0 ea 0
0 0.6 0 0 0.3 1 0 0.3 1 0 0.44
0.66
1 0.3 0 Eb 0 0.3 0.3 0.6 0 0.3 eb 0.2 0.43 0.3
0 0 0
0
R2
B4 B4
B1
B2
R1
Hibás döntés!
R0
B3
B5
R1
R2
B4
B1
B2
0
0
0.2
0
0
0
1
1
0.43
0
0
0.6
0.3
0
0
0
0
0
0
0
0
0
0
0
0
R0
ea 0 0
0.6
0
B3
B5
81
DOI: 10.15477/SZE.MMTDI.2015.001
A robotok munkatere
R1
Fuzzy szituációs térképek
R2
B4 R0
B1
B2
Él-mátrixok
0
0
0.2
0
0
e a 0 0 0 0
0
1
1
0.43
0
b-nek nincs új szomszédja
0.15
1
0
0
0
eb 0.2
0
0.15
0
0
0
0
0
0
0
0
0
0
0
0.2
0
0
1
1
1
0.43
0.15
1
0
0.3
0
0
0.15
0
0
0
0
0
0
0
0
B4
B3
B5
B1
R1 R0
B2
B3
0.43
0.3 0
0 0 0.3 0.3 Ec 0 0 0 0 ec 0 0 0.15 0.15
e a 0 0 0 0 eb 0 0 0 0 ec 0 0 0.15 0.15
B4
B3
B5
R2
B1
B2
B3
1 0.3 0 0 E d 0 0.3 0.3 0 0.6 0 0.3 0 e d 0.2
0.43
0.3 0
B5
B4 R0
Hibás döntés! R2
R1
B5
R0
B1 B4
B2
B3
B5 R1
0
0
0
0.2
0
0
1
1
1
0
0.15
1
0
0.3
0
0
0.15
0
0
0
0
0
0
0
0
R2
ed 0.2 0
0.3
0
82
DOI: 10.15477/SZE.MMTDI.2015.001
A robotok munkatere
R2
B1 B4
B2
B3
Fuzzy szituációs térképek
R0
B5
Él-mátrixok
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
B5
R1
Kész az alakzat!
4.1.3.2.1.2. Rendezési döntések globális fuzzy szituációs térképpel
Az előző fejezetben bemutatott, egy-egy elemre koncentráló lokális rendezési módszerrel szemben kidolgoztam egy globális algoritmust is, mely a teljes alakzatot veszi figyelembe. A fuzzy kommunikációban használt kódkönyv a kialakítható alakzatok alapján számított fuzzy szituációs térképre épül. Kezdeti lépésként meg kell határozni a fuzzy szituációs térkép méretét, és fel kell tölteni az előzetes ismereteknek megfelelő adatokkal. Minimális előzetes ismeret a kialakítható alakzatok formája. A fuzzy szituációs térkép maximális mérete A m 2 alakban számítható, ahol m az alakzatokban lévő elemek száma. Tehát, az adott fuzzy szituációs térkép egy m m méretű mátrixszal írható le, melynek elemei az egyes alakzatokat leíró, azonos felépítésű crisp mátrixokból (84) számítható (85).
Ak
k 1,, n
a11 a 21 am1
a12 a1m amm
aij
i , j 1,,m
0 ha aij nincs benne az alakzatban 1 ha aij bent van az alakzatban
(84)
ahol n a lehetséges alakzatok száma.
83
DOI: 10.15477/SZE.MMTDI.2015.001
n
A
A k 1
k
n
(85)
n
aij
i , j 1,, m
a A1 (i , j ) a A2 ( i , j ) a An ( i , j ) n
a k 1
Ak ( i , j )
n
Az A fuzzy szituációs térkép nem biztos, hogy teljes, lehetnek csak 0-t tartalmazó sorai és oszlopai. Ezek a csomópontok egyetlen alakzatban sem szerepelnek, törölhetők a szituációs térképből. Az így felírt fuzzy szituációs térkép az alakzatokhoz kötött, nem pedig azoknak a munkatérben való elhelyezkedéséhez. A szituációs térképet legkorábban az első elem elhelyezésével köthetjük a munkatér tényleges célterületéhez. Az első elem elhelyezését ennél a módszernél is a mester-robot és egy szolga-robot végzi. A további lépések számát drasztikusan csökkenti, ha a rendezés menetét bizonyos szabályokban rögzítjük. Mint már említettem, egyszerű, de hatékony szabály a „balróljobbra, fentről-le” rendezési lépésirány meghatározása. Ez a fuzzy szituációs térképből képzett mátrix soronkénti feldolgozását jelenti. A mester-robot minden esetben így építkezik, a szolga-robotok ezt a szabályt alkalmazzák az azonos fuzzy tagsági értékkel rendelkező rácspontok esetén. Egyszerű, kis elemszámú alakzatoknál jó eredményt szolgáltat a szabály alkalmazása, nagyobb elemszámnál viszont előfordulhat, hogy a rendezés kis tagsági értékű csomópontban indul, ami a szolga-robotok döntéseit megnehezítik, a szándék megsejtéséhez „gyenge” szabályokat tudnak használni. Nagyszámú téves következtetés és azok javítása növelheti a lépések számát. Általánosan használható, konvergenciát gyorsító eljárásra a következőket dolgoztam ki. A mester-robot is létrehozza a szolga-robotoknál leírt fuzzy szituációs térképet és annak egyszerűsített mátrixát. Így a mester rendelkezik egy feladatleíró crisp és egy számított fuzzy szituációs térképpel. A fuzzy szituációs térkép és a crisp térkép standard min operátoros metszetét képezve a mester-robot előállít egy speciális szituációs térképet (AMST). A mester-robot a soronkénti feldolgozás szabályát betartva az így kialakított szituációs térkép legnagyobb tagsági értékű pontja melletti pontban helyezi el az alakzat első elemét. Mivel az elhelyezett elem mellett egy nagy tagsági értékkel rendelkező rácspont van, így a szolga-robotok jó döntésének az esélye megnövekedik, a hibás és a javítási lépések száma csökken.
84
DOI: 10.15477/SZE.MMTDI.2015.001
Ha a szolga-robotok által elhelyezett elem jó helyen van, akkor a robotok megvizsgálják, hogy mely alakzatok tartalmazzák a létrejött rész-alakzatot. A többi alakzat kizárható, az új állapotnak megfelelő fuzzy szituációs térképet a robot vezérlők kiszámítják (85), és a robotok elkezdenek egy újabb iterációs lépést. Az iteráció az első hibás lépésig, vagy az alakzat elkészültéig tart. Hibás lépés esetén, a robot vezérlők az aktuális rácspont tagsági értékét nullázzák, és az újraszámolt fuzzy szituációs térkép legnagyobb tagsági értékű pontjába helyezik az aktuális elemet. Innen egy újabb hiba javítási lépés, vagy egy új iteráció kezdődik az előzőekben leírtak alapján. Tekintsük egy példát erre a globális rendezési algoritmusra. Vegyünk n = 3 alakzatot m = 5 elemmel. Az alakzatok a 38. ábrán és mátrixaik (86) láthatók.
B5
B4
B1
B5
B2
B3
B1
B2
B3
B4
B1
B2
B3
B4
B5
A1
A2
A3
38. ábra Rendezési alakzatok
0 1 0 0 A1 0 1 0 0 1 1 1 0
0 0 0 0 A 2 1 1 1 1 0 1 0 0
0 0 0 0 A 3 0 0 1 0 1 1 1 1
(86)
Az R0 mester-robot megkapja a célalakzat pozícióját és formáját, mely a példában az A2 alakzat. Az aktuális rendezési feladat számított fuzzy szituációs térképét leíró mátrix a (85) alapján (87): 0 0 0.3 0 A 0.3 0.6 0.6 0.3 0.6 1 0.6 0.3 1
(87)
85
DOI: 10.15477/SZE.MMTDI.2015.001
A mester-robot (86) és (87) alapján létrehozott fuzzy szituációs térképe (88):
A MST
0 0 0 0 0.3 0.6 0.6 0.3 0 1 0 0
(88)
Az előzetes szabályok szerint a mester-robot az a32 1 maximális tagsági értékű ponttal szomszédos, a23 0.6 pontba helyezi az első elemet. Mivel a a32 1 pont biztosan része az alakzatnak, ezért a szolga-robotok külön számítások nélkül helyezhetnek ide egy elemet. A mozgatással párhuzamosan a két új elem figyelembevételével átszámítható az A mátrix. Az A3 konfiguráció kiesett a lehetséges alakzatok közül, így az új mátrix (89):
0 0 0.5 0 A 0.5 1 0.5 0.5 0.5 1 0.5 0 2
(89)
Az A3 kiesésével létrejött egy olyan helyzet ahol a kerettel jelölt, helyükön lévő elemeken kívül csak 0.5 (neutrális) tagsági értékű pontok vannak. A szolga-robotok döntését nem segíti ez az állapotleíró, így kénytelenek lennének „vakon” dönteni a következő lépésben. A mester-robot egy újabb művelete segíti a továbblépést. Az előzőekhez hasonlóan az AMST mátrixot használva és a soronként rendezés szabályát figyelembe véve a mester-robot az a21 0.3 pozícióba helyez egy elemet. Ezzel egyértelművé vált, hogy a cél alakzat az A2, a hátralévő két lépést a szolga-robotok önállóan is el tudják végezni (90).
0 A3 1 0
0 1 1
0 0 1 1 0 0
(90)
A 2. táblázat az előző fejezetben bemutatott feladat globális fuzzy szituációs térkép alapú döntési algoritmust alkalmazó megoldásának lépéseit foglalja össze.
86
DOI: 10.15477/SZE.MMTDI.2015.001
2. táblázat Rendezési feladat globális fuzzy szituációs térkép felhasználásával A robotok munkatere
Fuzzy szituációs térképek
R1
Első lépésben a robotok a tengelyekkel párhuzamos
R0
B2
irányba forgatják a dobozokat. R2
Mester
B4
R1
B1
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
A MST
1 0.6 0
0 0 0.3 0 0 0 0
1 1
R0
B3
Szolga
B2
R2
B5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
1 1 0.3 1 A 0.6 0.3 0.3 0 0 0.3 0 0 1
87
DOI: 10.15477/SZE.MMTDI.2015.001
A robotok munkatere
R1
Fuzzy szituációs térképek 0
0
0
0
0
0
1
1
1
0.3
B4
B1
B4
R0
B3
0
0.6
0.3
0.3
0
0
0
0.3
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0.5
0
1
0
0.5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0.5
1 1 1 0.3 A 0.6 0.3 0.3 0 0 0.3 0 0 2
R2
B2
B5
R0
R1
B1 B1
B4
R2
B3
1 1 1 0.5 A3 1 0 0.5 0 0 0 0 0
B2
B5
R0
B1
B2
B4
B3
0
1
0
0.5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0.5
0
1
0
0.5
0
0
0
0
0
0
0
0
0
0
0
1 1 1 0.5 A 1 0 0.5 0 0 0 0 0 4
B2 R2 R1
B5
B1
R1 R0
B2
B3
B4
1 1 1 0.5 A5 1 0 0.5 0 0 0 0 0
B3
R2
B5
88
DOI: 10.15477/SZE.MMTDI.2015.001
A robotok munkatere
B1
B2
B3
Fuzzy szituációs térképek
B5
B4 R0
Hibás döntés! R2
R1
B5
R0
B1
B2
B3
B5 R1
B4
R2
B1 B4
B2
B3
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
R2
1 1 1 A 6 1 0 1 0 0 0
0 0 0
R0
B5
B5
Kész az alakzat! R1
89
DOI: 10.15477/SZE.MMTDI.2015.001
Az előző példát tekintve a lokális fuzzy szituációs térkép él-mátrixát használva 9 lépésben, míg a globális fuzzy szituációs térképpel 7 lépésben oldható meg a feladat. Így elmondható, hogy ebben az esetben a globális fuzzy szituációs térkép hatékonyabb kooperációs stratégiát eredményez. Kisszámú lehetséges alakzat esetén a globális módszer általában gyorsabb, mivel a teljes alakzatot tekinti és így élesebb döntésekre képes. Bonyolult formációk esetén a lokális módszer hatékonysága növekszik, mert minden lépésben csak egy-egy elemet vesz figyelembe, így a formák komplexitása csak a hibás lépések javításával növeli a feladat megoldásának idejét. A lokális módszer alkalmazható olyan esetekben is, ahol az alakzatok nem egyértelműek, csak az egyes elemekről rendelkezünk információval (szomszédsági viszony). A globális és lokális módszerek hatékonyságának és használhatóságának összehasonlítására részletes vizsgálatokat egyelőre nem végeztem, ez a későbbi terveim között szerepel. 4.1.3.2.2. Manipulációs taktikai döntések
A robot stratégiai céljainak eléréséhez a vezérlőnek intelligens taktikai döntéseket kell hoznia. E taktikai döntések szintjén dől el, hogy a következő lépésben melyik elemet fogják mozgatni, illetve ehhez milyen pozíciót vesznek fel a robotok. A robot vezérlők az együttműködéshez szükséges taktikai döntéseket kontextusfüggő rekonstruktív fuzzy kommunikációra támaszkodva hozzák meg. A robotok rendszerállapotot leíró fuzzy szignatúrákra épülő kódkönyveket használnak a fuzzy kommunikációban. 4.1.3.2.2.1. A résztvevők megfigyelése és szándékuk „megsejtése”
A „szándék megsejtése” az a folyamat ahol a kooperációs feladatban az egyik résztvevő a többi aktív résztvevő állapotából, mozgásából következtet annak szándékára, műveletének céljára. Az ismertetett kooperációs példában a művelet egy elem elmozdítására, forgatására vagy éppen ezek megakadályozására irányulhat. Minden egyes szolga-robotnak el kell döntenie, hogy az adott rendszerállapotok mellett a lehetséges stratégiai célok eléréséhez milyen műveleteket fog elvégezni. Gyakorlatilag ez a döntés az egyes kooperációs lépésekben való részvételt határozza meg.
90
DOI: 10.15477/SZE.MMTDI.2015.001
A döntéshez szükséges állapotleíró kétféle fuzzy szignatúra csoportból áll. Az egyik a robotok, a másik a dobozok aktuális állapotát leíró fuzzy szignatúrákat tartalmazza. A Ri robot állapotát, a tárgyakhoz való viszonyát leíró szignatúra struktúráját a 39. ábra és a struktúrához tartózó beágyazott vektorokat a (91) mutatja. Érint
B1
Közel
Messze Távolság Bj
Ri
Bm
Rövid
Várakozási idő
Közepes
Hosszú
39. ábra Ri robot állapotát és szándékát leíró szignatúra
A szignatúra Ri robot egyes dobozoktól való távolságát, esetleg valamelyik doboz érintését és az aktuális állapot fennállásának időtartalmát írja le. A dobozoktól mért távolság alapján lehet eldönteni, hogy melyikkel végez vagy végezne műveletet a robot. Az ideiglenes állapotok döntési mechanizmusból való kiszűréséhez az állapot fennállásának ideje fontos paraméter. Például egy doboz véletlen érintése vagy rövid időtartalmú megközelítése nem kelti fel a figyelmét a többi robotnak, az eset nem kerül be az állapotleírójukba. Az Ri robot és a Bj doboz kapcsolata akkor figyelembe veendő a kooperációs döntésekben, ha az Ri robot érinti, vagy nagyon megközelíti a Bj dobozt és ez az állapot egy adott ideig fennáll. Ebben az esetben fontossá válik a Bj doboz állapotának leírása is, mely a 40. ábrán látható fuzzy szignatúrával, illetve annak beágyazott vektoraival (92) történik.
91
DOI: 10.15477/SZE.MMTDI.2015.001
Érint B Közel 1 Távol Érint Távolság B j Közel Távol Ri Érint Bm Közel Távol Rövid Várakozás Közepes Hosszú
(91)
A tárgyak állapotát leíró fuzzy szignatúrának három fő részfája van. Az első a tárgyon munkát végző robotokat írja le. A tárgy körül lehet egy, két, esetleg három robot. Egy robot esetén annak pozíciója hordoz fontos információkat a szándékáról. A robot segítséget vár, a többieknek el kell dönteni, hogy segítenek-e neki, illetve, hogy milyen módon segítenek neki. Két robot esetén egy kész mozgatási konfigurációról van szó, itt már nem a segítség eldöntése a lényeges, hanem a stratégiai lehetőségek ismeretében a robotok „megsejtett” szándékának elfogadása vagy elvetése. A mozgatási szándék elvetése esetén – ha a tárgy elérhető – a robot célja a megállítási pozíció felvétele lesz. Amennyiben a konfigurációban résztvevő robotok egyike az R0 mester-robot, akkor csak a szándék elfogadása jöhet szóba. Három robotos megállítási konfiguráció hibás lépések megakadályozására jöhet létre, ebben az esetben a megfigyelő robotnak nem kell tennie semmit, csak a stratégiai lehetőségeket kell újra számolnia (lásd: 4.1.3.2.1. fejezet). A szignatúra második részfája a tárgy állapota, mely a tárgy lehetséges cél alakzathoz viszonyított állapotát írja le. Ez az állapot lehet rendezett, ha a vizsgált tárgy nagy tagsági értékű pontban van, lehet mozgatott, mikor két robot dolgozik a tárgyon, illetve lehet rendezetlen, ha nincs alakzatban és nem is mozgatják.
92
DOI: 10.15477/SZE.MMTDI.2015.001
A harmadik részfa a vizsgált tárgy elérhetőségét írja le. A robot a saját helyzetéhez viszonyítva az elérhetőség alapján dönt arról, hogy tud-e optimálisan segíteni a doboz mozgatásában vagy sem. Az elérhetőség ágai a távolság és útvonal. A távolság a tárgy és a robot aktuális pozíciója között értendő, nagy távolságban lévő tárgyak kevésbé aktiválják a robot kooperációs szándékát. Az útvonal, mint összetett nyelvi változó, a könnyű, közepes és nehéz fuzzy halmazokkal írja le a vizsgált tárgy eléréséhez szükséges költségfüggvényt. Az útvonal hossza, nehézsége, a robot bizonyos állapotjellemzői (pl. akkumulátorok töltöttségi szintje) befolyásolják ezt a költségfüggvényt. Minél közelebb van egy tárgy a robothoz, és az elérhetősége sem nehéz, annál nagyobb tagsági értékkel kerül a robot döntési fókuszába. A Bj doboz és a többi robot állapotát, szándékát leíró fuzzy szignatúrák alapján képes dönteni a robot, hogy az aktuális tárgy mozgatásban segítenie kell-e, és képes-e segíteni figyelembe véve a saját helyzetét. A döntési mechanizmus fuzzy szignatúra szabályokból felépített szabálybázison, következtetéssel történik. A szabályok egyszerű ha-akkor felépítésűek: Ha Ri érinti Bj-t és Várakozási idő hosszú akkor Ri a Bj-nél Pi j pozícióban van
93
DOI: 10.15477/SZE.MMTDI.2015.001
CC NB CW
CC EB CW
Pozíció, 1 robot
CC SB CW
CC WB CW
Robot NB
EB Mozg. SB
Kombináció 2 robot
WB
CC Forg Bj CW
3 robot
Rendezett
Állapot
Mozgatva
Rendezetlen
Kicsi
Távolság
Közepes
Nagy Elérhetőség Könnyű
Útvonal
Közepes
Nehéz
40. ábra Bj doboz állapotát leíró szignatúra
94
DOI: 10.15477/SZE.MMTDI.2015.001
CC NB CW CC EB CW Pozíció(1R) CC SB CW CC WB CW Robot N B Mozg . EB S B Kombináció(2 R ) WB Bj CC Forg . CW 3Robot Rendezett Állapot Mozgatva Rendezetlen Kicsi Távolság Közepes Nagy Elérhetőség Könnyű Útvonal Közepes Nehéz
(92)
A 1. pszeudókód mutat be egy-egy fontosabb algoritmus részletet a taktikai döntés menetéből.
95
DOI: 10.15477/SZE.MMTDI.2015.001
1. pszeudókód Taktikai döntéstámogatás
IF Ri Bj távolság = érint AND várakozási idő = hosszú THEN Bj állapota vizsgálandó IF Bj –nél egy robot van (Ri) THEN Ri segítségre vár 1:
pozíció(Ri,Bj)
2:
IF Bj állapota = rendezetlen AND Bj távolság = kicsi AND Bj útvonal = közepes THEN
3:
Ri kiszolgálása
4:
IF Bj feladat = forgatás THEN forgatási kombináció felvétele
_:
kombinacio = forg(Bj,Ri,Rk)
5:
ELSE IF Bj feladat = mozgatás THEN mozgatási kombináció felvétele
6:
kombinacio = mozg(Bj,Ri,Rk)
7: 8:
⋮
9:
END IF ELSE IF Bj állapota = rendezetlen AND Bj távolság = nagy AND Bj útvonal = nehéz
10: 11: _:
THEN
Ri
kiszolgálásosának elvetése következő (Ri+1) robot vizsgálata
12: 13:
⋮
14:
END IF
15: 16:
ELSE IF Bj –nél két robot van (Ri, Rl) AND Bj állapota = mozgásban THEN Stratégiai vizsgálat
17:
IF Bj mozgatása növeli a cél rendezettséget THEN következő (Bj+1) doboz vizsgálata
18:
ELSE Bj mozgatásának megakadályozása
19:
END IF
20:
ELSE IF Bj –nél három robot van (Ri, Rl, R0) THEN Bj rossz pozícióban
21:
Stratégiai fuzzy szituációs térkép módosítása
22:
END IF
23:
ELSE IF Ri Bj távolság = érint AND várakozási idő = rövid THEN következő (Ri+1) robot
24:
vizsgálata ⋮ END IF
96
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.4. Kísérleti robotkooperációs rendszer A kontextusfüggő rekonstruktív fuzzy kommunikációs és az erre épülő intelligens kooperációs algoritmusok kipróbálásához, fejlesztéséhez és működésének igazolásához egy robotkooperációs rendszert terveztem. A robotkooperációs rendszer megvalósításának első lépése a szimulációs környezet, ahol az előző fejezetekben ismertetet elvek alapján végeztem méréseket. A rendszer felépítésének blokkdiagramját a 41. ábra szemlélteti. Marilou Robotics Studio Fizikai, szenzor és aktuátor szimuláció Aréna Akadályok
Munkadarabok
Robotok
Visual C#/C++ Alacsony szintű irányítás Szenzorok
Aktuátorok Adat be- és kivitel
Megjelenítés
Konzol
Mentések, betöltések
Illesztések Marilou
Matlab
VirCA
Matlab
VirCA
Magas szintű irányítás
Távirányítás, távfelügyelet – (kiterjesztett valóság)
Fuzzy szignatúra és fuzzy szituációs térkép alapú döntési motor Tervezés Megvalósítás Kísérletek
Kliens-szerver kapcsolat
Kliens oldali aplikációk
Megjelenítés, szimuláció
HuNoRob
41. ábra Kísérleti robotkooperációs rendszer blokkvázlata
4.1.4.1. Kooperációs környezet és eszközök
A
kooperációs
kísérletek
végrehajtásához
létrehoztam
egy
szimulált
eszközrendszert, mely munkaterületből, robotokból, munkadarabokból, akadályokból és 97
DOI: 10.15477/SZE.MMTDI.2015.001
képfeldolgozáshoz szükséges eszközökből áll. A későbbiekben felépítésre kerülő valós kooperációs környezet elemei szolgáltak a szimulált rendszer alapjául. A rendszer meglévő elemeinek modellezéséhez szükséges tulajdonságait az A. mellékletben ismertetem. 4.1.4.1.1. Szimulált keretrendszer
A szimulációs kísérleti környezetet az előzőekben bemutatott eszközök felhasználásával hoztam létre. Olyan szimulált rendszer kialakítása volt a célom, mely a valós fizikai elemek tulajdonságait és viselkedésüket hűen modellezi. A kinematikai és dinamikai modelleken kívül a hajtások és a szenzorok viselkedését is szimuláltam, a kamerát is beleértve. Tehát a szimulátoron megírt és kipróbált algoritmusok elvileg kis átalakítással átvihetők a valós rendszerre. A szimulációnál még egy fontos szempont volt az algoritmusfejlesztő környezettel való összekapcsolhatóság. Ami viszont nem volt cél, de mint későbbi lehetőség fennáll, a tárgyak élethű 3Ds grafikai megjelenítése. A megjelenítés 3D-s, de sematikus. A szimulált rendszert a Marilou1 dinamikai szimulációs keretrendszerben hoztam létre. Azért esett a választásom a Marilou-ra, mert egy kényelmes használható grafikus szerkesztővel rendelkezik, így a környezet és a modellek megjelenítése gyorsan megalkotható (42. ábra). A hajtások és a szenzorok is meglévő alapelemekből összeállíthatók, és csak a paraméterezés igényel nagyobb figyelmet. Magát a működést programozni kell, C++ vagy C# nyelven. Szimulációs motorként az Open Dynamics Engine 2 -t használom, mely az egyik legjobb dinamikai modellező algoritmus gyűjtemény. Az aréna modellje (42. ábra) egy 2 x 2 m-es csúszásmentes sima felületű, fallal körülvett terület, felette van elhelyezve egy kamera, mely az igazi kamera optika tulajdonságaival rendelkezik. A megvilágítás is a laboratórium neonvilágítását modellezi.
1 2
A Marilou az AnyKode cég bejegyzett védjegye. http://www.anykode.com http://www.ode.org/ode.html
98
DOI: 10.15477/SZE.MMTDI.2015.001
42. ábra Szimulációs keretrendszer
A dobozok színesek, méretben és súlyban azonosak az eredetivel, súrlódási tényezőjük becslésen alapszik, de ennek nincs szignifikáns hatása a működésre. A dobozok tetején a QR-kódok is megtalálhatók. A robotok méretben és súlyban azonosak a fizikaival, QR-kóddal ellátottak. Hajtás tekintetében, a csekély rendelkezésre álló információ alapján, a fizikai robothajtással kinematikailag
azonos,
viszont
dinamikailag
csak
hasonló
modellt
alkottam.
Szenzortechnikai oldalról tekintve, az érzékelők ideális működését szimuláltam, zavarokat, mérési hibákat nem vettem figyelembe. A programozást C# nyelven, illetve az algoritmus fejlesztést Matlab-ban végeztem. Létrehoztam egy Marilou – Matlab intefészt mellyen keresztű a két rendszer képes adatokat cserélni. Az így elkészített keretrendszer alkalmas Khepera robotokkal, illetve robot csoportokkal való szimulált kísérletek végrehajtására. A rendszer általános célú, tehát nem csak az általam leírt kísérletek hajthatók végre benne.
99
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.4.2. Kooperációs rendezési példa szimulált környezetben
Az előző fejezetekben tárgyalt rendezési feladat került megvalósításra a szimulált környezetben. Az objektumok jobb azonosíthatóság érdekében színükkel is meg vannak különböztetve. A mester-robot (R0) piros színű, a két szolga-robot (R1, R2) kék színű. A dobozokból az azonos színűek tartoznak egy csoportba, az alakzatok csak egyszínű dobozokból állhatnak. A 43. ábrán a rendezési feladat szimulált környezete és a mesterrobot fedélzeti kamerájának képe látható. Az 44. ábra képsorozata a szimuláció fontosabb lépéseit mutatja be.
43. ábra Rendezés fedélzeti kamera képpel
100
DOI: 10.15477/SZE.MMTDI.2015.001
1. lépés: Az R0 mester-robot felvesz egy forgatási pozíciót a dobozon.
2. lépés: Az R1 szolga-robot „megsejti” az R0 szándékát és CC forgatási kombinációt képez R0-al.
3. lépés: A doboz elforgatása.
4. lépés: A kombinációban.
5. lépés: Az R2 szolga-robot eddig információkat gyűjtött a folyamatról, elindul a következő lehetséges pozícióba.
6. lépés: Az R2 segítségre vár a mozgatási kombináció kialakitásához.
7. lépés: R1 robot a következtetése alapján segít R2 robotnak.
8. lépés: A szolga-robotok mozgatják a dobozt, a mester-robot ettől a ponttól csak felügyeli a rendezést.
9. lépés: Utolsó doboz helyére mozgatása.
10. lépés: Elkészült az alakzat.
robotok
mozgatási
44. ábra Rendezési feladat lépései
101
DOI: 10.15477/SZE.MMTDI.2015.001
4.1.5. A fejezethez kapcsolódó tézisek
5. tézis.
Megoldást adtam egy robotkooperációs problémára, ahol a résztvevők között nincsen explicit kommunikáció. Igazoltam a fuzzy szituációs térkép és fuzzy szignatúra alapú kódkönyvek használhatóságát
a
kontextusfüggő
rekonstruktív
fuzzy
kommunikációhoz. [B1, B3, B6, B7, B10‐12, B14, B15, B21‐23, B26, B28, B29, B31, B33]
5.1 altézis.
Javaslatot tettem a kooperáló robotok stratégiai és taktikai döntéseinek rendszerére. Megadtam a döntésekhez szükséges fuzzy szituációs térkép és fuzzy szignatúra alapú kódkönyveket, és ezek módosításának
algoritmusait.
Elkészítettem
a
kooperáció
végrehajtásához szükséges kontextusfüggő rekonstruktív fuzzy kommunikáció algoritmusát.
Tézisekre
Létrehoztam egy szimulációs környezetett robotkooperációs
épülő
feladatok vizsgálatára. Megalkottam a Khepera mobil robotok
alkalmazás-
kinematikai és dinamikai szempontból hű modelljét. Alkalmassá
fejlesztés.
tettem a szimulációs keretrendszert külső algoritmusfejlesztő eszközökhöz való csatlakozásra. [B7, B10, B14, B15, B21, B22, B31]
102
DOI: 10.15477/SZE.MMTDI.2015.001
5. Összefoglalás és kitekintés A kutatás eredménye a fuzzy szituációs térkép definíciója, mint több dimenziós, térbeli struktúrával rendelkező fuzzy szignatúra. Kidolgoztam a fuzzy szituációs térképen végrehajtható egyszerű fuzzy halmazműveleteket, javaslatot tettem hatékony és tömör jelölésrendszerre is. A fuzzy szituációs térkép komplex strukturált adatatok leírására alkalmas, úgy, hogy képes kezelni az adatok hiányát és torzultságát is. Ez a tulajdonság a különböző struktúrájú szituációs térképeken való műveletvégzésen és összehasonlíthatóságon alapszik. Ennek érdekében bevezettem a fuzzy szituációs térkép struktúra átalakítási algoritmusát, mellyel a legnagyobb közös struktúra meghatározható. A fuzzy szituációs térkép csomópontjai között bonyolult belső kapcsolatrendszer állhat fent. Kidolgoztam a csomópontok közti kapcsolatokat leíró fuzzy gráfok átalakítási módszerét egyszerű fuzzy szignatúrákká. Megadtam a többrétegű fuzzy szituációs térképek felépítésének, a dimenzió növelésnek az alapszabályait. A fuzzy szituációs térképek következtető rendszerekben való használatához kidolgoztam a szabálybázis átalakításának, a szabályok felépítésének rendszerét és bemutattam a Mamdani következtető eljárás kiterjesztését erre a szabálybázisra. A tézisek igazolására egy robotkooperációs feladatot építettem fel, ahol egy robot csoport mozgat tárgyakat valamilyen cél elérése érdekében. A csoportból csak egy robot tudja a konkrét célt, a többieknek bizonyos előzetes ismeretei vannak a feladattal kapcsolatban. Ezeket az ismereteket kódkönyvekben tárolják. A robotok között nincs explicit kommunikáció, viszont képesek megfigyelni a környezetüket és egymást. A feladat megoldásához kontextusfüggő rekonstruktív fuzzy kommunikációt használnak, ahol a dinamikusan változó, tanuló, kódkönyvek fuzzy szituációs térképekre és szignatúrákra épülnek. Elkészítettem a robotrendszer számítógépes szimulációját, ahol a fuzzy szituációs térkép alapú kódkönyvek használhatósága és hatékonysága bizonyításra került. A disszertációban leírt kutatások önmagukban is önálló eredményeket jelentenek, de egyben új kutatási irányt nyitottak meg, ahol a komplex rendszereknél jelentkező kooperációs és kommunikációs problémák megoldására alkalmazható módszerek keresése, fejlesztése a cél. A szimulációs környezet jó kiindulási alap ezekhez a
103
DOI: 10.15477/SZE.MMTDI.2015.001
kísérletekhez, a valós modell felépítése pedig a szimulációban jelentkező korlátok feloldásához szükséges.
104
DOI: 10.15477/SZE.MMTDI.2015.001
Irodalomjegyzék [1]
[2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]
[14] [15] [16]
K. A. Wyrobek, E. H. Berger, H. F. M. Van der Loos, and J. K. Salisbury, "Towards a personal robotics development platform: Rationale and design of an intrinsically safe personal robot," in Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, 2008, pp. 2165-2170. M. Mataric, M. Nilsson, and K. Simsarian, "Cooperative multi-robot box pushing," in IEEE International Confereence on Intelligent Robots and Systems (IROS, 1995, pp. 556-561. T. Haider and M. Yusuf, "A fuzzy approach to energy optimized routing for wireless sensor networks," The International Arab Journal of Information Technology, vol. 6, pp. 179-188, 2009. J. Iqbal, M. M. Yousaf, and M. M. Awais, "A scalable approach of message interpretation by demonstrations for multi-robot communication," in IEEE 13th International Multitopic Conference, INMIC, 2009, pp. 1-6. R. J. Kok, T. J. M. Spaanand, and N. Vlassis, "Non-communicative multi-robot coordination in dynamic environments," Robotics and Autonomous Systems, vol. 50, pp. 99-114, February 2005. X.-L. Long, J.-P. Jiang, and K. Xiang, "Towards Multirobot Communication," in IEEE International Conference of Robotics and Biomimetics, ROBIO, 2004, pp. 307-312. Y. Meng, J. V. Nickerson, and J. Gan, "Multi-robot Aggregation Strategies with Limited Communication," in International Conference on Intelligent Robots and Systems (IEEE/RSJ), Beijing, China, 2006. J. V. Nickerson, "A concept of communication distance and its application to six situations in mobile environments," IEEE Transactions on Mobile Computing, vol. 4, pp. 409-419, 2005. J. V. Nickerson and S. Olariu, "A Measure of Integration and its Application to Sensor Networks," in WITS2005, 2005. G. Ran, H. Zhang, and S. Gong, "Improving on LEACH Protocol of Wireless Sensor Networks Using Fuzzy Logic," Journal of Information and Computational Science, vol. 7, pp. 767-775, 2010. N. Roy and G. Dudek, "Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations," Autonomous Robots, vol. 11, pp. 117-136, 2001. K. Shah and Y. Meng, "Communication-Efficient Dynamic Task Scheduling for Heterogenous Multi-Robot Systems," in IEEE International Symposium on Computational Intelligence in Robotics an Automation, USA, 2007, pp. 230-235. H. Yanco and L. Stein, "An Adaptive Communication Protocol for Cooperating Mobile Robots," in From Animals to Animats: International Conference on Simulation of Adaptive Behavior, J.-A. Meyer, H. Roitblat, and S. Wilson, Eds., ed: MIT press, 1993, pp. 478-485. R. Whitaker and O. Ostberg, "Channeling Knowledge: Expert Systems as Communications Media," AI and Society, vol. 2, pp. 197-208, 1988. B. R. Donald, J. Jennings, and D. Rus, "Analyzing Teams of Cooperating Mobile Robots," TR94-14291994. P. Zebrowski. (2004). Communication In Multi-Robot Systems. Available: http://www.sfu.ca/pzebrows/cmpt816/index.htm
105
DOI: 10.15477/SZE.MMTDI.2015.001
[17] [18] [19]
[20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34]
A. Sciutti, L. Patane, F. Nori, and G. Sandini, "Understanding Object Weight from Human and Humanoid Lifting Actions," Autonomous Mental Development, IEEE Transactions on, vol. 6, pp. 80-92, 2014. J. Denny, A. Giese, A. Mahadevan, A. Marfaing, R. Glockenmeier, C. Revia, et al., "Multi-robot caravanning," in Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on, 2013, pp. 5722-5729. B. Hayes and B. Scassellati, "Improving implicit communication in mixed humanrobot teams with social force detection," in Development and Learning and Epigenetic Robotics (ICDL), 2013 IEEE Third Joint International Conference on, 2013, pp. 1-7. M. Awais and D. Henrich, "Human-robot collaboration by intention recognition using probabilistic state machines," in Robotics in Alpe-Adria-Danube Region (RAAD), 2010 IEEE 19th International Workshop on, 2010, pp. 75-80. T. Wang, Q. Dang, and P. Pan, "A Predict-Fuzzy Logic Communication Approach for Multi Robotic Cooperation and Competition," Journal of Communication, vol. 6, 2011. P. Pedrycz and E. Roventa, "From Fuzzy Information Processing to Fuzzy Communication Channels," Kybernetes, vol. 28, pp. 515-526, 1999. L. Horváth and I. J. Rudas, Modelling and Solving Methods for Engineers. Burlington, MA: Elsevier, Academic Press, 2004. E. Hüllermeier and S. Vanderlooy, "Combining predictions in pairwise classification: an optima ladaptive voting strategy and its relation to weighted voting," Pattern Recognition, vol. 43, pp. 128-142, 2010. L. Martinez, D. Ruan, F. Herrera, and E. Herrera-Viedma, "Linguistic decision making: Tools and applications Preface," Information Sciences, vol. 179, pp. 22972298, Jun 27 2009. D. Naso, M. Surico, B. Turchiano, and U. Kaymak, "Genetic algorithms for supplychain scheduling: A case study in the distribution of ready-mixed concrete," European Journal of Operational Research, vol. 177, pp. 2069-2099, Mar 16 2007. Y. Tang and J. Lawry, "A prototype-based rule inference system incorporating linear functions," Fuzzy Sets Syst., vol. 161, pp. 2831-2853, 2010. H. Bustince, M. Pagola, E. Barrenechea, J. Fernandez, P. Melo-Pinto, P. Couto, et al., "Ignorance functions. An application to the calculation of the threshold in prostate ultrasound images," Fuzzy Sets Syst., vol. 161, pp. 20-36, 2010. P. Cintula, E. P. Klement, R. Mesiar, and M. Navara, "Fuzzy logics with an additional involutive negation,," Fuzzy Sets Syst., vol. 161, pp. 390-411, 2010. D. Graves and W. Pedrycz, "Kernel-based fuzzy clustering and fuzzy clustering: a comparative experimental study,," Fuzzy Sets Syst., vol. 161, pp. 522-543, 2010. R. E. Haber, R. Haber-Haber, A. Jiménez, and R. Galán, "An optimal fuzzy control system in a network environment based on simulated annealing. An application to a drilling process," Appl. Soft Comput., vol. 9, pp. 889-895, 2009. I. Harmati and K. Skrzypczyk, "Robot team coordination for target tracking using fuzzy logic controller in game theoretic framework," Robotics Autonomous Syst., vol. 57, pp. 75-86, 2009. D. Hladek, J. Vaščák, and P. Sinčák, "Multi-robot control system for pursuitevasion problem," J. Electr. Eng., vol. 60, pp. 143-148, 2009. C.-L. Hwang, H.-M. Wu, and C.-L. Shih, "Fuzzy sliding-mode underactuated control for autonomous dynamic balance of an electrical bicycle," IEEE Trans. Control Syst. Technol., vol. 17, pp. 658-670, 2009.
106
DOI: 10.15477/SZE.MMTDI.2015.001
[35] [36] [37] [38] [39] [40] [41] [42] [43] [44]
[45] [46] [47] [48] [49] [50] [51] [52]
S. Kurnaz, O. Cetin, and O. Kaynak, "Fuzzy logic based approach to design flight control and navigation tasks for autonomous UAVs," J. Intell. Robotic Syst., vol. 54, pp. 229-244, 2009. O. Linda and M. Manic, "Fuzzy force-feedback augmentation for manual control of multirobot system," IEEE Trans. Ind. Electron., vol. 58, pp. 3213-3220, 2011. Y. Narukawa and V. Torra, "Multidimensional generalized fuzzyintegral," Fuzzy Sets Syst., vol. 160, pp. 802-815, 2009. I. Perfilieva and B. De Baets, "Fuzzy transforms of monotone functions with application to image compression," Inf. Sci., vol. 180, pp. 3304-3315, 2010. A. Sala, T. M. Guerra, and R. Babuška, "Perspectives of fuzzy systems and control," Fuzzy Sets Syst., vol. 156, pp. 432-444, 2005. J. Zhang, P. Shi, and Y. Xia, "Robust adaptive sliding-mode control for fuzzy systems with mismatched uncertainties," IEEE Trans. Fuzzy Syst., vol. 18, pp. 700711, 2010. L. T. Koczy and K. Hirota, "Approximate Reasoning by Linear Rule Interpolation and General Approximation," International Journal of Approximate Reasoning, vol. 9, pp. 197-225, Oct 1993. L. T. Koczy and K. Hirota, "Interpolative Reasoning with Insufficient Evidence in Sparse Fuzzy Rule Bases," Information Sciences, vol. 71, pp. 169-201, Jun 15 1993. L. T. Kóczy and K. Hirota, "Approximative Inference in Hierarchical Structured Rule Bases," in Proceedings of Fifth IFSA World Congress, 1993. P. Baranyi, D. Tikk, T. D. Gedeon, and L. T. Kóczy, "Alpha-cut interpolation technique in the space of regular conclusion," in 9th IEEE International Conference on Fuzzy Systems (FUZZ IEEE 2000), SanAntonio,TX,USA, 2000, pp. 478-482. J. Fodor and I. J. Rudas, "On continuous triangular norms that are migrative," Fuzzy Sets Syst., vol. 158, pp. 1692-1697, 2007. Z. C. Johanyák, "Student evaluation based on fuzzy rule interpolation," Int. J. Artif. Intell., vol. 5, pp. 37-55, 2010. Z. C. Johanyák, D. Tikk, S. Kovács, and K. W. Wong, "Fuzzy rule interpolation Matlab toolbox—FRI toolbox," in 15th International Conference on Fuzzy Systems (FUZZ-IEEE’06), Vancouver, BC, Canada, 2006, pp. 1427-1433. L. T. Kóczy, K. Hirota, and L. Muresan, "Interpolation in Hierarchical Fuzzy Rule Bases," in 9th IEEE International Conference on Fuzzy Systems, 2000, pp. 471477. M. Štěpnička, U. Bodenhofer, M. Daňková, and V. Novák, "Continuity issues of the implicational interpretation of fuzzy rules," Fuzzy Sets Syst., vol. 161, pp. 19591972, 2010. K. W. Wong, D. Tikk, T. D. Gedeon, and L. T. Koczy, "Fuzzy rule interpolation for multidimensional input spaces with applications: A case study," Ieee Transactions on Fuzzy Systems, vol. 13, pp. 809-819, Dec 2005. Á. Ballagi and L. T. Kóczy, "Fuzzy Signature Based Mobil Robot Motion Control System," in 5th Slovakian - Hungarian Joint Symposium on Applied Machine Intelligence, SAMI 2008, Herlany, Slovakia, 2008, pp. 29-33. Á. Ballagi and L. T. Kóczy, "Multi-Robot Cooperation by Fuzzy Signature Sets," in International Multi-Conference on Complexity, Informatics and Cybernetics (IMCIC'10), Orlando, Florida, USA, 2010, pp. 154-159.
107
DOI: 10.15477/SZE.MMTDI.2015.001
[53] [54] [55] [56]
[57]
[58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72]
Á. Ballagi, L. T. Kóczy, and C. Pozna, "Fuzzy Action Selection in Multi-Robot Task," in The Third Győr Symposium on Computational Intelligence, Győr, Hungary, 2010, pp. 35-37. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Robot Systems with Fuzzy Signature Rule Basas," Acta Technica Jaurinensis, vol. 4, pp. 71 - 88, 2011. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Intelligent Multi-Robot Cooperation," in Factory Automation 2011, Győr, 2011, pp. 248 - 251. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Effective Multi-Robot Cooperation without Explicit Communication," in Fifth Győr Symposium and First Hungarian-Polish Joint Conference on Computational Intelligence, Győr, Hungary, 2012, pp. 118124. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Intelligent Robot Cooperation with Fuzzy Communication," in Issues and Challenges of Intelligent Systems and Computational Intelligence. vol. 530, L. T. Kóczy, C. R. Pozna, and J. Kacprzyk, Eds., ed: Springer International Publishing, 2014, pp. 185-197. T. Vámos, G. Bíró, and L. T. Kóczy, "Fuzzy Signatures," in SIC-EUROFUSE'99, Budapest, 1999, pp. 210-217. T. Vámos, L. T. Kóczy, and G. Bíró, "Fuzzy Signatures in Data Mining," in IFSA World Congress and 20th NAFIPS International Conference, Vancouver, 2001, pp. 2842-2846. C. Pozna, N. Minculete, R.-E. Precup, L. T. Kóczy, and Á. Ballagi, "Signatures: Definitions, operators and applications to fuzzy modelling," Fuzzy Sets and Systems, vol. 201, pp. 86-104, 2012. L. T. Kóczy and T. D. Gedeon, "Context Dependent Reconstructive Communication," in International Symposium on Computational Intelligence and Intelligent Informatics, ISCIII 2007, Agadir, Morocco, 2007, pp. 13-19. P. Galambos and P. Baranyi, "VirCA as Virtual Intelligent Space for RTMiddleware," in IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM2011), Budapest, Hungary,, 2011. L. T. Kóczy and D. Tikk, Fuzzy Rendszerek: Typotex, 2000. L. A. Zadeh, "Fuzzy Sets," Information and Control, vol. 8, pp. 338-353, 1965. M. Sugeno, "Fuzzy measures and fuzzy integrals: A survey," in Fuzzy Automata and Decision Processes, M. M. Gupta, G. N. Sadiris, and B. R. Gaines, Eds., ed Amsterdam - New York: North-Holland, 1977, pp. 89-102. J. Dombi, "The pliant concept and the Generalized Dombi operator," in IEEE International Workshop on Soft Computing Applications (SOFA), SzegedHungary, 2005. J. Dombi, "Towards a General Class of Operators for Fuzzy Systems," Fuzzy Systems, IEEE Transactions on, vol. 16, pp. 477-484, 2008. E. H. Mamdani and S. Assilian, "An Experiment in Linguistic Synthesis with a Fuzzy Logic Controller," International Journal of Man-Machine Studies, vol. 7, pp. 1-13, 1975. P. M. Larsen, "Industrial application of fuzzy logic control," Int. J. of Man Machine Studies, vol. 12, pp. 3-10, 1980. H. Hellendoorn and C. Thomas, "Defuzzification in fuzzy controllers," J. of Intelligent and Fuzzy Systems, vol. 1, pp. 109-123, 1993. T. Takagi and M. Sugeno, "Fuzzy identification of systems and its applications to modeling and control," IEEE Trans. Syst. Man Cybern., vol. 15, pp. 116-132, 1985. L. T. Kóczy, "Fuzzy if then rules models and their transformation into one another," IEEE Trans. on SMC, vol. 26, pp. 621-637, 1996. 108
DOI: 10.15477/SZE.MMTDI.2015.001
[73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83]
[84]
[85] [86] [87]
[88] [89]
L. A. Zadeh, "Outline of a new approach to the analysis of complex systems and decision processes," IEEE Transactions on Systems Man and Cybernetics, pp. 2844, 1973. L. T. Kóczy and M. Hajnal, "A new attempt to axiomatize fuzzy algebra with an application example," Problems of Control and Information Theory, vol. 6, pp. 4766, 1977. L. T. Kóczy, "Computational complexity of various fuzzy inference algorithms," Annales Univ. Sci. Budapest, Sect. Comp., vol. 12, pp. 151-158, 1991. L. T. Kóczy, "Algorithmic aspects of fuzzy control," Int. J. of Approximate Reasoning, vol. 12, pp. 159-217, 1994. L. T. Kóczy, "Complexity of bounded compact rule based fuzzy inference.," in 3rd Joint IFSA-EC and EURO-WG Workshop on Fuzzy Sets, Visegrád, Hungary, 1990, pp. 59-60. A. Stoica, "Fuzzy processing based on alpha-cut mapping," in 5th IFSA World Congress (IFSA '93), Seoul, 1993, pp. 1266-1269. W. Yu and Z. Bien, "Design of fuzzy logic controller with inconsistent rule base," J. of Intelligent and Fuzzy Systems, vol. 3, 1995. J. Bruinzel, V. Lacrose, A. Titli, and H. B. Verbruggen, "Real time fuzzy control of complex systems using rule-base reduction methods," in 2nd World Automation Congress (WAC'96), Montpellier, 1996. L. X. Wang, R. Langari, and J. Yen, "Principal components, B-splines, and fuzzy system reduction.," Fuzzy Logic for the Applications to Computer Systems, pp. 255259, 1996. Y. Yam, "Fuzzy approximation via grid point sampling and singular value decomposition," IEEE Trans. on SMC, vol. 27, pp. 933-951, 1997. P. Baranyi, A. Martinovics, D. Tikk, L. T. Kóczy, and Y. Yam, "Ageneral extension of fuzzy SVD rule base reduction using arbitrary inference algorithm," in IEEE Int. Conf. on System Man and Cybernetics (IEEE-SMC’98), San Diego, USA, 1998. P. Baranyi, A. Martinovics, D. Tikk, Y. Yam, and I. Nagy, "Fuzzy rule base reduction for arbitrary inference algorithm using singular value decomposition," in 5th Int. Conf. on Soft Computing and Information/Intelligent Systems, Iizuka, Japan, 1998, pp. 487-490. P. Baranyi, Y. Yam, C. T. Yang, and A. Várkonyi-Kóczy, "Complexity reduction of the rational general form," in 8th IEEE Int. Conf. on Fuzzy Systems (FUZZIEEE’99), Seoul, Korea, 1999, pp. 366-371. Y. Yam and P. Baranyi, "Reduction of fuzzy rule base via singular value decomposition," IEEE Trans. on FS, vol. 7, pp. 120-132, 1999. P. Baranyi, Y. Yam, C. T. Yang, and A. Várkonyi-Kóczy, "Practical extension of the SVD based reduction technique for extremely large fuzzy rule bases," in IEEE Int. Workshop on Intelligent Signal Proc. (WISP’99), Budapest, Hungary, 1999, pp. 29-33. M. Sugeno, M. F. Griffin, and A. Bastian, "Fuzzy hierarchical control of an unmanned helicopter," in 5th IFSA World Congress (IFSA’93), Seaul, Korea, 1993, pp. 1262-1265. M. Sugeno and G. K. Park, "An approach to linguistic instruction based learning," Intern. J. of Uncertainity, Fuzziness and Knowledge-Based Systems, vol. 1, pp. 1956, 1993.
109
DOI: 10.15477/SZE.MMTDI.2015.001
[90] [91] [92]
[93] [94] [95]
[96] [97] [98] [99] [100] [101] [102] [103] [104]
[105] [106] [107]
L. T. Koczy and K. Hirota, "Size reduction by interpolation in fuzzy rule bases," Ieee Transactions on Systems Man and Cybernetics Part B-Cybernetics, vol. 27, pp. 14-25, Feb 1997. Y. Yam and L. T. Koczy, "Representing membership functions as points in highdimensional spaces for fuzzy interpolation and extrapolation," Ieee Transactions on Fuzzy Systems, vol. 8, pp. 761-772, Dec 2000. K. W. Wong, L. T. Koczy, T. D. Gedeon, A. Chong, and D. Tikk, "Improvement of the cluster searching algorithm in Sugeno and Yasukawa's qualitative modeling approach," Computational Intelligence: Theory and Applications, Proceedings, vol. 2206, pp. 536-549, 2001. D. Tikk, I. Joo, L. T. Koczy, P. Varlaki, B. Moser, and T. D. Gedeon, "Stability of interpolative fuzzy KH controllers," Fuzzy Sets and Systems, vol. 125, pp. 105-119, Jan 1 2002. D. Tikk, G. Biro, T. D. Gedeon, L. T. Koczy, and J. D. Yang, "Improvements and critique on Sugeno's and Yasukawa's qualitative modeling," Ieee Transactions on Fuzzy Systems, vol. 10, pp. 596-606, Oct 2002. S. Kovacs and L. T. Koczy, "Application of the approximate fuzzy reasoning based on interpolation in the vague environment of the fuzzy rulebase in the fuzzy logic controlled path tracking strategy of differential steered AGVs," Computational Intelligence, vol. 1226, pp. 456-467, 1997. L. T. Koczy and A. Zorat, "Fuzzy systems and approximation," Fuzzy Sets and Systems, vol. 85, pp. 203-222, Jan 23 1997. L. T. Koczy and M. Sugeno, "Explicit functions of fuzzy control systems," International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, vol. 4, pp. 515-535, Dec 1996. L. T. Koczy, "Fuzzy if ... then rule models and their transformation into one another," Ieee Transactions on Systems Man and Cybernetics Part a-Systems and Humans, vol. 26, pp. 621-637, Sep 1996. L. T. Koczy, "Algorithmic Aspects of Fuzzy Control," International Journal of Approximate Reasoning, vol. 12, pp. 159-219, Apr-May 1995. P. Baranyi, L. T. Koczy, and T. D. Gedeon, "A generalized concept for fuzzy rule interpolation," Ieee Transactions on Fuzzy Systems, vol. 12, pp. 820-837, Dec 2004. K. Balazs and L. T. Koczy, "Constructing Dense, Sparse, and Hierarchical Fuzzy Systems by Applying Evolutionary Optimization Techniques," Applied and Computational Mathematics, vol. 11, pp. 81-101, 2012. J. A. Goguen, "L-fuzzy sets," J. Math. Anal. Appl, vol. 18, pp. 145-174, 1967. L. T. Kóczy, "Vector valued fuzzy sets," Bulletin for studies and exchanges on fuzziness and its applications, pp. 41-57, 1980. K. W. Wong, A. Chong, T. D. Gedeon, L. T. Kóczy, and T. Vámos, "Hierarchical fuzzy signature structure for complex structured data," in International Symposium on Computational Intelligence and Intelligent Informatics (ISCIII), Nabeul, Tunisia, 2003, pp. 105-109. L. A. Zadeh, "Fuzzy sets as a basis for theory of possibility," Fuzzy Sets and Systems, vol. 1, pp. 3-28, 1978. B. S. U. Mendis, T. D. Gedeon, and L. T. Kóczy, "Investigation of Aggregation in Fuzzy Signatures," in 3rd International Conference on Computational Intelligence, Robotics and Autonomous Systems, CIRAS 2005, Singapore, 2005. B. S. U. Mendis, T. D. Gedeon, and L. T. Kóczy, "Generalised Weighted Relevance Aggregation Operators for Hierarchical Fuzzy Signatures," in International 110
DOI: 10.15477/SZE.MMTDI.2015.001
[108] [109] [110] [111] [112] [113] [114] [115]
[116] [117] [118] [119]
[120]
[121] [122] [123]
Conference on Computational Inteligence for Modelling Control and Automation and International Conference on Intelligent Agents Web Technologies and International Commerce (CIMCA'06), Sydney, 2006, p. 198. K. Tamás and L. T. Kóczy, "Mamdani-type inference in fuzzy signature based rule bases," in 8th International Symposium of Hungarian Researchers (CINTI 2007), Budapest, Hungary, 2007, pp. 513-525. K. Tamás and L. T. Kóczy, "Inference in Fuzzy Signature Based Models," Acta Technica Jaurinensis, vol. 1, pp. 573-594, december 2008. K. Tamás and L. T. Kóczy, "Selection from a fuzzy signature database by mamdani-algorithm," in 6th International Symposium on Applied Machine Intelligence an Informatics (SAMI 2008), Herlany, Slovakia, 2008, pp. 63-68. M. Swaine, "Breadth-first search," Dr Dobbs Journal, vol. 25, pp. 100-+, Jun 2000. R. Zhou and E. A. Hansen, "Breadth-first heuristic search," Artificial Intelligence, vol. 170, pp. 385-408, Apr 2006. S. Beamer, K. Asanovic, and D. Patterson, "Direction-optimizing breadth-first search," Scientific Programming, vol. 21, pp. 137-148, 2013. D. A. L. Garcia and F. Gomez-Bravo, "Vodec: A fast Voronoi algorithm for carlike robot path planning in dynamic scenarios," Robotica, vol. 30, pp. 1189-1201, Dec 2012. F. S. Hover, R. M. Eustice, A. Kim, B. Englot, H. Johannsson, M. Kaess, et al., "Advanced perception, navigation and planning for autonomous in-water ship hull inspection," International Journal of Robotics Research, vol. 31, pp. 1445-1464, Oct 2012. I. Ardiyanto and J. Miura, "Real-time navigation using randomized kinodynamic planning with arrival time field," Robotics and Autonomous Systems, vol. 60, pp. 1579-1591, Dec 2012. A. Tuncer and M. Yildirim, "Dynamic path planning of mobile robots with improved genetic algorithm," Computers & Electrical Engineering, vol. 38, pp. 1564-1572, Nov 2012. M. Julia, A. Gil, and O. Reinoso, "A comparison of path planning strategies for autonomous exploration and mapping of unknown environments," Autonomous Robots, vol. 33, pp. 427-444, Nov 2012. N. Takemura, Y. Nakamura, Y. Matsumoto, and H. Ishiguro, "A Path-Planning Method for Human-Tracking Agents Based on Long-Term Prediction," Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, vol. 42, pp. 1543-1554, Nov 2012. M. X. Yuan, Z. L. Ye, S. Cheng, S. A. Wang, and Q. Wang, "A novel small-world algorithm incorporating chaos optimization and its application to robot path planning," Proceedings of the Institution of Mechanical Engineers Part I-Journal of Systems and Control Engineering, vol. 226, pp. 1356-1370, Nov 2012. B. Park and W. K. Chung, "Efficient environment representation for mobile robot path planning using CVT-PRM with Halton sampling," Electronics Letters, vol. 48, pp. 1397-1398, Oct 25 2012. B. Park, J. Choi, and W. K. Chung, "Sampling-Based Retraction Method for Improving the Quality of Mobile Robot Path Planning," International Journal of Control Automation and Systems, vol. 10, pp. 982-991, Oct 2012. J. T. Bao, H. R. Tang, and A. G. Song, "Combining Vision Learning and Interaction for Mobile Robot Path Planning," International Journal of Advanced Robotic Systems, vol. 9, Oct 4 2012.
111
DOI: 10.15477/SZE.MMTDI.2015.001
[124] L. T. Kóczy, "Fuzzy graphs in the evaluation and optimization of networks," Fuzzy Sets and Systems, vol. 46, pp. 307-319, 1992. [125] M. Flaherty, "Abundant Communication! The University of Montana Rural Institute," ed. [126] T. Terano and others, "Research Projects at LIFE," presented at the Laboratory for International Fuzzy Engineering Research, Yokohama, 1993. [127] L. A. Zadeh, "Precisiated Natural Language – Toward a Radical Enlargement of the Role of Natural Languages in Information Processing, Decision and Control," in ICONIP'02, Singapore, 2002. [128] J. T. Schwartz and M. Sharir, "On the Piano Movers’ Problem: II. General techniques for computing topological properties of algebraic manifolds," in Advances in Applied Mathematics, ed, 1983, pp. 298-351. [129] P. Caloud and W. Choi, "Indoor automation with many mobile robots," in In IEEE IROS'90, ed, 1990. [130] B. R. Donald, J. Jennings, and D. Rus, "Analyzing Teams of Cooperating Mobile Robots," ed. [131] C. Kube and E. Bonabeau, "Cooperative transport by ants and robots," Robotics and Autonomous Systems, pp. 85--101, 2000. [132] C. R. Kube and H. Zhang, "Collective robotic intelligence," in Proc. Second Int. Conf on Simulation of Adaptive Behavior, ed, 1993, pp. 460--468. [133] C. R. Kube and H. Zhang, "Task modelling in collective robotics, Autonomous Robots 4(1," ed, 1997, pp. 53--72. [134] F. R. Noreils, "An Architecture for Cooperative and Autonomous Mobile Robots," in In IEEE Int. Conf. on Robotics and Automation, ed, 1992. [135] L. E. Parker, "ALLIANCE: An Architecture for Fault Tolerant, Cooperative Control of Heterogeneous Mobile Robots," in "Intelligent Robots and Systems (IROS’94)", IEEE/RSJ/GI (editor, ed, 1994, pp. 776--783. [136] D. J. Stilwell and J. S. Bay, "Towards the development of a material transport system using swarms of ant-like robots," in 1994 IEEE/RSJ International Conference on Intelligent Robots and Systems, ed, 1993. [137] T. J. Soon, "QR Code," Synthesis journal, 2008.
112
DOI: 10.15477/SZE.MMTDI.2015.001
Saját publikációk [B1] [B2] [B3]
[B4] [B5] [B6] [B7] [B8] [B9] [B10] [B11]
[B12] [B13] [B14] [B15] [B16]
Á. Ballagi and L. T. Kóczy, "Fuzzy Communication in Cooperation of Mobile Robots," in First Győr Symposium on Computational Intelligence, Győr, Hungary, 2008, pp. 22-25. Á. Ballagi, L. T. Kóczy, and T. D. Gedeon, "Local Codebook Construction for Fuzzy Communication in Cooperation of Mobile Robots," Acta Technica Jaurinensis, vol. 1, pp. 547-560, 2008. Á. Ballagi, L. T. Kóczy, and T. D. Gedeon, "Fuzzy Communication and Motion Control by Fuzzy Signatures in Intelligent Mobile Robots," in Aspects of Soft Computing, Intelligent Robotics and Control. vol. Volume 241/2009, J. Fodor and J. Kacprzyk, Eds., ed: Springer Berlin / Heidelberg, 2009, pp. 147-164. L. T. Kóczy and Á. Ballagi, "Fuzzy communication and cooperation of mobile robots," in 3rd International Workshop on Soft Computing Applications, SOFA '09., Szeged -- Arad, Hungary -- Romania, 2009, pp. 25-26. Á. Ballagi and L. T. Kóczy, "Fuzzy Communication and Cooperation of Intelligent Mobile Robots," in Workshop on Cognitive and Eto-Robotics in iSpace (CERiS’10), Budapest, Hungary, 2010. Á. Ballagi and L. T. Kóczy, "Loose cooperation of mobile robots," in 11th Intern. Carpathian Control Conference (ICCC’2010), Eger, Hungary, 2010, pp. 469-472. Á. Ballagi and L. T. Kóczy, "Multi-Robot Cooperation by Fuzzy Signature Sets," in International Multi-Conference on Complexity, Informatics and Cybernetics (IMCIC'10), Orlando, Florida, USA, 2010, pp. 154-159. Á. Ballagi and L. T. Kóczy, "Robot Cooperation by Fuzzy Signature Sets Rule Base," in 8th IEEE International Symposium on Applied Machine Intelligence and Informatics, (SAMI 2010), Herlany, Slovakia, 2010, pp. 37-42. Á. Ballagi and L. T. Kóczy, "Fuzzy Communication in Collaboration of Intelligent Agents," in 9th WSEAS Int. Conference on APPLIED COMPUTER and APPLIED COMPUTATIONAL SCIENCE, Hangzhou, China, 2010, pp. 208-214. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Fuzzy Action Selection in Multi-Robot Task," in The Third Győr Symposium on Computational Intelligence, Győr, Hungary, 2010, pp. 35-37. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Fuzzy Signature Based Fuzzy Communication of Mobile Robots," in Intern. Conference on Computing and Communication Technologies (IEEE-RIVF 2010), Hanoi, Vietnam, 2010, pp. 119122. L. T. Kóczy and Á. Ballagi, "Robot Systems with Fuzzy Signature Rule Bases," in The Third Győr Symposium on Computational Intelligence, Győr, Hungary, 2010, pp. 7-10. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Fuzzy Situational Maps as Decision Support in Mobile Robotics," in Fourth Győr Symposium on Computational Intelligence, Győr, 2011, pp. 10 - 13. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Robot Systems with Fuzzy Signature Rule Basas," Acta Technica Jaurinensis, vol. 4, pp. 71 - 88, 2011. Á. Ballagi, L. T. Kóczy, and C. Pozna, "Intelligent Multi-Robot Cooperation," in Factory Automation 2011, Győr, 2011, pp. 248 - 251. C. Pozna, L. T. Kóczy, R.-E. Precup, N. Minculete, and Á. Ballagi, "Cooperation of Agents in Fuzzy Environments," in WConSC 2011, San Francisco, 2011, p. (CD). 113
DOI: 10.15477/SZE.MMTDI.2015.001
[B17] C. Pozna, L. T. Kóczy, R.-E. Precup, N. Minculete, and Á. Ballagi, "A cooperation scenario for multiagent systems," in AFRICON 2011, Livingstone, 2011. [B18] C. Pozna, N. Minculete, R.-E. Precup, L. T. Kóczy, and Á. Ballagi, "Signatures: Definitions, operators and applications to fuzzy modelling," Fuzzy Sets and Systems, vol. 201, pp. 86-104, 2012. [B19] Á. Ballagi, C. Pozna, P. Földesi, and L. T. Kóczy, "Fuzzy Situational Maps: a New Approach in Mobile Robot Cooperation," in IEEE 17th International Conference on Intelligent Engineering Systems, San Jose, Costa Rica, 2013, pp. 287-292. [B20] Á. Ballagi and L. T. Kóczy, "A New Fuzzy Graph and Signature Based Approach to Describe Fuzzy Situational Maps," in IEEE World Congress on Computational Intelligence (WCCI 2014 - FUZZ-IEEE 2014), Beijing, China, 2014. [B21] Á. Ballagi, L. T. Kóczy, and C. Pozna, "Intelligent Robot Cooperation with Fuzzy Communication," in Issues and Challenges of Intelligent Systems and Computational Intelligence. vol. 530, L. T. Kóczy, C. R. Pozna, and J. Kacprzyk, Eds., ed: Springer International Publishing, 2014, pp. 185-197. [B22] Á. Ballagi and L. T. Kóczy, "Fuzzy Signature Based Mobil Robot Motion Control System," in 5th Slovakian - Hungarian Joint Symposium on Applied Machine Intelligence, SAMI 2008, Herlany, Slovakia, 2008, pp. 29-33. [B23] T. Ádám, Á. Ballagi, J. Vásárhelyi, and I. Dalmi, "Intelligent Mobile Robot Development for Logistic Applications," in 10th International Carpathian Control Conference, ICCC'2009, Zakopane, Poland, 2009, pp. 199-202. [B24] Á. Ballagi and L. T. Kóczy, "Fuzzy Communication in a Cooperative Multi-Robot Task," in 10th International Carpathian Control Conference, ICCC'2009, Zakopane, Poland, 2009, pp. 59-62. [B25] Á. Ballagi and L. T. Kóczy, "Fuzzy Signature Sets in Robot Control," in Second Gyõr Symposium on Computational Intelligence, Gyõr, Hungary, 2009, pp. 41-44. [B26] Á. Ballagi, L. T. Kóczy, and T. D. Gedeon, "Motion control and communication of cooperating intelligent robots by fuzzy signatures," in IEEE International Conference on Fuzzy Systems, FUZZ-IEEE 2009., Jeju Island, South Korea, 2009, pp. 1073-1078. [B27] Á. Ballagi, L. T. Kóczy, and T. D. Gedeon, "Robot Cooperation without Explicit Communication by Fuzzy Signatures and Decision Trees," in International Fuzzy Systems Association World Congress, IFSA 2009, Lisbon, Portugal, 2009, pp. 1468-1473. [B28] Á. Ballagi and L. T. Kóczy, "Decision Making in Multi-Robot Cooperation by Fuzzy Signature Sets," in WCCI 2010 IEEE World Congress on Computational Intelligence, Barcelona, Spain, 2010, pp. 1049-1056. [B29] Á. Ballagi, L. T. Kóczy, and C. Pozna, "Context Recognition in Mobile Robots Cooperation Using Fuzzy Signature," in Intern. Conference on Theoretial and Mathematical Foundations of Computer Science (TMFCS), Orlando, Florida, USA, 2010, pp. 110-114. [B30] Á. Ballagi, L. T. Kóczy, and C. Pozna, "Man-Machine Cooperation without explicit communication," in World Automation Congress (WAC-ISSCI 2010), Kobe, Japan, 2010, pp. 1171-1176. [B31] Á. Ballagi, L. T. Kóczy, and C. Pozna, "Effective Multi-Robot Cooperation without Explicit Communication," in Fifth Győr Symposium and First Hungarian-Polish Joint Conference on Computational Intelligence, Győr, Hungary, 2012, pp. 118124.
114
DOI: 10.15477/SZE.MMTDI.2015.001
[B32] Á. Ballagi and L. T. Kóczy, "Path planning pre-optimization by fuzzy situational map," in International Congress on Control and Information Processing (ICCIP'13), Cracow, Poland, 2013. [B33] Á. Ballagi and L. T. Kóczy, "Robot path planning pre-optimization by multilayer fuzzy situational maps," Technical Transactions series Automatic Control, vol.4, 2014, pp. 65-75.
115
DOI: 10.15477/SZE.MMTDI.2015.001
A.
Melléklet
A.1. A munkaterület A robotos feladatok elvégzéséhez egy 2 x 2 méteres körbekerített „aréna” készül, ahol több robot képes mozogni és különböző feladatokat elvégezni. Az aréna fölött kerül elhelyezésre egy PTZ IP kamera, mely megfelelő képi információt közvetít az arénában történtekről. A dolgozatban ismertetett kísérlet egy raktárban történő rendezési feladat, így az aréna most nevezhető raktárnak is. A munkadarabok 300 x 300 x 100 mm-es négyszögletes dobozok. Méretük és súlyuk a robotok méretéhez és képességéhez igazított, két robot által könnyen eltolhatók. Akadályként azok a dobozok szolgálnak, melyek a feladatban éppen nem vesznek részt.
A.2. Khepera robotok A kísérleti feladatokat Khepera III. robotokból képzett csoportok végzik. A Khepera3 robotok (K3) kisméretű fejlesztési célú differenciál hajtásos mobil robotok (45. ábra), melyek mint alap platformok nagyon népszerűek a kutatási feladatokban. A Khepera III. robotok alaptulajdonságait a 3. táblázat foglalja össze.
45. ábra Khepera III. robot
3. táblázat Khepera III. robot tulajdonságai
3
Processzor
DsPIC 30F5011 @ 60 MHz
RAM
4 KB @ DsPIC, 64 MB @ KoreBot
Khepera III. a K-Team SA. terméke. http://www.k-team.com
116
DOI: 10.15477/SZE.MMTDI.2015.001
Falsh
66 KB @ DsPIC, 32 MB @ KoreBot
Hajtás
2 x DC motor inkrementális jeladóval (~22 imp/mm robot mozgás)
Sebesség
max: 0.5 m/s
Szenzorok
11 IR és 5 UH távmérő
Tápellátás
Cserélhető Li-Po akkumulátorral, akár 8 órás üzemidő
Kommunikáció
Bluetooth soros
Mérete
Ø 130 mm, magasság: 70 mm
Tömeg
690 g
Terhelhetőség
2 kg
A táblázatból kiolvasható, hogy a fedélzeti számítási kapacitása nem túl nagy a K3 robotnak. Ezt a korlátot kétféleképpen lehet áthidalni. Az első lehetőségként a robot bővítőportján keresztül egykártyás számítógép felhelyezésével a fedélzeti számítási kapacitás közvetlenül növelhető. Erre a legalkalmasabb eszköz a KoreBot4 számítógép, melyen beágyazott Linux operációs rendszer fut. Ennek a módszernek az előnye, hogy az autonómitás továbbra is biztosítható, hátránya az akkumulátor élettartalmának drasztikus csökkenése és a kényelmetlen programozási felület. A másik lehetőség az „off-board”, vagyis külső számítógépen keresztül történő irányítás. A robot és az irányító számítógép Bluetooth-on keresztül kommunikál. A robot fedélzeti vezérlője csak az alap funkciókat látja el, hajtások irányítása, érzékelők kezelése. A fölérendelt számítógép a szenzorjelek vételét és feldolgozását, az irányítási algoritmusok futtatását és a motorvezérlő parancsok kiadását végzi. Ennek az összeállításnak az egyetlen hátránya az autonóm működés bizonyos részeinek a feladása. Kutatási szempontból nagyon előnyős, hogy könnyen kezelhető, bővíthető számítási erőforrás áll rendelkezésre. Kutatásaimban a második összeállítást használom.
4
KoreBot a K-Team SA. terméke. http://www.k-team.com
117
DOI: 10.15477/SZE.MMTDI.2015.001
Az számítási algoritmusok jelentős része MATLAB5-ban kerül fejlesztésre, ahol elsőként elkészítettem egy khepera osztályt mely a Khepera III. robotok vezérléséhez szükséges metódusokat tartalmazza.
A.2.1. Khepera robotok szenzorrendszere A robot három féle szenzor csoportot tartalmaz:
kerekek forgását mérő inkrementális jeladók,
infravörös távolságmérők,
ultrahangos távolságmérők.
Inkrementális jeladók
A hajtás mindkét oldala fel van szerelve egy-egy inkrementális jeladóval, melyek a kerekek (egész pontosan a motorok) elfordulásával arányos impulzus sorozatot adnak. A kerék egy teljes körülfordulása 2764 impulzust ad. A kerék átmérője Ø 41 mm, így egy körülfordulással 128,8 mm-t tesz meg a robot, tehát egy impulzus kb. 0.05 mm elmozdulást jelent. Gyakorlatban ez a pontosság csak méréstechnikai szempontból érhető el, a robot nem pozícionálható ilyen pontossággal. Az elérhető pontosság milliméter nagyságrendű, ami az elvégzendő feladatokhoz elegendő. Infravörös távolságmérők
A Khepera robot 11 darab infravörös távolságmérő érzékelővel van felszerelve, ebből 9 darab körben a robot oldalpalástján, míg 2 darab a robot alján van elhelyezve, ahogy a 46. ábra mutatja.
46. ábra Kheperea robot IR érzékelői
5
A MATLAB a The MathWorks Inc. bejegyzett védjegye. http://www.mathworks.com
118
DOI: 10.15477/SZE.MMTDI.2015.001
A két alsó szenzor alkalmassá teszi a robotot a vonalkövetésre, illetve lukak és más mély akadályok érzékelésére. A körben elhelyezett szenzorok az akadályok érzékelésére alkalmasak. Az infravörös érzékelők kétféle üzemmódban működhetnek: 1. Külső infravörös tartomány érzékelése. Ebben az üzemmódban a szenzorok passzívak, vagyis nem bocsájtanak ki infravörös sugarakat. A környezet sugárzását mérik. A mérés eredményét felhasználhatjuk a környezeti sugárzás kompenzálására, hőforrások keresésére, illetve aktív infravörös bójákkal navigációra. 2. Aktív távolságmérés. A szenzor infravörös sugarakat bocsát ki, és a visszavert sugár beesési szöge alapján meghatározza a mért távolságot. A mérés a robot körüli tárgyak távolságának meghatározására használható. Általában kis távolságok mérésre és jól reflektáló felületek esetén alkalmazható. Az alkalmazott szenzor 12 bites és 2 – 20 mm közötti távolságok mérésére alkalmasak. Az IR szenzorok karakterisztikája a 47. ábrán látható.
47. ábra IR érzékelők karakterisztikája
Ultrahangos távolságmérők
A robot palástján 180° -os tartományban 5 darab ultrahangos távolságmérő szenzor van elhelyezve. A szenzorok egy adó és egy vevő egységből állnak, melyek 40 kHz-en működnek. A tárgyakról visszavert ultrahang futási idejét mérik, és abból számítják a távolságot. Közepes távolságok, 20 – 40 cm-es tartományok mérésére alkalmasak. Hátrányuk, hogy érzékenyek a felület minőségére, hangelnyelő képességére, illetve az interferenciák hamis méréseket okozhatnak. Az alkalmazott szenzor karakterisztikája a 48. ábrán látható.
119
DOI: 10.15477/SZE.MMTDI.2015.001
48. ábra UH érzékelők karakterisztikája
Ezek az egyszerű szenzorrendszerek alkalmasak arra, hogy a robot egy részben strukturált környezetben egyszerű navigációs feladatokat végezzen. Az aréna fölött lévő külső kamerával kiegészítve a kísérleti rendszerben elvégezhetőek a rendezési feladat mérései.
A.3. Munkatérben lévő tárgyak azonosítása, lokalizálása Az arénában lévő minden egyes tárgyat, dobozt és robotot azonosítani kell, és pontos pozíció és orientáció adatokat is kell gyűjteni róluk. Ehhez az aréna fölött elhelyezett PTZ IP kamera képei szolgáltatnak információt. A kamera képes kisebb területekre nagyítani így egyes részfeladatok közelebbről is vizsgálhatók. Az azonosításnál az igazi problémát az azonos elemek, robotok és dobozok, egymástól való megkülönböztetése és a pozíciók és orientációk meghatározása jelenti. A problémát egy egységes jelölő rendszer bevezetésével oldottam meg. A jelölésnek egyértelműnek, kamera által jól láthatónak és hibatűrőnek kell lennie. Mind a dobozok, mind a robotok azonos módon egy-egy QR-kóddal vannak megjelölve. A QRkód egy kétdimenziós vonalkód, pontosabban pont kód, melyet 1994-ben a Japán DensoWave cég dolgozott ki [137], 2000-ben nemzetközi szabvány lett, igazi elterjedése az okostelefonoknak köszönhető. A QR-kód képes 4296 alfanumerikus karakter tárolására és akár 30 % veszteség, hiba visszaállítására is. A 49. ábrán látható felépítése adta az ötletet, hogy nem csak információ hordozásra lehet használni, hanem a tárgyak pozícióját és orientációját is azonosítani lehet a segítségével. Ebben az esetben a kód pontos elhelyezése nagyon fontos.
120
DOI: 10.15477/SZE.MMTDI.2015.001
49. ábra A QR-kód felépítése
A robotok esetén a kód átlós eligazodási pontjait összekötő egyenes felezőpontját kell a robot referencia pontjához, helyben fordulási pontjához rögzíteni, ezzel a robot pozíciója meghatározható. Az orientáció meghatározása a következőképpen történik: a bal és a jobb oldali eligazodási pont közötti egyenes merőleges a robot elejét és hátulját összekötő középtengelyére, és ez az egyenes a robot elejéhez van közelebb. Így a robot elejének iránya, orientációja egyértelműen meghatározható. Dobozok esetén is hasonló az eljárás, csak itt a fedőlap geometriai középpontjához kötött a kód középpontja. A bal és a jobb oldali eligazodási pontot összekötő egyenes merőleges a dobozhoz rendelt észak-dél tengelyre, és a doboz „felső”, északi oldalához van közelebb. A QR-kód hordozza az azonosításhoz szükséges adatokat is, amely itt egyszerűen a robot azonosítója (pl. R0) vagy a doboz azonosítója (pl. B2) és esetleg színkódja. A 50. ábra mutat egy példát az R0 robot QR-kód jelölésére.
50. ábra Robot QR-kód jelölése
A leírtakból egyértelműen következik, hogy a QR-kódos azonosítási rendszer egy optimális megoldást jelent a robotok és dobozok jelölésére. A rendszernek egy további 121
DOI: 10.15477/SZE.MMTDI.2015.001
előnye is kihasználható a képfeldolgozási feladatokban. Mivel a QR-kód olvasásának megvannak a megfelelő algoritmusai, és mivel a kód elhelyezkedése és tárgy geometriája egyértelműen meghatározott, nem kell további képfeldolgozási algoritmusokat végrehajtani. Ha a kódot sikerült leolvasni, akkor az alatta lévő tárgy mind geometriailag, mind pozíció és orientáció tekintetében egyértelműen meghatározottnak vehető és a további számításokban feldolgozható.
122
