We used the hack you suggested for the IPC. Gabi has reimplemented the
conditional effect support in the meantime. I think we should continue this
issue with her implementation. As far as know it is faster than my
implementation but still has noticeable overhead compared to the original
implementation on tasks without conditional effects. I guess we should look at
this theoretically again before we continue testing.

Hmmm, I'm not sure a 10% slowdown in some of the STRIPS domains is acceptable.
:-( For the IPC, a simple solution is to create a separate ADL heuristic with
copy and paste. (Obviously not something to be left that way, but OK as a
temporary measure.)

Can the slowdown be reproduced with a profiler? If yes, I'd pick a problem with
a runtime of, say, 30-60 seconds, run it in the profiler with both versions and
then see how much time is lost in which method. One possibility is worse cache
locality, in which case it might actually be useful to copy the cost information
into the RelaxedOperators (i.e., have them redundant). But it's better to
measure first rather than speculate.

I've also added a bunch of comments in bitbucket. (Not sure if you get
notifications for these because it wasn't part of a pull request/code review.)

I ran experiments for a first implementation of option (a). There is some
time/memory overhead for tasks without conditional effects (exp1). For domains
with conditional effects, I only tried miconic so far. I'll add experiments for
Patrik's compiled domains later.

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue403-exp1-compare.html (5 MB)
http://ai.cs.unibas.ch/_tmp_files/pommeren/issue403-exp2-compare.html

> I'm not sure, I understand how this will make the implementation easier.

You wrote that variant (a) requires nesting of conditions two levels deep and
(b) requires three levels deep. The suggested semantics requires one level less
in both cases, which makes (a) simple to implement. Regarding (b), I don't
really know if one vs. two levels makes a big difference.

> Is this still admissible?

Yes; it's the standard notion of delete relaxation for finite-domain planning tasks.

Actually, I have some doubts about admissibility/completeness with the delete
relaxation variant you had in mind; maybe because the details are not fully
clear to me. (It can certainly be made admissible, but it depends in how exactly
you want to represent the notion of "none of the later effects on this variable
trigger".) Can you briefly write up the form of operators and semantics of
operator application in the delete-relaxed problem you had in mind?

I suggest we discuss this further in person.

I'm not sure, I understand how this will make the implementation easier.

Lets say we have an operator o = <pre(o); unconditional_effects(o), (cond_1(o),
eff_1(o)), ...,  (cond_n(o), eff_n(o))>


For the first option (counting every operator at most once) we could introduce
the following RelaxedOperators

  o_uncond = <pre(o); unconditional_effects(o)>
  o_1 = <pre(o) and cond_1(o); eff_1(o)>
  ...
  o_n = <pre(o) and cond_n(o); eff_n(o)>

All labeled with the same original operator. This would not consider the new
semantics of conditional effects, but may have been what you had in mind. Is
this still admissible?

For the second option (context splitting) I don't see a way to avoid the
disjunction even with the accumulating semantics.

> the resulting state after applying o is {a => 3}

Of course, this should be {a => 3, b => 2}.

Hi Florian,

> In option 1) this stems from a formula that ensures that an effect triggers, but
> no other effect "overwrites" the value. Here the precondition is a conjunction
> of disjunctions of facts.

let me stop you right there. There's more than one way to define "delete
relaxation" or "monotonic relaxation" semantics for the planning formalism we
want to support. They differ in several characteristics, such as

1) clarity/simplicity of definition
2) accuracy of the resulting delete-relaxation heuristics
3) computational cost for the resulting delete-relaxation heuristics
4) implementation effort

You are going with a definition that maximizes 2), but I think there are better
solutions in terms of 1), 3) and 4). Namely, I would go with a semantics where
in the monotonic relaxation, variables "accumulate" values rather than having
their values replaced, in which case their cannot be any "overwriting".

For example, let's consider the state s = {a => 1, b => 2} and the operator o
with effects "unconditionally, set a := 2"; "if b = 2, set a := 3". In the real
state space, this means the resulting state after applying o is {a => 3} with
our semantics. I think the implication in your discussion is that in the delete
relaxation, where variables are set-valued, so s = {a => {1}, b => {2}}, you
want the resulting state to be {a => {1,3}, b => {2}}.

But this is only one option. A simpler, easier to implement and easier to
compute semantics would be that the operator effects in the relaxation become:
"unconditionally, set a := a \cup {2}"; "if b = 2, set a := a \cup {3}". There
is no conflict here; the resulting state will be {a => {1,2,3}, b => {2}}.

I would suggest going with this semantics because I think it offers a better
tradeoff in terms of 1), 2), 3) and 4).

I ran into a new problem with this issue. Both options use disjunctions in the
precondition:

In option 1) this stems from a formula that ensures that an effect triggers, but
no other effect "overwrites" the value. Here the precondition is a conjunction
of disjunctions of facts.

In option 2) we have the same formula but additionally want to ensure in some
cases that some other effects cannot trigger. Here we end up with conjunctions
and disjunctions nested 3 levels deep.

For the forward reachability, I have an idea of how to handle disjunctions
(nested or not).
For the backward step (marking the goal area), I'm not so sure. I guess we could
give each formula (fact, disjunction, conjunction) a set of h^max achievers. The
set for a formula f would be

achievers(f) =
  {f},                                           if f is a fact
  achievers(\argmax_{x conjunct of f} h^max(x)), if f is a conjunction
  \bigcup_{x disjunct of f} achievers(x),        if f is a disjunction

The backwards step would then mark all facts in achievers(pre(o)) for a
reachable operator o with 0-cost that adds a fact inside the goal zone.

My questions are:
Is this correct?
Is there a better way to handle this?
Any idea how to handle the incremental forward exploration, i.e.,
first_exploration_incremental()?

Yes, we are. We are only ignoring their differences when we reduce the cost of
an operator in a landmark, i.e., once one conditional effect is part of a
landmark, the whole operator is free (including all its conditional effects).

I wouldn't call option 1 "ignoring" conditional effects, as we're taking into
account the effect conditions. (Right?)

Conditional effects should be supported with their new semantic.
We discussed two options:

1) ignoring conditional effects
2) context splitting