User:AnonymousEditor/sandbox
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
[edit]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 vertices is . 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
[edit]A*-based
[edit]- 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 , if there is line-of-sight between and the successor of , . If there is, the path from to since it will always be at least as short as the path from to and to .
- Field D* (FD*) - Add that it is based on D*
Applications
[edit]Robotics
[edit]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*
[edit]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
[edit]Basic Theta* is the most simple version of Theta*. The main loop is the same as in A*, with only difference being the 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
[edit]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
[edit]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*
See Also
[edit]This is a user sandbox of AnonymousEditor. You can use it for testing or practicing edits. This is not the sandbox where you should draft your assigned article for a dashboard.wikiedu.org course. To find the right sandbox for your assignment, visit your Dashboard course page and follow the Sandbox Draft link for your assigned article in the My Articles section. |