Sign in to follow this  
Phillipe

A* owns them all ?

Recommended Posts

Hey everybody ! I'm wondering - are there any other AI algorithms, other than A-Star, for path finding ?... And if there are, what are their advantages/disadvantages comparing to the A* algorithm ?... Thanks a lot in advance, Arie.

Share this post


Link to post
Share on other sites
Also, A* is made for finding a path to a specific goal. What if you want your bot to find a path to a health pack but theres many health packs throughout the level? It'd be inefficient to generate an A* to each of them to find the closest. Instead Dijkstra's is a better choice for this type of situation as it will find an optimal path to the first health pack it finds in the search, so in essence you get to find the closest cheapest healthpack to go to with 1 call to your Dijkstra path planner.

Share this post


Link to post
Share on other sites
A* is optimal, it is really I end of a series of search algorithm. You can see in the book from Russel and Norvig, Artificial Intelligence: a Modern Aproach.

Altough A* is optimal it is not complete, so it is a more IA search techniques.

Dijkstra is optimal and complete and is a more algorithm thing. And computes the distance from a node to all other's in the graph.

Share this post


Link to post
Share on other sites
It's not simply that A* is optimal... there are many other optimal search algorithms out there (in that they return the optimal path). What A* guarantees (and this is the kicker) is that it is optimally efficient, which means that not only does it guarantee to return the optimal path (under certain assumptions) but it also guarantees to expand fewer nodes in its search tree than any other algorithm.

Timkin

Share this post


Link to post
Share on other sites
The A* algorithm requires a distance heuristic (lower bound if I remember correctly). Most of the time this isn't a problem, but there are times when you can't provide one (e.g. a map with lots of wormholes?) so the other algorithms become more suitable.

Share this post


Link to post
Share on other sites
If you remove the heuristic from the cost calculations, A* turns into Dijkstra. In my A* implementation I have a flag I can set to use the heuristic, so when looking for the nearest health kit for example, a heuristic is pointless if there are many of them, so Dijkstra would be preferred, planning for specific goals and I use A*

Share this post


Link to post
Share on other sites
While A* is optimally efficient on a pure random access memory machine with limitless amount of memory, in reality it's not always the fastest algorithm for finding the optimal path, because it consumes so much memory. There are variations such as IDA* and SMA* which use less memory and are still optimally efficient on certain environments (not all, like A* is).

So, choosing A* is not always best bet. Sometimes you want less optimal paths, like others have mentioned, and sometimes the search space is such that SMA* has same speed complexity but lower memory usage complexity.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
If you remove the heuristic from the cost calculations, A* turns into Dijkstra. In my A* implementation I have a flag I can set to use the heuristic, so when looking for the nearest health kit for example, a heuristic is pointless if there are many of them, so Dijkstra would be preferred, planning for specific goals and I use A*


Do you have some benchmarks of your implementation?
I'de be very interested in comparing performances.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this