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 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.[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 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*[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
References
- ^ "An Empirical Comparison of Any-Angle Path-Planning Algorithms" (PDF).
- ^ "Theta*: Any-Angle Path Planning of Grids" (PDF).
- ^ Nash, Alex; Koeni, Sven; Tovey, Craig. "Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D" (PDF). idm-lab.org.