Can we combine weights with heuristics? (A* with monus-weighted-search)

[ocharles]

I'm interested in monus-weighted-search is the context of searches with heuristics - specifically A search. I understand A search as an extension of Dijkstra's algorithm where we track the cost of the path so far, but we weight our node expansion with a heuristic (the estimated remaining cost to the goal).

My attempt so far is to work with

data Cost a = Cost a (Maybe a)

Here, the first a is our incurred cost, and the second Maybe a is our estimated total cost to the goal, with Nothing meaning an infinite cost. Ordering is defined as ordering on the sum of the cost and estimate, and the monoid operation is the product of Sum and Min monoids (so combine costs, and take the minimum estimated cost).

However, I'm stuck on a sensible Monus for this (if there is any at all). My intuition as to what is happening in monus-weighted-search is we essentially have a forest of trees to explore. When we use popMin, we find a root in this forest with the lowest weight, and then sort of "splice in" the siblings of that root, and adjust all other roots with |-| to decrement their weight. In this case, I would have to reduce the cost and estimate for each node, but I'm not sure that can be done with |-| as |-| is commutative, and this operation isn't:

Cost a a' |-| Cost b b' = Cost (a |-| b) (a' |-| (fmap (|-| a) a')

Notice that we had to choose a for the new final Cost, completely ignoring b'.

Were |-| no longer commutative, I think this could work, however. The only assumption is commutativity appears in <||>:

(x, xv) <||> (y, yv)
  | x <= y    = (x, HeapT (ListT (pure ((x |-| y :< yv) :- runHeapT xv))))
  | otherwise = (y, HeapT (ListT (pure ((x |-| y :< xv) :- runHeapT yv))))

Notice how both branches call x |-| y. I think if we instead did:

(x, xv) <||> (y, yv)
  | x <= y    = (x, HeapT (ListT (pure ((x |-| y :< yv) :- runHeapT xv))))
  | otherwise = (y, HeapT (ListT (pure ((y |-| x :< xv) :- runHeapT yv))))

then things might work out.

Alternatively, maybe it's better to instead have something like:

HeapT w m a = ListT m (Node (w, Maybe w) a (HeapT w m a))

where each Node now has a cost and an estimate, allowing us to operate on the estimated cost independently.

I'd love to hear your thoughts!

[ocharles]

Aha, I just read in the conclusion of the paper:

One drawback of our approach is that it does not seem possible to formulate a monus for heuristic-augmented search algorithms, like A*: we would be interested in generalisations of the monus algebra which might allow for the inclusion of such heuristics

[oisdk]

Yes, unfortunately I can't figure out a way to add heuristics to the weight. The issue isn't just that |-| isn't commutative, it's that there's no implementation of |-| that satisfies:

(x <> y) |-| y = x

I haven't looked into the issue in a while, so I might be misremembering, but I am pretty sure that there's no general Monus (a,b) given Monus a and Monus b.

My intuition for how to add heuristics is not to pair them up with the weight, but rather to put them in a different part of the algorithm altogether.

[ocharles]

My intuition for how to add heuristics is not to pair them up with the weight, but rather to put them in a different part of the algorithm altogether.

Yea, I did also consider this (re-evaluate the heuristic at each popMin call) but I couldn't see a way to extract any information from each HeapT subtree to compute a heuristic with.