p15804_iconMetóda potenciálových polí je jednou z metód, ktoré sa používajú pre plánovanie cesty robotov v prostredí s prekážkami. Daná metóda je ľahko pochopiteľná a použiteľná pre statické aj dynamické prostredie. Avšak, má jeden nedostatok, možnosť tvorby lokálnych miním. Ten je možné odstrániť použitím harmonických potenciálových polí. Predkladaný článok je zameraný práve na popis harmonických potenciálových polí a na ich použitie pre statické prostredie s prekážkami. Článok obsahuje aj dosiahnuté simulačné výsledky pre pohyb robota v dvojrozmernom prostredí s prekážkami.

Úvod

V posledných rokoch je známych viacero metód, ktoré sa používajú pre plánovanie cesty robotov. Plánovanie cesty robotov úzko súvisí s navigáciou a riadením robotov. V súčasnosti sa čoraz viac ľudia snažia dať robotom „dušu“. Umelá inteligencia je veľmi často spájaná s robotikou s cieľom dosiahnuť autonómnosť robotov. K metódam plánovanie cesty robotov patrí aj metóda potenciálových polí. Čo vlastne rozumieme pod pojmom plánovanie? V odbore robotika je možné definovať plánovanie ako nájdenie algoritmu pre pohyb robota v prostredí tak, že sa dostane z počiatočnej do cieľovej pozície. V prostredí sa môžu nachádzať aj prekážky, čo znamená, že algoritmus musí zabezpečiť ich obchádzanie.

Princíp metódy potenciálových polí

Metóda potenciálových polí patrí k metódam plánovania na mriežke. Princíp plánovania na mriežke môžeme vysvetliť nasledovne. Predstavme si prostredie, v ktorom sa robot nachádza a môže pohybovať. Dané prostredie rozdeľme na n buniek. Každá bunka bude reprezentovať určitú časť prostredia. Takýmto spôsobom dostaneme prostredie, ktoré sa bude skladať z konečného n počtu buniek, čo pripomína mriežku. Dá sa povedať, že takto vytvorené virtuálne prostredie (mriežka) reprezentuje reálne prostredie. Metóda potenciálových polí je založená na rovnakom princípe, a preto patrí k metódam plánovania na mriežke.

Pohyb robota v takto virtuálnom prostredí je založený na princípe sledovania hodnôt jednotlivých buniek. To môžeme vysvetliť nasledovne. Majme prostredie rozdelené na určitý počet buniek, kde každá bunka reprezentuje určitú oblasť prostredia. Každej bunke priradíme určitú hodnotu. Ak cieľovej bunke priradíme najnižšiu hodnotu v prostredí, tak pohyb robota bude riadený sledovaním tejto najnižšej hodnoty. Môžeme povedať, že metóda potenciálových polí využíva princíp minima a maxima, čo znamená, že cieľovej bunke musí byť priradená najnižšia hodnota v prostredí a všetkým prekážkam najvyššia hodnota v prostredí (za prekážku považujeme aj hranice prostredia). Ak je táto podmienka splnená, tak pohyb robota je riadený od najvyššej do najnižšej hodnoty v prostredí. Dá sa povedať, že cieľová bunka musí byť globálne minimum prostredia a prekážky globálne maximum.

Keďže pri metóde potenciálových polí vytvárame virtuálnu mapu reálneho prostredia, musia byť splnené nasledujúce podmienky. Pozícia cieľa a pozícia všetkých prekážok v prostredí musí byť vopred známa (určená). Ak tieto podmienky nie sú splnené, tak použitie metódy potenciálových polí nie je možné. Je potrebné ešte poznamenať, že hranice priestoru považujeme za hranice prekážok. Tým, že metóda potenciálových polí využíva princíp minima a maxima, vzniká riziko tvorby lokálnych miním. Čo vlastne znamená lokálne minimum? V tomto prípade, lokálne minimum môžeme definovať ako bunku v prostredí, kde každá susedná bunka má vyššie ohodnotenie ako daná bunka. Ak sa robot dostane do tejto situácie, tak si „myslí“, že sa dostal do cieľovej bunky, avšak táto bunka nie je cieľová, zacyklí sa na tejto pozícií a nikdy nedosiahne cieľovú pozíciu.
Samotná metóda potenciálových polí nie je schopná odstrániť možnosť tvorby lokálnych miním, a to je jej hlavný nedostatok.

Metóda harmonických potenciálových polí

Nedostatok metódy potenciálových polí, tvorbu lokálnych miním, je možné odstrániť pomocou metódy harmonických potenciálových polí. Funguje na rovnakom princípe ako potenciálové polia, avšak má jednu podstatnú výhodu. Táto metóda je schopná generovať resp. vytvárať prostredie, kde existuje iba jedno minimum a maximum, a to globálne minimum a globálne maximum. Táto vlastnosť je veľmi dôležitá pre pohyb robota, ktorý je riadený sledovaním najnižšej hodnoty. Ak bude cieľová bunka reprezentovaná globálnym minimom prostredia, a ak prekážky budú reprezentované globálnym maximom prostredia, tak robot bude schopný prísť do cieľovej pozície z akejkoľvek pozície v prostredí.

Matematicky je možné podľa [1] popísať potenciálové pole nasledovne. Uvažujme konzervatívne pole F, ktoré je definované potenciálom φ v tvare:

\vec{F} = -\triangledown \varphi (1)

Ak platí rovnica (1) a pole F je konzervatívne, tak dané pole nazývame potenciálovým poľom. Potenciálové pole má svoje určité vlastnosti. Jednou z nich je, že potenciál φ poľa F za určitých podmienok spĺňa druhú diferenciálnu rovnicu nazývanú Laplaceova rovnica, ktorá má tvar:

\triangledown^2 \varphi = 0 (2)

v miestach neobsadenými zdrojmi F. Pre dvojrozmerný priestor môžeme rovnicu (2) zapísať v tvare:

\frac{\partial^2 \varphi}{\partial x^2} + \frac{\partial^2 \varphi}{\partial y^2} = 0 (3)

Ako je možné z názvu vidieť, metóda harmonických potenciálových polí je založená na harmonickej funkcii. Podľa [1] je možné harmonickú funkciu definovať ako funkciu, ktorá spĺňa nasledujúce kritéria:

  1. Spĺňa Laplaceovu rovnicu \triangledown^2 \varphi = 0
  2. Má spojitú prvú deriváciu
  3. Má druhú deriváciu

Harmonická funkcia má dôležité vlastnosti, ktoré sa využívajú pri metóde harmonických potenciálových polí. Funkcia, ktorá je harmonická nad priestorom R, musí mať maximum a minimum na hraniciach priestoru a nie vo vnútri priestoru. Práve táto vlastnosť harmonickej funkcie zaručuje, že pri metóde harmonických potenciálových polí nevznikajú žiadne lokálne minimá. Ďalšiu dôležitú vlastnosť harmonickej funkcie demonštruje definícia druhej derivácie funkcie φ(x). Druhá derivácia funkcie φ(x) (pre jednorozmerný priestor) je daná vzťahom:

\frac{d^2 \varphi(x_i)}{d x^2} \approx \frac{\varphi(x_{i+1})-2\varphi(x_i)+\varphi(x_{i-1})}{h^2} (4)

Z rovnice (4) a (2) vyplýva, že hodnota harmonickej funkcie φ(x) v nejakom bode sa rovná priemeru hodnôt tejto funkcie v jej susedných bodoch.

\varphi(x)=\frac{1}{2} lim_{\Delta x \rightarrow 0} [\varphi(x-\Delta x) + \varphi(x+\Delta x)] (5)

Nájsť riešenie Laplaceovej rovnice je problémom okrajových hodnôt Dirichletovho typu, t.j. je potrebné nájsť vyjadrenie φ pre celú oblasť R, pre ktorú vo vnútri oblasti platí rovnica (2) a na hraniciach oblasti R sú dané hodnoty φ. Plánovanie cesty robotov pomocou harmonických potenciálových polí pozostáva z dvoch problémov, ktoré je potrebné vyriešiť. Prvým je generovanie resp. vytvorenie harmonického poľa s globálnym minimom a maximom a druhým je vytvorenie algoritmu pre pohyb v tomto poli. Harmonické potenciálové pole môžeme vytvoriť nasledujúcim spôsobom. Keďže využívame princíp minima a maxima, je vhodné definovať okrajové podmienky pre hranice cieľa a hranice všetkých prekážok. Hľadané harmonické potenciálové pole musí teda spĺňať nasledujúce dve okrajové podmienky:

  1. \varphi |_R = c
  2. \varphi_{ciel} = 0

kde c je vopred určená konštanta. Prvá podmienka hovorí, že hranice všetkých prekážok budú nadobúdať maximálnu hodnotu funkcie φ (globálne maximum). Druhá podmienka hovorí, že cieľová pozícia bude mať minimálnu hodnotu funkcie φ (globálne minimum). Keďže už máme zadefinovanú hodnotu pre okrajové body a hodnotu pre všetky prekážky a cieľ, teraz je potrebné vyriešiť zvyšné body vo vnútri priestoru R. Pre tie bude platiť Laplaceova rovnica, a tým pádom je potrebné nájsť riešenie Laplaceovej rovnice. Analógiou s rovnicou (4) a podľa [1] a [2] vzniká vzťah pre výpočet Laplaceovej rovnice v tvare:

\varphi(x_i,y_j)=\frac{1}{4} [\varphi(x_{i+1},y)+ \varphi(x_{i-1},y)+ \varphi(x,y_{j+1})+ \varphi(x,y_{j-1})] (6)

Rovnica (6) platí pre dvojrozmerný priestor a vyplýva z nej dôležitá vlastnosť: Hodnota funkcie φ v bode [xi,yj] sa rovná priemeru hodnôt funkcie φ jej najbližších susedov. Keďže uvažovaný lineárny systém popísaný rovnicou (6) môže byť dosť rozsiahly, na výpočet je možné použiť metódy numerickej matematiky. Medzi tieto metódy patria Gauss-Seidelova metóda, relačná iteračná metóda, či Jacobiho metóda. Použitím jednej z týchto metód pre výpočet rovnice (6) a dostatočného počtu iterácií vznikne harmonické potenciálové pole, kde cieľová pozícia bude globálne minimum a hranice priestoru R a hranice všetkých prekážok budú globálne maximum. Zvyšné body priestoru budú nadobúdať hodnoty plynule od globálneho maxima ku globálnemu minimu.

Keďže prvý problém, vytvorenie harmonického potenciálového poľa je vyriešený, teraz je potrebné vytvoriť algoritmus, ktorý bude riadiť pohyb robota v tomto poli. Princíp tohto algoritmu spočíva v sledovaní najnižšej hodnoty priestoru, čiže globálneho minima, ktorým je cieľ. Môžeme povedať, že je založený na porovnávaní hodnoty aktuálneho bodu s hodnotami jeho susedných bodov. Je vhodné uvažovať osem-susednosť, t.j. v dvojrozmernom priestore sa robot môže pohybovať v každom smere. Keďže z princípu harmonickej funkcie vyplýva, že žiadne lokálne minimum nemôže existovať vo vnútri priestoru R, tak nemôže nastať situácia, že sa robot dostane do miesta, ktoré nie je cieľové. Tým, že cieľ je globálnym minimom priestoru, robot vždy príde do cieľovej pozície. Samozrejme, ak je cieľ dosiahnuteľný.

Je vhodné ešte poznamenať, že hodnoty okrajových podmienok pre hranice prekážok a cieľa môžu byť zadefinované aj opačne. To znamená, že cieľu priradíme hodnotu najvyššiu (globálne maximum) a hraniciam všetkých prekážok hodnotu najnižšiu (globálne minimum). V tomto prípade, algoritmus pre pohyb robota v tomto poli musí sledovať najvyššiu hodnotu priestoru, čiže pohyb bude smerovať od najnižšej do najvyššej hodnoty. Príklady vygenerovaných polí sú na obr.1 a obr.2. Na obr.1 je pole bez prekážok a na obr.2 je pole s prekážkami. V oboch prípadoch je cieľu priradené globálne maximum.

p15804_01_obr01
Obr.1 Príklad harmonického potenciálového poľa. Bez prekážok. Globálne maximum je v cieli

p15804_02_obr02
Obr.2 Príklad harmonického potenciálového poľa. S prekážkami. Globálne maximum je v cieli

Simulačné výsledky

Simulačné výsledky pre pohyb robota boli dosiahnuté v programe MATLAB. Harmonické potenciálové pole bolo vytvorené pomocou programu Student`s Quick Field. Pre simuláciu pohybu robota bolo použité virtuálne prostredie o veľkosti 42×42 bodov, v ktorom sa nachádza osem prekážok. Keďže sme uvažovali statické prostredie, pozícia prekážok a pozícia cieľa bola vopred daná a stála. V danom prostredí má cieľová pozícia súradnice [31, 18]. Na Obr. 3 môžeme vidieť vytvorenú aplikáciu pre simuláciu pohybu robota v uvažovanom prostredí. Biele resp. prázdne miesta reprezentujú prekážky a hranice prostredia, čierne bodky reprezentujú voľné miesta v prostredí, ktorými sa robot môže pohybovať. Aplikácia obsahuje vstup pre počiatočný (štartovací) bod, z ktorého sa robot bude pohybovať do cieľovej pozície. V tomto prípade, za štartovací bod bol zvolený bod so súradnicami [41,41]. Aplikácia umožňuje aj opätovné znovu zadanie štartovacieho bodu a spustenie simulácie.

p15804_03_obr03
Obr.3 Príklad simulácie pohybu robota

Metóda harmonických potenciálových polí je jednou z metód, ktoré sa používajú pre plánovanie cesty mobilných robotov. Cieľom plánovania pomocou tejto metódy je dosiahnuť požadovaný pohyb robota v prostredí, kde sa nachádza. Z dosiahnutých simulačných výsledkov vyplýva, že daná metóda je dobre aplikovateľná pre statické prostredie. Pri použití pre dynamické prostredie by bolo potrebné vyriešiť ešte viacero problémov spojených s dynamikou prostredia. Cieľom našej ďalšej štúdie je vytvorenie samotného algoritmu pre generovanie harmonického potenciálového poľa a rozšírenie už vytvoreného algoritmu pre pohyb v 3D prostredí.

Poďakovanie

Podporujeme výskumné aktivity na Slovensku/ Projekt je spolufinancovaný zo zdrojov EÚ. Tento článok bol vypracovaný v rámci projektu “Centrum excelentnosti integrovaného výskumu a využitia progresívnych materiálov a technológií v oblasti automobilovej elektroniky”, ITMS 26220120055. (100%)

Literatúra

  1. Blakely, J. R. Potential Theory in Gravity and Magnetic Applications. Cambridge: Cambridge University Press, 1996. 441 s. ISBN 0-521-57547-8
  2. Vaščák, J. Využitie potenciálových polí v navigácií mobilných robotov. Košice: TU FEI, 2008. Dostupné na internete:
    http://www.ai-cit.sk/source/navigacia/PPvNR.pdf
  3. Ge, S. S., Cui, I. J. New Potential Functions for Mobile Robot Path Planning. IEEE Transactions on Robotics and Automation, vol. 16, No. 5, 2000.
  4. Winkler, Z. Plánování na mřížce. 2003-12-03. [cit. 2012-20-03]. Dostupné na internete:
    http://robotika.cz/guide/gridplan/cs
  5. Shi, Ch., Zhang, M., Peng, J. Harmonic Potential Field Method for Autonomous Ship Navigation. Proceedings of the 7th International Conference on Intelligent Transport Systems Telecommunications. Sophia Antipolis, France, 2007. ISBN 1-4244-1178-5.
  6. Kellogg, O. D. Foundations of Potential Theory. New York, USA, 1953. ISBN 0-486-60144-7
  7. Latombe, J. C. Robot Motion Planning. Massachusetts, USA, 1991. 651 s. ISBN 0-7923-9129-2

Spoluautorom článku je Želmíra Ferková, Fakulta elektrotechniky a informatiky, Technická Univerzita v Košiciach

Napísať príspevok