Robotika 4. Lokalizáció Magyar Attila Pannon Egyetem Műszaki Informatikai Kar Villamosmérnöki és Információs Rendszerek Tanszék
[email protected]
2011. szeptember 23.
4. Lokalizáció
Robotika
2
4. Tartalom
1. 2. 3. 4. 5. 6.
Bevezetés Zaj és alias Lokalizáció alapú vs. programozott navigáció Pozícióbecslés Térkép Lokalizáció
Robotika
3
4.1. Bevezetés
•
Sikeres navigáció – – – –
•
Észlelés Lokalizáció Tervezés Mozgásirányítás
Általános struktúra
Robotika
4
4.2. Zaj és alias
•
Pontos pozíciómérés esetén a lokalizáció egyszerű… –
• • •
… de pontos pozíciómérés nincs
Komoly kihívás Abszolút vs. relatív pozíció Szenzorok és beavatkozók fontos szerepet játszanak –
Egyik sem tökéletes
Robotika
5
4.2. Zaj és alias
•
Szenzorok alapvető fontosságúak (érzékelés) –
•
Szenzorzaj – – –
•
Zajjal terheltek Csökkenti a mérésből származó információ mennyiségét Nem modellezett környezeti hatás (pl. megvilágítottság mértéke CCD-nél) Interferencia (UH szenzor)
Alias – – – –
Emberi érzékelés a különböző bemeneteket meg tudja különböztetni Robot nem képes rá -> alias jelenség Kis zaj mellett is jelen van Kiküszöbölhető, ha több egymás utáni mérést figyelünk
Robotika
6
4.2. Zaj és alias
• •
A szenzorokhoz hasonlóan a beavatkozók sem tökéletesek Beavatkozó zaj –
•
Valójában mindig a környezet hiányos modellezéséből származik
Odometria, dead reckoning – –
A pozíció proprioceptív szenzoradatokból Hibaforrások • • •
–
Hibák három csoportja • • •
–
Kerékcsúszás Talaj lejtése Kerékátmérő Távolság hiba Fordulási hiba Drift hiba
Hosszútávon a fordulási és a drift hibák gyorsabban növekednek Robotika
7
4.2. Odometriai hibák • •
Differenciális hajtású robot pozíciója p = (x, y, θ) ∆t (mintavételi) idő alatt megtett út (∆x, ∆y, ∆θ) – –
•
∆sr, ∆sl - jobb,bal kerék által megtett út (mérhető/számolható) b – kerekek közti távolság
Frissített pozíció
∆x = ∆s ⋅ cos(θ + ∆θ / 2) ∆y = ∆s ⋅ sin(θ + ∆θ / 2) ∆θ = ( ∆sr − ∆sl ) / b ∆s = ( ∆sr + ∆sl ) / 2
∆s −∆s ∆s +∆s x′ x ∆s ⋅ cos(θ + ∆θ / 2) x r 2 l ⋅ cos(θ + r2b l ) p′ = y′ = y + ∆s ⋅ sin(θ + ∆θ / 2) = y + ∆sr 2−∆sl ⋅ sin(θ + ∆sr2b+∆sl ) = f(x,y, θ, ∆sr , ∆sl ) ∆sr −∆sl θ′ θ θ ∆θ b
Robotika
8
4.2. Odometriai hibák terjedése •
Kovariancia mátrix rekurzív számítása Σp' = ∇p f ⋅ Σp ⋅ ∇p f T + ∇ ∆rl f ⋅ Σ ∆ ⋅ ∇ ∆rl f T
– – –
Σ∆ = cov(∆sr,∆sl), a mozgásinkrementum kovariancia mátrixa Σp = kiindulási pozíció kovariancia mátrixa Σp’ = aktuális pozíció kovariancia mátrixa
Robotika
9
4.3. Lokalizáció alapú vs. programozott navigáció •
Nem a lokalizáció az egyetlen járható út
•
A -> B – –
Térkép építés, lokalizáció, útvonal tervezés Viselkedés alapú megoldás: bal oldali fal követése, leállási feltétel
Robotika
10
4.3. Lokalizáció alapú vs. programozott navigáció •
Viselkedés alapú navigáció + – – –
•
Könnyen implementálható Nem skálázható (nagyobb környezetre) Az elemi procedúrákat alaposan meg kell tervezni Egy időben több aktív viselkedési elem
Térkép alapú navigáció + + + –
A robot térkép-alapú tudása átlátható A térkép egy kommunikációs csatorna A robot által készített térkép az emberek által is használható Mi van, ha rossz a térkép? Robotika
11
4.4. Pozíció •
•
A különböző térkép alapú lokalizációs rendszerek az alkalmazott reprezentációban különböznek Térkép –
•
A robot környezetéről alkotott modell
Pozícióbecslés – – –
Hol vagyok a térképen? Egy lehetséges pozíció Több lehetséges pozíció? Robotika
12
4.4. Pozícióbecslés •
Egy hipotézises pozícióbecslés – – –
Legelterjedtebb Feltételezett pozíció: egy pont a térképen Egyértelmű • •
–
Egyszerű útvonaltervezés Egyszerű pozíciófrissítés
Szenzor és beavatkozó zaja bizonytalanságot okoz •
Egy hipotézis nem írja le megfelelően a pozíciót
Robotika
13
4.4. Pozícióbecslés •
Több hipotézises pozícióbecslés –
Feltételezett pozíció: több lehetséges pont a térképen (ponthalmaz) Rendezés a lehetséges pontok között
– • •
– –
Térképpontonként egy valószínűségi sűrűségfüggvény (folytonos) Diszkrét térképcellák + valószínűség (egyenként frissíthető)
Kezeli a zaj okozta bizonytalanságot Nehéz az útvonaltervezés
Robotika
14
4.5. Térkép • •
A pozícióbecslés duálisa Alapvető összefüggések 1. A térkép felbontása függ a végrehajtandó feladat pontosságától 2. A térkép felbontása és a térkép által reprezentált jellemzők függnek a szenzorok pontosságától, és az általuk szolgáltatott adatok jellegétől 3. A térkép felbontása határozza meg a térképépítéssel, lokalizációval, és navigációval kapcsolatos számítási feladatok bonyolultságát
•
Térképépítés szenzorai – –
Távolságmérés (lézer/ultrahang) CCD/CMOS látórendszer Robotika
15
4.5. Folytonos térkép •
Pontos leírás –
•
Nagyon memóriaigényes
Általában kombinált megoldás – – –
Folytonos reprezentáció Zárt világ feltételezése: Minden objektum szerepel a térképen – ami nincs a térképen, az nem létezik. A térkép (memóriabeli) mérete arányos az objektumsűrűséggel – ritka környezet = kis memóriaigényű térkép
Robotika
16
4.5. Folytonos térkép - példa •
Folytonos térkép – –
Akadályok reprezentálása sokszögekkel Sokszögek csúcsait elég ismerni
Robotika
17
4.5. Folytonos térkép - példa •
Szenzor – –
•
Lézeres távolságmérés Távolságadatokból egyenesek kiemelése
Folytonos térkép –
Térkép leírása egyenesekkel y=mx+b
Robotika
18
4.5. Diszkretizált térkép •
0 0 0 0 1 2 2 2 2 0 0 0 0 1 2 2 2 2 2 0 0 Foglaltsági háló alapú térkép (fix dekompozíció) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0– 0 Pontos 0 0 0 0 0(kis 0 rácsméret) 0 0 0 0 memóriaigényes 0 0 0 0 0 0 0 2 térkép 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 – Mátrix reprezentáció 0 0 0 0 0 0 0 2 2 2 2 2 2 2 0 0 0 0 0 0 – 0 – üres, 1,2,3,… - foglalt (növekvő valószínűséggel) 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 világ feltételezés itt nem használható 0– 0 Zárt 0 0 0 0 0 2 2 2 2 2 2 2 0 0 0 0 0 0 – Adaptív rácsmérettel pontosabban leírható objektumok 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 Robotika
19
4.5. Topologikus térkép • •
Nem direkt méréseken alapul Gráf reprezentáció – – –
•
Csomópontok: helyszínek Nem azonos méretű helyszínek Élek: átjárhatóság
Sikeres navigáció kulcsa – –
Aktuális pozíció megfelelő leképezése a csomópontokra Élek megfelelő leképezése a robot mozgására
Robotika
20
4.6. Lokalizáció • • •
Térkép alapú lokalizáció – pozíció meghatározása Valószínségi sűrűségfüggvények Két lépésben történik 1. Akció: ot proprioceptív mérések és a korábbi st-1 becsült pozíció s′t = Act(ot ,st −1 )
2. Mérés: it exteroceptív mérések és az 1. pontban számolt s’t pozíció st = Meas(it ,s′t )
•
Két módszer: – –
Markov lokalizáció… Kalman szűrő… Robotika
21
4. Kvíz 1. Milyen típusú szenzorok adatait használjuk pozíció becslésére az odometria feladata során? A. B. C.
Exteroceptív Proprioceptív Mindkettő
2. Melyik pozícióbecslés szolgál(hat) statisztikai információval is a robot pozíciójáról? A. B.
Egy hipotézises pozícióbecslés Több hipotézises pozícióbecslés
3. A zárt világ feltételezés lényege, hogy… A. B. C.
… a térképet nem lehet kibővíteni. …ami nincs a térképen, arról feltételezzük, hogy nem létezik. …a kevés objektumot tartalmazó térképrészlet kis memóriát foglaljon.. Robotika
22
4. Kvíz - megoldások 1. Milyen típusú szenzorok adatait használjuk pozíció becslésére az odometria feladata során? A. B. C.
Exteroceptív Proprioceptív Mindkettő
2. Melyik pozícióbecslés szolgál(hat) statisztikai információval is a robot pozíciójáról? A. B.
Egy hipotézises pozícióbecslés Több hipotézises pozícióbecslés
3. A zárt világ feltételezés lényege, hogy… A. B. C.
… a térképet nem lehet kibővíteni. …ami nincs a térképen, arról feltételezzük, hogy nem létezik. …a kevés objektumot tartalmazó térképrészlet kis memóriát foglaljon.. Robotika
23
