Mobil robotok szimulációja speci 2. óra

Bevezetés

• bõséges és sokféle irodalom, nehéz válogatni
• komoly eltérések a világról alkotott modellben
• különbségek: mi fontos a kutatónak a világból, dimenziók száma, fizikai törvények pontossága
• szenzorok száma, felbontása
• jóság: mennyire felel meg a valóságnak, ugyanakkor mennyire kezelhetõ a jelenkor tudományos módszereivel
• a módszerek egyfajta csoportosítása:

  idõ	állapottér	állapotátmenet
  diszkrét	diszkrét	determinisztikus
  folytonos	folytonos	sztochasztikus

• most olyan laboratóriumban készült eredményekrõl lesz szó, melyek az elmúlt 20 év eredményeit nem használják

Navigáció

• rengeteg lehetséges feladat, a közös a mozgás és a tájékozódás
• kitûntetett helyek felismerése (kiindulás, energiaforrás, feladatvégzés helye)
• a robot a környezet jeleit és saját memóriáját használja
  
• helyek közötti útvonalak ismerete
• topológikus és metrikus megközelítés
• metrikus: számszerû mérések összegzése, kincs rejtekhelyének térképe, koordináta-rendszer
  
• topológikus: helyek közötti relációk
  
• tengerészet: part mentén, running down the lattitudes, deducted reckoning
• kognitív térkép a fejlett élõlényeknél: képek, hangok, szagok, kapcsolatok, távolságok, színek, textúrák gyûjteménye

Mazebots

• oktatási célú, egyszerû környezet
• a feladat a különféle labirintusokban elhelyezett robot startból célba juttatása egy saját szabályozó programkód segítségével
• négyzetes alaprajzú, kétdimenziós tetszõleges labirintus, körökkel és zsákutcákkal

• népszerû feladat rágcsálókísérletekben
• utasítások: Go Forward, Go Backward, Turn Left, Turn Right
• szenzorok: FrontWall, LeftWall, RightWall, BackWall
• programkonstrukciók (if, while), Long integer változók és tömbök
• egy egyszerû program ezen a nyelven

  Main 
  |---Turn Right
  |---Call FwdUntilWall
  |---Turn Left
  |---Go Forward
  |---Turn Left
  |---Call FwdUntilWall
  |---Turn Right
  |---Call FwdUntilWall
  |---Call Main
  FwdUntilWall
  |---While( NoFrontWall )
  |---Do
  |---|---Go Forward

• bal-jobb szlalompályán jól mûködik, de máshol nem
• néhány száz sorban elkészíthetõ a falkövetés programja is
• teljes térkép felépítése is elképzelhetõ

Automata porszívó

• Ulrich, Mondada és Nicoud cikke komplex, valódi robottal
• alulról fölfelé építkezés, egyszerû módszerek, metrikus navigáció
• 30 cm x 30 cm-es Koala robot, Motorola 68331 processzorral 1MBájt RAM-mal 128 KBájt ROM-mal, három órára elegendõ akkuval

  

• A robot szerkezete
  • a forma nagyban meghatározza a takarítandó terep bejárhatóságát
  • a legtöbb esetben komplex mozgássorok szükségesek, ez befolyásolja az algoritmust és az energiaigényt
  • szívófej változatossága
  • négyzet vagy kör alakú robot, peremén a szívófejjel: akadályok körül vagy sarkokban nehézkes

    

  • önálló szívófej elõnyei, hátrányai:
    • mozgás és takarítás függetlenítése
    • energiamegtakarítás
    • a robot fixpont a kar mozgásakor a tájékozódásban
    • de külön vezérlés szükséges
  • külön energiaforrás kell a takarításhoz, kéziporszívó felszerelése a robotra

    

• Szenzorok
  • robot helymeghatározása és tárgyak felismerése
  • tapintásérzékelõk a szívófejen, viszonylag nagy sûrûségben, 54 darab 6 mm-enként
  • szükséges az érintkezés, de csak finoman (erõelosztó védõgyûrû)
  • iránytû a tájékozódáshoz
  • falak esetében a legkisebb és a legnagyobb szög eltárolása a késõbbiekre
  • porszenzor: meddig kell még az adott helyen takarítani
  • valószínûleg van távolságmérés is, a kerekek elfordulásának mérésével

    

• Tárgyfelismerés
  • a tárgyfelismerésre azért van szükség, hogy az ismeretek ne egyszerûen foglalt és üres mezõk egymásutánját jelentsék
  • ezen kívül az azonosított tárgyak természetes tájékozódási pontok
    • Láb - kör alakú, és 15 cm-nél kisebb átmérõjû
    • Fal - egyenes oldalvonal, akár könyvespolc vagy konyhaszekrény is lehet
    • Sarok - két fal konvex vagy konkáv találkozása
    • Azonosíthatatlan objektumok - minden egyéb
  • tárgyfelismerés takarítás közben: a robot helyben áll, a szívófej körbejárja a tárgyat és osztályozza, amit késõbb még javíthat
  • helyi bittérkép-reprezentáció
  • plusz információ a tárgyak távolságáról és méretérõl
  • csökkentlátók bottal való tájékozódásához hasonló
  • hipotézisek használata az egyszerûség érdekében: minden egyenes fal, amíg túlságosan nem görbül, minden 80 és 100 fok közötti sarok derékszögû
• Térképépítés
  • lényeges a terep és a már bejárt részek ismerete, a pontos hely másodrendû
  • két lépéses megoldás: a körvonal bejárása, a belsõ lefedése
  • így csak a kezdõpontot kell felismerni, és eltévedéskor az oldalfalhoz vissza lehet térni tájékozódni
  • az adatok bittérképen tárolódnak: nem kell komplex alakzatokat poligonként tárolni, fej lokális adatai könnyen beilleszthetõk
  • a térkép pontjai a következõket tartalmazhatják:

    Érték	Osztály
    0	ismeretlen
    1	üres, takarítva
    2	üres, nem takarítva
    3	fal
    4	konkáv sarok
    5	konvex sarok
    6	láb
    7	azonosíthatatlan objektum

  • egy-egy pont 2 négyzetcentiméter, így 100 négyzetméter csak 250 KBájt
  • tárgyak keresésének gyorsítása listareprezentációval
  • a körvonal bejárásakor a megtett utak vektoriális összege nulla, ami a kezdõpont felismerését segíti (kétszeri mérés, nagyobb biztonság)
• A takarítás folyamata
  • körbejárás, majd szoba belsejének bejárása
  • legrövidebb útkeresés nem hatékony a nem ismert akadályok miatt
  • viszont fontos szempont a pozíció becslésének újrahangolása
  • egyenes vonalú mozgás falig, ekkor újrahangolható az irányzék és az egyik koordináta
  • ezután következõ merõleges falnál az irányzék és a másik koordináta
  • saroknál mindhárom paraméter hangolható
  • a navigáció irányát pedig a robot a nem takarított pixelek számának irányonkénti összegébõl határozza meg

    

• Eredmények
  • 2-3 négyzetméteres helyiség 90%-os kitakarítása, térképépítéssel és 95%-os bejárással, 12 perc alatt
  • látványos eredmény, de kereskedelmi forgalomba még nem való
  • a térkép igazából egy üres helyiséget mutat, egy valós szoba ennél sokkal összetettebb
  • érzékelt tárgyak nagy része az azonosítatlan kategóriába kerülne
  • problémás tárgyak: állólámpa, szõnyeg, alacsony szék, padlóváza
  • külön térkép kellene a robotnak és a karnak
  • a 90%-os teljesítmény valószínûleg pont a problémás részeket hagyja ki

Navigálás nézet gráffal

• Franz, Schölkopf, Mallot és Bülthoff cikke
• A feladat
  • tisztán topológiai megközelítés a kognitív térkép elkészítéséhez vizuális információk alapján
  • a rendszer autonóm módon felméri környezetét mesterséges tereptárgyak nélkül
  • a robot a lokális képekbõl és térbeli relációkból nézetgráfot készít
  • korábban labirintusban a nézetgráf alapján már tudott navigálni a robot (diszkrét állapottér, illetve állapottér diszkrétizáció)
  • ez egy új kísérlet nyílt terepen
• A környezet
  • körülbelül 1m x 1m-es vízszintes terület, modellházakkal

    

  • Khepera robot a tetején kamerával, mely egy kúp alakú tükörre néz, így teljes 360 fokos kép látható 10-10 fokos vertikális látószögben

    

• • a keletkezõ képbõl szûrés után kivonják az állandó hátteret, hisztogram kiegyenlítéssel kiemelik a kontrasztot
  • szimulációs környezetben hasonló világ sugárkövetéses technikával elõállítva
• A folytonos tér diszkrét reprezentációja
  • sajnos a nézetek nem biztos, hogy egyediek, ezért a környezet segíthet a döntésben, szomszédos képek felhasználásakor
  • a robot irányítására alkalmazható vizuális információ: a térbõl folytonos leképezés létezik a lehetséges nézetek terébe
  • véges számítási kapacitás: nem lehet minden képet eltárolni
  • az útvonalak szempontjából lényeges képek tárolása és gráfként összekapcsolása
  • a korábbi labirintusos kísérletben a térdiszkretizáció egyszerû volt: a labirintus csomópontjaiban kellett a képeket eltárolni
• Nézetek közötti navigáció
  • miként lehet egy helyet felismerni?
  • ha a hely jól megkülönböztethetõ távolról, akkor a helyrõl készített kép megfelelõ
  • ha a hely nem különleges, akkor az onnan a környezetrõl készített képet kell felhasználni
  • vagyis a képen lévõ tereptárgyak használata azonosításképpen
  • a kép létrehozásából adódóan a haladási irányban a tárgyak távolodnak, az ellentétes irányban közelednek

    

  • a kép és a valóság közötti legnagyobb egyezés keresése biológiailag is megalapozott (például méhek, hangyák)
  • bizonyítható, hogy a cél tetszõleges pontossággal megközelíthetõ ezzel a módszerrel (zajfüggés)
  • a kísérletekben 15 cm-rõl 95 %-os valószínûséggel, 25 cm-rõl már csak 50 %-os valószínûséggel talált vissza a robot egy korábbi képhez
• Képek begyûjtése
  • a 360 fokban készülõ képek egydimenziósak, szürkefokozatosak, és mindössze 78 képpontból állnak
  • az egyszerûség ellenére ez a megoldás jól használható
    az elõnyök
    • valós idejû feldolgozás
    • a távolódó tereptárgyak nem tûnnek el a horizonton, csak takaráskor
    • az elforgatásból és eltolásból adódó minimális eltérés könnyen kiszûrhetõ
    • robusztus képérzékelés, a kép egy kis részének megváltozása nem olyan súlyos probléma (például mozgó ember)
    • a helyek képének eltárolásához elég egy nézetet készíteni, nincs szükség több részleges kép integrálására
  • a képek használata
    a megfelelõ navigációhoz az alábbi feltételek teljesülése szükséges
    • a képeknek megkülönböztethetõeknek kell lenniük
    • kevés képpel is a terep nagy részét le kell tudni fedni
    • a szomszédos képek térbeli távolságának elég kicsinek kell lenni ahhoz, hogy egyikbõl a másikba megbízhatóan el lehessen jutni
  • a hasonlóság mérése egy osztályozási probléma: a küszöböt úgy kell megállapítani, hogy se túl sok, se túl kevés kép ne keletkezzen

    

  • ehhez a kutatók teszt futattáskor sok képet készítenek, melyek között a távolságot és az átjárhatóságot mérik, így állapítják meg a küszöb értékét
  • ezzel a módszerrel nagyjából 25-40 kép különböztethetõ meg

    

• A nézet gráf létrehozása
  • az elõbbi két mechanizmus az alapvetõ építõkövei a teljes eljárásnak

    

  • a gráf csúcspontjaiban nézetek vannak, az élek a robot számára megtehetõ útvonalakat jelentik
  • útvonalkészítés: a robot halad és ha a látott kép komolyan eltér a csúcspontokban tároltaktól, akkor új csúcsot készít
  • így a gráf fedése függ a terep változásától: változékonyabb terep, sûrûbb csúcsok, homogén terep, ritkább csúcsok
  • a láncszerû gráf elkerülésére egy bizonyos távolság megtétele után mindenképp új él keletkezik: ha a kép nem tér el a korábbiaktól lényegesen, akkor a hasonlóság alapján egy korábbi csúcsot kapcsol össze a megelõzõvel
  • ha a robot eltéved új gráf kezdõdik, ami jó esetben majd a korábbihoz kapcsolódik
  • ezzel a módszerrel metszõ élek sem nagyon keletkeznek
  • lokális felfedezési stratégiák
    • ahhoz, hogy a gráf jól fedje a terepet a felfedezés új irányát úgy kell megválasztani, hogy az a legtöbb információszerzéssel járjon
    • véletlen irányválasztás, Brown mozgás
    • keresés a legnagyobb felfedezetlen terület irányába
    • csúcshoz tartozó élek számának, élek szögének limitálása
    • hibás élkeresések megjegyzése (például ütközéskor)
    • tárgyakhoz közeli képkészítés letiltása a töredezettség csökkentése érdekében

      

  • ábrák a készülõ gráfokról

    

    

  • összefüggés a topológikus és a metrikus navigáció között
  • hátrány, hogy a nem egyértelmû képek miatt csak kis terepen alkalmazható
  • kombinálva metrikus módszerekkel nagyon eredményes lehet