Finding path back from the goal does not work when the graph has loops

[tsahyt]

When given a graph that has loops on every vertex, the aStar function never returns, even after a path has been found. The actual search seems to succeed, but building the path back to the start never finishes.

As a minimal example, I've been able to reproduce the problem with this (with S denoting Data.HashSet):

ghci> aStar (\x -> S.fromList [x, x - 1, x + 1]) (\_ _ -> 1) (const 0) (== 10) 1

ghci then hangs on Just. This indicates that the goal has been found and that the problem occurs in line 78 (or 133). It happens for both the monadic and normal versions of the function.

[cloudhead]

x shouldn't be considered adjacent to x, should it?

[tsahyt]

That depends entirely on the underlying state space. In general, graphs can have loops, i.e. nodes which are their own successors. The original A* paper does not exclude such graphs, and to my knowledge most other A* implementations work for graphs that have loops. The original A* paper is unfortunately behind a paywall, so I'll cite the relevant definition here

A graph G is defined to be a set nodes and a set {e_ij} of directed line segments called arcs. If e_pq is an element of the set {e_ij}, then we say that there is an arc from node n_p to node n_q and that n_q is a successor of n_p.

Note that this does not exclude arcs e_ii for node n_i. Of course, using such an arc would yield a suboptimal solution (assuming it has cost > 0), but the algorithm should still work regardless. Indeed, as formulated in the paper it does work. I'd argue that it should at least be noted somewhere (e.g. Haddock documentation) that this implementation only works for graphs without loops.

[cloudhead]

Ah I wasn't aware of the terminology there, thanks.