Informatika | Mesterséges intelligencia » Zsigmond-Biró - Kommunikáción alapuló problémamegoldás a raj robotikában

XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 Kommunikáción alapuló probléma megoldás raj robotikába Zsigmond Imre Babes-Bolyai Tudományegyetem, Matematika és Informatika kar, Informatika-angol, III. év Témavezető: Dr. Oltean Mihai, Lector Babes-Bolyai Tudományegyetem, Matematika és Informatika kar, Programozási Nyelvek és Módszerek Tanszék Biró Gábor Kolozsvári Műszaki egyetem, Matematika és Informatika kar, Informatika szak, III. év XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 1 Tartalomjegyzék 1 Tartalomjegyzék.2 2 Bevezető .3 3 Eddigi munka a területen.4 4 A rendszer összetevői .4 5 4.1 A környezet .4 4.2 A robotok javasolt tulajdonságai.4 4.3 Modulok: egy általános kép.5 Kommunikáció .6 5.1 Modul szétosztás .7 5.11 Probléma fák .7 5.12 Modulok: részletes áttekintés.9 5.13 Leképzési mechanizmus. 11 6 Konklúzió és további

munka. 15 7 Köszönetnyilvánítás . 15 8 Referenciák . 15 2 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 2 Bevezető Az utóbbi évtizedekben nagy hangsúlyt fektettek a robotika fejlesztésébe. A fejlesztések egy része elosztott rendszerekre és elosztott intelligenciára irányul. Az elosztott gondolkozásmóddal kapcsolatos például a Mars landolás körül kialakult vita is, ahol a kérdés az volt, hogy egyetlen komplex és minden feladatot ellátni képes robotot küldjenek vagy nagyszámú, egyszerű robotot, amelyek közösen képesek megvalósítani a feladatot. Az egyik fő érv a raj mellet a komplex robot sérülékenysége volt, ami a küldetés sikerét kockáztatta. Ellenben ha az egyszerűbb robotok fele meghibásodik, akkor a többi még be tudja fejezni a küldetést. Egy másik terület ahol nagyszámú egyszerű robotot használnának: a nanotechnológia. A raj ötlete a természetből származik. Egy

hangyakolónia az egyedek viszonylagos korlátozottsága ellenére lenyűgöző hatékonysággal old meg bizonyos problémákat. A fejlesztésekben használt egyszerű robotok bizonyos tekintetben hasonlítanak a hangyákra. Szenzoraikkal érzékelni tudják környezetüket, helyváltoztatásra képesek, egyesek a környezetük megváltoztatására alkalmas eszközökkel is rendelkeznek. Ez a dolgozat azonban nem tartozik az igazán „raj-ihletett” munkák közé, ugyanis az alant tárgyalt robotok közvetlen kommunikációra is képesek. Továbbá a dolgozat témáját egy probléma-modellezést alátámasztó adatstruktúra és probléma-megoldást alátámasztó interakciók képezik, nem maguk a problémamegoldó eljárások. Részben már kész rendszerekre kifejlesztett tehnológiákból merítettünk ötletet, mint például paralellizáció, pipelining és részben egyéni ötletekből készült rendszert próbálunk a robotika dinamikus világára alkalmazni. Pontosabban

olyan kommunikációs rendszert keresünk, amely az egyéni robot szintjén nem megoldható problémák esetén alkalmazható és amely összhangban van a robot–raj dinamikus tulajdonságaival. A dolgozat szerkezete: A területen lévő eddigi munka a 2. részbe található, a rendszer összetevőivel a 3. szekció foglalkozik, probléma megoldással kapcsolatos rész a 4 szekcióban, míg konklúziók és referenciák az 5. szekcióban találhatóak 3 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 3 Eddigi munka a területen Rengeteg raj alapú adatküldési algoritmus létezik. A legnépszerűbb az AntNet[1,2], egy adaptív ügynök alapú adatküldési algoritmus amely hatékonyabb az addig ismert adatküldési algoritmusoknál több csomag alapú kommunikációs hálózaton. Telefon hálózatoknál létezik egy sikeres applikáció Ant-Based Control[1,4,5] néven. Heusse et al[3] egy érdekes példát ad raj átirányításra Bellman

dinamikus programozási princípiumaira alapozva[6] . 4 A rendszer összetevői 4.1 A környezet • Részlegesen megfigyelhető (a robotok korlátozott érzékelési hatósugara miatt) • Stratégiai (a környezet kommunikáció-gátló tulajdonságait nem vesszük figyelembe csak a robot helyzetét és hogy hány szomszéddal tud egy adott ponton kommunikálni) • Szekvenciális (akármelyik robot képes a Topológiai gráfot (lásd: 4.2) megváltoztatni) • Dinamikus (a rajnak alkalmazkodnia kell változó környezethez) • Diszkrét (pontosan definiált állapotok a robotoknak, boolean típusú ingerek (van vagy nincs)) • Több játékos (kooperatív) 4.2 A robotok javasolt tulajdonságai Mesterséges intelligencia tudomány szempontjából a következő tulajdonságokat tartjuk fontosnak: • Korlátolt problémamegoldó képesség • Korlátolt adattárolási kapacitás • Kommunikáció korlátolt hatótávval • Helyváltoztatási képesség •

Korlátozott hatótávú szenzorok 4 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 1. ábra Szenzor és kommunikációs hatósugár Funkcionalitás szempontjából 2 entitást külömböztetünk meg a rajban. Az első típusú az ún „dolgozó” robot, mely rendelkezik a fent felsorolt tulajdonságokkal. A második típusú entitás az ún. „királynő” (az elnevezés önkényes), amely kapcsolatban áll a raj 1 vagy kevés számú tagjával (belépési pontok). Elsődleges feladata a raj által megoldandó probléma előkészítése mely folyamat végeredménye egy az alábbiakban ismertetett adatstruktúra az ún. “Probléma fa” (lásd 511) A problémának ezt az előkészített formáját átadja a dolgozóknak azok kommunikációs képességének keretei között. Más tulajdonságot nem feltételezünk a “királynőről”. A dolgozók és királynő(k) együtt a rajt alkotják, melyet topológiai gráf segítségével

modellezünk. Pontos koordinátája a robotoknak nem ismert ezért az élek a gráfba csak az aktív kapcsolatokat jelzik. A királynő(k) bárhol elhelyezkedhet(nek) 4.3 Modulok: egy általános kép A királynő által küldött adatok alapvető alkotóeleme a „modul” ami egy nagyobb probléma elégségesen kisméretű, darabja vagy egy utasítás, melyet egy robot fel tud dolgozni. Tartalmazhat utasítást, műveletet, műveletekhez szükséges adatot. Egy modulokra szétosztott probléma a probléma fát alkotja (lásd 5.11), amit egy erre a célra létrehozott algoritmus („Leképezési mechanizmus”) megfeleltet a már említett topológiai gráffal. Pontosabb magyarázatot a 4. szekcióba lehet találni 5 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 A modulokat a dolgozók „befogadják” és feldolgozzák. Amennyiben a modulban leírt müveletekhez szükséges adatok nem állnak rögtön rendelkezésre, úgy a dolgozónak

várnia kell. A hiányzó adatokat más modulok szolgáltatják és a maga során minden modul (a gyökér kivételével) a probléma valamely alrészének megoldását szolgáltatja az igénylőknek. Maga az igénylés nem dinamikus folyamat, már a probléma előkészítésénél pontosan lehet tudni, melyik modulnak melyik más modulok eredményére van szüksége. A dolgozók egymás között modulokat közvetítenek figyelembe véve a bennük tárolt információt és a leképezési algoritmust (lásd 5.13) Modulokról részletesen a 4.2 fejezetben lehet olvasni 5 Kommunikáció Várható problémák: • küldő és címzett közt nem biztos, hogy van közvetlen vagy közvetett kapcsolat • összeköttetések megjelenhetnek és eltűnhetnek a robotok mozogása során A kommunikáció ún. üzenetek és modulok küldésén alapszik Mivel wireless kommunikáció esetében nem lehet ténylegesen egy adott robotot célozni, az üzenetet/modult minden közeli robot megkapja,

melyek azután eldöntik, hogy fogadják-e azt vagy sem. Az egymással kapcsolatban álló robotok állandóan kommunikálnak, hogy egymás elérhetőségét számon tarthassák (ezáltal az újonnan csatlakozó robotok könnyen beépülnek a rajba). Minden robot - az ún kiáltás révén - elküldi a saját azonosítószámát, az éppen tárolt modul azonosítóját (ha van) és szabad szomszédjai számát, továbbá jelzi hogy ő maga szabade vagy sem. Ezen információkra szüksége van egy jó átirányító algoritmusnak Amennyiben egy üzenetnek nincs konkrét címzettje, vagy az távol van a küldőtől, a kiáltások száma hatványozottan megnövekedhet, túlterhelve a rajt. Ennek elkerüléséért egyrészt egy üzenetet csak egyszer szabad egy robotnak megismételni (ez feltételez valamilyen erre alkalmas nyilvántartást vagy a robotban, vagy magában a kiáltás tartalmában), másrészt szükséges a modulokhoz és üzenetekhez ún. „élettartam” információt

rendelni. Amennyiben ez utóbbi optimális értékéről nem lehet megbízható feltételezést tenni, alkalmazható az ún. „Iterative Deepening Search” eljárás: a küldő többször kiálltja ugyanazt, mindig egyel nagyobb élettartamú üzenetet vagy modult küldve ki. Ezt addig végzi, amíg a címzett nem válaszol vagy a kiáltások száma el nem ér egy felső, globális határt. 6 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 Modul átadás két szomszéd között történik: a küldő először egy „lefoglaló” üzenetet küld. Ha a címzett képes fogadni a modult, akkor válaszol Ezután, ha megkapja a modul másolatát, ismét válaszol, visszaigazolva a modul átvételét. Ha a küldő megkapja a visszaigazolást, törli a nála levő modult, ellenkező esetben egy bizonyos várakozási idő után újra kezdi az átadási eljárását. Ezt korlátozott számú alkalommal ismételi meg A modulok müködéséről bővebben

a 4.2 szekcióban lehet olvasni Az egyszerű üzenet általános robot-közi protokollok lebonyolítására vagy moduleredmények és hibaüzenetek közvetítésére alkalmas. 5.1 Modul szétosztás Ebben a részben bemutatjuk a modul szétosztás részleteit. 5.11 Probléma fák Az egyes robotok igen korlátozott számítási kapacitással rendelkeznek, ezért a problémamegoldás terhét szét kell osztani a bolyban. Feltételezzük, hogy a problémák, amelyekkel a boly szembekerül, ismételten szétoszthatóak alproblémákra, egészen addig, amíg egy elégségesen kis alproblémákból álló „probléma fát” nem kapunk. A probléma fa csomópontjai az úgynevezett „modulok” melyek közül a „levelek” a kielégítően egyszerű alproblémákat, a többi pedig a közöttük fennálló logikai kapcsolatokat jelöli. Bizonyos esetekben a probléma eredendően párhuzamosítható („paralellization”). A kérdés az, hogyan alkalmazható a probléma fa és

kommunikáló robotok egy halmaza (a boly) úgy, hogy ez problémamegoldó eljárást támaszthasson alá. Erre próbálunk választ adni Ki kell hangsúlyoznunk a különbséget a topológiai gráf és a probléma fa között. Az előbbi a bolyban létező kapcsolatokat ábrázolja (kapcsolat gráf), míg az utóbbi a megoldandó probléma egy modellezése. Vegyünk példaképpen egy problémát, melynek megoldása háromszor annyi kapacitást venne igénybe, mint amivel egy dolgozó rendelkezik. 7 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 2. ábra A probléma 3 külömböző típusú felosztása Komplex modul – nem igényel számítást, a problémának ezen része teljesen parallelizálható Vegyes modul – számítást igényel, bizonyos rész-problémák leosztodnak almoduloknak Elemi model – számítást igényel és megoldható önmagánban A fenti ábrán három elképzelhető probléma fa látható. Az első megoldás

paralellizációra alapul. Három elemi modul tartalmazza a probléma egyharmadát. Megoldásaik egy (negyedik) komplex modul részét képezik mely mintegy összegezi ezeket a megoldásokat. A második megoldás erősen lineáris. Az utolsó – elemi – modul kivételével mindegyik modul csak részlegesen képes megoldani a problémát, szüksége van más modulok segítségére. Ezek megoldásait kombinálja a sajátjával és feljebb küldi a megfelelő modulhoz. 8 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 A harmadik megoldás ismét feltételezi a probléma teljes paralellizálhatóságát, továbbá a fa minden szintjén szétoszlik ún. fej-részre és maradék-részre A számításokat elemi modulok végzik, eredményeiket komplex modulok összegezik. A első megoldás hatékony idő szempontjából, de feltételez egyetlen nagyszámú kapcsolattal rendelkező robotot. A második megoldás meglehetősen lassú A harmadik

hasonlóképpen, ráadásul több erőforrást igényel mint a másik kettő. Ezen megoldások valamely kombinációja szükséges a probléma hatékony megközelítéséhez. Például: A következő ábrán egy aritmetikai problémát modellező probléma fát láthatunk az imént felsorolt alkotóelemekkel. Az aritmetikai kifejezés megoldására vagyunk kiváncsiak Az alkalmazott problémafa többé-kevésbé kiegyensúlyozott. 3. ábra Egy aritmetikai probléma lebontása bináris probléma fává 5.12 Modulok: részletes áttekintés A modulok a következő adatokat tartalmazzák: • Gyökérhez vezető fordított útvonal (modul lista) • Kezdeti lépések száma (lásd: 5.13) • Almodulok száma • Korlátozott mértékű lista tiltott robotokról • Élettartam • Műveletek és adatok 9 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 Példa egy probléma fára és modulok tulajdonságaira: Modul név A B C D E

F Kezdeti lépések 2 2 2 2 2 2 „Felmenő” lista - A A „Gyerekek száma” 2 2 1 0 0 0 20 20 20 20 20 20 AB AB AC Tiltott robotok Élettartam 1. Táblázat Egy modul megoldásához szükség van minden almodul eredményére. A következőkben a probléma fa topológiai gráffal való megfeleltetésének egy lehetséges módozatát mutatjuk be. Feltételezzük, hogy rendelkezésünkre áll a probléma fa, ellenben nem ismerjük a topológiai gráfot, vagyis a robotok elhelyezkedését és a közöttük levő kapcsolatokat. A leképezési mechanizmus dönti el, hogy melyik modul melyik robothoz kerül és milyen sorrendben. 10 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 5.13 Leképzési mechanizmus A modulok közül egyszer mindig a szülő kerül kiküldésre, amelyet követnek az almodulok, továbbá a kiküldés 1 kiindulópontként funkcionáló roboton keresztül történik. Legyen egy robot fittsége

függvénye az elérhető szomszédok számának. Egy modul szemszögéből egy robot elérhető, ha nincs benne a tiltott robotok listájában és vagy üres, vagy a szóban forgó modul valamely felmenőjét tartalmazza. Ha feltételezzük, hogy egy robot akkor is képes továbbadni egy modult, ha ő maga éppen foglalt, akkor az elérhetőséghez nem szükséges üresnek lennie. Megj: Üresség és foglaltság alatt azt értjük, hogy tartalmaz-e a robot pillanatnyilag modult vagy sem. Ebből az értelmezésből fakadóan a fittség csak a kérdéses robottól és modultól függ. Következésképpen a modulok mozgása helyileg, a robotok szintjén dől el, nem szükséges a központi vezérlés. A végtelen körjáratban való megrekedést elkerülendő, a látogatott robotok bekerülnek a tiltott robotok listájába. Egy robot akkor alkalmas befogadónak, ha elérhető szomszédainak száma legalább egyenlő a kérdéses modul leszármazottainak számával (a modul „gondol”

leszármazottaira is). Továbbá a fittség fordítottan arányos a két szám közötti különbséggel. Azért fordítottan, mert a rokon modulok erőforrás igénye ellenben nem ismert. A modulok „spórolnak” az erőforrásokkal. fittség = 1 / (robot szomszédainak száma - modul leszármazottainak száma) A modulok mindig a legfittebb robot irányába haladnak, mely vándorlásnak 2 fontos szakasza van: A kezdeti szakaszban a modul - normális körülmények között – a szülő útvonalát követi (mivel az is a legfittebb robotok vonalán haladt). Ennek az útvonalnak a hossza nagyobb vagy egyenlő a “kezdeti lépések” számával, rákényszerítve a modult adott számú kezdeti lépés megtételére, még akkor is, ha időközben megtalálja a szülő-modulját. Erre a kiinduló robot(ok) körüli torlódás csökkentése érdekében van szükség. Miután a modul megtalálta szülő-modulját (és túljutott a kezdeti lépéseken), elkezd szabad, robotot keresni. A

legelső ilyen robotban elhelyezkedik A modulok továbbküldése és/vagy befogadása a robotok döntése, de a folyamat általában a fent leírt módon történik. 11 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 Sajátos esetek vándorlás során: • A modul nem találja meg szülőjét. A keresés nyilván csak az élettartamnak megfelelő ideig tarthat, ezért amennyiben a modul túljutott élettartamának egy bizonyos részén (mondjuk felén) automatikusan átlép a vándorlás második fázisába és elhelyezkedik a legközelebbi üres helyen. • A modul nem talál üres robotot. Ilyen helyzetben a konkrét modul-vándorlási mechanizmus dönti el, hogy mi a tennivaló. A modul kerülhet egyszerűen törlésre (esetleg hibaüzenet küldése után), vagy alkalmazható komplex alternatív útvonalkereső algoritmus is. Esetleg vissza is lehet küldeni a kindulóponthoz Amennyiben a modulnak sikerül felmenőit követnie

vándorlása során, gyakorlatilag egy a „felmenő listával” megegyező útvonalat jár be. Ha minden egyes lépésnél kitöröljük az éppen meglátogatott robotot, a „felmenő lista” kiürülése jelzi, hogy a modul vándorlásának második szakaszába ért. Elhelyezkedés után a modul – amennyiben minden szükséges adattal rendelkezik – megoldásra kerül. Az eredmény üzenet formájában kerül vissza a szülő-modulhoz, mely visszajutást nagymértékben megkönnyíti, ha a modul előzőleg már megtalálta szülőjét, így ugyanis a tiltott robotok listája tartalmazza a szülőhöz vezető útvonalat. Ha a modul nem ismeri közvetlen felmenőjéhez az utat, Iterative Deepening Search (lásd: 5.) eljárást kér a robottól. Ez utóbbi siker hiányában egy a rendszer konkrét megvalósításától függő „kárelhárítást” hajt végre (Ugyanazt mint a zsákutcába jutott modulok esetében, vagy valami egyebet. Akár törölheti is a modult) Ha a modul

vegyes vagy komplex modul, vagyis önmagában nem rendelkezik minden szükséges adattal, leszármazottaitól várja azt. Hogy minden leszármazott eredményére szükség van-e vagy sem, az a konkrét probléma fa megépülésekor dől el. 12 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 4.2 Példa: Dolgozók megszámlálása 4. ábra A statikus modell és a lépések I-IV- ig A válaszhoz elég egy rekurzív jellegű modult használni. A „CNT” modul a következő utasításokat tartalmazza: Ha nincs szabad szomszéd, akkor téríts vissza 1-et Ha van szabad szomszéd, akkor téríts vissza 1 + (válasz az első szabad szomszédtól) + (válasz a második szabad szomszédtól) + . + (válasz az utolsó szabad szomszédtól) ahol a válasz ennek a modulnak a másolatából jön. Az első CNT modul az egyes számú dolgozóba kerül a királynőtől (vastagított fekete nyíl). Az első lépében az egyes dolgozó megpróbálja

végrehajtani a modul utasításait. Az azonban még nem rendelkezik minden szükséges adattal, tehát várakozás szükséges. A CNT egy-egy újonnan érkező másolata továbbmegy a kettes és hármas dolgozóknak („I” és nyíl). A második lépésben („II” és egy nyíl) a kettes és hármas dolgozókban megismétlődik az egyes lépésnél leírt folyamat. Mindkettőn áthalad a szükséges mennyiségű CNT modul a szabad szomszédok (4, 5, 6) irányába. Azért jutnak el idáig, mert az egyes, kettes és hármas dolgozók már foglaltak. A kettes dolgozótól a négyes és ötös dolgozóba jutnak a modulok, míg ezzel nagyjából egy időben a hármas dolgozó is elküldi az ötöshöz és hatoshoz. A hatos fogadja de az ötöst (mondjuk) már elfoglalta a kettes irányából érkező modul. A harmadik lépésben („III” és egy vékonyabb nyíl) a CNT modul már eljutott mindenhová, elkezdenek visszatérülni az eredmények. A négyes és ötös dolgozó a

ketteshez küld üzenetet, 13 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 a hatos pedig a saját szülőjéhez: a hármashoz. Az visszatérített szám eddig minden esetben 1 volt. A negyedik lépésben („IV” és egy vékonyabb nyíl) a kettes és hármas dolgozóban lévő modulok megkapták a gyerekeik által kiszámolt értékeket, és hozzáadva 1-et visszatérítik a saját szüleiknek eredményüket: A kettes 3-at, a hármas pedig 2-t. Hozzáadva 1-et fejenként a 2. visszatérít 3-at az 1-nek és a 3-as visszatérít 2-t ugyancsak az 1-nek Végül az 1. kap egy 3-at egyik gyerekétől míg 2-t a másiktól Hozzáadva saját magát jelentő 1-et visszatérít a királynőnek 6-ot. Az előző példa eléggé egyszerű a rendszer bemutatásához és jól is megy ha a dolgozók nem mozognak. Ez nem mindig az eset és az átirányítás itt jut szerephez A 6 ábrán látható a dinamikus modell ahol pont ez történik: az egyik

dolgozó kimozdul a kommunikációs távolságból a problémamegoldás közbe. 5. ábra A dinamikus model és a lépések I-V ig A dinamikus modell példája a 1.-5 dolgozók számára teljesen megegyezik a statikus modellével a különbség a második lépés után lép fel, amikor a 6. dolgozó kimozdul az eddigi kapcsolatokból. A visszatérítési értékét nem tudja egyből a 3 dolgozó moduljához juttatni Az 5. dolgozó segítségével jut el az üzenet a 3-hoz A probléma megoldása folytatódik, és a királynő megkapja a válaszát. Természetesen az üzenet az Iterative Deepening Search (41 rész) szabályai szerint jut el 6. tól 3 ig, egyedül a könnyebben magyarázhatóság kedvéért nem kezdtem kifejteni. 14 XI. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2008 május 23–24 Ha a „CNT” modul az adott dolgozó szomszédjai id-jét térítené vissza és nem 1-et akkor az egész topológiai gráfot meg lehetne ismerni teljes rálátás

nélkül. 6 Konklúzió és további munka A bemutatott rendszer a következő előnyökkel rendelkezik: • Bővíthetőség – az újonnan jött robotok helyi kölcsönhatásának köszönhetően könnyen beépülnek a bolyba • Parallelizáció – A rendszer jól alkalmazható eredendően jól párhuzamosítható problémák megoldására • Autonómia – Nincs szükség külső vezérlésre Ez a téma még egyáltalán nincs kimerítve, rengeteg kérdés és optimalizáció van hátra. Pár fontosabb kérdés: Mi történik, ha több királynő van a bolyban? Hogyan osztoznak meg az erőforrásokon? 7 Köszönetnyilvánítás Köszönet Dr. Mihai-Nicolae Olteannak és Dr Jákó Zoltánnak a véleményeikért és javaslataikért. 8 Referenciák [1]. E Bonabeau, M Dorigo, and G Théraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, 1999 [2] G. Di Caro and M Dorigo, "AntNet: a mobile agents approach to adaptive routing",

Tech Rep IRIDIA/97-12, Université Libre de Bruxelles, Belgium [3]. M Heusse, D Snyers, S Guérin, and P Kuntz, "Adaptive agent-driven routing and load balancing in communication network", Proc ANTS98, First International Workshop on Ant Colony Optimization, Brussels, Belgium, October 15-16, 1998 [4]. R Schoonderwoerd, OE Holland, J Bruten, L Rothkrantz, "Ant-based load balancing in telecommunications networks", HP Labs Technical Report, HPL-96-76, May 21, 1996. [5]. R Schoonderwoerd, OE Holland, JL Bruten, "Ant-like agents for load balancing in telecommunications networks", Proc First ACM International Conference on Autonomous Agents. [6]. Bellman, Richard Ernest, "Dynamic programming", PrincetonUniversity Press, 1957 [7] Stuart J. Russel and Peter Norvig "Artificial Intelligence, A Modern Approach, Second Edition" Prentice Hall Series in Artificial Intelligence, Prentice Hall 2003 [8] Swarm Intelligence for Routing in Communication

Networks I. Kassabalidis, MA El-Sharkawi, RJMarks II, P Arabshahi, AA Gray Dept. of Electrical Eng, Box 352500 University of Washington Seattle, WA 98195 USA Jet Propulsion Laboratory 4800 Oak Grove Drive, MS 238-343 Pasadena, CA 91109 USA [9]Satyabrata Chakrabarti and Amitabh Mishra, “QoS Issues in Ad Hoc Wireless Networks”, IEEE Communication Magazine, February 2001. 15