I''ve been playing around with A* recently and didn''t notice this at first but after a quick glance at the algorithm, it becomes obvious...

push node on OPEN list

while OPEN list is not empty  
{
    node = Pop the best node from OPEN list

    if node is a goal node 
    {
        construct path to goal
        return success
    }
    
    // otherwise we need to find what nodes can be generated from this node
    PushNodeSuccessors( OPEN, CLOSED, node );

    push node onto CLOSED list // we have already examined this node
}

return failure 

...as soon as the ''goal'' node is reached, the search terminates with success. Hooray, we found a path! However, this might not be the "best" path (i.e. shortest distance, smallest travel time, safest route, etc.). I know you can adjust the heuristic to find "better" paths, but no matter what kind of heuristic you have, using the above algorithm, you will always terminate and return success as soon as the goal node is reached (which might not be the best path). Sure, I could use a Depth First Search, Breadth First Search or a Floyd-Warshall algorithm to find the shortest path, but has anyone found a simple way to modify the A* algorithm to evaluate multiple paths even when the goal has been reached? You DON''T need to provide me links to Amit''s website or any other A* webpages (unless they address this problem specifically). I know how to use www.google.com to search for articles and websites, it''s just that I haven''t found anything that addresses this topic specifically. My thoughts on this was to save each successful path somewhere (along with some criteria that ranked that path, i.e. total distance, total travel time, relative "safeness", etc.) whenever that path was "better" than any previously found paths. I probably wouldn''t want to exhaustively search the node graph for all possible paths so I could limit the total number of nodes evaluated or limit the amount of time spent searching for the "best" path and abort the search (returning the successful path) when either of this is reached or when the node graph had been exhaustively evaluated. My guess is that this would give me the same paths that would be found using DFS, BFS, or Floyd''s algorithm, but I was curious to see if anyone had done any work in this area and might have some pointers, tips or suggestions. botman

A* is a heuristic search. It returns _good_ paths, it can never give a _shortest_ path with any certianty unless it performs a _non-heuristic_ search. If you want to have shortest paths you will have to use something like Dijkstra''s algorithm where you will have the worst-case complexity of trying every single possibility.

Oh my god!
But what are you saying! Of course that A* can find optimum paths!

A* is an optimum search algorithm, that returns the SHORTEST PATH if the heuristic you give it matches some preconditions:
- The heuristic always increases when advancing from one node to the next one.
- The heuristic is an "underestimator" of the cost of the path.

If your heuristic has both of the above conditions, IT ALLWAYS RETURNS THE SHORTEST SOLUTION. If not, it is that you have some bug in your code.

A typical "underestimator" for computing paths is the distance in straigh line to the goal (that is clearly an underestimator of the length of the best path).

Popolon is correct. A* is an optimally efficient search algorithm. By optimally efficient, we mean that it is: ''optimal'' (returns the lowest cost transition set from the start state to the goal state); and, ''efficient'' (guarantees to search less nodes than any other search algorithm to produce the otpimal path).

Certainly, the only caveat we place on this statement is that the search algorithm returns the optimal path from among the set of possible paths examinable by the algorithm (although it certainly will not examine all possible paths). Hence, the optimal path depends on the discretisation of the state/transition space.

If you''d like a mathematical proof of the optimality of A* I would be happy to provide it.

Cheers,

Timkin

Hmmmm, okay. After looking back at Amit''s A* webpage...

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html#S2

...and reading this...

"It''s important to choose a good heuristic function. A bad heuristic can really slow down A* or make it produce bad paths. If you want A* to give you "perfect" paths, the heuristic function should be an underestimate of the actual cost of getting from one spot to the goal. Be careful that you don''t underestimate too much however. A low heuristic won''t give A* much information, and it''ll keep telling A* that there are better paths available, so it will take longer to give you a path."

...in order for A* to ALWAYS find the "best" path, the heuristic must always return an estimate lower than the actual cost to the goal node. If your heuristic occasionally returns estimates that are larger than the actual cost to the goal, that path will be bumped down in priority on the OPEN list in favor of other paths that have a lower cost (or a lower estimated cost).

In my case, my heuristic is the straight line distance from the current node to the goal (when trying to find the path with the shortest distance). Some of the paths that I am using have "warpzones" (teleporters or wormholes) that jump from one area of the map to another area closer to the goal. When estimating the cost of nodes on a path leading to a warpzone, the heuristic is overestimating the actual distance to the goal, thus A* is lowering the priority of this node on the OPEN list in favor of other nodes with a lower estimate.

The problem that I have is that some of these paths using nodes with very high estimates never get evaluated since they are so low in priority on the OPEN list (i.e. the algorithm never gets a chance to determine that a warpzone exists which would lower the total actual cost and bump it up in the OPEN list priority). In these cases, I would need to continue to find paths even when one has been found and hope that a better path can be found using nodes still in the OPEN list, or I would need to have a much smarter heuristic that can predict that this path will lead to a warpzone that gets me much closer to the goal (not an easy thing to do, I think).

Does all of this sound reasonable? Am I still missing something?

botman

Well, your heuristic just has to be a monotonically increasing underestimate.

You could do some fanciness with your ''warps'' by, say, using the distance to the nearest warp as a heuristic. To keep your heuristic admissible, you might need to restrict it to warps that are ''between'' your character and the goal, so you won''t run off in completely the wrong direction.


Or, if you''re having a really tough time coming up with a good heuristic, you could make things easier on yourself by using a somewhat less optimal search. Branch-and-bound (Maybe even the added heuristic version) would do allright in this situation, IMO.

Clearly, given your ''warps'', your pathing space is nonmonotonic... hence, you cannot use a heuristic based on a Euclidean metric and hope to find an optimal path. I faced this same problem in my PhD research. Here''s one method for solving this problem...

Determine a set of coarse patches of your pathing space that are locally monotonic (i.e, they''re flat... they don''t contain two warp zones). Starting at the goal node, apply the distance transform algorithm... that is, you label each patch neighbouring the goal 1, then add each patch adjacent to each of these to a list of patches considered - that are not already labeled - and label these as 2... and so on. When you find your first warp zone near the goal, you need to add all patches containing other warp zones to your list and label them as if they were adjacent to the warp patch near the goal. Then keep going until you have labeled the patch containing the start node.

Now, you have two choices. Use this setup to traverse from the start to the goal node (i.e., don''t use A*), simply by following the gradient of numbers down to zero (the goal). Alternatively, if you have big patches and are concerned with the cost of travel across them (because different patches might have different true costs to cross them) then perform A*, but use the number of a patch (in which the current node resides) as an estimate of the cost to travel from that patch to the goal.

If this doesn''t make sense, or you''d like more details, just holler.

Cheers,

Timkin

You could improve your heuristic by taking nearby warpzones into account. This could be done efficiently by perhaps generating an influence map, assigning a bonus to the heuristic for nodes closer to warpzones. This will ''encourage'' the algorithm to move towards the warpzones more frequently. The bonus should be proportional to the ''traditional'' estimated distance though, as you don''t need the algorithm to waste time being biased towards warpzones when it is just a node or two away from the destination anyway.

You''d be getting into the realms of guesswork and estimates here, so you''d want to test the values you use against something like BFS to tune it to be accurate. I would normally be loathe to introduce such a hack, but since you already run the risk of your heuristics being significantly overestimated I think it might be worth a go.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]