Hayatboyu Planlama A * - Lifelong Planning A*

Sınıf	Arama algoritması
Veri yapısı	grafik

LPA * veya Hayatboyu Planlama A * bir olan artan sezgisel arama dayalı algoritma A * . İlk 2001 yılında Sven Koenig ve Maxim Likhachev tarafından tarif edilmiştir.

içindekiler

1 Açıklama
2 Pseudocode
3 Özellikleri
4 Varyantlar
5 Kaynaklar

Açıklama

LPA * gerektiğinde düzeltmek için mevcut arama sırasında önceki aramadan g-değerlerine (baştan mesafe) güncelleyerek, tüm grafik yeniden hesaplamadan grafikte değişikliklere uyum sağlayabilen bir *, artımlı bir versiyonudur. A * gibi, LPA * hedefe belirli bir düğümden yolun maliyeti için bir alt sınır olan bir sezgisel kullanır. o negatif olmayan (sıfır kabul edilebilir olmak üzere) ve hedefe en ucuz yolunun maliyetinden daha asla büyük olması sağlanır eğer bir sezgisel geçersiz olacaktır.

Öncülleri ve Ardıllar

Başlangıç ve hedef düğüm hariç olmak üzere, her bir düğüm $n$ sahiptir öncülleri ve ardılları :

Bir kenar doğru neden olan herhangi bir düğüm $n$ öncülüdür $n$ .
Bir kenar ile ilgili yol açan herhangi bir düğüm $n$ bir ardılları olan $n$ .

Aşağıdaki açıklamada, bu iki terimin sadece atıfta hemen öncülleri ve ardılları, değil öncülleri veya halefleri halefleri öncekilerden için.

Mesafe Tahminleri Başlangıç

LPA * başlangıç mesafesi iki tahminleri tutar $g * (n)$ her bir düğüm için:

$g (n)$ , daha önce hesaplanan g-değeri, olduğu gibi (mesafe başlangıç) *
$RHS (n)$ , düğümün önceki g-değerleri üzerine bir ileri yönlü değeri (her minimum $g (n ') + d (n', n)$ , $n',$ öncülüdür $n$ ve $d (x, y)$ kenar maliyeti bağlayan bir $x$ ve $y$ )

başlangıç düğümü, aşağıdaki daima geçerlidir:

{\ Displaystyle rhs'si (başlangıç) = gr (başlangıç) = 0}

Eğer $rhs'si (n)$ eşittir $g (n)$ , daha sonra $n$ denir lokal tutarlı . Bütün düğümler yerel tutarlı ise, o zaman bir kısa yol A * olduğu gibi belirlenebilir. Kenar maliyetleri değiştirmek Ancak, yerel tutarlılık rota alakalı bu düğümler için sadece yeniden tesis edilmesi gerekmektedir.

Öncelik Sırası

Bir düğüm (selefi veya daha önceki bir bağlayarak kenarının maliyeti değiştiği için) yerel olarak tutarsız olduğu zaman, bu bir yerleştirilir öncelik sırasına yeniden değerlendirilmesi için. LPA * iki boyutlu bir anahtar kullanır:

{\ Displaystyle k (n) = {\ başlar {bmatrix} k_ {1}, (n) \\ k_ {2} (n) \\\ uç {bmatrix}} = {\ başlar {bmatrix} dakika (g (n ) n RHS ()) + n h (hedef) \\ dakika (g (n), sağ tarafta (n)) \\\ uç {bmatrix}}}

Girişler göre sıralanır $k 1$ ile, sonra, (A * kullanılan ön-değerlerine doğrudan tekabül eder) $k 2$ .

Düğüm Genişleme

aşağıdaki gibi sıraya üst düğüm genişletilir:

Bir düğüm rhs'si-değeri g-değerine eşit ise, düğüm lokal tutarlıdır ve sıra kaldırılır.
Bir düğüm rhs'si-değeri g-değerine (bilinen daha az ise yerel overconsistent düğüm), g-değeri düğüm lokal tutarlı olacak RHS-değeri ile eşleştirmek için değiştirilir. Düğüm kuyruktan kaldırılır.
Bir düğüm rhs'si-değeri, (a olarak bilinen g-değerinden daha büyük olduğu takdirde , yerel olarak underconsistent düğüm), g-değeri (yerel overconsistent ya da lokal olarak, tutarlı ya düğüm kılan) sonsuz ayarlanır. Düğüm sonra lokal olarak tutarlı ise, başka anahtar güncellenir, kuyruğundan kaldırılır.

Ayrıca (ve böylece yerel kıvam) ardıllarıyla rhs'si-değerleri değişebilir bir düğüm g değerini değiştirmek için, değerlendirildikleri ve gerekirse sıra üyelik ve anahtar güncellenir.

İki koşullar kadar düğüm Genişleme sırasının en üstündeki düğüm ile devam eder:

Amaç yerel tutarlı ve
öncelik sırası en az bir düğüm ya da daha büyük bir hedef için anahtar eşit olan bir anahtar vardır.

İlk Çalıştırma

Grafik 0 başlangıç düğüm rhs'si-değeri ve sonsuza G-değeri ayarlanarak başlatılır. Diğer tüm düğümler için, G-değeri RHS-değeri, hem aksi tahsis kadar sonsuz olduğu varsayılır. Bu başlangıçta böylece başlangıç düğümü yalnızca yerel olarak tutarsız düğümü ve kuyrukta sadece düğüm yapar. Bundan sonra düğüm genişleme başlar. LPA'nın ilk çalıştırma * Bu şekilde aynı sırada aynı düğümleri genişleyen, A * aynı şekilde davranır.

Maliyet değişiklikler

bir kenar değişikliklerin maliyet LPA * değişimden etkilenen tüm düğümlerin, bir kenar, her iki yönde de geçtiği ve değişim, her iki yön etkiler olabilir halinde değişmiş kenarları sonlanıncaya biri (her iki düğüm de bağlı olan en yani tüm düğümlerin incelediğinde kenar) incelenir:

düğümler rhs'si değerleri güncellenir.
Yerel olarak tutarlı hale gelmiştir Düğümler kuyruğundan kaldırılır.
Yerel olarak tutarsız hale gelmiştir Düğümler kuyruğa eklenir.
Yerel olarak tutarsız kalır Düğümler kendi tuşları olarak güncellenmiştir.

son durum ulaşıldı kadar Bundan sonra düğüm genişleme devam eder.

En Kısa Yol Bulma

Düğüm genişleme (çıkış koşulları karşılandığında, yani) bittikten sonra, en kısa yol değerlendirilir. hedef için maliyet sonsuz eşitse, baştan hedefe hiçbir sonlu maliyetli yolu yoktur. Aksi takdirde, kısa yol geriye doğru hareket ile belirlenebilir:

gol başlayın.
Önceki taşı $n$ 'mevcut düğümün $N$ olan $g (n') + d (n', n)$ en düşük puan birden çok düğüm tarafından paylaşılıyorsa, her bir geçerli bir çözümdür ve bunların herhangi biri olabilir (en düşük olduğu ) isteğe bağlı olarak seçilmiş.
Eğer başlangıç ulaşana kadar önceki adımı yineleyin.

pseudocode

Bu kod, bir öncelik sırası varsayar queueaşağıdaki işlemleri destekler:

topKey() sıraya herhangi bir düğümün (sayısal) en düşük önceliğe döner (ya da sonsuz sıra boşsa)
pop() kuyruktan en düşük önceliğe sahip düğüm kaldırır ve geri gönderir
insert(node, priority) sıraya belirli bir önceliğe sahip bir düğüm ekler
remove(node) kuyruktan bir düğüm kaldırır
contains(node) Sıra değilse yanlış Belirtilen düğüm içeriyorsa true döndürür

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

Özellikleri

A * algoritmik benzer olan binanın pek çok özelliğine LPA * paylaşır.

Her düğüm genişletilir * LPA'nın Her geçiş için en iki kez (ziyaret). Yerel overconsistent düğümler ve böylece ilk çalıştırma (ki burada her bir düğüm overconsistent durumuna girer) en fazla bir kere, her düğüm ziyaret A *, benzer bir performansa sahiptir, en fazla bir kere LPA * işlem başına genişletilir.
Bir * ile olduğu gibi her çalışma için genişletilmiş düğümlerin anahtarları monotonik, zamanla azalmayan edilir.
(Hala kabul edilebilirlik kriterleri karşılarken) daha bilinçli (ve dolayısıyla daha büyük) sezgisel olan, daha az düğümleri genişletilmesi gerekmektedir.
Öncelikli kuyruk uygulaması A * olduğu gibi performansı üzerinde önemli bir etkisi vardır. Bir Kullanarak Fibonacci yığın az verimli uygulamaları üzerinde önemli bir performans artışına yol açabilir.

(A * iyi tanımlanmış değildir) daha küçük bir G-değeri ile düğümün lehine eşit f-değeri, iki düğüm arasındaki bağları parçalayan bir A * uygulanması için, aşağıdaki ifadeler de doğrudur:

lokal overconsistent düğümleri genişletilmiş sırası A * ile aynıdır.
Tüm yerel overconsistent düğümleri, yalnızca, maliyeti, bu A * olduğu gibi hedefi olduğunu, genişletilmesi gereken aşmıyor.

LPA * ek olarak aşağıdaki özelliklere sahiptir:

Kenar maliyetleri değiştiğinde, LPA * düğümleri yeniden genişletilmesi gerekmektedir A * olarak yalnızca bir kısmını (ikinci varsayarak sıfırdan çalıştırılan) daha üstündür.

Varyantlar

D * Lite , bir reimplementation D * LPA dayalı algoritma *

Languages

In other projects