D * - D*

D * (vyslovuje se jako „hvězda D“) je kterýkoli z následujících tří souvisejících algoritmů přírůstkového vyhledávání :

• Původní D *, Anthony Stentz, je informovaný algoritmus přírůstkového vyhledávání.
• Focused D * je informovaný inkrementální heuristický vyhledávací algoritmus Anthonyho Stentze, který kombinuje myšlenky A * a původního D *. Zaostřený D * byl výsledkem dalšího vývoje původního D *.
• D * Lite je přírůstkový heuristický vyhledávací algoritmus od Svena Koeniga a Maxima Likhacheva, který staví na LPA * , přírůstkovém heuristickém vyhledávacím algoritmu, který kombinuje myšlenky A * a Dynamic SWSF-FP.

Všechny tři vyhledávací algoritmy řeší stejný předpoklad založený na plánování cesty problémy, včetně plánování s předpokladem, Freespace, kde robot má navigovat k danému cíli souřadnic v neznámém terénu. Vytváří předpoklady o neznámé části terénu (například: že neobsahuje žádné překážky) a podle těchto předpokladů najde nejkratší cestu od jeho aktuálních souřadnic k cílovým souřadnicím. Robot poté sleduje cestu. Když pozoruje nové mapové informace (například dříve neznámé překážky), přidá informace na svou mapu a v případě potřeby nahradí novou nejkratší cestu z aktuálních souřadnic na dané souřadnice cíle. Opakuje postup, dokud nedosáhne souřadnic cíle, nebo neurčí, že nelze dosáhnout souřadnic cíle. Při procházení neznámým terénem mohou být často objevovány nové překážky, takže toto přeplánování musí být rychlé. Inkrementální (heuristické) vyhledávací algoritmy urychlují hledání sekvencí podobných problémů s vyhledáváním pomocí zkušeností s předchozími problémy k urychlení hledání aktuálního. Za předpokladu, že se souřadnice cíle nezmění, jsou všechny tři vyhledávací algoritmy účinnější než opakované vyhledávání A *.

D * a jeho varianty byly široce používány pro mobilní roboty a autonomní navigaci vozidel . Současné systémy jsou obvykle založeny na D * Lite než na původním D * nebo Focussed D *. Ve skutečnosti dokonce i laboratoř Stentzu používá v některých implementacích spíše D * Lite než D *. Mezi takové navigační systémy patří prototypový systém testovaný na vozítkách Mars Opportunity a Spirit a navigační systém vítězného vstupu do soutěže DARPA Urban Challenge , oba vyvinuté na univerzitě Carnegie Mellon University .

Původní D * představil Anthony Stentz v roce 1994. Název D * pochází z termínu „Dynamic A *“, protože algoritmus se chová jako A * kromě toho, že se náklady na oblouk mohou během jeho běhu měnit.

Úkon

Základní operace D * je uvedena níže.

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

• NOVINKA, což znamená, že nikdy nebyla umístěna na OTEVŘENÝ seznam
• OPEN, což znamená, že je aktuálně na seznamu OPEN
• ZAVŘENO, což znamená, že již není na seznamu OPEN
• ZVÝŠIT, což znamená, že jeho cena je vyšší než naposledy, kdy byla na seznamu OPEN
• NIŽŠÍ, což znamená, že jeho cena je nižší než naposledy v seznamu OPEN

Rozšíření

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

• 

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

• 

  Expanze dokončena. Cesta je označena azurovou barvou.

Manipulace s překážkami

Když je detekována překážka podél zamýšlené cesty, všechny body, které jsou ovlivněny, se znovu umístí na seznam OPEN, tentokrát označený jako RAISE. Před zvýšením nákladů uzlu RAISED však algoritmus zkontroluje své sousedy a prozkoumá, zda může snížit náklady uzlu. Pokud ne, stav RAISE se rozšíří na všechny potomky uzlů, tj. Uzly, které k němu mají zpětné ukazatele. Tyto uzly se poté vyhodnotí a stav RAISE se předá a vytvoří vlnu. Když lze ZVÝŠENÝ uzel zmenšit, jeho zpětný ukazatel se aktualizuje a předá stav LOWER svým sousedům. Tyto vlny stavů RAISE a LOWER jsou srdcem D *.

Tímto bodem je zabráněno „dotknutí se“ vlnami celé řady dalších bodů. Algoritmus proto pracoval pouze na bodech, které jsou ovlivněny změnou ceny.

• 

  Byla přidána překážka (červená) a uzly označené RAISE (žlutá).

• 

  Probíhá expanze. Žlutá označuje uzly označené RAISE, zelená označuje uzly označené NÍZKÉ.

Nastává další zablokování

Tentokrát nelze patovou situaci obejít tak elegantně. Žádný z bodů nemůže najít novou trasu přes souseda do cíle. Proto nadále propagují zvýšení svých nákladů. Lze najít pouze body mimo kanál, které mohou vést k cíli životaschopnou cestou. Takto se vyvíjejí dvě spodní vlny, které se rozšiřují jako body označené jako nedosažitelné s novými informacemi o trase.

• 

  Kanál blokovaný dalšími překážkami (červený)

• 

  Probíhá expanze (zvedněte vlnu žlutě, spodní vlnu zeleně)

• 

  Nalezena nová cesta (azurová)

Pseudo kód

while (!openList.isEmpty()) {
    point = openList.getFirst();
    expand(point);
}

Rozšířit

void expand(currentPoint) {
    boolean isRaise = isRaise(currentPoint);
    double cost;
    for each (neighbor in currentPoint.getNeighbors()) {
        if (isRaise) {
            if (neighbor.nextPoint == currentPoint) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            } else {
                cost = neighbor.calculateCostVia(currentPoint);
                if (cost < neighbor.getCost()) {
                    currentPoint.setMinimumCostToCurrentCost();
                    openList.add(currentPoint);
                }
            }
        } else {
            cost = neighbor.calculateCostVia(currentPoint);
            if (cost < neighbor.getCost()) {
                neighbor.setNextPointAndUpdateCost(currentPoint);
                openList.add(neighbor);
            }
        }
    }
}

Zkontrolujte navýšení

boolean isRaise(point) {
    double cost;
    if (point.getCurrentCost() > point.getMinimumCost()) {
        for each(neighbor in point.getNeighbors()) {
            cost = point.calculateCostVia(neighbor);
            if (cost < point.getCurrentCost()) {
                point.setNextPointAndUpdateCost(neighbor);
            }
        }
    }
    return point.getCurrentCost() > point.getMinimumCost();
}

Varianty

Zaostřeno na D *

Jak název napovídá, Focused D * je rozšíření D *, které pomocí heuristiky zaměřuje šíření RAISE a LOWER směrem k robotovi. Tímto způsobem se aktualizují pouze státy, na kterých záleží, stejně, jako A * počítá náklady pouze pro některé uzly.

D * Lite

D * Lite není založen na původním D * nebo Focused D *, ale implementuje stejné chování. Je srozumitelnější a lze jej implementovat do méně řádků kódu, proto název „D * Lite“. Z hlediska výkonu je stejně dobrý nebo lepší než Focused D *. D * Lite je založen na celoživotním plánování A * , které představili Koenig a Likhachev před několika lety. D * Lite

Minimální náklady versus současné náklady

U D * je důležité rozlišovat mezi současnými a minimálními náklady. První je důležitý pouze v době sběru a druhý je zásadní, protože třídí OpenList. Funkce, která vrací minimální cenu, je vždy nejnižší cenou do aktuálního bodu, protože se jedná o první záznam OpenList.

Reference

externí odkazy

• Webová stránka Sven Koenig
• Webová stránka Anthonyho Stentze