Robotų grupės ir spiečiai (PDF)

Robotų grupės ir spiečiai (Multirobotų sistemos)  2 Turinys Multirobotai: apibrėžimai ir pavyzdžiai Spiečių robotika Robotų grupių struktūra Multirobotų elgsena ir valdymas Robotų grupių valdymo algoritmai 3 Multirobotai (angl....

Robotų grupės ir spiečiai (Multirobotų sistemos)  2 Turinys Multirobotai: apibrėžimai ir pavyzdžiai Spiečių robotika Robotų grupių struktūra Multirobotų elgsena ir valdymas Robotų grupių valdymo algoritmai 3 Multirobotai (angl. multi-robots) Robotų sistema sudaryta iš daugiau nei vieno bendraujančio (bendradarbiaujančio) roboto Robotų grupė, kurioje robotai gali dalintis savo resursais, kad išspręstų sudėtingas problemas Multi-agentinė sistema, kurioje kiekvienas agentas yra realus (fizinis) robotas Apibrėžimai Sinonimai: Bendradarbiaujantys robotai (collaborating robots) Robotų bendruomenės, komandos (robot teams) Robotų kolektyvai (robot collectives) Robotų klasteriai (robotic clusters) Robotų spiečiai (robot swarms)  Spiečių robotika Robotikos šaka, tirianti didelių grupių vienodų (dažniausiai paprastų) robotų elgsenos koordinavimą naudojant lokalias elgesio taisykles tirianti metodus, kurių pagalba pasiekiamas kolektyvinis didelės grupės robotų elgesys, jei žinomos tik atskiro roboto sąveikos su kitais robotais ir aplinka taisyklės Robotų grupės (spiečiai) Robotų spiečius - multirobotų sistemų sistema, susidedanti iš daugybės nesudėtingų robotų Kai robotai sąveikauja tarpusavyje ir su aplinka, atsiranda kolektyvinė elgsena Paprastos kiekvieno roboto elgesio taisyklės apibrėžia sudėtingą kolektyvinį elgesį Pagrindinis reikalavimas - nuolatinis bendravimas ir grįžtamasis ryšys Savybės: pigumas, paprastumas, mažas dydis 5  Robotų klasteris Robotų grupė, kurie gali dalintis savo resursais kad galėtų spręsti sudėtingas problemas Gali būti taikomi kompiuterių klasterių sudarymo ir valdymo metodai Robotai vykdo savo užduotis, o laisvus skaičiavimo resursus (pvz., prastovos metu) gali atiduoti grupės užduotims spręsti Šaltinis: A. Marjovi, S. Choobdarb, L. Marquesa. Robotic clusters: Multi-robot systems as computer clusters 6 A topological map merging demonstration  Pavyzdys: Vaizdo įrašas 7 https://www.youtube.com/watch?v=TYaquGrGhfk  Pavyzdys 2 Kilobot project (Harvard univ., JAV) Pigūs robotai skirti kolektyvinei robotų elgsenai demonstruoti Robotų spiečius http://www.youtube.com/watch?v=CJOubyiITsE https://www.youtube.com/watch?v=xK54Bu9HFRw http://www.youtube.com/watch?v=qBUFX41e1mc  Kam reikia robotų grupių? Multi-robotų sistemos: Užtikrina aukštą patikimumą (dėl pertekliškumo) Leidžia atlikti užduotis pigiau arba greičiau nei naudojant vieną sudėtingą robotą Kai kurioms užduotims atlikti reikalingos robotų komandos Kai kurias užduotis lengviau ir efektyviau spręsti pasidalinant darbą 10 Multirobotų sistemų sistemų taikymas 12  Homogeninė: Visi robotai yra tokie patys (aparatūra ir valdymo programinė įranga) Multirobotų Esant toms pačioms sąlygoms (įėjimams) visų robotų sistemos darbo rezultatai (išėjimas) sutampa Patikimumas: Sugedus vienam robotui, jį lengvai gali struktūra pakeisti bet kuris kitas bendruomenės narys Adaptyvumas menkas, nes robotai nesiskiria Rezultato pasiekimą užtikrina elementarių veiksmų kartojimas Heterogeninė:  Robotų aparatūrinė platforma arba valdymo programa skiriasi 14 Robotų bendravimas (komunikavimas) grupėje Tiesioginis bendravimas: (a) Naudoja centralizuotą („Master-Slave“) architektūrą, arba (b) Naudojamas tiesioginio ryšio kanalas Lengva įgyvendinti Leidžia efektyviai keistis informacija Robotai koordinuoja sprendimų priėmimo ir veiksmų planavimo procesus  Trūkumas: Priklauso nuo trikdžių ir aparatūros gedimo Robotų bendravimas (komunikavimas) grupėje Pasyvus (netiesioginis) bendradarbiavimas: Robotai nebendrauja tarpusavyje, kai bando kartu išspręsti užduotį Robotai per jutiklius gauna informaciją apie vienas kito buvimo vietą Pavyzdys: robotai reaguoja į kitus robotus kaip kliūtis aplinkoje Sprendimų priėmimas ir veiksmų planavimas vyksta vietoje, rezultatai nesidalijami 16  Centralizuotas valdymas: Sistema turi robotą (lyderį), kuris vadovauja organizuojant kitų robotų darbą Lyderis priima sprendimus, kiti grupės nariai juos įgyvendina Robotų grupių Centralizuota architektūra koordinuoja visą grupę iš vieno valdymo centro elgsenos Stiprus ir silpnas centralizavimas koordinavimas Paskirstytas valdymas: (valdymas) Decentralizuota valdymo architektūra robotai imasi veiksmų, pagrįstų tik lokaliomis žiniomis, atitinkančiomis jų situaciją robotai yra visiškai nepriklausomi vienas nuo kito: nėra lyderio Hibridinis:Hibridinis valdymas: Derinamas centralizuotas ir paskirstytas valdymas Lokalus / globalus robotų grupės valdymas Globalus valdymas Leidžia realizuoti sudėtingesnį komandos bendradarbiavimą Didesnė ryšio kanalo apkrova Globalios žinios: Žino ką daro kiti robotai Žino ką darys kiti robotai Lokalus / globalus robotų grupės valdymas Lokalus valdymas Paprasti, nesudėtingi skaičiavimai Gerai tinka dinaminėms aplinkoms Neoptimalus valdymas, priklauso nuo jutiklių Lokalios žinios: Žino ką daro ir darys pats Nežino ką daro ir darys kiti robotai grupėje Multirobotų sistemos organizacijos tipai Hierarchija (c) Koalicija (e) Komanda (b) Rinka (a)... 21  Hierarchija Robotai yra suskirstyti į medžio tipo struktūrą Aukščiau hierarchijoje esantys robotai turi daugiau informacijos Bendravimas vyksta tik tarp tiesiogiai sujungtų robotai Žemesnio lygio robotai renka informaciją Aukštesnio lygio robotai kontroliuoja žemesnio lygio robotus Koalicija: tam tikras robotų grupės poaibis 22  Koalicija Koalicija formuojama atsižvelgiant į tikslus ir egzistuoja tol, kol pasiekiami tie tikslai Koalicijos viduje organizacijos nėra, nors koalicija gali turėti lyderį, kuris valdo ir atstovauja koalicijos narius Galimos “persidengiančios koalicijos”, jei koalicijų tikslai persidengia. Tuomet robotai gali koordinuoti veiksmus Tarp skirtingų koalicijų bendravimas (koordinavimas) yra minimalus 23 Komanda Komandą sudaro robotai siekiantys bendro tikslo Skiriasi nuo koalicijos, nes koalicijos nariai siekia savo atskirų tikslų, kurie tik iš dalies sutampa Robotai turi koordinuoti savo veiksmus Robotai prisiima roles leidžiančias siekti bendro komandos tikslo Rolės gali keistis reaguojant į aplinkos pasikeitimus, įvykius, o komandos tikslas išlieka pastovus 20  Rinka Susideda iš dviejų tipų narių Pirkėjai („balti“) varžosi dėl išteklių, užduočių Pardavėjai („juodi“) siūlo užduotis ir renka nugalėtojus Toks modelis sukuria gamintojo-vartotojo tipo sistemą Panaši į federaciją, nes lyderiai koordinuoja kitų narių veiklą  Skiriasi nuo federacijos tuo, kad nariai konkuruoja tarpusavyje Panaši į bendruomenę, nes nariai gali dalyvauti, kol laikosi nurodytų taisyklių Robotų grupės organizacijos formų palyginimas Forma Charakteristika Pranašumai Trūkumai Hierarchija Problemos Gerai tinka daugeliui Potencialiai nestabili dekompozicija problemų spręsti Dinaminė, Išnaudoja robotų skaičių Koalicija orientuota į Trumpalaikė nauda gali būti tikslą mažesnė už koalicijos sudarymo kaštus Komanda Grupiniai ryšiai Tinka didesnėms Didelė ryšio infrastruktūros apkrova problemoms spręsti 26 Rinka Konkurencija Gerai tinka efektyviam Neapsaugota nuo kenkėjiškos elgse resursų paskirstymui  Kolektyvinis robotų judėjimas Problema – koordinuoti robotų grupę ir judėti kartu išlaikant grupės struktūrą Tvarkos palaikymas (Maintenance): kaip judėti spiečiuje palaikant tvarką Pasidalinimas (Partition): aptikus kliūtį, kaip spiečiui pasidalinti į mažesnius spiečius, kad būtų galima apeiti kliūtį Susijungimas (Unification): Kaip daugeliui spiečių susijungti į vieną spiečių Pabėgimas (Escape): daliai robotų papuolus į aklavietę, kaip jiems pabėgti iš aklavietės 28  Boids modelis robotų speičių valdymui Naudojamas greitai judančių robotų grupių (dronų spiečiams) valdyti Kiekvienas robotas turi kreipti dėmesį tik į savo artimiausius kaimynus ir gali nekreipti dėmesio į likusio spiečiaus elgesį. Paprastos taisyklės, kaip „venkite atsitrenkti į kliūtis“, suformuoja grupės elgesį. Robotai yra valdomi trimis paprastomis taisyklėmis: 1. Atsiskyrimas - vengti susidūrimo su kaimynais 2. Derinimas – judėti vidutine kaimynų judėjimo krypty 3. Sanglauda - judėti į vidutinę kaimynų padėtį 30 Atsiskyrimas (separation) 32  25 Derinimas (alignment) 33 Sanglauda (cohesion) 34 35 Demonstracija Roboto judėjimo kryptis ir greitis (vektorius) yra atskyrimo, derinimo ir sanglaudos vektorių svorinė suma 36  https://eater.net/boids 38  Paprasčiausias susibūrimo (aggregation) algoritmas If robot is outside aggregation distance turn toward aggregation centroid and go. Else stop. 40 gr – stūmos funkcija ga – traukos funkcija Susibūrimas (aggregation) 31 42  while { while (robots) { theta = robots[index]; // angle r = robots[index]; // distance Judėjimo F = G / (r * r); // Gravity force law if (F > F_MAX) F = F_MAX; spiečiumi // Break into x and y components fx = F * cos(theta); algoritmas fy = F * sin(theta); sum_fx += fx; sum_fy += fy; naudojant } virtualios // Compute new velocity delta_vx = delta_T*sum_fx; traukos lauką delta_vy = delta_T*sum_fy; vx = vx + delta_vx; vy = vy + delta_vy; delta_x = delta_T*vx; delta_y = delta_T*vy; } Išsiskirstymas Tikslas – padengti kuo didesnę teritoriją neprarandant tarpusavio ryšio Spiečius gali būti naudojamas teritorijos tyrimui, veikti kaip paskirstytas jutiklių tinklas aplinkos stebėjimui Susijęs su teritorijos padengimo problema Naudojami metodai: biologiniai, elgsenos (pvz., Behavioral State Machines), virtualios fizikos (elektros krūvių, gravitacinių jėgų, spyruoklių, potencialų lauko modeliai) Struktūros suformavimas Tikslas – robotams užimti tokią padėtį erdvėje, kad jie sudarytų tvarkingą (atsikartojančią) struktūrą. Robotai turi išlaikyti tam tikrą atstumą iki kitų robotų Gali būti naudojamas tikimybinių baigtinių automatų metodas Robotas juda aplinkoje ir suradęs kitus robotus nusprendžia, ar prisijungti priklausomai nuo tikimybinės funkcijos reikšmės Neuroninių tinklų metodas Apmokytas tinklas optimaliai apjungia robotus į struktūrą Grandinės suformavimas Robotai turi sudaryti grandinę, jungiančią du taškus erdvėje Naudojami metodai Virtualia fizika grįstas metodas Gradinės formavimas naudojant feromonų metodą 36 Multi-robotų pavyzdys: robotų futbolas Naudojamas daugelio robotų sistemoms testuoti Dinamiška, sudėtinga aplinka Reikalingas atsakas realiame laike ◼ Daug skirtingų elgsenų: ❑ Perimti kamuolį, Varytis kamuolį, Smūgiuoti į vartus, Ginti teritoriją, Atmušti kamuolį Problemos Robotų jutikliai riboti Informacijos apdorojimas turi būti atliekamas realiu laiku (>15 fps) Nėra visos informacijos apie aplinką Aktualus rungtyniavimas: neteisingas sprendimas nutolina nuo tikslo, nes kita komanda gali perimti kamuolį ir įmušti įvartį.  Robotų rolės Vartininkas Gynėjai – Pasyvus: robotas, esantis linijoje tarp kamuolio ir vartų – Palaikantis: robotas, kuris bando numatyti būsimą perdavimą ir perimti kamuolį – Aktyvus: artimiausias kamuoliui robotas, kurio tikslas yra atimti kamuolį iš priešininko komandos žaidėjo Puolėjas – Pirminis: robotas, varantis kamuolį – Antrinis: bando užimti padėtį, kur gali riedėti nesėkmingai perduotas arba smūgiuotas į vartus kamuolys – Palaikantis: ruošiasi varyti kamuolį, kurį gali pamesti pirminis puolėjas 38 Rolės priskyrimas ◼ Rolių priskyrimui gali būti naudojami neraiškiosios logikos elementai ◼ Savo lauko pusės viduryje esančiam žaidėjui gali būti priskirta palaikančio gynėjo rolė su tikimybe 0.4 ir palaikančio puolėjo rolė su tikimybe 0.6 ◼ Žaidėjo veiksmai priklauso nuo priskirtų rolių apjungtos elgsenos  39 Vartininko rolė Važiuoti apskrita trajektorija prie vartų  Visada būti atsisukusiam į kamuolį ◼ Sekti kamuolio trajektoriją ir prognozuoti jo padėtį ateityje ◼ Nuspirti kamuolį tolyn, kai tik jis priartėja pakankamai Žaidimo etapai ◼ Puolimas ❑ Kamuolio užvaldymas ◼ Jei nei vienas robotas neperduoda pranešimo „Turiu kamuolį“, laikoma, kad komanda kamuolį prarado ❑ Žaidimo plėtojimas ◼ Maksimizuoti žaidimo metrikos reikšmes ◼ Metrikos pvz.: kamuolio atstumas iki priešininko vartų ❑ Puolimas ir smūgis į vartus ◼ Bandyti perimti priešininko komandos roboto priekyje esantį kamuolį ◼ Perėmus kamuolį pradėti važiuoti link tikslo  (priešininko komandos vartų) ◼ Nuolat tikrinti ar kamuolys vis dar yra kontroliuojamas ◼ Priartėjus prie vartų, spirti kamuolį į vartus 41 Žaidimo metrikos ◼ Jei žaidimo strategija yra agresyvus puolimas ❑ Laiko dalis, kai kamuolys yra priešininko komandos pusėje turi būti maksimali ◼ Jei žaidimo strategija yra agresyvi gynyba ❑ Laiko dalis, kai kamuolys yra nuosavos komandos pusėje turi būti minimali ◼ Jei žaidimo strategija yra rezultato išlaikymas ❑ Laiko dalis, kai kamuolys yra nuosavos komandos pusėje turi būti mažesnė, nei laiko dalis, kai kamuolys yra priešininko komandos pusėje ◼ Aikštelės užimtumo metrika ❑ Žaidimo laukas padalinamas į laukelius ❑ Kai laukelis užimtas, laukelio reikšmė yra +2 (savo žaidėjui) arba -2 (priešininko žaidėjui) ❑ Jei laukelis tuščias, reikšmė 0. ❑ Skaičiuojamas laukelių reikšmių vidurkis per varžybų laiką P ◼ Kitos metrikos: E= own − Popp ❑ Entropija – tikimybė perimti kamuolį P 42 Valdymo struktūra ◼ Decentralizuoti autonominiai komunikuojantys robotai Taktika ◼ Naudojamas tikimybinis baigtinis automatas Pavyzdinė problema: kamuolio sekimas Problema: Raskite kamuolį aplinkoje Važiuoti link jo Sustoti prie kamuolio Elgesio pasirinkimas: Naudoti neuroninį tinklą Fitness funkcija: fitness = initDist - b_distance(); jei (fitness