[BGL] Question/suggestion about example/astar-cities.cpp
Hi, I had a look at the A*-search documentation and example code provided by boost (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/astar_search.html). In the example code, an exception is thrown as soon as the examined vertex is equal to the goal-vertex. Now I am wondering if this example is adequate because, as far as I have thought about it, this solution must not necessarily fullfill the characteristics of the A*-algorithm as it might lead to a premature abort (indeed actually intended) and thus could miss an optimal solution. Simple scenario: A graph with 3 vertices: one start, one goal, one intermediate and 3 edges: (start, goal), (start, intermediate), (intermediate, goal). If the weights are "similar enough" and the heuristic might be beneficial for the direct edge (start, goal), the program will throw the error when it examines the goal vertex, while actually it might have been optimal to take the route over the intermediate-vertex. This is not intended to be picky. I just sat on the example (or a custom modification to it) for quite some time now, wondering if my thoughts are correct. If they are, I think a short comment/note might help to clarify the situation for future readers, perhaps getting unexpected results on their own. Please correct me if I missed some point there. Thank you. Best, Cedric
Hello! I have not yet used BGL, but think there is a requirement on the heuristic missing in the documentation. See below: On 2011-03-30 15:16, Cedric Laczny wrote:
I had a look at the A*-search documentation and example code provided by boost (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/astar_search.html). [...] Simple scenario: A graph with 3 vertices: one start, one goal, one intermediate and 3 edges: (start, goal), (start, intermediate), (intermediate, goal). If the weights are "similar enough" and the heuristic might be beneficial for the direct edge (start, goal), the program will throw the error when it examines the goal vertex, while actually it might have been optimal to take the route over the intermediate-vertex.
So, in your example: w(start, goal) < w(start, intermediate) + w(intermediate, goal) At the start of the second iteration of the while loop in the pseudo-code we have: Q = { intermediate, goal } f(intermediate) = w(start, intermediate) + h(intermediate) f(goal) = w(start, goal) + h(goal) = w(start, goal) Now, for goal to be examined prematurely we would need to choose u = goal at the line u := EXTRACT-MIN(Q) in the pseudo-code. But, given that f(intermediate) <= f(goal), we will choose u = intermediate. I think the documentation is indeed lacking there: The "<=" is only guaranteed if the heuristic does not overestimate the distance to the goal, which is a requirement of A* to (reliably) work. I could not find that mentioned within the documentation. Hope that clears it up. Cheers Thomas Luzat -- Thomas Luzat Softwareentwicklung USt-IdNr.: DE255529066 Kaiserring 2a Mobile: +49 173 2575816 Web: http://luzat.com 46483 Wesel Fax: +49 173 502575816 E-Mail: thomas@luzat.com
On Wednesday, 30. March 2011 17:43:17 Thomas Luzat wrote:
Hello!
I have not yet used BGL, but think there is a requirement on the heuristic missing in the documentation. See below:
On 2011-03-30 15:16, Cedric Laczny wrote:
I had a look at the A*-search documentation and example code provided by boost (http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/astar_search.html).
[...]
Simple scenario: A graph with 3 vertices: one start, one goal, one intermediate and 3 edges: (start, goal), (start, intermediate), (intermediate, goal). If the weights are "similar enough" and the heuristic might be beneficial for the direct edge (start, goal), the program will throw the error when it examines the goal vertex,
while actually it might have been optimal to take the route over
the intermediate-vertex.
So, in your example: w(start, goal) < w(start, intermediate) + w(intermediate, goal) At the start of the second iteration of the while loop in the pseudo-code we have:
Q = { intermediate, goal } f(intermediate) = w(start, intermediate) + h(intermediate) f(goal) = w(start, goal) + h(goal) = w(start, goal)
Now, for goal to be examined prematurely we would need to choose u = goal at the line u := EXTRACT-MIN(Q) in the pseudo-code. But, given that f(intermediate) <= f(goal), we will choose u = intermediate. I think the documentation is indeed lacking there: The "<=" is only guaranteed if the heuristic does not overestimate the distance to the goal, which is a requirement of A* to (reliably) work. I could not find that mentioned within the documentation.
Hope that clears it up.
Yes, thank you for this nice explanation. More formally, this seems to come down for the heuristic to be at least admissible, or even stronger, to be monotonic or consistent. I found that out only later on. Given the case of an overestimating heuristic, if the program aborts upon examination of the goal, it might miss the optimal path due to the overestimation. However, when it runs as long as the queue Q is not empty, I think it should find the optimal path nevertheless, although possibly reopening the closed goal-vertex. What do you think about that?
Cheers
Thomas Luzat
-- Thomas Luzat Softwareentwicklung USt-IdNr.: DE255529066 Kaiserring 2a Mobile: +49 173 2575816 Web: http://luzat.com 46483 Wesel Fax: +49 173 502575816 E-Mail: thomas@luzat.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Best, Cedric
On Mar 30, 2011, at 12:28 PM, Cedric Laczny wrote:
Yes, thank you for this nice explanation. More formally, this seems to come down for the heuristic to be at least admissible, or even stronger, to be monotonic or consistent. I found that out only later on. Given the case of an overestimating heuristic, if the program aborts upon examination of the goal, it might miss the optimal path due to the overestimation. However, when it runs as long as the queue Q is not empty, I think it should find the optimal path nevertheless, although possibly reopening the closed goal-vertex. What do you think about that?
Not sure, but I think you might just use Dijkstra's shortest-path algorithm in that case. Will be faster than looking at all paths and still minimal.
participants (3)
-
Cedric Laczny -
Gordon Woodhull -
Thomas Luzat