Clemens, Remo and me discussed this and related issues today. As far as we can tell there are three mechanisms for detecting unsolvability (two of which Thomas mentioned below already):
a) A landmark with no first achievers that is false in the initial state (issue467)
b) Cycle with natural (or stronger) orderings (issue937)
c) lm_zg returns an empty graph when the task is not relaxed solvable (issue998)
We discussed two possible approaches to deal with this:
1. Add a flag in the landmark graph denoting that the task is unsolvable. The heuristic can then first of all check this flag and return infinity if the flag is set to true. For b) and c) this is straightforward. For a) we need to have access to the initial state during the graph construction, but we assume this should already be the case (or at the very least should be easy to add).
2. Encode the information in the "cost" attribute of Landmark Nodes and ensure that heuristics deal with it properly. However, the code is inconsistent in how it uses the cost attribute: it is by default set to one, only set explicitly by lm_rpg_sasp and only used in the inadmissible lm-count heuristic.
- For a) we at first thought this is straightforward (if it has no achievers, cost is infinite). But there is a difference between "no achievers" and "no first achievers": If for example a landmark has achievers but no first achievers and is true in the initial state, then setting the cost to infinity would be wrong. So I think the only way to encode a) in the cost is to again have access to the initial state and only set the cost to infinite if the node either has no achievers, or has no first achievers and is false in the initial state. Or have different cost attributes for first/all achievers...
- For b) we could set the cost of all landmarks that are part of the cycle to infinity. This somewhat abuses the cost semantics.
- For c) ther are no nodes to begin with. But we could either force the heuristic to return an infinite estimate if no landmarks are present (although this in my opinion is not really the intended semantics of an empty graph), or we could instead of an empty graph return a graph containing the goal landmarks that are relaxed unreachable, and assign infinite cost to them.
I initially though option 2 would be more elegant, but there are many issues: unclear semantics of "cost" attribute (first or all achievers), it is only used in one factory and for inadmissible heuristics, plus the suggested way to encode b) and c) feels hacky. Option 1 is definitively easier and also more straightforward, with it's main downside being that we need to check an additional (static after graph construction) flag every time we compute the heuristic. But given that we currently loop over all landmarks in every state for checking if the (first) achievers are empty I assume that it will not make a big dent in performance, especially if stuff like branch prediction might trigger here (I have no idea if this is the case; if someone has more insight on these types of optimization we'd greatly appreciate the input).
One last remark about the per-state checks: While we can move the check on whether the set of first achievers is empty into the factory, we should still do a per-state check whether the set of (all) achievers is empty and the landmark is false and needed again. We could however consider to store a list of all landmarks with no achievers in the landmark graph, and instead of iterating over all landmarks, we check for needed-again landmarks if they are in this list. Or, if we decide to properly use the cost attribute we could also encode it in there.
|