Weighted A* Node Re-Opening
Weighted A* is often used when bounded suboptimal solutions are desired, although recent algorithms such as Simplified Explicit Estimate Search (SEES) (Hatem and Ruml, 2014) can offer strong performance.
On this page we illustrate the performance of Weighted A* when we do and do not re-open nodes that we find via a different path with lower g-cost. This is an important algorithmic parameter; in most cases you don't want to re-open nodes, but users should be aware of how this influences performance.
The first video shows a standard A* search. The search expands uniformly outward as the f-cost increases. Red states are on the closed list, while green states are on the open list. The yellow state is the next to be expanded.
Now, consider the same problem with weighted A* and a weight of 10. That is, it searches according to f(n) = g(n) + 10*h(n). The weighted A* search focuses on states that are closer to the goal, giving up the guarantee of finding the optimal solution.
Consider the same problem, except that if we find a shorter path to a state that is already closed, we put the state back on to the open list to re-open again later. In this video re-opened states on the closed list are purple, while re-opened states on the open list are blue. In this example it is clear that re-opening nodes does not speed up the search, but it will reduce the solution cost.
Now, we look at the influence of opening/re-opening nodes in a different problem. It seems to be more common that you shouldn't re-open nodes in a weighted A* search, but this really depends on the properties of domains being used. In this case we attempt to solve a new problem without re-opening nodes. The search is blocked for some time before it can continue to the goal.
Solving the same problem with node re-openings, the we are able to solve the problem much more quickly. This is because the state which was blocked in the previous search can now be re-opened with lower cost. (The purple and blue states are being re-expanded multiple times as before.)
Permission is granted to download and use these videos for non-commercial use. Downloads