Issue247

Title LM heuristic crashes and/or wrongly reports dead ends
Priority bug Status chatting
Superseder Nosy List emilkeyder, erez, malte, rpgoldman, silvia
Assigned To emilkeyder Keywords
Optional summary

Created on 2011-06-29.18:41:04 by malte, last changed by malte.

Files
File name Uploaded Type Edit Remove
robert-tony-domain.pddl malte, 2011-06-29.18:41:15 application/octet-stream
robert-tony-problem.pddl malte, 2011-06-29.18:41:23 application/octet-stream
robert-tony.soln malte, 2011-06-29.18:41:31 application/octet-stream
Messages
msg1457 (view) Author: malte Date: 2011-08-04.19:42:58
> The first stage of refactoring is ready to be merged, so I'll make that a
> priority (which hopefully means I'll get to it this week).

Well, that was too optimistic, but it is now merged.
msg1411 (view) Author: emilkeyder Date: 2011-06-30.13:14:00
Hmm, at least in the case of the h^m landmarks adding support for conditional 
effects is not going to be easy. It would mean basically rewriting it from 
scratch to compute subsets of fluents that are subsets because part of the set 
appears in an action precondition and part of it in a conditional effect. So I 
think I'll go the cowardly route and copy in something similar to Raz's function 
for now. 

I'm working on some other stuff in the h^m landmarks code though, so I'll wait 
until I have that done and merge it in then - unless you feel that there's a 
hurry for this.
msg1408 (view) Author: malte Date: 2011-06-30.10:44:25
It may indeed be better not to mess with the landmark code while it is being
refactored. (But we should still look into it to find out what is going on here.)

The first stage of refactoring is ready to be merged, so I'll make that a
priority (which hopefully means I'll get to it this week).
msg1404 (view) Author: silvia Date: 2011-06-30.09:55:03
> Silvia, is lm_zg supposed to support conditional effects?

From memory, I'd say yes, but I can only verify this on Monday when
I'm back from my holiday.

Silvia
msg1402 (view) Author: erez Date: 2011-06-30.08:43:48
I seem to remember that someone is working on refactoring the landmarks code.
If so, it seems like it should be handles as part of the refactoring (something 
like having each landmark generation method declare what PDDL features it can 
handle, and showing an error otherwise).
I could also add this check now, if anyone thinks it's urgent.
msg1397 (view) Author: malte Date: 2011-06-29.22:01:34
Ah, I think you brought us on the right track here!

Our documentation on
http://www.fast-downward.org/HeuristicSpecification#Landmark_count_heuristic
says: "conditional effects: supported if admissible=false". I know Silvia
evaluated LAMA on tasks with conditional effects. However, I guess this support
is only there for the parts that Silvia implemented, not for lm_hm.

Silvia, is lm_zg supposed to support conditional effects?


It's fine to not support them in parts of the code, but in such cases we should
bail out with an error message rather than silently ignoring them; see
MergeAndShrinkHeuristic::verify_no_axioms_no_cond_effects in
raz_mas_heuristic.cc for an example. (Really, this function should be available
globally, rather than being stuck in this place.)

So one thing we can do is document that only some LM generation methods support
conditional effects and let the others reject tasks that have them.

Of course, we could also open a separate issue to add such support, which should
not be too hard (famous last words?). Anyone interested in looking into that? I
can give advice, but probably won't be able to provide code.


Conditional effects are probably only part of the story here, though.
The main problem for LM_RHW here are vey likely derived variables, which the
translator introduces in this case (I guess because of universally quantified
conditions in the original input).

Our documentation says "axioms: supported if admissible=false (but may behave
stupidly and be unsafe)", where "unsafe" means: can falsely claim a problem to
be unsolvable. So the outcome we get here might just be a known limitation
rather than an actual bug. One potential bug is that an alternation search that
uses both safe and unsafe heuristic should be safe; I think it isn't in this
case because the LM-count heuristic doesn't own up to being unsafe. But that
should be easy to fix and address the actual problem here.


In summary:

1) lm_hm should probably bail out when faced with conditional effects or axioms,
or at least print a clear warning message, also on cerr, that it is unsafe in
this case (like the one for issue240). It should not fail an assertion.

2) Optionally, we should open an issue for adding conditional effect support to h^m.

3) We might also open an issue for proper derived predicate support for all LM
generation methods.

4) We should clarify what the exact support for conditional effects for LM
heuristics is in the documentation.

5) The LM count heuristic should only claim that it is safe for those tasks
where this is actually true.
msg1396 (view) Author: emilkeyder Date: 2011-06-29.20:27:28
Does the landmark heuristic, or any of the landmark generation methods currently 
implemented, actually support conditional effects? I don't remember ever seeing 
conditional effects mentioned in the context of landmarks, and after a quick look 
through the code I'm not sure how to access them either. Where should I look for 
the documentation?
msg1394 (view) Author: malte Date: 2011-06-29.18:42:39
Tentatively assigning to Emil hoping that you can look into the h^m landmark
thing. If not, please reassign to "- no selection -".

Everyone else (Erez? Silvia?), if you have any insights about LM_RHW or LM_ZG,
that would be great.
msg1393 (view) Author: malte Date: 2011-06-29.18:41:03
When working on issue240, I think I found a bug with the landmark heuristic.
Here is what Robert and Tony tried to do (after translate/preprocess, and using
debug mode; paste command as a single line):

$ make debug && ./downward-1-debug --heuristic
"hlm,hff=lm_ff_syn(lm_rhw(reasonable_orders=true,cost_type=2,lm_cost_type=2))"
--search "lazy_greedy([hlm,hff], preferred=[hlm,hff])" < output

This fails noting that the search space was exhausted. However, when using just
hff (e.g. change "[hlm,hff]" to "[hff]" in both places), the problem is solved,
hinting at wrong dead-ends reported by h^LM.

The problem also appears when using the plain LM heuristic in various forms.
Here are some simple examples:

$ ./downward-1-debug --search 'astar(blind())' < output
=> Solves the task.

$ ./downward-1-debug --search 'astar(lmcount(lm_rhw(reasonable_orders=false)))'
< output
=> Exhausts the search space.

$ ./downward-1-debug --search 'astar(lmcount(lm_hm(m=1)))' < output
=> LM construction claims problem is unsolvable.

$ ./downward-1-debug --search 'astar(lmcount(lm_zg()))' < output
=> LM construction assert-fails.

Possibly a clue, possibly not: Disabling all orderings in LM_RHW leads to the
problem being solved:
$ ./downward-1-debug --search
'astar(lmcount(lm_rhw(reasonable_orders=false,no_orders=true)))' < output

However, this doesn't help with the other LM generation methods, which already
fail during LM graph construction.
History
Date User Action Args
2011-08-04 19:42:58maltesetmessages: + msg1457
2011-06-30 13:14:00emilkeydersetmessages: + msg1411
2011-06-30 10:44:25maltesetmessages: + msg1408
2011-06-30 09:55:03silviasetmessages: + msg1404
2011-06-30 08:43:48erezsetmessages: + msg1402
2011-06-29 22:01:35maltesetmessages: + msg1397
2011-06-29 20:27:28emilkeydersetmessages: + msg1396
2011-06-29 18:42:39maltesetassignedto: emilkeyder
messages: + msg1394
2011-06-29 18:41:31maltesetfiles: + robert-tony.soln
2011-06-29 18:41:23maltesetfiles: + robert-tony-problem.pddl
2011-06-29 18:41:15maltesetfiles: + robert-tony-domain.pddl
2011-06-29 18:41:04maltecreate