Lifelong Planning A*

Az LPA* vagy Lifelong Planning A* egy heurisztikus keresési algoritmus, amely az A*-on alapul. Először Sven Koenig és Maxim Likhachev írta le 2001-ben.

Leírás

Az LPA* az A* egy növekményes változata, amely alkalmazkodni tud a grafikon változásaihoz anélkül, hogy a teljes grafikont újra kiszámítaná, frissíti a g-értékeket (a kezdetektől való távolságot) az előző keresésből az aktuális keresés során, hogy szükség esetén helyesbítse azokat. Az A*-hoz hasonlóan az LPA* heurisztikát is használ, amely az adott csomóponttól a célig vezető út költségeinek alsó határa. A heurisztika elfogadható, ha garantáltan nem negatív (nulla megengedett), és soha nem haladja meg a cél elérésének legolcsóbb útjának költségét.

Elődök és utódok

A kezdő és a cél csomópont kivételével minden n csomópont rendelkezik elődökkel és utódokkal:

• Bármely csomópont, amelybe él vezet n egy elődje.
• Bármelyik csomópont, amelyből él vezet az n utódja.

A következő leírásban ez a két kifejezés csak a közvetlen elődökre és utódokra utal, nem pedig az elődök elődeire vagy az utódok utódaira.

A távolság becslései

Az LPA* a g*(n) kezdési távolság két becslését készíti el minden csomópontnál:

• g(n), az előzőleg kiszámított g-érték (kezdeti távolság) mint az A* algoritmusban
• rhs(n), a előrejelzett érték amelyek a csomópont elődjeinek g-értékén alapul (a g(n' ) + d(n' , n) minimuma, ahol n' az n elődje és d(x, y) az x és y csomópontokat összekötő él költsége)

A kezdő csomópont esetében a következő mindig igaz:

$rhs(start)=g(start)=0$

Ha rhs(n) megegyezik g(n)-nel akkor n-t lokálisan konzisztensnek nevezzük. Ha az összes csomópont lokálisan konzisztens, akkor a legrövidebb utat meg lehet határozni, mint az A*-nál. Ha azonban az élköltségek megváltoznak, a lokális konzisztenciát csak az útvonal szempontjából releváns csomópontokban kell kiszámítani.

Prioritási sor

Amikor egy csomópont lokálisan inkonzisztenssé válik (mivel elődjének költsége vagy az elődjének összekötő élének költsége megváltozott), akkor az algoritmus prioritási sorba helyezi az újraértékeléshez. Az LPA* kétdimenziós kulcsot használ:

$k(n)={\begin{bmatrix}k_{1}(n)\\k_{2}(n)\\\end{bmatrix}}={\begin{bmatrix}min(g(n),rhs(n))+h(n,goal)\\min(g(n),rhs(n))\\\end{bmatrix}}$

A bejegyzések először k₁ (amely közvetlenül megfelel az A*-ban használt f-értékeknek), majd k₂ szerint vannak rendezve.

Csomópont bővítés

A sor felső csomópontja az alábbiak szerint bővül:

• Ha egy csomópont rhs-értéke megegyezik g-értékével, akkor a csomópont lokálisan konzisztens, és eltávolításra kerül a sorból.
• Ha egy csomópont rhs-értéke kisebb, mint g-értéke (helyileg túlkonzisztens csomópontnak nevezik), akkor a g-értéket úgy módosítja, hogy megfeleljen az rhs-értéknek, így a csomópont lokálisan konzisztens lesz. Ezután a csomópontot eltávolítják a sorból.
• Ha egy csomópont rhs-értéke nagyobb, mint g-értéke (helyileg aligkonzisztens csomópontként nevezik), akkor a g-értéket végtelenre állítják (ami a csomópontot lokálisan túlkonzisztensnek vagy lokálisan konzisztensnek tekinti). Ha a csomópont lokálisan konzisztens, akkor azt eltávolítják a sorból, a kulcs megújul.

Mivel egy csomópont g-értékének megváltoztatása megváltoztathatja utódjainak rhs-értékeit (és így lokális konzisztenciájukat), ezeket kiértékeljük, és a sor sorrendjük és kulcsuk szükség esetén frissül.

A csomópontok bővítése a sor tetején lévő következő csomóponttal folytatódik, amíg két feltétel teljesül:

• A cél lokálisan konzisztens, és
• A prioritási sor tetején levő csomópontnak olyan kulcs van, amely nagyobb vagy egyenlő a cél kulcsával.

Kezdeti futás

A grafikon inicializálása úgy történik, hogy a kezdő csomópont rhs-értékét 0-ra, g-értékét végtelenre állítja. Az összes többi csomópontnál mind a g-értéket, mind az rhs-értéket végtelennek tekintik, amíg azok nem változnak meg. Ez kezdetben a kezdő csomópontot az egyetlen lokálisan inkonzisztens csomóponttá, és ezáltal a sor egyetlen csomópontjává teszi. Ezután megkezdődik a csomópont-bővítés. Az LPA* első futtatása tehát ugyanúgy viselkedik, mint az A*, azaz ugyanazon csomópontok kibővítése történik ugyanabban a sorrendben.

Költségváltozások

Amikor egy él költsége megváltozik, az LPA* megvizsgálja a változás által érintett összes csomópontot, azaz azokat a csomópontokat, amelyeknél az egyik megváltozott él lezárul (ha egy él mindkét irányban áthaladhat, és a változás mindkét irányba hat, az él mindkét végét megvizsgáljuk):

• A csomópontok rhs-értékei frissülnek.
• Azok a csomópontok, amelyek lokálisan konzisztensek lettek, eltávolításra kerülnek a sorból.
• Azok a csomópontok, amelyek lokálisan inkonzisztenssé váltak, hozzáadódnak a sorhoz.
• Azok a csomópontok, amelyek lokálisan inkonzisztensek maradnak, a kulcsokat frissítik.

Ezt követően a csomópont kibővítése folytatódik, amíg a végső feltételt elérik.

A legrövidebb út megkeresése

Amint a csomópont kibővítése befejeződött (azaz a kilépési feltételek teljesülnek), a legrövidebb utat kiértékelik. Ha a cél költsége megegyezik a végtelenséggel, akkor nincs elegendő költségút az indulástól a célig. Egyébként a legrövidebb utat visszafelé haladással lehet meghatározni:

• Kezdje a céltól.
• Lépjen az aktuális n csomópont n' elődjére, ahol a g(n' ) + d(n' , n) a legalacsonyabb (ha a legalacsonyabb pontszámot több csomópont is eléri, akkor mindegyik érvényes megoldás, és ezek közül bármelyiket lehet választani).
• Ismételje meg az előző lépést, amíg el nem éri a startot.

Pszeudokód

Ez a kód feltételezi a queue prioritási sort, amely támogatja a következő műveleteket:

• topKey() visszaadja a sorban lévő bármely csomópont (numerikusan) legalacsonyabb prioritását (vagy végtelennek, ha a sor üres)
• pop() eltávolítja a sorból a legalacsonyabb prioritású csomópontot, és visszatér
• insert(node, priority) beszúr egy adott prioritással rendelkező csomópontot a sorba
• remove(node) eltávolítja a csomópontot a sorból
• contains(node) igaz értéket ad, ha a sor a megadott csomópontot tartalmazza; hamist, ha nem

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)};
}

Tulajdonságok

Mivel algoritmikusan hasonló az A*-hoz, az LPA* számos tulajdonságát megosztja.

• Minden csomópontot az LPA* futtatásakor legfeljebb kétszer kibontunk (látogatunk meg). A lokálisan túlkonzisztens csomópontok LPA* futtatásonként legfeljebb egyszer kibővülnek, így az első futtatás (amelyben minden csomópont túlkonzisztens állapotba lép) hasonló teljesítményű, mint az A*, amely minden csomópontot egyszerre meglátogat.
• Az egyes futtatásokhoz kibővített csomópontok kulcsai monoton módon nem csökkennek az idő múlásával, mint az A* esetében.
• Minél informáltabb (és így nagyobb) a heurisztika (miközben továbbra is teljesíti az elfogadhatósági kritériumokat), annál kevesebb csomópontot kell kibővíteni.
• A prioritási sor végrehajtása jelentős hatást gyakorol a teljesítményre, mint az A* esetében. A Fibonacci-halom használata jelentős teljesítménynövekedést eredményezhet a kevésbé hatékony megvalósításokhoz képest.

Az A* megvalósítás esetén, amely megszakítja a két csomópont közötti egyenlő f-értékek közötti kapcsolatokat a kisebb g-értékű csomópont javára (amelyet az A* nem határoz meg pontosan), a következő állítások is igazak:

• A lokálisan túlkonzisztens csomópontok kibővítésének sorrendje megegyezik az A*-gal.
• Az összes lokálisan túlkonzisztens csomópont közül csak azokat - amelyek költsége nem haladja meg a célt - kell kibővíteni, mint az A* esetében.

Az LPA* ezen felül a következő tulajdonságokkal rendelkezik:

• Amikor az élköltségek megváltoznak, az LPA* felülmúlja az A*-ot (feltételezve, hogy az utóbbi a nulláról indul), mivel csak a csomópontok töredékét kell kibővíteni.

Változatok

• D* Lite, a D* algoritmus újbóli megvalósítása LPA* alapján

Fordítás

• Ez a szócikk részben vagy egészben a Lifelong Planning A* című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.