Diplomová práce
Plánování cesty robota ve spojitém prostředí vypracoval: Michal Šíma vedoucí práce: RNDr. Jiří Dvořák, CSc. obor: Inženýrská informatika a automatizace specializace: Informatika 2006
Strana 2
Strana 3 Vysoké učení technické v Brně, Fakulta strojního inženýrství Ústav: Ústav automatizace a informatiky Akademický rok 2005/2006
ZADÁNÍ DIPLOMOVÉ PRÁCE pro: Michala Šímu který/která studuje v magisterském studijním programu obor: Inženýrská informatika a automatizace
Ředitel ústavu Vám v souladu se zákonem č.111/1998 o vysokých školách a se Studijním a zkušebním řádem VUT v Brně určuje následující téma diplomové práce: Plánování cesty robota ve spojitém prostředí
v anglickém jazyce: Robot Path Planning in Continuous Environment
Stručná charakteristika problematiky úkolu a cíle diplomové práce: Úkolem systému pro plánování dráhy robota je najít cestu z výchozího do cílového bodu tak, aby se robot nedostal do kolize se známými překážkami a aby nebyla porušena případná omezení kladená na pohyb robota.. Cíle diplomové práce: 1. Analyzovat problematiku plánování dráhy robota se zaměřením na metody RRT (Rapidly-exploring Random Trees). 2. Popsat vybrané metody a případně navrhnout jejich modifikace. 3. Prozkoumat možnost kombinace těchto metod s případovým usuzováním. 4. Implementovat vybrané a navržené metody a na základě výpočetních experimentů provést jejich srovnání.
Strana 4 Rozsah grafických prací: dle požadavků vedoucího práce Rozsah průvodní zprávy: cca 50 stran Seznam odborné literatury: [1] Meyer J.-A., Filliat D.: Map-Based Navigation in Mobile Robots: II. A Review of Map-Learning and Path-Planning Strategies. Cognitive Systems Research, 4 (2003), pp. 283-317. [2] LaValle, S.M., Kuffner, J.J.: "Rapidly Exploring Random Trees: Progress and Prospects". In proceedings of the Workshop on the Algorithmic Foundation, 2000. [3] Haigh K.Z., Shewchuk J.R.: Geometric Similarity Metrics for Case-Based Reasoning. In Case-Based Reasoning: Working Notes from the AAAI-94 Workshop, Seattle, WA, August 1994, AAAI Press, p. 182-187.. [4] Rouzek, P. Plánování dráhy robota pomocí případového usuzování. Diplomová práce. VUT FSI, Brno, 2005.
Vedoucí diplomové práce: RNDr. Jiří Dvořák CSc.
Termín odevzdání diplomové práce je stanoven časovým plánem akademického roku 2005/06. V Brně dne L.S.
Doc. RNDr. Ing. Miloš Šeda, Ph.D ředitel ústavu
Prof. Ing. Josef Vačkář, CSc. děkan
Strana 5
Anotace Tato práce se zabývá plánováním cesty robota pomocí pravděpodobnostních stromů (RRT) a analyzuje možnosti jejich použití v kombinaci s případovým usuzováním (CBR). Teoretická část obsahuje popis základních pojmů, přehled metod používaných pro plánování cesty robota, popis pravděpodobnostních stromů a případového usuzování. Praktická část popisuje implementaci navržené metody, která pro plánování cesty neholonomického mobilního robota ve dvourozměrném pracovním prostoru se statickými polygonálními překážkami používá pravděpodobnostní stromy s případovým usuzováním. Tato práce byla zpracována v rámci vědecko-výzkumného záměru MSM 0021630518 "Simulační modelování mechatronických soustav".
Annotation This thesis deals with robot path planning by means of Rapidly-exploring Random Trees (RRT) and analyzes possibilities of their use in combination with Case-Based Reasoning (CBR). The theoretic part contains description of basic terms, overview of robot path planning methods, description of RRT and CBR. The practical part describes implementation of proposed method using RRT with CBR for path planning of nonholonomic mobile robot in 2D workspace with static polygonal obstacles. This thesis was created in the project MSM 0021630518 "Simulation Modelling of Mechatronic Systems".
Strana 6
Strana 7
Obsah 1. 2.
Úvod .............................................................................................................................. 9 Robot a okolní prostředí ........................................................................................... 11 2.1 Autonomní mobilní robot .................................................................................... 11 2.2 Pracovní prostor................................................................................................... 12 2.3 Konfigurační prostor ........................................................................................... 12 2.4 Metrika v konfiguračním prostoru....................................................................... 13 3. Plánování pohybu ...................................................................................................... 15 3.1 Globální a lokální plánování................................................................................ 15 3.2 Holonomické a neholonomické plánování .......................................................... 15 3.3 Kompletní algoritmy plánování pohybu.............................................................. 15 4. Metody pro plánování cesty robota ......................................................................... 17 4.1 Metody rozkladu do buněk .................................................................................. 17 4.1.1 Exaktní rozklad............................................................................................ 17 4.1.2 Aproximativní rozklad................................................................................. 18 4.2 Mapy cest............................................................................................................. 18 4.2.1 Deterministické metody............................................................................... 18 4.2.1.1 Graf viditelnosti....................................................................................... 18 4.2.1.2 Redukovaný graf viditelnosti (graf tečen) ............................................... 19 4.2.1.3 Voronoiův diagram.................................................................................. 19 4.2.2 Pravděpodobnostní metody ......................................................................... 20 4.2.2.1 Pravděpodobností mapy cest (Probabilistic Roadmaps – PRM) ............. 20 4.2.2.2 Pravděpodobnostní stromy (Rapidly-exploring Random Trees – RRT) . 21 4.3 Potenciálová pole................................................................................................. 21 5. Pravděpodobnostní stromy (Rapidly-exploring Random Trees – RRT) ............. 23 5.1 Základní algoritmus RRT .................................................................................... 23 5.1.1 Popis základního algoritmu RRT ................................................................ 24 5.2 Plánovače na bázi RRT........................................................................................ 25 5.2.1 Plánovač se spádem k cíli (RRT-GoalBias) ................................................ 25 5.2.2 Plánovač se zaměřením na cíl (RRT-GoalZoom)........................................ 25 5.2.3 Dvoustromový RRT plánovač ..................................................................... 25 5.2.4 Ostatní vylepšení RRT plánovače ............................................................... 26 5.2.5 Limitní případ RRT plánovače .................................................................... 26 5.3 Vlastnosti RRT .................................................................................................... 26 5.3.1 Vysvětlení některých vlastností RRT.......................................................... 26 6. Případové usuzování (Case-Based Reasonig – CBR) ............................................. 29 6.1 Historie ................................................................................................................ 29 6.2 Základní pojmy CBR........................................................................................... 30 6.2.1 Případy......................................................................................................... 30 6.2.2 Případová báze............................................................................................. 30 6.3 Účinnost CBR...................................................................................................... 30 6.4 Proces případového usuzování ............................................................................ 31 6.4.1 Nalezení případu.......................................................................................... 31 6.4.2 Použití případu............................................................................................. 32 6.4.3 Ověření případu ........................................................................................... 32 6.4.4 Uchování případu ........................................................................................ 32 6.5 CBR a plánování cesty robota ............................................................................. 33 7. Implementace ............................................................................................................. 35 7.1 Model robota ....................................................................................................... 35
Strana 8 7.2 Metrika ................................................................................................................ 36 7.3 Inkrementální simulátor ...................................................................................... 36 7.4 Překážky a detekce kolizí.................................................................................... 37 7.5 RRT ..................................................................................................................... 38 7.6 CBR..................................................................................................................... 40 7.6.1 Vzorkování .................................................................................................. 41 7.6.2 Přidání nové cesty do případového grafu .................................................... 41 7.6.3 Optimalizace případového grafu ................................................................. 42 7.6.4 Nalezení vhodného případu v případovém grafu ........................................ 42 7.7 Algoritmus RRT s CBR ...................................................................................... 43 8. Editor překážek ......................................................................................................... 47 8.1 Funkce pro kreslení a práci s objekty.................................................................. 47 8.2 Požadavky programu na PC ................................................................................ 48 9. Simulační program.................................................................................................... 49 9.1 Hlavní okno programu ........................................................................................ 49 9.2 Hlavní menu a příkazy ........................................................................................ 50 9.2.1 Příkazy v nabídce Akce............................................................................... 50 9.2.2 Příkazy v nabídce Nastavení ....................................................................... 50 9.3 Nastavení RRT metody ....................................................................................... 51 9.4 Načtení překážek ................................................................................................. 52 9.5 Nastavení robota.................................................................................................. 52 9.6 Nastavení CBR .................................................................................................... 52 9.7 Generování náhodných konfigurací robota ......................................................... 53 9.8 Zobrazení výsledků a import do Excelu.............................................................. 54 9.9 Požadavky programu na PC ................................................................................ 55 10. Experimenty........................................................................................................... 57 10.1 Stanovení optimální velikosti případového grafu ............................................... 58 10.2 Srovnání RRT a RRT+CBR................................................................................ 59 11. Závěr....................................................................................................................... 61
Strana 9
1. Úvod Během posledních tří desetiletí se plánování pohybu robota ukázalo jako rozhodující a produktivní výzkumná oblast robotiky. Základním problémem plánování pohybu je nalezení nekolizní cesty robota mezi statickými překážkami. To je čistě geometrický problém, který vypadá zdánlivě jednoduše. Ve skutečnosti, s výjimkou robotů s několika málo stupni volnosti, je výpočetně velmi náročný. V polovině 80. let byla většina rozšířených plánovačů stěží schopná spočítat nekolizní cesty pro posouvající se a rotující rovinné objekty ve dvoudimenzionálních pracovních prostorech. Od té doby byl učiněn velký pokrok a dnešní plánovače běžně řeší složité praktické problémy často zahrnující roboty s mnoha stupni volnosti v komplikovaných prostředích. Příkladem může být plánovač použitý neurochirurgy k výpočtu pohybu kloubového robota s lineárním pohonem (Cyberknife) pro operaci nádorů mozku. Jako další příklad lze uvést plánovač, který byl úspěšně použit při montáži řídící sekce střely vzduch-vzduch Huges AIM-9X (sestava obsahovala 472 částí popsaných 55 MB dat z CAD systému). V posledních 10 letech bylo uvedeno množství nových algoritmů pro plánování pohybu, které jsou mimořádně úspěšné v řešení náročných problémů plánování pohybu, včetně problémů s mnoha stupni volnosti. Příkladem nových technik je plánovač cesty založený na náhodě použitý u pravděpodobnostních map cest (Probabilistic Roadmaps) nebo pravděpodobnostních stromů (Rapidly-exploring Random Trees). Plánování pohybu našlo uplatnění i mimo oblasti tradiční robotiky, jako jsou průmyslový design, počítačová animace a počítačové hry, mikroinvazivní chirurgie, spojování a dělení molekul. Problémy vyplývající z těchto oblastí jsou předmětem výzkumu plánování pohybu přinejmenším stejně jako množství robotických problémů. Základní problém plánování pohybu lze rozšířit o pohybující se překážky, kinematická a dynamická omezení pohybu robota, výpočet optimálních trajektorií nebo koordinaci více robotů. Podobně jako základní problém plánování pohybu, některá z těchto rozšíření, mají řešení, která mohou být použita v praxi, ale ještě vyžadují větší výzkum. Změny v robotických technologiích, stejně tak jako jejich nové aplikace, vyvolávají nové druhy problémů, které je třeba řešit.
Strana 10
Strana 11
2. Robot a okolní prostředí Robot je mechanické zařízení, které je schopné provádět naprogramované úlohy. Robot může pracovat pod přímým řízením člověka (např. robotická ruka raketoplánu) nebo autonomně pod řízením naprogramovaného počítače. Roboty lze rozdělit na manipulátory (průmyslové roboty) a mobilní roboty. Mobilní roboty mají schopnost se přesouvat po svém pracovním prostředí a nejsou fixovány na jednu fyzickou lokaci. V kontrastu s nimi manipulátory tvoří kloubová ruka, která je připevněna k pevnému povrchu. Nejběžnější skupinou mobilních robotů jsou roboty s koly. Druhou skupinu tvoří chodící roboty a poslední nejmenší skupina obsahuje létající roboty (např. bezpilotní letadla). Nás budou zajímat v této práci především autonomní mobilní roboty.
2.1 Autonomní mobilní robot Autonomní mobilní robot je inteligentní stroj schopný vykonávat úkoly samostatně, bez lidské pomoci. Příkladem takového robota může být autonomní helikoptéra, ale i autonomně řízený automobil.
Obr. 1 Autonomní mobilní robot Rover Sojourner na Marsu (NASA) Nejdůležitější vlastností autonomního robota je jeho schopnost reagovat na změny. Za tu většinou vděčí svému mozku – počítači, který je zodpovědný více méně za vše, počínaje zpracováváním vstupních údajů, rozhodováním i konečným provedením vybraných akcí. Vstupní údaje počítači poskytují senzory. Senzor je zařízení, které je schopné měřit nějakou vlastnost prostředí. Příkladem takového senzoru může být třeba i obyčejný spínač. Tento spínač může robot využít jako nárazník. Měřená vlastnost prostředí je tedy fakt, že se v cestě nachází překážka. Naopak působit na své prostředí může robot pomocí efektorů. Typickým příkladem efektoru je elektromotor. Po připojení na kolo umožní robotu pohyb. V závislosti na velikosti robota se můžeme setkat i s dalšími typy efektorů, ať už to jsou spalovací motory či hydraulika.
Strana 12 Z nutných součástí zbývá zmínit ještě zdroj energie, nejčastěji akumulátor, který poskytuje energii senzorům, počítači i většině efektorů. Větší roboty vybavené spalovacími motory mívají alternátory, které akumulátor průběžně dobíjí, a doba, po kterou je robot schopen operovat autonomně, je tím značně prodloužena. Některé roboty používají i solární panely (např. roboty vyslané na Mars). Pokud má robot mapu prostředí, ve kterém se pohybuje, tak ho zajímá, kde se nachází (lokalizace), případně jak se dostat na jiné místo (plánování). Pokud nemá robot mapu k dispozici, tak musí řešit souběžně lokalizaci i plánování. V této práci se budeme zabývat pouze případem, kdy robot má mapu prostředí a řeší tedy jenom problém plánování.
2.2 Pracovní prostor Každý robot se pohybuje v nějakém pracovním prostoru W. Pracovní prostor lze reprezentovat jako N-rozměrný euklidovský prostor RN, kde N = 2, 3 podle toho, jestli je dvourozměrný nebo trojrozměrný. V pracovní prostoru W se navíc mohou vyskytovat překážky, které omezují pohyb robota. Aby bylo možné matematicky popsat pozici a orientaci robota v pracovním prostoru, byl zaveden pojem konfigurační prostor C.
2.3 Konfigurační prostor Konfigurační prostor je množina všech konfigurací robota, ve kterých se může robot nacházet. Jeho dimenze odpovídá počtu stupňů volnosti robota. Při zvětšení překážek o tělo robota lze robot v konfiguračním prostoru C zredukovat na bod (obr. 2), čímž se problém jeho reprezentace značně zjednodušuje.
Obr. 2 Robot v pracovním prostoru W (vlevo) se redukuje na bod v C (vpravo) Konfigurace robota q představuje vektor, jehož složky jednoznačně určují pozici a orientaci robota v konfiguračním prostoru. Protože v pracovním prostoru robota se obvykle vyskytují různé překážky, nejsou všechny konfigurace robota přípustné. Proto byl zaveden volný konfigurační prostor Cfree. Volný konfigurační prostor je prostor všech konfigurací, které nekolidují s žádnou překážkou a ve kterých nejsou porušeny omezující podmínky kladené na robot (např. maximální úhel natočení kloubu). Jinými slovy jsou to všechny přípustné pozice robota. Protikladem volného konfiguračního prostoru Cfree je kolizní konfigurační prostor Cobs, který je definován jako prostor všech konfigurací robota, při kterých dochází ke kolizi robota s některou překážkou nebo jsou porušena omezení kladená na pohyb robota. Jedná se tedy o prostor všech nepřípustných konfigurací.
Strana 13 Aby plánování mohlo být vůbec úspěšné, musí start i cíl náležet volnému konfiguračnímu prostoru. Problém hledání cesty, případně sekvence dovolených pohybů se potom převede na hledání přípustné křivky ve volném konfiguračním prostoru. Pro robot ve dvourozměrném pracovním prostoru, který může provádět translaci a rotaci, vypadá situace následovně. Robot má tři stupně volnosti (translace je možná v osách x, y a rotace okolo osy z), takže konfigurační prostor je třírozměrný. Pozici robota v konfiguračním prostoru jednoznačně určují souřadnice x, y a natočení θ. Tedy q = (x, y, θ) ∈ R2 × [0, 2π). Celá situace je znázorněna na obr. 3.
pracovní prostor
robot
θ
konfigurační prostor
2π π
referenční směr y
θ y
cesta
referenční bod
x
x
Obr. 3 Pracovní a konfigurační prostor robota
2.4 Metrika v konfiguračním prostoru Plánovací algoritmus potřebuje funkci, která dokáže určit vzdálenost mezi dvěma body (konfiguracemi) v C. Vzdálenost dvou bodů d v prostoru je určena tzv. metrikou.
θ
konfigurační prostor
2π (x1,y1,θ1) y d
(x2,y2,θ2)
x Obr. 4 Vzdálenost d mezi dvěmi konfiguracemi robota v C
Strana 14
Metrika ρ v C je zobrazení ρ : (q1 , q 2 ) ∈ C 2 → ρ (q1 , q 2 ) ≥ 0 pro které platí: 1) podmínka totožnosti ρ(q1, q2) = 0 jestliže q1 = q2 2) podmínka symetrie ρ(q1, q2) = ρ(q2, q1) 3) podmínka trojúhelníkové nerovnosti ρ(q1, q2) ≤ ρ(q1, q3) + ρ(q3, q2) Hodnota ρ(q1,q2) se potom nazývá vzdáleností d. Speciálním, všeobecně známým, případem metriky je Euklidovská metrika. Ta je definována pro n-rozměrný Euklidovský prostor vztahem:
ρ ( X , Y ) = ( x1 − y1 ) 2 + ( x 2 − y 2 ) 2 + ... + ( x n − y n ) 2 kde X = (x1, x2,…, xn) ∈ Rn a Y = (y1, y2,…, yn) ∈ Rn. V praxi se potom používají různé druhy metrik (Euklidovská je pouze jednou z nich) podle vhodnosti pro řešenou úlohu. Popis různých metrik lze nalézt např. v [4].
Strana 15
3. Plánování pohybu 3.1 Globální a lokální plánování Cílem globálního plánování je nalezení nekolizní cesty z počáteční do cílové konfigurace. Globální plánování se provádí ještě před tím, než robot vykoná první pohyb a vyžaduje, aby prostředí bylo kompletně známé, tzn. aby byla k dispozici mapa, a to včetně všech statických překážek, kterým je třeba se vyhnout. Tato cesta se poté předá lokálnímu plánovači, který podle ní řídí robota a zohledňuje případná omezení (omezení pohybu robota, nové překážky apod.), které se vyskytnou během průchodu po cestě. Úkolem lokálního plánování je tedy vlastní řízení pohybu robota po cestě, která se naplánuje při globálním plánování. U některých metod není hranice mezi lokálním a globálním plánováním úplně zřejmá, a proto je problém je od sebe na první pohled odlišit.
3.2 Holonomické a neholonomické plánování Podle omezení kladených na pohyb robota rozlišujeme dva základní druhy plánování pohybu – holonomické a neholonomické. V klasické mechanice může být systém definován jako holonomický pokud všechna jeho omezení jsou holonomická. Holonomická omezení jsou taková, která lze vyjádřit jako funkce f(x1, x2, x3,...xn , t) = 0, tj. omezení závisí pouze na souřadnicích systému a času. Omezení nezávisí na rychlosti nebo hybnosti systému. Příkladem holonomického systému je například jednoduché kyvadlo o délce L vyjádřené jako ( x 2 + y 2 ) − L = 0 . V robotice holonomičnost vyjadřuje vztah mezi počtem řiditelných stupňů volnosti robota a jejich celkovým počtem. Jestliže počet řiditelných stupňů volnosti je stejný jako jejich celkový počet, potom můžeme říct, že robot je holonomický. Pokud je počet řiditelných stupňů volnosti menší než jejich celkový počet, potom je robot neholonomický. Příkladem neholonomického systému je auto, protože jeho pohyb do stran je omezen maximálním natočením předních kol.
3.3 Kompletní algoritmy plánování pohybu Algoritmus pro plánování pohybu je kompletní, pokud garantuje nalezení cesty mezi dvěma danými konfiguracemi robota, jestliže cesta existuje, a v opačném případě ohlásí, že cesta neexistuje. Kompletní algoritmy jsou někdy označovány jako exaktní.
Strana 16
Strana 17
4. Metody pro plánování cesty robota Metod pro plánování cesty robota existuje poměrně velké množství a každá z nich má spoustu různých subvariant, které vznikly modifikací původního algoritmu. Proto budou uvedeny v následujícím přehledu jen ty základní. Podrobnější informace lze nalézt např. v [4, 6, 11]. V podstatě lze rozlišit tři skupiny plánovacích metod: 1) Metody rozkladu do buněk (Cell decomposition) 2) Mapy cest (Roadmaps) 3) Potenciálová pole (Potential fields) Každá metoda má dvě fáze. V první fázi se provádí tzv. předzpracování, kdy se metoda snaží popsat volný pracovní prostor robota pomocí grafu nebo funkce. Ve druhé fázi tzv. dotazovací je vyhledávána cesta v grafu mezi počáteční a cílovou konfigurací robota. K vyhledání cesty je možné použít různé druhy algoritmů pro nalezení cesty v grafu (např. Dijkstrův algoritmus, algoritmus A*). Často se také používají, především u metod rozkládajících prostředí do buněk, genetické algoritmy.
4.1 Metody rozkladu do buněk Tato skupina metod nejprve rozloží pracovní prostor do buněk různého tvaru. U každé z buněk se určí, jestli obsahuje překážku nebo ne. Z buněk, které neobsahují překážku, se vytvoří vrcholy grafu. Vrcholy představující sousední buňky se spojí hranou. V takto vytvořeném grafu se potom vyhledává cesta. K dělení do buněk se používá exaktní nebo aproximativní rozklad.
4.1.1
Exaktní rozklad
Základní myšlenkou je rozdělit volný prostor do množiny nepřekrývajících se buněk. Jejich tvar by měl být jednoduchý, aby bylo možné jednoduše spočítat cestu mezi dvěma pozicemi robota uvnitř buňky. Musí být také snadné zjistit hranice mezi buňkami, protože je nutné určit bod přejezdu do sousední buňky. Jako buňky se často používají lichoběžníky nebo trojúhelníky. Tato metoda je kompletní, tzn. že vždy nalezne cestu (pokud existuje), v opačném případě ověří, že neexistuje.
Obr. 5 Cesta nalezená pomocí exaktního rozkladu
Strana 18
4.1.2
Aproximativní rozklad
U této metody se rozkládá do buněk celý pracovní prostor (i překážky). Všechny buňky mají stejný tvar, který je velmi jednoduchý, např. čtverce. Proto je výpočet rozkladu podstatně jednodušší než u exaktního způsobu, kde jsou tvary buněk složitější. Existuje i varianta rozkladu do kvadrantů, u níž není velikost buňky konstantní. Tato metoda není kompletní, protože se může stát, že nenajde cestu, která ve skutečnosti existuje. To je způsobeno tím, že za překážku se považuje i buňka, jejíž prostor překážka vyplňuje jen částečně.
Obr. 6 Aproximativní rozklad na čtvercové buňky konstantní velikosti
4.2 Mapy cest Metody patřící do této skupiny vytváří graf (tzv. roadmapu) reprezentující volný pracovní prostor. Jeho hrany představují cesty, po kterých se může robot pohybovat. Vrcholy tvoří různé body v pracovním prostoru (podle konkrétní metody). Pokud do grafu přidáme počáteční a cílovou pozici robota jako další vrcholy grafu, přechází problém nalezení cesty ze startu do cíle na problém hledání cesty v grafu. K nalezení cesty se používají standardní algoritmy pro hledání cesty v grafu. Metody map cest lze dále rozdělit na deterministické a pravděpodobnostní.
4.2.1
Deterministické metody
4.2.1.1 Graf viditelnosti Vrcholy grafu tvoří start, cíl a vrcholy překážek. Hrany grafu představují spojnice vrcholů, které neprochází žádnou překážkou. Mezi hrany grafu je možné zařadit i hrany překážek. Graf viditelnosti lze aplikovat jenom na pracovní prostor s polygonálními překážkami. Nepolygonální překážky (např. kružnice) musí být nahrazeny polygonem, který co nejvíce odpovídá jejich tvaru.
Strana 19
Obr. 7 Graf viditelnosti
4.2.1.2 Redukovaný graf viditelnosti (graf tečen) Princip je stejný jako u grafu viditelnosti, ale jako hrany se berou jenom tečny. Hledání cesty je oproti grafu viditelnosti rychlejší (menší počet hran) a je možné použít i nepolygonální překážky.
Obr. 8 Redukovaný graf viditelnosti
4.2.1.3 Voronoiův diagram Robot se pohybuje po hranách Voronoiova diagramu pro množinu překážek, které určují možné průchody mezi překážkami maximalizující vzdálenost od překážek. Výjimkou jsou pouze první a poslední úsek cesty. Po jejich zahrnutí se nalezení optimální trasy robota redukuje na určení nejkratší cesty po hranách Voronoiova diagramu mezi jeho body danými koncovými body přidaných úseků. Tuto úlohu lze řešit např. Dijkstrovým algoritmem.
Strana 20
Obr. 9 Voronoiův diagram
4.2.2
Pravděpodobnostní metody
4.2.2.1 Pravděpodobností mapy cest (Probabilistic Roadmaps – PRM) Algoritmus funguje ve dvou fázích – učící a dotazovací. V první fázi se vygeneruje graf cest (roadmapa) a ve druhé fázi se hledá cesta v grafu. 1) fáze učení Graf cest je pravděpodobnostní – náhodně se vybírá konfigurace robota a ověřuje se zda náleží do Cfree. Pokud ano, tak je vytvořen nový vrchol grafu a algoritmus se pokouší tuto konfiguraci propojit s ostatními přímou cestou. Je-li tato cesta celá v Cfree, přidá do grafu novou hranu. Tento proces opakuje, dokud je dostatek času, paměti, případně je možné použít složitější test, zda již vzniklý graf dobře popisuje Cfree.
Obr. 10 Učící fáze 2) fáze zpracování dotazu na cestu V druhé fázi je třeba nejprve napojit start a cíl. To se provádí stejným způsobem jako náhodné konfigurace popsané v předešlém odstavci. Pak se hledá cesta v grafu. Pokud existuje, tak je zaručeno, že je platná. Pokud však cesta nebyla nalezena, tak to ještě neznamená, že neexistuje, protože pokrytí v první fázi nemuselo být dostatečné. Aby se pokrytí zlepšilo, je možné opakovat první fázi.
Strana 21
Obr. 11 Dotazovací fáze Pravděpodobnostní mapy fungují dobře především pro pracovní prostory se statickými překážkami, kdy stačí první fázi provést pouze jednou a druhá, dotazovací fáze, se může několikrát opakovat.
4.2.2.2 Pravděpodobnostní stromy (Rapidly-exploring Random Trees – RRT) Protože jsou základem této práce, budou popsány podrobně v následující kapitole.
4.3 Potenciálová pole Princip této metody spočívá v pokrytí celého pracovního prostoru potenciálovým polem, které je definováno jako potenciálová funkce E(x, y). Počáteční pozice robota má větší potenciál než cílová. Místa, kde jsou překážky, mají potenciál větší než jejich okolí (tvoří „kopce“). Robot hledající cestu se potom pohybuje ve směru opačného gradientu potenciálové funkce. Lze si ho tedy představit jako míč jedoucí z kopce.
Obr. 12 Potenciálové pole
Strana 22
Strana 23
5. Pravděpodobnostní stromy (Rapidly-exploring Random Trees – RRT) Tato metoda byla poprvé představena v [12] v roce 1998, jako metoda navržená pro širokou skupinu problémů plánování cesty se zaměřením především na neholonomické plánování (včetně dynamických omezujících podmínek) robotů s vysokým počtem stupňů volnosti. Základní myšlenkou je inkrementální vytváření prohledávajícího stromu, který se snaží rychle a rovnoměrně prohledat konfigurační prostor. Před použitím metody RRT je třeba definovat: 1) Konfigurační prostor C 2) Počáteční a cílovou konfiguraci qinit ∈ C a qgoal ⊂ C 3) Detektor kolizí Funkce D: C → {true, false}, která určuje zda konfigurace q ∉ Cfree. 4) Množinu vstupů U Specifikuje vstupy nebo akce, které mohou ovlivnit konfiguraci robota (např. natočení kol, rychlost apod.). 5) Inkrementální simulátor Počítá jakou konfiguraci q bude mít robot po čase ∆t, během kterého provádí akci u ∈ U. V podstatě jde o integraci pohybových rovnic robota. Pro integraci se používá některá numerická metoda (např. Eulerova nebo Runge-Kutta). 6) Metriku
5.1 Základní algoritmus RRT Následující algoritmus zapsaný v pseudojazyce představuje pouze základní verzi RRT algoritmu, tak jak byl popsán v [13] . function BUILD_RRT(qinit) 1) T.init(qinit); 2) for k = 1 to K do 3) qrand ← RANDOM_CONF( ); 4) EXTEND(T, qrand); 5) return T; function EXTEND(T, qrand) 1) qnear ←NEAREST_NEIGHBOR(qrand, T); 2) if NEW_CONF(qrand, qnear, qnew, unew) then 3) T.add_vertex(qnew); 4) T.add_edge(qnear, qnew, unew); 5) if qnew = qrand then 6) return Reached; 7) else 8) return Advanced; 9) return Trapped;
Strana 24
5.1.1
Popis základního algoritmu RRT
Strom T se vytváří iteračně tak, že se v každé iteraci rozroste směrem k náhodně vygenerované konfiguraci robota o nový vrchol. Vrcholy stromu představují konfigurace robota a jeho hrany akce robota. Funkce BUILD_RRT Ve funkci BUILD_RRT se nejprve za kořen stromu dosadí počáteční konfigurace robota qinit (krok 1). Potom se v K iteracích volají funkce RANDOM_CONF a EXTEND. Funkce RANDOM_CONF vygeneruje náhodnou konfiguraci robota qrand, která leží v jeho konfiguračním prostoru. Funkce EXTEND následně realizuje růst stromu směrem ke qrand. Funkce EXTEND Ve funkci EXTEND se nejdříve volá funkce NEAREST_NEIGHBOR (krok 1), která vybere vrchol stromu T s nejmenší vzdáleností od náhodné konfigurace qrand. Tento vrchol je označen jako qnear. K výpočtu vzdálenosti se použije zvolená metrika. Úkolem funkce NEW_CONF (krok 2) je spočítat pohyb robota z qnear do qrand. Tato funkce vlastně představuje inkrementální simulátor. Pohyb vznikne aplikací vstupu u∈U po nějaký časový inkrement ∆t (časový inkrement může být jiný než v integrační metodě). Vstup u může být vybrán náhodně, nebo se zkusí všechny možné vstupy a z nich se vybere ten, který je nejblíže k qrand. Jestliže je množina U nekonečná, pak se používá aproximace. Funkce NEW_CONF také volá funkci pro detekci kolizí, která zjistí, zda nová konfigurace qnew (a všechny mezilehlé konfigurace) robota je nekolizní a splňuje případná další omezení. Pokud funkce NEW_STATE skončí úspěšně, pak se nová konfigurace qnew vloží jako nový vrchol do stromu (krok 3) a spojí se hranou s nejbližším vrcholem stromu qnear (krok 4). Ohodnocením hrany je vstup unew vypočítaný ve funkci NEW_CONF. Mohou nastat tři situace, podle kterých vrací funkce EXTEND následující hodnoty: 1) Reached (dosažen) – nový vrchol qnew je totožný s qrand. Pro neholonomické plánování se netestuje úplná shoda qnew s konfigurací qrand, ale počítá se vzdálenost mezi qnew a qrand. Pokud je vzdálenost mezi nimi menší než nějaké δ, je qrand prohlášen za dosažený. Jako δ se volí malé kladné číslo. 2) Advanced (rozšířen) – nový vrchol qnew ≠ qrand byl vložen do stromu. 3) Trapped (uvězněn) – funkci NEW_STATE se nepodařilo nalézt novou konfiguraci ležící v Cfree. Princip tvorby stromu a činnost funkce EXTEND ukazuje obr. 13.
Obr. 13 Činnost funkce EXTEND
Strana 25
5.2 Plánovače na bázi RRT V principu může být jako plánovač použit i základní algoritmus RRT. V praxi se ovšem tato základní varianta RRT nepoužívá. Jejím hlavním problémem je především příliš pomalá konvergence k cíli, protože strom se rozrůstá na všechny strany stejně. K řešení tohoto a dalších problémů základní varianty RRT plánovače byly navrženy následující upravené verze. V praktických aplikacích se většinou používají jejich kombinace s různými vylepšeními a modifikacemi pro danou konkrétní aplikaci.
5.2.1
Plánovač se spádem k cíli (RRT-GoalBias)
Tento plánovač se vyznačuje podstatně rychlejší konvergencí stromu k cíli, než základní varianta RRT plánovače. Zrychlení je dosaženo malou úpravou funkce RANDOM_CONF. Spád stromu k cíli je vytvořen tím, že tato funkce vrací s malou pravděpodobností (např. 0,05) místo náhodné konfigurace, konfiguraci cílovou (qgoal). Pravděpodobnost ale nesmí být příliš velká, protože jinak se může stát, že dojde k uváznutí stromu v lokálním minimu.
5.2.2
Plánovač se zaměřením na cíl (RRT-GoalZoom)
Tato varianta zrychluje konvergenci stromu k cíli a zároveň zmenšuje riziko uváznutí v lokálním minimu, které hrozí u plánovače se spádem k cíli. Opět jde o modifikaci funkce RANDOM_CONF. Funkce RANDOM_CONF vrací náhodné konfigurace z nějakého okolí cílové konfigurace qgoal. Na začátku je toto okolí velké a jak se blíží strom k cíli, tak se velikost okolí zmenšuje. Stále ovšem hrozí uvíznutí v lokálním minimu. Všeobecně se zdá nejlepší nahradit funkci RANDOM_CONF funkcí generující náhodné konfigurace robota s nerovnoměrnou hustotou pravděpodobnosti, která roste směrem k cíli.
5.2.3
Dvoustromový RRT plánovač
Tento plánovač při prohledávání konfiguračního prostoru používá dva stromy místo jednoho. První strom roste z qinit a druhý z qgoal. Cesta je nalezena, když se oba stromy potkají. Algoritmus dvoustromového RRT plánovače popsaného v [13] vypadá takto: function RRT_BIDIRECTIONAL(qinit, qgoal) 1) Ta.init(qinit); Tb.init(qgoal); 2) for k = 1 to K do 3) qrand ← RANDOM_CONF(); 4) if not (EXTEND(Ta, qrand) = Traped) then 5) if (EXTEND(Tb, qnew) = Reached) then 6) return PATH(Ta, Tb); 7) SWAP(Ta, Tb); 8) return Failure; Funkce RRT_BIDIRECTIONAL rozděluje výpočet na dvě části. První část výpočtu tvoří prohledávání konfiguračního prostoru a druhou snaha o spojení obou stromů. V každé iteraci se jeden strom rozroste o nový vrchol qnew směrem k náhodné konfiguraci qrand (krok 4) a druhý strom se pokouší napojit na nový vrchol qnew v prvním stromu (krok 5). Potom se oba stromy prohodí (krok 7) a výpočet se opakuje. Cesta je nalezena, když dojde ke spojení obou stromů (krok 6). Problémem tohoto plánovače (především u neholonomického plánování) je napojení obou stromů na sebe.
Strana 26
5.2.4
Ostatní vylepšení RRT plánovače
Úpravou výrazně zrychlující konvergenci stromu ke qgoal je změna funkce EXTEND. Místo rozšiřování RRT inkrementačně po krocích, může být funkce EXTEND opakována, dokud strom nedosáhne náhodné konfigurace qrand nebo nedojde ke kolizi s překážkou. Algoritmus funkce CONNECT, která toto provádí, vypadá následovně: CONNECT(T, qrand) 1) repeat 2) S ← EXTEND(T, qrand); 3) until not (S = Advanced); 4) return S; Další možností, jak zrychlit konvergenci, je dynamicky měnit velikost kroku ε použitého pro konstrukci stromu. Pomocí dané metriky se zjistí vzdálenost aktuální konfigurace robota od nejbližší překážky. Pokud je robot daleko, může být krok větší, než když je blízko překážky.
5.2.5
Limitní případ RRT plánovače
V této poměrně extrémní variantě začíná nový strom růst z každé nově vygenerované náhodné konfigurace qrand. Vždy, když je vygenerován první vrchol stromu, tak se spustí funkce CONNECT. V případě, že funkce CONNECT uspěje, dojde ke spojení dvou stromů do jednoho grafu. Výsledkem je algoritmus, který se chová jako pravděpodobnostní mapy (PRM).
5.3 Vlastnosti RRT V této časti se zaměříme na některé vlastnosti RRT, které z této metody dělají ideální řešení pro širokou škálu praktických problémů plánování cesty. Strom má snahu růst směrem k ještě neprohledaným částem prostoru Algoritmus RRT je relativně jednoduchý Vrcholy stromu zůstávají vždy propojeny RRT algoritmus může být implementován jako speciální modul pro plánování cesty, který lze potom začlenit do různých plánovacích systémů 5) RRT algoritmus je pravděpodobnostně kompletní
1) 2) 3) 4)
5.3.1
Vysvětlení některých vlastností RRT
Ad 1) Tendence stromu růst směrem k ještě neprohledaným částem prostoru je způsobena velikostí Voronoiových oblastí pro jednotlivé vrcholy stromu. Největší Voronoivy oblasti patří vrcholům, které představují listy stromu. Algoritmus RRT vybere jako vrchol stromu pro růst ten, který je nejblíže k náhodně vygenerovanému vrcholu. V případě rovnoměrného rozložení pravděpodobnosti je pravděpodobnost, že tento náhodně vygenerovaný vrchol bude ležet uvnitř nějaké Voronoiovy oblasti přímo úměrná velikosti této oblasti. Tendence stromu růst směrem k ještě neprohledaným částem prostoru je vidět na obr. 14.
Strana 27
Obr. 14 Levý sloupec zobrazuje RRT stromy a pravý sloupec Voronoivy oblasti pro jejich vrcholy Ad 3) Zachování propojení všech vrcholů do souvislého stromu představuje zásadní rozdíl mezi RRT a pravděpodobnostními mapami (PRM). U PRM, především v případech, kdy pracovní prostor obsahuje překážky s úzkými průchody, dochází k rozpadnutí roadmapy
Strana 28 na několik nepropojených segmentů (obr. 15). Pokud ovšem start a cíl cesty leží v různých segmentech, není možné cestu nalézt. Tento problém se potom musí řešit nějakou metodou, která segmenty propojí.
Obr. 15 Rozpad roadmapy na segmenty u metody PRM Ad 5) Pravděpodobnostně kompletní plánovací algoritmus je slabší variantou kompletního plánovacího algoritmu. U algoritmu RRT totiž nalezení cesty závisí na počtu vrcholů stromu. Pravděpodobnost, že strom rostoucí z počáteční konfigurace obsahuje cílovou konfiguraci se blíží k jedné, když se blíží počet vrcholů stromu k nekonečnu.
Strana 29
6. Případové usuzování (Case-Based Reasonig – CBR) Případové usuzování (CBR) je metoda pro řešení nových problémů inspirovaná postupem, který využívají při své práci lidé. Pro člověka je zcela přirozená a běžná věc, že pro řešení nových problémů využívá předchozích znalostí. Například lékař, který při vyšetření pacienta pozoruje podobné symptomy, jaké viděl u jiného pacienta, kterému byla v minulosti úspěšně stanovena diagnóza a byl úspěšně vyléčen, se na základě této zkušenosti rozhodne pro stejnou léčbu. Dalším příkladem je finanční poradce, který rozhoduje, zda nějaké společnosti má být poskytnut úvěr. Určitě si vzpomene, že v minulosti už o poskytnutí úvěru pro společnost s podobnými problémy rozhodoval a tehdy doporučil, aby poskytnutí úvěru bylo zamítnuto. Na základě této zkušenosti vydá s největší pravděpodobností negativní stanovisko i k této nové žádosti. CBR tedy přistupuje k řešení nového problému tak, že při řešení využije předešlých zkušeností. Je v základě odlišné od hlavních přístupů umělé inteligence. Místo spoléhání se na široké znalosti z oblasti řešeného problému nebo tvorby asociací podle obecných vztahů mezi popisem problému a závěry, je CBR schopné zužitkovat specifické znalosti získané z předchozích zkušeností při řešení konkrétních problémových situací (případů). Nový problém je vyřešen nalezením podobného minulého případu a jeho znovupoužitím v této nové situaci. Druhým důležitým rozdílem je také přístup k učení, kdy po každém vyřešeném problému se zkušenosti uchovávají a jsou okamžitě dostupné pro budoucí řešení nových problémů. Tím se samozřejmě zvyšuje efektivita systému založeného na CBR a také jeho kompetentnost při rozhodování. Oblast CBR se v posledních letech značně rozrůstá, jak lze vidět ze zvětšujícího se počtu článků na vědeckých konferencích, dostupných komerčních nástrojů, či na úspěšných aplikacích v řadě vědních oborů.
6.1 Historie Kořeny CBR vedou k práci Rogera Schanka a jeho studentů z Yale University na začátku 80. let. Jeho práci Dynamic memory: a theory of reminding and learning in computers and people z roku 1982 lze považovat za počátky případového usuzování v umělé inteligenci. Tato práce pojednává o teorii učení založené na zapamatování si zkušeností v dynamicky se rozvíjející se paměťové struktuře. První systém případového usuzování byl systém CYRUS (Janet Kolodner) vyvinutý na Yale University v rámci skupiny R. Schanka. Tento systém byl založen na zmíněném paměťovém modelu a MOP teorii řešení problémů a učení. Byl to v podstatě systém odpovídající na otázky ohledně cest a návštěv ministra zahraničí, které uchovával v bázi případů. Případový paměťový model vyvinutý pro tento systém byl později použit jako základ v řadě dalších systémů případového usuzování (MEDIATOR, PERSUADER, CHEF, JULIA, CASEY). Další základy případového usuzování položil B. Porter a jeho skupina z Texaské Univerzity v Austinu systémem PROTOS. Tento systém integroval hlavní znalosti daného oboru a specifické znalosti případu do jednotné struktury. Tím propojil bázi případů a jednotlivé případy. Tato kombinace znalostí a jednotlivých případů byla dále použita v systému GERBE (Branting), což byla aplikace pracující v oboru práva. Dalším významným příspěvkem k případovému usuzování byla práce Edwina Risslanda a jeho skupiny z Univerzity v Massachusetts v Armhearstu. S několika odborníky na právo se snažili vytvořit systém pro řešení soudních sporů, který místo jednoduché odpovědi poskytoval argumenty pro obě strany sporu na základě tzv. precedentů. Výsledkem jejich snahy byl systém HYPO a později systém CABARET.
Strana 30 V Evropě započal výzkum CBR o něco později než ve Spojených Státech. Mezi jednu z prvních prací se řadí systém MOLTKE pro komplexní technické diagnózy Michaela Richtera, Klause D. Althoffa a jejich skupiny z Univerzity v Kaiserslauternu. Tento systém sloužil jako základ pro systém PATDEX Stefana Bosse a jeho kolegů a později i pro řadu dalších systémů (REFINER, IULIAN, CREEK). V dnešní době celosvětově zájem o systémy případového usuzování rychle roste a prosazují se v nejrůznějších vědních oborech včetně robotiky. Výzkumem případového usuzování se zabývají vědečtí pracovníci především v Německu, Japonsku, Indii, ale i dalších zemích.
6.2 Základní pojmy CBR 6.2.1
Případy
Systémy CBR se pokouší adaptovat řešení podobných problémů řešených v minulosti na nový řešený problém. Aby byl tento postup možný, musí CBR systém uchovávat popis předchozích problémů i jejich řešení, a to ve formě tzv. případů. Případ tedy obsahuje popis situace, se kterou se systém již setkal, a řešení této situace, které systém použil. V nejjednodušší variantě je reprezentován jako uspořádaná dvojice (problém, řešení), kde problém je obvykle popsán pomocí vektoru hodnot atributů (a1 , ... , a n ) . Tato podoba odpovídá pravidlu a1 , ... , a n → řešení . Atribut může být číselný, symbolický (řetězce znaků s definovanými významy) nebo vágně lingvistický (lingvistická hodnota je reprezentována pomocí odpovídající fuzzy množiny). Jednotlivé případy nemusí představovat jenom informace o úplně vyřešených problémech, ale i informace o částečně vyřešeném problému může být užitečná.
6.2.2
Případová báze
Protože CBR při řešení nového problému využívá znalosti o předchozích řešených problémech (případy) je nutné tyto informace někde uchovávat, aby mohly být v budoucnu použity. Proto se nové případy ukládají do speciální databáze, tzv. báze případů. Reprezentace báze znalostí závisí na druhu řešených úloh a také na struktuře již dostupných dat. Může se jednat o reprezentaci využívající principů databázových technik, vztahů mezi objekty, teorie grafů či predikátové logiky v závislosti na konkrétní úloze a její implementaci. Na počátku může být báze znalostí systému zcela prázdná, v tom případě je nutné doplnit do systému také nástroje a postupy schopné řešit celou úlohu úplně od začátku nezávisle na CBR. Mohou nastat i jiné situace, než je prázdná báze, jako např. když není v bázi případů dostatek informací nutných pro navržení řešení nebo pokud řešení navrhované systémem případového usuzování není dostatečně kvalitní. Potom je nutné využít jiných postupů k nalezení řešení.
6.3 Účinnost CBR Účinnost CBR systému závisí na několika parametrech. Prvním z nich je volba vhodné reprezentace případu a celé báze, protože s narůstajícím počtem zapamatovaných případů bude samozřejmě vzrůstat i čas potřebný k jejich zpracovávání. Lze ji dále také výrazně zvyšovat volbou vhodné strategie pro výběr případů do báze, výběrem druhu informací uchovávaných o případech (např. úspěšná nebo neúspěšná řešení), případně i doplněním o vhodné metody navrhování pro případ, že adaptované řešení bude nevhodné nebo nebude nalezen dostatečně podobný případ.
Strana 31
6.4 Proces případového usuzování Celý proces případového usuzování má v obecném případě čtyři následující fáze: 1) Nalezení případu (retrieve) – spočívá v procházení celé případové báze, při kterém se hledá nejvhodnější podobný případ. 2) Použití případu (reuse) – v případě, že předchozí krok nalezne v bázi vhodný případ, tak se zkusí použít jeho řešení na nový problém. 3) Ověření případu (revise) – jedná se o ověření, zda je nalezené řešení možné skutečně použít. 4) Uchování případu (retain) – uložení znalostí získaných řešením problému do případové báze. Posloupnost těchto čtyř fází tvoří tzv. obecný cyklus případového usuzování (obr. 16).
Obr. 16 Obecný cyklus případového usuzování
6.4.1
Nalezení případu
Fáze nalezení případu začíná s popisem nyní řešeného problému a končí, když byl v bázi nalezen nejlepší odpovídající případ. Nejprve je třeba určit hlavní rysy nově
Strana 32
řešeného problému, na základě kterých se vyhledá podobný případ uložený v bázi. Identifikace podobných odpovídajících případů lze řešit tzv. mírou podobnosti (podobnostní metrikou), která odhaduje podobnost případů právě řešenému problému. Potom probíhá prohledávání případové báze. Při prohledávání se na základě podobnostní metriky najde nejlépe odpovídající případ nebo jejich skupina. 6.4.2
Použití případu
Po úspěšném určení podobného případu (případů) v minulém kroku následuje jeho adaptace na konkrétní řešený problém. Samozřejmě může nastat i případ, kdy adaptace není nutná a problém lze vyřešit přímým použitím řešení nalezeného případu. Tato situace může nastat, např. pokud řešíme stejný případ, který jsme již v minulosti vyřešili. Obvyklejší je ale situace, kdy je nutné nalezené řešení adaptovat. Adaptace je závislá na oblasti, pro kterou je systém určen, a na konkrétní reprezentaci případů, proto nelze obecně popsat postupy použitelné pro jakýkoliv CBR systém.
6.4.3
Ověření případu
V této fázi se provede ověření, zda nalezené řešení je skutečně použitelné pro řešený problém. Pokud známe výsledek řešení problému, stačí porovnat dosažený výsledek s výsledkem požadovaným. Samotné ověření nabízeného řešení však nezaručuje, že se jedná o řešení optimální. Z tohoto důvodu je vhodné v tomto kroku zavést nějaký kontrolní mechanismus, který by posoudil i jeho kvalitu. Toho se dá docílit pomocí vhodných algoritmů nebo může řešení ohodnotit operátor (člověk), který ho v případě potřeby upraví.
6.4.4
Uchování případu
Poslední fáze ukládá řešení nového problému do báze znalostí. Kromě úspěšných řešení může být někdy prospěšné ukládat i neúspěšná nebo částečná řešení. Pokud by se ovšem do báze ukládaly všechna nová řešení, její velikost by prudce narůstala a časem by práce s ní byla neúnosně pomalá. Proto je dobré zvolit nějakou vhodnou strategii, která určí, co do báze případů ukládat a co ne. Je například zbytečné ukládat do báze případ, který tam už je nebo je velmi podobný. Jenom by se tak zvětšovala redundance případové báze. Další možnost omezení nárůstu velikosti báze nabízí ukládání jenom částí případů, která nesou z hlediska báze nějakou novou informaci. I když omezíme ukládání stejných nebo podobných případů do báze, její velikost se bude neustále zvětšovat. Existuje určitá optimální velikost báze, při které je využití případového usuzování nejefektivnější. Lze předpokládat, že optimální velikost báze nesmí být příliš malá, protože potom by systém CBR neměl dostatek informací a většinu nových problémů by bylo nutné řešit nějakou jinou metodou, ale ani příliš velká, kvůli již zmiňované nízké rychlosti práce s případovou bází. Optimální velikost báze je možné většinou alespoň přibližně stanovit. Nejjednodušší variantou je nastavit limit velikosti báze na její optimální velikost nebo velikost o něco větší. Po dosažení tohoto limitu se do báze už nové případy nebudou ukládat. Tím ovšem přicházíme o největší výhodu CBR, a to schopnosti učit se z minulých zkušeností. O něco lepší způsob je po dosažení maximální velikosti báze začít nahrazovat nejstarší případy novými. Takto ale může dojít ke zhoršení navrhovaných řešení, pokud z báze odstraníme úspěšná stará řešení. Mnohem lepší je způsob, kdy nahrazujeme nejméně úspěšná řešení. Tím zachováme flexibilitu systému a zároveň se nepřipravíme o kvalitní řešení. Také můžeme u každého případu ukládat kromě úspěšnosti i počet jeho
Strana 33 využití, případně jenom počet využití. V podstatě je možné ohodnocovat případy na základě kombinace různých hledisek, která se zohlední právě při odstraňování přebytečných případů.
6.5 CBR a plánování cesty robota Předchozí popis se týkal obecných vlastností CBR. Nyní se podívejme, jak lze CBR aplikovat na konkrétní problém, a to plánování cesty robota. Využití CBR při plánování cesty robota vychází z předpokladu, že se robot často pohybuje po stejných nebo podobných cestách jako v minulosti. Nalezení každé cesty je poměrně výpočetně náročný problém. Aplikací CBR lze částečně odstranit opakování výpočtů pro stejné, případně podobné cesty, které byly již jednou v minulosti provedeny nebo alespoň snížit jejich složitost a časovou náročnost. Největších časových úspor se dosáhne při hledání cest mezi starty a cíli podobnými těm z minulosti, kdy se nejvíce využije uchovaných znalostí. Namísto složitého hledání nových cest, stačí nalézt nejpodobnější případy (cesty) v případové bázi a ty adaptovat na nový start a cíl. Při plánování cesty robota jsou tedy jednotlivé případy v bázi představovány cestami, kterými robot v minulosti již prošel. Způsoby reprezentace případů a případové báze mohou být různé podle metody použité pro plánování nebo prostředí ve kterém plánování probíhá (mřížka, spojité). Ve [2] je případ chápán jako cesta, která je dána svým startovním bodem s[x, y], cílovým bodem c[x,y] a je tvořena posloupností směrů pohybu robota po dané cestě. Nevýhoda tohoto přístupu je v tom, že jednotlivé případy jsou izolované (nepropojené žádnou strukturou) a báze se vyznačuje značnou redundancí. Jsou tam totiž uloženy kompletní cesty, i když obsahují části již existujících případů. Tyto nedostatky lze odstranit aplikací případového grafu, který byl použit např. v [15] pro úlohu plánování cesty robota ve spojitém prostředí. V uvedené práci bázi případů reprezentuje tzv. případový graf. Při ukládání cesty do báze případů je cesta uložena buď celá jako jeden případ, nebo se rozdělí do několika částí, které jsou uloženy jako samostatné případy (pokud se ovšem ještě tyto případy nebo případy jim podobné v bázi případů nevyskytují). Segmenty cest (uložené případy) mohou mít společné pouze své krajní body. Pokud cesta protíná nějaký již existující případ, pak tato cesta i případ jsou rozděleny do menších případů tak, aby byla splněna výše uvedená podmínka. Případy (segmenty) reprezentují hrany výsledného grafu a vrcholy tohoto grafu jsou krajními body těchto segmentů. K nalezení cesty v případovém grafu je použitá kombinace Delauneyho triangulace s Dijkstrovým algoritmem. Případový graf použitý v [15] znázorňuje obr. 17.
Strana 34
Obr. 17 Případový graf Kromě reprezentace případové báze a případů je třeba stanovit parametry, na základě kterých bude v bázi vyhledán optimální případ (cesta). Optimálnost cesty nemusí být dána pouze její délkou, ale i dalšími faktory, jako jsou obtížnost průjezdu, pravděpodobnost výskytu překážek cestou, počet změn směru apod. U případového grafu lze na základě těchto hledisek ohodnotit jednotlivé hrany. Toto ohodnocení se potom zohlední při nalezení cesty v grafu, např. Dijkstrovým algoritmem. Plánování cesty robota se ale i v případě použití CBR neobejde bez některé další metody hledání cest. Použití jiné metody je nezbytné v situacích, kdy systém případového usuzování začíná pracovat s prázdnou bází případů nebo když získané řešení není dost dobré a musí být přepracováno.
Strana 35
7. Implementace Jedním z cílů diplomové práce bylo navrhnout systém plánování cesty robota, který využívá RRT stromy v kombinaci s případovým usuzováním (CBR). Navržený systém se skládá ze dvou programů. Prvním z nich je editor překážek, ve kterém se vytváří 2D mapa pracovního prostoru robota. Překážky představují polygony. Při plánování cesty je tedy mapa pracovního prostoru robota již dopředu známa. Druhým programem je vlastní simulátor plánování cesty robota. Ten využívá mapy pracovního prostoru robota a umožňuje plánování cesty jak samotným algoritmem RRT, tak i pomocí RRT kombinovaného s CBR. Díky tomu lze vzájemně porovnat obě metody a posoudit, zda je použití CBR pro RRT přínosem. Obě aplikace byly napsány v prostředí Microsoft Visual C++ .NET 2003. Editor překážek je navržen jako aplikace MFC (Microsoft Foundation Class) postavená na architektuře Dokument/Pohled. Implementaci simulačního programu lze rozdělit na uživatelské rozhraní a samotné algoritmy potřebné pro plánování. Uživatelské rozhraní je napsáno pomocí Win32 API (Windows Application Programming Interface) a pro grafické výstupy používá knihovnu OpenGL. Algoritmy jsou potom napsány v čistém C++ s využitím funkcí, algoritmů a především kontejnerů nabízených knihovnou STL (Standard Template Library), která je součástí normy ANSI/ISO pro C++.
7.1 Model robota Program simuluje pohyb robota, jehož konstrukce odpovídá jednoduchému autu. Jedná se tedy o neholonomický mobilní robot. Jako každé auto může robot jezdit dopředu i dozadu a natáčet přední kola podle směru, kterým se chce pohybovat. Maximální úhel natočení předních kol je ovšem limitován. Robot a jeho jednotlivé parametry znázorňuje obr. 18.
Obr. 18 Použitý model robota Jak je zřejmé z obr. 18, natočení předních kol je dáno úhlem φ. Pro úhel natočení kol platí omezení |φ| ≤ φmax, kde φmax je maximální úhel natočení předních kol a jeho hodnota musí ležet v intervalu [0, π/2]. Dalším parametrem robota je vzdálenost mezi přední a zadní osou označená jako L. Referenčním bodem robota, který určuje jeho pozici v
Strana 36 pracovním prostoru, je střed zadní osy definovaný pomocí souřadnic x a y. Celkové natočení robota určuje úhel θ. Vzdálenost ρ znázorňuje poloměr projížděné zatáčky a lze ji vypočítat podle vztahu ρ = L / tan φ. Pozici a orientaci robota tedy popisují souřadnice x, y a celkové natočení θ. Z toho je zřejmé, že jeho konfigurace je vektor q = (x, y, θ) a jeho konfigurační prostor bude tedy třírozměrný. Robot je popsán následujícími pohybovými rovnicemi: dx = v ⋅ cos(φ ) ⋅ cos(θ ) dt dy = v ⋅ cos(φ ) ⋅ sin(θ ) dt dθ v = ⋅ sin(φ ) dt L Tyto pohybové rovnice popisují auto s náhonem na přední kola, které bylo použito v [16]. Rychlost robota v může být –1, 0, nebo 1 podle toho jestli auto couvá, stojí nebo jede dopředu.Vstup u∈U, který modifikuje konfiguraci robota, tedy obsahuje rychlost v a natočení předních kol φ, takže u = (v, φ).
7.2 Metrika Použitá metrika je stejná jako v práci [16]. Tato metrika vystihuje vzdálenost mezi konfiguracemi použitého robota lépe než standardní Euklidovská metrika a navíc výpočet vstupu u, který minimalizuje vzdálenost mezi dvěma konfiguracemi, lze poměrně jednoduše vypočítat pomocí funkce arctan. Použitá metrika: d ( p, q ) = ( p.x − q.x) 2 + ( p. y − q. y ) 2 + L2 ⋅ min[( p.θ − q.θ ), ( p.θ − q.θ + 2π ), ( p.θ − q.θ − 2π )]2 kde p a q jsou konfigurace robota a L je vzdálenost os robota.
7.3 Inkrementální simulátor Implementovaný simulátor používá pro integraci pohybových rovnic metodu RungeKutta 4. řádu. Pro vstupní konfiguraci qi počítá novou konfiguraci qn, která vznikne aplikací vstupu u na qi po dobu t0. Integrační časová konstanta t0 je nastavena na t0 = 2. t0 = 2
u
Simulátor
qn
qi Obr. 19 Použitý inkrementální simulátor
Strana 37
7.4 Překážky a detekce kolizí Překážky mohou být tvořeny jednoduchými polygony (konkávními nebo konvexními). Editor překážek sice umožňuje kreslit i komplexní polygony, ale tento typ není podporován v simulačním programu, kde by mohl způsobit problémy. Rozdíl mezi jednotlivými druhy polygonů znázorňuje obr. 20 a obr. 21.
Obr. 20 Jednoduché polygony (vlevo konvexní, vpravo konkávní)
Obr. 21 Komplexní polygon Pro detekci kolizí se používá jednoduché testování průsečíků úseček. Kolize s překážkami se testují vůči obdélníku, uvnitř kterého je uzavřen celý robot. Velikost obdélníku je o něco větší než samotný robot, čímž je zajištěno, že mezi robotem a překážkou zůstane vždy nějaký volný prostor. Detekce kolizí probíhá tak, že se testuje, zda některá ze čtyř úseček tvořících obdélník neprotíná některou z hran polygonů, které přestavují překážky. Protože RRT strom se rozrůstá po krocích určité velikosti, musí se zajistit, že nová konfigurace robota qnew, která se přidává do stromu, „nepřeskočí“ hranu polygonu, čímž by se robot dostal dovnitř překážky. Protože se testuje průsečík úseček, kolize robota a překážky by tak nebyla zachycena. V použité implementaci je velikost kroku omezena tak, aby se to nestalo, integrační časovou konstantou t0, která určuje vzdálenost, kterou robot ujede, a tím i krok, o který se RRT strom může rozrůst během jedné iterace. Implementovaná detekce kolizí je tedy velmi jednoduchá, ale její efektivita by v případě velkých scén s množstvím složitých překážek byla žalostná. Ovšem pro použitou velikost scény a překážky s nízkým počtem hran se ukazuje jako dostačující. Její výhodou je i univerzálnost, protože ji lze, na rozdíl od jiných druhů detekce kolizí, použít na konvexní i konkávní polygony, aniž by bylo nutné počítat triangulaci konkávních polygonů a tím je převádět na konvexní.
Strana 38 V případě složitých rozsáhlých scén a robotů se složitým tvarem by bylo nutné použít např. metodu s hierarchií ohraničujících těles (Bounding Volume Hierarchy). Ta je ovšem implementačně podstatně náročnější.
7.5 RRT Pro plánování cesty se používá RRT plánovač s jedním stromem. Důvodem, proč byla použita jednostromová varianta RRT je, v případě neholonomického robota, problematické napojení stromů v místě jejich setkání. Implementovaný algoritmus RRT plánovače vychází z varianty RRT s CONNECT funkcí a se zaměřením na cíl (RRT-GoalZoom). CONNECT funkci, s jistými modifikacemi, odpovídá cyklus 2 v níže uvedeném algoritmu. Počet iterací je na rozdíl od základní verze CONNECT funkce omezen, protože jinak měl robot příliš velkou tendenci jezdit po kružnicích a zbytečně si tak prodlužoval cestu. V simulačním programu jsou implementovány dva RRT plánovače. Jeden pro použití bez CBR a druhý, který CBR využívá. Algoritmy obou plánovačů se od sebe příliš neliší. V této kapitole bude popsán algoritmus RRT plánovače bez CBR. Algoritmus RRT, který využívá CBR, bude popsán až v následují kapitole o CBR, protože úzce souvisí se způsobem implementace CBR. Algorimus RRT (bez CBR): function RRT(qstart, qgoal) 1) Nastav „normální“ mód konvergence (Normal Mode) 2) Jako kořen stromu použij qstart 3) V K iteracích opakuj (Cyklus 1) a. Vygeneruj náhodnou konfiguraci qrand b. Najdi vrchol stromu qnear , který je nejblíže qrand c. Vypočítej optimální vstup u = (v, φ) (viz. funkce OPT_ACTION) d. Jestliže u.v = 0 potom se všechny následující kroky přeskoč a začni další iteraci cyklu 1 (viz. krok a.) e. Vypočítej novou konfiguraci robota qnew , která vznikne aplikací vstupu u na qnear (využití inkrementálního simulátoru) f. Přidej qnew do stromu jako nový vrchol g. Spoj qnew a qnear hranou ohodnocenou vstupem u h. Jestliže je vzdálenost mezi qnew a qgoal menší než DGoalMode, zapni „cílový“ mód konvergence (Goal Mode) - pokud už není zapnut i. Jestliže je vzdálenost mezi qnew a qgoal menší než DEnd (cílová konfigurace qgoal byla dosažena), ukonči cyklus 1 - přesun na krok 4 j. V R iteracích opakuj (Cyklus 2) i. Poslední konfiguraci qnew označ jako lastqnew ii. Vypočítej novou konfiguraci robota qnew , která vznikne aplikací již vypočítaného vstupu u na lastqnew (využití inkrementálního simulátoru) iii. Vypočítej vzdálenost δ mezi qnew a qrand iv. Pokud je vzdálenost δ větší než v předchozí iteraci (strom se vzdaluje od qrand) nebo qnew je kolizní konfigurace, potom ukonči cyklus 2 v. Přidej qnew do stromu jako nový vrchol vi. Spoj qnew a lastqnew hranou ohodnocenou vstupem u
Strana 39 vii. Jestliže je vzdálenost mezi qnew a qgoal menší než DGoalMode, zapni „cílový“ mód konvergence (Goal Mode) - pokud už není zapnut viii. Jestliže je vzdálenost mezi qnew a qgoal menší než DEnd (cílová konfigurace qgoal byla dosažena), ukonči cykly 2 i 1 - přesun na krok 4 4) Najdi vrchol stromu qend, která je nejblíže qgoal 5) Najdi cestu stromem z jeho kořene qstart do qend Aby měl strom tendenci rychleji růst ke qgoal (spád), generuje se náhodná konfigurace robota qrand tak, že za qrand je vybrána s pravděpodobností PG cílová konfigurace qgoal a s pravděpodobností PG1 náhodná konfigurace, která leží v nějakém okolí D od qgoal. V ostatních případech je qrand úplně náhodná a může ležet kdekoliv v konfiguračním prostoru. Algoritmus funguje ve dvou módech konvergence, v nichž se nastavení hodnot PG, PG1 a D liší.V případě, že rostoucí RRT strom je ještě daleko od qrand, je žádoucí, aby spád k cíli nebyl příliš velký a strom se rozrůstal do všech stran přibližně rovnoměrně. Pokud by spád byl příliš silný, hrozilo by uvíznutí v lokáním minimu a strom by se zastavil o některou z překážek, protože by ji nedokázal obejít a stále by se snažil růst nejkratší cestou k cíli. Na druhou stranu, jestliže strom je již kousek od qgoal, je vhodné, aby se rozrůstal především směrem ke qgoal. Právě tyto změny spádu RRT stromu při růstu zajišťují již zmíněné módy. Pokud je RRT strom ještě daleko od qgoal, pracuje algoritmus v „normálním“ módu (Normal Mode), ale pokud se RRT strom dostane blíže než DGoalMode, přepne se do „cílového“ módu (Goal Mode), který má standardně nastaven větší spád k cíli. Klíčovým bodem RRT algoritmu je nalezení takového vstupu u, který minimalizuje vzdálenost mezi qnear a qrand. Celá situace je navíc komplikována překážkami v pracovním prostoru. Použitý algoritmus, který hledá optimální vstup u minimalizující vzdálenost mezi qnear a qrand, vypadá následovně: function OPT_ACTION(qrand , qnear) 1) Najdi optimální vstup u minimalizací funkce pro výpočet vzdálenosti 2) Aplikuj vstup u na qnear, výslednou konfiguraci označ qnew (využití inkrementálního simulátoru) 3) Pokud není qnew kolizní, vrať qnew a ukonči funkci 4) Opakuj dokud je u.φ < φmax a. u.φ = u.φ + ∆φ b. Aplikuj nový vstup u na qnear, výslednou konfiguraci označ qnew c. Pokud není qnew kolizní, vrať qnew a ukonči funkci 5) Opakuj dokud je u.φ > -φmax a. u.φ = u.φ - ∆φ b. Aplikuj nový vstup u na qnear, výslednou konfiguraci označ qnew (využití inkrementálního simulátoru) c. Pokud není qnew kolizní, vrať qnew a ukonči funkci 6) Překážce se nelze vyhnout, nastav u.v = 0, vrať u a skonči Funkce OPT_ACTION nejprve vypočítá samotný optimální vstup u pomocí minimalizace funkce pro výpočet vzdálenosti. V kroku 2 se použije inkrementální simulátor, čímž se získá nová konfigurace robota qnew, která je blíže ke qrand. Pokud qnew není kolizní, tak ji funkce vrátí a skončí. V případě kolize se potom zkouší měnit
Strana 40 po malých krocích ∆φ optimální natočení předních kol u.φ tak, aby se robot překážce vyhnul. Pokud se funkci OPT_ACTION nepodaří najít žádný vstup u, protože jakýkoliv přípustný pohyb robota zmenšující vzdálenost od qrand by znamenal kolizi s překážkou, vrací funkce vstup u, ve kterém je rychlost robota v nulová. Cesta z qstart do qgoal je nalezena, jestliže vzdálenost mezi qnew a qgoal je menší než DEnd, protože u neholonomického robota je v podstatě nemožné dosáhnout přesné shody qnew s qgoal v rozumném čase. Cesta stromem z jeho kořene qstart do qend (konfigurace, která je nejblíže ke qgoal) se vyhledá v obráceném směru od qend do qstart (protože se jedná o strom je nalezení cesty tímto způsobem rychlejší a jednodušší než ve směru qstart → qend) a otočí se. Výslednou cestu tvoří seznam konfigurací robota Qpath = {q1, q2,…, qn} a seznam vstupů Upath = {u1, u2,…, un-1}, které realizují přechody mezi nimi.
7.6 CBR V použité implementaci je případová báze reprezentována případovým grafem. Případ tedy představuje cesta robota z qstart do qgoal. Ta se ovšem neukládá do báze celá jako jeden úsek, ale z každé cesty se uloží pouze některé konfigurace robota, tzv. kontrolní body (Waypoints – WP). Tyto kontrolní body potom tvoří vrcholy případového grafu. Hranami se propojují ty vrcholy (kontrolní body), které leží blízko sebe. Vzdálenost mezi nimi určuje již popsaná metrika. Při každém plánování nové cesty se systém nejprve pokusí najít cestu (případ) v případovém grafu (případové bázi) využitelnou pro právě řešený problém plánování cesty z konfigurace qstart do qgoal. Pokud je taková cesta nalezena, RRT strom se na ni „napojí“ a roste podél této cesty od jednoho kontrolního bodu k druhému. Celý postup je hodně podobný práci autopilota, který řídí letadlo. Nejprve jsou do letového plánu zaneseny kontrolní body popisující celou trasu letu a autopilot potom řídí letadlo od jednoho kontrolního bodu k dalšímu. Vždy když letadlo dosáhne kontrolního bodu, jako cíl se určí následující kontrolní bod a autopilot změní směr letu k novému kontrolnímu bodu. To se opakuje tak dlouho, dokud letadlo nedoletí k poslednímu kontrolnímu bodu cesty. Při použití tohoto způsobu CBR inspirovaného autopilotem v letadle je sice nutné pokaždé počítat celou cestu znovu pomocí RRT, ale i přesto je výpočet rychlejší než u klasického RRT bez CBR, protože RRT strom zná díky kontrolním bodům směr, kterým má růst tak, aby se vyhnul překážkám a zároveň dosáhl cílové konfigurace robota. Navíc tento způsob má oproti ukládání celých úseků cest do případového grafu některé výhody. U varianty, kdy se do případového grafu ukládají celé úseky cest, totiž práci značně komplikují omezení kladená na neholonomický robot a je třeba vyřešit následující problémy: • • •
přesné napojení RRT stromu na cestu nalezenou v případovém grafu propojení cest v případovém grafu, které se kříží, tak aby mohl robot přejít z jedné cesty na druhou nalezení průjezdné cesty v případovém grafu (nelze projet jakoukoliv zatáčku)
Při použití navrženého systému CBR není nutné řešit tyto problémy a díky tomu je mnohem méně náročný na implementaci.
Strana 41 Jinak systém řešící problém nalezení cesty robota pomocí kombinace metod RRT a CBR s případovým grafem, do kterého se ukládají celé úseky cest, popisuje práce [5]. Zajímavá i když výpočetně složitá metoda pro přesné napojení byla popsána v [17], kde je pro spojení dvou RRT stromů použitá deformace trajektorie.
7.6.1
Vzorkování
Kontrolní body se z nalezené cesty získají tak, že se prochází seznam konfigurací Qpath a jako kontrolní bod se vybere prvá konfigurace robota, jejíž vzdálenost od poslední konfigurace použité pro kontrolní bod je větší nebo stejná jako DWP. Celý postup popisuje následující algoritmus. Cesta pro vzorkování: Cesta = {Qpath, Upath}, kde Qpath = {q1, q2,…, qn} je seznam konfigurací a Upath = {u1, u2,…, un-1} je seznam vstupů Vytvářený seznam kontrolních bodů: WPlist = {wp1, wp2,…,wpm} Algoritmus vzorkování: function WP_LIST(Qpath) 1) WPlist.add(q1) 2) For i = 0 to Qpath.size do a. Jestliže d(WPlist.last, Qpath[i]) ≥ DWP potom WPlist.add(Qpath[i]) 3) return WPlist
7.6.2
Přidání nové cesty do případového grafu
Každá nová cesta, která se má přidat do případového grafu, je reprezentována již uvedeným seznamem kontrolních bodů WPlist. Tento seznam se postupně prochází a jednotlivé kontrolní body se vkládají do případového grafu jako nové vrcholy. Do případového grafu má ovšem smysl ukládat jenom ty kontrolní body, které nejsou stejné nebo příliš podobné již existujícím vrcholům grafu. Proto se přidávají jenom takové kontrolní body, jejichž vzdálenost od nejbližšího vrcholu je větší nebo stejná jako Dsame. V opačném případě se provede substituce, tzn. že nový kontrolní bod se do grafu nepřidá, ale místo něho se použije již existující vrchol grafu, který je k němu nejblíž. Další fází je propojení nových a starých vrcholů hranami. Do případového grafu se přidávají jen takové hrany, které neprotínají žádnou z překážek. Po každém vložení nového vrcholu do případového grafu se vyhledají vrcholy, které leží v jeho okolí definovaném vzdáleností Dneigh. Nově přidaný vrchol se potom spojí hranou se všemi vrcholy, které leží v okolí Dneigh. Výjimku tvoří kontrolní body, které nebyly do grafu přidány, ale byly nahrazeny (substituce). V tom případě se vrchol, kterým byl nahrazen kontrolní bod, propojí jen s těmi vrcholy ležícími v Dneigh, se kterými ještě není spojen. Aby se nestalo, že jednotlivé vrcholy cesty zůstanou nepropojeny hranou, je třeba, aby vzorkovací vzdálenost DWP byla o něco menší než okolí Dneigh, ve kterém se provádí propojení vrcholů. Speciálním případem jsou opět kontrolní body, které byly nahrazeny vrcholem grafu (substituce). Tyto vrcholy jsou totiž oproti původním kontrolním bodům různě posunuty a mohlo by se stát, že zůstanou osamoceny bez propojení na případový graf. Proto je třeba zajistit jejich připojení, i když neleží v okolí Dneigh.
Strana 42 Algoritmus přidání nové cesty do případového grafu: function ADD_PATH(WPlist) 1) Opakuj kroky 2 a 3 pro všechny wp∈WPlist 2) Jestliže v případovém grafu G existuje vrchol V, pro který platí d(V, wp) < Dsame a. Propoj V hranou se všemi vrcholy ležícími v okolí o velikosti Dneigh (pokud hrana už neexistuje a pokud neprotíná překážku) b. Jestliže předchozí vrchol byl získán substitucí a není připojen k V, potom přidej mezi nimi hranu 3) Jinak a. Přidej wp do G jako nový vrchol Vn b. Propoj Vn hranou se všemi vrcholy ležícími v okolí o velikosti Dneigh (pokud hrana neprotíná překážku) c. Jestliže předchozí vrchol byl získán substitucí a není připojen k Vn, potom přidej mezi nimi hranu
7.6.3
Optimalizace případového grafu
I když se do případového grafu neukládají nové vrcholy, které jsou stejné nebo podobné těm již uloženým, časem by stejně došlo k velkému nárůstu velikosti grafu a tím i ke značnému zpomalení práce s ním. Proto systém udržuje počet vrcholů pod hodnotou Vmax tak, že po každém vložení nové cesty do případového grafu ověří, jestli došlo k překročení Vmax a pokud ano, zmenší velikost báze na Vmin. Hodnoty Vmin a Vmax závisí na optimálním počtu vrcholů případového grafu Vopt, při kterém je CBR nejefektivnější. Vmax je hodnota o něco větší než Vopt, kdy CBR ještě výrazně nezpomaluje celý systém. Vmin je potom hodnota o něco menší než Vopt, taková aby úspěšnost CBR nebyla příliš nízká. Stanovení Vmax a Vmin bude provedeno v kapitole 11. Aby bylo možné určit, které vrcholy odstranit a které v grafu ponechat, ohodnocuje se každý vrchol podle počtu použití (tzn. vrchol byl využit jako kontrolní bod). Nový vrchol grafu má ohodnocení nula a za každé použití se hodnota ohodnocení zvýší o jedna. Celý systém optimalizace případového grafu funguje tedy tak, že po vložení kontrolních bodů nové cesty do grafu se ověří zda došlo k překročení hodnoty Vmax a pokud ano, odstraní se tolik vrcholů (včetně jejich hran) s nejmenším ohodnocením, aby počet vrcholů v případovém grafu byl Vmin. Po této operaci ovšem mohou v grafu zůstat vrcholy s nulovou aritou, jejichž výskyt je nežádoucí, protože snižují úspěšnost CBR. Proto se provede ještě odstranění těchto vrcholů.
7.6.4
Nalezení vhodného případu v případovém grafu
Nejprve se najde vrchol Vs případového grafu s nejmenší vzdáleností od počáteční konfigurace qstart a potom vrchol Vg, který má nejmenší vzdálenost od qgoal. Následuje hledání nejkratší cesty případovým grafem z vrcholu Vs do vrcholu Vg. K hledání nejkratší cesty je použit Dijkstrův algorimus s haldou (funkce FIND_PATH). Samozřejmě je třeba ověřit, zda je nalezená cesta vhodná pro nový případ a nebude znamenat zhoršení výkonu celého systému. To zajišťuje krok 3 v následujícím algoritmu. Nalezená cesta, kterou funkce FIND_BEST_CASE vrací, je představována seznamem vrcholů, které se použijí jako kontrolní body pro RRT.
Strana 43 Algoritmus nalezení vhodného případu: function FIND_BEST_CASE(qstart, qgoal) 1) najdi vrchol grafu Vs s minimální vzdáleností od qstart 2) najdi vrchol grafu Vg s minimální vzdáleností od qgoal 3) Pokud je d(Vs, qstart) >Dsmax nebo d(Vg, qgoal) > d(qstart, qgoal), potom skonči – nebyl nalezen vhodný případ 4) Path ← FIND_PATH(Vs, Vg) 5) return Path
7.7 Algoritmus RRT s CBR Pokud byl v bázi nalezen vhodný případ může RRT využít získané informace pro aktuálně hledanou cestu z qstart do qgoal. Kvůli využití informací získaných pomocí CBR musel být původní algoritmus RRT bez CBR modifikován. Implementovaný algoritmus RRT využívající CBR vypadá následovně: Algoritmus RRT s CBR: function RRT_WITH_CBR(qstart, goals) 1. Nastav „normální“ mód konvergence (Normal Mode) 2. Jako kořen stromu použij qstart 3. V K iteracích opakuj (Cyklus 1) a. Vygeneruj náhodnou konfiguraci qrand b. Najdi vrchol stromu qnear , který je nejblíže qrand c. Vypočítej optimální vstup u = (v, φ) (viz. funkce OPT_ACTION) d. Jestliže u.v = 0, potom všechny následující kroky přeskoč a začni další iteraci cyklu 1 (viz. krok a.) e. Vypočítej novou konfiguraci robota qnew , která vznikne aplikací vstupu u na qnear (využití inkrementálního simulátoru) f. Přidej qnew do stromu jako nový vrchol g. Spoj qnew a qnear hranou ohodnocenou vstupem u h. Jestliže GOALS_TEST(goals, qnew) = TRUE, ukonči cyklus 1 i 2 (přesun na krok 4) i. V R iteracích opakuj (Cyklus 2) i. Poslední konfiguraci qnew označ jako lastqnew ii. Vypočítej novou konfiguraci robota qnew , která vznikne aplikací již vypočítaného vstupu u na lastqnew (využití inkrementálního simulátoru) iii. Vypočítej vzdálenost δ mezi qnew a qrand iv. Pokud je δ větší než v předchozí iteraci (strom se vzdaluje od qrand) nebo qnew je kolizní konfigurace, potom ukonči cyklus 2 v. Přidej qnew do stromu jako nový vrchol vi. Spoj qnew a lastqnew hranou ohodnocenou vstupem u vii. Jestliže GOALS_TEST(goals, qnew) = TRUE ukonči cyklus 1 i 2 (přesun na krok 4) 4. Najdi vrchol stromu qend, který je nejblíže goals.last 5. Najdi cestu stromem z jeho kořene qstart do qend
Strana 44 function GOALS_TEST(goals, qnew) 6. Jestliže goals.size > 1 (existují nedosažené kontrolní body) a. Najdi v seznamu goals poslední kontrolní bod, který byl dosažen b. Pokud byl nějaký kontrolní bod dosažen, odstraň ho ze seznamu goals včetně všech kontrolních bodů před ním a přepni na CBR mód (CBR Mode) c. Pokud d(qnew, goals.last) < DGoalMode, zapni „cílový“ mód (pokud už není zapnut) a vymaž všechny kontrolní body z goals kromě posledního (goals.last) d. Jestliže d(qnew, goals.last) < DEnd (cílová konfigurace qgoal byla dosažena) return TRUE 7. Jinak (v goals je už jen cílová konfigurace qgoal (= goals.last) ) a. Jestliže je RRT v CBR módu, přepni na „normální“ mód (pokud už není zapnut) b. Pokud d(qnew, goals.last) < DGoalMode, zapni „cílový“ mód konvergence (Goal Mode) - pokud už není zapnut c. Jestliže d(qnew, goals.last) < DEnd (cílová konfigurace qgoal byla dosažena) return TRUE 8. return FALSE
Jak již bylo uvedeno, při každém hledání nové cesty se systém nejprve pokusí najít cestu (případ) v případovém grafu (případové bázi) využitelnou pro právě řešený problém hledání cesty z konfigurace qstart do qgoal. To provádí také již popsaná funkce FIND_BEST_CASE. Pokud je nalezen vhodný případ, vrací tato funkce seznam kontrolních bodů představujících cestu. Na tuto cestu se RRT strom „napojí“ a roste podél ní od jednoho kontrolního bodu k druhému. Pokud by nebyl žádný vhodný případ nalezen, použije se místo modifikovaného RRT plánovače využívajícího CBR standardní plánovač RRT. Seznam kontrolních bodů z FIND_BEST_CASE je předán funkci RRT_WITH_CBR jako seznam goals, přičemž na jeho konec se přidá cílová konfigurace robota qgoal. Celý algoritmus je v podstatě stejný jako u RRT bez CBR. Liší se jen funkcí GOALS_TEST, která určuje kontrolní bod, ke kterému má RRT aktuálně konvergovat. Aktuální kontrolní bod představuje vždy první prvek seznamu goals. Ve funkci GOALS_TEST se nejprve provede test, zda seznam goals obsahuje ještě nějaké kontrolní body, kterých RRT strom nedosáhl. To je splněno tehdy, když počet prvků goals je větší než 1. Pokud je počet prvků jedna, zbývá v goals už jen cílová konfigurace qgoal. Pokud má goals více než jeden prvek, je prvním krokem nalezení kontrolního bodu, který už byl dosažen, přičemž se hledá ten, který je nejblíže ke konci seznamu goals, protože RRT strom může být např. už u 4. kontrolního bodu a předchozí tři přitom vůbec nemusel projít. Za dosažený kontrolní bod se považuje takový, jehož vzdálenost od qnew je menší než nějaké DNextWP. Jinými slovy to znamená, že RRT strom se dostal do okolí kontrolního bodu. Protože kontrolní body mohly být původně získány pro opačný směr jízdy robota, musí se testovat i vzdálenost vůči kontrolnímu bodu (konfiguraci) otočenému o 180°. Pokud byl nějaký kontrolní bod dosažen, tak se provede jeho odstranění z goals včetně všech kontrolních bodů před ním a RRT nastaví parametry PG, PG1 a D podle CBR módu (CBR Mode). CBR mód se používá pro růst RRT stromu mezi kontrolními body a je nastaven tak, aby měl RRT strom větší spád k aktuálnímu kontrolnímu bodu (první v goals). Větší spád
Strana 45 je možný, protože vzdálenost mezi dvěma kontrolními body je poměrně malá a na cestě mezi nimi se většinou nevyskytují překážky, čili riziko uváznutí v lokálním minimu je malé. V následujícím kroku se ověří, zda se RRT strom nedostal k cílové konfiguraci qgoal (odpovídá goals.last) blíže než DGoalMode. Pokud ano, zapne se „cílový mód“ a ze seznamu goals se vymažou všechny prvky kromě posledního představujícího qgoal. Když už zbývá v goals pouze qgoal, přepne se RRT zpět do „normálního“ módu, protože cesta do qgoal může být ještě komplikovaná a spád nemůže být tak velký, jako je v CBR módu. Potom konverguje RRT strom už jenom ke qgoal a práce algoritmu je v podstatě stejná jako u RRT bez CBR.
Strana 46
Strana 47
8. Editor překážek Editor překážek slouží k vytváření mapy pracovního prostoru, kterou lze poté použít v simulačním programu. Velikost pracovního prostoru je 800x600 bodů. V editoru lze kreslit komplexní i jednoduché polygony, ale simulační program podporuje pouze jednoduché (konvexní i konkávní). S editorem se pracuje podobně jako s každým jiným grafickým editorem. Umožňuje mapy ukládat i otevírat, kreslit obdélníky nebo obecné polygony a nakreslené objekty samozřejmě i mazat.
Obr. 22 Hlavní okno editoru překážek
8.1 Funkce pro kreslení a práci s objekty Výběr funkcí se provádí kliknutím na příslušnou ikonku v panelu nástrojů.
Obr. 23 Panel nástrojů pro kreslení a práci s objekty Kreslení obdélníku – levým tlačítkem myši se nejprve určí levý horní bod obdélníku a potom pravý dolní bod (opět levým tlačítkem). Kreslení lze zrušit klávesou ESC.
Strana 48
Kreslení obecného polygonu – vrcholy polygonu se zadávají levým tlačítkem myši a uzavření polygonu se provede spojením posledního vloženého vrcholu s prvním po stisknutí pravého tlačítka myši. Kreslení lze zrušit klávesou ESC. Označení objektu – označení se provede stisknutím levého tlačítka myši nad plochou objektu a je signalizováno červeným orámováním. Vymazání objektu DELETE.
– vymaže aktuálně označený objekt. Stejnou funkci má i klávesa
8.2 Požadavky programu na PC Podporované OS: Windows 2000, Windows XP Minimální rozlišení 1024x768
Strana 49
9. Simulační program Simulační program slouží k plánování cesty robota v pracovním prostoru definovaném mapou nakreslenou v editoru překážek. K plánování využívá implementovaný RRT plánovač kombinovaný s případovým usuzováním (CBR).
9.1 Hlavní okno programu V hlavním okně se zobrazuje mapa pracovního prostoru. Tu je třeba nejprve načíst ze souboru *.obs, který byl vytvořen v editoru překážek (Nastavení\Načtení překážek). Obrysy překážek jsou vykresleny černě, počáteční konfigurace robota zeleně a cílová fialově. Robot v cílové a počáteční konfiguraci je zobrazen jako obdélník, vůči kterému se testují kolize. Souřadnice x a y pro počáteční konfiguraci se zadávají levým tlačítkem myši. Při jeho stisknutí se za x a y dosadí hodnoty podle aktuální polohy kurzoru myši v mapě. Souřadnice přestavují polohu středu zadní osy auta, který je vyznačen černou tečkou. Celkové natočení robota θ lze změnit kolečkem myši. Natočení se opět provádí vůči středu zadní osy auta. Pro cílovou konfiguraci je to podobné, jenom se místo levého tlačítka používá pravé a pro nastavení natočení je třeba použít kombinaci klávesy CTRL s kolečkem myši. Nastavení počáteční a cílové konfigurace je možné i přes nabídku Nastavení\RRT metoda. Aby bylo plánování cesty úspěšné, nesmí zadaná počáteční a cílová konfigurace robota kolidovat s žádnou překážkou nebo ležet mimo pracovní prostor vymezený okrajem okna. Během výpočtu a po jeho skončení se v okně zobrazuje červenou barvou RRT strom a modrou případový graf. Vykreslování RRT stromu i případového grafu lze samozřejmě vypnout.
Obr. 24
Hlavní okno programu
Strana 50
9.2 Hlavní menu a příkazy Hlavní menu má dvě podnabídky. Nabídka Akce obsahuje příkazy pro spuštění výpočtu a ukončení programu. V nabídce Nastavení, jak už název napovídá, lze nastavit parametry modelu robota, RRT metody, CBR a dalších částí systému.
9.2.1
Příkazy v nabídce Akce
Výpočet lze spustit v automatickém nebo manuálním módu. V manuálním módu se provede výpočet pouze jedné cesty ze zadané počáteční konfigurace do cílové. Poté je uživatel dotázán, zda chce spustit simulaci jízdy robota. Simulace jízdy robota graficky znázorňuje, jak by po nalezené cestě, která je v červeném RRT stromu vyznačena černými tečkami, projížděl skutečný robot. Pokud je zapnuto CBR, ukládá se každá nová cesta do případového grafu. Naproti tomu v automatickém módu se počítají cesty mezi více konfiguracemi, které vygeneruje generátor náhodných konfigurací (Nastavení\Generátor náhodných konfigurací). Cesta se hledá vždy z aktuální konfigurace qn do následující qn+1 (v pořadí, ve kterém byly vygenerovány) tak, jak by se pohyboval reálný robot, tedy z jednoho místa na druhé. Každá vypočítaná cesta se zanáší do případového grafu (pokud je CBR zapnuto) a výsledky pro jednotlivé cesty se ukládají do souboru. Automatický mód je určený pro testování efektivity implementovaného RRT a CBR a není v něm možná simulace jízdy robota. Příkaz Start pro automatický mód je možné použít až po vygenerování náhodných konfigurací v Nastavení\Generátor náhodných konfigurací.
Obr. 25 Nabídka Akce
9.2.2
Příkazy v nabídce Nastavení
Obsahuje příkazy vyvolávající dialogy pro nastavení parametrů jednotlivých částí systému. Všechny dialogy budou popsány v následujícím textu. Protože však nelze vytrhávat popis jednotlivých nastavitelných parametrů z kontextu celého algoritmu, bude popis pouze orientační s tím, že podrobnosti lze nalézt v kapitole o implementaci. V závorce za názvem je uvedeno stejné označení, jaké bylo použito v popisu implementace.
Obr. 26 Nabídka Nastavení
Strana 51
9.3 Nastavení RRT metody Počet iterací (K) – počet iterací RRT algoritmu (cyklus 1 v RRT algoritmu). Po dosažení této hodnoty výpočet končí. Proto nesmí být tato hodnota příliš malá, jinak se může stát, že cílová konfigurace nebude dosažena. Odchylka od cíle (DEnd) – vzdálenost mezi dosaženou a skutečnou cílovou konfigurací. Po dosažení této vzdálenosti od cílové konfigurace se výpočet ukončí a cesta se považuje za nalezenou. Čím menší hodnota, tím větší přesnost dosažení cílové konfigurace, ale tím delší čas výpočtu. Opakování akce (R) – počet opakování optimální akce (cyklus 2 v RRT algoritmu). Malé hodnoty zpomalují konvergenci, velké prodlužují cestu (robot jezdí po kružnicích). Normální mód – nastavení PG, PG1 a D pro „normální“ mód. Cílový mód – nastavení PG, PG1 a D pro „cílový“ mód. Hodnota D se bere i jako vzdálenost DGoalMode, při které se cílový mód aktivuje . CBR mód – nastavení PG, PG1 a D pro CBR mód. Položka Další WP odpovídá vzdálenosti DNextWP. Zobrazovat strom – zapnutí/vypnutí zobrazování RRT stromu. Na pomalých počítačích může vypnutí zrychlit výpočet. Použít CBR – zapnutí/vypnutí případového usuzování.
Obr. 27 Dialog pro nastavení parametrů RRT metody Počáteční konfigurace robota – nastavení souřadnic x, y a celkového natočení CITA (θ) v radiánech pro počáteční konfiguraci robota.
Strana 52
Cílová konfigurace robota – nastavení souřadnic x, y a celkového natočení CITA (θ) v radiánech pro cílovou konfiguraci robota.
9.4 Načtení překážek Po vybrání tohoto příkazu se objeví standardní dialog pro otevření souboru. V něm je třeba zvolit soubor *.obs vytvořený v editoru překážek. Načtená mapa bude potom použita jako pracovní prostor robota.
9.5 Nastavení robota Jednotlivé parametry robota jsou zakreslené do obrázku. Červený obdélník odpovídá obdélníku, vůči kterému budou testovány kolize. KX, KY – délka a šířka kol robota CX, CY – nastavení obdélníku pro testování kolizí L – vzdálenost os robota W – šířka robota P – přední a zadní přesah přes osu MAXFI – maximální natočení předních kol robota ve stupních
Obr. 28 Dialog pro nastavení parametrů robota
9.6 Nastavení CBR Aktuální velikost báze – zobrazuje aktuální počet vrcholů v případovém grafu. Max. velikost báze (Vmax) – počet vrcholů případového grafu po jehož překročení se provede vyčištění báze, tzn. že se odstraní nepoužívané vrcholy případového grafu.
Strana 53 Velikost vyčištěné báze (Vmin) – počet vrcholů případového grafu po vyčištění báze. Maximální vzdálenost startu (Dsmax) – maximální vzdálenost počáteční konfigurace od nejbližšího vrcholu případového grafu. Pokud je vzdálenost počáteční konfigurace od nejbližšího vrcholu případového grafu větší než Dsmax, v bázi nebude nalezen podobný případ. Propojovací okolí (Dneigh) – okolí nového vrcholu v případovém grafu ve kterém se budou hledat staré vrcholy, aby se propojily hranou s nově vloženým vrcholem. Vzorkování (DWP) – vzorkovací vzdálenost, podle které se vytváří kontrolní body z nově nalezené cesty. Substituce (Dsame) – vzdálenost mezi novým a starým vrcholem případového grafu pro provedení substituce nového vrcholu. Pokud je vzdálenost mezi novým a starým vrcholem menší než Dsame, nový vrchol se nepřidá, ale nahradí se starým. Zobrazovat případový graf – zapnutí / vypnutí zobrazování RRT stromu. Na pomalých počítačích může vypnutí zrychlit výpočet. Vymazat bázi – stiskem tohoto tlačítka se smaže celý případový graf.
Obr. 29 Dialog pro nastavení parametrů CBR
9.7 Generování náhodných konfigurací robota Počet generovaných konfigurací – počet náhodných konfigurací, které budou vygenerovány. Cesta robota při spuštění plánování v automatickém módu se potom hledá z aktuální konfigurace do následující v pořadí, ve kterém byly vygenerovány.
Strana 54
Obr. 30 Dialog pro generování náhodných konfigurací Generování konfigurací, tlačítko Generování – spuštění procesu generování náhodných konfigurací. Tato operace může trvat při velkém počtu konfigurací delší dobu. Vymazání náhodných konfigurací, tlačítko Vymazat – odstranění náhodně vygenerovaných konfigurací. Zobrazovat náhodné konfigurace – zapnutí / vypnutí zobrazování náhodných konfigurací, které jsou v hlavním okně vykreslovány šedou barvou.
9.8 Zobrazení výsledků a import do Excelu Po skončení výpočtu se zobrazí okno s informacemi o proběhlém plánování cesty. Okno ukazuje obr. 31.
Obr. 31 Informace o proběhlém plánování cesty Při použití automatického módu se navíc vytváří soubor statdat.txt, který obsahuje základní informace o výpočtu každé cesty. Jeho formát je definován tak, aby informace byly snadno zpracovatelné v programu MS Excel. Jedná se o textový soubor s následujícím uspořádáním dat: 0;143;0.46;0 6;716;7.03;1
Strana 55 29;326;0.66;1 37;391;0.75;1 37;428;1.40;1 47;92;0.07;1 … Jsou v něm čtyři sloupce oddělené středníky. Každý řádek odpovídá jedné cestě. První sloupec obsahuje velikost báze v počtu vrcholů případového grafu, která se použila pro plánování cesty. V druhém sloupci je výsledná délka cesty v hranách RRT stromu. Třetí sloupec obsahuje dobu trvání výpočtu cesty v sekundách. V posledním, čtvrtém sloupci může být 0 nebo 1 podle toho, zda byl nalezen v bázi vhodný případ pro plánovanou cestu. Jako oddělovač desetinných míst slouží tečka. Soubor lze otevřít a zpracovávat v Excelu s tím, že při otvírání se zvolí textový soubor. Jako oddělovač sloupců je nutné nastavit středník a jako oddělovač desetinných míst tečku.
9.9 Požadavky programu na PC Podporované OS: Windows 2000, Windows XP Doporučena grafická karta s akcelerací OpenGL Minimální rozlišení 1024x768
Strana 56
Strana 57
10. Experimenty Prvním experimentem bylo stanovení optimálního počtu vrcholů případového grafu Vopt. Na základě Vopt se určí maximální počet vrcholů případového grafu Vmax a počet vrcholů po vyčištění případového grafu Vmin. Při hodnotě Vmax je spuštěno čištění grafu. Následně byly provedeny testy pro srovnání výkonu a efektivity samotného RRT plánovače bez CBR a plánovače RRT s CBR. Pro experimenty byly použity dvě mapy pracovního prostoru o různé složitosti. Tu jednodušší z hlediska počtu a složitosti překážek přestavuje mapa 1 (obr. 32). Mapa 2 (obr. 33) potom popisuje složitější variantu pracovního prostoru robota, kdy pracovní prostor připomíná bludiště. Veškeré testování probíhalo na PC s konfigurací AMD Athlon XP 1600+, 512 MB RAM, NVIDIA GeForce FX 5600 256 MB a OS Windows 2000 SP4.
Obr. 32 Mapa 1 (jednodušší)
Obr. 33 Mapa 2 (složitější)
Strana 58
10.1 Stanovení optimální velikosti případového grafu Pro každou z map bylo vygenerováno 241 náhodných nekolizních konfigurací robota, mezi kterými se hledaly cesty (240 cest). Aby mohlo být stanovení provedeno, bylo třeba před jeho spuštěním vypnout čištění báze a povolit přidávání podobných vrcholů do grafu. Vypnutí čištění báze bylo provedeno nastavením hodnoty maximální velikosti báze Vmax na 9999, čímž se systém čištění odstavil z činnosti. Povolení přidávání podobných vrcholů do případového grafu je nezbytné, protože jinak je v podstatě nemožné v rozumném čase dosáhnout takové velikosti případového grafu, aby práce s ním měřitelně zpomalovala celý systém plánování cesty. Protože zobrazování tisíců vrcholů a hran případového grafu během výpočtu by mohlo měření ovlivnit, bylo zobrazování případového grafu vypnuto. Ostatní nastavení simulačního programu zůstalo defaultní. CBR muselo být samozřejmě zapnuto. Závislost doby nalezení cesty na velikosti případového grafu pro mapu 1 8 y = -4E-11x3 + 5E-07x2 - 0,0009x + 1,2314
7
čas [s]
6 5 4 3 2 1 0 0
500
1000
1500
2000
2500
3000
3500
velikost případového grafu [vrchol]
Graf 1 Závislost doby nalezení cesty na velikosti případového grafu (Mapa 1)
čas [s]
Závislost doby nalezení cesty na velikosti případového grafu pro mapu 2 20 18 16 14 12 10 8 6 4 2 0
y = -4E-11x3 + 9E-07x2 - 0,0024x + 3,4391
0
1000
2000
3000
4000
5000
velikost případového grafu [vrchol]
Graf 2 Závislost doby nalezení cesty na velikosti případového grafu (Mapa 2)
Strana 59 Charakteristické počty vrcholů (Vopt, Vmax, Vmin) určené na základě změřených hodnot a jejich proložení polynomem 3. stupně (černá křivka a rovnice v grafu) uvádí tabulka 1. Hodnota Vopt odpovídá minimu polynomu a hodnoty Vmin a Vmax určuje jeho derivace. Vmax a Vmin jsou počty vrcholů, při nichž platí, že absolutní hodnota derivace polynomu dy = 0,0003 . dx
Mapa 1 Mapa 2
Vopt 1026 1479
Vmax 1453 1690
Vmin 650 1275
Tab. 1 Charakteristické hodnoty počtu vrcholů Vopt, Vmax a Vmin Jak je vidět z tabulky, optimální počet vrcholů je pokaždé jiný. Je to způsobeno tím, že stanovit obecně platnou hodnotu optimálního počtu vrcholů v postatě nelze. Určit ji lze jen přibližně, protože tato hodnota závisí na množství faktorů, jako je mapa pracovního prostoru nebo vzorek hledaných cest použitý pro testování. Každopádně na základě provedených měření lze pro každou z map pracovního prostoru nastavit v simulačním programu maximální velikost báze (Vmax) a velikost vyčištěné báze (Vmin).
10.2 Srovnání RRT a RRT+CBR Testování probíhalo opět při defaultním nastavení simulačního programu. Rozdíl byl jen v zapnutí nebo vypnutí CBR. Test spočíval v nalezení 200 cest pro obě mapy při vypnutém a následně při zapnutém CBR. Velikost případové báze byla na počátku nulová a tvořila se postupně s každou nově nalezenou cestou. Během testování nedošlo k překročení maximální velikosti báze Vmax, protože se neukládaly stejné nebo podobné vrcholy, jaké už v případovém grafu byly. Výsledky měření uvádí tabulky 2 a 3.
RRT bez CBR RRT s CBR
∅délka cesty [hrana] 405,19 414,67 (+2,3%)
∅čas výpočtu [s] úspěšnost CBR [%] 1,70 0,73 (-57,0%) 98,0
Tab. 2 Výsledky měření (Mapa 1)
RRT bez CBR RRT s CBR
∅délka cesty [hrana] 458,82 461,73 (+0,6%)
∅čas výpočtu [s] úspěšnost CBR [%] 7,75 1,65 (-78,7%) 93,5
Tab. 3 Výsledky měření (Mapa 2) Z výsledků je vidět, že průměrná doba výpočtu potřebná k nalezení cesty z počáteční konfigurace robota do cílové je při použití CBR výrazně kratší. Časový přínos CBR je tím větší, čím složitější je mapa pracovního prostoru. Průměrná délka cesty je zanedbatelně větší při použití CBR, protože systém se snaží využít sice delší, ale již v případové bázi uložené cesty. Nárůst délky je ovšem bohatě kompenzován zkrácením doby výpočtu.
Strana 60
Strana 61
11. Závěr Z výsledků experimentů vyplývá, že metoda RRT dosahuje v případě, že se zkombinuje s CBR, podstatně lepších výsledků než bez použití CBR. Přínos CBR je především ve výrazném zkrácení doby potřebné k nalezení cesty robota. U složitých pracovních prostorů s velkým množstvím překážek může být časová úspora až několikanásobná oproti samostatné metodě RRT bez CBR. Ukazuje se také, že při použití kombinace RRT+CBR je průměrná nalezená cesta delší, protože systém využívá sice delší, ale již v případové bázi uložené cesty. Nárůst délky je však minimální a v podstatě zanedbatelný oproti získaným časovým úsporám. Problémem RRT ovšem mohou být lokální minima. I když v nich RRT neuvázne a cesta je nakonec úspěšně nalezena, znamenají výrazné prodloužení doby potřebné pro nalezení cesty. Toto riziko hrozí především u složitých pracovních prostorů s množstvím překážek. V případě, že by se to stávalo často, je možné dosáhnout zlepšení změnou parametrů systému tak, aby se snížil spád RRT k cíli, čímž se ovšem mírně prodlouží doba výpočtu pro všechny hledané cesty.
Strana 62
Strana 63
Seznam použité literatury [1]
[2] [3] [4] [5] [6] [7] [8] [9]
[10] [11] [12] [13]
[14]
[15]
[16] [17]
Latombe, J.-C.: Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other Artifacts. International Journal of Robotics Research, Special Issue on Robotics at the Millennium – Part I, 1999. Samohýl, P.: Navigace robota pomocí případového usuzování. Diplomová práce. ÚAI FSI VUT, Brno, 2003. Látal, P.: Plánování dráhy robota pomocí evolučních metod. Diplomová práce. ÚAI FSI VUT, Brno, 2004. LaValle, S. M.: Planning Algorithms, Cambridge University Press, 2006. Krček, P. Dvořák, J.: Mobile Robot Path Planning by Means of Case Based Reasoning and Rapidly Exploring Random Trees. ÚAI FSI VUT, Brno, 2006. Latombe, J.-C.: Přednášky Motion Plannig – 2004 Winter Quarter. Dostupné na WWW: http://ai.stanford.edu/~latombe/cs326/2004/schedule.htm Internetová encyklopedie Wikipedia. Dostupná na WWW: http://www.wikipedia.org/ Šeda, M.: Teorie grafů, FSI VUT, Brno, 2003. Halperin, D. Kavraki, L. E. Latombe, J.-C.: Robotics. CRC Handbook of Discrete and Computational Geometry, J.E. Goodman and J. O'Rourke (eds.), CRC Press, Boca Raton, FL, Chapter 41, pp. 755-778, 1997. Rouzek, P.: Plánování dráhy robota pomocí případového usuzování. Diplomová práce. ÚAI FSI VUT, Brno, 2005. Bayazit, B.: Introduction to Motion Planning – Lecture Notes, 2003. Dostupné na WWW: http://www.cse.wustl.edu/~bayazit/courses/cs522/index.html LaValle, S. M.: Rapidly-exploring random trees: A new tool for path planning. Computer Science Dept., Iowa State University, 1998. LaValle, S. M. Kuffner, J. J.: Rapidly-exploring random trees: Progress and prospects. In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 293-308. A K Peters, Wellesley, MA, 2001 Aamodt, A. Plaza, E.: Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches. AI Communications. IOS Press, Vol. 7: 1, pp. 39-59, 1994 Haigh K. Z., Shewchuk J. R.: Geometric Similarity Metrics for Case-Based Reasoning. In Case-Based Reasoning; Working Notes from the AAAI-94 Workshop, Seattle, WA, AAAI Press, 1994, pp. 182-187. Jun Qu: Nonholonomic Mobile Robot Motion Planning – Motion Strategy Project, 1999. Dostupné na WWW:http://msl.cs.uiuc.edu/~lavalle/cs576_1999/projects/junqu/ Lamiraux, F. Ferré, F. Vallée, E.: Kinodynamic Motion Planning: Connecting Exploration Trees Using Trajectory Optimization Methods. ICRA, 2004
