Is A* the best pathfinding algorithm?

Question

It is generally said that A* is the best algorithm to solve pathfinding problems.

Is there any situation when A* is not the best algorithm to find solution?

How good is A* compared to BFS, DFS, UCS, etc?

Answer 1

The short answer is yes, there are situations in which A* is not the best algorithm to solve a problem. However, there are a number of ways to assess what constitutes the best algorithm for finding a solution.

If you are considering best in terms of performance of multiple searches from a single source to many destinations, then you should consider using a more suitable approach (Dijkstra's algorithm).

If you are considering best in terms of performance, then in some special cases DFS and BFS will significantly outperform A*. From past experience, this occurs for very small, almost trivial graphs, but would require careful testing and profiling to make a stronger statement.

If you are considering best in terms of path-length, that is how long the final path produced by the algorithm is, then A* is equivalent to any other optimal search algorithm.

If you are considering best in terms of completeness, that is, will the algorithm always find a path to the goal if such a path exists. If so, then A* is equivalent to any other complete algorithm (for example, breadth-first-search).

If you are considering best in cases where some of the weights in the graph are negative, then you will need to use a special algorithm to solve those problems (for example bellman-ford)

If you are considering best in cases where the no heuristic is available then you must fall back on h(x,y)=0 forall states x and y. In this case A* is equivalent to best first search.

If you are considering best in cases related to motion planning in continuous configuration spaces, then A* may work adequately in low dimensions, but storage of the search graph starts to become impractical at high dimensions, and the need to use probabilistically complete algorithms increases (for example RRT, Bi-RRT, RDT)

If you are considering best in cases where the graph is partially observable, you only know a subset of all the possible vertices and edges within the graph at any time, and you need to change state to observe more of the graph, then you need an alternative algorithm designed for this (for example, Keonig's Lifelong Planning A*, LPA*, does exactly this).

If you are considering best in cases where the graph changes over time, which occurs frequently in robotics when you incorporate moving obstacles, then you need an algorithm which is designed for this (for example Stentz's D* or Koenig & Likhachev's D*-Lite).

Answer 2

A* is special because can be morphed into other path-finding algorithms by playing with how it evaluates nodes and the heuristics it uses. You can do this to simulate Djikstra's, best-first-search, breadth-first-search, and depth-first-search.

Furthermore, it's often easy to speed it up. For instance, if you multiply an admissible heuristic by a constant, c, you can guarantee that the cost of the resulting sequence of nodes is no more than c times the optimal result.

For instance, take this awesome paper by Ian Davis (written for Star Trek Armada). A* is used with a hierarchical set of waypoints, which results in a rough path. THEN, in order to smooth the path, they run A* again on a new, generated graph containing the nodes on the path and those nearby to get a more reasonable path. Finally, they run rubber-banding to remove redundant nodes.

So, A* isn't the solution to everything, but it's a very versatile tool.

Answer 3

Collaborative Diffusion is a simple alternative (no wrangling with heuristics).

It works well when you need to target one target or any member of a group, indiscriminately, and in this case can be faster than A*. It mimics "You're Getting Warmer/Colder". This works in two steps:

1. Create a heatmap for each target... if you want to track a specific target, treat it as its own group by creating a heatmap just for that target. Heatmaps are created by selecting the target location / cell, setting a high value scent (say 1.0 if we are using floating point) and using a standard diffusion formula to spreads that scent across the map. This scent gets weaker and weaker as it spreads out from target. Once a certain weakness of scent is reached, we stop spreading.
2. Each agent now uses the map for hill climbing, where agents (like wolves tracking a scent) move repeatedly to that nearest neighbouring cell where scent is strongest. Any cell where an agent is already present, has its scent value overridden with 0.0, since you cannot move there.

It works best in games like football with just a few goals (where both teams of agents track the ball and goalposts specifically, leading to just 3 influence maps) or Pacman (similar, multiple agents tracking Pac) or games where there is one combined heatmap representing the centroid of a group of agents, as averaged from each agent in that army, so that one army can approach "the other army" rather than "specific units within the other army". This generality may afford increased performance.

It is best suited where maps are fairly densely populated with many, moving units, thus justifying the extensive diffusion which must occur across the entire search space on each update, although the computational cost increases on the number of maps that must be updated per frame.

Answer 4

I see question is old but probably this practical solution will be useful for someone. Recently I found very nice open source code written in python

code contains next pathfinding algorithms:

• A*
• Dijkstra
• Best-First
• Bi-directional A*
• Breadth First Search (BFS)
• Iterative Deeping A* (IDA*)

changing the matrix size and values allows to feel difference between different path finding algorithms. As it is mentioned on Wikipedia: "A* is complete and will always find a solution if one exists"