Theta * - Theta*

Theta * je libovolný úhel algoritmus plánování cesty to je založeno na * Vyhledávací algoritmus. Může najít téměř optimální cesty s dobou chodu srovnatelnou s dobou A *.^[1]

Popis

U nejjednodušší verze Theta * je hlavní smyčka téměř stejná jako u A *. Jediný rozdíl je ${ displaystyle { text {update}} _ { text {vertex}} ()}$ funkce. Ve srovnání s A * nemusí rodič uzlu v Theta * být sousedem uzlu, pokud je mezi dvěma uzly přímá viditelnost.^{[Citace je zapotřebí ]}

Pseudo kód

Převzato z.^[2]

funkce theta*(Start, fotbalová branka)    // Tato hlavní smyčka je stejná jako A *    gScore(Start) := 0    rodič(Start) := Start    // Inicializace otevřených a uzavřených sad. Otevřená sada je inicializována     // s počátečním uzlem a počáteční cenou    otevřeno := {}    otevřeno.vložit(Start, gScore(Start) + heuristický(Start))    // gScore (uzel) je aktuální nejkratší vzdálenost od počátečního uzlu k uzlu    // heuristika (uzel) je odhadovaná vzdálenost uzlu od uzlu cíle    // existuje mnoho možností pro heuristiku, jako je euklidovský nebo manhattanský     Zavřeno := {}    zatímco otevřeno je ne prázdný        s := otevřeno.pop()        -li s = fotbalová branka            vrátit se rekonstruovat_cesta(s)        Zavřeno.tlačit(s)        pro každý soused z s        // Smyčka skrz každého bezprostředního souseda s            -li soused ne v Zavřeno                -li soused ne v otevřeno                    // Inicializujte hodnoty pro souseda, pokud je                     // již není v otevřeném seznamu                    gScore(soused) := nekonečno                    rodič(soused) := Nula                update_vertex(s, soused)    vrátit se Nula                funkce update_vertex(s, soused)    // Tato část algoritmu je hlavním rozdílem mezi A * a Theta *    -li přímá viditelnost(rodič(s), soused)        // Pokud je mezi rodiči a sousedem přímá viditelnost        // potom ignorujte s a použijte cestu od rodičů k sousedům         -li gScore(rodič(s)) + C(rodič(s), soused) < gScore(soused)            // c (s, soused) je euklidovská vzdálenost od s k sousedovi            gScore(soused) := gScore(rodič(s)) + C(rodič(s), soused)            rodič(soused) := rodič(s)            -li soused v otevřeno                otevřeno.odstranit(soused)            otevřeno.vložit(soused, gScore(soused) + heuristický(soused))    jiný        // Pokud je délka cesty od začátku do s a od s do         // soused je kratší než nejkratší momentálně známá vzdálenost        // od začátku k sousedovi, poté aktualizujte uzel o novou vzdálenost        -li gScore(s) + C(s, soused) < gScore(soused)            gScore(soused) := gScore(s) + C(s, soused)            rodič(soused) := s            -li soused v otevřeno                otevřeno.odstranit(soused)            otevřeno.vložit(soused, gScore(soused) + heuristický(soused))funkce rekonstruovat_cesta(s)    celková_cesta = {s}    // Tím se rekurzivně rekonstruuje cesta z uzlu cíle     // dokud není dosažen počáteční uzel    -li rodič(s) != s        celková_cesta.tlačit(rekonstruovat_cesta(rodič(s)))    jiný        vrátit se celková_cesta

Varianty

Existují následující varianty algoritmu:^{[Citace je zapotřebí ]}

Líný Theta *^[3] - Expanze uzlů jsou zpožděny, což má za následek méně kontrol přímého pohledu
Inkrementální Phi * - Modifikace Theta *, která umožňuje dynamické plánování cest podobné D *

Viz také

Reference

[1] Empirické srovnání algoritmů plánování trasy v libovolném úhlu

[2] Theta *: Plánování sítí v libovolném úhlu

[3] ttp://idm-lab.org/bib/abstracts/papers/aaai10b.pdf

[1]

[2]

[3]