Theta*

Theta* is an 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*.^[1]

Description

For the simplest version of Theta*, the main loop is much the same as that of A*. The only difference is the ${\displaystyle {\text{update}}\_{\text{vertex}}()}$ function. Compared to A*, the parent of a node in Theta* does not have to be a neighbour of the node as long as there is a line-of-sight between the two nodes.^{[citation needed]}

Pseudocode

Adapted from.^[2]

function theta*(start, goal)  // This main loop is the same as A*  gScore(start) := 0  parent(start) := start  // Initializing open and closed sets. The open set is initialized   // with the start node and an initial cost  open := {}  open.insert(start, gScore(start) + heuristic(start))  // gScore(node) is the current shortest distance from the start node to node  // heuristic(node) 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(s)  closed.push(s)  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(neighbor) := infinity  parent(neighbor) := Null  update_vertex(s, neighbor)  return Null     function update_vertex(s, neighbor)  // This part of the algorithm is the main difference between A* and Theta*  if line_of_sight(parent(s), neighbor)  // If there is line-of-sight between parent(s) and neighbor  // then ignore s and use the path from parent(s) to neighbor   if gScore(parent(s)) + c(parent(s), neighbor) < gScore(neighbor)  // c(s, neighbor) is the Euclidean distance from s to neighbor  gScore(neighbor) := gScore(parent(s)) + c(parent(s), neighbor)  parent(neighbor) := parent(s)  if neighbor in open  open.remove(neighbor)  open.insert(neighbor, gScore(neighbor) + heuristic(neighbor))  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(s) + c(s, neighbor) < gScore(neighbor)  gScore(neighbor) := gScore(s) + c(s, neighbor)  parent(neighbor) := s  if neighbor in open  open.remove(neighbor)  open.insert(neighbor, gScore(neighbor) + heuristic(neighbor)) function reconstruct_path(s)  total_path = {s}  // This will recursively reconstruct the path from the goal node   // until the start node is reached  if parent(s) != s  total_path.push(reconstruct_path(parent(s)))  else  return total_path 

Variants

The following variants of the algorithm exist:^{[citation needed]}

• Lazy Theta*^[3] – 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*

See also

• Any-angle path planning
• A*

References

1. An Empirical Comparison of Any-Angle Path-Planning Algorithms
2. Theta*: Any-Angle Path Planning of Grids
3. http://idm-lab.org/bib/abstracts/papers/aaai10b.pdf^{[bare URL PDF]}