Theta*

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} _ \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) // 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(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*

References

References

1. "An Empirical Comparison of Any-Angle Path-Planning Algorithms".
2. "Theta*: Any-Angle Path Planning of Grids".
3. "Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D".