Planowanie na całe życie A*

Klasa	Algorytm wyszukiwania
Struktura danych	Wykres

LPA* lub Lifelong Planning A* to przyrostowy algorytm wyszukiwania heurystycznego oparty na A* . Po raz pierwszy została opisana przez Svena Koeniga i Maxima Lichaczowa w 2001 roku.

Opis

LPA* to przyrostowa wersja A*, która może dostosowywać się do zmian na wykresie bez ponownego obliczania całego wykresu, aktualizując wartości g (odległość od początku) z poprzedniego wyszukiwania podczas bieżącego wyszukiwania, aby w razie potrzeby je poprawić. Podobnie jak A*, LPA* wykorzystuje heurystykę, która jest dolną granicą kosztu ścieżki od danego węzła do celu. Heurystyka jest dopuszczalna, jeśli gwarantuje się, że nie jest ujemna (dopuszczalne jest zero) i nigdy nie jest większa niż koszt najtańszej ścieżki do celu.

Poprzednicy i następcy

Z wyjątkiem węzła początkowego i docelowego, każdy węzeł n ma poprzedników i następców :

• Każdy węzeł, z którego krawędź prowadzi do n, jest poprzednikiem n .
• Każdy węzeł, do którego prowadzi krawędź od n, jest następcą n .

W poniższym opisie te dwa terminy odnoszą się tylko do bezpośrednich poprzedników i następców, a nie do poprzedników poprzedników lub następców następców.

Rozpocznij szacowanie odległości

LPA* utrzymuje dwa oszacowania odległości początkowej g *( n ) dla każdego węzła:

• g ( n ) , wcześniej obliczona wartość g (odległość początkowa) jak w A*
• rhs ( n ) , wartość wyprzedzająca oparta na wartościach g poprzedników węzła (minimum wszystkich g ( n' ) + d ( n' , n ) , gdzie n' jest poprzednikiem n i d ( x , y ) to koszt krawędzi łączącej x i y )

Dla węzła początkowego zawsze obowiązuje następujący warunek:

${\ Displaystyle rhs (początek) = g (początek) = 0}$

Jeśli rhs ( n ) jest równe g ( n ) , to n nazywamy spójnym lokalnie . Jeśli wszystkie węzły są lokalnie spójne, to najkrótszą ścieżkę można wyznaczyć jak w przypadku A*. Jednakże, gdy zmieniają się koszty brzegowe, spójność lokalna musi zostać przywrócona tylko dla tych węzłów, które są istotne dla trasy.

Kolejka priorytetowa

Kiedy węzeł staje się lokalnie niespójny (ponieważ zmienił się koszt jego poprzednika lub krawędź łącząca go z poprzednikiem), jest umieszczany w kolejce priorytetowej do ponownej oceny. LPA* wykorzystuje klucz dwuwymiarowy:

${\ Displaystyle k (n) = {\ rozpocząć {bmatrix} k_ {1} (n) \\ k_ {2} (n) \\\ koniec {bmatrix}} = {\ początek{bmacierz}min(g(n),prawa os(n))+h(n,cel)\\min(g(n),prawa os(n))\\\koniec{bmacierz}}}$

Wpisy są uporządkowane według k1 _według (co odpowiada bezpośrednio wartościom f użytym w A*), a k2 _następnie .

Rozbudowa węzła

Górny węzeł w kolejce jest rozwijany w następujący sposób:

• Jeśli wartość rhs węzła jest równa jego wartości g, węzeł jest lokalnie spójny i jest usuwany z kolejki.
• Jeśli wartość rhs węzła jest mniejsza niż jego wartość g (znana jako węzeł lokalnie nadmiernie spójny ), wartość g jest zmieniana w celu dopasowania do wartości rhs, dzięki czemu węzeł jest lokalnie spójny. Węzeł jest następnie usuwany z kolejki.
• Jeśli wartość rhs węzła jest większa niż jego wartość g (znana jako węzeł lokalnie niespójny ), wartość g jest ustawiana na nieskończoność (co powoduje, że węzeł jest lokalnie nadmiernie spójny lub lokalnie spójny). Jeśli węzeł jest wtedy spójny lokalnie, jest usuwany z kolejki, w przeciwnym razie jego klucz jest aktualizowany.

Ponieważ zmiana wartości g węzła może również zmienić wartości rhs jego następców (a tym samym ich lokalną spójność), są one oceniane, a ich członkostwo w kolejce i klucz są aktualizowane, jeśli to konieczne.

Rozszerzanie węzłów jest kontynuowane z następnym węzłem na górze kolejki, dopóki nie zostaną spełnione dwa warunki:

• Cel jest lokalnie spójny i
• Węzeł na górze kolejki priorytetów ma klucz większy lub równy kluczowi celu.

Uruchomienie początkowe

Wykres jest inicjowany przez ustawienie wartości rhs węzła początkowego na 0 i jego wartości g na nieskończoność. Dla wszystkich innych węzłów zakłada się, że zarówno wartość g, jak i wartość rhs są nieskończone, dopóki nie zostanie przypisane inaczej. To początkowo sprawia, że ​​węzeł początkowy jest jedynym węzłem niespójnym lokalnie, a tym samym jedynym węzłem w kolejce. Następnie rozpoczyna się ekspansja węzła. Pierwsze uruchomienie LPA* zachowuje się zatem w taki sam sposób jak A*, rozszerzając te same węzły w tej samej kolejności.

Zmiany kosztów

Kiedy zmienia się koszt krawędzi, LPA* sprawdza wszystkie węzły, na które zmiana ma wpływ, tj. wszystkie węzły, w których kończy się jedna ze zmienionych krawędzi (jeśli krawędź może być przebyta w obu kierunkach i zmiana dotyczy obu kierunków, oba węzły są połączone krawędź jest badana):

• Wartości rhs węzłów są aktualizowane.
• Węzły, które stały się lokalnie spójne, są usuwane z kolejki.
• Węzły, które stały się lokalnie niespójne, są dodawane do kolejki.
• Węzły, które pozostają lokalnie niespójne, mają zaktualizowane klucze.

Następnie rozszerzanie węzła jest wznawiane, aż do osiągnięcia warunku końcowego.

Znalezienie najkrótszej ścieżki

Po zakończeniu rozszerzania węzła (tj. spełnieniu warunków wyjścia) oceniana jest najkrótsza ścieżka. Jeśli koszt celu jest równy nieskończoności, nie ma ścieżki o skończonych kosztach od początku do celu. W przeciwnym razie najkrótszą ścieżkę można określić, cofając się:

• Zacznij od celu.
• Przejdź do poprzednika n' bieżącego węzła n , dla którego g ( n' ) + d ( n' , n ) jest najniższe (jeśli najniższy wynik jest wspólny dla wielu węzłów, każdy jest poprawnym rozwiązaniem i każdy z nich może być wybrany arbitralnie).
• Powtarzaj poprzedni krok, aż dojdziesz do początku.

Pseudo kod

Ten kod zakłada kolejkę priorytetową , która obsługuje następujące operacje:

• topKey() zwraca (liczbowo) najniższy priorytet dowolnego węzła w kolejce (lub nieskończoność, jeśli kolejka jest pusta)
• pop() usuwa węzeł o najniższym priorytecie z kolejki i zwraca go
• insert(węzeł, priorytet) wstawia do kolejki węzeł o zadanym priorytecie
• remove(node) usuwa węzeł z kolejki
• zawiera (węzeł) zwraca wartość true, jeśli kolejka zawiera określony węzeł, wartość false, jeśli nie

  
  
    
    
     
      
        
        
        
    
   unieważnić  główny  ()  {  zainicjować  ();  while  (  prawda  )  {  oblicz najkrótszą ścieżkę  ();  while  (  !  hasCostChanges  ())  sleep  ;  for  (  krawędź  :  getChangedEdges  ())  {  krawędź  .  setCost  (  pobierzNowyKoszt  (  krawędź  ));  updateNode  (  krawędź  .  endNode  );  }  } 


  
     
      
      
      
  
    0
    }  unieważnić  inicjowanie  ()  {  kolejka  =  nowa  kolejka priorytetowa  ();  for  (  węzeł  :  getAllNodes  ())  {  węzeł  .  g  =  NIESKOŃCZONOŚĆ  ;  węzeł  .  rhs  =  NIESKOŃCZONOŚĆ  ;  }  zacznij  .  rhs  =  ;  kolejka  .  wstaw  (  start  ,  obliczKlucz  (  start  )); 



  
          
      
        }  /** Rozwija węzły w kolejce priorytetowej. */   void  computeShortestPath  ()  {  while  ((  kolejka  .  getTopKey  ()  <  obliczKlucz  (  cel  ))  ||  (  cel  .  rhs  ! =  cel  .  g  ))  {  węzeł  =  kolejka  .  pop  ();  if  (  węzeł  .  g  >  węzeł  .  rhs  
        
      
        
      
    
       
      
  


 )  {  węzeł  .  g  =  węzeł  .  prawa strona  ;  }  inny  {  węzeł  .  g  =  NIESKOŃCZONOŚĆ  ;  updateNode  (  węzeł  );  }  for  (  następnik  :  węzeł  .  getSuccessors  ())  updateNode  (  następnik  );  }  }  /** Przelicza rhs dla węzła i usuwa go z kolejki. 

  
      
      
      
          * Jeśli węzeł stał się lokalnie niespójny, jest (ponownie) wstawiany do kolejki z nowym kluczem. */   void  updateNode  (  węzeł  )  {  if  (  węzeł  !=  start  )  {  węzeł  .  rhs  =  NIESKOŃCZONOŚĆ  ;  for  (  poprzednik  :  węzeł  .  getPredecessors  ())  węzeł  .  rhs  =  min  (  węzeł  .  rhs  ,  poprzednik   
     
      
       
       
  


 .  g  +  poprzednik  .  getCostTo  (  węzeł  ));  if  (  kolejka  .  zawiera  (  węzeł  ))  kolejka  .  usunąć  (  węzeł  );  if  (  węzeł  .  g  !=  węzeł  .  rhs  )  kolejka  .  wstaw  (  węzeł  ,  obliczKlucz  (  węzeł  ));  }  }  wewn   
        
 []  obliczKlucz  (  węzeł  )  {  return  {  min  (  węzeł  .  g  ,  węzeł  .  rhs  )  +  węzeł  .  getHeuristic  (  cel  ),  min  (  węzeł  .  g  ,  węzeł  .  rhs  )};  } 

Nieruchomości

Będąc algorytmicznie podobnym do A*, LPA* ma wiele wspólnych właściwości.

• Każdy węzeł jest rozszerzany (odwiedzany) co najwyżej dwa razy dla każdego przebiegu LPA*. Lokalnie nadmiernie spójne węzły są rozwijane co najwyżej raz na uruchomienie LPA*, dlatego jego początkowe uruchomienie (w którym każdy węzeł wchodzi w stan nadmiernej spójności) ma podobną wydajność do A*, która odwiedza każdy węzeł co najwyżej raz.
• Klucze węzłów rozwiniętych dla każdego przebiegu są monotonicznie niemalejące w czasie, jak ma to miejsce w przypadku A*.
• Im bardziej poinformowane (a tym samym większe) są heurystyki (wciąż spełniające kryteria dopuszczalności), tym mniej węzłów trzeba rozszerzyć.
• Implementacja kolejki priorytetowej ma znaczący wpływ na wydajność, podobnie jak w A*. Korzystanie ze stosu Fibonacciego może prowadzić do znacznego wzrostu wydajności w porównaniu z mniej wydajnymi implementacjami.

W przypadku implementacji A*, która zrywa powiązania między dwoma węzłami o równych wartościach f na korzyść węzła o mniejszej wartości g (który nie jest dobrze zdefiniowany w A*), prawdziwe są również następujące stwierdzenia:

• Kolejność, w jakiej rozwijane są lokalnie nadmiernie spójne węzły, jest identyczna jak w A*.
• Spośród wszystkich węzłów nadmiernie spójnych lokalnie tylko te, których koszt nie przekracza kosztu celu, muszą zostać rozszerzone, tak jak ma to miejsce w przypadku A*.

LPA* posiada dodatkowo następujące właściwości:

• Kiedy zmieniają się koszty brzegowe, LPA* przewyższa A* (zakładając, że ten ostatni jest uruchamiany od zera), ponieważ tylko ułamek węzłów wymaga ponownej rozbudowy.

Warianty

• D* Lite , reimplementacja algorytmu D* opartego na LPA*