Planificación de por vida A *

Clase	Algoritmo de búsqueda
Estructura de datos	Grafico

Algoritmos de búsqueda de gráficos y árboles
α – β A* B* Retroceso Haz Bellman – Ford Mejor primero Bidireccional Borůvka Rama y encuadernado BFS Museo Británico D* DFS Dijkstra Edmonds Floyd – Warshall Búsqueda de franjas Montañismo IDA * Profundización iterativa Johnson Punto de salto Kruskal BFS lexicográfico LPA * Remilgado SMA *
Listados
Algoritmos de grafos Algoritmos de búsqueda Lista de algoritmos de gráficos
Temas relacionados
Programación dinámica Recorrido del gráfico Cruce de árboles Buscar juegos Coloración gráfica
v t mi

LPA * o Lifelong Planning A * es un algoritmo de búsqueda heurística incremental basado en A * . Fue descrito por primera vez por Sven Koenig y Maxim Likhachev en 2001. ^[1]

Descripción

LPA * es una versión incremental de A *, que puede adaptarse a los cambios en el gráfico sin recalcular el gráfico completo, actualizando los valores g (distancia desde el inicio) de la búsqueda anterior durante la búsqueda actual para corregirlos cuando sea necesario. Al igual que A *, LPA * utiliza una heurística, que es un límite inferior para el costo de la ruta desde un nodo determinado hasta el objetivo. Una heurística es admisible si se garantiza que no será negativa (cero es admisible) y nunca mayor que el costo del camino más barato hacia la meta.

Predecesores y sucesores

Con la excepción del nodo de inicio y objetivo, cada nodo $n$ tiene predecesores y sucesores :

Cualquier nodo desde el que una arista conduzca hacia $n$ es un predecesor de $n$ .
Cualquier nodo al que una arista conduzca desde $n$ es un sucesor de $n$ .

En la siguiente descripción, estos dos términos se refieren únicamente a los predecesores y sucesores inmediatos , no a los predecesores de predecesores o sucesores de sucesores.

Iniciar estimaciones de distancia

LPA * mantiene dos estimaciones de la distancia inicial $g * (n)$ para cada nodo:

$g (n)$ , el valor g calculado previamente (distancia inicial) como en A *
$rhs (n)$ , un valor de búsqueda hacia delante en base a los valores g de predecesores del nodo (el mínimo de todos $g (n ') + d (n', n)$ , donde $n'$ es un predecesor de $n$ y $d (x, y)$ es el coste del borde de conexión $x$ y $y$ )

Para el nodo de inicio, lo siguiente siempre es válido:

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

Si $rhs (n)$ es igual a $g (n)$ , entonces $n$ se llama localmente consistente . Si todos los nodos son consistentes localmente, entonces se puede determinar una ruta más corta como con A *. Sin embargo, cuando los costos de borde cambian, la consistencia local debe restablecerse solo para aquellos nodos que son relevantes para la ruta.

Cola de prioridad

Cuando un nodo se vuelve localmente inconsistente (porque el costo de su predecesor o el borde que lo vincula a un predecesor ha cambiado), se coloca en una cola de prioridad para su reevaluación. LPA * utiliza una clave bidimensional:

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

Las entradas están ordenadas por $k 1$ (que corresponde directamente a los valores f usados en A *), luego por $k 2$ .

Expansión de nodo

El nodo superior de la cola se expande de la siguiente manera:

Si el valor rhs de un nodo es igual a su valor g, el nodo es localmente consistente y se elimina de la cola.
Si el valor rhs de un nodo es menor que su valor g (conocido como un nodo localmente superconsistente ), el valor g se cambia para que coincida con el valor rhs, haciendo que el nodo sea localmente coherente. Luego, el nodo se elimina de la cola.
Si el valor rhs de un nodo es mayor que su valor g (conocido como nodo localmente subconsistente ), el valor g se establece en infinito (lo que hace que el nodo sea localmente superconsistente o localmente consistente). Si el nodo es localmente coherente, se elimina de la cola; de lo contrario, se actualiza su clave.

Dado que cambiar el valor g de un nodo también puede cambiar los valores rhs de sus sucesores (y por lo tanto su consistencia local), se evalúan y su membresía de cola y clave se actualiza si es necesario.

La expansión de nodos continúa con el siguiente nodo en la parte superior de la cola hasta que se cumplen dos condiciones:

El objetivo es coherente a nivel local y
El nodo en la parte superior de la cola de prioridad tiene una clave que es mayor o igual que la clave del objetivo.

Ejecución inicial

El gráfico se inicializa estableciendo el valor rhs del nodo de inicio en 0 y su valor g en infinito. Para todos los demás nodos, se supone que tanto el valor g como el valor rhs son infinitos hasta que se asignen de otro modo. Esto inicialmente hace que el nodo de inicio sea el único nodo localmente inconsistente y, por lo tanto, el único nodo en la cola. Después de eso, comienza la expansión del nodo. La primera ejecución de LPA * se comporta de la misma manera que A *, expandiendo los mismos nodos en el mismo orden.

Cambios de costo

Cuando cambia el costo de un borde, LPA * examina todos los nodos afectados por el cambio, es decir, todos los nodos en los que termina uno de los bordes cambiados (si un borde puede atravesarse en ambas direcciones y el cambio afecta a ambas direcciones, ambos nodos están conectados por se examinan el borde):

Los valores rhs de los nodos se actualizan.
Los nodos que se han vuelto consistentes localmente se eliminan de la cola.
Los nodos que se han vuelto localmente inconsistentes se agregan a la cola.
Los nodos que siguen siendo localmente inconsistentes tienen sus claves actualizadas.

Después de eso, la expansión del nodo se reanuda hasta que se alcanza la condición final.

Encontrar el camino más corto

Una vez que la expansión del nodo ha finalizado (es decir, se cumplen las condiciones de salida), se evalúa la ruta más corta. Si el costo de la meta es infinito, no hay un camino de costo finito desde el principio hasta la meta. De lo contrario, el camino más corto se puede determinar retrocediendo:

Empiece por la meta.
Pasar al predecesor $n '$ del nodo actual $n$ para el cual $g (n') + d (n ', n)$ es el más bajo (si el puntaje más bajo es compartido por múltiples nodos, cada uno es una solución válida y cualquiera de ellos puede ser elegido arbitrariamente).
Repita el paso anterior hasta que haya llegado al inicio. ^[2]

Pseudocódigo

Este código asume una cola de prioridad queue, que admite las siguientes operaciones:

topKey() devuelve la prioridad más baja (numéricamente) de cualquier nodo en la cola (o infinito si la cola está vacía)
pop() elimina el nodo con la prioridad más baja de la cola y lo devuelve
insert(node, priority) inserta un nodo con una prioridad determinada en la cola
remove(node) elimina un nodo de la cola
contains(node) devuelve verdadero si la cola contiene el nodo especificado, falso si no

void  main ()  {  inicializar ();  while  ( verdadero )  {  computeShortestPath ();  while  ( ! hasCostChanges ())  sleep ;  para  ( borde  :  getChangedEdges ())  {  borde . setCost ( getNewCost ( borde ));  updateNode ( borde . endNode );  }  } }void  initialize ()  {  cola  =  new  PriorityQueue ();  para  ( nodo  :  getAllNodes ())  {  nodo . g  =  INFINITO ;  nodo . rhs  =  INFINITO ;  }  inicio . rhs  =  0 ;  cola . insertar ( iniciar ,  calcularClave ( inicio )); }/ ** Expande los nodos en la cola de prioridad. * / void  computeShortestPath ()  {  while  (( cola . getTopKey ()  <  calculateKey ( objetivo ))  ||  ( objetivo . rhs  ! =  objetivo . g ))  {  nodo  =  cola . pop ();  si  ( nodo . g  >  nodo . rhs )  {  nodo . g  =  nodo . rhs;  para  ( sucesor  :  nodo . getSuccessors ())  updateNode ( sucesor );  }  else  {  nodo . g  =  INFINITO ;  updateNode ( nodo );  para  ( sucesor  :  nodo . getSuccessors ())  updateNode ( sucesor );  }  } }/ ** Recalcula rhs para un nodo y lo elimina de la cola. * Si el nodo se ha vuelto localmente inconsistente, se (re) inserta en la cola con su nueva clave. * / void  updateNode ( nodo )  {  if  ( nodo  ! =  inicio )  {  nodo . rhs  =  INFINITO ;  para  ( predecesor :  nodo . getPredecessors ())  nodo . rhs  =  min ( nodo . rhs ,  predecesor . g  + predecesor . getCostTo ( nodo ));  if  ( cola . contiene ( nodo ))  cola . eliminar ( nodo );  if  ( nodo . g  ! =  nodo . rhs )  cola . insert ( nodo ,  calculateKey ( nodo ));  } }int []  calculateKey ( nodo )  {  retorno  { min ( nodo . g ,  nodo . rhs )  +  nodo . getHeuristic ( objetivo ),  min ( nodo . g ,  nodo . rhs )}; }

^[2]

Propiedades

Al ser algorítmicamente similar a A *, LPA * comparte muchas de sus propiedades.

Cada nodo se expande (visita) como máximo dos veces por cada ejecución de LPA *. Los nodos con sobreconsistencia local se expanden como máximo una vez por ejecución de LPA *, por lo que su ejecución inicial (en la que cada nodo entra en el estado de sobreconsistencia) tiene un rendimiento similar a A *, que visita cada nodo como máximo una vez.
Las claves de los nodos expandidos para cada ejecución no disminuyen monótonamente con el tiempo, como es el caso de A *.
Cuanto más informadas (y, por lo tanto, más grandes) sean las heurísticas (sin dejar de satisfacer los criterios de admisibilidad), menos nodos deben expandirse.
La implementación de la cola de prioridad tiene un impacto significativo en el rendimiento, como en A *. El uso de un montón de Fibonacci puede conducir a un aumento significativo del rendimiento en implementaciones menos eficientes.

Para una implementación A * que rompe los lazos entre dos nodos con valores f iguales a favor del nodo con el valor g más pequeño (que no está bien definido en A *), las siguientes afirmaciones también son verdaderas:

El orden en el que se expanden los nodos con sobreconsistencia local es idéntico a A *.
De todos los nodos con sobreconsistencia local, solo aquellos cuyo costo no exceda el de la meta deben expandirse, como es el caso de A *.

Además, LPA * tiene las siguientes propiedades:

Cuando los costos de borde cambian, LPA * supera a A * (asumiendo que este último se ejecuta desde cero) ya que solo una fracción de los nodos necesita expandirse nuevamente.

Variantes

D * Lite , una reimplementación del algoritmo D * basado en LPA * ^[3]

Referencias

^ Koenig, Sven; Likhachev, Maxim (2001), Incremental A * (PDF)
^ a b Koenig, Sven; Likhachev, Maxim (2002), D * Lite (PDF)
^ S. Koenig y M. Likhachev. Replanificación rápida para la navegación en terreno desconocido . Transactions on Robotics, 21, (3), 354-363, 2005.

[KoenigLikhachev2001-1] Koenig, Sven; Likhachev, Maxim (2001), Incremental A * (PDF)

[KoenigLikhachev2002-2] Koenig, Sven; Likhachev, Maxim (2002), D * Lite (PDF)

[KoenigLikhachev2005-3] S. Koenig y M. Likhachev. Replanificación rápida para la navegación en terreno desconocido . Transactions on Robotics, 21, (3), 354-363, 2005.

[1]