Perfect Pathfinding?
Author
I'm not really familiar with the algorithms used in path finding beyond the basic "keep trying until you find a way" method, and A*.
What I need is an algorithm that will return the exactly optimal path. It doesn't have to be terribly fast, it just needs to take a directional graph (with the possibility of loops), and find the 100% best path, if one exists.
Each node will have a list of child nodes, and similar to A*, each node will have a score that makes it more or less attractive to move to. I want to find the path with the highest score possible.
What's my best bet?
"path finding" implies that you start in a particular node, and have a particular goal node you want to get to. (Or, at the very most, you have a set of goal nodes, and you want to find the cheapest path to get to any ONE of them.) That is your situation, right?
If so, A* will return the exactly optimal path, as will Dijkstra's algorithm and uniform cost search. A* will be more efficient, assuming you can come up with a good heuristic to give it. The only situation in which these algorithms fail is if certain edges have negative weights. If you're in that situation, you'll need Bellman-Ford.
By the way, you mention having "scores" (costs) on nodes, as opposed to edges. This is unusual, but it isn't really a problem for any algorithm -- the cost of an edge is simply the cost of its destination node.
If so, A* will return the exactly optimal path, as will Dijkstra's algorithm and uniform cost search. A* will be more efficient, assuming you can come up with a good heuristic to give it. The only situation in which these algorithms fail is if certain edges have negative weights. If you're in that situation, you'll need Bellman-Ford.
By the way, you mention having "scores" (costs) on nodes, as opposed to edges. This is unusual, but it isn't really a problem for any algorithm -- the cost of an edge is simply the cost of its destination node.
Author
Hey, yeah that's my situation, I have a start and goal. My understanding is that A* will return a pretty good path that's often the best, but not guaranteed to be the best. Is my understanding wrong? I need to return the absolutely best possible path or it's no good for my scenario. A* can do that?
Quote:Original post by Pete Michaud
Hey, yeah that's my situation, I have a start and goal. My understanding is that A* will return a pretty good path that's often the best, but not guaranteed to be the best. Is my understanding wrong? I need to return the absolutely best possible path or it's no good for my scenario. A* can do that?
As long as the A* heuristic is admissible - meaning, it never overestimates the cost to get to the target. Underestimating will still return the best path, it'll just explore more nodes. In fact, if your A* heuristic returns 0, then your A* algorithm has essentially turned into Dijkstra's algorithm (which will always return the best path, but it will explore quite a lot more nodes)
Quote:Original post by Pete MichaudYes, your understanding is wrong. clicky
My understanding is that A* will return a pretty good path that's often the best, but not guaranteed to be the best. Is my understanding wrong?
Author
Maybe I'm just being dumb here, but I'm trying to learn, so humor me.
Let's say I have a roughly diamond shaped graph, that has a start, connected to two equally long branches, that both eventually lead to a goal.
Branch A has an attractive node connected directly to the start, but the rest of the nodes are bad. Branch B has a bad node connected to start, but the rest of the nodes are attractive. Overall, Branch B is the better branch.
My understanding is that the algorithm will check both connected nodes, choose Branch A because the first node is better, then be forced to travel along Branch A since it can't really back up.
The "Heuristic" in this case, that would solve the problem, is not really a heuristic, but just traversing the path for each node to find what the actual cost would be.
In my scenario, there isn't really a better heuristic... path length is nearly meaningless, and there's no way to estimate what the scores of each node might be because they are totally arbitrary.
I guess I could try pre computing the average node score and using that as the heuristic, but from the example, since the branches are the same length, it would calculate the heuristic as equal, and still choose branch A instead of the better branch B.
Maybe this is a case for which A* isn't suited since there's no meaningful heuristic?
Let's say I have a roughly diamond shaped graph, that has a start, connected to two equally long branches, that both eventually lead to a goal.
Branch A has an attractive node connected directly to the start, but the rest of the nodes are bad. Branch B has a bad node connected to start, but the rest of the nodes are attractive. Overall, Branch B is the better branch.
My understanding is that the algorithm will check both connected nodes, choose Branch A because the first node is better, then be forced to travel along Branch A since it can't really back up.
The "Heuristic" in this case, that would solve the problem, is not really a heuristic, but just traversing the path for each node to find what the actual cost would be.
In my scenario, there isn't really a better heuristic... path length is nearly meaningless, and there's no way to estimate what the scores of each node might be because they are totally arbitrary.
I guess I could try pre computing the average node score and using that as the heuristic, but from the example, since the branches are the same length, it would calculate the heuristic as equal, and still choose branch A instead of the better branch B.
Maybe this is a case for which A* isn't suited since there's no meaningful heuristic?
Author
Maybe it would help to answer my question if I got more specific about what I want to do.
The score of each node in this isn't a "cost" in the traditional A* sense. It's a percentage, so from 0 to 1. The score % is like a dice roll, so when you move to a node you have to flip a biased coin, as it were, according to the node's score.
So if I move from start to a node with .5, then there's a 50% chance I "die" and can't continue.
If I move from start to a node with 1, then I can automatically move on, since there's no chance of failure.
As I travel along the path, the chance of "dying" increases multiplicatively. So, for example for the path:
[start]->[.5]->[.5]->[goal]
I have a 25% of success to reach the goal.
However, for:
[start]->[1]->[1]->[goal]
I have 100% of reaching my goal
And:
[start]->[0]->[1]->[goal]
I have no chance of reaching the goal.
One relevant side effect here is that length is meaningless. Here are two paths on the same graph:
[start]->[.5]->[goal]
[start]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[goal]
One of them only has one step, but only a 50% chance of success. The other has a bunch of steps, but 100% chance of success. The second path wins.
I want to ALWAYS choose the path with the highest chance. And for what it's worth, as in Drjkstra's algorithm, I actually need the list of equally optimal paths. Bonus points if I can get a list of paths above a certain threshold, so I can know for example, the top 5 possible paths.
Are we really sure A* is the right choice for this?
The score of each node in this isn't a "cost" in the traditional A* sense. It's a percentage, so from 0 to 1. The score % is like a dice roll, so when you move to a node you have to flip a biased coin, as it were, according to the node's score.
So if I move from start to a node with .5, then there's a 50% chance I "die" and can't continue.
If I move from start to a node with 1, then I can automatically move on, since there's no chance of failure.
As I travel along the path, the chance of "dying" increases multiplicatively. So, for example for the path:
[start]->[.5]->[.5]->[goal]
I have a 25% of success to reach the goal.
However, for:
[start]->[1]->[1]->[goal]
I have 100% of reaching my goal
And:
[start]->[0]->[1]->[goal]
I have no chance of reaching the goal.
One relevant side effect here is that length is meaningless. Here are two paths on the same graph:
[start]->[.5]->[goal]
[start]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[1]->[goal]
One of them only has one step, but only a 50% chance of success. The other has a bunch of steps, but 100% chance of success. The second path wins.
I want to ALWAYS choose the path with the highest chance. And for what it's worth, as in Drjkstra's algorithm, I actually need the list of equally optimal paths. Bonus points if I can get a list of paths above a certain threshold, so I can know for example, the top 5 possible paths.
Are we really sure A* is the right choice for this?
== Edit ==
Sorry, you already answered my question while I was writing this post :).
You could use A* quite easily.
Lets say that the score of the node X is:
f(X) = node chance * running chance of branch
and count of hops to end goal is:
hops(X) = count of hops to end goal
We know that during X hops the chance of reaching goal will never grow above f(X) because node chance is never > 1.0 and f(X) * 1.0 * 1.0 * ... * 1.0 = f(X).
Therefore we can use f(X) as the search heuristic since we can always compare two branches and always pick the one that we have had less trouble to reach during search.
To get a list of best paths, just don't stop after finding the best path, just continue the search until you have found all you need.
At least that's how I see it right now. I could be wrong though.
== End edit ==
Maybe you could give us a bit more idea, what the graph is and what meta-info do you have for each node? If there is absolutely no heuristic, then A* would indeed be equal to brute force search, but it might not be true.
Also, the example you gave, isn't a very good one. Lets say we have a graph G where there are two paths:
S=>A1(0.2) => B1(0.6) => C1(0.3)=>E
and
S=>A2(0.6) => B2(0.1) => C2(0.3)=>E
Then A* sorted queue in each step would look like:
1. A1(0.2)
2. B1(0.8)
3. A2(0.6), B1(0.8)
4. B2(0.7), B1(0.8)
5. B1(0.8), C2(1.0)
6. C2(1.0), C1(1.1)
From C2 we reach the end having avoided searching C1 for next node.
However, this isn't a very good example as you rarely have only two paths and in case of path-finding in 2D or 3D space there are clearly some branches that are in the wrong direction.
So, give a few more hints of what the graph, that you are searching from, looks like. At the least it may be possible to pre-calculate some values if you have to do a lot of searches on the same graph.
[Edited by - mrjones on April 16, 2010 8:55:44 AM]
Sorry, you already answered my question while I was writing this post :).
You could use A* quite easily.
Lets say that the score of the node X is:
f(X) = node chance * running chance of branch
and count of hops to end goal is:
hops(X) = count of hops to end goal
We know that during X hops the chance of reaching goal will never grow above f(X) because node chance is never > 1.0 and f(X) * 1.0 * 1.0 * ... * 1.0 = f(X).
Therefore we can use f(X) as the search heuristic since we can always compare two branches and always pick the one that we have had less trouble to reach during search.
To get a list of best paths, just don't stop after finding the best path, just continue the search until you have found all you need.
At least that's how I see it right now. I could be wrong though.
== End edit ==
Maybe you could give us a bit more idea, what the graph is and what meta-info do you have for each node? If there is absolutely no heuristic, then A* would indeed be equal to brute force search, but it might not be true.
Also, the example you gave, isn't a very good one. Lets say we have a graph G where there are two paths:
S=>A1(0.2) => B1(0.6) => C1(0.3)=>E
and
S=>A2(0.6) => B2(0.1) => C2(0.3)=>E
Then A* sorted queue in each step would look like:
1. A1(0.2)
2. B1(0.8)
3. A2(0.6), B1(0.8)
4. B2(0.7), B1(0.8)
5. B1(0.8), C2(1.0)
6. C2(1.0), C1(1.1)
From C2 we reach the end having avoided searching C1 for next node.
However, this isn't a very good example as you rarely have only two paths and in case of path-finding in 2D or 3D space there are clearly some branches that are in the wrong direction.
So, give a few more hints of what the graph, that you are searching from, looks like. At the least it may be possible to pre-calculate some values if you have to do a lot of searches on the same graph.
[Edited by - mrjones on April 16, 2010 8:55:44 AM]
Quote:Original post by Pete Michaud
Maybe I'm just being dumb here, but I'm trying to learn, so humor me.
Let's say I have a roughly diamond shaped graph, that has a start, connected to two equally long branches, that both eventually lead to a goal.
Branch A has an attractive node connected directly to the start, but the rest of the nodes are bad. Branch B has a bad node connected to start, but the rest of the nodes are attractive. Overall, Branch B is the better branch.
My understanding is that the algorithm will check both connected nodes, choose Branch A because the first node is better, then be forced to travel along Branch A since it can't really back up.
Your understanding is wrong. It may well 'waste time' evaluating nodes along Branch A, but when it reaches a point of realising that Branch B could actually be better, it will investigate Branch B instead. The awkwardness of the example has an effect on the efficiency of the algorithm but not the correctness.
Author
I think I see what I missed -- it doesn't just disregard previous possibilities, it keeps that in the queue to compare to nodes farther along a different branch, and if the branch(s) it's traversing start looking too hairy, it's going to favor a previously untraversed branch.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
