3
$\begingroup$

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent.

Suppose I already know of a path whose length is guaranteed to be at most 1.1 times as long as the shortest path. Does this help A* find the shortest path faster? If so, how and why? Can knowledge of this path be used to improve the running time of A*, reduce the number of nodes, or make the heuristic more accurate?

One improvement I can see is to remove the all the nodes in the open list which exceed the current solution. But if the heuristic is weak, this wouldn't help in reducing the number of nodes to be explored in the open list. So, in what other ways one can use the knowledge of known path in hand to help A* terminate itself earlier than without the knowledge of known complete path.

$\endgroup$
1
$\begingroup$

In order to prove that the solution is optimal, with a consistent heuristic A* needs to expand all states with f < f* (the perfect solution cost) and it also may expand some states with f = f* so it seems hard that knowing an upper bound on the number of expansions can help to reduce the number of node expansions without modifying the heuristic.

A potential way of helping A* in this context may be that of heuristic selection. That is, in cases where more than one heuristic is available, meta-reason about what subset of heuristics should be used [1,2].

In this scenario it could be possible to use the sub-optimal path to select which ones to use (e.g., it may be worth it to compute more expensive heuristics because they have greater chances of pruning the node). However, this is an open problem and I'm not aware of any work on that direction.

[1] David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas: Toward Rational Deployment of Multiple Heuristics in A. IJCAI 2013: 674-680

[2] Levi H. S. Lelis, Santiago Franco, Marvin Abisrror, Mike Barley, Sandra Zilles, Robert C. Holte: Heuristic Subset Selection in Classical Planning. IJCAI 2016: 3185-3191

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.