Vizualization of Theta*

Any-Angle Planning

For path planning in video games and robotics, one can discretize a continuous environment into an 8-neighbor grid with unblocked and blocked cells and search the grid graph with an optimal path-planning algorithm (such as A*) to find a shortest path on the graph. The resulting path can be longer than a shortest path in the continuous environment. A* with Post Smoothing shortens the path after the A* search by replacing parts of it with straight lines. However, the shortened path can still be long since shortening it does not change how it moves around around blocked cells. Any-angle path-planning algorithms, on the other hand, interleave the shortening and the search. One such any-angle path-planning algorithm, Theta*, is a simple extension of A*: When it expands a vertex v and generates a successor u, Theta* checks if the straight line between the parent of v and u intersects any blocked cell. If not, it changes the parent of u to be the parent of v if this decreases the g-value of u.

Applet

This applet demonstrates how A*, A* with Post Smoothing and Theta* operate on 8-neighbor grids with blocked and unblocked cells, where the vertices of the grid graph are placed at the corners of cells. Movement between two diagonally-touching blocked cells is not allowed.

Theta* uses the Euclidean distance between two vertices as heuristic, while A* and A* with Post Smoothing use the Octile distance instead. The search tree is displayed by drawing a line from each generated vertex to its parent. If a vertex has been expanded, the line to its parent is red. If it has been generated but not expanded, the line is beige. Blue vertices are in the open list, and the green path is the path from the start vertex to the goal vertex found by the search.

Usage

• Getting ready: You want to make sure that Javascript is enabled.
• Setting up the map: You can select one of the five pre-generated maps (such as the Cretan Labyrinth) or click the 'reset' button to start with an empty map. Left clicking a cell toggles its blockage status.
• Setting up the start and goal vertices: Right clicking two cells in succession sets the first one to contain the start vertex and the second one to contain the goal vertex. The start and the goal have four radio buttons associated with each of them that control which corner of the selected cell should be the start or goal vertex, respectively.
• Running the simulation: The simulation runs automatically when valid start and goal vertices are selected (they need to be corners of unblocked cells). Adding or removing blocked cells restarts the simulation. The simulation speed can be adjusted with the slider or can be made instant by selecting the 'immediate' button. The bottom of the screen shows the number of vertex expansions and the length of the resulting path.