VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV AUTOMATIZACE A INFORMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF AUTOMATION AND COMPUTER SCIENCE
ALGORITMY PRO HLEDÁNÍ CESTY ALGORITHMS FOR SEARCHING THE PATH
BAKALÁŘSKÁ PRÁCE BACHELOR‘S THESIS
AUTOR PRÁCE
MICHAL PAVLIŠ
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2007
Ing. TOMÁŠ MARADA, Ph.D.
Strana 2
Strana 3
ZADÁNÍ ZÁVĚREČNÉ PRÁCE Do práce je vložen vyplněný formulář “Zadání BP” s příslušnými razítky a podpisy děkana FS a ředitele ÚAI.
Strana 4
Strana 5
LICENČNÍ SMLOUVA POSKYTOVANÁ K VÝKONU PRÁVA UŽÍT ŠKOLNÍ DÍLO uzavřená mezi smluvními stranami: 1. Pan/paní Jméno a příjmení:
Michal Pavliš
Bytem:
Štefánikova 311, Hradec Králové, 500 11
Narozen/a (datum a místo):
11.11. 1983, Hradec Králové
(dále jen „autor“) a 2. Vysoké učení technické v Brně Fakulta strojního inženýrství se sídlem Technická 2896/2, 616 69 Brno jejímž jménem jedná na základě písemného pověření děkanem fakulty: Doc. RNDr. Ing. Miloš Šeda, Ph.D., ředitel ÚAI (dále jen „nabyvatel“)
Čl. 1 Specifikace školního díla 1. Předmětem této smlouvy je vysokoškolská kvalifikační práce (VŠKP): □ disertační práce □ diplomová práce □ bakalářská práce □ jiná práce, jejíž druh je specifikován jako ................................................. (dále jen VŠKP nebo dílo) Název VŠKP:
Algoritmy pro hledání cesty
Vedoucí/ školitel VŠKP:
Ing. Tomáš Marada, Ph.D.
Ústav:
Ústav automatizace a informatiky
Datum obhajoby VŠKP: VŠKP odevzdal autor nabyvateli v*: □ tištěné formě
*
–
počet exemplářů
2
□ elektronické formě –
počet exemplářů
3
hodící se zaškrtněte
Strana 6
2. Autor prohlašuje, že vytvořil samostatnou vlastní tvůrčí činností dílo shora popsané a specifikované. Autor dále prohlašuje, že při zpracovávání díla se sám nedostal do rozporu s autorským zákonem a předpisy souvisejícími a že je dílo dílem původním. 3. Dílo je chráněno jako dílo dle autorského zákona v platném znění. 4. Autor potvrzuje, že listinná a elektronická verze díla je identická.
Článek 2 Udělení licenčního oprávnění 1. Autor touto smlouvou poskytuje nabyvateli oprávnění (licenci) k výkonu práva uvedené dílo nevýdělečně užít, archivovat a zpřístupnit ke studijním, výukovým a výzkumným účelům včetně pořizovaní výpisů, opisů a rozmnoženin. 2. Licence je poskytována celosvětově, pro celou dobu trvání autorských a majetkových práv k dílu. 3. Autor souhlasí se zveřejněním díla v databázi přístupné v mezinárodní síti □ ihned po uzavření této smlouvy □ 1 rok po uzavření této smlouvy □ 3 roky po uzavření této smlouvy □ 5 let po uzavření této smlouvy □ 10 let po uzavření této smlouvy (z důvodu utajení v něm obsažených informací) 4. Nevýdělečné zveřejňování díla nabyvatelem v souladu s ustanovením § 47b zákona č. 111/ 1998 Sb., v platném znění, nevyžaduje licenci a nabyvatel je k němu povinen a oprávněn ze zákona.
Článek 3 Závěrečná ustanovení 1. Smlouva je sepsána ve třech vyhotoveních s platností originálu, přičemž po jednom vyhotovení obdrží autor a nabyvatel, další vyhotovení je vloženo do VŠKP. 2. Vztahy mezi smluvními stranami vzniklé a neupravené touto smlouvou se řídí autorským zákonem, občanským zákoníkem, vysokoškolským zákonem, zákonem o archivnictví, v platném znění a popř. dalšími právními předpisy. 3. Licenční smlouva byla uzavřena na základě svobodné a pravé vůle smluvních stran, s plným porozuměním jejímu textu i důsledkům, nikoliv v tísni a za nápadně nevýhodných podmínek. 4. Licenční smlouva nabývá platnosti a účinnosti dnem jejího podpisu oběma smluvními stranami.
V Brně dne: …………………………………….
…………………………………….. Nabyvatel
…………………………………… Autor
Strana 7
ABSTRAKT Tato bakalářská práce se zabývá přehledem a vysvětlením principů algoritmů pro hledání cesty, jak neinformovaných, tak informovaných. U každého algoritmu jsou uvedeny jejich vlastnosti, výhody a nevýhody. Dále je uvedena reálná aplikace těchto algoritmů na příkladu robotu v bludišti pro soutěže Micromouse, kde jsou vysvětleny obvyklé a základní metody jak bludiště řešit ve smyslu nejkratší a nejrychlejší cesty. Výstupem bakalářské práce jsou názorné prezentace funkce jednotlivých algoritmů pro výukové účely v Microsoft PowerPointu.
ABSTRACT This bachelor´s work deal with a summary and definition of principles algorithms for searching the paths as uninformed search methods, so informed search methods. There are introduced properties, advantages and disadvantages for each of algorithm. Further is introduced a real application of these algorithms on instance of robot in the maze for Micromouse contests, where there are explained usual and basic methods how to solve the maze in sence of the shortest and the fastest paths. Departure of bachelor`s work there are an objective presentations function of separate algorihms for tutorial purposes in Microsoft PowerPoint.
KLÍČOVÁ SLOVA Algoritmy pro hledání cesty, neinformované metody prohledávání, informované metody prohledávání, Micromouse.
KEYWORDS Algorithms for searching the path, uninformed search methods, informed search methods, Micromouse.
Strana 8
Strana 9
Obsah: Zadání závěrečné práce.................................................................................................. 3 Licenční smlouva............................................................................................................. 5 Abstrakt ........................................................................................................................... 7 1 Úvod ....................................................................................................................... 11 1.1 Co je to algoritmus.......................................................................................... 12 1.2 Algoritmy pro hledání cesty = pathfinding..................................................... 12 1.3 Aplikace Pathfindingu .................................................................................... 12 1.4 Příklady k řešení úloh ..................................................................................... 13 2 Implementace prostředí (stavový prostor) ......................................................... 15 2.1 Grafová reprezentace ...................................................................................... 15 2.2 Mapová reprezentace ...................................................................................... 17 3 Neinformované metody vyhledávání (uninformed search methods) ............... 19 3.1 Hledání do hloubky (depth-first search) ......................................................... 19 3.2 Hledání do šířky (breadth-first search) ........................................................... 22 3.3 Algoritmus iterativního vyhledávání (depth-first iterative deeping) .............. 24 3.4 Hledání do hloubky s omezenou hloubkou prohledávání (depth limited)...... 26 3.5 Hledání do šířky v obou směrech (bidirectional breadth-first search)............ 28 3.6 Hledání naslepo (blind search) ....................................................................... 29 3.7 Hledání metodou rozděl a panuj (divide and conquer search)........................ 30 4 Základní porovnání neinformovaných algoritmů pro hledání cesty ............... 31 5 Informované metody vyhledávání (informed search methods)........................ 33 5.1 Gradientní algoritmus (hill-climbing algorithm) ............................................ 33 5.2 Rovnoměrné prohledávání (uniform-cost search) .......................................... 37 5.3 Algoritmus uspořádaného prohledávání (best-first search algorithm) ........... 38 5.4 Paprskové prohledávání s aperturou n (beam search) .................................... 40 5.5 Algoritmus A (A algorithm) ........................................................................... 40 5.6 Algoritmus A* (A* algorithm) ....................................................................... 40 6 Základní porovnání informovaných algoritmů pro hledání cesty ................... 43 7 Reálné aplikace algoritmů pro hledání cesty ..................................................... 45 7.1 Co je to Micromouse....................................................................................... 46 7.2 Pravidla soutěže .............................................................................................. 46 7.2.1 Bludiště ....................................................................................................... 46 7.2.2 Robot – myš ................................................................................................ 46 7.2.3 Hodnocení ................................................................................................... 47 7.3 Algoritmy pro řešení bludiště, kde neexistují tzv. ostrůvky ........................... 47 7.3.1 Algoritmus levé nebo pravé ruky................................................................ 47 7.3.2 Flood-fill algoritmus (the flood-fill algorithm) .......................................... 48 7.4 Algoritmy pro řešení bludiště, kde existují tzv. ostrůvky............................... 49 7.4.1 Standardní flood-fill algoritmus (the flood-fill algorithm) ......................... 50 7.4.2 Modifikovaný flood-fill algoritmus (the modified flood-fill algorithm) .... 51 7.5 Algoritmus nejrychlejší cesty bludištěm......................................................... 53 8 Závěr ...................................................................................................................... 55 Seznam použité literatury ............................................................................................ 57
Strana 10
Strana 11
1
ÚVOD
Algoritmy pro hledání cesty jsou velmi často používanými algoritmy v oblasti umělé inteligence. Jednou z charakteristik problémů umělé inteligence je to, že k jejich vyřešení potřebujeme hledání, pokusy o nalezení řešení. Velkou část problémů umělé inteligence můžeme reprezentovat orientovaným grafem, proto často nalezneme řešení prohledáváním grafů. Řešení úloh (angl. problem solving) chápeme jako odborný termín k označení velmi důležité partie umělé inteligence. [9] Je-li dán počáteční model prostředí a požadovaný koncový model prostředí, je úkolem systému na řešení úloh hledat vhodnou posloupnost akcí, jejichž aplikací lze přejít od počátečního modelu ke koncovému. Tato posloupnost se nazývá plánem a metody vytváření plánů pak označujeme jako metody řešení úloh. Řešení úlohy lze pak formulovat jako hledání cesty v orientovaném grafu. [9] Každá řídící strategie, má-li být úspěšnou, musí splňovat dvě základní vlastnosti: a) Musí vést k prohledávání (způsobovat pohyb a zabraňovat cyklům v posloupnosti pravidel), b) musí být systematická, to znamená, že nevynechá žádný stav a také, že žádný stav nevybere dvakrát. Vzhledem k velikosti stavového prostoru může být systematické prohledávání stavového prostoru velice neefektivní. Je totiž možné, že se zbytečně prohledává značná část stavového prostoru, která nevede k cíli. Prohledávání lze omezit využitím znalostí o řešeném problému. Tyto znalosti mají někdy charakter empirický, mohou to být neexaktní poznatky, o nichž víme, že jsou „často“ užitečné při řešení, přičemž mnohdy ani nezaručují, že nalezneme řešení. Tyto znalosti nazýváme znalostmi heuristickými (tzv. heuristikami). Heuristiky se používají tam, kde není k dispozici exaktní algoritmus. Mohou mít různou podobu. Ze dvou řešitelů stejného problému ten, který je vybaven lepším souborem heuristik, prohledává menší část stavového prostoru, postupuje přímočařeji k cíli a jeho způsob řešení se jeví jako inteligentnější. Podle toho, zda jsou využity znalosti o dané úloze či nikoliv, rozlišujeme algoritmy informované a neinformované. [7] Neinformované metody prohledávání stavového prostoru jsou schopny najít řešení problémů systematickým generováním nových stavů a testováním, zda splňují cílové podmínky. Potíž je v tom, že ve většině případů jsou tyto metody vysoce neefektivní (úplnost, čas, prostor, optimalita). Informované metody prohledávání jsou založeny na specifických znalostech pro daný problém a nalezení cíle je mnohem efektivnější, včetně lepší možnosti dosáhnout optimálního řešení.
Strana 12
1.1
Co je to algoritmus
Algoritmus nebo dřívějším pravopisem algorithmus, je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchyňský recept. [1] 1.2
Algoritmy pro hledání cesty = pathfinding
Problém hledání cesty (angl. pathfinding) je schopnost najít pro daný objekt dobrou cestu z místa A do místa B v mapě, orientovaném grafu, nebo orientovaném stromu. Dobrou cestou se rozumí: • • • • • • •
Nejvhodnější, nejkratší, nejrychlejší, nejlevnější, nejjednodušší (např. v dopravě), nejbezpečnější cesta, atd.
Reálná aplikace: Přijde nám přirozené, že když klikneme myší na nějaký předmět ve scéně počítačové hry, postava k němu dojde, přičemž se inteligentně vyhne všem překážkám, které ji stojí v cestě. To zajišťuje právě pathfinding. Existuje mnoho algoritmů, jak toho dosáhnout. Zpravidla se některé části scény označí jako neprůchozí, a algoritmy poté hledají volné průchody mezi těmito blokovanými oblastmi. 1.3
Aplikace Pathfindingu
Hledání cest má mnoho aplikací v umělé inteligenci, počítačových hrách, virtuální realitě, vojenství a robotice, kde je potřeba vhodně procházet prostředím a vyhýbat se překážkám. Příkladem může být robot na vzdálené planetě, který musí být schopen pohybu nezávisle, protože k němu signály buď neproniknou nebo díky velké latenci signálu je nemožné ho dálkově ovládat člověkem. Pathfinding je užitečný v automatickém řízení vozidel a jiných dopravních prostředků. V počítačových hrách má pathfinding velké uplatnění zejména ve strategiích nebo ve hrách s počítačem řízenými protihráči. Zde je simulováno chování člověka při hledání cesty nebo se požaduje hledání nejkratších cest. Pathfinding je široce uplatňován také při zjišťování nejlepšího propojení směrovačů pro přenos zpráv v sítích, také při navrhování desek s plošnými spoji. Aplikací je opravdu hodně. [2]
Strana 13
1.4
Příklady k řešení úloh
Procesy řešení úloh jsou prováděny podle určité řídící strategie, realizované ve formě algoritmů pro řešení úloh. Tvorba a studium vlastností těchto strategií jsou hlavním obsahem části umělé inteligence, kterou nazýváme řešení úloh. Ke klasickým, dnes již školním úlohám efektivně řešitelným metodami prohledávání stavového prostoru například patří: -
Hlavolam „8“ tzv. „Lišák“. (Máme čtvercovou hrací desku s devíti místy, kterou tvoří osm očíslovaných kamenů od 1 do 8. Jedna z možných pozic zůstává vždy neobsazena. Začínáme s náhodným rozmístěním kamenů, což lze považovat za počáteční stav, a koncový stav je charakterizován přiřazením jednotlivých kamenů daným místům viz. obr. 1. Posouváním kamenů s číslicemi přes volné pole se má docílit uvedeného cílového postavení.)
Obr. 1: Hlavolam „8“ -
Úloha přelévání vody. (Jsou dány dva džbány, menší má obsah 3 a větší 4 litry viz. znázornění na obr. 2, dále je k dispozici kohoutek s vodou a odtokový žlábek. Na počátku řešení úlohy jsou oba džbány prázdné a pomocí pouze tří operací – přelití vody z jednoho džbánu do druhého, vylití vody do žlábku a naplnění džbánu po okraj se má naplnit jeden ze džbánů dvěma litry vody a druhý má zůstat prázdný. K dispozici je neomezený zdroj vody a nádoby nemají žádné označení míry. Úlohu lze řešit i obecně pro více džbánů.)
Obr. 2: Úloha přelévání vody -
Úloha obchodního cestujícího. (Obchodník musí navštívit N měst viz. obr. 3, každé pouze jedenkrát, a vrátit se do výchozího města tak, aby celková délka cesty byla minimální.)
Strana 14
Obr. 3: Úloha obchodního cestujícího -
Problém osmi královen. (Úkolem je umístit na hrací pole 8 královen tak, aby žádná nebyla v ohrožení té druhé, viz. obr. 4.)
Obr. 4: Problém osmi královen -
Úloha „misionáři a kanibalové“. (3 kanibalové a 3 misionáři se mají přepravit pomocí dvoumístné loďky z jednoho břehu řeky na druhý. Ze zřejmých důvodů však nikdy nesmí být na žádném břehu více kanibalů než misionářů.)
-
Úloha „vlk, koza, zelí“. (Problém podobný předchozímu: převozník má převézt z jednoho břehu řeky na druhý po jednom vlka, kozu a zelí, přičemž opět ze zřejmých důvodů nesmí nechat na žádném břehu bez dozoru vlka s kozou, nebo kozu se zelím.)
Situace se vážně komplikuje v případě, že se jedná o dynamicky se měnící stavový prostor – například, při řešení problému v dynamickém prostředí, nebo hře s počítačem řízeným protihráčem. [5]
Strana 15
2
IMPLEMENTACE PROSTŘEDÍ (STAVOVÝ PROSTOR)
Každému modelu umělé inteligence odpovídá jistý stav prostředí, množina všech stavů tvoří stavový prostor. Přechody mezi modely odpovídají přechodům mezi stavy. Stavový prostor je (uspořádaná) dvojice S = ( D, Φ ) , kde
D ≡ {si } je konečná množina stavů,
Φ ≡ {ϕi } je konečná množina operátorů reprezentujících přechody mezi stavy. Každý operátor ϕi : D → D je (parciálním) zobrazením D do D. Operátor ϕi může být reprezentován hranou grafu. Stavový prostor bývá nejčastěji detailněji reprezentován například orientovaným grafem, kde stavy jsou reprezentovány uzly grafu a operátory ϕi jsou reprezentovány orientovanými hranami grafu stavového prostoru. Tato reprezentace umožňuje využívat obecných poznatků teorie grafů. [13] Reprezentace stavovým prostorem: • •
2.1
Umožňuje formální definici problému pomocí převodu daných situací na nějaké požadované situace použitím množiny přípustných operátorů. Umožňuje definovat proces řešení daného problému pomocí prohledávání stavového prostoru. Grafová reprezentace
Stavový prostor lze reprezentovat orientovaným grafem. Orientovaný graf G je definován jako uspořádaná dvojice (V , E ) , kde V je nějaká množina vrcholů a E je množina uspořádaných dvojic prvků množiny V . Prvky V se jmenují vrcholy grafu a prvky množiny E orientované hrany grafu, kde E ⊆ V 2 = V × V . Dále už budu psát o orientovaném grafu jen jako o grafu, o orientované hraně jako o hraně apod. Každý vrchol reprezentuje jednotlivý stav úlohy, každá hrana přechod mezi těmito stavy způsobené danými elementárními operátory. Řešení úloh lze pak formulovat jako hledání přijatelné cesty v grafu, a to cesty mezi vrcholem počátečního stavu a vrcholem cílového stavu grafu stavového prostoru. Cílových stavů může být obecně více. Navíc cílový stav nemusí být popsán explicitně, může být popsán pouze podmínkami, které musí splňovat.
Strana 16
V práci budu používat následující terminologii:
Obr. 5: Grafová reprezentace stavového prostoru
-
Uzel A je uzlem kořenovým, uzly S, T, …, Y, Y jsou uzly listové, uzel O je bezprostředním předchůdcem uzlu W atd., uzly A, C, H, N jsou předchůdci uzlu V atd., uzel K je bezprostředním následovníkem uzlu E atd., uzly I, P, Q, X jsou následníci uzlu C atd., uzel A má hloubku 0, uzly B, C, D mají hloubku 1 atd., expanzí uzlu se rozumí určení všech jeho bezprostředních následovníků, generací uzlu se nazývá proces jeho vytvoření, ohodnocením uzlu se nazývá určení jeho ceny; později bude upřesněno. [8]
Hloubkou uzlu ve stromu řešení rozumíme počet hran na cestě od počátečního uzlu k danému uzlu, viz. následující obrázek:
Obr. 6: Hloubka stromu
Strana 17
2.2
Mapová reprezentace
Struktura, na které se převádějí algoritmy pro hledání cesty, je také mapa, která je reprezentována jako množina M = N × N (dvojrozměrná čtvercová síť). Políčko je prvek množiny M . Každé políčko reprezentuje pozici v mapě a má své souřadnice [ x, y ] vzhledem k počátku Pm . Vyznačené políčko A v mapě je označeno jako start a políčko B jako cíl cesty. Cesta v mapě je posloupnost políček mapy ( m1 , m2 , ..., mn ) taková, že každé následující políčko sousedí s předcházejícím políčkem na cestě. Žádná políčka se v cestě neopakují. Úkolem algoritmu bude najít nejkratší cestu v mapě ze startu do cíle (nejkratší ve smyslu délky cesty). [2]
Obr. 7: Mapová reprezentace stavového prostoru
Snadno nahlédneme, že mapová reprezentace odpovídá speciálnímu případu grafu. Vrcholy odpovídají políčkům = bijektivní zobrazení převádějící vrcholy grafu na políčka nazveme s indexem m . Přechod mezi sousedními políčky odpovídá hraně a počáteční vrchol v grafu Pg odpovídá počátečnímu vrcholu v mapě Pm . Je ihned vidět, že takový graf je souvislý a každý vrchol má 8 hran z něj vystupujících a 8 hran do něj vstupujících, protože každé políčko má 8 sousedů kam, nebo odkud se může jít. Díky existenci bijekce map můžeme nadefinovat ekvivalentní pojmy v mapě a grafu, jako například cesta v mapě (odpovídá pojmu cesta v grafu z teorie grafů a příslušné hrany se dají jednoznačně určit z posloupnosti vrcholů). Bijektivní zobrazení je tedy zobrazení, které přiřazuje každému prvku z výchozí množiny právě jeden prvek z cílové množiny. [2]
Strana 18
Strana 19
3
NEINFORMOVANÉ METODY VYHLEDÁVÁNÍ (UNINFORMED SEARCH METHODS)
Neinformované metody vyhledávání jsou použitelné pouze v nejjednodušších případech. Tím, že nevyužívají znalostí prostředí, je ta část stavového prostoru, která byla prohledána, obvykle příliš velká. [9] Algoritmy neinformovaného vyhledávání dělíme z hlediska pořadí, ve kterém jsou uzly expandovány, na slepé vyhledávání do hloubky, slepé vyhledávání do šířky a jejich další modifikace. [7] V následujících neinformovaných algoritmech (kap. 3.1, 3.2, 3.3 a 3.5) budu ukazovat příklady algoritmů na úloze hlavolam „8“. Kde budou čísla nad uzly značit pořadí jejich expanze (levé číslo) a dále jejich hloubku (pravé číslo). Uvnitř uzlu bude zobrazován stav úlohy.
3.1
Hledání do hloubky (depth-first search)
Prvním, základním algoritmem neinformovaného vyhledávání je slepé vyhledávání do hloubky (angl. depth-first search). Při tomto vyhledávání se přednostně expanduje uzel s největší hloubkou. Tento typ vyhledávání lze popsat níže uvedeným algoritmem. K popisu algoritmu vyhledávání do hloubky, ale i k popisu dalších algoritmů vyhledávání, zavedeme – tak jak je obvyklé – dva seznamy, a to seznam neexpandovaných stavů OPEN a seznam již expandovaných stavů CLOSED. [7] Algoritmus vyhledávání do hloubky: 1. Zapiš počáteční stav do seznamu OPEN, seznam CLOSED je prázdný. Je-li počáteční stav současně stavem cílovým, ukonči vyhledávání. 2. Pokud je seznam OPEN prázdný, řešení neexistuje, ukonči vyhledávání. 3. Vymaž první stav (označíme jej i) v seznamu OPEN a zapiš tento stav do seznamu CLOSED. 4. Expanduj stav i. Pokud tento stav nemá následovníky nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), pokračuj krokem č. 2. 5. Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED, na začátek seznamu OPEN. 6. Pokud některý z následovníků stavu i je cílovým stavem, řešení bylo nalezeno, ukonči vyhledávání. Jinak pokračuj krokem č. 2. [7]
Strana 20
Obr. 8: Vyhledávání do hloubky Metoda slepého vyhledávání do hloubky je úplná za podmínky, že omezíme hloubku vyhledávání, a řešení se nachází do této hloubky. Výhodou vyhledávání do hloubky jsou nižší nároky na paměť, neboť se v ní uchovávají pouze uzly na cestě od počátečního stavu ke stavu právě expandovanému. [9] Tento způsob vyhledávání může vést k cíli mnohem rychleji, zvláště když se vydáme správným směrem, než vyhledávání do šířky popsané v kapitole 3.2, ale nemáme zaručeno (v případě nekonečné větve), že vždy nalezneme koncový stav. Na rozdíl od vyhledávání do šířky můžeme některými uzly procházet vícekrát, neboť se často musíme navracet. [12] Vlastnosti vyhledávání do hloubky:
b = efektivní faktor větvení (angl. branching factor) m = maximální hloubka větve/délka cesty (angl. maximum depth/path) kritérium úplné čas paměť
hledání do hloubky NE (Je-li v grafu nekonečná větev, nebo existují-li cykly.) 1 + b + b2 + b3 + ... + bd = O(bm) O(b·m) NE (Upřednostňuje jednu větev oproti druhé, z toho důvodu některé optimální problémy, obdobně složité, mohou trvat srovnatelný čas.)
Tab. 1: Vlastnosti vyhledávání do hloubky
Strana 21
Výhody vyhledávání do hloubky: •
Nižší nároky na paměť, protože se v ní uchovávají pouze uzly na cestě od počátečního stavu ke stavu právě expandovanému.
Nevýhody vyhledávání do hloubky: • •
Nemusí nalézt řešení. Nemusí být nalezena nejkratší cesta.
Příklad vyhledávání do hloubky pro hlavolam „8“: 1
0
2 8 3 1
4
7 6 5 2
1
3
2 8 3
6
2 8 3 1 6 4
7 6 5
7 6 5
7 6 5
7
2
14
2
15
2 3 1 8 4
7 6 5
6 5
7 6 5
7 6 5
3
11
8 3 2 1 4 7 6 5 4 10
3
8 3 2 1 4
7 6 5
7 6 5
1 2 3
3
2 8 3
1 2 3
7 1 4 6 5
7 6 5
4 12
8 1 3 2 4
16
8 4
4 13
4 17
4 18
2 8 3
2 8 3
1 2 3
4 7 6 1 5
7 1 4 6 5
8
4
4
1 2 3 7 8 4
7 6 5
6 5
1 2 3 7 8 4 6 5
2 3
2 8 3
2 8 3
8 4 7 6 5
1 8 4 7 6 5
1 4 7 6 5
1 6 4 7 5
2 8 3
2 8 3
8 3 2 1 4
8 3 2 1 4
8 1 3 2 4
8 3 2 1 4
7 6 5
7 6 5
7 6 5
1
4
1 4
7 6 5
7 6 5
7 6 5
3
2 3
1 2 3
1 8 4
1 8 4
8 4
7 6 5
7 6 5
7 6 5
2
5
2
2 3 1 8 4
CLOSED
1
1 4
2 8 3 7 1 4
OPEN
5
2 8 3
7
3
1
1 8 4
8 3 2 1 4
8
9
4
1 4 2
2
1
2 8 3
2 8 3
2 8 3
2 8 3
7 1 4 6 5
7 1 4 6 5
4 7 6 1 5
7 1 4 6 5
Obr. 9: Příklad vyhledávání do hloubky pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu vyhledávání do hloubky pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
Strana 22
3.2
Hledání do šířky (breadth-first search)
Při slepém vyhledávání do šířky (angl. breadth-first search) se nejdříve expanduje uzel s minimální hloubkou. Tento typ vyhledávání lze popsat níže uvedeným algoritmem. [7] Algoritmus vyhledávání do šířky: 1. Zapiš počáteční stav do seznamu OPEN, seznam CLOSED je prázdný. Je-li počáteční stav současně stavem cílovým, ukonči vyhledávání. 2. Pokud je seznam OPEN prázdný, řešení neexistuje, ukonči vyhledávání. 3. Vymaž první stav (označíme jej i) v seznamu OPEN a zapiš tento stav do seznamu CLOSED. 4. Expanduj stav i. Pokud tento stav nemá následovníky nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), pokračuj krokem č. 2. 5. Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED, na konec seznamu OPEN. 6. Pokud některý z následovníků stavu i je cílovým stavem, řešení bylo nalezeno, ukonči vyhledávání. Jinak pokračuj krokem č. 2. [7]
Obr. 10: Vyhledávání do šířky Metoda slepého vyhledávání do šířky je úplná, tj. pokud existuje cesta k cíli, pak bude vždy nalezena. Může při tom však být expandován neúměrně větší počet uzlů, než je skutečně třeba k řešení (procházíme všechny uzly, které mají hloubku menší, než je hloubka koncového uzlu). Každý uzel v grafu navštívíme nejvýše jednou. Tato metoda vždy najde nejkratší řešení. [9]
Strana 23
Vlastnosti vyhledávání do šířky:
b = efektivní faktor větvení (angl. branching factor) d = hloubka řešení/cíle (angl. goal depth) kritérium úplné
čas paměť optimální
hledání do šířky ANO (Je-li b konečné, jestliže existuje řešení, nalezne jej; jedná-li se o nekonečný graf, algoritmus nebude divergovat k řešení, v praxi pak dříve nebo později dojde k vyčerpání paměťových prostředků.) 1 + b + b2 + b3 + ... + bd = O(bd+1) O(bd+1) ANO, optimalizuje-li se hloubka.
Tab. 2: Vlastnosti vyhledávání do šířky Výhody vyhledávání do šířky: • •
Vždy nalezne řešení. Vždy vede k nalezení nejkratší cesty.
Nevýhody vyhledávání do šířky: •
Vyšší nároky na paměť oproti vyhledávání do hloubky, neboť se v ní uchovávají všechny uzly na cestě od počátečního stavu ke stavu právě expandovanému.
Strana 24
Příklad vyhledávání do šířky pro hlavolam „8“: 1
0
2 8 3 1
4
7 6 5 2
1
3
2 8 3
6
1 4 7 6 5
2
8
2
2 8 3
2 3
2 1 4
7 1 4 6 5
3
15
8 3 2 1 4 7 6 5 4 23
8 3 2 1 4
7 6 5
7 6 5
1 8 4
1 4 3
7 6 5
7 6 5
7 6
3
17
8 4
4 25
4 26
2 8 3
1 2 3
4 7 6 1 5
7 1 4 6 5
8
7
2 8 3
2 8 3
2
3
18
3
2
8
1 8
1 4 3
2 8 3 1 4 5
7 6 5
7 6 5
7
4
7 6 5
6 5
2 8 3
6
6 4 1 7 5
1 6 7 5 4
3
13
2
2 8 3
1 6 4
1 6 4
3
7 5 21
3
2 8 3
2 8 3
6 4 1 7 5
1 6 7 5 4
2 8 3
2 8 3
1 2 3
4 7 6 1 5
7 1 4 6 5
8 4 7 6 5
2 3
2 8
1 8 4
1 4 3
7 6 5
7 6 5
2 8 3
2 3
7 1 4 6 5
1 8 4 7 6 5
2 8 3
2 8 3
1 8 4
1 4
1 6 4
8 3 2 1 4
7 6 5
7 6 5
7 6 5
7 6 5
7
5
7 6 5
2 8 3 1 4 5
2 8 3
2 8 3
2 8 3
1 2 3
1 6 4
1 6 4
8 3 2 1 4
7 5
7 6 5
7 1 4 6 5
7 6 5
7 5
6
5
2 8 3
20
8 3 2 1 4 7 6 5
1 4
7 6
3
8 1 3 2 4 7 6 5
4
1
2
4
1 2 3 7 8 4
2 8 3
2 8 3 1 4 5
19
12
7 5
2 3 4
4 27
2 8 3
8
2
7 6 5
7 6 5
1 4 3 7 6 5
7
11
1 8 4
7 1 4 6 5
2
2
2 8 3 1 4 5
1 2 3
1 8 7 6 5
10 2 8
16
2 3 4
2
2 3
2 8 3
4 24
8 1 3 2 4
CLOSED
3
9
1
1 6 4
1 8 4
7
5
2 8 3
7 6 5
8 3
OPEN
1
2 8 3
1 4
7 6 5
22
4
3
7 6 5 2
14
1
2
8 4
Obr. 11: Příklad vyhledávání do šířky pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu vyhledávání do šířky pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
3.3
Algoritmus iterativního vyhledávání (depth-first iterative deeping)
Určitým kompromisem mezi výhodami a nevýhodami vyhledávání do hloubky a do šířky je tzv. algoritmus iterativního vyhledávání (angl. depth-first iterative deeping), označovaný obvykle jako algoritmus DFID, nebo pod jiným názvem taktéž jako hledání do hloubky s postupným zanořováním. Algoritmus začíná úplným vyhledávání do hloubky tak, že v každé iteraci roste povolená hloubka vyhledávání o jedničku. První nalezené řešení je řešením optimálním (ve smyslu nejkratší délky cesty). [9] Klíčovým bodem ve vyhledávání do hloubky je správné určení maximální přípustné hloubky. Pokud povolíme délku cesty příliš krátkou, algoritmus do cíle nedosáhne. Pokud naopak ponecháme délku příliš velkou, pak se budou zbytečně prozkoumávat slepé neperspektivní listy.
Strana 25
To povede ke značnému zpomalení. Možným řešením je postupné zvyšování hranice maximální přípustné hloubky. Nejdřív algoritmus vyzkouší všechny cesty délky 2, poté délky 3, 4, 5 a tak dále, dokud není nalezen cíl. Pokud máme kvalitní heuristiku, která je dolním odhadem vzdálenosti, můžeme rovnou začít se vzdáleností h(start, cíl). Toto řešení může být v některých případech efektivnější než klasické vyhledávání do hloubky (ne příliš členitá mapa, dobrý odhad hloubky heuristikou, malá vzdálenost start-cíl). Vlastnosti algoritmu iterativního vyhledávání:
b = efektivní faktor větvení (angl. branching factor) d = hloubka řešení/cíle (angl. goal depth) kritérium úplné čas paměť optimální
algoritmus iterativního vyhledávání ANO, je-li b konečné. d + (d − 1)·b + (d − 2)·b2 + (d − 3)·b3 + ... + bd < dbd = O(bd) O(b·d) ANO, optimalizuje-li se hloubka.
Tab. 3: Vlastnosti algoritmu iterativního vyhledávání Výhody algoritmu iterativního vyhledávání: • •
Jedná se o kompromis mezi výhodami a nevýhodami vyhledávání do šířky a do hloubky. Je nejvhodnější neinformovaná metoda pro velké stavové prostory s neznámou hloubkou, ve které se nachází řešení.
Nevýhody algoritmu iterativního vyhledávání: •
Často nevíme, jaký určit limit pro hloubku vyhledávání, a proto můžeme vyzkoušet všechny hloubky počínaje nulovou.
Strana 26
Příklad algoritmu iterativního vyhledávání pro hlavolam „8“: 1
0
2 8 3 1 4 7 6 5 2
1
3
2 8 3 1 4 7 6 5 6
2
7
8 3 2 1 4 7 6 5 14
22
3
4 23
8 1 3 2 4 7 6 5
15
CLOSED
8
3
4 24
2
4
16
1
5
2 8 3 1 4 7 6 5
9
2 3 1 8 4 7 6 5
1
2 8 3 1 6 4 7 5
2
2 3 1 8 4 7 6 5
3
1 2 3 8 4 7 6 5
2 8 3 7 1 4 6 5
8 3 2 1 4 7 6 5
OPEN
2
2 8 3 7 1 4 6 5
8 3 2 1 4 7 6 5
1
2 3 1 8 4 7 6 5
4 25
2 8 3 4 7 6 1 5
4 26
2 8 3 7 1 4 6 5
4 27
1 2 3 8 4 7 6 5
4
1 2 3 7 8 4 6 5
1 2 3 8 4 7 6 5
1 2 3 7 8 4 6 5
2 3 1 8 4 7 6 5
2 8 3 1 4 7 6 5
2 8 3 1 6 4 7 5
2 8 3 1 4 7 6 5
2 8 3 1 4 7 6 5
8 3 2 1 4 7 6 5
8 3 2 1 4 7 6 5
8 1 3 2 4 7 6 5
2 3 1 8 4 7 6 5
2 3 1 8 4 7 6 5
1 2 3 8 4 7 6 5
8 3 2 1 4 7 6 5
2 8 3 7 1 4 6 5
2 8 3 7 1 4 6 5
2 8 3 4 7 6 1 5
2 8 3 7 1 4 6 5
Obr. 12: Příklad algoritmu iterativního vyhledávání pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu algoritmu iterativního vyhledávání pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
3.4
Hledání do hloubky s omezenou hloubkou prohledávání (depth limited)
Vyhledávání do hloubky je často spojeno s omezením maximální prohledávané hloubky, při jejímž dosažení se používá mechanismus navracení (angl. backtracking). Tuto strategii používá algoritmus vyhledávání ho hloubky s omezenou hloubkou prohledávání (angl. depth limited). [7] V globální bázi dat eviduje jednu možnou cestu. U každého stavu eviduje použitelné a ještě nevyzkoušené uzly. Pravidla jsou na stavech definované uzly a pravidlo kroku zpět.
Strana 27
Řídící strategie je jednoduchá: pravidlo kroku zpět použít, jestliže pro daný stav není možné použít žádné jiné pravidlo. Podstata vyhledávání za použití kroku zpět je taková, že najednou eviduje jednu cestu v reprezentačním grafu, a když se dostane do slepé uličky, vrátí se zpět na nejbližší rozcestí a zkouší jinou cestu. Tato jednoduchá strategie má dvě slabiny: • •
Při výběru nevhodné cesty se může pouze po dlouhé době ukázat, že nevede k cíli. Tou samou slepou uličkou můžeme projít vícekrát, jestliže k ní vede víc cest, protože si nepamatujeme prošlé cesty, nebrání tedy cyklům v posloupnosti stavů a není systematická. [9]
Velice výhodný pro použití např. u úlohy obchodního cestujícího, když je na mapě 20 měst, a my víme že nejkratší cestu z města A do města B není nutné vést přes víc než 18 měst. Algoritmus vyhledávání do hloubky s omezenou hloubku prohledávání: 1. Zapiš počáteční stav do seznamu OPEN, seznam CLOSED je prázdný. Je-li počáteční stav současně stavem cílovým, ukonči vyhledávání. 2. Pokud je seznam OPEN prázdný, řešení neexistuje, ukonči vyhledávání. 3. Vymaž první stav (označíme jej i) v seznamu OPEN a zapiš tento stav do seznamu CLOSED. 4. Pokud se hloubka uzlu i rovná maximální přípustné hloubce, pokračuj krokem č. 2. 5. Expanduj stav i. Pokud tento stav nemá následovníky nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), pokračuj krokem č. 2. 6. Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED, na začátek seznamu OPEN. 7. Pokud některý z následovníků stavu i je cílovým stavem, řešení bylo nalezeno, ukonči vyhledávání. Jinak pokračuj krokem č. 2. [7] Vlastnosti vyhledávání do hloubky s omezenou hloubkou prohledávání:
b = efektivní faktor větvení (angl. branching factor) l = použití maximální přípustné hloubky (dobrá volba limitu hloubky l se volí podle znalosti problému) kritérium úplné
čas paměť optimální
hledání do hloubky s omezenou hloubkou prohledávání NE (Díky limitování hloubky zanoření může nastat případ, kdy řešení se vyskytuje v hloubce limit + 1.) 1 + b + b2 + b3 + ... + bl = O(bl) O(b·l) NE (Upřednostňuje jednu větev oproti druhé, z toho důvodu některé problémy, obdobně složité, mohou trvat nesrovnatelný čas.)
Tab. 4: Vlastnosti vyhledávání do hloubky s omezenou hloubkou prohledávání
Strana 28
Výhody vyhledávání do hloubky s omezenou hloubkou prohledávání: • •
Odstraňuje nevýhodu vyhledávání do hloubky nekompletnosti. Nalezne řešení vždy, existuje-li v dané hloubce zanoření.
Nevýhody vyhledávání do hloubky s omezenou hloubkou prohledávání: •
3.5
Nevíme předem, jak hluboko určit maximální přípustnou hloubku.
Hledání do šířky v obou směrech (bidirectional breadth-first search)
Je jednoduché vylepšení algoritmu vyhledávání do šířky, které si všímá toho, že počet prozkoumaných políček roste kvadraticky s délkou cesty. Proto rozjíždí simultánně dvě vyhledávání do šířky. Jedno ze startu, druhé z cíle. Postupně provádí vždy jeden cyklus jedné, a jeden cyklus druhé šířky. Ve chvíli, kdy se šířky setkají, je možné zkonstruovat cestu ze startu do cíle. Pokud jedna z šířek dojde do stavu, kdy už nemá nová políčka na prozkoumání, pak cesta v mapě neexistuje a algoritmus může skončit. [2] Opět se zde pochopitelně projeví nedostatky vyhledávání do šířky. Jedná se jen o optimalizaci původního algoritmu. Pokud počet prohledaných políček normálním vyhledávání do šířky je n , pak na stejné mapě vyhledávání v obou směrech prohledá typicky druhou odmocninu z n políček (experimentálně zjištěno). [2]
Obr. 13: Vyhledávání do šířky v obou směrech [5] Vlastnosti vyhledávání do šířky v obou směrech: • • •
Paměťová i časová náročnost je závislá vzhledem k počtu políček mapy. Hledáme současně z počátečního i cílového stavu. Hledání skončí, když na druhém konci najdeme uzel, který si pamatujeme z prvního konce.
Výhody vyhledávání do šířky v obou směrech: •
Rychlý algoritmus, protože počet prozkoumaných políček roste kvadraticky s délkou cesty.
Strana 29
Nevýhody vyhledávání do šířky v obou směrech: •
Paměťové nároky jsou mnohem vyšší než u vyhledávání do šířky.
Příklad vyhledávání do šířky v obou směrech pro hlavolam „8“: 1
0
1 4 2 8
3 7 6 5
3
1
5
1 4 2 8 3
7 6 5
2
2
2
4 2
1 4 2
1 2
1 8 3
7 8 3
7 6 5
6 5
2
1 1 4 2 8 6 3
7 6 5
7
2
2
1 4
1 4 2
8 4 3
8 4 3
8 3 2
7 6 5
7 6 5
7 6 5
8 3 5 7 6
**** 1 2
2
2
2
1 3 8 2 4
1 3 8 2 4
6 5
7 6 5
7 6 5
7 6 5
1
1 4 2 8 3 2
2 3 7 8 4
1
4
7
2
8 4 3
7 6 5
2 3 1 8 4
1
1
1
6
**** 1 2
2 1
2 3 8 4 5
8 4 3 7 6 5
1
1
2
5
7 6
8
1
1
1 2 3 8 4
1
8
3 2 4
2 3 8 4
2 3 8 6 4
7 6 5
7 6 5
7 6 5
7
1 8
1
5
2 3 4
7 6 5 2 0
OPEN
OPEN
CLOSED
1 4 2 8 6 3
4 2
1 4 2
1 2
1 8 3
7 8 3
8 4 3
8 4 3
7
7 6 5
6 5
7 6 5
7 6 5
7 6 5
2 3 7 8 4
1 3 8 2 4
1 3 8 2 4
1
7 6 5
7 6 5
8 4 3 7 6 5
1
1
2
1
8 4 3 7 6 5
8
5
1 2 3 8 6 4
2 3 1 8 4
7
7 6 5
5
1 4 2
1
8
8
3 7 6 5
2 3 4
7 6 5
1
6 5 1 4 2 8 3 7 6 5
2 3 8 4
7 6 5
1
2
1 4
1 4 2
8 3 2
8 3 5 7 6
2
3 2 4
7 6 5
1 2 3 8 4 5 7 6 1 4 2
1
8 3 7 6 5
8 4
2 3
7 6 5
Obr. 14: Příklad vyhledávání do šířky v obou směrech pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu vyhledávání do šířky v obou směrech pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
3.6
Hledání naslepo (blind search)
Tato metoda se používá na mapové reprezentaci stavového prostoru. Algoritmus vyhledávání naslepo (angl. blind search) je založen na triviálním postupu: jdi směrem k cíli, pokud narazíš na překážku, změň směr a snaž se postupovat podél hrany překážky a obejít ji. Tento algoritmus pracuje s výhledem jednoho políčka. Kvalita tohoto algoritmu se liší podle toho, jakým způsobem se snaží překážky obejít. Paměťová náročnost je konstantní. Časová náročnost závisí na typu mapy a překážek.
Strana 30
Nevýhody vyhledávání naslepo: • •
Nemusí cestu najít vůbec, protože se může zacyklit. Algoritmus negarantuje nalezení nejkratší cesty.
Výhody vyhledávání naslepo: •
3.7
Může být použit pro speciální jednoduché mapy kvůli rychlosti, paměťové nenáročnosti a jednoduchosti implementace.
Hledání metodou rozděl a panuj (divide and conquer search)
Pro zajímavost uvedu ještě jeden způsob, jak řešit hledání cest na mapové reprezentaci stavového prostoru. Je jím použití rekurzivní metody rozděl a panuj: pro nalezení cesty ze startu do cíle, čili z A do B najdi prostřední bod, který leží na úsečce A,B. Pokud je jemu odpovídající X políčko překážkou, použij nějakou metodu na nalezení blízkého volného políčka (metoda spirály, náhodné testy, šířka, apod.). Poté spusť algoritmus na A,X a X,B. Pokud jsou nalezeny, tak výsledné cesty spoj, jinak vrať neúspěch. Zarážkou je stav, kdy A a B jsou sousední políčka (nebo ve složitější modifikaci: políčka, jejíchž spojnice rastrovaná do mapy nekoliduje s překážkami). Metoda opět nebere v potaz ohodnocení. Nemusí najít cestu, přestože cesta v mapě existuje. Zde je příklad takové situace je na obr. 15, kdy je prostřední bod na spojnici ze startu do cíle překážkou. [2]
Obr. 15: Selhání metody rozděl a panuj[2] Výhody vyhledávání metodou rozděl a panuj: •
Rychlá metoda pro jednoduché mapy.
Nevýhody vyhledávání metodou rozděl a panuj: • •
Je-li prostřední bod, který leží na úsečce A,B překážkou, musí se použít nějaká jiná metoda pro nalezení blízkého volného políčka. Složitost a správnost algoritmu závisí na volbě metody nalezení blízkého políčka.
Strana 31
4
ZÁKLADNÍ POROVNÁNÍ NEINFORMOVANÝCH ALGORITMŮ PRO HLEDÁNÍ CESTY
Základní porovnání neinformovaných metod vyhledávání stavového prostoru je uvedeno v tab. 5. Je zde provedeno porovnání z hlediska časové a paměťové náročnosti algoritmu. Dále porovnání jejich optimality a úplnosti metody. Optimalitou se myslí, zda algoritmus najde nejkratší řešení. Úplností metody, se rozumí, zda-li nalezne, nebo nenalezne řešení.
b = efektivní faktor větvení (angl. branching factor) m = maximální hloubka větve/délka cesty (angl. maximum depth/path) d = hloubka řešení/cíle (angl. goal depth) l = použití maximální přípustné hloubky (dobrá volba limitu hloubky l se volí podle znalosti problému) kritérium hledání hledání do do / algoritmus hloubky šířky
čas paměť optimalita úplnost
bm bm ne ne
bd+1 bd+1 ano ano
algoritmus iterativního vyhledávání bd bd ano ano
hledání hledání s omezenou do šířky v obou hloubkou prohledávání směrech bl bd/2 bl bd/2 ne ano ne ano
Tab. 5: Porovnání neinformovaných algoritmů pro hledání cesty [4],[5]
Strana 32
Strana 33
5
INFORMOVANÉ METODY VYHLEDÁVÁNÍ (INFORMED SEARCH METHODS)
Informované metody vyhledávání stavového prostoru pro řešení problému často používají pro výběr nejvhodnějšího vrcholu k expandování různé typy heuristik. Heuristika je postup, jak postupovat při výpočtu konkrétní situace, který není hromadný, platí jen pro konkrétní hodnoty a konkrétní problémy a zpravidla byla odpozorována z praxe. K rozhodnutí, který uzel grafu expandovat se používají různé hodnotící funkce. Podle charakteru úlohy je možné definovat hodnotící funkci f, která pro každý uzel stromu řešení určí jeho ohodnocení. Hodnoty hodnotící funkce se pak používají k výběru uzlu pro další expanzi. Odtud je intuitivně zřejmé, že pokud hodnotící funkce dobře postihuje vlastnosti a charakter úlohy, budou vždy expandovány „nejperspektivnější“ uzly a zabrání se prohledávání cest, které nevedou k cíli. Platí, že čím kvalitnější heuristické znalosti o daném problému jsou použity k formulaci hodnotící funkce, tím efektivnější bude vyhledávání. Hodnoty hodnotící funkce f, a její funkční hodnoty f(i) v i-tém stavu získáme ze vztahu:
f (i ) = g (i ) + h(i ) ,
(1)
kde g(i) je cesta z počátečního stavu s0 do stavu i, a h(i) je cesta ze stavu j do některého z cílových stavů. U hlavolamu „8“ by mohly být hodnotící funkce takové:
h1) počet políček, ve kterých se dva stavy liší, h2) summa (horizontálních a vertikálních) vzdáleností, ve kterých se dva stavy liší. [11] V následujících informovaných algoritmech (kap. 5.1, 5.2 a 5.6) budu ukazovat příklady algoritmů na úloze hlavolam „8“. Kde budou čísla nad uzly značit pořadí jejich expanze (levé číslo) a dále jejich ohodnocení (pravé číslo). Uvnitř uzlu bude zobrazován stav úlohy.
5.1
Gradientní algoritmus (hill-climbing algorithm)
Jak už samotný název metody napovídá, je tato metoda inspirována reálnou situací. Chceme-li dosáhnout vrcholu kopce, bude nejrychlejší postup po spádnici, tedy cestou nejvyššího gradientu (pokud použijeme analogii z matematiky). Nejjednodušší verzí informovaného algoritmu je algoritmus gradientní (angl. hill-climbing algorithm) vycházející z vyhledávání do hloubky. Gradientní strategie vždy expanduje ten uzel, který byl dosud vyhodnocen pomocí hodnotící funkce f jako nejlepší, a vyhodnocuje jeho následovníky. Při expanzi se následovníci seřadí podle hodnotící funkce a v zásobníku na vrcholu bude nejperspektivnější z nich. Předchůdci, stejně jako následovníci daného uzlu jsou okamžitě zapomenuti, neboť algoritmus v každém kroku uchovává v paměti jen právě rozvíjený uzel, protože nás nezajímá rekonstrukce cesty. [7]
Strana 34
Vyhledávání je zastaveno, jakmile je dosaženo cílového stavu, nebo takového stavu, který má „lepší“ ohodnocení pomocí funkce f než jeho následovníci, případně nemá žádné následovníky. [7] Gradientní algoritmus je vhodný pro úkoly, u kterých nás zajímá pouze řešení, cesta do něj vedoucí není důležitá. Algoritmus začíná u libovolného uzlu reprezentačního grafu a expanduje ho, pak na základě hodnotící funkce f vybere nejlepší z jeho přímých následovníků k další expanzi, atd. Jestliže je nejlepších následovníků více, tzn. mají stejné nejlepší ohodnocení na základě funkce f, pak algoritmus náhodně (obvykle funkcí random) vybere jeden z nich. [9]
Čistě gradientní strategie má základní nevýhodu všech gradientních metod – může skončit v lokálním extrému viz. obr. 16, což nemusí být řešením dané úlohy. Navíc, vzhledem k tomu, že se neuschovává historie vyhledávání, není vyloučen ani pohyb po nekonečně dlouhé cestě (tj. zacyklení). [7]
Obr. 16: Globální a lokální extrém Názorný a přitom jednoduchý příklad zacyklení lze nalézt při hraní hry hlavolam „8“, jak je tomu vidět na obr. 17. Definujme funkci f jako počet kamenů, které jsou na svém místě. Typický je pak případ, kdy musíme hnout kameny, které jsou již v cílové poloze a zhoršit hodnotu stavu jen proto, abychom mohli posunout jiný kámen žádaným směrem. Samozřejmě, pro jiný tvar funkce f to nemusí platit. [9]
Strana 35
Obr. 17: Příklad zacyklení gradientního vyhledávání pro hlavolam „8“ Vlastnosti gradientního vyhledávání: •
Jako hodnotící funkci použijeme: f (i ) = h(i ) .
Výhody gradientního vyhledávání: •
Je nejjednodušší verzí informovaného algoritmu.
Nevýhody gradientního vyhledávání: •
Nebezpečí lokálního extrému.
Strana 36
Příklad gradientního vyhledávání pro hlavolam „8“: 1 1 4 8 7 5 2 h=7 1 4 2 7 8 3 5 6
h=6 2 3 6
2
h=7 4 2 1 8 3 7 5 6
2 h=5 1 4 2 8 3 7 5 6
3 h=5 1 4 2
3 1
8 5 3 7 6 4 1
h=5 2
8 4 3 7 5 6
3 h=5 1 4 2 8 3 7 5 6 4
h=4 2
8 4 3 7 5 6
h=6 1 2
8 4 3 7 5 6
5 h=3 1 2 3 8 4 7 5 6 6 h=3 1 2 3
6 h=2 1 2 3
8 4 6 7 5
8
4 7 5 6 7 1 2 8 7 5
h=3 3
7 1 8 2 7 5
4 6
h=3 3 4 6
7 h=2 1 2 3 8 5 4 7
6
8 h=3 1 2 3 8 5 4 7 6
OPEN
CLOSED
8 h=1 1 2 3 8 5 4 7 6
1 2 3 8 5
9 h=2 1 2 3 8 5
7 6 4
7 6 4
1 4 2
1 4 2
1 4 2
4 2
2
1 4 2
1 4 2
1
8 3 7 5 6
8
3 7 5 6
7 8 3 5 6
1 8 3 7 5 6
8 4 3 7 5 6
8 5 3 7 6
8 3 7 5 6
8 4 3 7 5 6
1 2 3 8 4 7 5 6
1 2 3 8 4 7 5 6
1 2 3 8 4 6 7 5
1 2 3 8 5 4 7 6
1 2 3 8 4 7 5 6
1 3 8 2 4 7 5 6
1 2 3 8 5 4 7 6
1 2 3 8 5 4 7 6
1
2
1 2 8 4 3 7 5 6
Obr. 18: Příklad gradientního vyhledávání pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu gradientního vyhledávání pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
Strana 37
5.2
Rovnoměrné prohledávání (uniform-cost search)
Tato metoda je taktéž označována jako prohledávání metodou stejných cen (angl. uniform-cost search). Metoda vychází z předpokladu ohodnocení uzlů cenami, které odpovídají vynaloženým nákladům na vygenerování těchto uzlů. K expanzi se vždy vybírá uzel, ke kterému v prohledávacím grafu vede cesta s nejnižšími náklady, tj. uzel s minimálním ohodnocením. Jsou-li ohodnocení uzlů rovny jejich hloubce, je metoda stejných cen shodná s metodou vyhledávání do šířky. [8] Ať cena c(n, m) označuje náklady přiřazené k hraně vedoucí z uzlu n do uzlu m (odpovídají nákladům na uplatnění operátora vedoucího ze stavu reprezentovaného uzlem n do stavu reprezentovaného uzlem m). Můžeme pak zavést nákladovou funkci pro startovní uzel: g (s) = 0 , (2) a pro uzel m: g ( m ) = g ( n ) + c ( n, m ) , (3) kde m je přímým následovníkem uzlu n, a c jsou náklady vynaložené na tuto cestu. Situace je názorně popsána na následujícím příkladu (viz. obr. 19.):
Obr. 19: Příklad rovnoměrného prohledávání Vlastnosti rovnoměrného prohledávání: • •
Jako hodnotící funkci použijeme nákladovou funkci: f (i ) = g (i ) . Vidíme, že slepé vyhledávání do šířky je speciálním případem prohledávání metodou stejných cen, a sice když náklady všech hran jsou jednotkové.
Výhody rovnoměrného prohledávání: • •
Vždy nalezne optimální řešení (za předpokladu, že řešení existuje). Vhodně se používá u úlohy obchodního cestujícího.
Strana 38
Nevýhody rovnoměrného prohledávání: •
Je obecně málo efektivní, optimální řešení často nalezne za cenu expanze velkého počtu uzlů.
Příklad rovnoměrného prohledávání pro hlavolam „8“: 3 1 4 2 [3]
8
3 7 6 5
+1 4 1 4 2 8 3
1 [4]
[3]
7 6 5 +1 -1 4 1 2 8 4 3
3 1 4 2 8 3
2
8 4 3
7 6 5
+1
0
0
3
1 [4]
7
[4]
5
2 2 [2]
8 4 3
7 6 5
[3]
7 6 5
4 1 4 2 8 6 3
7 6 5 -1 1 2 3 8 4 1
[1]
7 6 5 -1 0 1 2 3 8 4
+1 2 2 3 8 4 5 1
[0]
7 6 5
1 4 2 8 3
OPEN
7 6 5
CLOSED
1 4 2
1 4 2 8 6 3
1 2
1
8 3
8 4 3
8
7 6 5
7
7 6 5
7 6 5
1 4 2
1
8
3
8 4 3
8 4 3
8 4
7 6 5
7 6 5
7 6 5
7 6 5
2
1
5 2
1
[2]
7 6
2 3 4
1 2 3 8 4 5 7 6
2 3
Obr. 20: Příklad rovnoměrného prohledávání pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu rovnoměrného prohledávání pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
5.3
Algoritmus uspořádaného prohledávání (best-first search algorithm)
Výrazně účinnějšího informovaného prohledávání lze dosáhnout algoritmem uspořádaného prohledávání (angl. best-first search algorithm), který vznikl rozšířením gradientního algoritmu o paměť. Tato paměť se opět skládá opět ze seznamů OPEN a CLOSED. Prvky těchto seznamů nejsou však pouhá jména uzlů (stavů), nýbrž trojice: < jméno uzlu, hodnota f, jméno rodičovského uzlu >. Zápisem stavu v seznamu rozumíme zápis uvedené trojice. [7]
Činnost algoritmu nejlépe pochopíme z následujícího podrobného popisu, v němž expandujeme stavy podle minimální hodnoty funkce f. [7]
Strana 39
Algoritmus uspořádaného prohledávání: 1. Počáteční stav zapiš do seznamu OPEN, seznam CLOSED je prázdný. 2. Pokud je seznam OPEN prázdný, řešení neexistuje, ukonči prohledávání. 3. Ze seznamu OPEN vyber stav i s nejmenší hodnotou f(i). V případě většího počtu stavů se stejnou minimální hodnotou f(i) prověř, zda některý z těchto stavů není stavem cílovým, v takovém případě jej vyber; jinak vyber mezi stavy se stejnou minimální hodnotou f(i) libovolně. 4. Vymaž stav i ze seznamu OPEN a zařaď jej do seznamu CLOSED. 5. Je-li stav i cílovým stavem, řešení je nalezeno, ukonči prohledávání. 6. Expanduj stav i; pro každého následovníka j stavu i vypočítej hodnotu f(j). Pokud stav j není ani v seznamu OPEN ani v seznamu CLOSED, zařaď jej do seznamu OPEN. Pokud je stav j již v seznamu OPEN nebo CLOSED, avšak s ohodnocením větším než právě vypočtené f(j) změň jeho ohodnocení na f(j), změň jméno rodičovského uzlu v zápisu uzlu a zařaď ho do seznamu OPEN. 7. Pokračuj krokem č. 2. [7] V jistém smyslu je protějškem rovnoměrného prohledávání. Zatímco algoritmus rovnoměrného prohledávání expanduje vždy ten otevřený uzel, ke kterému našel (zatím) cestu s nejnižšími náklady, u uspořádaného prohledávání si nevšímá prošlé cesty a vybírá otevřený uzel pouze na základě odhadu nákladů na zbývající cestu. Úspěšnost uspořádaného prohledávání do velké míry závisí na výběru heuristické funkce. Úspěšné ukončení prohledávání není zaručeno, může se lehce stát, že prohledávání projde mimo řešení. [9] Vlastnosti uspořádaného prohledávání: • •
Jako hodnotící funkci použijeme: f (i ) = h(i ) . Uzly jsou uspořádány tak, že ty s nejlepším ohodnocením jsou expandovány jako první.
Výhody uspořádaného prohledávání: •
Nejrychlejší (u jednoduchých typů úloh).
Nevýhody uspořádaného prohledávání: • •
Není zaručeno nalezení nejkratší cesty. Nebere v úvahu náročnost úlohy.
Strana 40
5.4
Paprskové prohledávání s aperturou n (beam search)
Kromě základní podoby obecného algoritmu prohledávání existují další varianty. Často se například užívá seznamu OPEN konečné délky n, přičemž v každém kroku se do seznamu OPEN zapíší jen ty nově expandované uzly, které mají lepší ohodnocení než uzly dosud zachycené v seznamu OPEN, ty se tím automaticky vyškrtnou. Tedy jenom n nejslibnějších uzlů se uchovává v seznamu OPEN, což má samozřejmě za následek značné zredukování expandovaného stromu, což může zabránit nalezení optimálního řešení. Právě popsaný algoritmus se nazývá algoritmem paprskového prohledávání (angl. beam-search) s aperturou n. [9]
5.5
Algoritmus A (A algorithm)
Jednou z možností obecné formalizace funkce f je vyjádřit její hodnotu f(i) v i-tém stavu jako součet ceny g(i) tj. cesty z počátečního stavu s0 do stavu i a ceny h(i) tj. cesty ze stavu j do některého z cílových stavů c ∈ ξ . Cenou rozumíme libovolné nezáporné ohodnocení cesty. Pak lze psát:
f (i ) = g (i ) + h(i )
(1)
a funkci f(i) chápat jako cenu přechodu z počátečního stavu do cílového stavu přes stav i. V každém kroku prohledávání bude tedy při aplikaci algoritmu A vybrán k expanzi ten uzel, který má minimální hodnotu hodnotící funkce f(i). Algoritmus uspořádaného prohledávání využívající takto chápanou hodnotící funkci bývá označován jako algoritmus A. [7]
5.6
Algoritmus A* (A* algorithm)
Algoritmus A* (čteno „A star“) vychází z algoritmu A s tím rozdílem, že ve většině praktických úloh však funkce g(i) a h(i) neznáme, a proto je nahrazujeme jejich odhady g*(i) a h*(i). Funkci g(i) odhadneme minimální dosud zjištěnou cenou g*(i) přechodu z počátečního stavu s0 do stavu i. Funkci h(i) nahrazujeme funkcí h*(i), která kvantitativně vyjadřuje náš odhad cesty z uzlu i do cíle. Tento odhad vyjadřuje naši heuristickou znalost o tom, jaké jsou šance nalézt (optimální) řešení, pokračovali-li bychom expanzí daného uzlu. Funkce h*(i) je tedy nositelem heuristické informace a bývá proto nazývána heuristickou funkcí. Je zřejmé, že tato funkce je pro efektivní prohledávání velmi podstatná. V souvislosti s konstrukcí funkce f vyvstává zajímavá otázka tzv. přípustnosti algoritmu prohledávání. Říkáme, že algoritmus prohledávání je přípustný, jestliže vždy nalézá optimální cestu, pokud tato cesta existuje. Lze ukázat, že pokud funkce h*(i) je nezáporná a menší nebo rovna skutečné ceně přechodu ze stavu i do cílového stavu, je algoritmus A přípustný. Funkce h*(i) s touto vlastností se nazývá přípustnou heuristickou funkcí. Algoritmus A využívající přípustnou heuristickou funkci se označuje jako algoritmus A*.
Strana 41
Čím je funkce h*(i) lepším spodním odhadem funkce h(i), tím menší část stavového prostoru se prohledává při hledání optimálního řešení. Jestliže je odhad h*(i) roven skutečné ceně přechodu do cílového stavu pro každý stav i a jestliže optimální řešení existuje, expanduje algoritmus A* pouze stavy na cestě k cílovému stavu. Říkáme, že algoritmus A1* je lépe informován než algoritmus A2*, jestliže pro každý stav i je h1*(i) ≥ h2*(i). Jestliže A1* a A2* jsou algoritmy s přípustnými funkcemi h1* a h2* a A1* je lépe informován než A2*, potom A2* expanduje všechny stavy, které expanduje A1*. Mohou však existovat stavy, které expanduje A2* a neexpanduje A1*. [7] Volba heuristické funkce pro hlavolam „8“ je znázorněna na obr. 21 a je taková, že h* je počet kamenů na chybných pozicích. Na prvním obrázku je umístěno 4 z 8 kamenů chybně, takže stav má h* = 4. Na druhém obrázku je umístěno 8 z 8 kamenů chybně, proto má stav h* = 8 a na třetím obrázku jsou umístěny 3 z 8 kamenů chybně, takže stav má h* = 3. Je to přijatelná heuristika, protože každý chybně umístěný kámen musí být alespoň jednou posunut.
Obr. 21: Volba heuristické funkce pro hlavolam „8“ Vlastnosti algoritmu A*: •
Jako hodnotící funkci použijeme: f*(i) = g*(i) + h*(i), kde pro ∀ i v h*(i) ≥ h(i) ≥ 0. • Hledá za pomoci heuristiky. • Zkouší vždy nejslibnější neprobraný stav. Výhody algoritmu A*: • • • •
Cesta je vždy nalezená a je nejkratší možná. Volnost v ohodnocování polí – nejrůznější druhy zvýhodnění. Použití s libovolnou reprezentací terénu. Jednoduchost implementace.
Nevýhody algoritmu A*: • • • •
Počet vrcholu v OPEN nebo CLOSED listu muže být v řádu stovek nebo tisíců. Cesta se musí spočítat celá najednou. Pokud cesta neexistuje, prohledá se celý prostor, což muže trvat extrémně dlouho. Pokud se změní prostředí, je nutné celou cestu přeplánovat.
Strana 42
Příklad algoritmu A* pro hlavolam „8“: 1 0+4 2 8 3 1 6 4 7 5 1+5 2 8 3 1 6 4
2 1+3 2 8 3 1 4
7 5
7 6 5
3 2+3 2 8 3
4 2
1 4 7 6 5 3+3 8 3 2 1 4 7 6 5
1+5 2 8 3 1 6 4 7 5
2+3 3
2+4 2 8 3
1 8 4 7 6 5
3+4 2 8 3 7 1 4 6 5
1 4 7 6 5
5
3+2 2 3 1 8 4
3+4 2 3 1 8 4 7 6 5
7 6 5 6 4+1 1 2 3 8 4 7 6 5
OPEN
CLOSED
2 8 3 1 6 4 7 5
5+0 1 2 3
5+2 1 2 3
8 4 7 6 5
7 8 4 6 5
2 8 3 1 6 4 7 5
2 8 3 1 4 7 6 5
2 8 3
2 8 3
2 8 3
2
1 6 4 7 5
1
1 4 7 6 5
4 7 6 5
2 8 3 7 1 4 6 5
2 3 1 8 4 7 6 5
3
2 3
1 2 3
1 8 4 7 6 5
1 8 4 7 6 5
8 4 7 6 5
8 3 2 1 4 7 6 5
1 2 3 8 4 7 6 5
1 2 3 7 8 4 6 5
Obr. 22: Příklad algoritmu A* pro hlavolam „8“ Poznámka: Kompletní ukázka příkladu algoritmu A* pro hlavolam „8“ se nachází na CD přiloženém k bakalářské práci.
Strana 43
6
ZÁKLADNÍ POROVNÁNÍ INFORMOVANÝCH ALGORITMŮ PRO HLEDÁNÍ CESTY
Základní porovnání informovaných metod vyhledávání stavového prostoru je uvedeno v tab. 6. Je zde provedeno porovnání podle toho, jakou používají dané metody hodnotící funkci f(i), v i-tém stavu, která se skládá ze součtu ceny g(i) tj. cesty z počátečního stavu s0 do stavu i a ceny h(i) tj. cesty ze stavu j do některého z cílových stavů. Cenou rozumíme libovolné nezáporné ohodnocení cesty.
strategie prohledávání gradientní algoritmus rovnoměrné prohledávání uspořádané prohledávání algoritmus A algoritmus A*
hodnotící funkce f(i) má tvar: f(i) = g(i) + h(i) g(i) h(i) 0 h(i) g(i) 0 0 h(i) g(i) h(i), kde pro ∀i h(i) ≥ 0 g*(i) h*(i), kde pro ∀ i h*(i) ≥ h(i) ≥ 0
Tab. 6: Porovnání informovaných algoritmů pro hledání cesty [11]
Strana 44
Strana 45
7
REÁLNÉ APLIKACE ALGORITMŮ PRO HLEDÁNÍ CESTY
Použití algoritmů pro hledání cesty se nejčastěji vyskytuje v oblasti umělé inteligence, jak již jsem psal v úvodu bakalářské práce. Proto jako reálnou aplikaci algoritmů pro hledání cesty uvedu robot pro Micromouse (vlastní UAI FSI VUT Brno), jehož úkolem je najít cestu bludištěm ze startovní do cílové polohy.
Obr. 23: Robot pro Micromouse na UAI FSI VUT Brno Robot je postaven na diferenciálním podvozku, pro pohon je použita dvojice krokových motorů. Změna směru pohybu je realizována různou rychlostí otáčení kol. Aby se robot nepřevrátil, je vybaven dvěma kulovými podpěrami. Základní technické parametry robotu jsou v tab. 7. [14] PARAMETR podvozek pohon senzory napájení komunikace délka šířka výška rozteč kol hmotnost
HODNOTA diferenciální dvě hnaná kola dvě podpěry 2x krokový motor TEAC KP39HM2-025 3x senzor SHARP GP2D120 4x akumulátor LiIon CGR18650/4,2V 2x RS323/TTL/38400Bd 130 mm 105 mm 80 mm 95 mm 990 g
Tab. 7: Základní technické parametry robotu [14]
Strana 46
7.1
Co je to Micromouse
Micromouse je soutěž, kde autonomní roboty závodí, kdo prozkoumá různé konfigurace bludiště a vyřeší optimální cestu ze startu do cíle v nejkratším možném čase. Moderní forma soutěže začala okolo roku 1980. V podstatě se jedná o bludiště vytvořené z čtvercové mřížky, kterou tvoří 16 řádků a 16 sloupců (celkem 256 buněk). Roboty musí najít bez pomoci cestu ze startovní předurčené výchozí polohy do cílové polohy, tím je obvykle centrum bludiště. Robot potřebuje sledovat, kde se nachází, prozkoumávat a objevovat, kde jsou stěny, mapovat bludiště a tím zjistit kdy dosáhne cíle. Provedení bludiště i robotu stanovují pravidla soutěže. [14]
7.2
Pravidla soutěže
Ačkoliv jsou pravidla soutěže většinou shodné, tak i přes to se v různých zemích malinko liší. Tyto pravidla jsou vypracované na základě pravidel soutěží "IEEE Micromouse Contest", které probíhají po celém světě.
7.2.1
Bludiště
Bludiště se skládá ze sítě základních čtverců o velikosti 18x18 cm, maximální rozměr bludiště je omezen na 16x16 základních čtverců. Stěny představující bludiště jsou 5 cm vysoké a 1,2 cm tlusté. Z toho plyne, že chodbičky bludiště jsou 16,8 cm široké. Vnější stěna uzavírá celé bludiště v jeden čtverec. Stěny bludiště jsou z boku bílé, horní strana stěn je červená. Podlaha bludiště je ze dřeva nebo z podobného materiálu, obvykle natřená matnou černou barvou. Barva na vrcholu stěn musí být vybrána tak, aby odrážela infračervené světlo, a barva na podlaze musí naopak absorbovat infračervené světlo. Start se nachází v jednom ze čtyřech rohů bludiště. Ve středu bludiště je otevřená část, tvořená čtyřmi základními čtverci. Tento centrální čtverec je cílem, vchod do tohoto čtverce je jen jeden. Je možné, že do cíle povede více než jedna cesta. [15] Upřesňující parametry: • • • •
Celkové rozměry bludiště musí být dodržené s přesností ±5% nebo 2 mm, vždy menší z obou hodnot. Spoje na podlaze nesmí vytvářet schůdky větší než 1 mm. Změna sklonu nesmí být větší než 4°. Mezery mezi souvisejícími stěnami jsou menší než 2 mm.
7.2.2 Robot – myš Myš musí být autonomní. Nesmí používat zdroj energie, který využívá spalovací proces. Délka a šířka nesmí překročit 25 cm. Pokud myš mění v průběhu jízdy svoje rozměry, v žádném okamžiku nesmí překročit 25x25 cm, výška není omezená. Myš nesmí během cesty bludištěm nic odhodit ani ztratit. Myš nesmí skákat, překračovat stěny, nebo po nich lézt. Také nesmí žádnou svou činností poškodit bludiště. [15]
Strana 47
7.2.3 Hodnocení Vítězem se stane robot s nejnižším dosaženým soutěžním časem. Pokud v průběhu soutěže nedosáhne žádná myš cíle, porota určí vítěze na základě celkové úspěšnosti, např. jak blízko k cíli se podařilo dostat, nebo jestli byl pohyb v bludišti koordinovaný nebo náhodný apod. [14]
7.3
Algoritmy pro řešení bludiště, kde neexistují tzv. ostrůvky
Ostrůvkem se rozumí ta část bludiště, která není nijak připojena k vnějšku bludiště stěnou. Záměrem tohoto zjednodušení je umožnit účast i začátečníkům, kteří se obvykle potřebují více soustředit na konstrukci robotu, než na samotný algoritmus. Robot nejprve projde celé bludiště pomoci algoritmu levé nebo pravé ruky (viz. kapitola 7.3.1), aby zmapoval přesný tvar bludiště a zjistil, kde se nacházejí stěny, poté použije flood-fill algoritmus (viz. kapitola 7.3.2) a nakonec se vydá směrem k cíli.
Obr. 24: Příklad bludiště bez ostrůvků
7.3.1 Algoritmus levé nebo pravé ruky Je mnoho algoritmů jak bludiště řešit, ale kohokoliv se zeptáte, jak se dostat ven z nějakého bludiště, tak vám odpoví, že položí ruku na stěnu a bude ji následovat kolem dokola bludiště, a dříve či později se dostane k východu, což je vlastně samotný algoritmus levé nebo pravé ruky. Avšak toto je pravda jen pro obzvlášť jednoduché typy bludišť a může být v pořádku s výjimkou tří věcí. Zaprvé oba směry nemusí být rovnocenné a zároveň to není nejkratší cesta do cíle. Zadruhé je to velmi pomalá metoda, protože se může stát, že následujeme celé bludiště, než se dostaneme k východu. Zatřetí může mít bludiště ostrůvky a můžeme chodit okolo nich pořád dokola.
Strana 48
7.3.2 Flood-fill algoritmus (the flood-fill algorithm) Metoda taktéž známa pod českým názvem jako algoritmus rozlévání, protože angl. „flood-fill“ = rozlévání, nebo-li záplava, dokonce i povodeň. Nejjednodušší metoda k dispozici pro Micromouse je flood-fill algoritmus. Základní myšlenka je taková, že každému políčku v mapě je přiřazena hodnota vzdálenosti do cíle, která je použita pro rozhodnutí, kterým směrem se má robot vydat. Cíli bude přiřazena hodnota nula a startu hodnota co nejvyšší. Při pohybu bludištěm k cíli je snaha jít jakoby „z kopce“ dolů. Jestliže robot stojí na políčku s hodnotou 3, je vzdálený o 3 pole od cíle. Jestliže robot stojí na políčku s hodnotou 1, je vzdálený o 1 pole od cíle, atd. Flood-fill algoritmus: 1. Připrav si pole 256 bytů k tomu, aby uchovávaly hodnoty vzdáleností do cíle pro kompletní bludiště (pro bludiště plné velikosti tj. 16x16 = 256 bytů), kde jeden byte představuje každé políčko v bludišti. 2. Začni v cíli. Tomuto políčku přiřaď hodnotu 0. 3. Vezmi všechna neočíslovaná volná políčka sousedící s již očíslovaným políčkem a přiřaď jim hodnotu o jedna vyšší. 4. Opakuj krok 3 do té doby, dokud není očíslovaný i start, nebo dokud nevyčerpáme všechna neočíslovaná políčka. 5. Při rekonstruování cesty začni ve startu. Následuj hodnoty do cíle v sestupném pořadí dokud nejsi v cíli. Příklad flood-fill algoritmu pro bludiště 5x5:
krok 1
krok 2
krok 3
krok 4
krok 5
krok 6
krok 7
krok 8
Obr. 25: Příklad flood-fill algoritmu pro bludiště 5x5 Poznámka: Kompletní ukázka příkladu flood-fill algoritmu pro bludiště 5x5 se nachází na CD přiloženém k bakalářské práci.
Strana 49
Výhody flood-fill algoritmu: • • •
Zajistí vždy nalezení nejkratší cesty, pokud nějaká existuje. Pokud existují dvě totožné cesty, jsou nalezeny obě. Tento algoritmus je rychlý a nenáročný na paměť (pro bludiště 16x16 potřebuje pouze 256 bytů).
Nevýhody flood-fill algoritmu: •
Délka hledání je velmi závislá na počtu cest vedoucích k cíli.
Flood-fill algoritmus je dobrý způsob jak najít nejkratší cestu bludištěm, které již máme předem zmapované. Je to spolehlivá a snadno pochopitelná a realizovatelná metoda, avšak máme na výběr i jiné algoritmy (Tremauxův algoritmus, Tarryho algoritmus).
7.4
Algoritmy pro řešení bludiště, kde existují tzv. ostrůvky
Bludiště pro mezinárodní soutěže Micromouse jsou navrženy tak, aby nebyly možné vyřešit algoritmem levé nebo pravé ruky, nebo nějakým náhodným mapováním terénu, protože cíl je v centru bludiště, a není připojen k vnějšku bludiště žádnou stěnou. Takže každý pokus o následování stěny nás přivede zpět tam, kde jsme začali, proto tedy musíme použít algoritmy jiné.
Obr. 26: Příklad bludiště s ostrůvky Následující akce vykonává robot každým krokem, když přejde do nového políčka: • • • •
Aktualizuje mapu a zjišťuje, jestli nenašel stěnu. Aktualizuje vzdálenosti do cíle (je-li to nezbytně nutné). Rozhoduje se, které sousední políčko má nejnižší vzdálenost do cíle. Přesune se do sousedního políčka s nejnižší vzdálenost do cíle.
Strana 50
7.4.1 Standardní flood-fill algoritmus (the flood-fill algorithm) Jedná se o stejný princip algoritmu jako v kapitole 7.3.2 s tou výjimkou, že v bludišti existují ostrůvky. Pro názornost budu vysvětlení algoritmů v kapitolách 7.4.1 a 7.4.2 ukazovat na bludišti o rozměrech 5x5, které by po vyplnění standardním flood-fill algoritmem vypadalo jako na obr. 27 (krok 1). Číselné hodnoty udávají vzdálenost z daného pole do středu bludiště, tj. do cíle. V následujícím textu budu označovat vzdálenost do cíle bludiště jen jako vzdálenost.
krok 1
krok 2
krok 3
krok 4
krok 5
krok 6
krok 7
krok 8
krok 9
krok 10
krok 11
krok 12
Obr. 27: Příklad standardního flood-fill algoritmu pro bludiště 5x5 Poznámka: Kompletní ukázka příkladu standardního flood-fill algoritmu pro bludiště 5x5 se nachází na CD přiloženém k bakalářské práci. Jakmile se má robot pohnout, musí prozkoumat všechny přiléhající políčka, které nejsou odděleny stěnami a vybrat si jedno s nejnižší hodnotou vzdálenosti. V našem výše uvedeném příkladu na obr. 27 (krok 2) si robot nebude všímat políčka na západě, protože je tam stěna. Robot si vybírá pouze z hodnot vzdáleností políček na severu, jihu a východě, protože tam nejsou žádné stěny. Políčko na severu má hodnotu 2, políčko na jihu má hodnotu 4 a políčko na východě má hodnotu 2. Standardní flood-fill algoritmus třídí hodnoty tak, aby rozhodnul, které políčka mají nejnižší vzdálenost.
Strana 51
To ukazuje, že obě políčka jak severní, tak východní mají vzdálenost 2, čili robot může jít na sever, nebo na východ a překročí stejné množství políček do cíle. Je jasné, že odbočení trvá robotu nějaký čas, tak si vybere cestu na políčko kupředu, čili na sever. Jak se robot postupně pohybuje v bludišti, tak nachází stěny. Jakmile jsou objeveny nové stěny, tak jsou vzdálenosti ovlivněny, a my je potřebujeme aktualizovat. V našem příkladu na obr. 27 (krok 3) je vidět, jak robot našel stěnu na východě. Nyní robot nemůže jít na západ, ani na východ, ale může jít pouze na sever, nebo jih. Ale při cestě na sever nebo na jih, by se nám vzdálenosti zvyšovaly a to my nechceme. Proto tedy následkem nalezení stěny v bludišti potřebujeme aktualizovat vzdálenosti v celém bludišti, což je na obr. 27 (krok 4). Robot by se následně pohyboval celým bludištěm, což je vidět na následujících krocích na obr. 27.
7.4.2 Modifikovaný flood-fill algoritmus (the modified flood-fill algorithm) Modifikovaný flood-fill algoritmus je podobný jako standardní flood-fill algoritmus v tom, že robot používá hodnoty vzdáleností do cíle (dále jen vzdálenosti) k tomu, aby se pohyboval bludištěm. Vzdálenosti představují, jak daleko je robot od cílového políčka a jsou následované v patřičném sestupném pořadí, dokud robot nedosáhne cíle.
krok 1
krok 2
krok 3
krok 4
krok 5
krok 6
krok 7
krok 8
krok 9
krok 10
krok 11
krok 12
Obr. 28: Příklad modifikovaného flood-fill algoritmu pro bludiště 5x5
Strana 52
Poznámka: Kompletní ukázka příkladu modifikovaného flood-fill algoritmu pro bludiště 5x5 se nachází na CD přiloženém k bakalářské práci. Jak robot nalézá nové stěny během prohledávání, je potřeba vždy aktualizovat vzdálenosti. Namísto aktualizování celého bludiště novými hodnotami, jak tomu je u standardního flood-fill algoritmu, modifikovaný flood-fill algoritmus změní jen ty vzdálenosti, které potřebují být aktualizovány. Jak je vidět na příkladu výše na obr. 28 (krok 3), tak se robot pohybuje vpřed o jedno políčko a nachází stěnu na východě. Nyní robot nemůže jít na západ, ani na východ, ale může jít pouze na sever, nebo jih. Ale při cestě na sever nebo na jih, by se nám vzdálenosti zvyšovaly, a to my nechceme, proto musíme aktualizovat vzdálenosti v bludišti, které potřebují být změněné. Nyní pro aktualizaci platí následující pravidlo: •
Jestliže políčko není cílovým políčkem, tak jeho hodnota vzdálenosti do cíle by měla být 1 + minimální hodnota jeho přímých otevřených sousedů.
Ve výše uvedeném příkladu na obr. 28 (krok 3) je minimální hodnota z jeho přímých otevřených sousedů 3. Přičtení 1 k této hodnotě má za výsledek 3 + 1 = 4, a my musíme provést aktualizaci. Bludiště nyní po aktualizaci vypadá takto obr. 28 (krok 4). Nyní aktualizace vzdálenosti políčka způsobí, že i sousedé by mohli porušit pravidlo „1 + minimální hodnota“ a tudíž i oni musí být zkontrolovány. V našem výše uvedeném příkladu na obr. 28 (krok 4) je vidět, že políčka na severu a na jihu mají sousedy, jejichž minimální hodnota je 2. Přičtení 1 k této hodnotě má za následek 2 + 1 = 3, proto políčka na severu a na jihu neporušují pravidlo a aktualizace je splněna. Nyní byly vzdálenosti aktualizované, a robot může znovu následovat hodnoty vzdáleností do cíle ve správném pořadí. Modifikovaný flood-fill algoritmus: 1. 2. 3. 4.
Aktualizuj vzdálenosti do cíle (je-li to nezbytné). Ujisti se, že je zásobník prázdný. Ulož aktuální políčko (to, na kterém robot stojí) na vrchol zásobníku. Opakuj následující soubor instrukcí dokud zásobník není prázdný: {Vytáhni políčko ze zásobníku Je hodnota do cíle tohoto políčka rovna 1 + minimální hodnota z jeho otevřených sousedů ? NE – změní políčko na 1 + minimální hodnota z jeho otevřených sousedů a umístí všechny otevřené sousední políčka navrchol zásobníku ke kontrole. ANO – nedělej nic.}
Shrnutí vlastností modifikovaného flood-fill algoritmu: Mnohokrát je modifikovaný flood-fill algoritmus rychlejší, než standardní flood-fill algoritmus. Aktualizují se jen ty vzdálenosti, které potřebují být aktualizované, robot může udělat svůj další pohyb tedy mnohem rychleji.
Strana 53
7.5
Algoritmus nejrychlejší cesty bludištěm
Algoritmus předpokládá, že známe přesnou konfiguraci bludiště, a dá se použít pro oba typy bludiště, jak bez ostrůvků, tak s ostrůvky. Algoritmus nejrychlejší cesty bludištěm: 1. Začni flood-fill algoritmem z cílového políčka až do startovního. 2. Předělej celé bludiště na orientovaný graf, kde každé políčko bludiště představuje uzel, a přechod mezi políčky je hrana grafu. 3. Ty části grafu, kde robot jede rovně sluč, protože robot nabere rychlost, když nemusí zatáčet. 4. Vypočti časy, za jak dlouho robot přejede daný počet políček dle vzorce: S S = 0,5 ⋅ a ⋅ t 2 ⇒ t = (4) 0,5 ⋅ a 5. Časově ohodnoť zatáčky a úseky políček, kde robot jede rovně. 6. Pro každou cestu bludištěm sečti všechny jednotlivé časy, a výsledky mezi sebou porovnej. 7. Ta cesta, která má nejmenší výsledný čas je nejrychlejší cesta bludištěm.
Příklad algoritmu nejrychlejší cesty bludištěm 8x8 (bludiště UAI FSI VUT Brno):
Obr. 29a): Bludiště FSI VUT 8x8
Obr. 29b): Bludiště FSI VUT 8x8
Podmínky, které vycházejí z konstrukce robotu Micromouse na UAI FSI VUT Brno: a = 0,5 políček/s2, vmax = v = 1 políčko/s, odbočka = t = 1 s s = počet políček, t = čas, a = zrychlení, v = rychlost Základní podmínka je zobrazena na obr. 30 a je taková, že robot dosáhne své maximální rychlosti až po dvou políčkách, jak je vidět níže. Systém je takový, že první dvě pole zrychluje, a poslední dvě naopak zpomaluje, tudíž jede přes jedno pole svou maximální rychlostí.
Strana 54
zrychlení max zpomalení
Obr. 30: Chování robotu Použité vztahy: S = 0,5 ⋅ a ⋅ t 2 ⇒ t = v=
S 0,5 ⋅ a
s s ⇒t = t v
(4) (5)
Výpočty pro algoritmus nejrychlejší cesty bludištěm: Výpočty času pro 1 políčko: celkový čas: t = t1 + t 2 = 1,414 + 1,414 = 2,828 s Výpočty času pro 2 políčka: celkový čas: t = t1 + t 2 = 2 + 2 = 4 s Výpočty času pro 3 políčka: celkový čas: t = t1 + t 2 = 2,499 + 2499 = 4,998 s Výpočty času pro 4 políčka: celkový čas: t = t1 + t 2 = 2,828 + 2,828 = 5,656 s Výpočty času pro 5 políček: celkový čas: t = t1 + t 2 + t 3 = 2,828 + 1 + 2,828 = 6,656 s Porovnání výsledků: Cesta na obr. 29a): t = 74,074 s, při délce 27 políček. Cesta na obr. 29b): t = 99,214 s, při délce 29 políček. Rozdíl obou cest: ∆t = 25,14 s. Závěr řešení: Příklad má, jak je vidět dvě řešení, to znamená, že existují dvě cesty. Na obr. 29a) je zvýrazněna cesta kratší, a v tomto případě i cesta rychlejší. Na obr. 29b) je zvýrazněná druhá cesta (delší a pomalejší). Poznámka: Kompletní ukázka příkladu algoritmu nejrychlejší cesty bludištěm FSI VUT 8x8 se nachází na CD přiloženém k bakalářské práci. Výhody algoritmu nejrychlejší cesty bludištěm: •
Nalezne nejrychlejší cestu, pokud existuje.
Nevýhody algoritmu nejrychlejší cesty bludištěm: •
Pro velké typy bludišť je obvykle orientovaný graf málo přehledný a řeší se obtížněji.
Strana 55
8
ZÁVĚR
Tato bakalářská páce se zabývá detailním přehledem algoritmů pro hledání cesty, a dále jejich vzájemným porovnáním z hlediska výhod, či nevýhod jednotlivých metod. Algoritmy pro hledání cest mají mnoho využití například ve virtuální realitě, robotice, umělé inteligenci a například v počítačových hrách, kde je ve strategiích simulováno chování člověka. Jejich základní rozdělení je na dvě skupiny, a to na algoritmy neinformované a algoritmy informované. V první části práce se zabývám neinformovanými algoritmy, nebo-li metodami slepého prohledávání, které se používají v jednodušších případech prohledávání stavového prostoru, protože neznají žádné specifické znalosti daného problému. Mezi tyto metody patří vyhledávání do šířky, které oproti vyhledávání do hloubky nalezne nejkratší řešení vždy pokud existuje, ovšem s tou nevýhodou, že má vyšší nároky na paměť. Pro velké stavové prostory se nejvhodněji využívá algoritmus iterativního prohlubování, protože spojuje výhody obou algoritmů jak do hloubky, tak do šířky. Velice rychlá metoda avšak za cenu toho, že si musíme pamatovat všechny navštívené uzly z obou konců je algoritmus vyhledávání do šířky v obou směrech. V druhé části práce se zabývám informovanými algoritmy, které naopak znají nějaké specifické znalosti daného problému a používají tzv. hodnotící funkce pro efektivnější způsoby prohledávání. U těchto metod se k prohledávání stavového prostoru výhodně používá algoritmus A*, který nahrazuje hodnotící funkce jejich odhady, a které vyjadřují jaké jsou šance nalézt optimální řešení. V neposlední řadě jsem uvedl algoritmy pro hledání cesty pro autonomní roboty soutěže typu Micromouse, kde se používají pro orientaci a následný pohyb bludištěm tzv. flood-fill algoritmy a to podle charakteru bludiště, zda-li obsahuje, nebo neobsahuje ostrůvky. Ostrůvkem se rozumí ta část bludiště, která není nijak připojena k vnějšku bludiště stěnou. V tomto smyslu tedy rozlišujeme standardní flood-fill algoritmus a modifikovaný flood-fill algoritmus. Dále byl vymyšlen algoritmus pro nejrychlejší cestu bludištěm, kde se spočte rychlost robotu, za kterou se dokáže rozjet na maximální rychlost a tedy se dostane nejrychleji ze startu do cíle. Nakonec byly vytvořeny názorné prezentace pro výukové účely, které se nacházejí na CD přiloženém k bakalářské práci. Příklady jsou ukazovány na úloze hlavolam „8“, protože na této úloze lze srozumitelně vidět princip daného algoritmu. Hlavním cílem těchto prezentací je studentům názorně předvést, jak daný algoritmus funguje a srovnat jej s teoretickým výkladem. Obsah CD přiloženého k bakalářské práci: Bakalářská práce ve formátu Adobe Acrobat [PDF]. Bakalářská práce ve formátu MS Word [DOC]. Příklady prezentací algoritmů: • • • • •
Prohledávání do hloubky, prohledávání do šířky, algoritmus iterativního prohlubování, hledání do šířky v obou směrech, gradientní algoritmus, rovnoměrné prohledávání, algoritmus A*, standardní flood-fill algoritmus, modifikovaný flood-fill algoritmus, algoritmus nejrychlejší cesty bludištěm.
Strana 56
Strana 57
SEZNAM POUŽITÉ LITERATURY [1]
WIKIPEDIE. Algoritmus – Wikipedie, otevřená encyklopedie [online]. 10.4. 2007 [cit. 20.1.2007]. Dostupný z:
.
[2]
HILDEBRAND, Antonín . pathref [online]. 8.9.2000 [cit. 20.1.2007]. Dostupný z: .
[3]
BAJER, Lukáš. Algoritmy pro pathfinding. [PDF dokument]. Duben 2006. [cit. 9.3.2007]. Dostupný z: .
[4]
HORÁK, Aleš. Prohledávání stavového prostoru. [PDF dokument]. podzim 2006, [cit. 18.3.2007]. Dostupný z: .
[5]
PĚCHOUČEK, Michal. Neinformované metody prohledávání stavového prostoru. [PDF dokument]. 15.2.2007 [cit. 10.2.2007]. Dostupný z: .
[6]
NEJEDLOVÁ, Dana. Umělá inteligence. [PDF dokument]. [cit. 27.1.2007]. Dostupný z: .
[7]
MAŘÍK, V.; a kolektiv. Umělá inteligence 1. Praha : Academia, 1993. 264 s. ISBN 80-200-0496-3.
[8]
ZBOŘIL, František; HANÁČEK, Petr. Umělá inteligence. Brno : Ediční středisko VUT Brno, Fakulta elektrotechnická, 10.7.1990. 125 s.
[9]
MIKULECKÝ, Peter; PONCE, Daniela. Základy umělé inteligence. Studijní text na KAI FŘIT VŠP Hradec Králové, 1996. 16 s.
[11]
MARADA, Tomáš. Informované metody. [DOC dokument]. 2006. Výuková prezentace Ing. Tomáše Marady, Ph.D. pro předmět algoritmy umělé inteligence 2006. 2 s.
[12]
BERKA, Petr. Umělá inteligence. [PDF dokument]. 2004 [cit. 29.1.2007]. Dostupný z: .
[13]
BŘEZINA, Tomáš. Algoritmy umělé inteligence, řešení úloh ve stavovém prostoru. Vysoké učení technické v Brně, Fakulta Strojního inženýrství, Ústav automatizace a informatiky. 40 s.
[14]
PASEKA, Tomáš. Návrh a realizace autonomního robotu pro kategorii IEEE Micromouse. Brno, květen 2006. 87 s. Diplomová práce na fakultě Strojního inženýrství na Ústavu mechaniky těles, mechatroniky a biomechaniky. Vedoucí diplomové práce Ing. Tomáš Marada, Ph.D.
2006
Strana 58
[15]
BALOGH, Richard. robotika.sk [online]. 12.2.2005 [cit. 24.3.2007]. Dostupné z: .
[16]
BENKOVIC, Steve. Hints, Ideas, Inspiration for Mice Builders [online]. [cit. 3.4.2007]. Dostupné z: .
