Issue166

Title improve support of conditional effects in FF heuristic
Priority feature Status chatting
Superseder Nosy List gabi, haz, jendrik, malte, salome
Assigned To salome Keywords
Optional summary

Created on 2010-12-18.00:15:33 by malte, last changed by gabi.

Files
File name Uploaded Type Edit Remove
domain.pddl gabi, 2013-12-20.16:17:38 application/octet-stream
domain2.pddl gabi, 2013-12-20.16:17:51 application/octet-stream
prob.pddl gabi, 2013-12-20.16:17:46 application/octet-stream
prob2.pddl gabi, 2013-12-20.16:17:56 application/octet-stream
Messages
msg2845 (view) Author: gabi Date: 2013-12-20.16:17:38
I add two very small example tasks by Salomé. With the first one, the change
improves the heuristic estimates, with the second one the change leads to an
overestimate.
msg2843 (view) Author: gabi Date: 2013-12-20.11:06:51
Treating effects with different conditions as separate operators is also not
beneficial if preferred operators are switched on:
http://ai.cs.unibas.ch/_tmp_files/roeger/issue166_pref.html

(Preferred operators implemented as specified in msg895)

Jendrik, if you add the other ADL domains to the repo, I will also run
experiments on these.
msg2831 (view) Author: malte Date: 2013-12-18.20:44:43
> I guess these shouldn't become part of the master repo, right?

At least not without further discussion. After the IPC, we should maybe revive
our discussion of benchmark collections and add missing domains to the
repository (e.g. from the learning competitions, or alternative formulations of
domanis for which we already have a formulation).
msg2830 (view) Author: jendrik Date: 2013-12-18.20:37:20
I am currently searching for benchmark domains with conditional effects as well. So far I found the 
following domains that are not part of the FD repo:

http://fai.cs.uni-saarland.de/hoffmann/ff-domains.html
    Briefcaseworld
    Fridge

http://users.cecs.anu.edu.au/~patrik/
    Alternate encoding of the two Pipesworld domains
    The WITAS Event Loss Detection domain
    One formulation of the genome edit distance domain

I was planning to add them to a branch in our IPC14 repo, ok? I guess these shouldn't become part of the 
master repo, right?
msg2829 (view) Author: malte Date: 2013-12-18.20:31:06
Doesn't look too promising indeed. However, we just don't have many ADL domains
to test on at the moment. I think there is some effort under way in our group to
assemble a benchmark suite with conditional effects. Is this right? In that
case, I would maybe wait and do an evaluation with that benchmark suite before
we make a final decision here. BTW, we might also try airport-adl, which is not
part of our regular benchmark suite but already included in our repository.

If we end up running another experiment, I think it would be good to also do
tests with preferred operators enabled. If it is possible to report initial h
values, this would be interesting, too.
msg2828 (view) Author: gabi Date: 2013-12-18.15:47:34
I conducted some experiments (without preferred operators):
http://ai.cs.unibas.ch/_tmp_files/roeger/issue166_no_prefered_operators.html

The results look rather unpromising. The first comparison measures the overhead
of the new implementation if we compute the same heuristic as before. These
might be improved with some refactoring. However, the second comparison raises
doubts whether this way of supporting conditional effects is really beneficial. :-(
msg2708 (view) Author: gabi Date: 2013-11-20.13:20:24
In terms of dead end detection both implementations should behave equally.
We just do not always count several applications of one action in a relaxed plan.
msg2704 (view) Author: haz Date: 2013-11-20.05:55:45
Does this effect the use of the FF heuristic in terms of detecting deadends by 
any chance? I.e., does the following hold:

hFF(s) = \infty iff hFF'(s) = \infty

...where hFF is the ideal implementation of FF and hFF' is FD's current 
implementation.
msg2382 (view) Author: malte Date: 2013-01-07.12:10:12
The most interesting domains for testing this are:

- miconic-simpleadl
- miconic-fulladl
- assembly
- airport-adl

It would probably also be a good idea to add an explicit test case, e.g.
something like the example in msg895.
msg895 (view) Author: malte Date: 2010-12-18.00:15:33
If I recall our code correctly, in the presence of conditional effects, our FF
heuristic's relaxed plans are not actually guaranteed to be proper relaxed plans
(in the sense that they solve the relaxation).

Specifically, in cases where the same operator is needed twice, we only count it
once. Here's such an example:

Facts {a, b, c}
initial state I = {a} (using STRIPS-ish set notation)
goal set G = {c}
operator set O = {o} with

 pre(o) = \top
 eff(o) = b AND (IF b THEN c)

We'll need o twice, but only count it once.

There are various ways to solve this. One way is what we do in the planning
lecture: Treat two effects of an operator as coming from a different operator
iff they have different associated effect conditions. For example, an operator o
with preconditions {u, v, w} and effect list

 a
 b
 IF x THEN c
 IF x and y THEN d
 IF x THEN e
 f
 IF x THEN g

would be treated as three different operators:

o_1 with preconditions {u, v, w} and effects {a, b, f}
o_2 with preconditions {u, v, w, x} and effects {c, e, g}
o_3 with preconditions {u, v, w, x, y} and effects {d}


This should also influence preferred operators: e.g. if in the current state o
is applicable but x is not true and we're really only interested in the o_2 part
of o, then o should not be marked as preferred even though it's applicable and
"occurs in the relaxed plan" (in the form of o_2).

It should only be marked as preferred if one of the o_i versions that is part of
the relaxed plan is applicable in the current state.
History
Date User Action Args
2013-12-20 16:17:56gabisetfiles: + prob2.pddl
2013-12-20 16:17:51gabisetfiles: + domain2.pddl
2013-12-20 16:17:46gabisetfiles: + prob.pddl
2013-12-20 16:17:38gabisetfiles: + domain.pddl
messages: + msg2845
2013-12-20 11:06:51gabisetmessages: + msg2843
2013-12-18 20:44:43maltesetmessages: + msg2831
2013-12-18 20:37:20jendriksetmessages: + msg2830
2013-12-18 20:31:06maltesetmessages: + msg2829
2013-12-18 15:47:35gabisetmessages: + msg2828
2013-11-20 13:20:24gabisetmessages: + msg2708
2013-11-20 05:55:45hazsetnosy: + haz
messages: + msg2704
2013-01-07 12:10:12maltesetmessages: + msg2382
2013-01-07 12:03:23maltesetnosy: + gabi, salome
assignedto: salome
2011-06-18 01:30:49jendriksetnosy: + jendrik
2010-12-18 00:15:33maltecreate