Pathfinding, and perturbing source and destination

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.

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.

Quote:

Original post by alvaro 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.

Yeah, 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.

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.

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.

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.

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.

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.