Any-angle path planning algorithms are a subset of pathfinding algorithms that search for a path between two points and allows the turns in the path to have any angle. This results in paths that appear natural and direct. Other pathfinding algorithms such as A* constrain the paths to a grid, which produces jagged, unnatural paths. Any-angle algorithms are able to find optimal or near-optimal paths by incorporating the any-angle search into the algorithm itself. Algorithms such as A* Post Smoothing that smooth a path found by a grid constrained algorithm are unable to reliably find optimal paths since they cannot change what side of a blocked cell is traversed (would like to add an illustration of this).

Motivation

Any-angle path planning algorithms are necessary in order to quickly find an optimal path. For a world represented by a grid of blocked and unblocked cells, the brute-force way to find an any-angle path is to search the corresponding visibility graph. This is problematic since the the number of edges in a graph with $V$ vertices is $O(V^{2})$ . Searching the discrete grid graph can be done quickly, but the paths aren't optimal since since the the angle of the turns are constrained to 45° or 90°, which will add turns and increase the overall length of the path. Smoothing a grid-constrained path after doesn't fix this problem since the algorithm that found that path did not look at all possible paths. Any-angle path planning algorithms find shorter paths than the grid-constrained algorithms while taking roughly same amount of time to compute.

Points I wanted to make clear in this section:

shorter paths

smoother paths

post smoothing doesn't work as well

try to add example of shorter paths on different sides of an obstacle

Searches more options than a grid constrained algorithm while preserving its efficiency and avoiding the quadratic growth of a visibility graph

Algorithms

A*-based

ANYA - Finds optimal any-angle paths by looking at an interval of points as a node rather than a single point.
Theta* - Same main loop as A*, but for each expansion of a vertex $s$ , if there is line-of-sight between $parent(s)$ and the successor of $s$ , $s'$ . If there is, the path from $parent(s)$ to $s'$ since it will always be at least as short as the path from $parent(s)$ to $s$ and $s$ to $s'$ .
Field D* (FD*) - Add that it is based on D*

Applications

Robotics

Hybrid A* was created by Stanford Racing as part of the navigation system for Junior, their entry to the DARPA Urban Challenge. ^[1] Hybrid A* is continuous and tracks the vehicle's position and orientation. This ensures that the path generated can be followed by the vehicle, unlike the paths generated by A* for Field D*.

Video Games (Couldn't actually find much on this, maybe they all use some basic modification of A*)

Theta*

Theta* is an any-angle path planning algorithm that is based on A*. It can find near-optimal paths with run times comparable to A*^[2].

Description

Basic Theta* is the most simple version of Theta*. The main loop is the same as in A*, with only difference being the $update\_vertex()$ function. In A* the parent of node is always its neighbor. In Basic Theta*, the parent of a node does not have to be its neighbor if there is line-of-sight between the two nodes.

Pseudocode

Adapted from ^[3].

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
    // heurisitc(node) is the esitmated 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 differnce 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

Angle-Propagation Theta* is a variation of Basic Theta* that

Field D* is not constrained to a grid, but but the lines through each cell are linear, which can be difficult for a robot to follow.

Variants

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*

User:AnonymousEditor/sandbox

Contents