2 Pravděpodobnostní lokalizace

V úvodní kapitole jsme mimo jiné rozdělili lokalizační techniky na relativní a absolutní, představili jejich hlavní výhody a slabiny a předeslali, že žádná z lokalizačních technik není dokonalá a sama o sobě dostačující pro kvalitní lokalizaci. Techniky relativní lokalizace jsou zatížené chybou, která roste s ujetou vzdáleností nebo s časem, a jsou proto použitelné pouze pro krátkodobý odhad pozice. Techniky absolutní lokalizace problémem s akumulací chyby netrpí, ale jejich přesnost a spolehlivost je také omezená. Nejlepším řešením pro spolehlivou, robustní a přesnou lokalizaci je proto data z relativních a absolutních měření vhodným způsobem kombinovat, a to při vědomí silných i slabých stránek jednotlivých kombinovaných technik.

Tato kapitola se zabývá způsoby, jak zpracovávat a kombinovat chybami zatížená data z různých senzorů, a to především s ohledem na jejich použití k lokalizaci robota. Zpracování dat z více senzorů se ale používá i v dalších robotických aplikacích, jmenovitě například k mapování nebo k rozpoznávání objektů.

Jedním z možných a přirozených způsobů, jak pracovat s nepřesnými informacemi ze senzorů na vstupu a jak reprezentovat často ne zcela jednoznačnou pozici robota v prostoru, a zároveň způsobem nejčastěji používaným, je pravděpodobnostní přístup. Podle něj představují veličiny měřené pomocí senzorů i skutečná poloha robota náhodné veličiny. Problém lokalizace robota je pak při tomto přístupu problémem nalezení takové hustoty pravděpodobnosti, která co nejlépe odpovídá hustotě pravděpodobnosti skutečného výskytu robota. Pravděpodobnostní přístup se pro řešení úloh zpracování dat z více senzorů osvědčil a je toho času považován za standardní metodu řešení těchto úloh [2].

Vedle pravděpodobnostního přístupu existují i další metody pro zpracování a kombinaci nepřesných dat, například fuzzy logika nebo intervalový počet. Ačkoliv se obecně pro zpracování dat z více senzorů příliš nepoužívají, stojí alespoň za krátkou zmínku v části 2.8 a představení principu, na němž fungují.

V této kapitole se podrobně seznámíme s principem pravděpodobnostní lokalizace. Zadefinujeme pravděpodobnostní odhad polohy robota, ukážeme, jakým způsobem použít všechna dostupná data z relativních i absolutních měření k aktualizacím tohoto odhadu, a odvodíme potřebné vzorce pro jeho výpočet. Představíme také různé metody, jak pravděpodobnostní odhad implementovat, a detailně srovnáme jejich přednosti a slabiny.

2.1 Princip pravděpodobnostní lokalizace a filtrování

Pravděpodobnostní lokalizace odhaduje polohu robota podle všech dostupných relativních a absolutních měření a podle předcházejícího odhadu jeho polohy. Odhadem polohy robota v pravděpodobnostní lokalizaci není jeden bod – nějaké místo, kde se robot nejspíše nachází – ale hustota pravděpodobnosti – funkce, která každé možné poloze v prostoru přiřazuje pravděpodobnost, že je aktuální polohou robota.

Pro lokalizaci po zemi se pohybujících robotů se většinou uvažuje trojrozměrný prostor možných poloh l, sestávající z dvourozměrné pozice v rovině x a y a z orientace θ.

Sama pravděpodobnostní lokalizace je instancí obecnější metody, totiž pravděpodobnostního odhadu v čase se měnícího stavu na základě nepřesných, chybami a šumem zatížených informací o tomto stavu. Taková metoda odhadující aktuální stav se nazývá filtrování. V našem případě bude odhadovaným stavem poloha robota a informacemi o ní data z relativních a absolutních měření. I když podstatná část následujícího textu a vzorců vysvětluje v zásadě i podstatu filtrování obecně, vzhledem k zaměření práce se bude držet popisu této problematiky z pohledu lokalizace.

2.1.1 Základní pojmy z teorie pravděpodobnosti

V této kapitole budeme používat některé základní pojmy z teorie pravděpodobnosti. Pro úplnost je nyní v krátkosti velmi stručně připomeneme.

Podmíněnou pravděpodobností P(A|B) rozumíme pravděpodobnost jevu A za předpokladu, že nastal náhodný jev B. Přitom předpokládáme, že pravděpodobnost náhodného jevu B je nenulová.

(2.1)

Náhodné jevy A a B nazveme nezávislé, jestliže P(A∩B) = P(A)·P(B). Ekvivalentní podmínkou pro nezávislost jevů A a B je rovnost P(A|B) = P(A) resp. P(B|A) = P(B).

Věta o úplné pravděpodobnosti. Pokud náhodné veličiny B_i tvoří úplný systém jevů (to znamená, že jevy B_i jsou po dvou neslučitelné a zároveň sjednocení všech jevů B_i tvoří jev jistý), potom pro libovolný náhodný jev A platí:

(2.2)

Bayesova věta. Pro náhodné jevy A a B, za předpokladu, že pravděpodobnost náhodného jevu B je nenulová, platí:

Pro jev podmíněný více jevy potom platí následující varianta Bayesovy věty:

(2.3)

Řekneme, že náhodný proces {X_n} má Markovovu vlastnost, pokud pravděpodobnost nového stavu nezáleží na minulosti předcházející aktuálnímu stavu.

Náhodný proces splňující Markovovu vlastnost nazveme Markovův řetězec. Pokud výše uvedená pravděpodobnost není závislá na konkrétním kroku k, nýbrž zůstává stále stejná, tedy platí, že P(X_k−1=j | X_k−1=i) = p_i, j ∀k > 0, nazveme takovou vlastnost náhodného procesu silná Markovova vlastnost a náhodný proces samotný pak homogenní Markovův řetězec.

Předpoklad silné Markovovi vlastnosti budeme v pravděpodobnostní lokalizaci používat na několika místech této kapitoly, konkrétně v části 2.4 a 2.5. Tento předpoklad nám dovolí udržet složitost problému lokalizace na úrovni, na které jsme schopni ho časově a prostorově zvládnout. Řešením problému lokalizace v dynamickém prostředí, ve kterém nelze Markovovu vlastnost předpokládat, se budeme zabývat v části 5.1.

2.2 Odhad polohy

Odhad polohy Bel(l) (v anglicky psané literatuře Belief) je hustota pravděpodobnosti výskytu robota na jednotlivých pozicích l prostoru, v němž se má robot lokalizovat. Z definice hustoty pravděpodobnosti plyne, že integrál odhadu polohy přes všechny možné polohy robota v prostoru je vždy roven jedné.

(2.4)

Cílem pravděpodobnostní lokalizace je udržovat odhad Bel(l) tak, aby co nejlépe odpovídal skutečnému rozdělení pravděpodobnosti výskytu robota. V ideálním případě, je-li robotovi jeho pozice s vysokou pravděpodobností známá, má funkce Bel(l) jediný vrchol a mimo něj je její hodnota rovná (respektive blízká) nule.

Aktuální odhad polohy v kroku k je hustota pravděpodobnosti výskytu robota podmíněná všemi daty, které byla do okamžiku odhadu k dispozici.

Odhad polohy je na základě senzory naměřených údajů sekvenčně aktualizován, a to vždy po získání nějakého relativního nebo absolutního měření. Ačkoliv tomu tak ve skutečnosti typicky nebývá, pro odvození vzorce pro výpočet aktualizovaného odhadu polohy budeme bez újmy na obecnosti v následujícím textu předpokládat, že se měření z absolutních a relativních senzorů pravidelně střídají.

Obrázek 2.1: Ilustrace postupné aktualizace odhadu polohy na základě dostupných absolutních a relativních měření.

V každém kroku k > 0 aktualizujeme odhad polohy nejprve na základě relativního a poté na základě absolutního měření. Odhad polohy, ve kterém je posledním zahrnutým měřením relativní měření a_k−1 nazveme apriorní odhad polohy v kroku k a označíme ho Bel⁻(l_k). Podrobně se mu budeme věnovat v části 2.4. Odhad polohy, ve kterém je posledním zahrnutým měřením absolutní měření zk, nazveme aposteriorní odhad polohy v kroku k a označíme ho Bel⁺(l_k). Detailně se jím budeme zabývat v části 2.5. Ještě předtím ale v části 2.3 popíšeme počáteční odhad polohy, ze kterého se při následné aktualizaci odhadu polohy vychází.

2.3 Počáteční odhad polohy

Počáteční odhad polohy (anglicky initial belief) je výchozí hodnota odhadu polohy v okamžiku zapnutí robota, tedy ještě před tím, než robot získá jakékoliv informace ze svých senzorů. Pro fungování lokalizace je nutné, aby byl robotovi počáteční odhad polohy Bel⁻(l₀) znám.

Pokud je robotovi jeho počáteční poloha známá, bude mít počáteční odhad Bel⁻(l₀) jeden vrchol v místě skutečné výchozí polohy, mimo něj pak bude blízký nule. V tomto případě se počáteční odhad polohy zpravidla inicializuje úzkým normálním rozdělením. Znalost počáteční polohy je nutnou podmínkou pro fungování lokalizace tehdy, je-li robot schopen pouze lokálních technik.

Inicializace počátečního odhadu polohy Bel⁻(l₀) je nutná i v situaci, ve které robot o své počáteční poloze nemá vůbec žádnou představu. V takovém případě bude počáteční odhad polohy naprosto neutrální, reprezentující skutečnost, že všechny možné polohy robota v prostoru jsou stejně pravděpodobné. Tuto vlastnost má rovnoměrné rozdělení pokrývající celý prostor, v němž se má robot lokalizovat. Inicializace odhadu polohy rovnoměrným rozdělením je charakteristická pro roboty schopné lokalizace bez znalosti své počáteční polohy.

Pomocí počátečního odhadu polohy je možné vyjádřit i situaci, kdy robot sice přesně neví, jaká je jeho počáteční poloha, ale má o ní nějakou představu – například tehdy, existuje-li jen několik možných výchozích pozic. Zahrnutí takových informací do Bel⁻(l₀) umožní robotovi schopnému globálních technik rychlejší lokalizování se, než při inicializaci Bel⁻(l₀) rovnoměrným rozdělením.

2.4 Apriorní odhad polohy

Aktualizace odhadu polohy podle informací o pohybu robota se nazývá predikční krok, protože se nový odhad polohy předpovídá na základě předcházejícího odhadu polohy a posledních dat z relativních měření o změně polohy robota.³

Odhad polohy vytvořený v predikčním kroku se označuje jako apriorní odhad polohy (anglicky prior beleif). Apriorní odhad polohy v kroku k závisí na počátečním odhadu polohy a na datech ze všech dosavadních absolutních měření z_i a relativních měření a_i, přičemž poslední zahrnutou informací v apriorním odhadu polohy jsou data z posledního relativního měření a_k−1.

(2.5)

K výpočtu apriorního odhadu polohy budeme potřebovat pravděpodobnostní popis, jak data z relativních měření promítnout do změny polohy robota. Ten proto v podobě pravděpodobnostního modelu nyní definujeme. V navazující části pak odvodíme vzorec pro výpočet apriorního odhadu polohy.

---

³ Protože se predikční krok často opakuje v pravidelných časových intervalech, označuje se někdy také jako time update.

2.4.1 Pravděpodobnostní pohybový model

K výpočtu Bel⁻(l_k) je nutné mít k dispozici model, který by popisoval, jakým způsobem určitá akce a_k−1 změní polohu robota z původní l_k−1 na novou l_k. Akcí v tomto případě rozumíme určitý pohyb robota, zpravidla detekovaný a změřený pomocí relativních senzorů. Tento model budeme nazývat pravděpodobnostní pohybový model nebo akční model (anglicky motion model resp. action model).

(2.6)

Pravděpodobnostní pohybový model vyjadřuje podmíněnou pravděpodobnost nové polohy l_k v kroku k za předpokladu, že v kroku k−1 provedl robot nacházející se v poloze l_k−1 akci a_k−1. Vzhledem k tomu, že efekt akce typicky nezáleží na kroku, ve kterém k ní došlo, není třeba akce indexovat číslem kroku.

Pravděpodobnostní pohybový model robota se nejčastěji vytváří z kinematického modelu robota a zahrnuje také očekávané systematické chyby použitých technik relativní lokalizace. Kinematickými modely pro kolové roboty se budeme podrobně zabývat v kapitole 3.2.2, systematické chyby přitom budou diskutovány v kapitole 3.2.1. Alternativní, méně často využívanou možností získání tohoto modelu je samoučení robota.

V případě, že relativní měření o pohybu robota nejsou k dispozici, typicky proto, že robot není vybaven žádnými senzory tohoto druhu, lze místo těchto měření jako akce a používat přímo ovládací povely, kterými je pohyb robota řízen. To do odhadování polohy vnáší předpoklad, že řídící povel bude naplněn a promítnut do změny polohy robota, a potenciálně také další chybu, protože splnění tohoto předpokladu nemusí být dokonalé.

2.4.2 Predikční krok

Apriorní odhad polohy definovaný v (2.5) můžeme podle věty o úplné pravděpodobnosti (2.2) rozepsat jako integrál přes všechny polohy v předcházejícím kroku lk−1 takto:

(2.7)

Můžeme-li předpokládat Markovovu vlastnost P(l_k | l_k−1, l₀, z₀, a₀, … z_k−1, a_k−1) = P(l_k | l_k−1, a_k−1), tedy že pravděpodobnost přechodu z polohy l_k−1 do polohy l_k závisí pouze na poloze l_k−1 a akci a_k−1, nikoliv však na polohách, akcích a pozorováních předcházejících, můžeme první výraz v součinu (2.7) upravit do tvaru známého z (2.6) jako pravděpodobnostní pohybový model.

Dále pak můžeme v druhém výrazu v součinu (2.7) zcela odstranit podmínění akcí a_k−1, protože poloha l_k−1 na akci a_k−1, jenž představuje přechod z polohy l_k−1 do polohy l_k, vůbec nezávisí. Tím upravíme druhý výraz do podoby, kterou podle (2.9) můžeme přepsat jako aposteriorní odhad polohy v kroku k−1. Po těchto úpravách nakonec získáme následující vzorec pro výpočet apriorního odhadu polohy:

(2.8)

Apriorní odhad polohy v kroku k je tedy integrálem přes všechny potenciální polohy l_k−1 v kroku k−1 ze součinu aposteriorní pravděpodobnosti polohy l_k−1 v kroku k−1 a pravděpodobnosti přechodu z polohy l_k−1 do polohy l_k při akci a_k−1.

2.5 Aposteriorní odhad polohy

Aktualizace odhadu polohy podle informací o absolutní poloze robota se nazývá korekční krok, protože se nový odhad polohy získává opravou předcházejícího odhadu na základě dat z absolutních měření aktuální polohy robota.⁴

Odhad polohy vytvořený v korekčním kroku se označuje jako aposteriorní odhad polohy (anglicky posterior beleif). Aposteriorní odhad polohy v kroku k závisí na počátečním odhadu polohy a na datech ze všech dosavadních absolutních měření z_i a relativních měření a_i, přičemž poslední zahrnutou informací v aposteriorním odhadu polohy jsou data z posledního absolutního měření z_i.

(2.9)

K výpočtu aposteriorního odhadu polohy budeme potřebovat pravděpodobnostní popis, jak data z absolutních měření interpretovat jako informace o aktuální poloze robota. Ten nyní ve formě pravděpodobnostního modelu proto definujeme. V navazující části poté odvodíme vzorec pro výpočet aposteriorního odhadu polohy.

---

⁴ Protože se korekční krok provádí vždy po získání nějakého pozorování, označuje se někdy také jako observation update.

2.5.1 Senzorický model

K výpočtu Bel⁺(l_k) je nutné disponovat pravděpodobnostním modelem, který by popisoval, jakým způsobem je možné použít naměřená data (pozorování) z_i získaná z absolutních senzorů k upřesnění odhadu polohy l_k. Tento model budeme nazývat pravděpodobnostní senzorický model (anglicky sensor model nebo perceptual model).

(2.10)

Senzorický model vyjadřuje podmíněnou pravděpodobnost zjištění pozorování zk za předpokladu, že se robot nachází v poloze l_k. Vzhledem k tomu, že typicky předpokládáme, že pravděpodobnost pozorování v určité pevné poloze nezáleží na kroku, ve kterém k pozorování došlo, není třeba indexování krokem k.

Senzorický model robota může být reprezentován v zásadě dvěma způsoby:

• předpisem, který popisuje, jak lze hodnotu P(z | l) vypočítat, například ze znalosti rozmístění majáčků v prostoru nebo pomocí ray-tracingu a známé mapy prostředí, nebo
• může být vypočítán předem pro všechny myslitelné polohy l a pozorování z a uložen k pozdějšímu použití.
  Alternativně se v některých situacích může robot senzorický model naučit, je-li lokalizován jiným způsobem a může-li naměřená pozorování použít k tvorbě senzorického modelu.

Volba vhodného způsobu reprezentace senzorického modelu záleží na konkrétní aplikaci. Předpisy jsou úspornější na paměťový prostor a náročnější na výpočetní čas, naopak uložené hodnoty P(z | l) jsou za cenu vyšších nároků na paměť méně výpočetně náročné, což může být kvůli omezené výpočetní kapacitě pro lokalizaci v reálném čase velmi důležité.

V některých případech, například při vizuální lokalizaci pomocí kamery, mohou být pozorování natolik složitá, že by bylo vytvoření a použití senzorického modelu příliš náročné. Tehdy je potřeba mnoharozměrná hrubá vstupní data předzpracovat a získat z nich tzv. charakteristické rysy (v angličtině feature vector), pokud možno tak, aby při této redukci objemu dat nedošlo k citelné ztrátě informace. Takovéto zobrazení z prostoru hrubých dat do prostoru charakteristických rysů se nazývá extrakce charakteristických rysů (feature extraction).

Získané charakteristické rysy se poté ve výpočtech aposteriorního odhadu polohy používají na místě absolutních měření. Ve výše uvedeném příkladě by charakteristickým rysem mohl být například výskyt nebo absence výskytu viditelného orientačního bodu v zorném poli kamery. Způsoby, jakým se extrakce charakteristických rysů provádí, mohou být různé (algoritmy pro zpracování obrazu, neuronové sítě), jejich popis ale přesahuje rámec této práce.

Protože při extrakci charakteristických rysů typicky dojde k částečné ztrátě informace ze senzorů, je výsledek takové lokalizace suboptimální; to je ale vyváženo snížením výpočetní náročnosti, které je v případech, kdy by bez provedení popsané transformace lokalizace v reálném čase nebyla možná, nevyhnutelné. Jiný případ, kdy se namísto hrubých dat používají při výpočtu aposteriorního odhadu polohy charakteristické rysy, je uveden v části 2.7.1.2 o odhadu polohy reprezentované pomocí topologických grafů.

2.5.2 Korekční krok

Aposteriorní odhad polohy jsme definovali v (2.9). Aplikací Bayesovy věty (2.3) ho můžeme upravit následovně. Druhý výraz v čitateli pak můžeme zapsat jako apriorní odhad polohy v kroku k (2.5).

(2.11)

Budeme-li předpokládat Markovovu vlastnost P(z_k | l_k, l₀, z₀, a₀, ... z_k−1, a_k−1) = P(z_k|l_k), tedy že pravděpodobnost pozorování z_k v poloze l_k závisí pouze na této poloze, nikoliv však na polohách, akcích a pozorováních, které dosažení této polohy předcházely, můžeme první výraz v čitateli (2.11) upravit do tvaru definovaného v (2.10) jako senzorický model.

(2.12)

Smyslem jmenovatele v tomto zlomku je zajistit, aby integrál pravděpodobnosti výskytu robota přes všechny polohy l_k byl roven jedné. Můžeme ho proto nahradit normalizační konstantou C_k.

(2.13)

Aby byla splněna podmínka, že ∫ Bel⁺(l_k) dl_k = 1 , musí pro normalizační konstantu C_k platit:

(2.14)

Aposteriorní odhad polohy v kroku k je tedy normovaným součinem apriorní pravděpodobnosti polohy l_k v kroku k a podmíněné pravděpodobnosti detekce absolutního pozorování z_k za předpokladu, že se robot nachází v poloze l_k.

2.6 Lokalizační vzorec

Kompletní rekurzivní vzorec pro aktualizaci odhadu polohy po získání relativních a absolutních měření můžeme vyjádřit spojením vzorců (2.8) a (2.13) pro predikční a korekční krok.

(2.15)

Ck je normalizační konstanta vypočtená podle (2.14).

Kromě tohoto vzorce samotného potřebuje robot pro svou lokalizaci také znalost dvou pravděpodobnostních modelů, které jsou ve vzorci používány – pravděpodobnostního pohybového modelu popsaného v 2.4.1, který vyjadřuje vliv relativních měření na změnu polohy robota, a senzorického modelu popsaného v 2.5.1, který udává souvislost polohy robota a výsledků absolutních měření v této poloze provedených. Kvůli rekurentnímu charakteru lokalizačního vzorce potřebuje robot navíc znát také počáteční odhad své polohy, a to i v případě, že mu není o jeho počáteční poloze nic známo, jak jsme detailně probrali v 2.3.

Vzhledem k velikosti prostoru možných poloh robota, který je za předpokladu spojitosti souřadnic x, y a θ nekonečný, je zřejmé, že reprezentace obecné hustoty pravděpodobnosti nad tímto prostorem není úplně triviální. V následující části se proto budeme zabývat možnostmi, jak odhad polohy robota reprezentovat a jak s pomocí této reprezentace implementovat pravděpodobnostní lokalizaci.

2.7 Reprezentace odhadu polohy

Jednotlivé implementace pravděpodobnostní lokalizace se v zásadě liší způsobem, jakým je reprezentován odhad polohy Bel(l). Protože je odhad polohy obecnou hustotou pravděpodobnosti, je problematické vyjádřit ho přesně, naštěstí ale není jeho naprosto přesná reprezentace pro lokalizaci nutná.

Níže popsané reprezentace odhadu polohy se vzájemně liší ve třech aspektech:

• přesností, s jakou dokáží aproximovat skutečný odhad polohy,
• omezeními a případnými vynucenými předpoklady, které z takových omezení plynou,
• výpočetní náročností při jednotlivých operacích s odhadem polohy.

Reprezentace odhadu polohy můžeme rozdělit do dvou kategorií, na diskrétní a spojité, aproximující skutečný odhad polohy nějakým diskrétním resp. spojitým rozdělením. Podrobněji je lze dále dělit podle toho, jak je taková diskrétní nebo spojitá aproximace implementována.

2.7.1 Diskrétní reprezentace odhadu polohy

Při diskrétní reprezentaci je odhad polohy, definovaný na spojitém prostoru, reprezentovaný pouze konečným množstvím hodnot, které odpovídají jednotlivým částem původního spojitého definičního oboru. Díky tomu lze integrály použité ve výše uvedených lokalizačních vzorcích považovat za konečné sumy a explicitně je vypočítat.

Jednotlivé diskrétní reprezentace odhadu polohy se liší úrovní detailu pohledu, složitostí implementace a výpočetní náročností. V dalším textu se budeme podrobněji zabývat pravděpodobností mřížkou, topologickými grafy a Monte Carlo lokalizací.

2.7.1.1 Pravděpodobností mřížka

Pravděpodobnostní mřížka je jednoduchou a přímočarou reprezentací odhadu polohy. Prostor, v němž se má robot lokalizovat, rozděluje mřížka do pravidelných buněk konstantní velikosti. Hodnoty Bel(l) uložené pro každou buňku, které jsou indexované souřadnicemi buňky, pak vyjadřují pravděpodobnost, že se robot nachází právě na této pozici. Pravděpodobnostní mřížka umožňuje reprezentovat multimodální rozdělení pravděpodobnosti, tady taková, která reprezentují více hypotéz o poloze robota současně.

Rozměry buněk v mřížce se v závislosti na aplikaci pohybují kolem 10 až 40 centimetrů v osách x a y a kolem 2 až 5° v ose θ (viz [6]). Celkové rozlišení mřížky je limitováno výpočetní kapacitou, zpravidla proto platí, že čím rozsáhlejší je prostor, tím větší budou mít buňky rozměry. Právě rozměry buněk jsou přitom rozhodující pro přesnost lokalizace.

Výpočet odhadu polohy aktualizovaného podle dat o změně polohy robota v predikčním kroku probíhá podle vzorce, který je diskrétní variantou vzorce (2.8):

(2.16)

V korekčním kroku umožňuje pravděpodobnostní mřížka provádět aktualizaci odhadu polohy přímo na základě dat o absolutní poloze robota, naměřených prostřednictvím senzorů. Typicky k tomu využívá předem připravený senzorický model v podobě tabulky P(z | l) o rozměrech shodných s rozměry mřížky. Takový senzorický model se často označuje jako observation grid.

Vzorce pro aktualizaci odhadu polohy robota Bel(l) po získání absolutních měření jsou diskrétní variantou (2.13) a následujících.

(2.17)

kde je normalizační konstanta zajišťující, aby platila rovnost .

Hlavní nevýhodou této reprezentace odhadu polohy je její výpočetní náročnost, která roste s rozlišením mřížky. Řešením tohoto problému je použití jiné, méně přímočaré reprezentace odhadu polohy, nebo úprava pravděpodobnostní mřížky tak, aby se její výpočetní náročnost snížila. Jednou takovou úpravou může být selektivní aktualizace, při které se buňkám s menší hodnotou pravděpodobnosti věnuje méně pozornosti než buňkám reprezentujícím pravděpodobnost vysokou.

Možnou implementací je aktualizovat v každém kroku odhad polohy jen pro ty pozice, ve kterých Bel(l) překročí předem stanovený práh ε. To na jedné straně snižuje náročnost výpočtu, na druhé straně ale představuje riziko v případě, že se některá velmi nepravděpodobná poloha ukáže přece jen být skutečnou polohou robota. S takovým případem musí implementace počítat.

Další možné optimalizace pravděpodobnostní mřížky představují hierarchické (např. quadtree) nebo nečtvercové (např. trojúhelníkové nebo pětiúhelníkové) mřížky. Podle [2], kapitoly 25.1.2 lze považovat také Monte Carlo Lokalizaci za speciální implementaci optimalizované pravděpodobnostní mřížky, u které nemají jednotlivé buňky stálou velikost ani polohu, ale dynamicky se přizpůsobují tak, aby co nejlépe vyhověly potřebě reprezentovat hustotu pravděpodobnosti. V této práci je ale vzhledem k této výrazné odlišnosti metoda Monte Carlo Lokalizace popsána samostatně, jako další způsob implementace diskrétní reprezentace odhadu polohy. Použití pravděpodobnostních mřížek v robotice se ale neomezuje pouze na lokalizaci, jejich další aplikací je mapování. Vzhledem k tomu, že toto téma s lokalizací úzce souvisí, zaslouží si tato aplikace pravděpodobnostních mřížek alespoň krátce zmínit.

Pravděpodobnostní mřížka pro mapování nese zpravidla informaci o pravděpodobnosti volnosti resp. obsazení jednotlivých buněk mřížky. Ačkoliv je takové použití nejčastější, mapováním sledovaná vlastnost nemusí být binární (volno – obsazeno), ale může nabývat více vzájemně se vylučujících hodnot (barva povrchu pod robotem), a dokonce může být i spojitá. Výhodou mapování jediné binární vlastnosti je snadná reprezentace pravděpodobnosti v každé buňce jednou jedinou hodnotou, protože platí:

P(„buňka l je volná“) = 1 − P(„buňka l je obsazená“)

Podobně jako v případě lokalizace je i pro mapování potřeba vyhledávací tabulka P(z | l), obdobný je i vzorec pro aktualizaci odhadu stavu v buňce mřížky, také odvozený z Bayesova vzorce:

Normalizační konstanta c_l zde ale na rozdíl od lokalizačního vzorce zajišťuje, aby byl součet pravděpodobností všech vzájemně se vylučujících vlastností A roven 1. Počítá se tedy pro každou buňku samostatně, přes všechny různé vlastnosti A, na rozdíl od lokalizace, kde součet Bel⁺(l) musel být roven 1 přes všechny buňky v mřížce.

2.7.1.2 Topologické grafy

Topologické grafy jsou další možností, jak diskrétně reprezentovat odhad polohy. Topologický graf je tvořen uzly a hranami; uzly představují možné pozice robota v prostoru, ve kterém se má robot lokalizovat, hrany grafu pak reprezentují možné přechody mezi jednotlivými pozicemi. Pro každý uzel je uložena hodnota Bel(l) vyjadřující pravděpodobnost, že se robot nachází právě v tomto uzlu. Díky tomu umožňují i topologické grafy reprezentovat multimodální rozdělení.

Ze všech popisovaných diskrétních reprezentací poskytují topologické grafy nejvyšší míru abstrakce. Od zbývajících diskrétních reprezentací, prostřednictvím kterých lze vyjádřit odhad polohy univerzálně bez ohledu na konkrétní prostředí, se liší tím, že části prostoru, v němž se má robot lokalizovat, mohou být přiřazeny jednotlivým uzlům grafu „na míru“ podle konkrétního prostředí. Díky tomuto způsobu volby jednotlivých uzlů je jejich počet řádově nižší než počet buněk pravděpodobnostní mřížky nebo počet vzorků u Monte Carlo lokalizace, a díky tomu je i výpočetní náročnost samotných topologických grafů mnohem nižší než u obou zbývajících diskrétních reprezentací.

Daní za vyšší a tedy méně detailní úroveň pohledu poskytovanou topologickými grafy je zpravidla nemožnost přímo použít data naměřená senzory k aktualizaci odhadu polohy robota. Topologické grafy navíc principiálně nemusí obsahovat žádné geometrické resp. mapové informace, neumí proto na základě naměřených dat lokalizovat robota vůči jinak potenciálně známé geometrické mapě prostředí. Informace získané prostřednictvím senzorů je potřeba pro využití v topologických grafech typicky předzpracovat a z hrubých, nízkoúrovňových dat extrahovat komplexnější charakteristické rysy příznačné pro jednotlivé uzly.

Aktualizace odhadu polohy probíhá obdobně, jako u pravděpodobnostní mřížky, s drobným posunem ve významu parametrů z a l. U topologických grafů se zpravidla používá předem připravený senzorický model, který opět označíme P(z|l). Ten v tomto případě obsahuje hodnoty podmíněné pravděpodobnosti detekce charakteristického rysu z za předpokladu, že se robot nachází na pozici reprezentované uzlem l. Díky tomu, že je počet možných charakteristických rysů menší než počet možných různých hodnot přímo naměřených senzory, a díky tomu, že je počet uzlů topologického grafu menší než počet buněk u pravděpodobnostní mřížky, je také velikost senzorického modelu podstatně menší.

Je třeba poznamenat, že předzpracování hrubých senzorických dat na komplexnější charakteristické rysy stojí také určitý výpočetní čas, který může být v některých případech významnější než výpočetní náročnost samotného topologického grafu. Při posuzování celkové výpočetní náročnosti tohoto způsobu lokalizace je proto nutné vzít náročnost předzpracování senzorických dat v úvahu.

Přesnost lokalizace pomocí topologických grafů je omezená kvůli poměrně nízké hustotě uzlů v prostoru a s ní související absolutní velikostí prostoru, který jednotlivé uzly pokrývají.

2.7.1.3 Monte Carlo lokalizace

Monte Carlo lokalizace je univerzální a přitom velmi efektivní způsob reprezentace a aktualizace odhadu polohy robota. Odhad polohy reprezentuje pomocí konečné množiny vážených vzorků. Tyto vzorky označené⁵ lⁱ jsou rozmístěny v prostoru, v němž se má robot lokalizovat, a mají přiřazenou váhu wⁱ, která vyjadřuje jejich důležitost – čím je vzorek důležitější, tím je pravděpodobnost, že odpovídá aktuální poloze robota, vyšší. Počet vzorků N se typicky pohybuje od stovek do desetitisíců a může se dokonce průběžně podle potřeby měnit. Díky tomu, že jednotlivé vzorky lze v prostoru rozmístit – ve srovnání s omezeným rozlišením pravděpodobnostní mřížky nebo s nízkou hustotou uzlů topologického grafu – velmi volně, dovoluje Monte Carlo lokalizace dosáhnout vyšší přesnosti. Stejně jako obě výše popsané diskrétní reprezentace, i Monte Carlo lokalizace umožňuje reprezentovat multimodální rozdělení pravděpodobnosti výskytu robota. Ačkoliv se budeme nadále zabývat pouze lokalizací, je třeba zmínit, že reprezentace prostřednictvím množiny vážených vzorků se používají i v jiných aplikacích na odhad stavu dynamických procesů.

Hustota vzorků v prostoru, v němž se má robot lokalizovat, spolu s váhami jednotlivých vzorků určují společně hustotu pravděpodobnosti výskytu robota, tedy odhad polohy Bel(l). Ten můžeme v celém prostoru přibližně vyjádřit následovně.

Funkce δ je diskrétní Diracův impulz⁶. Aby byl odhad polohy hustotou pravděpodobnosti, tedy aby byla dodržena podmínka (2.4), musí platit:

(2.18)

Tento způsob reprezentace odhadu polohy prostřednictvím množiny vážených vzorků poskytuje jistou volnost, jak vyjádřit určitý pevný odhad polohy Bel(l): vyšší pravděpodobnost výskytu robota v určité části prostoru může být vyjádřena jak většími vahami příslušných vzorků, tak vyšší hustotou vzorků v této části prostoru. V jednom z krajních případů mohou být váhy všech vzorků stejné a odhad polohy bude dán jen rozdělením vzorků v prostoru, v druhém krajním případě budou vzorky rozmístěny pravidelně a budou se lišit svými vahami (taková reprezentace odpovídá pravděpodobnostní mřížce). Skutečná reprezentace při praktickém použití v Monte Carlo lokalizaci se většinou pohybuje mezi těmito popsanými extrémy. Jedním z důvodů nižší výpočetní náročnosti Monte Carlo lokalizace oproti pravděpodobnostní mřížce je způsob, jakým se do odhadu polohy promítají relativní měření v predikčním kroku. Zatímco u obou dříve zmíněných metod bylo potřeba hodnotu v každé buňce nebo uzlu přepočítat pomocí pravděpodobnostního pohybového modelu a hodnot všech ostatních buněk resp. uzlů v předcházejícím kroku podle vzorce (2.16), u Monte Carlo lokalizace stačí vzorky vhodně posunout v prostoru a jejich váhy ponechat nezměněné.

Získáme-li v predikčním kroku k relativní měření a_k−1, pro každý vzorek lⁱ_k−1 určíme jeho novou polohu následujícím způsobem. Dosazením a_k−1 a lⁱ_k−1 do pravděpodobnostního pohybového modelu (2.6) získáme pravděpodobnostní rozdělení nové polohy tohoto vzorku po zahrnutí relativního měření. Z tohoto pravděpodobnostního rozdělení pak náhodně vybereme jednu hodnotu, a tu prohlásíme za novou polohu tohoto vzorku, tedy lⁱ_k. Váha vzorku wⁱ_k−1 se predikčním kroku nemění.

Je třeba ještě jednou zdůraznit, že hodnota lⁱ_k se vybírá z daného pravděpodobnostního rozdělení náhodně podle tohoto rozdělení, tedy nikoliv deterministicky – například jako nejpravděpodobnější hodnota. Jen tak je zajištěno promítnutí nejistoty relativního měření a_k−1 do apriorního odhadu polohy. Za předpokladu, že je v místě pravděpodobného výskytu robota vzorků mnoho, bude takto zkonstruovaná množina vzorků lⁱ_k po provedení predikčního korku přibližně odpovídat apriornímu odhadu polohy. Platí, že přesnost aproximace skutečného odhadu polohy s počtem vzorků roste.

V korekčním kroku Monte Carlo lokalizace dochází k aktualizaci vah jednotlivých vzorků podle získaných absolutních měření; polohy vzorků se v korekčním kroku nemění. Obdobně jako v (2.17) u pravděpodobnostní mřížky se aposteriorní váha vzorku počítá jako normovaný součin apriorní váhy a podmíněné pravděpodobnosti dané senzorickým modelem.

(2.19)

Přitom je normalizační konstanta zajišťující splnění podmínky (2.18).

Je přirozené, že při použití málo přesných absolutních senzorů bude lokalizace méně přesná, než při použití senzorů přesnějších. U Monte Carlo lokalizace se ale, na první pohled poněkud paradoxně, může v korekčním kroku vyskytnout i opačný problém – budou-li absolutní senzory velmi přesné, může být chyba lokalizace větší než při použití méně přesných senzorů. Nejlepšího výsledku tedy Monte Carlo lokalizace dosahuje při použití senzorů, které nejsou ani nepřesné, ani příliš přesné. Vysvětlení je přímočaré – zafixujeme-li hodnotu z získanou z absolutního měření konkrétního senzoru a dosadíme-li ji do senzorického modelu P(z|l), získáme funkci jedné proměnné l. Bez újmy na obecnosti budeme nyní předpokládat, že tato funkce má jediný vrchol, a to v takovém bodě prostoru, v němž je naměření hodnoty z nejpravděpodobnější. Čím je přesnost senzoru vyšší, tím užší tento vrchol bude, mimo něj pak budou hodnoty P(z|l) velmi blízké nebo rovné nule. U velmi přesných senzorů s malým rozptylem může být tento vrchol tak úzký, že se s vysokou pravděpodobností ve výpočtu podle (2.19) oblast výrazně nenulových hodnot P(z|l) nebude krýt s žádným vzorkem lⁱ_k. V takovém případě se toto přesné měření stane pro lokalizaci zcela bezcenným.

Jednoduchým a prakticky použitelným, i když suboptimálním řešením je nadhodnocení rozptylu jinak přesného senzoru při tvorbě senzorického modelu P(z|l). Toto řešení eliminuje paradoxní problém vyšší chybovosti lokalizace při použití velmi přesných senzorů. Nedokáže ale využít výhody přesných senzorů a část dostupných informací ze senzorů tak vlastně bez užitku zahazuje.

Práce [3] popisuje robustnější řešení. Představuje algoritmus nazvaný Mixture Monte Carlo Localization, který pro část vzorků používá tzv. duální Monte Carlo lokalizaci, zbývající vzorky přitom spravuje stejně jako výše popsaná Monte Carlo lokalizace. Při duální Monte Carlo lokalizaci jsou postupy pro aktualizaci vzorků vzájemně otočené – v korekčním kroku se mění poloha vzorků, v predikčním kroku se nastavují jejich váhy. Duální Monte Carlo lokalizace není prakticky použitelná sama o sobě, jako součást popsaného algoritmu ale dobře řeší problém velmi přesných senzorů a navíc výrazně zlepšuje zotavení lokalizace při únosu robota.

Kromě korekčního a predikčního kroku má Monte Carlo lokalizace ještě jednu fázi, která se u ostatních diskrétních reprezentací odhadu polohy nevyskytovala. Touto fází je převzorkování (resampling).

Při postupné aktualizaci odhadu polohy reprezentované prostřednictvím vážených vzorků dochází k určité degeneraci této reprezentace – vzorky na místech nepravděpodobného výskytu robota nabudou zanedbatelné až nulové váhy, zatímco vzorky v místě pravděpodobného výskytu robota budou mít váhy obrovské. Oba tyto jevy jsou nežádoucí. Vzorky s mizivou vahou jsou zbytečné a pouze plýtvají výpočetní kapacitou. Vzorky s obrovskými vahami, ve srovnání s ekvivalentní reprezentací téhož odhadu polohy pomocí vyššího množství vzorků s nižšími, ale v součtu stejnými vahami, zase neumožňují dobře zahrnout nejistoty relativních měření v predikčním kroku. Cílem převzorkování je tedy vzorky se zanedbatelnou vahou rušit a vzorky s vysokou vahou rozštěpit na více vzorků. Je-li to toho potřeba, je možné v této fázi změnit celkový počet vzorků. Původní resp. nový počet vzorků označme N resp. n.

Právě díky eliminaci vzorků v oblastech nepravděpodobného výskytu robota může být celkový počet vzorků Monte Carlo lokalizace nižší než počet buněk pravděpodobnostní mřížky při stejně přesné reprezentaci odhadu polohy. To je dalším důvodem menší výpočetní náročnosti Monte Carlo lokalizace. Schopnost měnit za běhu počet vzorků zase umožňuje přizpůsobovat náročnost Monte Carlo lokalizace požadavkům na přesnost lokalizace nebo velikosti dostupné výpočetní kapacity. Pro převzorkování celého odhadu polohy do nové reprezentace tvořené n novými vzorky s jednotnými vahami wⁱ = 1/n ∀i se používají různé metody, založené typicky na myšlence náhodného výběru pomocí ruletového kola. Níže si představíme tři varianty takového převzorkování. Pro všechny z nich platí, že pravděpodobnost výběru každého vzorku lⁱ z původní reprezentace a jeho přenesení do reprezentace nové je přímo úměrná jeho původní váze wⁱ.

Nejpřímočařejší variantou je ruletová selekce, při které jsou všechny nové vzorky vybírány náhodně a nezávisle. Protože tato metoda podle konkrétní implementace vyžaduje N binárních vyhledání vybraného vzorku [4] a nebo setřídění posloupnosti n náhodných hodnot podle velikosti [5], je časová složitost ruletové selekce O(n · log n).

Alternativní metodou je stochastické univerzální vzorkování. To vybírá náhodně pouze první vzorek, všechny další vzorky se poté vybírají po obvodu ruletového kola v pravidelných intervalech 1/n. Na rozdíl od ruletové selekce stochastické univerzální vzorkování garantuje, že vzorky s vahou alespoň 1/n převzorkování přežijí, resp. že vzorky s vahou alespoň c/n budou v nové reprezentaci zastoupeny alespoň c–krát. Časová složitost stochastického univerzálního vzorkování je lineární. Třetí možností je převzorkování v lineárním čase navržené v [4], které dokáže zkonstruovat uspořádanou posloupnost náhodných hodnot s rovnoměrným rozdělením na (0, 1) s časovou složitostí O(n). Dále potom funguje obdobně jako ruletová selekce. Uspořádaná posloupnost náhodných hodnot se přitom vytváří jako normovaný kumulativní součet záporných logaritmů z náhodných proměnných s rovnoměrným rozdělením na (0, 1).

Pro přehledné srovnání jsou všechny tři algoritmy pro převzorkování v Monte Carlo lokalizaci shrnuty v následující tabulce, a to tak, aby byly vidět rozdíly mezi jednotlivými algoritmy. Inicializace kumulativního součtu původních vah a vlastní převzorkování jsou potom pro všechny tři algoritmy společné.

Ruletová selekce O(n · log n)	Stochastické univerzální vzorkování O(n)	Převzorkování v lineárním čase O(n)
for (i=0; i<n; i++)   t[i] = rand(0, 1); T = sort(t); T[n] = 1;	T[0] = rand(0, 1/n); for (i=1; i<n; i++)   T[i] = t[t-1] + 1/n; T[n] = 1;	t[0] = -log(rand(0, 1)); for (i=1; i<=n; i++)   t[i] = t[i-1] +   (-log(rand(0, 1))); for (i=0; i<=n; i++)   T[i] = t[i]/t[n];
q[0] = w[0]; for (j=1; j<N; j++)   q[j] = q[j-1] + w[j]; /* Vlastní převzorkování */ i = 0; j = 0; while (i < n) {   if (T[i] < q[j]) {     novy_vzorek[i] = l[j];     nova_vaha[i] = 1/n;     i++;   } else {    j++;   } }
Časová složitost O(n · log n)	Časová složitost O(n)	Časová složitost O(n)

Tabulka 2.1: Porovnání jednotlivých algoritmů pro převzorkování odhadu polohy.

Na závěr zmíníme ještě jednoduchý způsob, kterým je možné zlepšit schopnost zotavení lokalizace při únosu robota. Za běhu Monte Carlo lokalizace se většina vzorků soustředí v místech pravděpodobného výskytu robota. Je-li robot unesen, ocitne se typicky v místě málo pravděpodobném, ve kterém se nemusí nacházet žádné vzorky. To představuje pro zotavení lokalizace vážný problém. Jednoduchým řešením je přidání náhodných, po celém prostoru rovnoměrně rozptýlených vzorků s velmi malou vahou. Tyto vzorky, které při nejbližším převzorkování budou typicky zase eliminovány, mohou být přidávány v pravidelných intervalech nebo při podezření na únos robota, které lze detekovat z prudkých změn odhadu polohy v korekčním kroku. Po únosu robota tyto vzorky dovolí rychlé nalezení nové pozice, na kterou byl robot přemístěn. Alternativním řešením je použití nějaké robustnější varianty Monte Carlo lokalizace, například výše zmíněné Mixture Monte Carlo Localization.

---

⁵ Aby nemohlo dojít k záměně indexu vzorku a čísla kroku, budeme jednotlivé exempláře vzorků označovat horními indexy a jednotlivé kroky indexy dolními.

⁶ Diskrétní Diracův impulz je definován následovně: δ(x) = 1 pro x = 0; δ(x) = 0 jinak.

2.7.2 Spojité reprezentace odhadu polohy

Při spojité reprezentaci je odhad polohy reprezentován vhodně zvoleným spojitým rozdělením pravděpodobnosti, které lze v celém prostoru přesně vyjádřit prostřednictvím pevného a typicky nízkého počtu parametrů zvolené spojité funkce. Aktualizace odhadu polohy v predikčním i korekčním kroku potom spočívá právě v přepočítání těchto parametrů zvolené funkce. V rámci této práce popíšeme jedinou techniku spojité reprezentace odhadu polohy, a to Kalmanův filtr. Ten představuje v této kategorii nejvýznamnější metodu pro odhad aktuálního stavu dynamického systému na základě šumem zatížených měření.

2.7.2.1 Kalmanův filtr

Kalmanův filtr reprezentuje hustotu odhadu polohy prostřednictvím normálního neboli Gaussova rozdělení. To je charakterizováno pouze dvěma parametry: střední hodnotou, která popisuje, kde má zvonovitá Gaussova křivka svůj vrchol, a rozptylem, který vyjadřuje, jak je Gaussova křivka široká. Normální rozdělení je unimodální, Gaussova křivka má tedy vždy jeden jediný vrchol a na rozdíl od dříve popsaných reprezentací tak není schopná vyjádřit více hypotéz o různých polohách robota současně.

Přesná reprezentace odhadu polohy pouhými dvěma hodnotami, střední hodnotou a rozptylem, je prostorově a také výpočetně mnohem méně náročná než u všech dříve popsaných metod, u kterých byla přesnost reprezentace úměrná počtu hodnot (buněk, uzlů nebo vzorků) v reprezentaci používaných. Na druhou stranu vzorce pro aktualizaci odhadu polohy a matematické odvození těchto vzorců jsou poněkud složitější, kvůli prostorovým limitům proto v této práci představíme jen základní myšlenky Kalmanova filtru. Detailní popis této metody je možno nalézt v [6] nebo [2].

Daní za nižší výpočetní i prostorovou náročnost reprezentace odhadu polohy pomocí normálního rozdělení jsou mnohem silnější předpoklady ve srovnání s dříve popsanými metodami. Ty zajišťují, aby po zahrnutí relativních a absolutních měření v predikčním resp. korekčním kroku zůstal odhad polohy ve tvaru popsatelném normálním rozdělením. Předně Kalmanův filtr předpokládá tzv. lineární dynamický systém – tedy systém proměnný v čase, jehož model lze vyjádřit pomocí lineárních rovnic. K řešení odhadu stavu nelineárních systémů, mezi které patří i lokalizující se roboti [6], lze potom použít složitější variantu této metody – rozšířený Kalmanův filtr (v angličtině Extended Kalman Filter).

Další předpoklady jsou pak kladeny na absolutní a relativní měření, respektive na senzorický model a pravděpodobnostní pohybový model. Kalmanův filtr požaduje, aby oba modely měly, stejně jako odhad polohy, podobu normálního rozdělení pravděpodobnosti. To je zejména pro senzorický model velmi silný předpoklad, který zcela diskvalifikuje použití celé řady potenciálně možných absolutních měření. Mezi absolutní měření a pozorování, které při použití Kalmanova filtru k upřesnění odhadu polohy použít nelze, zatímco při použití jiných metod na zpracování dat ano, patří například rozpoznávání barvy pod robotem pohybujícím se po šachovnici, detekce neunikátního orientačního bodu (roh místnosti, dveře, obrubník, …) nebo naměření vzdálenosti k jednomu majáku.

Požadavek normálního rozdělení senzorického a pravděpodobnostního pohybového modelu se interpretuje také tak, že naměřený výsledek absolutního nebo relativního měření je součtem ideálně přesného měření a náhodné chyby neboli šumu. Kalmanův filtr přitom předpokládá, že tento šum bude nezávislý, bílý (nekorelovaný v čase), s nulovou střední hodnotou a normálním rozdělením. Samotný proces lokalizace se od ostatních metod principiálně nijak neliší. Po inicializaci, při které je odhad polohy podle znalosti počáteční polohy robota inicializován úzkým nebo širokým normálním rozdělením, se střídají predikční a korekční kroky.

• V predikčním kroku se podle relativního měření upraví odhad polohy, rozptyl odhadu polohy se přitom vždy zvětšuje, a to právě o míru nejistoty zanesenou do odhadu zahrnutím posledního omezeně přesného relativního měření.
• V korekčním kroku se aposteriorní odhad polohy vypočítává v zásadě jako vážený průměr apriorního odhadu polohy a polohy odhadnuté absolutním měřením. Parametr, který určuje váhu apriorního odhadu polohy a odhadu z absolutního měření ve váženém průměru, se nazývá Kalmanův zisk (anglicky Kalman gain), a je závislý na rozptylech obou odhadů. Do aposteriorního odhadu je tak zahrnut větší měrou ten z odhadů, jehož rozptyl je menší. V korekčním kroku se rozptyl odhadu polohy snižuje – po provedení korekčního kroku je vždy menší nebo roven rozptylům obou odhadů, které se v korekčním kroku kombinují.

Lokalizace je pouze jednou z mnoha možných aplikací Kalmanova filtru. Kalmanovy filtry se používají v širokém spektru oblastí, mimo jiné v navigaci, předzpracování senzorických dat, počítačovém vidění, sledování stavu pomocí nepřímých měření, ale například také v ekonometrii. Lze dokázat, že při splnění všech předpokladů je odhad získaný prostřednictvím Kalmanova filtru optimální (viz [6], kapitola 1.4), mimo jiné proto, že filtr využívá všechna dostupná data i informace o jejich nejistotách.

2.7.3 Srovnání reprezentací odhadu polohy

V této části jsme se podrobně zabývali třemi nejpoužívanějšími diskrétními reprezentacemi odhadu polohy – pravděpodobnostní mřížkou, topologickými grafy a Monte Carlo lokalizací – a jednou reprezentací spojitou – Kalmanovým filtrem. Na závěr nyní stručně porovnáme jejich nejdůležitější vlastnosti a krátce shrneme nejzásadnější rozdíly mezi nimi.

Všechny diskrétní reprezentace aproximují odhad polohy prostřednictvím konečného počtu hodnot, přesnost reprezentace je přitom úměrná jejich počtu. Dovolují reprezentovat multimodální rozdělení, umožňují globální lokalizaci a dokáží vyřešit problém uneseného robota.

Pravděpodobnostní mřížka reprezentuje odhad polohy pomocí hodnot v buňkách pravidelné trojrozměrné mřížky. Jde o jednoduchou a přitom univerzální metodu, její nevýhodou je ale relativně značná výpočetní náročnost a omezená přesnost. Existují úpravy a optimalizace, které dokáží výpočetní náročnost snížit, ovšem za cenu složitější implementace takto upravené metody. Pravděpodobnostní mřížka se v robotice používá nejen k lokalizaci, ale také k mapování.

Topologické grafy reprezentují odhad polohy prostřednictvím hodnot v jednotlivých uzlech grafu. Na rozdíl od ostatních metod nejsou univerzální metodou; vyžadují strukturované prostředí a jeho grafový popis. Kvůli řádově menšímu stavovému prostoru jsou na jedné straně méně přesné, na druhou stranu ale mají velmi nízkou výpočetní náročnost. Jejich další nevýhodou proti zbývajícím popsaným metodám je nemožnost přímého použití senzorických dat a nutnost jejich předzpracování.

Monte Carlo lokalizace využívá k reprezentaci odhadu polohy množinu vážených vzorků. Jedná se o univerzální metodu pro reprezentaci jakéhokoliv odhadu polohy, ve srovnání s pravděpodobnostní mřížkou je ale díky dynamickému umístění vzorků v prostoru přesnější a efektivnější. Na rozdíl od předcházejících metod vyžaduje občasné převzorkování, které brání degeneraci reprezentace. Změnou počtu vzorků dovoluje Monte Carlo lokalizace za běhu přizpůsobovat výpočetní náročnost a přesnost lokalizace.

Kalmanův filtr reprezentuje odhad polohy pomocí Gaussovy křivky. Tu lze přesně vyjádřit pouhými dvěma parametry, střední hodnotou a rozptylem, neumožňuje ale reprezentovat více hypotéz o různých polohách robota současně. Kvůli tomu je Kalmanův filtr vhodný spíše pro sledování pozice než pro globální lokalizaci, kromě lokalizace je ale využíván i v mnoha dalších aplikacích. Kalmanův filtr má nižší prostorovou i časovou náročnost než výše popsané diskrétní reprezentace odhadu polohy, to je ale vykoupeno přísnými předpoklady na charakter prováděných měření, jejichž modely musejí mít normální rozdělení pravděpodobnosti. Kvůli tomu nelze některá jinak užitečná měření v Kalmanově filtru vůbec použít.

2.8 Alternativní metody k pravděpodobnostní lokalizaci

Dalšími možnými a přirozenými způsoby práce s nepřesnými daty z více senzorů jsou například fuzzy logika nebo intervalový počet. Ačkoliv se tyto alternativy k pravděpodobnostní lokalizaci obecně pro zpracování dat z více senzorů příliš nepoužívají, stojí alespoň za krátkou zmínku a představení jejich principu.

Fuzzy logika umožňuje ohodnocovat logické výroky resp. náležení prvku do nějaké množiny mírou pravdivosti resp. mírou příslušnosti k množině, jež může nabývat jakékoliv hodnoty mezi nulou (nepravda, nenáleží) a jedničkou (pravda, náleží). Tím se liší od klasické logiky, ve které je každý výrok buď pravdivý, nebo nepravdivý, a kde každý prvek do určité množiny buď náleží, nebo nenáleží. Díky tomu dovoluje fuzzy logika vyjádřit nepřesnost informací poskytnutých senzory i reprezentovat ne zcela jistou pozici robota v prostoru. Stejně jako klasická logika, i fuzzy logika má svoje dobře definovaná pravidla a zákony pro operace s výroky a množinami.

Intervalový počet charakterizuje každou veličinu prostřednictvím intervalu, v němž se její hodnota nachází. To umožňuje přirozeně reprezentovat veličiny, které jsou v určitých pevných a konečných mezích nepřesné. Typickým příkladem takovéto omezené přesnosti je konečné rozlišení kvantované veličiny z jakéhokoliv senzoru. Rozdělení pravděpodobnosti takové veličiny nemusí být známé, intervalový počet pravděpodobnostní rozdělení (ani rovnoměrné) jednotlivých veličin v daných intervalech nepředpokládá. Pro základní matematické operace s intervaly předepisuje intervalový počet pravidla, která jsou sice naprosto korektní, při použití na zpracování dat z více senzorů ale vedou k příliš pesimistickým výsledkům: výsledný interval sice obsahuje skutečnou polohu robota, je ale současně natolik rozsáhlý, že je v praxi pro lokalizaci robota zcela nepoužitelný.

2.9 Shrnutí kapitoly

V této kapitole jsme se zabývali pravděpodobnostní lokalizací jakožto nejdůležitější metodou pro zpracování omezeně přesných dat z více senzorů. Úvodem jsme vysvětlili, že kvůli nedokonalosti jednotlivých technik relativní i absolutní lokalizace je kombinování dat z různých měření nutné ke spolehlivému, robustnímu a přesnému odhadu polohy robota, a že pravděpodobnostní přístup je přirozeným způsobem řešení tohoto problému.

Nejprve jsme zadefinovali pravděpodobnostní odhad polohy jako hustotu pravděpodobnosti výskytu robota na jednotlivých pozicích prostoru, v němž se má robot lokalizovat. Poté jsme se zabývali samotným procesem lokalizace, který se skládá z jednorázové inicializace, při které je do výchozího odhadu polohy zahrnuta případná znalost počáteční polohy robota, a střídajících se predikčních a korekčních kroků, při kterých je odhad aktualizován podle dat z posledních relativních respektive absolutních měření. Věnovali jsme se také popisu pravděpodobnostního pohybového modelu a senzorického modelu, které se v predikčních a korekčních krocích využívají. Nakonec jsme vyjádřili kompletní rekurzivní vzorec pro aktualizaci odhadu polohy po získání relativních a absolutních měření.

V další části této kapitoly jsme se zabývali různými způsoby reprezentace odhadu polohy a jejich vzájemnými rozdíly, týkajícími se mimo jiné jejich přesnosti, výpočetní náročnosti, složitosti implementace nebo předpoklady nutnými pro jejich správné fungování. Celkem jsme přitom představili tři různé diskrétní reprezentace a jednu reprezentaci spojitou.

V závěru kapitoly jsme nakonec zmínili také dvě potenciální, avšak zřídkakdy používané alternativy k pravděpodobnostní lokalizaci. Hlavní slabinou těchto alternativních metod je nevyužití všech informací z dostupných lokalizačních dat a z toho plynoucí horší výsledky ve srovnání s pravděpodobnostní lokalizací.