Robotika Helymeghatározás
Helymeghatározás Helyi helymeghatározás • Feltételezzük, hogy a robot helyzete egy szűk területen belül adott Globális helymeghatározás • A globális megközelítés hatékonyabb, mert a kiindulási hely ismerete nélkül tudják meghatározni a robot helyzetét. • Az „eltévedt robot” probléma: a robotnak képesnek kell lennie saját helyének meghatározására, akkor is ha egy külső erő ismeretlen helyre vitte.
Helymeghatározás Adott: a környezet modellje, pl. az akadályok rácsos geometriai leírása vagy a környezet térképe. Feladat: Becsüljük meg a robot környezeten belüli helyzetét a megfigyelések alapján. Ezek a megfigyelések tipikusan különböző odometriai méréseken alapulnak valamint egyéb a környezetből információt szerző szenzorok mérésein.
Állandó és változó környezet Állandó környezet feltételezi, hogy az egyetlen változó dolog a robot saját helyzete Változó környezet
Belső a robot számára egy belső környezet lényegesen
megváltozik, ha akár egy bútort is arrébb teszünk. Nyitott, zárt ajtók, emberek járkálnak.
Külső pl. az utca
Aktív és passzív lokalizáció Passzív
kizárólag a robot szenzorainak a jeleit használja fel sem a robot mozgása, sem a helyzete nem változtatható
Aktív
számos hely hasonlóan néz ki (főleg a robot számára) Megoldás: a robotot távolabbi hely(ek)re küldjük el, hogy különbséget tudjon tenni a lehetséges helyek között. (van saját térkép!) A helymeghatározó modul részlegesen vagy teljesen be tud avatkozni a robot mozgásába.
Aktív lokalizáció
Markovi helymeghatározás Általános, valószínűségszámítási keretet biztosít, ami jól illeszkedik a globális helymeghatározási feladathoz. Globális becslő eljárás; a szenzoros megfigyelé-seket és a robot mozgását is figyelembe veszi. Az általános helymeghatározási probléma Bayes-becslésként fogalmazható meg (alapelv: ami ismeretlen, az legyen valószínűségi változó)
Markovi helymeghatározás (MH) A robot az összes rendelkezésre álló információ alapján tartózkodási valószínűséget rendel hozzá minden lehetséges helyszínhez Lokalizációs probléma: a tartózkodási valószínűség sűrűségfüggvényének meghatározása az összes lehetséges helyszín halmazán
MH: tartózkodási valószínűség Az összes lehetséges helyszín halmaza: Ω ‘Belief’ (a robot feltételezése arról, hogy hol lehet): valószínűségsűrűség Ω-n
Bel(xk)=P(xk | d0…k)
Annak a valószínűsége, hogy a robot a k időpillanatban az xk helyen tartózkodik, feltéve, hogy a d0…k adatok állnak rendelkezésére (ebbe a-priori információk is beleértendők, pl. a környezet valamilyen térképe)
MH: prior és poszterior feltételezések A navigáció során a robot relatív és abszolút mérési információkat kap Prior feltételezés: Bel-(xk) a k. időpillanatig beérkező összes információ felhasználásával, kivéve a k. abszolút mérés eredményét Poszterior feltételezés: Bel+(xk) a legutolsó (k.) abszolút mérés eredményének figyelembevételével
MH: Akciók (cselekvések, mozgások) A robot által elvégezhető (hely- ill. helyzetváltoztatást eredményező) akciók halmaza: A Valószínűségi modell:
P(xk | xk-1, ak-1)
leírja, hogyan változik a robot helyzete az akciók nyomán (akció- v. mozgás-modell) Meghatározása: a robot kinematikájából és dinamikájából, esetleg tanulással
MH: Érzékelés A szenzorokból érkező összes lehetséges mérés halmaza: S (pl. kamera-adatok esetén elég komplex lehet) Mérési v. érzékelési modell:
P(sk | xk)
sok dimenziós mérési adatok esetén nehéz számítani, ezért szokták a dimenziót csökkenteni: Tulajdonságkiemelő (feature extractor):
σ :S → Z
MH: lokalizációs formula Kezdeti feltételezés: Bel-(x0) alakja attól függ, vannak-e a robotnak információi a kezdeti helyzetéről (ha semmit sem tud, akkor egyenletes eloszlás) A feltételezések frissítése:
Bel-(xk) = P(xk | z1, a1 ,z2 , a2, … zk-1, ak-1) Bel+(xk) = P(xk | z1, a1, z2, a2,… zk-1, ak-1, zk)
MH: lokalizációs formula Ismétlés: teljes valószínűség tétele Legyen A1, …, An az eseménytér egy partícionálása. Ekkor bármely B eseményre igaz: n
P( B) = ∑ P( B | A j ) P( A j ) j =1
A prior feltételezés ez alapján átírható: Bel − ( xk ) = ∫ P( xk | xk −1 , z1 , a1 ,..., z k −1 , ak −1 ) ⋅ P( xk −1 | z1 , a1 ,..., z k −1 , ak −1 )dxk −1 Ω
xk-1 nem függ ak-1-től, így : Bel − ( xk ) = ∫ P ( xk | xk −1 , z1 , a1 ,..., z k −1 , ak −1 ) ⋅ P ( xk −1 | z1 , a1 ,..., ak − 2 , z k −1 )dxk −1 Ω
MH: lokalizációs formula Bel+ definíciójának felhasználásával: Bel − ( xk ) = ∫ P ( xk | xk −1 , z1 , a1 ,..., z k −1 , ak −1 ) ⋅ Bel + ( xk −1 )dxk −1 Ω
Markov-feltételezés: az aktuális helyzet csak az előző helyzettől, és a legutolsó akciótól függ: P( xk | xk −1 , z1 , a1 ,..., z k −1 , ak −1 ) = P( xk | xk −1 , ak −1 )
A fenti egyenlet jobb oldalán az akció-modell van! Felírhatjuk a következőt: Bel − ( xk ) = ∫ P( xk | xk −1 , ak −1 )Bel + ( xk −1 )dxk −1 Ω
MH: lokalizációs formula Ismétlés: Bayes-szabály
ennek felhasználásával bevonható az érzékelési modell: P( z k | xk , z1 , a1 ,..., z k −1 , ak −1 ) P( xk | z1 , a1 ,..., z k −1 , ak −1 ) Bel ( xk ) = P( z k | z1 , a1 ,..., z k −1 , ak −1 ) +
MH: lokalizációs formula Markov feltételezés: a szenzorok által szolgáltatott adatok csak az aktuális állapottól függnek (a múltbeliektől nem): P( z k | xk , z1 , a1 ,..., z k −1 , ak −1 ) = P ( z k | xk )
Ez alapján Bel+(xk) így írható (a nevező tekinthető normalizációs tényezőnek): P( z k | xk ) Bel − ( xk ) Bel ( xk ) = P( z k | z1 , a1 ,..., z k −1 , ak −1 ) +
MH: lokalizációs formula A nevező kiszámítása (azért, hogy Bel+(xk)-ra valószínűségsűrűség függvényt kapjunk): P ( z k | z1 , a1 ,..., z k −1 , ak −1 ) = ∫ P ( z k | xk ) Bel − ( xk )dxk Ω
Számítási szabály:
− P ( z | x ) Bel ( xk ) k k Bel + ( xk ) = P( z k | z1 ,..., ak −1 )
=
P ( z k | xk ) ∫ P( xk | xk −1 , ak −1 ) Bel + ( xk −1 )dxk −1 Ω
P( z k | z1 ,..., ak −1 )
= η k P( z k | xk ) ∫ P( xk | xk −1 , ak −1 ) Bel + ( xk −1 )dxk −1 Ω
MH: tipikus működés kezdeti állapot semmit sem érzékel Mozog és érzékel egy útjelzőt Mozog és semmit sem érzékel Mozog és érzékel egy útjelzőt
MH: komponensek a számításhoz Akció- (cselekvési) modell Érzékelési modell Kezdeti feltételezés
MH: implementációs kérdések Reprezentációs komplexitás: az összes lehetséges hely és helyzet számítógépes ábrázolása nehézkes lehet Modellezési komplexitás: a valósághű akció- és érzékelési modellek bonyolultak lehetnek
MH: térben diszkrét implementációk Topologikus gráfok: a tér durva felbontása a lehető legkevesebb akcióval (pl. egyenes haladás, 4 irányba történő fordulás) csúcsok: helyszínek élek: információ arról, hogy a robot hogyan juthat el egyik helyről a másikra Rácsok: egyenletes rögzített koordináta- és szögfelbontás (10-40cm, 2-5 fok)
MH: térben diszkrét implementációk Particle szűrők: Bel reprezentációja m db (konvex kombinációval) súlyozott minta segítségével egy minta egy helyszínhez tartozik súlyok: fontossági tényezők nagy valószínűséghez sűrűbb mintavétel és nagyobb súlyok tartoznak
Markovi helymeghatározás particle szűrőkkel A részecske szűrők az egyenletes rácsok alternatívái A minta halmaz tekinthető, mint egy nem egyenletes rács, a minták sűrűsége jeleníti meg a valószínűséget a tér tetszőleges pontján.
A Bel függvény reprezentációja Kálmán szűrő A Kálmán szűrő paraméteres normál eloszlással reprezentálja az aposzteriori feltételezést.
Kálmán szűrő A mozgás modell Gaussi A szenzor modell Gaussi Minden egyes belief függvényt egyértelműen meghatározza a várható értéke μ és a szórás Σ. A poszterior számítása azt jelenti, hogy új várhatóértéket és kovarianciát számolunk a régi adatok és szenzoros jelek alapján. Korlátok: Unimodális eloszlás Lineáris rendszer Globális helymeghatározásra nem alkalmas Többféle hipotézis nincs
Kálmán szűrő Diszkrét lineáris sztochasztikus folyamat sztochasztikus mérés Folyamat és mérési zaj, normális eloszlású, w, v, nulla várható értékű, Q, R kovariancia mátrixszal.
Kálmán szűrő a priori valószínűség és hiba kovariancia ahol xk a apriori becslése az aposzteriori valószínűség és hiba kovariancia zk megfigyelése esetén.
Kálmán szűrő számoljuk ki az aposzteriori valószínűséget, mint a becsült állapot és az aktuális és a várt mérés közötti különbség lineáris kombinációját. becslés innováció (mérés)
K egy súly, és úgy van megadva, hogy minimalizálja az aposzteriori kovarianciát
Kálmán szűrő A Kálmán szűrő az állapot vektor várható értékét és szórását számolja (első két momentum).
A aposzteriori becslési hiba kovarianciája tükrözi az állapot eloszlásának szórását
Kálmán szűrő a következő állapot becslése
a következő állapot javítása a mérés alapján
Kálmán szűrő Becslés (predikció) (1) a becsült állapot
(2) a hiba kovariancia becslése
Mérés (korrekció) (1) A Kálmán erősítés számolása (2)Frissítjük a becslést a zk mérés alapján (3)Frissítjük a hiba kovariancia becslését
P0
Példa
Kiterjesztett Kálmán szűrő Nemlineáris folyamatokhoz
Linearizál az aktuális becslés körül Parciális deriváltak számítása (Jakobi mátrix)
Kiterjesztett Kálmán szűrő
KF: Alkalmazási példa Feladat: mobilrobot helymeghatározása
KF: Alkalmazási példa Az ultrahangos jeladók működése:
KF: Alkalmazási példa Rendszermodell:
Folyamat- és mérési zajok:
Állapotvektor:
KF: Alkalmazási példa Állapotegyenletek:
KF: Alkalmazási példa Kimeneti egyenletek meghatározása:
KF: Alkalmazási példa Bemenet hatása: ahol ω a bemenetnek tekintett mért szögsebesség Linearizált rendszermátrix:
KF: Alkalmazási példa A pozícióbecslés működése:
