I'm trying to solve the following problem: Find the best path that is at least N% different than the optimal path. The optimal path is being solved by A* over a graph. The end product desired is a number of different paths, all different by at least some percentage from the optimal path. "At least 10% different" would mean shares less than 90% of the optimal path's edges. Are there keywords I should be searching for? Multiple Route Path Planning only got me articles on path planning for multiple cooperative agents. Thanks!

Can't you just get the optimal path then mark every 10th node as 'blocked' and path again? The new path will be at least 10% different...
Mind you, you might get a situation where a node MUST be used to get a path at all, so you'd have to allow for that... In the worst case (ie a maze with just one path through it) ALL the nodes must be used, so a 10% different path would be impossible!

What's the actual application of this particular problem?

I would say find the optimal path (chain of nodes) and then generate paths for a terrain where you block nodes along that path. Do single nodes blockage first to see if any qualify as N% different then if needed test a conbination set of 2 nodes blocked (3 etc...)


Sounds like an arbitrary homework assignment (cant think immediately why you would want such a limitation in a real use)



Rethinking it, the open list would have all the node path ends which were less than optimal and you could continue pulling them as candidates to move to completing the path. You would save the length/cost of the optimal and throw out completed paths that overlap less than N% different and return all those with a larger difference (which would probably be rather alot of them : 100% - N% using your N=10 means 90% of all valid paths would have to be returned -- depending on your node count could be a very large combinatoric set of paths)

Quote: Original post by SimonHx
Can't you just get the optimal path then mark every 10th node as 'blocked' and path again? The new path will be at least 10% different...
Mind you, you might get a situation where a node MUST be used to get a path at all, so you'd have to allow for that... In the worst case (ie a maze with just one path through it) ALL the nodes must be used, so a 10% different path would be impossible!

Yes, that's the current approach that I inherited. I'm trying to find ways to make it faster. That approach also doesn't guarantee the best path that is 10% different, just *a* path that is 10% different.

Quote: Original post by wodinoneeye
I would say find the optimal path (chain of nodes) and then generate paths for a terrain where you block nodes along that path. Do single nodes blockage first to see if any qualify as N% different then if needed test a conbination set of 2 nodes blocked (3 etc...)

Right, that's the current approach. It takes quite a long time and still doesn't guarantee the best path that is N% different than the optimal path.

Quote:
Sounds like an arbitrary homework assignment (cant think immediately why you would want such a limitation in a real use)

Heh, no, I'm well out of college (I'm 28). This is for existing production software.

Quote:
Rethinking it, the open list would have all the node path ends which were less than optimal and you could continue pulling them as candidates to move to completing the path. You would save the length/cost of the optimal and throw out completed paths that overlap less than N% different and return all those with a larger difference (which would probably be rather alot of them : 100% - N% using your N=10 means 90% of all valid paths would have to be returned -- depending on your node count could be a very large combinatoric set of paths)

Yea, reusing the information in the open list is one of the things I wanted to explore. I'll definitely keep looking in that direction.

I was really hoping that there existed a few papers on the subject and I just didn't know what keywords to look for.

You probably need to rethink your requirements. Is the 10% difference really what's important to you? Or is what's important to you more a matter of the path going different ways around obstacles, and other such more substantive changes?

You could also make the heuristc incorrect, which could result in a desired path.

Quote: Original post by Sneftel
You probably need to rethink your requirements. Is the 10% difference really what's important to you? Or is what's important to you more a matter of the path going different ways around obstacles, and other such more substantive changes?

That is the intended result. As to whether or not the actual 10% matters, I'd have to ask the subject matter experts...

Right now users enter in the percent difference they require the alternative paths to be. I'm not sure how users come up with their percent different requirements.

Couldn't you increase the weights along the path that was found by some value in order to encourage the path finder to use other edges? You don't need to block them, but if, for example, you increased the weights along the optimal path by 5% at a time until you get a path that is X% off, that would probably be faster and more accurate than actually blocking nodes.

If you're looking for a series of different paths as you say later in the OP, instead of increasing the weight along the optimal path, increase the weights along all previously-found paths, so that those edges are less likely to be reused in future paths.

You could also start each path by randomly weighting all edges by (for example) +-10% of their original weight so that the paths will vary automatically.