D*

De Wikipedia, la enciclopedia libre

D* (pronunciado "D estrella") es uno de los siguientes tres algoritmos de búsqueda incremental:

  • El D* original,[1]​ por Anthony Stentz, es un algoritmo de búsqueda incremental informada.
  • D* Enfocado[2]​ es un algoritmo heurístico de búsqueda incremental informada creado por Anthony Stentz que combina ideas de A*[3]​ y el D* original. D* Enfocado es el resultado de un desarrollo adicional de D* original.
  • D* Lite[4]​ es un algoritmo heurístico de búsqueda incremental creado por Sven Koenig y Maxim Likhachev que se basa en LPA*,[5]​ combina ideas de A* y Dynamic SWSF-FP.[6]​

Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de ruta basada en la suposición, incluyendo la planificación con la suposición de espacio libre,[7]​ donde un robot tiene que navegar hasta las coordenadas de un objetivo dado en un terreno desconocido. Hace suposiciones sobre la parte desconocida del terreno (por ejemplo: que no contiene obstáculos) y encuentra un camino más corto desde sus coordenadas actuales hasta la meta bajo estas suposiciones. El robot entonces sigue el camino. Cuando se observa nueva información del mapa (como obstáculos previamente desconocidos), se añade la información a su mapa y, si es necesario, planea el nuevo camino más corto a partir de sus coordenadas actuales a las coordenadas del objetivo determinado. Se repite el proceso hasta que llega a las coordenadas del objetivo o determina que no se puede llegar a las coordenadas del objetivo. Al atravesar terrenos desconocidos, nuevos obstáculos se pueden descubrir con frecuencia, por lo que esta nueva planificación tiene que ser rápida. Los algorítmos de búsqueda (heurística) incremental aceleran las búsquedas de secuencias de problemas de búsqueda similares mediante el uso de la experiencia con los problemas anteriores para acelerar la búsqueda de la actual. Suponiendo que las coordenadas del objetivo no cambian, los tres algoritmos de búsqueda son más eficientes que las reiteradas búsquedas A*.

D* y sus variantes han sido ampliamente utilizados para robots móviles y navegación de vehículos autónomos. Los sistemas actuales se basan normalmente en D* Lite en lugar del D* original o D* Enfocado. De hecho, incluso el laboratorio de Stentz utiliza D* Lite en lugar de D* en algunas implementaciones.[8]​ Tales sistemas de navegación incluyen un sistema prototipo probado en Marte en los astromóviles Opportunity y Spirit y en el sistema de navegación de la obra ganadora en el DARPA Urban Challenge, todos desarrollados en la Carnegie Mellon University.

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada.
Busca fuentes: «D*» – noticias · libros · académico · imágenes
Este aviso fue puesto el 19 de diciembre de 2014.

El D* original fue presentado por Anthony Stentz en 1994. El nombre de D* viene del término "Dynamic A*", ya que el algoritmo se comporta como A* excepto que los costos de los arcos pueden cambiar a medida que se ejecuta el algoritmo.

Funcionamiento[editar]

El funcionamiento básico de D* se describe a continuación.

Al igual que el algoritmo de Dijkstra y A*, D* mantiene una lista de nodos para ser evaluados, conocida como la "lista abierta". Los nodos están marcados por tener uno de varios estados:

  • NUEVO, lo que significa que nunca ha sido colocado en la lista abierta
  • ABIERTO, lo que significa que se encuentra actualmente en la lista abierta
  • CERRADO, lo que significa que ya no está en la lista abierta
  • SUPERIOR, indicando su coste es más alto que la última vez que estaba en la lista abierta
  • INFERIOR, indicando su costo es menor que la última vez que estaba en la lista abierta

Expansión[editar]

El algoritmo funciona mediante la selección iterativa de un nodo de la lista abierta y evaluándolo. A continuación, propaga los cambios del nodo a todos los nodos vecinos y los coloca en la lista abierta. Este proceso de propagación se denomina "expansión". A diferencia de A*, que sigue el camino de principio a fin, D* comienza por buscar hacia atrás desde el nodo objetivo. Cada nodo expandido tiene un backpointer que se refiere al siguiente nodo que conduce al objetivo, y cada nodo conoce el costo exacto al objetivo. Cuando el nodo de partida es el siguiente nodo a expandirse, el algoritmo para, y el camino hacia la meta se puede encontrar, simplemente siguiendo los backpointers.

Manejo de obstáculos[editar]

Cuando se detecta una obstrucción a lo largo de la trayectoria prevista, todos los puntos que se ven afectados se colocan de nuevo en la lista abierta, esta vez marcados a SUPERIOR. Antes de marcarlos a SUPERIOR se aumenta los costos, sin embargo, el algoritmo comprueba sus vecinos y examina si se puede reducir el costo del nodo. Si no, el estado SUPERIOR se propaga a todos los descendientes de los nodos, es decir, los nodos que tienen backpointers a ella. Estos nodos se evalúan entonces, y el estado SUPERIOR se transmite, formando una onda. Cuando un nodo SUPERIOR se puede reducir, su backpointer se actualiza y pasa al estado LOWER a sus vecinos. Estas ondas de estados SUPERIOR y LOWER son el corazón de D*.

En este momento, se evita que una serie de otros puntos sean "tocados" por las ondas. El algoritmo, por tanto, solo ha trabajado en los puntos que se ven afectados por el cambio de los costos.

Ocurrencia de algún deadlock[editar]

Esta vez, el deadlock no puede anularse con tanta elegancia. Desde ninguno de los puntos se puede encontrar una nueva ruta a través de un vecino para el destino, por lo tanto, ellos siguen propagando su aumento de costos. Solo fuera del canal se pueden encontrar puntos, que pueden llevar al destino a través de una ruta viable. Esto trata de cómo se desarrollan dos ondas LOWER, que expanden puntos marcados inalcanzables con nueva información de la ruta.

D* Enfocado[editar]

Como su nombre indica, D* Enfocado es una extensión de D* que utiliza una heurística para enfocar la propagación de SUPERIOR e INFERIOR hacia el robot. De esta manera, solo los estados que importan son actualizados, de la misma manera que A* solo calcula los costos para algunos de los nodos.

D* Lite[editar]

D * Lite no se basa en el D* original o D* Enfocado, pero implementa el mismo comportamiento. Es más fácil de entender y se puede implementar en un menor número de líneas de código, de ahí el nombre de "D* Lite". En cuanto al rendimiento, es tan bueno o mejor que D* Enfocado. D* Lite se basa en Lifelong Planning A*, que fue presentado por Koenig y Likhachev unos años antes. D* Lite

Costo mínimo contra costo actual[editar]

Para D *, es importante distinguir entre los costos actuales y costos mínimos. El primero es solo importante en el momento de la recolección y el último es fundamental, ya que ordena la lista abierta. La función que devuelve el costo mínimo es siempre el menor costo para el punto actual, ya que es la primera entrada de la lista abierta.

Referencias[editar]

  1. ↑ Stentz, Anthony (1994), «Optimal and Efficient Path Planning for Partially-Known Environments», Proceedings of the International Conference on Robotics and Automation: 3310-3317 . }}
  2. ↑ Stentz, Anthony (1995), «The Focussed D* Algorithm for Real-Time Replanning», Proceedings of the International Joint Conference on Artificial Intelligence: 1652-1659 .
  3. ↑ Hart, P.; Nilsson, N.; Raphael, B. (1968), «A Formal Basis for the Heuristic Determination of Minimum Cost Paths», IEEE Trans. Syst. Science and Cybernetics, SSC-4 (2): 100-107 .
  4. ↑ Koenig, S.; Likhachev, M. (2005), «Fast Replanning for Navigation in Unknown Terrain», Transactions on Robotics 21 (3): 354-363, doi:10.1109/tro.2004.838026 .
  5. ↑ Koenig, S.; Likhachev, M.; Furcy, D. (2004), «Lifelong Planning A*», Artificial Intelligence Journal 155 (1–2): 93-146, doi:10.1016/j.artint.2003.12.001 .
  6. ↑ Ramalingam, G.; Reps, T. (1996), «An incremental algorithm for a generalization of the shortest-path problem», Journal of Algorithms 21: 267-305, doi:10.1006/jagm.1996.0046 .
  7. ↑ Koenig, S.; Smirnov, Y.; Tovey, C. (2003), «Performance Bounds for Planning in Unknown Terrain», Artificial Intelligence Journal 147 (1–2): 253-279, doi:10.1016/s0004-3702(03)00062-6 .
  8. ↑ Wooden, D. (2006). Graph-based Path Planning for Mobile Robots (Tesis). Georgia Institute of Technology. 

Enlaces externos[editar]


Obtenido de «https://es.wikipedia.org/w/index.php?title=D*&oldid=159847385»