Romana Seidlová, Jaroslav Poživil
V prvopočátku byly metody pro plánování (projektování) cesty využívány zejména při řešení problému obchodního cestujícího, za účelem ušetřit jeho čas, a především náklady na dopravu. V současné době je projektování cesty mimo jiné důležitým tématem v robotice, je-li ve snaze po jeho lepším využití po robotu vyžadována určitá samostatnost. V posledních několika letech zažívá velký rozmach metoda projektování cesty robotu prostředím s překážkami s využitím rojové inteligence. Rojová inteligence patří mezi biologicky inspirované metody umělé inteligence. V článku je podrobně popsána metoda projektování cesty robotu inspirovaná chováním kolonie mravenců při hledání nejkratší cesty ke zdroji potravy, která byla popsána teprve nedávno, ale ukazuje se jako velmi perspektivní.
Nowadays, the problem of path planning is an important subject theme in the robotics, allowed to autonomous robots receives better utilization. In recent years, the solution based on the swarm intelligence is frequently used theme and is one of the biologically inspired artificial intelligence methods. The article introduces in detail the method for path planning inspired by the behavior of ant colonies, which was recently described and seems to be very perspective. The ant colony optimization (ACO) is perspective optimization algorithm inspired by the behavior of ants in their search for the shortest paths to food source.
1. Úvod
Projektování cesty je důležitá úloha při navigaci a řízení pohybu autonomních robotů. V teorii složitosti je projektování cesty klasifikováno jako nedeterministicky polynomiální (NP) úplný problém. Je známo, že výpočetní doba potřebná k řešení problémů kategorie NP s rostoucí velikostí problému prudce roste (obvykle exponenciálně).
Nechť robot A je tuhý objekt pohybující se ve dvoj- nebo trojrozměrném eukleidovském prostoru (tzv. pracovní prostor W) a nechť překážky B1 až Bn jsou pevné předměty rozmístěné v prostoru W. Za předpokladu, že neexistuje žádné kinematické omezení pohybu, lze problém projektování cesty formulovat takto: je dána počáteční a cílová pozice a orientace objektu A v prostoru W, projektovaná cesta je určena sledem poloh a orientací objektu A takovým, aby objekt A při cestě z počáteční do cílové polohy nepřišel do kontaktu se žádným z objektů B1 až Bn; jestliže žádná taková cesta neexistuje, je ohlášena chyba.
Analýzy zaměřené na projektování cest se začaly objevovat od konce 60. let minulého století a bylo navrženo mnoho různých algoritmů, včetně přístupu „roadmap“, mobilní dekompozice či algoritmů založených na potenciálových polích. Bylo zjištěno, že uvedené metody jsou pro svou velkou výpočetní náročnost neúčinné nebo vzhledem k zachycování lokálních minim nepřesné. K překonání těchto omezení bylo vyvinuto mnoho heuristických postupů, např. využití umělých neuronových sítí. Jednou z hlavních předností heuristických algoritmů je schopnost velmi rychle dosáhnout přijatelného řešení, což je zvláště vhodné pro řešení úplných NP problémů.
Algoritmus založený na mravenčích koloniích (Ant Colony Optimization – ACO) představuje metaheuristický přístup inspirovaný chováním biologických mravenců v reálném světě. Jde o jeden z nejúspěšnějších vzorů inteligentních rojových systémů, který byl použit k řešení problémů mnoha různých typů, jako např. optimalizace nelineárních objektivních funkcí nebo síťového směrování v telekomunikačních sítích.
2. Algoritmus optimalizace mravenčí kolonie
Je známo, že biologičtí mravenci v reálném světě jsou k nalezení nejkratší cesty k potravě schopni využít inteligenci roje. Pro heuristické řešení optimalizačních problémů byly vyvinuty algoritmy ACO, které napodobují chování skutečných mravenců.
Mnoho druhů mravenců zanechává při shánění potravy na podkladu, po němž se pohybují, nestabilní chemické látky zvané feromony [1]. Tímto způsobem vznikají tzv. feromonové cesty. Mravenci feromon cítí a při výběru cesty mají tendenci s větší pravděpodobností vybírat cesty s větší koncentrací feromonů. Čím více mravenců projde danou cestu, tím více feromonu je položeno a roste pravděpodobnost, že si tuto cestu vybere i další mravenec. Nejvíce feromonů se hromadí na nejkratší cestě k potravě, k jejímuž zdolání mravenci potřebují nejkratší dobu. Tento jev byl poprvé pozorován při známém experimentu s dvojitým mostem (experiment double bridge [2], viz obr. 1). S časem množství feromonu uloženého mravenci podél kratší větve cesty roste rychleji, a kratší větev se tak stává více a více atraktivní pro další mravence (jde o rekurzivní chování označované jako autokatalýza).
Napodobování mravenčích kolonií tvoří základ pravděpodobnostní výpočetní metaheuristické metody využitelné k řešení komplexních problémů, které je možné vyjádřit jako hledání optimální cesty v grafu [3], [4].
Umělý mravenec k nacházející se ve vrcholu i grafu G = (V, E), kde V = {v1,…,vn} jsou vrcholy a E = {(vi, vj)|vi, vj ∈ V, i ≠ j} jsou hrany, se přesune do sousedního vrcholu j s pravděpodobností pki j, kterou lze vyjádřit vztahem
rovnice 1
kde
Nki je množina všech vrcholů dostupných mravenci k (tzn. množina vrcholů, do kterých vede z i hrana),
τij množství feromonu na hraně (vi, vj),
τil množství feromonu na hraně (vi, vl).
Každý mravenec provede během jedné iterace výpočtu zadaný počet kroků vpřed. Trasu mezi jednotlivými vrcholy pomyslní mravenci volí podle pravidla (1). Jakmile mravenci dokončí své putování grafem, vracejí se do hnízda s úlovkem. Konkrétní trasa k-tého mravence Tka délka této trasy Ckvyjadřují kvalitu nalezeného řešení a jsou použity pro výpočet množství feromonu, který mravenec ukládá na každou hranu cesty, po které se v dané iteraci pohyboval, takto
rovnice 2
rovnice 3
kde
Δτijk je nově uložené množství feromonu na hranu (vi, vj),
τijnew nové množství feromonu uložené na hraně (vi, vj),
m celkový počet mravenců.
Aby se zabránilo uváznutí řešení úlohy v lokálním minimu, předpokládá se v mravenčích algoritmech také vypařování feromonové stopy, čímž během času klesá pravděpodobnost, že mravenec zvolí stejnou cestu jako jeho předchůdci. Naproti tomu je rychlost ukládání feromonu stále větší než rychlost odpařování. V základní variantě optimalizace mravenčí kolonie se po každé iteraci množství feromonu uloženého na každé jednotlivé hraně zmenší podle vztahu
rovnice 4
kde ρ (0, 1) je rychlost odpařování feromonu.
Pseudokód uvedeného algoritmu lze zapsat způsobem podle obr. 2.
3. Algoritmus projektování cesty robotu
Jedním z algoritmů projektování cesty robotu založených na optimalizaci mravenčí kolonie, který dosahuje velmi dobrých výsledků, je algoritmus popsaný v [5]. Schéma tohoto algoritmu je uvedeno na obr. 3.
Předpokládejme, že robot se pohybuje po ploše vymezené kladnými poloosami x a y, na níž jsou náhodně rozmístěny překážky, jejichž polohy robot nezná (obr. 4). Souřadnice počátečního bodu cesty robotu (source) jsou (XS, YS) a souřadnice cílového bodu (target) jsou (XT, YT). Počáteční směr pohybu robotu je dán úhlem θ podle
rovnice 5
V závislosti na typu problému je nutné definovat vhodně zvolený graf G = (V, E), např. pravoúhlou nebo triagonální síť, která popř. není pravidelná.
Činnost algoritmu [5] je poté takováto:
1. Robot vyjde z pevného počátečního bodu (XS, YS).
2. Robot udělá jeden krok o délce L. Poloha robotu se změní z (XS, YS) na (XSnew, YSnew) a robot takto dále pokračuje v azimutu θ posloupností poloh XSnew, YSnew, pro něž platí
rovnice 6
rovnice 7
kde Xprev, Yprev jsou souřadnice polohy robotu před každým jednotlivým krokem.
3. Robot před každým dalším krokem zjistí, zda v aktuální budoucí poloze (XSnew,YSnew) není překážka. Jestliže není, robot krok provede.
4. Je-li v daném místě překážka, robot se zastaví a vrátí se tři kroky zpět, tedy
rovnice 8
rovnice 9
5. Robot musí obejít překážku a po optimální cestě nakonec dosáhnout pevného cílového bodu (XT,YT).
6. K nalezení optimální cesty k obejití překážky se použije algoritmus optimalizace mravenčích kolonií. Tento algoritmus je realizován v několika iteracích, pokaždé ve dvou fázích:
a) v první fázi mravenci postupně procházejí po hranách sítě podle volby na základě pravděpodobnostního vzorce (1); obecně se během této fáze mravenec k nachází v uzlu i a na hraně (vi, vj) je uloženo množství τijferomonu,
b) ve druhé fázi, jakmile všichni mravenci dosáhnou cíle (XT, YT), se globálně aktualizuje množství feromonů podle vztahů (3) a (4).
7. Proces „mravenčí“ optimalizace, probíhající v několika po sobě jdoucích iteracích, končí splněním ukončujících podmínek, ke kterým může patřit nalezení optimálního řešení, určitý počet iterací bez zlepšení nebo jednoduše dosažení určitého počtu iterací. Příklad cesty robotu nalezené při použití algoritmu ACO je na obr. 5.
Závěr
V článku je představen algoritmus založený na chování kolonií mravenců, který je určen k nalezení nejkratší cesty mobilního robotu z výchozího bodu do zadaného cílového bodu vyhýbající se překážkám. Tento algoritmus sice při realizaci v praxi vykazuje určité problémy, které představují výzvu pro budoucí výzkum, avšak při jeho porovnání s genetickým algoritmem [3] bylo zjištěno, že „mravenčí“ algoritmus je rychlejší a efektivnější (viz tab. 1 a obr. 6). Bez ohledu na počet překážek ve zkoumaném prostoru se doba běhu algoritmu prodlužuje jen málo. Lze se domnívat, že tento způsob projektování optimální cesty robotu je velmi perspektivní.
Literatura:
[1] HÖLLDOBLER, B. – WILSON, E. O.: The Ants. Berlin, Springer-Verlag, 1990.
[2] GOSS, S. – ARON, S. – DENEUBOURG, J. L.. – PASTEELS, J. M.: Self-organized Shortcuts in the Argentine Ant. Naturwissenchaften,
1989, Issue 76, pp. 579–581, Springer-Verlag.
[3] DORIGO, M. – STÜTZLE, T.: Ant Colony Optimization. Cambridge, MA: MIT Press, 2004.
[4] ABRAHAM, A. – GUO, H. – LIU, H.: Swarm intelligence: Foundations, perspectives and applications. In: Swarm Intelligent Systems,
ser. Studies in Computational Intelligence, N. Nedjah and L. de Macedo Mourelle, Eds., 2006, Vol. 26, pp. 3–25, Springer.
[5] GIGRAS, Y. – GUPTA, K.: Artificial Intelligence in Robot Path Planning. International Journal of Soft Computing and Engineering
(IJSCE), May 2012, Vol. 2, Issue 2, ISSN 2231-2307.
[6] BUNIYAMIN, N. – SARIFF, N. – WAN NGAH, W. A. J. – MOHAMAD, Z.: Robot global path planning overview and a variation
of ant colony system algorithm. International Journal of Mathematics and Computers in Simulation, 2011, Vol. 5, Issue 1, pp. 9–16.
Mgr. Romana Seidlová,
Ústav počítačové a řídicí techniky,
Vysoká škola chemicko-technologická v Praze
doc. Ing. Jaroslav Poživil, CSc.,
katedra informačních technologií a analytických metod,
Vysoká škola obchodní v Praze
Lektoroval: prof. Ing. Pavel Ošmera, CSc.
Obr. 1. Schéma experimentu s dvojitým mostem (tzv. double bridge experiment, [2])
Obr. 2. Pseudokód „mravenčího“ algoritmu vyhledání optimální cesty v grafu
Obr. 3. Schéma algoritmu pro projektování cesty robotu [5]
Obr. 4. Geometrické uspořádání problému projektování cesty robotu po ploše s překážkami
Obr. 5. Příklad optimální cesty robotu nalezené algoritmem [5]
Obr. 6. Počty iterací potřebných k nalezení optimální cesty (převzato ze [3], s úpravou)
Tab. 1. Porovnání genetického algoritmu a algoritmu založeného na chování mravenčích kolonií (ACO) z hlediska počtu iterací a času potřebného k nalezení optimální cesty (převzato ze [3], s úpravou)