D*

Last updated

D* (pronounced "D star") is any one of the following three related incremental search algorithms:

Contents

All three search algorithms solve the same assumption-based path planning problems, including planning with the freespace assumption, [7] where a robot has to navigate to given goal coordinates in unknown terrain. It makes assumptions about the unknown part of the terrain (for example: that it contains no obstacles) and finds a shortest path from its current coordinates to the goal coordinates under these assumptions. The robot then follows the path. When it observes new map information (such as previously unknown obstacles), it adds the information to its map and, if necessary, replans a new shortest path from its current coordinates to the given goal coordinates. It repeats the process until it reaches the goal coordinates or determines that the goal coordinates cannot be reached. When traversing unknown terrain, new obstacles may be discovered frequently, so this replanning needs to be fast. Incremental (heuristic) search algorithms speed up searches for sequences of similar search problems by using experience with the previous problems to speed up the search for the current one. Assuming the goal coordinates do not change, all three search algorithms are more efficient than repeated A* searches.

D* and its variants have been widely used for mobile robot and autonomous vehicle navigation. Current systems are typically based on D* Lite rather than the original D* or Focused D*. In fact, even Stentz's lab uses D* Lite rather than D* in some implementations. [8] Such navigation systems include a prototype system tested on the Mars rovers Opportunity and Spirit and the navigation system of the winning entry in the DARPA Urban Challenge, both developed at Carnegie Mellon University.

The original D* was introduced by Anthony Stentz in 1994. The name D* comes from the term "Dynamic A*", [9] because the algorithm behaves like A* except that the arc costs can change as the algorithm runs.

Operation

The basic operation of D* is outlined below.

Like Dijkstra's algorithm and A*, D* maintains a list of nodes to be evaluated, known as the "OPEN list". Nodes are marked as having one of several states:

Expansion

The algorithm works by iteratively selecting a node from the OPEN list and evaluating it. It then propagates the node's changes to all of the neighboring nodes and places them on the OPEN list. This propagation process is termed "expansion". In contrast to canonical A*, which follows the path from start to finish, D* begins by searching backwards from the goal node. This means that the algorithm is actually computing the A* optimal path for every possible start node. [10] Each expanded node has a backpointer which refers to the next node leading to the target, and each node knows the exact cost to the target. When the start node is the next node to be expanded, the algorithm is done, and the path to the goal can be found by simply following the backpointers.

Obstacle handling

When an obstruction is detected along the intended path, all the points that are affected are again placed on the OPEN list, this time marked RAISE. Before a RAISED node increases in cost, however, the algorithm checks its neighbors and examines whether it can reduce the node's cost. If not, the RAISE state is propagated to all of the nodes' descendants, that is, nodes which have backpointers to it. These nodes are then evaluated, and the RAISE state is passed on, forming a wave. When a RAISED node can be reduced, its backpointer is updated, and passes the LOWER state to its neighbors. These waves of RAISE and LOWER states are the heart of D*.

By this point, a whole series of other points are prevented from being "touched" by the waves. The algorithm has therefore only worked on the points which are affected by change of cost.

Another deadlock occurs

This time, the deadlock cannot be bypassed so elegantly. None of the points can find a new route via a neighbor to the destination. Therefore, they continue to propagate their cost increase. Only points outside of the channel can be found, which can lead to destination via a viable route. This is how two Lower waves develop, which expand as points marked as unattainable with new route information.

Pseudocode

while(!openList.isEmpty()){point=openList.getFirst();expand(point);}

Expand

voidexpand(currentPoint){booleanisRaise=isRaise(currentPoint);doublecost;foreach(neighborincurrentPoint.getNeighbors()){if(isRaise){if(neighbor.nextPoint==currentPoint){neighbor.setNextPointAndUpdateCost(currentPoint);openList.add(neighbor);}else{cost=neighbor.calculateCostVia(currentPoint);if(cost<neighbor.getCost()){currentPoint.setMinimumCostToCurrentCost();openList.add(currentPoint);}}}else{cost=neighbor.calculateCostVia(currentPoint);if(cost<neighbor.getCost()){neighbor.setNextPointAndUpdateCost(currentPoint);openList.add(neighbor);}}}}

Check for raise

booleanisRaise(point){doublecost;if(point.getCurrentCost()>point.getMinimumCost()){foreach(neighborinpoint.getNeighbors()){cost=point.calculateCostVia(neighbor);if(cost<point.getCurrentCost()){point.setNextPointAndUpdateCost(neighbor);}}}returnpoint.getCurrentCost()>point.getMinimumCost();}

Variants

Focused D*

As its name suggests, Focused D* is an extension of D* which uses a heuristic to focus the propagation of RAISE and LOWER toward the robot. In this way, only the states that matter are updated, in the same way that A* only computes costs for some of the nodes.

D* Lite

D* Lite is not based on the original D* or Focused D*, but implements the same behavior. It is simpler to understand and can be implemented in fewer lines of code, hence the name "D* Lite". Performance-wise, it is as good as or better than Focused D*. D* Lite is based on Lifelong Planning A*, which was introduced by Koenig and Likhachev few years earlier. D* Lite

Minimum cost versus current cost

For D*, it is important to distinguish between current and minimum costs. The former is only important at the time of collection and the latter is critical because it sorts the OpenList. The function which returns the minimum cost is always the lowest cost to the current point since it is the first entry of the OpenList.

Related Research Articles

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

A* is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path from source to goal.

Best-first search is a class of search algorithms, which explores a graph by expanding the most promising node chosen according to a specified rule.

<span class="mw-page-title-main">Hill climbing</span> Optimization algorithm

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found.

<span class="mw-page-title-main">R-tree</span> Data structures used in spatial indexing

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both theoretical and applied contexts. A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" or "find the nearest gas station". The R-tree can also accelerate nearest neighbor search for various distance metrics, including great-circle distance.

Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to conservatively estimate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times.

<span class="mw-page-title-main">Pathfinding</span> Plotting by a computer application

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(bd/2) (in Big O notation), and the sum of these two search times is much less than the O(bd) complexity that would result from a single search from the beginning to the goal.

Motion planning, also path planning is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used in computational geometry, computer animation, robotics and computer games.

In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

<span class="mw-page-title-main">Rapidly exploring random tree</span> Search algorithm

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. They easily handle problems with obstacles and differential constraints and have been widely used in autonomous robotic motion planning.

In computer science, fringe search is a graph search algorithm that finds the least-cost path from a given initial node to one goal node.

<span class="mw-page-title-main">Any-angle path planning</span> Algorithm to find Euclidean shortest paths

Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

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*.

Incremental heuristic search algorithms combine both incremental and heuristic search to speed up searches of sequences of similar search problems, which is important in domains that are only incompletely known or change dynamically. Incremental search has been studied at least since the late 1960s. Incremental search algorithms reuse information from previous searches to speed up the current search and solve search problems potentially much faster than solving them repeatedly from scratch. Similarly, heuristic search has also been studied at least since the late 1960s.

<span class="mw-page-title-main">Sven Koenig (computer scientist)</span> German computer scientist

Sven Koenig is a full professor in computer science at the University of Southern California. He received an M.S. degree in computer science from the University of California at Berkeley in 1991 and a Ph.D. in computer science from Carnegie Mellon University in 1997, advised by Reid Simmons.

In computer science, jump point search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers.

In computer science, anytime A* is a family of variants of the A* search algorithm. Like other anytime algorithms, it has a flexible time cost, can return a valid solution to a pathfinding or graph traversal problem even if it is interrupted before it ends, by generating a fast, non-optimal solution before progressively optimizing it. This ability to quickly generate solutions has made it attractive to Search-base sites and AI designs.

LPA* or Lifelong Planning A* is an incremental heuristic search algorithm based on A*. It was first described by Sven Koenig and Maxim Likhachev in 2001.

<span class="mw-page-title-main">Wavefront expansion algorithm</span> Path planner similar to potential field method with breadth first search modification

The wavefront expansion algorithm is a specialized potential field path planner with breadth-first search to avoid local minima. It uses a growing circle around the robot. The nearest neighbors are analyzed first and then the radius of the circle is extended to distant regions.

References

  1. ↑ Stentz, Anthony (1994), "Optimal and Efficient Path Planning for Partially-Known Environments", Proceedings of the International Conference on Robotics and Automation: 3310–3317, CiteSeerX   10.1.1.15.3683
  2. ↑ Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659, CiteSeerX   10.1.1.41.8257
  3. ↑ Hart, P.; Nilsson, N.; Raphael, B. (1968), "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on Systems Science and Cybernetics, SSC-4 (2): 100–107, doi:10.1109/TSSC.1968.300136
  4. ↑ Koenig, S.; Likhachev, M. (2005), "Fast Replanning for Navigation in Unknown Terrain", IEEE Transactions on Robotics, 21 (3): 354–363, CiteSeerX   10.1.1.65.5979 , doi:10.1109/tro.2004.838026, S2CID   15664344
  5. ↑ Koenig, S.; Likhachev, M.; Furcy, D. (2004), "Lifelong Planning A*", Artificial Intelligence, 155 (1–2): 93–146, doi:10.1016/j.artint.2003.12.001
  6. ↑ Ramalingam, G.; Reps, T. (1996), "An incremental algorithm for a generalization of the shortest-path problem", Journal of Algorithms, 21 (2): 267–305, CiteSeerX   10.1.1.3.7926 , doi:10.1006/jagm.1996.0046
  7. ↑ Koenig, S.; Smirnov, Y.; Tovey, C. (2003), "Performance Bounds for Planning in Unknown Terrain", Artificial Intelligence, 147 (1–2): 253–279, doi: 10.1016/s0004-3702(03)00062-6
  8. ↑ Wooden, D. (2006). Graph-based Path Planning for Mobile Robots (Thesis). Georgia Institute of Technology.
  9. ↑ Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning", Proceedings of the International Joint Conference on Artificial Intelligence: 1652–1659, CiteSeerX   10.1.1.41.8257
  10. ↑ Murphy, Robin R. (2019). Introduction to AI robotics (2nd ed.). Bradford Books. Paragraph 14.5.2. ISBN   978-0262038485.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.