Vyhledávací algoritmus D*

Vyhledávací algoritmus D* (vyslovuje se "De Star" ) je kterýkoli ze tří souvisejících přírůstkových vyhledávacích algoritmů :

• Původní D* algoritmus [1] od Anthonyho Stentze je informovaný inkrementální vyhledávací algoritmus.
• Focused D* [2]  je inkrementální heuristický vyhledávací algoritmus vyvinutý Anthonym Stentzem, který kombinuje myšlenky A* [3] a původního D* . Focused D* je dalším vývojem původního D* .
• Lightweight D* [4]  je inkrementální heuristický vyhledávací algoritmus vytvořený Svenem Königem a Maximem Likhachevem, který je založen na LPA* [5] , inkrementálním heuristickém vyhledávacím algoritmu, který kombinuje nápady z vyhledávacího algoritmu A* a dynamického SWSF-FP [6] ] .

Všechny tři vyhledávací algoritmy řeší stejné problémy s předpoklady plánování cesty , včetně plánování s předpoklady volného prostoru [7] , kdy musí robot navigovat na dané cílové souřadnice v neznámém terénu. Vytváří předpoklady o neznámé části terénu (např. že na něm nejsou žádné překážky) a za těchto předpokladů najde nejkratší cestu ze svých aktuálních souřadnic k souřadnicím cíle. Robot pak sleduje cestu. Když na mapě zpozoruje nové informace (například dosud neznámé překážky), doplní si tyto informace do své mapy a v případě potřeby přeplánuje novou nejkratší cestu z aktuálních souřadnic na zadané cílové souřadnice. Opakuje proces, dokud nedosáhne cílových souřadnic nebo nezjistí, že cílové souřadnice nelze dosáhnout. Při přejezdu neznámým terénem lze často objevit nové překážky, takže toto přeplánování musí být rychlé. Inkrementální (heuristické) vyhledávací algoritmy urychlují vyhledávání sekvencí podobných vyhledávacích problémů a využívají zkušenosti z řešení předchozích problémů k urychlení vyhledávání aktuálního. Za předpokladu, že se cílové souřadnice nemění, jsou všechny tři vyhledávací algoritmy efektivnější než opakované A* vyhledávání .

D* a jeho varianty byly široce používány pro mobilní roboty a autonomní navigační vozidla . Moderní systémy jsou obvykle založeny na lehkých , spíše než na původním nebo zaměřeném D* . Ve skutečnosti dokonce i Stenzova laboratoř v některých implementacích používá spíše odlehčenou konstrukci než původní D* [8] . Mezi takové navigační systémy patří prototyp systému testovaný na Mars roverech Opportunity a Spirit a navigační systém vítěze DARPA Urban Challenge , oba vyvinuté na Carnegie Mellon University .

Původní D* byl představen v roce 1994 Anthonym Stentzem . Název D* pochází z výrazu „ Dynamic A * “ , protože algoritmus se chová jako A * [ 2] , kromě toho, že cena oblouku se může během běhu algoritmu měnit .

Operace

Hlavní operace D* jsou popsány níže.

Stejně jako Dijkstrův algoritmus a A * udržuje D* seznam uzlů k vyhodnocení, známý jako OPEN list . Uzly jsou označeny jako mající jeden z několika stavů:

• NEW znamená, že nikdy nebyl umístěn na seznam OPEN .
• OPEN znamená, že je aktuálně na seznamu OPEN .
• CLOSED znamená, že již není na seznamu OPEN .
• RAISED , znamená , že jeho hodnota je vyšší , než když byl naposledy na seznamu OPEN .
• LOWER , znamená , že jeho hodnota je nižší , než když byla naposledy na OPEN Listu .

Rozšíření

Algoritmus funguje tak, že iterativně vybere uzel ze seznamu OPEN a vyhodnotí jej. Poté šíří změny uzlu do všech sousedních uzlů a umístí je do seznamu OPEN . Tento distribuční proces se nazývá „expanze“ . Na rozdíl od kanonické A* , která sleduje cestu od začátku do konce, D* začne hledat zpětně od cílového uzlu. Každý rozšířený uzel má zpětný ukazatel, který odkazuje na další uzel vedoucí k cíli, a každý uzel zná přesné náklady na cíl. Když je počáteční uzel dalším uzlem, který se rozšíří, algoritmus je hotov a cestu k cíli lze najít jednoduchým sledováním zpětných značek.

• Probíhá rozšiřování. Cílový uzel (žlutý) je uprostřed horní řady teček, počáteční uzel je uprostřed spodní řady. Červená označuje překážku; černá/modrá označuje rozšířené uzly (jas označuje náklady). Zelená označuje uzly, které se rozšiřují.

• Rozšíření dokončeno. Cesta je znázorněna modře.

Překonávání překážek

Když je na dané cestě nalezena překážka, všechny dotčené body jsou opět umístěny na seznam OPEN , tentokrát označený UP . Před zvýšením nákladů na uzel BOOSTER však algoritmus zkontroluje své sousedy a prozkoumá, zda může snížit náklady na uzel. V opačném případě se stav UP šíří na všechny potomky uzlů, tj. na uzly, které mají zpětné ukazatele. Tyto uzly jsou poté vyhodnoceny a je přenášen stav UP , tvořící vlnu. Když lze zmenšit uzel UP , jeho backpointer se aktualizuje a předá stav DOWN svým sousedům. Tyto vlny NAHORU a DOLŮ jsou srdcem D* .

V tomto bodě se vlny nemohou dotknout řady dalších bodů. Algoritmus tedy pracoval pouze s body, které jsou ovlivněny změnou hodnoty.

• Překážka se přidá (červená) a uzly se označí jako UP (žlutá).

• Probíhá rozšiřování. Uzly označené jako LIFT jsou označeny žlutě, uzly označené jako LOWER jsou označeny zeleně .

Další slepá ulička

Tentokrát je nemožné prolomit patovou situaci tak elegantně. Žádný z bodů nemůže najít novou trasu přes souseda do cíle. Takže dál propagují své uznání. Mimo kanál můžete najít pouze body, které mohou vést k cíli podél schůdné trasy. Takto se vyvíjejí dvě vlny BOTTOM , které se rozšíří do bodů označených jako nedosažitelné s novými informacemi o trase.

• Kanál je blokován dalšími překážkami (červená).

• Probíhá rozšiřování. RAISE vlna (žlutá), LOWER vlna (zelená).

• Našel NOVOU cestu (modrá).

Pseudokód