Planificación a lo Largo de la Vida A* - Enciclopedia

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.

Descripción
LPA* es una versión incremental de A*, que puede adaptarse a los cambios en el grafo sin recalcular todo el grafo, actualizando los valores de g (distancia desde el inicio) de la búsqueda anterior durante la búsqueda actual para corregirlos cuando es necesario. Al igual que A*, LPA* utiliza una heurística, que es una barrera inferior para el costo del camino desde un nodo dado al objetivo. Una heurística es admisible si se garantiza que sea no negativa (cero es admisible) y nunca mayor que el costo del camino más económico al objetivo.

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

Cualquier nodo desde el que un arco conduce hacia n es un predecesor de n.
Cualquier nodo al que un arco conduce desde n es un sucesor de n.
En la siguiente descripción, estos dos términos solo se refieren a los predecesores y sucesores inmediatos, no a los predecesores de los predecesores o los sucesores de los sucesores.

= Estimaciones de distancia de inicio =
LPA* mantiene dos estimaciones de la distancia de inicio g*(n) para cada nodo:

g(n), el valor de g previamente calculado (distancia de inicio) como en A*
rhs(n), un valor de mirada adelantada basado en los valores de g del nodo de sus predecesores (el mínimo de todos g(n' ) + d(n' , n), donde n' es un predecesor de n y d(x, y) es el costo del arco que conecta x y y)
Para el nodo de inicio, lo siguiente siempre es cierto:


r
h
s
(
s
t
a
r
t
)
=
g
(
s
t
a
r
t
)
=
0


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


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

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


k
(
n
)
=

[


k

1

(
n
)


k

2

(
n
)

]


=

[


min
(
g
(
n
)
,
r
h
s
(
n
)
)
+
h
(
n
,
g
o
a
l
)


min
(
g
(
n
)
,
r
h
s
(
n
)
)

]


{\displaystyle 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 se ordenan por k1 (que corresponde directamente a los valores de f utilizados en A*), luego por k2.

= Expansión de nodos =
El nodo más alto en la cola se expande de la siguiente manera:

Si el valor de rhs de un nodo es igual a su valor de g, el nodo es localmente consistente y se elimina de la cola.
Si el valor de rhs de un nodo es menor que su valor de g (conocido como un nodo localmente superconsistente), se cambia el valor de g para que coincida con el valor de rhs, haciendo que el nodo sea localmente consistente. El nodo se elimina entonces de la cola.
Si el valor de rhs de un nodo es mayor que su valor de g (conocido como un nodo localmente subconsistente), se establece el valor de g en infinito (lo que hace que el nodo sea localmente superconsistente o localmente consistente). Si el nodo es luego localmente consistente, se elimina de la cola, de lo contrario se actualiza su clave.
Como cambiar el valor de g de un nodo también puede cambiar los valores de rhs de sus sucesores (y por lo tanto su consistencia local), se evalúan y se actualiza su membresía en la cola y su clave 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 localmente consistente, y
El nodo en la parte superior de la cola de prioridad tiene una clave que es mayor o igual que la clave para el objetivo.

= Ejecución inicial =
El grafo se inicializa estableciendo el valor de rhs del nodo de inicio en 0 y su valor de g en infinito. Para todos los demás nodos, tanto el valor de g como el valor de rhs se asumen que son infinito hasta que se asignen de otra manera. Esto 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 de nodos. La primera ejecución de LPA* tiene el mismo comportamiento que A*, expandiendo los mismos nodos en el mismo orden.

= Cambios en el costo =
Cuando cambia el costo de un arco, LPA* examina todos los nodos afectados por el cambio, es decir, todos los nodos en los que uno de los arcos cambiados termina (si un arco se puede transitar en ambas direcciones y el cambio afecta ambas direcciones, se examinan ambos nodos conectados por el arco):

Se actualizan los valores de rhs de los nodos.
Se eliminan de la cola los nodos que se han convertido en localmente consistentes.
Se agregan a la cola los nodos que se han convertido en localmente inconsistentes.
Se actualizan las claves de los nodos que permanecen localmente inconsistentes.
Después de eso, se reanuda la expansión de nodos hasta que se alcanza la condición de finalización.

= Encontrar la trayectoria más corta =
Una vez finalizada la expansión de nodos (es decir, se cumplen las condiciones de salida), se evalúa la trayectoria más corta. Si el costo para el objetivo es infinito, no hay una trayectoria de costo finito desde el inicio al objetivo. En caso contrario, se puede determinar la trayectoria más corta moviéndose hacia atrás:

Comienza en el objetivo.
Se mueve al predecesor n' del nodo actual n para el que g(n' ) + d(n' , n) es más bajo (si el puntaje más bajo es compartido por múltiples nodos, cada uno es una solución válida y cualquier uno puede ser elegido arbitrariamente).
Se repite el paso anterior hasta llegar al inicio.

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 dada en la cola
remove(node) elimina un nodo de la cola
contains(node) devuelve true si la cola contiene el nodo especificado, false si no

Propiedades
Dado que el algoritmo es similar al 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 localmente superconsistentes se expanden como máximo una vez por ejecución de LPA*, por lo que su ejecución inicial (en la que todos los nodos entran en el estado de superconsistencia) tiene un rendimiento similar al de A*, que visita cada nodo como máximo una vez.
Las claves de los nodos expandidos para cada ejecución son no decrecientes monótonamente con el tiempo, como en A*.
Cuanto más informada (y por lo tanto mayor) sea la heurística (siempre y cuando satisfaga los criterios de admisibilidad), menor es la cantidad de nodos que necesita expandirse.
La implementación de la cola de prioridad tiene un impacto significativo en el rendimiento, al igual que en A*. El uso de un Fibonacci heap puede llevar a un aumento significativo en el rendimiento en comparación con implementaciones menos eficientes.
Para una implementación de A* que resuelve empates entre dos nodos con valores de f iguales a favor del nodo con el valor de g más pequeño (lo que no está bien definido en A*), las siguientes afirmaciones también son verdaderas:

El orden en que se expanden los nodos localmente superconsistentes es idéntico al de A*.
De todos los nodos localmente superconsistentes, solo aquellos cuyo costo no excede el del objetivo necesitan expandirse, como en A*.
LPA* tiene las siguientes propiedades adicionales:

Cuando cambian los costos de los arcos, LPA* tiene un rendimiento superior al de A* (asumiendo que el último se ejecuta desde cero) ya que solo una fracción de los nodos necesita volver a expandirse.

Variantes
D* Lite, una reimplementación del algoritmo D* basada en LPA*

Referencias