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*.

Description

For the simplest version of Theta*, the main loop is much the same as that of A*. The only difference is the $\text{update}\mathrm{\_}\text{vertex}()$ 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*(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

Line-of-sight algorithm

lineOfSight(node1, node2) {
let x0 = node1.x;
let y0 = node1.y;
let x1 = node2.x;
let y1 = node2.y;
let dx = abs(x1 - x0);
let dy = -abs(y1 - y0);
let sX = -1;
let sY = -1;
if(x0 < x1) {
sX = 1;
}
if(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;
}
}
}

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*

See also

• Any-angle path planning
• A*