Theta*


Theta* is an any-angle [path planning|any-angle] path planning algorithm that is based on the A* search algorithm. It can find near-optimal paths with run times comparable to those of A*.

Description

For the simplest version of Theta*, the main loop is much the same as that of A*. The only difference is the function. Compared to A*, the parent of a node in Theta* does not have to be a neighbor of the node as long as there is a line-of-sight between the two nodes.

Pseudocode

Adapted from.
function theta*
// This main loop is the same as A*
gScore := 0
parent := start
// Initializing open and closed sets. The open set is initialized
// with the start node and an initial cost
open :=
open.insert + heuristic)
// gScore is the current shortest distance from the start node to node
// heuristic is the estimated distance of node from the goal node
// there are many options for the heuristic such as Euclidean or Manhattan
closed :=
while open is not empty
s := open.pop
if s = goal
return reconstruct_path
closed.push
for each neighbor of s
// Loop through each immediate neighbor of s
if neighbor not in closed
if neighbor not in open
// Initialize values for neighbor if it is
// not already in the open list
gScore := infinity
parent := Null
update_vertex
return Null


function update_vertex
// This part of the algorithm is the main difference between A* and Theta*
if line_of_sight
// If there is line-of-sight between parent and neighbor
// then ignore s and use the path from parent to neighbor
if gScore + c < gScore
// c is the Euclidean distance from s to neighbor
gScore := gScore + c
parent := parent
if neighbor in open
open.remove
open.insert + heuristic)
else
// If the length of the path from start to s and from s to
// neighbor is shorter than the shortest currently known distance
// from start to neighbor, then update node with the new distance
if gScore + c < gScore
gScore := gScore + c
parent := s
if neighbor in open
open.remove
open.insert + heuristic)
function reconstruct_path
total_path =
// This will recursively reconstruct the path from the goal node
// until the start node is reached
if parent != s
total_path.push
else
return total_path

Line-of-sight algorithm


lineOfSight

Variants

The following variants of the algorithm exist:
  • Lazy Theta* – Node expansions are delayed, resulting in fewer line-of-sight checks
  • Incremental Phi* – A modification of Theta* that allows for dynamic path planning similar to D*