MASARYKOVA UNIVERZITA V BRNĚ FAKULTA INFORMATIKY
PLÁNOVÁNÍ TRASY ROBOTA POMOCÍ VORONÉHO DIAGRAMŮ A DALŠÍCH PROSTŘEDKŮ VÝPOČETNÍ GEOMETRIE DIPLOMOVÁ PRÁCE
ING. PETR ŠVEC 2006
Prohlášení Prohlašuji, že diplomová práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
Vedoucí práce: Mgr. Petr Tobola, Ph.D.
ii
Poděkování Chtěl bych tímto poděkovat vedoucímu diplomové práce, Mgr. Petru Tobolovi, Ph.D., za seznámení s problematikou plánování robota pomocí prostředků výpočetní geometrie. Mé díky také patří mé rodině za podporu při mé cestě za vzděláním.
iii
Shrnutí Diplomová práce se zabývá plánováním bezkolizní trasy bodového nebo polygonového konvexního robota ve 2D prostředí s bodovými, liniovými nebo konvexními polygonovými překážkami pomocí prostředků výpočetní geometrie. Hlavním použitým prostředkem je zobecněný Voroného diagram, který je konstruován pomocí navrhnutého aproximačního algoritmu. Vedle implementovaného translačního pohybu pro daného konvexního robota je předložen návrh i pro rotační pohyb. Dále je diskutováno plánování pohybu pro skupinu polygonových konvexních robotů opět v prostředí s bodovými, liniovými nebo polygonovými překážkami.
iv
Klíčová slova Flocking behaviour, Plane sweep algoritmus, plánování trasy robota, výpočetní geometrie, Voroného diagram
v
Obsah Úvod........................................................................................................................................................ 2 1
2
3
Konfigurační prostor...................................................................................................................... 3 1.1
Abstrakce pomocí konfiguračního prostoru........................................................................... 3
1.2
Transformace pracovního prostoru do prostoru konfiguračního ........................................... 3
Základní metody plánování cesty.................................................................................................. 7 2.1
Dekompozice buněk .............................................................................................................. 7
2.2
Silniční mapa ......................................................................................................................... 8
2.3
Potenciální pole...................................................................................................................... 9
Retrakční přístup.......................................................................................................................... 10 3.1
A* algoritmus....................................................................................................................... 10
3.2
Voroného diagram pro množinu bodových generátorů ....................................................... 10
3.3
Zametací algoritmus (plane sweep) ..................................................................................... 12
3.4
Zobecněný Voroného diagram pro bodové a liniové generátory......................................... 17
3.5
Zobecněný Voroného diagram pro bodové, liniové a polygonové generátory.................... 19
4
Rotační pohyb polygonového robota .......................................................................................... 22
5
Plánování pohybu skupiny robotů .............................................................................................. 26
6
Implementace ................................................................................................................................ 30
7
6.1
Reprezentace reálného světa W............................................................................................ 30
6.2
Reprezentace a výpočet konfiguračního prostoru C ............................................................ 30
6.3
Reprezentace datových struktur a detaily výpočtu algoritmu Plane Sweep ........................ 31
6.4
Uživatelské prostředí programu........................................................................................... 35
Experimentální výpočty ............................................................................................................... 36
Závěr..................................................................................................................................................... 41 Literatura............................................................................................................................................. 43
1
Úvod Výpočetní geometrie jako součást oboru analýzy a návrhu algoritmů nabízí řešení problémů z mnoha dalších oborů – počítačová grafika, geografické informační systémy (GIS), robotika, CAD / CAM, počítačová biologie, počítačová chemie a další. První algoritmická řešení geometrických problémů byla pomalá nebo příliš složitá pro implementaci. V posledních letech bylo vyvinuto několik nových technik algoritmizace, které zlepšují a zjednodušují mnoho přístupů k praktickému řešení geometrických problémů. Výhodou řešení problémů pomocí výpočetní geometrie je prokazatelná časová složitost jednotlivých algoritmů. Časová složitost měří kvalitu algoritmů a udává se jako asymptotická časová složitost v nejhorším případě. Omezení výpočetní geometrie spočívá především ve velice náročné implementaci vybraných algoritmů, schopností operací pouze s liniovými nebo rovinnými objekty a v zaměření především na 2D prostor, kde geometrické algoritmy pro 3D a více rozměrný prostor (především v robotice) jsou složitým rozšířením algoritmů počítajících nad 2D prostorem. Jedním z nejvíce diskutovaných problémů v robotice v oblasti výpočetní geometrie je plánování pohybu robota zahrnující plánování nebo nalezení cesty v neznámém prostředí s překážkami. Dalším souvisejícím problémem je návrh autonomních robotů, což je robotů, které mají zadán cíl práce, ale nemají zadáno jakým způsobem tohoto cíle dosáhnout. Aby byl robot schopný cíleného pohybu, musí mít znalost o oblasti, ve které se nachází. Tato znalost je buď dopředu dána mapou daného prostředí nebo je získána robotem pomocí senzorů. Výsledkem je bezkolizní a pokud možno co nejkratší cesta spojující danou počáteční a cílovou pozici. V diplomové práci je diskutováno řešení návrhu a vlastní implementace plánování bezkolizního pohybu bodového nebo polygonového konvexního robota ve 2D prostředí s bodovými, liniovými nebo konvexními polygonovými překážkami pomocí aproximačního algoritmu konstrukce Voroného diagramu. Cesty generované pomocí Voroného diagramu nám garantují co největší možnou vzdálenost robota od překážek. Dále je předložen návrh plánování pohybu a nalezení nejkratší cesty pro skupinu konvexních robotů v prostředí s polygonovými překážkami. Vedle translačního pohybu je brán v úvahu i pohyb rotační.
2
Kapitola 1
Konfigurační prostor 1.1 Abstrakce pomocí konfiguračního prostoru Hlavní myšlenkou abstrakce problému plánování cesty pomocí konfiguračního prostoru je nahrazení konvexního robota A reprezentujícím bodem. Konfigurace q robota A (viz obr. 1) je určena pozicemi všech bodů robota v pracovním prostoru W (reprezentován jako euklidovský prostor ℜ2 ) a je vyjádřena jako vektor (složený z pozičních a orientačních parametrů, kde jejich počet je udán počtem stupňů volnosti robota) zastupujícího bodu.
Obrázek 1. Konfigurace q při translačním a rotačním pohybu Množina všech možných konfigurací robota A se nazývá konfigurační prostor C. Oblast W okupovaná robotem A v konfiguraci q se označuje jako A(q). Pozice libovolného bodu a ∈ A ve W, pokud A je v konfiguraci q, se značí a(q). Překážka ve W je značena jako B, což je nepřístupná oblast prostoru W. Zavedením konfiguračního prostoru C se redukuje problém nalezení cesty pro polygonového robota ve W na problém nalezení cesty pro bodového robota v C a poskytuje jednotnou soustavu pro porovnání a vyhodnocení algoritmů. Existují tři druhy konfigurací – volná konfigurace Cfree, kde robot a překážka se vzájemně nepřekrývají, dále kontaktní konfigurace a zakázaná konfigurace Cobs. Konfigurační prostor C se rozdělí do volných, kontaktních a zakázaných množin konfigurací. Mapa překážek C je definována jako CB = {q | A(q ) ∩ B ≠ ∅} , což znamená, že pro každou Bi (i ∈ Ν ) ve W existuje odpovídající CBi v C reprezentující všechny konfigurace q robota A kolidující s Bi (viz obr. 2).
1.2 Transformace pracovního prostoru do prostoru konfiguračního Redukce problému nalezení cesty pro polygonového konvexního robota A na problém nalezení cesty pro bodového robota A zahrnuje transformaci pracovního prostoru W do konfiguračního prostoru C. Jádrem této transformace je namapování překážek B ∈ W do překážek CB ∈ C (viz obr. 2).
3
Obrázek 2. Mapování B ∈ W do CB ∈ C pro translační a rotační pohyb
V případě translačního a zároveň i rotačního pohybu po mapování vzniknou 3D překážky CBi = {( x, y, φ ) ∈ ℜ 2 x [0 : 360) : A(x, y,φ ) ∩ Bi ≠ ∅} (viz obr. 2), které jsou složené z několika vrstev CBik pro k = 1, .., z, kde z je počet vrstev. Každá vrstva odpovídá danému natočení robota A o úhel φ a počet těchto vrstev závisí na úhlu dovoleného natočení A a velikosti přechodů mezi natočeními. Dále nechť existuje i takové, že 0 ≤ i ≤ z − 1 , pak φi = i × (360 / z ) . Transformace překážek může být popsána Minkowského sumou (Latombe, 1991, de Berg a kol., 2000). Minkowského suma dvou množin S 1 ⊆ ℜ 2 a S 2 ⊆ ℜ 2 je popsána operací S 1 ⊕ S 2 = { p + q | p ∈ S 1, q ∈ S 2} , kde p + q je vektorový součet vektorů p a q. Minkowského suma pro transformaci B do CB je definována jako P ⊕ (− A(0,0)) . Důkaz a další vlastnosti Minkowského sumy jsou uvedeny v (de Berg a kol., 2000). Minkowského suma P ⊕ (− A(0,0)) může být považována jako Minkowského rozdíl, který je často interpretován jako konvoluce (LaValle, 2005). Příkladem v 1D může být konvoluce ∞
h( x ) =
∫ f (τ ) g ( x − τ )dτ
, kde h( x) = 1 pokud x ∈ Cobs a h( x) = 0 v opačném případě. Funkce
−∞
f : ℜ → {0,1} a platí f ( x) = 1 pouze tehdy, když x ∈ B . Funkce g : ℜ → {0,1} a platí g ( x) = 1 pouze tehdy, když x ∈ A . Nejjednodušší algoritmus pro transformaci B do CB spočívá v jednoduchém součtu vektorů každého vrcholu v a –w, kde v ∈ B a w ∈ A , a následné nalezení konvexního obalu tohoto součtu (jak
4
je uvedeno dále, platí pouze pro konvexní objekty). Algoritmus je velmi jednoduchý, ale má časovou složitost O (nm) , kde n je počet vrcholů B a m je počet vrcholů A. Následující algoritmus podle (Latombe, 1991, de Berg a kol., 2000) počítá pouze s těmi dvojicemi vrcholů, které jsou extrémní (mají největší vzdálenost na polygonu) ve stejném směru a to má za následek snížení časové složitosti na O(n + m) pro případ, kdy robot i překážka jsou konvexní polygonové útvary. Algoritmus č. 1: MINKOWSKÉHO_SUMA(B, –A) Vstup:
Konvexní polygon B s vrcholy v1,..., vn a konvexní polygon (–A) s vrcholy w1,..., wm . Předpokládá se, že vrcholy jsou setříděny proti směru hodinových ručiček a vrcholy v1 a w1 mají nejmenší y–ovou souřadnici.
Výstup: Minkowského suma B ⊕ (− A) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
i = 1; j = 1; vn+1 = v1; wm+1 = w1; repeat přidej vrchol vi + wj do B ⊕ ( − A) . if úhel(vi, vi+1) < úhel(wj, wj+1) then i = i + 1; else if úhel(vi, vi+1) > úhel(wj, wj+1) then j = j + 1; else i = i + 1; j = j + 1; until i = n + 1 and j = m + 1;
Poznámka: notace úhel(p, q) popisuje úhel, který svírá vektor pq s kladnou osou x. Na příkladu na obrázku č. 3 je zobrazena jednotková kružnice, na které jsou vyneseny všechny normály ploch robota –A a překážky B. Při provádění algoritmu v krocích 5 - 10 se prochází tyto normály na jednotkové kružnici proti směru hodinových ručiček a sčítají se vektory odpovídajících vrcholů. Lineární časová složitost O(n + m) algoritmu se dá jednoduše dokázat následujícím způsobem. V každém kroku cyklu dochází ke zvětšení proměnné indexu i, j nebo obou indexů. Po dosáhnutí hodnot indexů n + 1 a m + 1 nemůže dojít k další inkrementaci. Podle (de Berg a kol., 2000), v případě, že jeden z polygonů není konvexní, je časová složitost O(nm) a O(n 2 m 2 ) v případě, že oba polygony nejsou konvexní. Výpočet Minkowského sumy pro nekonvexní polygony spočívá v triangulaci těchto polygonů, výpočet Minkowského sumy každé dvojice polygonů a následně se provede jejich sjednocení.
5
Obrázek 3. Minkowského suma B a –A, jednotková kružnice
Na obrázku č. 4 je zobrazen příklad Minkowského sumy z implementovaného programu pro osmibokého robota –A s bodovými, liniovými a polygonovými překážkami. Před vlastním výpočtem se pomocí Grahamova algoritmu (O’Rourke, 1998) transformují všechny překážky na jejich konvexní obal.
Obrázek 4. Minkowského suma osmibokého robota –A s bodovými, liniovými a polygonovými překážkami
6
Kapitola 2
Základní metody plánování cesty Proces nalezení cesty mezi polygonovými překážkami v ℜ 2 pro polygonového robota A zahrnuje vytvoření konfiguračního prostoru Cfree pomocí uvedeného algoritmu č. 1 a poté aplikaci jedné z dále uvedených metod pro plánování cesty. V řešení konkrétně uveden přístup pomocí silniční mapy (road map), která je v tomto případě tvořena Voroného diagramem, jehož konstrukce je uvedena dále v textu. Cesta v C podle (Latombe, 1991) je spojitá křivka spojující konfigurace qstart a qcíl, formálněji je cesta spojité zobrazení τ : s ∈ [0,1] → τ ( s ) ∈ C , kde τ (0) = qstart je počáteční konfigurace a τ (1) = qcíl je cílová konfigurace cesty. Spojité zobrazení znamená, že pro ∀s1, s 2 ∈ [0, 1] : lim d (τ ( s1),τ ( s 2)) = 0 , s 2 → s1
+
kde d : C x C → ℜ ∪ {0} je zvolená metrika nad ℜ . Příklad metriky v C d (q1, q 2) = max(|| a( q1) − a(q 2) ||) , kde ||x – y|| je euklidovská metrika ve W. Volná cesta je definována a∈ A
jako τ : [0, 1] → Cfree = C \ CB . Algoritmy pro plánování cest dle (Latombe, 1991) zahrnují dva hlavní kroky: - předzpracování – reprezentace volného konfiguračního prostoru Cfree mezi všemi překážkami v dané oblasti pomocí funkce nebo grafu - zpracování dotazu – prohledávání grafu nebo použití funkce pro nalezení cesty Základní přístupy pro plánování cesty zahrnují: - dekompozice buněk – dekompozice Cfree do buněk a reprezentace spojitosti Cfree pomocí grafu sousednosti buněk - silniční mapa – reprezentace spojitosti Cfree grafem - potenciální pole – definuje funkci nad Cfree, která má globální minimum v cílové konfiguraci a maxima v místě překážek.
2.1 Dekompozice buněk Krok předzpracování zahrnuje dekompozici Cfree do kolekce buněk a vytvoření grafu sousednosti reprezentující sousední relace mezi buňkami. Dekompozice Cfree může být do buněk, které přesně pokrývají celé Cfree nebo do buněk, jejichž sjednocení pouze aproximuje volný prostor (např. pouze čtvercové buňky). Na obrázku č. 5 je zobrazen příklad dekompozice Cfree do lichoběžníkových buněk (tzv. lichoběžníková dekompozice Cfree). Krok zpracování dotazu zahrnuje nalezení posloupnosti sousedních buněk vedoucí z počáteční qa konfigurace do cílové konfigurace qb a transformace této posloupnosti do cesty.
7
Obrázek 5. Lichoběžníková dekompozice
2.2 Silniční mapa Krok předzpracování zahrnuje přímou konstrukci grafu cest (bez dekompozice do buněk jako v předchozí metodě) reprezentující spojitost v Cfree. Graf viditelnosti (redukovaný graf viditelnosti – vzájemné propojení vrcholů všech objektů pouze tečnými hranami k těmto objektům – viz obr. 6), retrakční metoda a PRM (Probabilistic Road Map Method) jsou příklady metod konstrukcí grafu cest (Latombe, 1991). Krok zpracování dotazu zahrnuje napojení počáteční qa a koncové qb konfigurace robota A ke grafu cest a nalezení nejkratší cesty. Metody založené na silničních mapách patří mezi nejefektivnější metody plánování cest (Latombe, 1991).
Obrázek 6. Redukovaný graf viditelnosti
8
2.3 Potenciální pole Krok předzpracování zahrnuje umístění mřížky nad prostor a definice funkce (potenčního pole, viz obr. 7) s daným globálním minimem (cílová pozice) nad touto mřížkou. Krok zpracování dotazu zahrnuje nalezení cesty pomocí potenčního pole (hledáme globální minimum). Výhoda této metody spočívá v rychlosti nalezení cílové konfigurace qb, ale vážným problémem je nebezpečí uváznutí v lokálním minimu.
Obrázek 7. Potenciální pole
9
Kapitola 3
Retrakční přístup Retrakční přístup (Latombe, 1991) umožňuje přímou konstrukci grafu cest, který reprezentuje spojitost Cfree (není zapotřebí dekompozice Cfree do buněk). Jedná se o redukci problému nalezení cesty mezi překážkami CB v Cfree na problém nalezení cesty v grafu tvořeného např. Voroného diagramem. Základem retrakčního přístupu je zobrazení libovolného bodu z Cfree do bodu na grafu cest. Pro nalezení nejkratší cesty se nejdříve určí obraz počáteční a koncové konfigurace q ∈ Cfree v tomto grafu a následuje samotné nalezení cesty z qa do qb pomocí A* algoritmu popsaného v první podkapitole. Formálněji je retrakce zobrazení ρ : Cfree → R , R ⊆ Cfree platí–li zároveň, že se jedná o spojité a identické zobrazení ( ρ ( R) = R ) . Tedy ρ ( x) ∈ R pro ∀x ∈ Cfree a zároveň ρ ( y ) = y pro ∀y ∈ R . Volná cesta τ z qa do qb existuje právě tehdy, když existuje cesta v R mezi ρ (qa ) a ρ (qb) (Latombe, 1991).
3.1 A* algoritmus A* algoritmus patří mezi tzv. „best–first“ algoritmy pro nalezení nejkratších cest. Jedná se o výpočetně nejvýkonnější algoritmus garantující nalezení nejkratší cesty. Nechť n označuje libovolný uzel. Algoritmus je postaven na formuli f (n) = g (n) + h(n) , kde f (n) je odhadnutá cena nejlevnějšího řešení přes n, g (n) je cena cesty z počátečního uzlu do uzlu n, a h(n) je heuristická cena udávající nejlevnější cestu z n do cíle. Pro nalezení nejkratší cesty je opakovaně vybírán uzel s nejnižší cenou f (n) a dále je prováděna relaxační operace podobně jako v Dijkstrově algoritmu (Russel & Norvig, 1995), (LaValle, 2005). Heuristická funkce h musí být vybrána takovým způsobem, aby nedošlo k nadhodnocení ceny cesty do cíle (heuristická funkce musí být tzv. přípustná). Nejjednodušší příklad přípustné heuristiky je vzdálenost přímé viditelnosti. Mezi algoritmy, které rozšiřují vyhledávácí cestu z kořene, je A* algoritmus optimálně výkonný (optimally efficient) pro libovolnou danou heuristickou funkci, což znamená, že neexistuje takový algoritmus, který by garantoval expanzi menšího počtu uzlů než A*. Časová složitost A* algoritmu závisí na přesnosti heuristické funkce. Například, pokud heuristická funkce je schopná naprosto přesně odhadnout cenu do cíle, pak A* algoritmus běží v lineárním čase expandující pouze ty uzly ležící na optimální výsledné cestě. Důkazy optimality, úplnosti a další diskuze o složitosti A* algoritmu mohou být dále nalezeny v (Russel & Norvig, 1995), (Korf, 1999), (Konar, 2000) a (LaValle, 2005).
3.2 Voroného diagram pro množinu bodových generátorů Nechť je dána množina konečného počtu různých bodů P = { p1 ,..., pn } ⊆ ℜ 2 , kde 2 < n < ∞ a pi ≠ p j pro i ≠ j , i, j ∈ I n (In je množina přirozených čísel o mohutnosti n). Všechna umístění v prostoru jsou přiřazena k jejich nejbližším generátorům (bodům) z množiny P s ohledem na euklidovskou ℜ2 do množiny regionů vzdálenost. Výsledkem je zobrazení prostoru 2 V ( pi ) = {x | x − pi ≤ x − p j pro ∀x ∈ ℜ , i, j ∈ I n ; j ≠ i} asociované s pi . Samotný Voroného diagram (viz obr. 8) je daný množinou regionů V o ( P ) = {V ( p1 ),...,V ( pn )} generované množinou P.
10
Osa souměrnosti dvou generátorů p a q rozdělující rovinu do dvou polorovin je definována jako kolmá přímka na spojnici pq vedoucí uprostřed této spojnice. Otevřená polorovina obsahující p je definována jako h(p, q) a otevřená polorovina obsahující q je definována jako h(q, p). Samozřejmě e ∈ h( p, q ) , kde e ∈ ℜ 2 je libovolná lokace v rovině, právě tehdy, když d (e, p ) < d (e, q) . Samotná buňka V°(P), která je generována pi je definována jako V ( pi ) = I h( pi, pj ) (de Berg a kol., 2000). 1≤ j ≤ n , j ≠ i
Nechť Cp(v) popisuje největší možnou kružnici, která má střed v libovolném bodě v a neobsahuje žádný generátor. Potom pro V°(P) platí následující věty:
(i) Umístění v je vrcholem Voroného diagramu V°(P) pouze tehdy, když Cp(v) obsahuje na obvodu tři nebo více generátorů p (viz obr. 8),
(ii) osa souměrnosti mezi generátory pi a pj definuje hranu V°(P) pouze tehdy, když zde existuje takový bod v ležící na této ose tak, že na obvodu Cp(v) leží jak pi, tak i pj a zároveň žádný jiný generátor (viz obr. 8).
Obrázek 8. Voroného diagram pro bodové generátory
Základní metody pro výpočet Voroného digramu jsou: inkrementální metoda, metoda rozděl a panuj (divide and conquer) a zametací metoda (plane sweep). Inkrementální metoda má časovou složitost O (n 2 ) , kdežto rozděl a panuj metoda a zametací metoda mají časovou složitost O(n log n) . Důkazy časových složitostí těchto metod jsou provedeny v (Okabe a kol., 2000) a (de Berg a kol., 2000). Nejjednodušší případ retrakce pro zobecněný Voroného diagram V °(Cfree) (i pro liniové nebo polygonové generátory) může být definován následovně: ρ : Cfree → V °(Cfree) 1. případ: q ∈ V °(Cfree) : ρ (q) = q 2. případ: q ∉ V °(Cfree) : nechť p je nejbližší bod k bodu q na hranici Cfree, nechť L je vedená polopřímka z bodu p přes q, pak ρ (q ) je průsečík L z V°(Cfree). Retrakce je použita jako nástroj pro nalezení cesty z počáteční (nebo do koncové) konfigurace, která neleží na vypočteném V°(Cfree), k tomuto diagramu.
11
Výhodou Voroného diagramu v roli grafu cest mezi překážkami v prostoru je jeho implicitní udržování největší vzdálenosti od překážek, avšak bohužel za cenu relativně složité implementace algoritmů pracujících v logaritmickém čase (např. zametací algoritmus, který bude dále rozebrán v textu).
3.3 Zametací algoritmus (plane sweep) Následuje rozbor implementovaného zametacího algoritmu, který navrhl Steve Fortune (1985) a který byl použit pro výpočet Voroného diagramu s bodovými generátory. Další detaily algoritmu jsou uvedeny v kapitole vlastní implementace. Hlavní část algoritmu tvoří posun horizontální přímky l z horní části diagramu do dolní přes všechny generátory P = { p1 ,..., pn } ⊆ ℜ 2 . Během posunu se udržuje informace o části už vytvořeného V°(P) nad l, která nemůže být dále ovlivněna generátory pod l. Část V°(P) nad l je ohraničena sekvencí parabol (tzv. beach line), jak je ukázáno na obrázku č. 9. Body na parabole mají stejnou vzdálenost od generátoru této paraboly a l. Je třeba zdůraznit, že v daném kroku neexistuje informace o pozici generátorů pod l. Průsečíky jednotlivých parabol v sekvenci parabol nad l postupně tvoří hrany V°(P). Místo udržování jednotlivých průsečíků V°(P) s l se během posunu udržuje struktura sekvence parabol. Změna sekvence parabol nad l nastává v okamžiku vzniku nové paraboly nebo zániku paraboly existující.
Obrázek 9. Sekvence oblouků parabol
Nová parabola o nulové šířce vznikne v okamžiku, kdy l dosáhne dalšího generátoru, jedná se tedy pouze o vertikální úsečku spojující nový generátor se sekvencí parabol. Průsečík této úsečky (nově vzniklé paraboly) s parabolou ze sekvence parabol udává počáteční pozici nově vznikající hrany V°(P). Při dalším posunu se tato parabola dále rozšiřuje a postupně mění tvar sekvence parabol, jak je ukázáno na obrázku č. 10. Tento typ události se nazývá událost generátoru (site event).
Obrázek 10. Vznik události generátoru
12
Druhým typem události je smrštění existující paraboly do bodu a následný její zánik, jak je ukázáno na obrázku č. 11. Bod q na obrázku č. 11 má stejnou vzdálenost od l a od všech tří generátorů pi, pj a pk. Tedy existuje kružnice procházející třemi generátory a její nejnižší bod leží na l. Uvnitř kružnice se nemůže vyskytovat žádný jiný generátor, protože takový generátor by byl bližší k bodu q než q k l a to odporuje faktu, že bod q leží na sekvenci oblouků parabol. Z toho plyne, že q je vrcholem Voroného diagramu. Tato událost, která vznikne dosáhnutím l na nejnižší bod kružnice procházející třemi generátory definující sousední paraboly v sekvenci se nazývá kružnicová událost (circle event).
Obrázek 11. Vznik kružnicové události (zánik paraboly a následný vznik nového vrcholu V°(P))
Algoritmus používá tři datové struktury pro udržování nezbytných informací během výpočtu. Vypočtený V°(P) je ukládán ve dvojitém spojovém seznamu hran (doubly connected edge list, dále DCEL). Podrobný popis struktury DCEL může být nalezen v (Okabe a kol., 2000) a (de Berg a kol., 2000). Po ukončení výpočtu se vytvoří obdélníkový okraj vypočteného V°(P) a k němu se napojí okrajové hrany diagramu. Sekvence parabol je reprezentována AVL stromem T (vyvážený vyhledávací strom) (Preiss, 2000), který je zobrazen na obrázku č. 12. Jeho listy odpovídají obloukům sekvence parabol v uspořádaném pořadí. Každý list obsahuje ukazatel na generátor definující daný oblouk. Vnitřní uzly T reprezentují body přerušení v sekvenci parabol a jsou definovány jako dvojice (pi, pj), kde pi je ukazatel na generátor levé paraboly a pj je ukazatel na generátor pravé paraboly. Díky této stromové reprezentaci sekvence parabol lze v logaritmickém čase nalézt oblouk ležící nad nově vzniklou událostí daného generátoru. Dále každý list, reprezentující oblouk α v sekvenci parabol, obsahuje ukazatel na prvek ve frontě událostí, který představuje budoucí kružnicovou událost, při které α zanikne. Tento ukazatel je NIL, pokud v dané části výpočtu neexistuje taková kružnicová událost, při které α zanikne.
13
Obrázek 12. Vyvážený binární vyhledávací strom pro reprezentaci sekvence oblouků parabol
Fronta událostí Q je definována jako prioritní fronta, kde prioritou je y–ová souřadnice události. V případě kružnicových událostí se ukládá nejnižší bod vzniklé kružnice s ukazatelem na list v T, který zanikne při vyvolání této kružnicové události. Při každé události nastane topologická změna sekvence parabol. Topologická změna může mít za následek potenciální vznik kružnicové události ze tří sousedních oblouků. Může ovšem dojít k situaci, kdy dělící čáry sousedních oblouků nekonvergují do vrcholu Voroného diagramu, jak je ukázáno na obrázku č. 13, a tedy se nejedná o kružnicovou událost. Druhým případem je stav, kdy v okamžiku zpracování kružnicové události už neexistují její tři oblouky (dané generátory tvořící tuto událost) v pořadí vedle sebe v sekvenci parabol. Tento případ je způsoben náhlým zpracováním bezprostředně předcházející události generátoru. Z tohoto důvodu se pro každý zanikající oblouk v T provádí kontrola, zda neexistuje odpovídající kružnicová událost v Q. Pokud odpovídající kružnicová událost existuje, jedná se o nekorektní událost (false alarm), která je následně vymazána z Q.
Obrázek 13. Demonstrace nekonvergence dělících čar generátorů p1, p2 a p3
14
Algoritmus č. 2: PLANE_SWEEP(P) Vstup:
Množina P = { p1 ,..., pn } ⊆ ℜ 2 generátorů v rovině.
Výstup: Voroného diagram V°(P) uzavřený v obdélníkové oblasti a uložený v DCEL. 1. 2. 3. 4. 5. 6. 7.
Naplnění fronty událostí Q všemi událostmi generátorů, inicializace prázdné struktury T a prázdného DCEL. while Q ≠ ∅ do Odstraň z Q událost U s největší y–ovou souřadnicí if U je událostí generátoru pi then ZPRACUJ_UDÁLOST_GENERÁTORU(pi) else ZPRACUJ_KRUŽNICOVOU_UDÁLOST( φ ), kde φ je list z T reprezentující parabolický oblouk, který při zpracování zanikne. Vytvoř hraniční obdélník a připoj hrany V°(P), které jsou dány ukazateli z vnitřních uzlů T k hranici tohoto obdélníka.
1 ZPRACUJ_UDÁLOST_GENERÁTORU(pi) 1.1 1.2 1.3
1.4
1.5
Pokud je T prázdný, vlož do něj pi a proveď návrat z procedury (T v tomto případě obsahuje pouze list). Jinak pokračuj kroky 1.2 – 1.5. Nalezni parabolický oblouk α (daný generátorem pj) vertikálně nad pi. Pokud α obsahuje ukazatel na kružnicovou událost v Q, pak tuto událost odstraň z Q (jedná se o nekorektní událost). Nahraď list z T reprezentující oblouk α podstromem mající tři listy. Prostřední list ukazuje na oblouk daný generátorem pi a zbylé dva listy ukazují na oblouky (rozštěpený původní oblouk) dané generátorem pj. Dále podstrom obsahuje vnitřní uzly (pi, pj) a (pj, pi) reprezentující zlomy (breakpoints) mezi oblouky. Proveď převážení stromu. V DCEL struktuře vytvoř novou hranu V°(P) o nulové délce rozdělující V(pi) a V(pj). Ukazatele na nově vytvořenou hranu ulož do odpovídajících vnitřních uzlů stromu T (pi, pj) a (pj, pi). Pokud trojice sousedních oblouků, kde pi je generátor nejlevějšího oblouku, tvoří kružnicovou událost, vlož ji do Q (vkládá se nejspodnější bod vzniklé kružnice!) a nastav ukazatel mezi prostředním obloukem (listem ve stromě T) a nově vloženou kružnicovou událostí. Proveď to stejné pro případ, kdy pi je generátor nejpravějšího oblouku.
2 ZPRACUJ_KRUŽNICOVOU_UDÁLOST( φ ) 2.1
Vymaž list φ z T reprezentující zanikající oblouk α . Proveď úpravu záznamů zlomů ve vnitřních uzlech stromu T a proveď jeho vyvážení. Vymaž všechny kružnicové události, které se odkazují na α z Q (jsou nalezeny pomocí ukazatelů předchůdce a následníka φ v T).
15
2.2
2.3
Střed kružnice přidej do DCEL jako nový vrchol V°(P) a na tento vrchol napoj konce hran os souměrnosti sousedních generátorů (ukazatele na hrany uloženy ve vnitřních uzlech stromu T). Vytvoř novou hranu o nulové délce na místě středu kružnice. Nastav ukazatele mezi nimi odpovídajícím způsobem (viz obr. 14). Do vnitřních uzlů reprezentujících zlom mezi levým a pravým generátorem vlož ukazatel na nově vytvořenou hranu (v případě na obr. 14 se vloží ukazatel do (p1, p3) a (p3, p1). Pokud trojice nově vzniklých sousedních oblouků, kde levý soused zaniklého α je středem této trojice a tvoří kružnicovou událost, vlož ji do Q (vkládá se nejspodnější bod vzniklé kružnice!) a nastav ukazatel mezi prostředním obloukem a nově vloženou kružnicovou událostí. Proveď to stejné pro případ, kdy pravý soused zaniklého α je středem této trojice.
Obrázek 14. DCEL V°(P) pro tři generátory (bez hraničního diagramu)
Degenerované případy při výpočtu mohou být následující: •
Zpracování událostí se stejnou y–ovou souřadnicí. Řeší se imaginárním natočením roviny o velmi malý úhel na pravou stranu. Tím dochází při výběru z prioritní fronty k upřednostnění událostí s menší x–ovou souřadnicí. Problém dále nastává na počátku výpočtu, kdy události se stejnou y– ovou souřadnicí neumožňují nalezení odpovídající paraboly nad druhým generátorem v řadě (průsečík parabol leží v nekonečnu), situace je zobrazená na obrázku č. 15. Řešení spočívá v minimálním kladném posunu y–ové souřadnice prvního generátoru nebo ošetřením pomocí speciálního kódu v implementaci algoritmu.
Obrázek 15. Degenerovaný případ, generátory se stejnou y–ovou souřadnicí na počátku výpočtu •
Problém výskytu několika stejných kružnicových událostí, tj. existence kružnice s větším počtem generátorů na obvodu, jak je zobrazeno na obrázku č. 16. Střed takovéto kružnice je vrchol V°(P) o stupni alespoň 4. V tomto případě algoritmus vytvoří dva vrcholy V°(P) se stejnými
16
souřadnicemi a hranou o nulové délce, která je propojuje. Tyto hrany mohou být dále po výpočtu z DCEL odstraněny.
Obrázek 16. Degenerovaný případ, kružnicová událost •
Při zpracování události generátoru může dojít k nalezení průsečíku nově vzniklé paraboly (vertikální úsečka) se sekvencí parabol přesně v průsečíku dvou sousedních parabol. V tomto případě algoritmus rozdělí jednu z těchto sousedních parabol a vloží novou parabolu mezi dvě části původní paraboly, kde jedna část bude mít nulovou délku (ta část, která leží blíže k průsečíku původních parabol). Část paraboly s nulovou délkou tvoří prostřední oblouk trojice definující kružnicovou událost. Po obsloužení této kružnicové události je vytvořena hrana s nulovou délkou, která může být později vymazána z DCEL.
Časová složitost algoritmu je O( n log n) a prostorová složitost je O(n) , důkaz časové složitosti následuje v textu. Nechť n je počet událostí generátoru. Operace vkládání nebo odebírání prvku v T nebo Q (vkládání nebo výmaz elementů) mají časovou složitost O(log n) . Primitivní operace v DCEL jsou v O(1) časové složitosti. Obsluha události zahrnuje sadu primitivních operací, výsledkem je celková časová složitost obsluhy události O(log n) . Každá kružnicová událost definuje vrchol Voroného diagramu. Kružnicové události jsou vytvářeny a odstraňovány při zpracování události generátoru. Čas potřebný pro obsloužení kružnicové události je zahrnut do zpracování události generátoru. Nekorektní kružnicové události jsou před zpracováním vymazány z Q. Maximální počet kružnicových událostí obsluhovaných algoritmem je 2n – 5 a algoritmus korektně ošetřuje i degenerované případy (de Berg a kol., 2000). Ve výsledku dává celkovou časovou složitost O(n log n) .
3.4 Zobecněný Voroného diagram pro bodové a liniové generátory Nechť L = {l1 ,..., ln } ⊆ ℜ 2 (1 ≤ n < ∞) , kde li (1 ≤ i ≤ n) reprezentuje bodový generátor, liniový generátor nebo posloupnost liniových generátorů (sekvence liniových generátorů, kde koncový bod daného liniového generátoru je shodný s počátečním bodem následujícího liniového generátoru). Pak V (li ) = {x | ds ( x, li ) ≤ ds ( x, lj ) pro ∀x ∈ ℜ 2 , i, j ∈ In, i ≠ j} reprezentuje liniový Voroného region (line Voronoi region), kde ds ( x, li ) = min{|| x − xi || | xi ∈ li, x ∈ ℜ 2 } je nejkratší možná euklidovská xi
vzdálenost mezi bodem x a bodem xi ∈ li , který je nejbližší ze všech bodů generátoru k bodu x. Množina V °( L) = {V (l1),...,V (ln) tvoří liniový Voroného diagram generovaný množinou L. V případě, že li degeneruje na bod pro všechny i, pak liniový Voroného digram redukuje na Voroného diagram pro bodové generátory.
17
Množina L se dekomponuje do množiny ⎡ n ⎤ ⎡ n ⎤ L( d ) = { pi, i ∈ Io} ∪ ⎢ { pij , j ∈ I ni +1}⎥ ∪ ⎢ {lijo , j ∈ I ni }⎥, ⎣i = o +1 ⎦ ⎣i = o +1 ⎦ která je složená z původních bodových generátorů o počtu o ≤ n , generátorů koncových a vnitřních bodů linií a samotných liniových generátorů bez koncových bodů (liniový generátor li se skládá z ni (1)
U
U
segmentů lijo , kde j ∈ I ni ). Na schematickém obrázku č. 17 je uveden příklad V°(L) získaného z V°(L(d)) odstraněním přebytečných linií (tj. Voroného hran vedoucích mezi koncovými nebo vnitřními body liniových generátorů a segmentů l o ), které jsou znázorněné přerušovanou čarou.
Obrázek 17. V°(L) generovaný dekomponovanou množinou generátorů (bez přerušovaných čar)
Hrany ve V°(L(d)) tvoří buď přímé linie nebo parabolické oblouky. Na obrázku č. 18 jsou zobrazeny čtyři případy klasifikací hran podle typů generátorů. Typ E1 představuje rovnou hranu – osu souměrnosti mezi body pi a pj. Typ E2 představuje rovnou hranu generovanou linií li° a jejím koncovým bodem pi1 . Typ E3 reprezentuje hranu danou parabolickým obloukem generovanou bodem pi a linií l °j . Typ E4 reprezentuje rovnou hranu generovanou dvěmi liniemi li° a l °j .
Obrázek 18. Čtyři případy klasifikací hran V°(L(d)) podle typu generátorů
Inkrementální algoritmus pro V°(L(d)) (Okabe a kol., 2000) předem vypočítá V°(P) pro množinu bodových generátorů a poté postupně přidává liniové generátory a tím modifikuje diagram. Postup je podobný inkrementálnímu algoritmu pro bodové generátory. Algoritmus rozděl a panuj pro výpočet V°(L(d)) (Okabe a kol., 2000) rozděluje rekurzivně množinu generátorů přibližně na poloviny, dokud nevzniknou množiny pouze o dvou generátorech.
18
Množiny se poté postupně spojují do stále větších celků až vznikne V°(L(d)). Jedná se o poměrně komplikovaný algoritmus, zvláště při slučování množin a generování os souměrnosti (hran V°(L(d))). Zametací algoritmus, který má časovou složitost podobně jako algoritmus rozděl a panuj O (n log n) , je však oproti algoritmu rozděl a panuj jednodušší na implementaci.
3.5 Zobecněný Voroného diagram pro bodové, liniové a polygonové generátory Zobecněný Voroného diagram V°(O), kde O = {o1 ,..., on } ⊆ ℜ2 (1 ≤ n < ∞) reprezentuje bodové, liniové a polygonové generátory, lze získat nahrazením liniových částí polygonových generátorů v O liniovými generátory a provést pouze výpočet pro novou množinu bodových a liniových generátorů L. Na obrázku č. 19 je příklad tohoto diagramu pro množinu bodových, liniových a polygonových generátorů v obdélníkové oblasti společně s nalezenou nejkratší cestou pomocí A* algoritmu pro bodového robota.
Obrázek 19. V°(O) společně s nejkratší cestou mezi dvěmi danými konfiguracemi
Následující implementovaný aproximační algoritmus využívá zametací algoritmus pro výpočet V°(O). Algoritmus je poměrně jednoduchý v porovnání s nativním algoritmem (viz kap. 3.4) pro výpočet V°(O), ale není vhodný pro velké množství aproximovaných polygonových generátorů. Algoritmus č. 3: VORONÉHO_DIAGRAM_APROXIMACE(O, K) Vstup:
Množina O = {o1 ,..., o n } ⊆ ℜ 2 generátorů v rovině a přesnost K ≥ 1 udávající délku jednotlivých segmentů aproximujících každou hranu z oi pro i = 1, …, n.
Výstup: Aproximace Voroného diagramu V°(O) uzavřeného v obdélníkové oblasti a uloženého v DCEL.
19
1.
2.
3.
for i = 1, 2, …, n do Vytvoř konečnou množinu bodů |Pij|= (LENGTH(hj) / K) + 1, která souměrně aproximuje hranu hj generátoru oi pro j = 0 ,...,H , kde H je počet hran generátoru oi. Funkce LENGTH vrací délku hrany uvedené jako parametr. Body v množině Pi očísluj indexem i. Pomocí upraveného zametacího algoritmu č. 2 vypočti V ° ( P1 ∪ P2 ∪ ... ∪ Pn) . Úprava algoritmu č. 2 – krok č. 2.2 (zpracování kružnicové události), označí se hrana vedoucí mezi levým (p1) a prostředním (p2) bodovým generátorem nebo hrana vedoucí mezi prostředním a pravým (p3) bodovým generátorem pokud tyto generátory mají stejný index, tj. patří do stejné CB (viz obr. č. 20). Dále se označí hrana vedoucí z vrcholu V°(O) pokud levý generátor (p1) a pravý generátor (p3) mají stejný index, situace krátce po zpracování kružnicové události zobrazená na obrázku č. 21. Vymaž z V°(O) označené hrany.
Obrázek 20. Situace při zpracování kružnicové události, při které je označena hrana mezi generátory se stejným indexem p1 a p2
Obrázek 21. Situace krátce po zpracování kružnicové události, při které byla označena hrana mezi generátory se stejným indexem p1 a p3
Situace před výmazem nadbytečných hran V°(O), tj. hran incidujících s překážkou, je zobrazena na obrázku č. 22. Pro větší přehlednost byla zvolena přesnost K = 10 bodů oproti přesnosti K = 1 z obrázku č. 19.
20
Obrázek 22. V°(O) před výmazem nadbytečných hran v aproximačním algoritmu (č. 3)
V°(O) s přesností K = 1 pro polygonového robota spolu s vypočtenou nejkratší cestou mezi počáteční a koncovou konfigurací je zobrazen na obrázku č. 23. V tomto případě V°(O) je tvořen pro konfigurační prostor vzniklý transformací všech B do CB (viz kapitola 1.2). Překrývající se CB získají stejný index a tím se sloučí v jednu překážku (generátor).
Obrázek 23. V°(O) pro C vytvořeného pro polygonového robota společně s nejkratší cestou
mezi dvěmi danými konfiguracemi
21
Kapitola 4
Rotační pohyb polygonového robota Problém rotace robota A v pracovním prostoru W je redukován na problém translačního pohybu A ve volném konfiguračním prostoru Cfree (de Berg a kol., 2000). Pro každé možné natočení robota A je třeba vypočítat V°(O), který tvoří jednu z mnoha vrstev reprezentace Cfree. Všechny vrstvy se navzájem propojí a jejich počet je dán jemností a velikostí možného úhlu rozsahu natočení A. Cesta τ robota A se nyní skládá ze dvou typů pohybu. Prvním typem pohybu je čistě translační pohyb uvnitř konkrétní vrstvy a druhým typem je pohyb do vrstvy vyšší nebo nižší reprezentující čistě rotační pohyb. Celá idea je zobrazena na obrázcích č. 24 a 25.
Obrázek 24. Znázornění navzájem propojených dvou vrstev V°(O) tvořící reprezentaci Cfree, průsečík obou diagramů v rovině určuje pozici kolmé spojnice obou vrstev
Obrázek 25. Znázornění překryvu dvou vrstev V°(O) pro různé natočení robota A, propojení vrstev pomocí průsečíku V°(O)
Formálněji pro ∀i takové, že platí 0 ≤ i ≤ z − 1 , nechť φ i = i (360 / z ) . Pro každou vrstvu ti se nalezne Cfree a jeho spojitá reprezentace pomocí V°(O). Dále se propojí každá dvojice sousedních vrstev ti a ti+1 (také se propojí poslední a první vrstva) tak, aby vznikla Voroného reprezentace celého Cfree i pro rotační pohyb. Vypočítá se překryv ti a ti+1. Pro každou dvojici hran h1 ∈ ti a h 2 ∈ ti + 1 pro které platí h1 ∩ h 2 ≠ ∅ , se vloží získaný průsečík p těchto hran do obou vrstev ti a ti+1. Průsečík
22
p1 ∈ ti se propojí novou hranou s průsečíkem p 2 ∈ ti + 1 . Dále pro každý vrchol vj ∈ V °(O) , kde 1 ≤ j ≤ N a N je počet vrcholů V°(O), patřící do ti a ti+1 se přidá kolmá hrana vedoucí z vj ∈ ti (vj ∈ ti + 1) do průsečíku z s vrstvou ti+1 (ti) pokud platí, že z ∈ Cfree . Průsečík z se propojí s nejbližším vrcholem vj ∈ V °(O ) ∈ ti + 1 (vj ∈ V °(O ) ∈ ti ) (viz obr. 26).
Obrázek 26. Propojení vrstev přes vrcholy V°(O)
Pro nalezení nejkratší cesty τ z počáteční konfigurace q1( xstart , ystart ,φstart ) do koncové konfigurace q 2( xcíl , ycíl ,φcíl ) se postupuje následovně: • • •
Určí se nejbližší vrstvy t1 a t2 odpovídající danému natočení robota v q1 a q2. Pokud pro dané natočení robota A(q1) nebo A(q2) neexistuje místo v Cfree ve vrstvách t1 a t2, pak τ pro A(q1) neexistuje. Pomocí retrakce se naleznou body p1 a p2 na hraně Voroného buněk obsahující q1 ∈ t1 a q 2 ∈ t 2 (např. nejbližší bod na obvodu Voroného buňky od q1 / do q2 konfigurace). Pomocí A* algoritmu se nalezne nejkratší cesta v grafu vytvořeném propojením vrstev V°(P) z pozice p1 do pozice p2.
Metoda v této základní formě pro lichoběžníkovou dekompozici není korektní (de Berg a kol., 2000). V některých případech vrací chybové hlášení o neexistenci nebo naopak existenci bezkolizní cesty oproti skutečnosti. Např. metoda může určit, že startovní konfigurace q1( xstart , ystart ,φstart ) , která ve skutečnosti se vyskytuje v Cfree, v Cfree není, protože její nejbližší konfigurace q1NEAR ( xstart , ystart ,φstartNEAR ) v odpovídající nejbližší vrstvě do Cfree nespadá. Konfigurace v jednotlivých vrstvách jsou bezkolizní, ale na hraně spojující tyto dvě vrstvy tomu tak být nemusí. Čím více vrstev, tím méně je pravděpodobnější problém kolize s překážkou, ale zvýšení počtu vrstev není řešením. Pro zajištění, aby robot v žádném případě nekolidoval s libovolnou překážkou, se musí zvětšit rotací po směru i proti směru hodinových ručiček o úhel (180 / z)° a vytvořit jeho konvexní obal (de Berg a kol., 2000), jak je ukázáno na obrázku č. 27.
23
Obrázek 27. Umělé zvětšení robota
Pro ilustraci na obrázku č. 28 je zobrazen 3D konfigurační prostor složený z 2D vrstev pro daného polygonového konvexního robota A. Po propojení jednotlivých vrstev výše uvedeným způsobem vznikne 3D graf ve kterém lze opět hledat τ z počáteční do koncové konfigurace. Tímto způsobem se aproximuje nalezení τ mezi vzniklými 3D CB.
24
Obrázek 28. Vrstvy 3D konfiguračního prostoru, které po propojení tvoří 3D graf umožňující nalezení nejkratší cesty τ pro polygonového konvexního robota s rotací
25
Kapitola 5
Plánování pohybu skupiny robotů Plánování pohybu skupiny objektů postaveném na flocking modelu (Reynolds, 1987) zahrnuje dva hlavní směry. První směr umožňuje co nejreálnější simulaci přirozeného života. Příklady mohou být např. simulace hejna ptáků, hejna ryb, davu lidí utíkajících ze sportovního stadionu a další. Využití je zejména ve hrách, v kinematografii, v systémech virtuální reality, architektuře a biologických nebo ekologických simulacích. Druhým směrem je plánování pohybu skupin objektů s menším ohledem na realitu jejich pohybu. Skupinou objektů může být skupina robotů pohybujících se z dané počáteční konfigurace do dané cílové konfigurace. Objekt skupiny se podle (Reynolds, 1987) nazývá boid (objekt schopný okamžité reakce na stav jiných členů skupiny v jeho okolí) a jednoduchá pravidla pro simulaci shromažďování (flocking) objektů se označují jako řídící typy chování (steering behaviours). Základem pro reprezentaci typů chování jednotlivých entit tvoří jednoduchý transportní model (Reynolds, 1999) aproximující složitější fyzikální modely, které nejsou postaveny na idealizovaných entitách. Jedná se o výpočetně nenáročný fyzikální model postavený na aproximaci hmotného bodu (bod má rychlost, ale žádnou setrvačnost). Typy chování objektů lze rozdělit do dvou částí – řídící typy chování a typy chování skupin (group behaviours) objektů. Samotné základní řídící typy chování lze kombinovat do složitějších typů řídících chování nebo do typů chování skupin (Reynolds, 1999). Pohyb objektů je umožněn pomocí zmíněného fyzikálního modelu, který je parametrizován řídícím vektorem síly. Řídící typy chování jsou založeny pouze na výpočtu vektoru reprezentující požadovanou řídící sílu (F = ma). Mezi základní řídící styly chování patří vyhledávací (seek) typ. Vyhledávací typ chování počítá vektor síly, která soustředí daný objekt směrem do cílové pozice. Na obrázku č. 29 je požadovaná rychlost objektu označena jako vektor působící ve směru od objektu do cíle upravený na délku maximální rychlosti objektu a řídící síla je vypočtena jako rozdíl mezi požadovanou rychlostí a rychlostí momentální.
Obrázek 29. Výpočet velikosti řídícího vektoru síly vyhledávacího typu chování
Modifikací vyhledávacího stylu chování je přijíždějící (arrival) styl chování, který umožňuje plynulé snižování rychlosti objektu přibližujícího se k cíli. Typy chování skupin zahrnují řídící typy chování, které berou v úvahu nějaké nebo všechny objekty v prostoru. Aby objekt mohl určit řídící sílu, musí počítat se všemi ostatními objekty uvnitř oblasti předdefinované velikosti – označované jako sousedství, které je centrováno na tomto objektu.
26
Po vstupu cizího objektu do sousedství vzniká potenciální kolize, které musí daný objekt zabránit vzdálením se od všech objektů v sousedství. Sousedství je specifikováno poloměrem a úhlem rozsahu, jak je ukázáno na obrázku č. 30.
Obrázek 30. Sousedství
Pro simulaci a řízení skupiny objektů slouží skupinový tzv. shromažďující se (flocking) styl chování (Reynolds, 1987) a skládá se z následujících tří řídících chování (viz obr. 31), které určují způsob chování objektu dle pozice a rychlosti jeho blízkých sousedů ve skupině. •
•
•
Separace – počítá řídící sílu, která směruje objekt dál od objektů, které se nacházejí v jeho sousedství. Nechť r značí vzdálenost k sousedovi. Pro výpočet řídící síly se postupuje následovně: vypočítá se odpudivá sílu pro každý blízký objekt odečtením pozice sousedního objektu od pozice daného objektu, dále se provede normalizace této odpudivé síly, aplikuje se váha 1/r a nakonec se výsledná řídící síla dostane jako součet odpudivých sil všech sousedních objektů. Koheze – počítá řídící sílu, která směruje objekt do středu skupiny jeho sousedních objektů. Tato síla je použita pro udržení soudržnosti skupiny. Pro výpočet řídící síly se postupuje následovně: vypočítá se průměrná pozice sousedů daného objektu a poté se odečte pozice objektu od této průměrné pozice. Zarovnání – udržuje směr pohybu daného objektu se směrem pohybu jeho sousedů. Pro výpočet řídící síly se postupuje následovně: vypočítá se průměrný směr pohybu jeho sousedů a poté se odečte směrový vektor daného objektu od tohoto průměrného směru pohybu.
Obrázek 31. Shromažďující styl chování
Určení sousedů objektu je velmi pomalé, pokud se porovnává vzdálenost mezi každými dvěma objekty v prostoru. Touto primitivní metodou se dosáhne časové složitosti O (n 2 ) . Nalezení nejbližších sousedů je jednou ze základních úloh výpočetní geometrie. Časová složitost může být podstatně snížena rozdělením prostoru do menších částí. Existuje mnoho různých technik, například
27
BSP stromy, čtyřstromy (quad–trees), okt. stromy (oct–trees) atd. Metoda bin–lattice (cell-space) (Reynolds, 2000) rozděluje prostor do několika buněk. Každá buňka obsahuje seznam ukazatelů na všechny objekty, které obsahuje. Seznam ukazatelů v jednotlivých buňkách se mění při každé změně pozic objektů. Po určení, které buňky leží uvnitř sousedství daného objektu, se porovnává vzdálenost pouze vůči objektům obsaženým v těchto buňkách (viz obr. č. 32). Počet objektů uvnitř sousedství je shora ohraničen, protože skupina má maximální hustotu objektů. Tuto hranici označíme konstantou k. Tedy původní algoritmus zrychlí z O (n 2 ) na O(kn) , což je asymptoticky ekvivalentní k O(n) .
Obrázek 32. Ilustrace metody bin–lattice, objekty ohraničené kružnicí spadají do sousedství bíle označeného objektu
Cílem řízeného (homing) skupinového typu chování podle (Bayazit a kol., 2002) je přesun skupiny robotů RG z počáteční do cílové pozice. Jednotlivé roboty skupiny RG se řídí třemi výše zmíněnými lokálními řídícími typy chování. Samotné plánování cesty zahrnuje aplikaci A* algoritmu pro nalezení nejkratší cesty τ z dané počáteční do dané cílové pozice ve V°(O), který reprezentuje Cfree. Každý robot má být schopen projít τ o minimální šířce průměru největšího robota skupiny a proto překážka CB je vypočítána jako Minkowského suma překážky B a nejmenší kružnice ohraničující největšího robota. Nalezená cesta τ je rozdělena do jednotlivých podcílů, které jsou tvořeny vrcholy V°(O). Posun po τ podle (Bayazit a kol., 2002) je uveden jako postupný přesun jednotlivých členů skupiny do podcílů, dokud se nedostanou do samotného cíle. Algoritmus č. 4: ŘÍZENÝ_STYL_CHOVÁNÍ 1. for ∀A ∈ RG 2. do if (cíl je v dosahu senzorů) 3. přibliž se k němu a zastav 4. else if (podcíl je v dosahu senzorů) 5. nastav ho jako dočasný cíl 6. else 7. pohybuj se směrem k dočasnému cíli V°(O) obsahuje pouze globální informaci, tj. informaci o možných cestách přesunu z dané počáteční konfigurace do dané koncové konfigurace, ale neobsahuje lokální informaci, která by sloužila pro ovlivnění chování skupiny v určitých místech diagramu (např. změna stylu chování skupiny robotů před vstupem do úzkého koridoru). (Bayazit a kol., 2002) nabízí možnost uložení předefinovaných pravidel chování v jednotlivých uzlech V°(O). Pokud v uzlu se takováto informace nevyskytuje, chování skupiny zůstává univerzální. Pravidla akceptovaná jednotlivými členy mohou být ve tvaru např. „Přesuň se na další uzel na cestě“ nebo ve složitějším tvaru „počkej na ostatní, vyber lídra a následuj ho při dalším posunu“. Odlišný přístup nabízí (Masciotra a kol., 2005), kde skupina jedná
28
dle vlastního seznamu typu chování, které vybírá dle toho v jakém stavu se nachází, přičemž stavy jsou uložené v jednotlivých uzlech V°(O). Při procházení úzkých koridorů je vhodné použít strategii následování lídra (leader following) (Bayazit a kol., 2002), která zahrnuje tyto kroky: shromáždění celé skupiny před úzkým průchodem, výběr člena skupiny, který je nejblíže vstupu a jeho následování zbytkem skupiny. Navigace skupiny robotů pomocí algoritmu č. 4 je možná pouze v případě V°(O) vytvořeného pomocí aproximačního algoritmu č. 3, který s danou přesností aproximuje parabolické oblouky liniovými segmenty, pro V°(P) tvořený bodovými generátory nebo pro jiné reprezentace Cfree pomocí silniční mapy. Pro navigaci skupiny robotů ve V°(L) nebo V°(O) vytvořeného pomocí algoritmů pro liniové překážky (viz kapitola 3.4) je potřeba aproximace parabolických oblouků vyskytujících se na nalezené nejkratší cestě. Typ chování následování stěny (wall following) prezentovaný v (Reynolds, 1999) je možné aplikovat na jednotlivé členy RG pro zamezení kolize s CB. Jednotlivé roboty A jsou vybavené senzory (viz obr. 33). Po virtuálním proniknutí senzoru do překážky se ve směru normály této překážky vypočítá odpudivá síla, která se připočte k celkové řídící síle.
Obrázek 33. Ilustrace použití senzorů pro vyhýbání se polygonovým překážkám
29
Kapitola 6
Implementace Implementace samotného programu byla provedena v jazyce Java (Preiss, 2000), (Knudsen a kol., 2004). Samotný program zahrnuje plánování cesty pro bodového a polygonového konvexního robota ve 2D prostředí s bodovými, liniovými nebo konvexními polygonovými překážkami. Drobné geometrické problémy byly řešeny s pomocí publikace (Schneider a kol., 2003).
6.1 Reprezentace reálného světa W Reprezentace W je tvořena seznamem překážek, kde každá překážka vlastní index a typ (bodová, liniová nebo polygonová) jakožto nejdůležitější atributy. Dále přesnost K se kterou se aproximují zbylé (neklíčové) body.
6.2 Reprezentace a výpočet konfiguračního prostoru C Reprezentace C je tvořena seznamem rozšířených překážek CB podobně jako u reprezentace W se stejnými atributy. Transformace W do C je popsána v kapitole 1.3 a zahrnuje nalezení konvexního obalu robota A a všech překážek CB pomocí Grahamova algoritmu, použití Minkowského sumy na –A a CB a následné sjednocení všech překrývajících se překážek (tj. sjednocení jejich indexů). V samotném programu byl implementován pouze O(n2) algoritmus pro výpočet překrytí překážek, kde n je počet všech hran překážek namísto použití algoritmu uvedeném v (de Berg a kol., 2000) s logaritmickou složitostí. Pro samotné sjednocení indexů byl použit Union – Find algoritmus (Sedgewick, 2002). Union – Find algoritmus zahrnuje dvě hlavní operace: operace Find – nalezení množiny ve které se vyskytuje daná překážka o stejném indexu a operace Union – sjednocení množin překážek o stejném indexu. Byla implementována nejjednodušší verze tohoto algoritmu bez stromové struktury pro rychlé sjednocení. U této nejjednodušší verze platí, že algoritmus provede alespoň M N kroků, kde M je počet operací provedených sjednocení a N je počet všech překážek. Na obrázku č. 34 je uveden příklad tří operací sjednocení.
Obrázek 34. Ilustrace nejjednodušší verze Union – Find algoritmu
30
6.3 Reprezentace datových struktur a detaily výpočtu algoritmu Plane Sweep Tato kapitola dále rozšiřuje kapitolu 3.3 věnující se rozboru Plane Sweep algoritmu a jeho datových struktur pro konstrukci Voroného diagramu. Prioritní fronta obsahující události generátoru nebo kružnicové události je reprezentována pomocí binární haldy (Preiss, 2000), (Sedgewick, 2002) s přidanou operací odebrání nejen kořenového prvku ze vzniklého vyváženého binárního stromu, ale i ostatních uzlů (v tomto případě je odebíraný prvek označen jako neplatný). Sekvence parabolických oblouků je uložena v AVL stromu. Při zpracování události generátoru se v kroku 1.2 algoritmu č. 2 hledá odpovídající parabolický oblouk nad nově vybraným generátorem z prioritní fronty. Tato operace je provedena postupným procházením AVL stromu od kořene k listu reprezentující odpovídající parabolický oblouk. V každém vnitřním uzlu se algoritmus rozhoduje jakou další větví sestoupí do nižší úrovně před dosáhnutím samotného listového uzlu. Jednoduchým na implementaci, ale lehce opomenutelným krokem je snížení y–ových souřadnic generátorů odpovídajících parabolických oblouků (např. p1 a p2) vzhledem k aktuální pozici zametací přímky z uzlu stromu (např. (p1, p2)) před samotným nalezením jejich průsečíku. Srozumitelnější vysvětlení této normalizace je ilustrováno na obrázku č. 35.
Obrázek 35. Snížení y–ových souřadnic generátorů parabolických oblouků před nalezením průsečíku
Obecně existují dva průsečíky parabol daných generátory ve vnitřních uzlech stromu, ale v případě existence generátorů o stejné y–ové souřadnici existuje pouze jeden (resp. dva průsečíky o stejných souřadnicích). Nejjednodušší případ je ilustrován na obrázku č. 36, kdy se zpracovává generátor p3 a při procházení stromu od kořene k listu hledáme průsečíky parabol dané generátory z uzlu (p1, p2) a poté generátory z uzlu (p2, p1).
Obrázek 36. Situace při zpracování události generátoru p3, kdy při postupném procházení stromu T z kořene do listu je nalezen pouze jeden průsečík parabol daných generátory ve vnitřních uzlech
31
Určení korektního průsečíku a rozhodnutí ve které větvi stromu T se bude dále prohledávat (viz obr. 36) lze popsat následujícím algoritmem. Algoritmus č. 5: URČI_PODSTROM((pi, pj), p) Vstup:
Uzel ( pi, pj) ∈ T a právě zpracovávaný generátor p udávající pozici zametací přímky.
Výstup: Ukazatel U na levý nebo pravý podstrom stromu Tp ⊆ T (Tp má kořenový uzel v (pi, pj)). 1.
Nalezni průsečík(y) parabol danými generátory pi a pj a ulož ho (je) do dvourozměrného pole I[2]. if byl nalezen pouze jeden průsečík intersection = I[0]; else if pi.y > pj.y || (pi.y == pj.y && pi.x < pj.x) if I[0].x < I[1].x intersection = I[0]; else intersection = I[1]; else if I[0].x < I[1].x intersection = I[1]; else intersection = I[0];
2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. if p.x > intersection.x 17. U = Tp.rightTree(); 18. else 19. U = Tp.leftTree();
Poznámka: notace leftTree() (rightTree()) představuje funkci vracící ukazatel na levý (pravý) podstrom stromu Tp a proměnná intersection představuje korektní bod průsečíku daných parabol (tj. takového, který leží mezi generátory nebo je blíže k nim). V kroku 1.3 algoritmu č. 2 dochází k nahrazení listu podstromem (ilustrováno na obrázku č. 37) následované vyvážením celého stromu T. Vyvážení stromu T je třeba provést pro případ vkládání levého a pravého syna kořene nahrazujícího stromu a (viz p1.1 a p1.2 na obrázku č. 37).
32
Obrázek 37. Ilustrace zpracování události generátoru (vložení nového podstromu následované vyvážením T) a následné zpracování kružnicové události (odebrání daného listu a úprava vnitřních uzlů stromu T)
V kroku 2.1 algoritmu č. 2 dochází při obsloužení kružnicové události k výmazu zanikajícího parabolického oblouku a tedy k výmazu odpovídajícího listu z T. Po této operaci je třeba provést výmaz rodiče odebíraného listu z T, úpravu záznamů ve vnitřních uzlech (prarodič a praprarodič atd.) a korektní nastavení ukazatelů mezi rodičem a prarodičem odebíraného uzlu z T. Na obrázku 37 je ukázán příklad odebírání listu označeného jako RL. V následujícím algoritmu č. 6 je celý tento proces podrobně znázorněn. Algoritmus č. 6: VYMAŽ_LIST(RL) Vstup:
Odebíraný list RL ∈ T představující parabolický oblouk při výpočtu algoritmu č. 2, který zanikne při vzniku kružnicové události.
Výstup: Korektně upravený strom T po odebrání listu RL. 1. 2. 3. 4. 5. 6. 7. 8. 9.
P = RL.parent; GP = P.parent; if P je levý potomek jeho rodiče SN = P.right; SN.parent = GP; if GP je levý potomek jeho rodiče GP.left = SN; else GP.right = SN;
33
10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.
else SN = P.left; SN.parent = GP; if GP je levý potomek jeho rodiče GP.left = SN; else GP.right = SN; RLL = RL.leftLeaf; RRR = RL.rightLeaf; if GP existuje if GP je levý potomek jeho rodiče GP.pi = findMostRightLeaf(SN); else GP.pj = findMostLeftLeaf(SN); node = GP; while node.parent stále existuje if node.whichChild() == left node.parent.pi = findMostRightLeaf(node); else node.parent.pj = findMostLeftLeaf(node); node = node.parent;
Poznámka: funkce findMostRightLeaf() nebo findMostLeftLeaf() vrací nejpravější nebo nejlevější listový uzel daného podstromu. Proměnná P představuje rodiče, proměnná GP prarodiče, proměnná SN sourozenecký uzel, proměnná RLL levý listový uzel a proměnná RRR pravý listový uzel odebíraného listového uzlu RL. Listy stromu T jsou sekvenčně propojeny. První část algoritmu po řádek 16. včetně slouží pro odstranění rodiče odebíraného listového uzlu a následující část algoritmu slouží pro úpravu záznamů (pi, pj) uvnitř vnitřních uzlů z prarodiče do kořenového uzlu. Další částí, která již není vložena ve výpisu algoritmu č. 6, představuje vyvážení celého stromu. V kroku č. 2 algoritmu č. 2 dochází k napojení konců hran sousedních generátorů ke středu kružnice obsluhované kružnicové události. Ukazatele na hrany sousedních generátorů jsou získány ze společného předka listového uzlu a jeho levého listového předchůdce a dále ze společného předka listového uzlu kružnicové události a jeho pravého listového následníka. Příkladem může být opět obrázek č. 37, kde pro uzel RL a RRL je společný předek uzel P ve kterém je uložen ukazatel na koncový uzel napojované hrany. Posledním krokem po výpočtu algoritmu č. 2 je napojení zbylých hran ze stromu T na ohraničující oblast. V pořadí inorder se prochází uzly stromu T a hrany, které mají nulovou délku (tj. hrany, které jsou v uzlech V°(P) na okraji diagramu) se napojí na hranici oblasti.
34
6.4 Uživatelské prostředí programu Uživatelské prostředí (viz obr. č. 38) je tvořeno kreslící plochou pro vytvoření reálného světa W a dále kreslící plochou pro návrh tvaru robota. Dále ovládacími prvky pro konstrukci bodových, liniových nebo polygonových překážek a prvky pro vygenerování V°(P) pro W nebo C. Je třeba zdůraznit, že bodová překážka musí mít vždy nulový index a ohraničující polygonová oblast má vždy index roven jedné. Dále je zde možnost určení přesnosti K pro danou překážku.
Obrázek 38. Uživatelské prostředí implementovaného programu
35
Kapitola 7
Experimentální výpočty Výsledky experimentálního výpočtu V°(P) pomocí zametacího algoritmu pro množinu náhodně vygenerovaných bodových generátorů na stroji o konfiguraci AMD Sempron procesor 3000+ MHz jsou vyneseny v grafu na obrázku č. 39. Do výpočtu je zahrnut i proces počátečního vložení všech událostí generátoru do prioritní fronty (třídění generátorů dle y–ové souřadnice). 450 400 350
čas (s)
300
N log(N) / 1000
250 200 150
měření (ms) / 1000
100 50
N / 1000
0 0
10000
20000
30000
40000
50000
60000
70000
80000
Počet náhodných bodových generátorů (N)
Obrázek 39. Graf závislosti doby výpočtu V°(P) na počtu náhodných bodových generátorů
Na obrázku č. 40 je postupně zobrazen V °(O) = {V (oi ),...,V (on)} vytvořený pomocí aproximačního algoritmu pro přesnosti K = 60, 40, 30, 10 a 5 udávající délku segmentů aproximujících každou hranu liniových nebo polygonových generátorů bodovými generátory o průměru 5 obrazových bodů. Rozměry oblasti byly zvoleny na 840 x 580 obrazových bodů. Na posledním obrázku s přesností K = 1 je navíc zobrazena nejkratší cesta z počáteční do koncové konfigurace.
K = 60
K = 40
36
K = 30
K = 10
K=5 Obrázek 40. V°(O) pro W s přesností postupně pro K = 60, 40, 30, 10 a 5 pro bodové, liniové a polygonové generátory
Další experiment představuje výpočet V °(O) = {V (oi ),...,V (on)} pro stejné prostředí jako v předchozím případě, ale pro CB v konfiguračním prostoru C pro trojúhelníkového robota. Opět pro přesnosti K = 60, 40, 30, 10 a 5 na obrázku č. 41. Rozměry oblasti byly zachovány na 840 x 580 obrazových bodů.
37
K = 60
K = 40
K = 30
K = 10
K=5 Obrázek 41. V°(O) pro C s přesností postupně pro K = 60, 40, 30, 10 a 5 pro bodové, liniové a polygonové generátory
38
Graf závislosti doby výpočtu V°(O) pro W (plná čára) a C (čárkovaná čára) s překážkami (viz obr. č. 40 a obr. č. 41) na přesnosti K je na obrázku č. 42. Na grafu na obrázku č. 43 je počet bodových generátorů pro první experiment označen N1 a pro druhý experiment N2. Navíc je zde zobrazena logaritmická a lineární hranice pro porovnání pro oba případy. Rozdíl ve zpoždění výpočtu ve druhém případě pro C lze zdůvodnit především výpočtem Minkowského rozdílu robota a překážek, protože počet aproximačních bodových generátorů pro C se nezvýší o řád oproti počtu aproximačních generátorů pro W a výpočet překryvu CB trvá přibližně stejný čas i pro preventivní výpočet překryvu zadaných B ∈ W . Nakonec je třeba zdůraznit, že kód neprošel důraznou optimalizací a implementace je provedena v jazyce Java (kód je spuštěn na virtuálním stroji).
60 50
C
čas (s)
40 30 20 10
W 0 0
10
20
30
40
50
60
70
přesnost (K )
Obrázek 42. Graf závislosti doby výpočtu V°(O) pro bodové, liniové a polygonové generátory B ∈W z obrázku č. 40 (plná čára) a pro polygonové generátory CB ∈ C z obrázku č. 41 (čárkovaná čára) na přesnosti K
39
70
N 2 log(N 2) / 1000
60
čas (s)
50
N 1 log(N 1) / 1000
40 30
měření pro N 2 (ms) / 1000
20
měření pro N 1 (ms) / 1000
10
N 1 / 1000
0 0
2000
4000
6000
8000
10000
N 2 / 1000 12000
14000
16000
počet generátorů (N )
Obrázek 43. Graf závislosti doby výpočtu V°(O) pro bodové, liniové a polygonové generátory B ∈W z obrázku č. 40 (plná čára) a pro polygonové generátory CB ∈ C z obrázku č. 41 (čárkovaná čára) na počtu bodových (aproximujících) generátorů (N1 pro první a N2 pro druhý experiment)
40
Závěr Diplomová práce se zabývala řešením problému bezkolizního přesunu bodového nebo polygonového konvexního robota mezi bodovými, liniovými nebo konvexními polygonovými překážkami pomocí prostředků výpočetní geometrie. Vedle translačního pohybu byl předložen návrh i pro rotační pohyb. Dále byl diskutován problém bezkolizního přesunu skupiny polygonových konvexních robotů. Zavedením konfiguračního prostoru (de Berg a kol., 2000, Latombe, 1991) se redukoval problém nalezení cesty pro polygonového konvexního robota na problém nalezení cesty pro bodového robota. Výpočet konfiguračního prostoru pomocí uvedeného algoritmu má časovou složitost O(k (ni + m)) , i = 1,..., k , kde k je počet překážek, m počet vrcholů konvexního polygonového robota a ni je počet vrcholů i–té konvexní polygonové překážky. Podle (de Berg a kol., 2000), v případě, že jeden z polygonů není konvexní, je časová složitost O(nm) a O (n 2 m 2 ) v případě, že oba polygony nejsou konvexní. Řešení problematiky bezkolizního pohybu bylo řešeno s pomocí retrakčního přístupu, který umožňuje přímou konstrukci grafu cest reprezentující spojitost konfiguračního prostoru. Jedná se o redukci problému nalezení cesty mezi překážkami v konfiguračním prostoru na problém nalezení cesty v grafu tvořeného např. použitým Voroného diagramem (de Berg a kol., 2000, Okabe a kol., 2000). Užitečnou vlastností Voroného diagramu je jeho implicitní udržování největší možné vzdálenosti od všech překážek (generátorů), bohužel za cenu poměrně složité implementace algoritmů počítajících tento diagram. Existuje několik metod tvorby Voroného diagramu (de Berg a kol., 2000, Okabe a kol., 2000) pro bodové generátory. V práci byla podrobněji diskutována metoda zametací (plane sweep) s časovou složitostí O (n log n) , která je následně použita i pro tvorbu Voroného diagramu s bodovými, liniovými nebo polygonovými generátory pomocí předloženého aproximačního algoritmu. Představený implementovaný aproximační algoritmus pro bodové, liniové a polygonové generátory počítá Voroného diagram s určenou přesností, kde parabolické oblouky (hrany) Voroného diagramu vypočteného pomocí nativního algoritmu pro bodové a liniové generátory (viz kapitola 4.3), jsou nahrazeny sekvencí liniových segmentů. Způsobené zpoždění výpočtu záleží na zvolené postačující přesnosti. Rotační pohyb je v práci podle návrhu (de Berg a kol., 2000) pro lichoběžníkovou dekompozici řešen i pro Voroného diagram. Konfigurační prostor pro translační a rotační pohyb představuje sadu vzájemně propojených vrstev Voronových diagramů pro každé možné natočení robota. Hledání samotné nejkratší cesty poté probíhá ve vzniklém 3D grafu reprezentující 3D konfigurační prostor. Přesun skupiny robotů je postaven na myšlence (Reynolds, 1987) shromažďující se ho (flocking) modelu, který zahrnuje tři jednoduchá pravidla pro udržení koheze, vzájemné bezkoliznosti a stejného směru jednotlivých členů skupiny robotů. Obecné tzv. řízené chování skupiny robotů podle (Bayazit a kol., 2002) slouží pro samotný přesun skupiny z počáteční do koncové pozice. V jednotlivých částech diagramu lze toto chování změnit dle nastavených parametrů v uzlech diagramu (např. změna chování skupiny při průchodu úzkým koridorem). Detekce kolizí robotů (v konfiguračním prostoru) s překážkami probíhá pomocí senzorů a kolize mezi roboty samotnými se řeší aplikací pravidla separace ze skupinového shromažďující se ho chování. Výhodou je jednoduchost a škálovatelnost tohoto řešení ovšem za cenu poměrně velkého nároku na výpočetní výkon. Jak je naznačeno v předchozím textu, samotné implementace v práci zahrnují netriviální implementaci zametacího algoritmu pro bodové generátory obsahující implementaci AVL stromu a binární haldy, implementaci aproximačního algoritmu využívající zametací algoritmus pro bodové, liniové a polygonové generátory, implementaci algoritmu výpočtu Minkovského sumy robota a překážek pro výpočet konfiguračního prostoru, implementaci Grahamova algoritmu pro nalezení konvexního obalu, implementaci A* algoritmu pro nalezení nejkratší cesty a implementaci Union–
41
Find algoritmu pro udržení informace o překryvu jednotlivých překážek. Text může sloužit jako podrobně zpracovaná dokumentace implementace zametacího algoritmu včetně popisu ošetření netriviálních kroků (degenerované případy, udržování datových struktur pro zachování výkonnosti) standardně neuváděných v běžné literatuře. Poměrně podrobně jsou rozebrány i časové složitosti jednotlivých algoritmů. Mezi návrhy lze zařadit samotné řešení a formální popis rotačního pohybu robota inspirované řešením rotačního pohybu robota pro lichoběžníkové rozdělení konfiguračního prostoru. Dalším předloženým návrhem je plánování pohybu skupiny robotů pomocí kombinace jednoduchých pravidel shromažďujícího se chování, ve kterém se používají pravidla inspirovaná pravidly z přirozeného života, a postupů z nedávné literatury. Experimentální výpočty mohou poskytnout představu o výkonnosti aproximačního algoritmu s danou přesností na konkrétním stroji. Další práce by mohla zahrnovat implementaci nativního zametacího algoritmu pro výpočet Voroného diagramu pro bodové a liniové generátory a jeho použití pro výpočet zobecněného Voroného diagramu pro polygonové generátory, plánování a implementace nejkratší cesty bez použití předem zjištěné podkladové mapy překážek a návrh a implementace algoritmu pro výpočet Voroného diagramu pro 3D prostředí s překážkami a to vše včetně rotačního pohybu.
42
Literatura BAYAZIT, O.B., LIEN, J., AMATO, N. Better Flocking Behaviors in Complex Environments using Global Roadmaps. In Proceedings of the Workshop on Algorithmic Foundations of Robotics. Nice, France : 2002. BAYAZIT, O.B., LIEN, J., AMATO, N. Better Group Behaviors in Complex Environments using Global Roadmaps. In Proceedings of the eight International Conference on Artificial life. Cambridge, MA, USA : 2002, s. 362 – 370. BAYAZIT, O. B., LIEN, J., AMATO, N. Better Group Behaviors using Rule–Based Roadmaps. In Proceedings of the Workshop on Algorithmic Foundations of Robotics. Nice, France : 2002. DE BERG, M., VAN KREVELD, M., OVERMARS, M. & SCHWARZKOPF, O. Computational Geometry: Algorithms and Applications. 2. vyd. Berlin : Springer–Verlag, 2000. 367 s. ISBN: 3–540–65620–0. KNUDSEN, J., NIEMEYER, P. Learning Java. 3. vyd. Sebastopol : O’Reilly, 2005. 976 s. ISBN 0–596–00873–2. KONAR, A. Artificial Intelligence and Soft Computing: Behavioral and Cognitive Modeling of the Human Brain. 1. vyd. London : CRC Press, 2000. 787 s. ISBN 0–849–31385–6. KORF, R. Artificial Intelligence Search Algorithms. In Algorithms and Theory of Computation Handbook. Los Angeles : CRC Press, 1999, s. 36–1–36–20. ISBN 0–849–32649–4 LATOMBE, J. C. Robot Motion Planning. 1. vyd. Norwell : Kluwer, 1991. 672 s. ISBN: 0–792–39206–0. LAVALLE, S., Planning Algorithms. 1. vyd. Cambridge : Cambridge University Press, 2005. 1014 s. ISBN 0–521–186205–1. MASCIOTRA, A., RODRIGUEZ, S., LIEN, J., AMATO, N. Composable Group Behaviors, Technical Report. Parasol Laboratory, Texas : Department of Computer Science, Texas A&M University : 2005. OKABE, A., BOOTS, B., SUGIHARA, K. & CHIU, S., N. Spatial Tesselations: Concepts and Applications of Voronoi Diagrams. 2. vyd. Chichester : John Wiley & Sons, 2000. 584 s. ISBN 0–471–98635–6. O’ROURKE, J. Computational geometry in C. 2. vyd. Cambridge : Cambridge University Press, 1998. 390 s. ISBN 0–52164–976–5. PREISS, B. R. Data Structures and Algorithms with Object–Oriented Design Patterns in Java. 1. vyd. University of Waterloo, 2000. 656 s. ISBN 0–471–34613–6.
43
REYNOLDS, C. W. Flocks, Herds, and Schools: A Distributed Behavioral Model. In SIGGRAPH ’87 Conference Proceedings. New York : ACM Press, 1987, s. 25–34. ISBN 0–89791–227–6. REYNOLDS, C. W. Interaction with Groups of Autonomous Characters. In Proceedings of Game Developers Conference 2000. San Francisco, California : 2000, s. 449–460. REYNOLDS, C. W. Steering Behaviours for Autonomous Characters. In Proceedings of Game Developers Conference 1999. San Francisco, California : 1999. s. 763–782. RUSSEL, S. J., NORVIG, P. Artificial Intelligence: A Modern Approach. 1. vyd. New Jersey : Prentice–Hall, 1995. 932 s. ISBN 0–131–03805–2. SEDGEWICK, R. Algorithms in Java: Parts 1 – 4 3. vyd. Boston : Addison Wesley, 2002. 768 s. ISBN 0–201–36120–5. SCHNEIDER, P. J., EBERLY, D. H. Geometric Tools for Computer Graphics. 1. vyd. San Francisco : Morgan Kaufmann Publishers, 2003. 1007 s. ISBN 1–55860–594–0.
44
