Read on Twitter
Many people know A* and Weighted A*, but there is actually rich family of similar algorithms that are all easily to implement, with several suboptimal variants. A thread on our AAAI 2021 paper. ( https://webdocs.cs.ualberta.ca/~nathanst/papers/chen2021general.pdf) [1/10]
A* is one of the most common search algorithms. Even when something is “better than A*” that often means A* with a better heuristic, better constraints, or abstracted search space. A* prioritizes state expansions by f = g+h. [2/10]
When something faster is needed and optimality can be relaxed, then Weighted A* is a good choice. Weighted A* returns a solution that is at most w-suboptimal by using f = g+w·h. Essentially a 1-line change to A*. [3/10]
Ira Pohl (who invented Weighted A*) was at the SoCS conference a few years ago where he related that he didn’t realize that Weighted A* had w-bounded suboptimality when he designed the algorithm - he was just looking for faster search. [4/10]
In the past years, there have been many algorithms (eg Explicit Estimation Search and Dynamic Potential Search) that outperform Weighted A*, but these are rarely used in practice, likely because they are much more complicated to implement. [5/10]
(These algorithms also require node re-openings, something I won’t won’t get into here, but re-openings can seriously impact performance, so we ant to avoid that.) [6/10]
For the past few years we have been working to characterize the simple functions that can be dropped into A* to improve performance. Our AAAI 2021 paper characterizes the necessary and sufficient conditions for priority functions. [7/10]
We now have a very simple, highly performant piecewise evaluation function:
[h > g: f = g+h; h ≤ g: f = (g+(2w-1)h)/w]
This says, search with A* as long as h > g. Then, search with weight 2w-1. [8/10]
[h > g: f = g+h; h ≤ g: f = (g+(2w-1)h)/w]
This says, search with A* as long as h > g. Then, search with weight 2w-1. [8/10]
Weighted A* almost always has to search exhaustively around the start anyway, so this function does this explicitly, and then is able to search more aggressively when it gets closer to the goal. [9/10]
This is a minor change to most A* implementations. If you’re doing suboptimal search, this only takes a few minutes to implement, and typically is able to improve performance, especially when the heuristic is weak. [10/10]
You can play with these and other suboptimal algorithms here: https://www.movingai.com/SAS/SUB/ [11/10]
