Celoživotní plánování A * - Lifelong Planning A*

Třída	Vyhledávací algoritmus
Datová struktura	Graf

LPA * nebo celoživotní plánování A * je inkrementální heuristický vyhledávací algoritmus založený na A * . Poprvé to popsali Sven Koenig a Maxim Likhachev v roce 2001.

Obsah

1 Popis
2 Pseudo kód
3 Vlastnosti
4 Varianty
5 Reference

Popis

LPA * je přírůstková verze A *, která se dokáže přizpůsobit změnám v grafu bez přepočítání celého grafu aktualizací hodnot g (vzdálenost od začátku) z předchozího vyhledávání během aktuálního vyhledávání, aby je v případě potřeby opravila. Stejně jako A * používá LPA * heuristiku, což je spodní hranice nákladů na cestu z daného uzlu k cíli. Heuristika je přípustná, pokud je zaručeno, že bude nezáporná (nula je přípustná) a nikdy nebude vyšší než cena nejlevnější cesty k cíli.

Předchůdci a nástupci

S výjimkou začátku a na brankové každý uzel $n$ má předchůdce a následníky :

Jakýkoli uzel, ze kterého hrana vede k $n,$ je předchůdcem $n$ .
Jakýkoli uzel, do kterého hrana vede z $n,$ je nástupcem $n$ .

V následujícím popisu tyto dva výrazy odkazují pouze na bezprostřední předchůdce a nástupce, nikoli na předchůdce předchůdců nebo nástupců následovníků.

Počáteční odhady vzdálenosti

LPA * udržuje dva odhady počáteční vzdálenosti $g * (n)$ pro každý uzel:

$g (n)$ , dříve vypočtená hodnota g (počáteční vzdálenost) jako v A *
$rhs (n)$ , vyhledávací hodnota založená na hodnotách g předchůdců uzlu (minimum všech $g (n ') + d (n', n)$ , kde $n '$ je předchůdce $n$ a $d (x, y),$ jsou náklady na okraji spojovací $x$ a $y$ )

Pro počáteční uzel platí vždy následující:

{\ displaystyle rhs (start) = g (start) = 0}

Pokud se $rhs (n)$ rovná $g (n)$ , pak $n$ se nazývá lokálně konzistentní . Pokud jsou všechny uzly lokálně konzistentní, lze určit nejkratší cestu jako u A *. Když se však změní náklady na okraji, místní konzistence musí být obnovena pouze pro ty uzly, které jsou relevantní pro trasu.

Prioritní fronta

Když se uzel stane místně nekonzistentním (protože se změnila cena jeho předchůdce nebo okraje spojujícího jej s předchůdcem), umístí se do prioritní fronty pro opětovné vyhodnocení. LPA * používá dvourozměrný klíč:

{\ displaystyle k (n) = {\ begin {bmatrix} k_ {1} (n) \\ k_ {2} (n) \\\ end {bmatrix}} = {\ begin {bmatrix} min (g (n ), rhs (n)) + h (n, cíl) \\ min (g (n), rhs (n)) \\\ end {bmatrix}}}

Položky jsou seřazeny podle $k 1$ (což odpovídá přímo f-hodnotám použitým v A *), poté $k 2$ .

Rozšíření uzlu

Horní uzel ve frontě se rozbalí takto:

Pokud se rhs-hodnota uzlu rovná jeho g-hodnotě, je uzel lokálně konzistentní a je z fronty odstraněn.
Pokud je hodnota rhs uzlu menší než jeho hodnota g (známá jako lokálně nadměrně konzistentní uzel), hodnota g se změní tak, aby odpovídala hodnotě rhs, čímž se uzel stane lokálně konzistentním. Uzel je poté odebrán z fronty.
Pokud je rhs-hodnota uzlu větší než jeho g-hodnota (známá jako lokálně podkonzistentní uzel), je g-hodnota nastavena na nekonečno (díky čemuž je uzel lokálně nadkonzistentní nebo lokálně konzistentní). Pokud je uzel lokálně konzistentní, je z fronty odebrán, jinak je jeho klíč aktualizován.

Vzhledem k tomu, že změna hodnoty g uzlu může také změnit hodnoty rhs jeho následníků (a tedy jejich místní konzistenci), vyhodnotí se a v případě potřeby se aktualizuje jejich členství ve frontě a klíč.

Expanze uzlů pokračuje dalším uzlem v horní části fronty, dokud nebudou splněny dvě podmínky:

Cíl je místně konzistentní a
Uzel v horní části prioritní fronty má klíč, který je větší nebo roven klíči pro cíl.

Počáteční běh

Graf se inicializuje nastavením hodnoty rhs počátečního uzlu na 0 a jeho hodnoty g na nekonečno. U všech ostatních uzlů se předpokládá, že jak hodnota g, tak hodnota rhs jsou nekonečno, dokud nebude přiřazeno jinak. To zpočátku dělá počáteční uzel jediným lokálně nekonzistentním uzlem, a tedy jediným uzlem ve frontě. Poté začne expanze uzlů. První běh LPA * se tak chová stejným způsobem jako A * a rozšiřuje stejné uzly ve stejném pořadí.

Změny nákladů

Když se změní cena hrany, LPA * prozkoumá všechny uzly ovlivněné změnou, tj. Všechny uzly, na kterých končí jedna ze změněných hran (pokud lze hranou procházet v obou směrech a změna ovlivní oba směry, oba uzly spojené hrana je zkoumána):

Hodnoty rhs uzlů jsou aktualizovány.
Uzly, které se staly místně konzistentními, jsou z fronty odstraněny.
Uzly, které se staly lokálně nekonzistentními, se přidají do fronty.
Uzly, které zůstávají lokálně nekonzistentní, mají své klíče aktualizované.

Poté se obnova uzlů obnoví, dokud nebude dosaženo konečné podmínky.

Hledání nejkratší cesty

Po dokončení rozšíření uzlu (tj. Jsou splněny podmínky ukončení) se vyhodnotí nejkratší cesta. Pokud se cena za cíl rovná nekonečnu, neexistuje cesta konečných nákladů od začátku do cíle. V opačném případě lze nejkratší cestu určit pohybem vzad:

Začněte od cíle.
Přesuňte se na předchůdce $n '$ aktuálního uzlu $n,$ pro který je $g (n') + d (n ', n)$ nejnižší (pokud nejnižší skóre sdílí více uzlů, každý je platným řešením a každý z nich může být zvoleno libovolně).
Opakujte předchozí krok, dokud nedosáhnete začátku.

Pseudo kód

Tento kód předpokládá prioritní frontu queue, která podporuje následující operace:

topKey() vrací (číselně) nejnižší prioritu libovolného uzlu ve frontě (nebo nekonečno, pokud je fronta prázdná)
pop() odebere uzel s nejnižší prioritou z fronty a vrátí jej
insert(node, priority) vloží do fronty uzel s danou prioritou
remove(node) odebere uzel z fronty
contains(node) vrátí true, pokud fronta obsahuje zadaný uzel, false, pokud ne

void main() {
  initialize();
  while (true) {
    computeShortestPath();
    while (!hasCostChanges())
      sleep;
    for (edge : getChangedEdges()) {
        edge.setCost(getNewCost(edge));
        updateNode(edge.endNode);
    }
  }
}

void initialize() {
  queue = new PriorityQueue();
  for (node : getAllNodes()) {
    node.g = INFINITY;
    node.rhs = INFINITY;
  }
  start.rhs = 0;
  queue.insert(start, calculateKey(start));
}

/** Expands the nodes in the priority queue. */
void computeShortestPath() {
  while ((queue.getTopKey() < calculateKey(goal)) || (goal.rhs != goal.g)) {
    node = queue.pop();
    if (node.g > node.rhs) {
      node.g = node.rhs;
      for (successor : node.getSuccessors())
        updateNode(successor);
    } else {
      node.g = INFINITY;
      updateNode(node);
      for (successor : node.getSuccessors())
        updateNode(successor);
    }
  }
}

/** Recalculates rhs for a node and removes it from the queue.
 * If the node has become locally inconsistent, it is (re-)inserted into the queue with its new key. */
void updateNode(node) {
  if (node != start) {
    node.rhs = INFINITY;
    for (predecessor: node.getPredecessors())
      node.rhs = min(node.rhs, predecessor.g + predecessor.getCostTo(node));
    if (queue.contains(node))
      queue.remove(node);
    if (node.g != node.rhs)
      queue.insert(node, calculateKey(node));
  }
}

int[] calculateKey(node) {
  return {min(node.g, node.rhs) + node.getHeuristic(goal), min(node.g, node.rhs)};
}

Vlastnosti

Být algoritmicky podobný A *, LPA * sdílí mnoho z jeho vlastností.

Každý uzel je rozšířen (navštíven) maximálně dvakrát pro každý běh LPA *. Lokálně nadměrně konzistentní uzly se rozšiřují maximálně jednou za běh LPA *, takže jeho počáteční běh (ve kterém každý uzel přejde do nadkonzistentního stavu) má podobný výkon jako A *, který navštíví každý uzel maximálně jednou.
Klíče uzlů rozšířených pro každý běh jsou monotónně neklesající v průběhu času, jako je tomu v případě A *.
Čím jsou heuristiky informovanější (a tedy větší) (přestože stále splňují kritéria přijatelnosti), tím méně uzlů je třeba rozšířit.
Implementace prioritní fronty má významný dopad na výkon, jako v A *. Použití haldy Fibonacci může vést k výraznému zvýšení výkonu oproti méně efektivním implementacím.

Pro implementaci A *, která přeruší vazby mezi dvěma uzly se stejnými hodnotami f ve prospěch uzlu s menší hodnotou g (což není v A * dobře definováno), platí také následující tvrzení:

Pořadí, ve kterém jsou lokálně nadměrně konzistentní uzly expandovány, je identické s A *.
Ze všech lokálně nadměrně konzistentních uzlů je třeba rozšířit pouze ty, jejichž cena nepřesahuje cenu cíle, jako je tomu v případě A *.

LPA * má navíc následující vlastnosti:

Když se změní náklady na okraji, LPA * překoná A * (za předpokladu, že je spuštěn od nuly), protože je třeba znovu rozšířit pouze zlomek uzlů.

Varianty

D * Lite , reimplementace algoritmu D * na základě LPA *

Languages

In other projects