Theta * es un algoritmo de planificación de trayectorias en cualquier ángulo que se basa en el algoritmo de búsqueda A * . Puede encontrar rutas 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 parecido al de A *. La única diferencia es lafunción. En comparación con A *, el padre de un nodo en Theta * no tiene que ser vecino del nodo siempre que haya una línea de visión entre los dos nodos. [ cita requerida ]
Pseudocódigo
Adaptado de. [2]
function theta * ( start , goal ) // Este bucle principal es el mismo que A * gScore ( start ) : = 0 parent ( start ) : = start // Inicializando conjuntos abiertos y cerrados. El conjunto abierto se inicializa // con el nodo de inicio y un costo inicial abierto : = {} abierto . insert ( start , gScore ( start ) + heuristic ( start )) // gScore (nodo) es la distancia más corta actual desde el nodo inicial al nodo // heuristic (nodo) es la distancia estimada del nodo desde el nodo objetivo // allí Hay muchas opciones para la heurística como Euclidiana o Manhattan cerrada : = {} mientras que abierto no está vacío s : = abierto . pop () si s = meta retorno reconstruct_path ( s ) cerrado . empuje ( s ) para cada vecino de s // bucle a través de cada vecino inmediato de s si vecino no en cerrado si vecino no en abiertas valores // Inicializar para vecino si es // no está ya en la lista abierta GPuntucaion ( vecino ) : = padre infinito ( vecino ) : = Nulo update_vertex ( s , vecino ) return Null function update_vertex ( s , vecino ) // Esta parte del algoritmo es la principal diferencia entre A * y Theta * if line_of_sight ( padre ( s ) , vecino ) // Si hay línea de visión entre padre (s) y vecino // luego ignore sy use la ruta de padre (s) a vecino si gScore ( padre ( s )) + c ( padre ( s ) , vecino ) < gScore ( vecino ) // c (s, vecino) es el Distancia euclidiana de sa vecino gScore ( vecino ) : = gScore ( padre ( s )) + c ( padre ( s ) , vecino ) padre ( vecino ) : = padre ( s ) si vecino en abierto abierto . quitar ( vecino ) abierto . insert ( vecino , gScore ( vecino ) + heurístico ( vecino )) else // Si la longitud de la ruta desde el inicio as y desde s hasta el // vecino es más corta que la distancia más corta conocida actualmente // desde el inicio al vecino, entonces actualizar 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 abierto . quitar ( vecino ) abierto . insert ( vecino , gScore ( vecino ) + heurística ( vecino ))función reconstruct_path ( s ) total_path = {s} // Esto forma recursiva reconstruir la ruta desde el nodo objetivo // hasta que se alcanza el nodo de inicio si el padre ( s ) ! = s ruta_total . push ( reconstruct_path ( padre ( s ))) de lo contrario devuelve total_path
Variantes
Existen las siguientes variantes del algoritmo: [ cita requerida ]
- Lazy Theta * [3] : las expansiones de nodos se retrasan, lo que resulta en menos comprobaciones de la línea de visión
- Incremental Phi *: una modificación de Theta * que permite una planificación de ruta dinámica similar a D *