Merged.

I added a little print message to check-exitcodes.py, so please pull again. You 
can merge the branch now from my point of view.

I will add the buildbot test in the master branch.

Can you push your latest changes again?

Thanks for the comments, Jendrik, I implemented most of them.

I am happy to merge. Any objections?

Not me, please. :-) (Happy to merge when you are.)

Thanks for the offline feedback. Could anyone have a (hopefully final) look at
the overall patch introduced in the issue's branch?

An admissible heuristic implies that dead ends are reliable, so if it's
admissible, they definitely are reliable.

Moreover, they're also reliable in cases where we don't use cost partitioning
(admissible=false), but the other requirements for admissibility are met.

Thanks for the feedback. I updated the code accordingly.

Concerning your msg3167, I assume you referred to my comment at msg3162, rather
than msg3164, thus I also updated the documentation for lm_count according to my
suggestion in msg3162.

I hope the documentation and the corresponding tests to accept or reject tasks
with conditional effects/axioms is correct now.

Going back to the original question of this issue, see msg3023 and msg3025, I
wonder what the correct documentation and behaviour is for the lm count
heuristic: are dead ends always not reliable for the heuristic? Or are dead ends
reliable under the same conditions the heuristic is admissible? Or something else?

I added my comments on the pull request, and what you wrote in msg3164 makes
sense to me.

In general: I don't really know these landmark generation methods either. This
is all old code that dates back to Silvia's work for the AAAI 2008 paper, or
even earlier stuff from Matthias's "Studienarbeit". So we probably need to look
at the code. I'm happy to do this, but not right now.

In the meantime, I'm fine with any temporary solutions that work for you.


For this specific comment: for example if you ignore a precondition, you can
only shrink the set of landmarks, but never grow it, since it's a problem
simplification (all plans still work, but additional action sequences might
become plans that previously weren't). So everything that is a landmark after
the simplification (is contained in all plans and some non-plans) also is a
landmark before the simplification (is contained in all plans).

Does the same hold if we ignore effect conditions rather than preconditions? It
depends on how clever or stupid the algorithm is. I think most of our LM
detection methods more or less consider each effect in isolation, i.e., more or
less treat each operator as a bunch of unary operators. (which doesn't work for
all kinds of purposes, but works at least for certain kinds of LM generation
techniques based on delete relaxation, because in delete-free problems,
splitting each operator up into individual effects is safe.) Then ignoring
effect conditions is not really different from ignoring preconditions, and
should be "safe".

I understand this part and it makes sense. I was rather wondering to the text
that followed this definition: 

"It *may* be the case that
for some of our LM generation methods, "supporting" conditional effects could be
as simple as ignoring the effect conditions. (It probably is.)"

That means that I am not sure anymore whether the properties of certain landmark
factories we discussed below are correct or not. For example, we said
lm_exhaust()
conditional effects: ignored
but that means that lm_exhaust *may support* conditional effects according to
our definition. Can we infer this from the way how the landmark generation
methods work (I am not familiar with them conceptually) or do we have to find
this out by looking at the code?

Well, we first need to decide what *we* mean by supports. I suggested a
definition in the text you refer to:

'I think a landmark approach "supports conditional effects" (or axioms, etc.) if
the landmarks and achievers it produces are correct (i.e., the landmarks are
actually landmarks, and all possible first achievers and
achievers are included in the computed sets of possible first achievers and
achievers).'

Does this make sense to you? (I think it makes sense in so far as this is what
we need for admissibility, goal-awareness, etc.)

(Also, this definition should be extended to also mention orderings, but let's
discuss that separately.)

I updated documentation according to the messages from below and added various
TODOS/questionmarks. I further added a "supports conditional effects" flag to
the landmarkgraph class.

Could you please have a look at the pull request at jendriks bitbucket repo?

Regarding point 3) of msg3097, I don't know how I can "find this out". What do I
need to know about the landmark generation methods in order to understand if
"ignoring conditional effects" means "supporting" them or not?

Leaving this aside for the moment, the lmcount heuristic had the following
documentation for admissible so far:
yes if `admissible=true` and there are neither conditional effects nor axioms

From my understanding of the previous messages, this should be updated to:
yes if 1) admissible=true, 2) there are no axioms, and 3) there are no
conditional effects or the chosen landmark generation method supports
conditional effects.

Is that correct?

Assigning this to Silvan since he agreed to work on the landmarks part of the 
issue. The other heuristics (h^max, h^add, h^ff, h^m) already correctly supply 
information about safeness (in the issue branch).

Three points (mostly minor):

1) I'd prefer to spell this out as "supports_conditional_effects".

2) I'd prefer an API with getters as opposed to setters. Mutating methods are a
bit awkward and error-prone, I think. (For example, I'm worried about potential
ordering dependencies in the merged landmark graphs; if we merge two landmark
graphs of which one supports conditional effects and the other doesn't, will the
one which is added last win?) So it may be nicer to have just a getter in the
landmark factory instead. But this may be something we can defer to the landmark
refactoring effort if it's currently awkward to implement. But in this case
please add a code comment to reconsider this design later.

3) You should clarify what "supports" means. "Take into account" is not really a
workable definition. I think a landmark approach "supports conditional effects"
(or axioms, etc.) if the landmarks and achievers it produces are correct (i.e.,
the landmarks are actually landmarks, and all possible first achievers and
achievers are included in the computed sets of possible first achievers and
achievers). This should be said explicitly somewhere. It *may* be the case that
for some of our LM generation methods, "supporting" conditional effects could be
as simple as ignoring the effect conditions. (It probably is.)

The second paragraph should probably be
LandmarkGraph::set_supports_cond_effs(bool supported).

LandmarkGraph::supports_conf_effs() should return true if the factory/factories that created the 
graph take conditional effects into account (this was our definition of "support"). This method is 
called by the lmcount heuristic when the heuristic checks whether it supports the task at hand and 
when LandmarkCountHeuristic::are_dead_ends_reliable() is called.

LandmarkGraph::supports_conf_effs() would be called by the landmark factories when they create the 
graph. A factory that doesn't support cond-effs cannot directly abort the program for tasks with 
cond-effs since it doesn't know whether admissible=true or admissible=false.

I don't understand the intended semantics of the two methods. Also, who would
call them and for what purpose?

Silvan and I just discussed the implementation and we see two options:

a) Add set_supports_cond_effs(bool supported) and supports_conf_effs() methods to the LandmarkGraph class. Ideally, we would like to put this information in into the factories, but we cannot use the 
LandmarkFactory class since the heuristic only sees the LandmarkGraph instances).

b) Ignore the landmarks code for this issue and keep this issue in mind when refactoring the landmarks code.

We would both prefer option a). What do you think, Malte?

Thanks, Silvan. The basis for msg3040 was that Jendrik and I agreed to call
verify_no_axioms and verify_no_conditional_effects when admissible=true, to
avoid potentially getting an inadmissible heuristic. So the remaining properties
(e.g. consistency) would be predicated on the assumption that there are no
conditional effects or axioms. But I'm not 100% sure about consistency even
then. Better be explicit about our doubts and write something like "consistency:
complicated; needs further thought" and add a TODO to the code.

I had a look at the code and found the properties for lm_merged(), lm_rhw(),
lm_zg(), lm_exhaust() and lm_hm() to be meaningful (i.e. no conditional effects
used/mentioned in the sources for lm_exhaust() and lm_hm()). The general
landmark factory class tests for conditional effects at several places, but only
to find out if certain effects 'always happen' (i.e. unconditionally on a given
effect condition) or if a landmark is unconditionally achieved by an operator.
So there is no conditional effects support for the landmark factories, unless
the instantiation supports them, as far as I found.

For the lmcount heuristic, I cannot fully confirm msg3040 from looking at the
code. For example, it is not clear to me if the heuristic is consistent in the
cases mentioned and what the impact of "admissible=fals/true" is on the support
of conditional effects and axioms. But if I understand it correctly, you
discussed this offline, so I am happy to trust the documentation for lmcount in
msg3040 (but it definitely needs to be updated in the code and the case
mentioned in msg3026 should be fixed).

Let's talk about this tomorrow offline. I have already started, but let's work on 
this together.

> I don't know the code enough to say whether it makes sense or not, but I could
> have a look at the lm factories, if required.

This would be useful!

> Are you sure that the properties as stated in msg3035 and msg3040 are correct?

No.

> Has the documentation been updated anywhere already?

If Jendrik hasn't done it yet: no. (We only have one source for the
documentation now: the C++ source. The web documentation is generated from this.)

I don't know the code enough to say whether it makes sense or not, but I could
have a look at the lm factories, if required.

The code in the pull request looks fine, but it does not contain the
documentation changes and, as Malte said, these conceptual things are anyway not
an issue of the code in the first place. Are you sure that the properties as
stated in msg3035 and msg3040 are correct? Has the documentation been updated
anywhere already?

I'd put it a bit differently:

conditional effects: supported if the LandmarkGraph supports them; otherwise
ignored with admissible=false and not allowed with admissible=true
axioms: ignored with admissible=false; not allowed with admissible=true
consistent: yes with admissible=true and optimal cost partitioning; otherwise no
safe: yes except on task with axioms or on tasks with conditional effects when
using a LandmarkGraph not supporting them

Does that make sense?

Malte, could you please check if I understood you correctly in our offline discussion? (the notes for the LandmarkGraphs stay the same)

lmcount()
conditional_effects: supported if admissible=false or if the LandmarkGraph supports them
axioms: supported if admissible=false (but may behave stupidly)
admissible: yes if admissible=true and there are no conditional effects or the LandmarkGraph supports them
consistent: no
safe: yes (except on tasks with axioms or conditional effects)

Checking the details of this would require a close look at the current code -- I
don't think I have time to help with this.

In general terms, this doesn't look fully consistent with what we discussed
earlier. Didn't we say that the admissible heuristic should reject tasks with
conditional effects until they are properly supported (see msg3026)? The
suggested new documentation suggests otherwise (e.g. that conditional effects
with admissible=true and lm_rhw are supported). And in which sense can we say
that conditional effects are supported if admissible=true and the landmark
factory doesn't support them?

Maybe it's best to fix the documentation first and update the dead_ends_are_reliable() code later. This is my current understanding of 
things. Is it correct? Can we concretize or omit the "maybe" below?

lmcount()
conditional_effects: supported if admissible=false or if the LandmarkGraph supports them
axioms: supported if admissible=false (but may behave stupidly and lead to an unsafe heuristic)
admissible: yes if admissible=true and there are neither conditional effects nor axioms
consistent: no
safe: yes (except maybe on tasks with axioms or if admissible=true on tasks with conditional effects using a LandmarkGraph that doesn't 
support them)

lm_merged()
conditional effects: supported if all component LandmarkGraphs support them

lm_rhw()
conditional effects: supported

lm_zg()
conditional effects: supported

lm_exhaust()
conditional effects: ignored

lm_hm()
conditional effects: ignored

I guess it's best to document the LM heuristic's properties as depending on the
LM factory, and add notes to the LM factories regarding their properties.

By looking at the code I would say that lm_rhw and lm_zg take effect conditions 
into account while lm_hm and lm_exhaust do not.

Any volunteers to review the code? :-)

We should check the code. I think some landmark methods correctly take into
account conditional effects (lm_rhw?) while others don't (lm_hm). But I'm not sure.

I opened a pull request at bitbucket.

The admissible LM heuristic indeed rejects tasks with axioms, but it accepts 
tasks with conditional effects. I guess this is a bug in the code, not the 
documentation, right?

> Task has axioms:
> h^m, h^max, h^lmcount, h^add, h^FF: dead_ends not reliable

Looks correct to me except that I think this should only be h^lmcount with
admissible=false if our documentation is correct. The admissible LM heuristic
should reject tasks with axioms (or our documentation is wrong, which is always
possible, but then we should fix the code to match the documentation).

> Task has conditional effects
> h^m, h^lmcount(admissible=true): dead_ends not reliable

Looks correct for h^m, but not for h^lmcount. If our documentations is correct,
then h^lmcount(admissible=true) should reject tasks with conditional effects.


I also notice that our documentation says "conditional_effects" in the supported
features everywhere instead of "conditional effects". Would it be possible for
someone to a global search-and-replace there? (Doesn't need to be done in an
issue branch if it's the only change.)

By my reasoning (looking at the documentation and the code) the following 
heuristics 
currently return the wrong result for dead_ends_are_reliable() and should return 
the results 
below instead:

Task has axioms
h^m, h^max, h^lmcount, h^add, h^FF: dead_ends not reliable

Task has conditional effects
h^m, h^lmcount(admissible=true): dead_ends not reliable

Is that correct?