Hispanopedia Wiki
Articulo de referencia

Theta*

Theta* es un algoritmo de planificación de trayectorias para cualquier ángulo que se basa en el algoritmo de búsqueda A* . Puede encontrar trayectorias casi óptimas con tiempos ...

Hispanopedia WikiContenido en espanolLectura gratuita

Theta* es un algoritmo de planificación de trayectorias para cualquier ángulo que se basa en el algoritmo de búsqueda A* . Puede encontrar trayectorias casi óptimas con tiempos de ejecución comparables a los de A*. [ 1 ]

Descripción

Para la versión más simple de Theta*, el bucle principal es muy similar al de A*. La única diferencia es laactualizar_vértice(){\displaystyle {\text{actualizar}}\_{\text{vértice}}()}función. En comparación con A*, el padre de un nodo en Theta* no tiene que ser un vecino del nodo siempre que haya una línea de visión entre los dos nodos.

Pseudocódigo

Adaptado de. [ 2 ]

función theta * ( inicio , meta ) // Este bucle principal es el mismo que A* gScore ( inicio ) := 0 padre ( inicio ) := inicio // Inicializando conjuntos abiertos y cerrados. El conjunto abierto se inicializa // con el nodo de inicio y un costo inicial abierto := {} abierto . insertar ( inicio , gScore ( inicio ) + heurística ( inicio )) // gScore(nodo) es la distancia más corta actual desde el nodo de inicio al nodo // heurística(nodo) es la distancia estimada del nodo desde el nodo meta // hay muchas opciones para la heurística, como la euclidiana o la de Manhattan cerrado := {} mientras abierto no esté vacío s := abierto . pop () si s = meta devolver reconstruct_path ( s ) cerrado . push ( s ) para cada vecino de s // Recorre cada vecino inmediato de s si el vecino no está cerrado si el vecino no está abierto // Inicializa los valores para el vecino si no está // ya en la lista abierta gScore ( vecino ) := infinito padre ( vecino ) := Nulo update_vertex ( s , vecino ) devuelve Nulo función update_vertex ( s , vecino ) // Esta parte del algoritmo es la principal diferencia entre A* y Theta* si line_of_score ( padre ( s ) , vecino ) // Si hay línea de visión entre padre(s) y vecino // entonces ignora s y usa la ruta desde padre(s) hasta vecino si gScore ( padre ( s )) + c ( padre ( s )) , vecino ) < gScore ( vecino ) // c(s, vecino) es la distancia euclidiana de s a vecino gScore ( vecino ) := gScore ( padre ( s )) + c ( padre ( s ) , vecino ) padre ( vecino ) := padre ( s ) si vecino en abierto abrir . remove ( vecino ) abrir . insert ( vecino , gScore ( vecino ) + heurística ( vecino )) de lo contrario // Si la longitud del camino desde inicio a s y desde s a // vecino es más corta que la distancia más corta actualmente conocida // desde inicio a vecino, entonces actualiza el nodo con la nueva distancia si gScore ( s ) + c ( s , vecino ) < gScore ( vecino ) gScore ( vecino ) := gScore ( s ) + c ( s , vecino ) padre ( vecino ) := s si vecino en abierto abrir . remove ( vecino ) abrir . insertar ( vecino , gScore ( vecino ) + heurística ( vecino ))función reconstruct_path ( s ) total_path = {s} // Esto reconstruirá recursivamente la ruta desde el nodo objetivo // hasta que se alcance el nodo de inicio if parent ( s ) ! = s total_path . push ( reconstruct_path ( parent ( s ))) else return total_path

Algoritmo de línea de visión

líneaDeVisión ( nodo1 , nodo2 ) { let x0 = nodo1 . x ; let y0 = nodo1 . y ; let x1 = nodo2 . x ; let y1 = nodo2 . y ; let dx = abs ( x1 - x0 ); let dy = - abs ( y1 - y0 );sea ​​sX = - 1 ; sea ​​sY = - 1 ; si ( x0 < x1 ) { sX = 1 ; } si ( y0 < y1 ) { sY = 1 ; }let e = dx + dy ; while ( true ) { let point = getNode ( x0 , y0 ); if ( point does not exist OR point is not walkable ) { return false ; } if ( x0 == x1 AND y0 == y1 ) { return true ; } let e2 = 2 * e ; if ( e2 >= dy ) { if ( x0 == x1 ) { return true ; } e += dy ; x0 += sX ; } if ( e2 <= dx ) { if ( y0 == y1 ) { return true ; } e += dx ; y0 += sY ; } } }

Variantes

Existen las siguientes variantes del algoritmo:

  • Theta perezoso* [ 3 ] – Las expansiones de nodos se retrasan, lo que resulta en menos comprobaciones de línea de visión.
  • Phi* incremental: una modificación de Theta* que permite una planificación de trayectorias dinámica similar a D*.

Véase también

Referencias

  1. ↑ "Una comparación empírica de algoritmos de planificación de trayectorias en cualquier ángulo" (PDF) .
  2. ↑ "Theta*: Planificación de trayectorias en cuadrículas desde cualquier ángulo" (PDF) .
  3. ↑ Nash, Alex; Koeni, Sven; Tovey, Craig. "Lazy Theta*: Planificación de trayectorias en cualquier ángulo y análisis de longitud de trayectoria en 3D" (PDF) . idm-lab.org .