Related to issue937 and issue998.

I have merged and resolved this issue.

I have addressed the comment in the pull request and added a changelog entry.

Forgot to mention: I did leave a comment on the pull request regarding a comment, and this needs a changelog entry before it can be merged.

Forwarding the link to the pull request from Discord: https://github.com/aibasel/downward/pull/90

The pull request looks good to me. There are a few things I'd do differently if the code were to stay, but the things I dislike are inherited from the existing code, so no problem there.

I looked into how infinite costs are handled in other parts of the search code, and use how the search handles infinite heuristic values as an example here:

Before grabbing the actual value the search always calls is_dead_end to catch infinite values. The landmark code we consider here does this as well, although in a somewhat unsafe way (we don't directly check each landmark cost, we check if the first achievers are empty, but at least conceptually this should be the case exactly if cost is infinite). After checking for dead_ends the search can access the evaluator value over a function of EvaluationContext; and in this function we also only have an assertion.

Given this I'd say that an assertion should be fine in our case as well.

Salomé, Remo and I talked about this yesterday and decided to just try Salomé's suggestion from msg10488. We're now 100% sure that the cost of landmarks is only used in the inadmissible LM-count. We now check whenever the heuristic is computed, whether one of the unreached or required again landmarks has cost infinity with an additional if-clause. If this is the case, we return a heuristic value of infinity.

The experiments show that this might not be the best option, because it affects the search time negatively. 

https://ai.dmi.unibas.ch/_tmp_files/buechner/issue467-v1-satisficing-compare.html

We had the hypothesis that branch-prediction might prune this conditional, but the numbers indicate this was wrong. 

As discussed in msg10486, the only reason why landmark costs are set to infinity should be because it has no first achievers. Since the function *dead_end_exists* already captures this case and returns an infinite heuristic value, we actually know that in the current code-base, the new if conditional will never trigger. Therefore, it's wasted effort to even have it. My suggestion now is to just assert that cost is finite when we sum up the heuristic value. 

Ultimately, this means we tackle this issue by simply moving the assertion. Instead of asserting when computing the cost (where we know it can be infinite), we assert when we add up the costs (where we know they should be finite).

Hmm good point. The lmcount code doesn't handle infinite values separately. I am fairly sure that we would actually never end up adding infinite values, because if the set of first achievers is empty, the dead-end will be detected before we touch the cost attribute. But that of course doesn't mean its ok like this.
(I'm not 100% sure because when computing the cost attribute the set of first achievers is not computed yet and we do an independent computation there.)

I think the easiest fix would be to explicitly allow infinite for this cost variable and handle the case of infinite value separately wherever cost is used (should only be in the inadmissible part of lmcount but I'm not 100% sure). For anything more elaborate I think we first need to have this discussion about what we want to do with the cost attribute in general.

> The assertion can fail if no first achiever exists, all first achievers have infinite cost,
> or the landmark is empty. (I assume the first is what happens here, but the other two are
> at least theoretically possible.)

Thanks! The first one is possible. The second one isn't; actions must have finite non-negative cost. Regarding the third, a landmark is currently either an atom, a disjunction of two or more atoms, or a conjunction of two or more atoms -- I don't think there is such a thing as an "empty" landmark.

Generally speaking, a "cost" in our code is usually meant to be a finite number. There are some specific places where we support specific representations for infinities, but most of the code relies on finiteness. If we want to allow infinite values in more places than before, we need to make this clear in the inteface and change the code using these places to support infinities. This usually doesn't work without code changes. For example, adding two costs breaks if one of them is infinite unless we handle the case specially. This is why these assertions exist.

Clemens, Remo and me looked into this issue in the context of issue937.

To summarize what happens: lm_rhw sets the "cost" attribute for landmarks by basically computing all *first* achievers   and taking the minimum cost amongst them. The assertion can fail if no first achiever exists, all first achievers have infinite cost, or the landmark is empty. (I assume the first is what happens here, but the other two are at least theoretically possible.)

We would argue that if we want to keep this first-achiever semantic, then just getting rid of the assertion is correct, i.e. in all three cases listed above it's valid to say achieving the landmark the first time has infinite cost.

Whether or not we want to keep this first-achiever semantic is a different question. It does currently not cause issues for landmarks that are true in the initial state (see msg9027), since the code only sets the cost attribute for landmarks that are *not* true in the initial state (otherwise it defaults to 1). It will of course make the heuristic inaccurate when the landmark is required again, but since the cost attribute is only used in the inadmissible setting I guess we can live with that.

In summary, our suggestion is to just remove the assertion. As already discussed in other issues the cost attribute should probably be removed or at the very least rethought at some point, but I would do this in a different issue.

When dealing with this, we have to be careful with landmarks that are true in the initial state, because these do not need achievers. Landmarks that are true in the initial state are permitted and may potentially become useful in future revisions of the landmarks code (that implement the "sensible orderings" we discussed).

Given that this error occurs inside the lm_rhw landmark factory but is based on a symptom that might equally trip up other landmark generators, we should also check the other landmark factories for similar problems.

I have added a link to issue937 in the summary, which is another problem that arises when the landmark code detects unsolvability.

Like Erez suggested five short years ago, I think the most direct way to address this is to give the landmark graphs a way to mark a problem as unsolvable and then skip parts of the processing that can misbehave on unsolvable problems.

For unsolvable problems, we can skip all further processing and perhaps discard unnecessary information like the landmark nodes etc. Instead, we could have the heuristic always return infinity.

Once we have such a facility, it could also be used to address issue937.

I think it would be good to address this one in the not-too-far future because
it is showing up in some of our experiments (see issue837), and failed
assertions aren't great. :-)

I think it should remain open. I'm not sure how soon we'll be able to work on
the landmark code, but I think it should be one of our main priorities.

I added the comment in the master branch. Should we set this issue to deferred,
resolved or leave it open?

Sounds like the landmarks are detecting that the problem is unsolvable, but not 
expecting that. As part of the refactoring it might be good to add an option for 
detecting unsolvability.

Please add a comment to this assertion explaining where it fails. It may not be
a good idea to try fixing this locally. The landmark code needs some more global
revisions.

The following assertion fails for the unsolvable tasks that are created if the
translator detects unsolvability.
To reproduce, search with "astar(lmcount(lm_rhw()))" on mystery/prob07.pddl in
debug mode.

landmarks/landmark_factory_rpg_sasp.cc:109: int
LandmarkFactoryRpgSasp::min_cost_for_landmark(LandmarkNode*,
std::vector<std::vector<int> >&): Assertion `min_cost <
numeric_limits<int>::max()' failed.