Pathfinding, and perturbing source and destination
April 20, 2010 09:45 AM
Is there a way to use A*, or a variant of A*, to perturb the source and destination nodes slightly without having to fully re-plan each time? That is, given that I've already gone to the trouble of finding a shortest path from position (15,35) to position (80, 5), a way to reuse most of the computation to find a shortest path from (10,35) to (80,5), or a path from (15,35) to (85,5)? This would be repeated over time, with the source and destinations tending to wander around.
If it matters, it's a bidirectional 2D euclidean graph.
21,604
April 20, 2010 11:37 AM
Reusing part of the computation to find a slightly different goal should be possible. At the end of your original A* run, you'll have an open list with a value assigned to each element which is the cost of getting there plus the heuristic estimate of the cost to go from there to the goal. You could traverse that struture adding (heuristic(P, new_goal) - heuristic(P,old_goal)). Your open list is probably a heap, so you'll have to rearrange things so it continues to be a heap. Then you can resume A* from there.
If your new goal happens to be in your closed list, you don't even have to do any of that.
I can't think of a way to reuse the results of a previous A* search if the starting node changes a bit. You could find a path from the new starting point to the old one and that would give you upper bounds on how much effort it would take to get to many places, but I'm not sure how to exploit that data in a clean way.
If your new goal happens to be in your closed list, you don't even have to do any of that.
I can't think of a way to reuse the results of a previous A* search if the starting node changes a bit. You could find a path from the new starting point to the old one and that would give you upper bounds on how much effort it would take to get to many places, but I'm not sure how to exploit that data in a clean way.
648
April 20, 2010 11:55 AM
Given the example you gave, it may be possible to just rescale, translate, rotate the path onto the new start/destination and check its validity.
April 20, 2010 12:00 PM
Quote: Original post by alvaroYeah, I got that part. Actually, I think there may be a way to do it without reprocessing the open list at all, by redefining the heuristic, but I'm still trying to convince myself that the resultant heuristic is admissible, and that the results of several successive perturbations don't lead to a poor heuristic. The idea would be to find the path from old_goal to new_goal, and the new heuristic is the old heuristic minus that cost; the old f values, therefore, are still accurate, though more pessimistic than before.
Reusing part of the computation to find a slightly different goal should be possible. At the end of your original A* run, you'll have an open list with a value assigned to each element which is the cost of getting there plus the heuristic estimate of the cost to go from there to the goal. You could traverse that struture adding (heuristic(P, new_goal) - heuristic(P,old_goal)). Your open list is probably a heap, so you'll have to rearrange things so it continues to be a heap. Then you can resume A* from there.
Quote: I can't think of a way to reuse the results of a previous A* search if the starting node changes a bit. You could find a path from the new starting point to the old one and that would give you upper bounds on how much effort it would take to get to many places, but I'm not sure how to exploit that data in a clean way.The upper bound is useful, because you can basically run a single iteration of IDA*. But yeah, I agree that that's the harder of the two perturbations. The closed list is no longer accurate.
April 20, 2010 12:03 PM
Quote: Original post by bzroom
Given the example you gave, it may be possible to just rescale, translate, rotate the path onto the new start/destination and check its validity.
Sorry, I should clarify: It's euclidean graph, but not a dense euclidean graph. Transforming the path is likely to result in vertices which do not exist in the graph.
21,604
April 20, 2010 12:47 PM
Quote: Original post by Sneftel
The upper bound is useful, because you can basically run a single iteration of IDA*. But yeah, I agree that that's the harder of the two perturbations. The closed list is no longer accurate.
Oh, I see. I didn't think of using IDA* for this, but it sounds like a good idea.
157
May 01, 2010 07:30 AM
Here's an idea: given a perturbation of size d and some constant k, walk back up the existing path from the target until distance traveled exceeds d * k and search anew from there. This won't give you the best possible path, but (given some reasonable assumptions) it will be off by a bounded distance. Full search can be run every N iterations to limit the degradation of path quality.
The assumption is that the new location is close to the old one in search space, which may not always be the case. Consider an agent A that can walk through water, being chased by B who cannot. A crosses a stream and the small change in A's position could produce arbitrarily large changes in the optimal path as B searches for a bridge or similar. Search-avoiding tricks would produce terrible paths in that case, although it might be possible to detect such short circuiting of the search space to trigger a full search when necessary.
The assumption is that the new location is close to the old one in search space, which may not always be the case. Consider an agent A that can walk through water, being chased by B who cannot. A crosses a stream and the small change in A's position could produce arbitrarily large changes in the optimal path as B searches for a bridge or similar. Search-avoiding tricks would produce terrible paths in that case, although it might be possible to detect such short circuiting of the search space to trigger a full search when necessary.
458
May 02, 2010 04:54 AM
How about just running Dijkstra locally around the source and destination, to see which points are accessible nearby (set a limit number of expansions). Then pick a point within the area that has been covered...
You can then generate the new path by concatenating the two Dijkstra runs with your A* path, though the result may require local re-smoothing to look realistic.
You can then generate the new path by concatenating the two Dijkstra runs with your A* path, though the result may require local re-smoothing to look realistic.
Join us in Vienna for the nucl.ai Conference 2015, on July 20-22... Don't miss it!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
