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 neighbor of the node as long as there is a line-of-sight between the two nodes.^{[ citation needed ]}

Pseudocode

Adapted from. ^[2]

functiontheta*(start,goal)// This main loop is the same as A*gScore(start):=0parent(start):=start// Initializing open and closed sets. The open set is initialized // with the start node and an initial costopen:={}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:={}whileopenisnotemptys:=open.pop()ifs=goalreturnreconstruct_path(s)closed.push(s)foreachneighborofs// Loop through each immediate neighbor of sifneighbornotinclosedifneighbornotinopen// Initialize values for neighbor if it is // not already in the open listgScore(neighbor):=infinityparent(neighbor):=Nullupdate_vertex(s,neighbor)returnNullfunctionupdate_vertex(s,neighbor)// This part of the algorithm is the main difference between A* and Theta*ifline_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 ifgScore(parent(s))+c(parent(s),neighbor)<gScore(neighbor)// c(s, neighbor) is the Euclidean distance from s to neighborgScore(neighbor):=gScore(parent(s))+c(parent(s),neighbor)parent(neighbor):=parent(s)ifneighborinopenopen.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 distanceifgScore(s)+c(s,neighbor)<gScore(neighbor)gScore(neighbor):=gScore(s)+c(s,neighbor)parent(neighbor):=sifneighborinopenopen.remove(neighbor)open.insert(neighbor,gScore(neighbor)+heuristic(neighbor))functionreconstruct_path(s)total_path={s}// This will recursively reconstruct the path from the goal node // until the start node is reachedifparent(s)!=stotal_path.push(reconstruct_path(parent(s)))elsereturntotal_path

Line-of-sight algorithm

lineOfSight(node1,node2){letx0=node1.x;lety0=node1.y;letx1=node2.x;lety1=node2.y;letdx=abs(x1-x0);letdy=-abs(y1-y0);letsX=-1;letsY=-1;if(x0<x1){sX=1;}if(y0<y1){sY=1;}lete=dx+dy;while(true){letpoint=getNode(x0,y0);if(pointdoesnotexistORpointisnotwalkable){returnfalse;}if(x0==x1ANDy0==y1){returntrue;}lete2=2*e;if(e2>=dy){if(x0==x1){returntrue;}e+=dy;x0+=sX;}if(e2<=dx){if(y0==y1){returntrue;}e+=dx;y0+=sY;}}}

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