Issue251

Title Merged Landmark Graph Causes an Assertion Error
Priority bug Status resolved
Superseder Nosy List erez, malte, silvan, silvia
Assigned To erez Keywords
Optional summary

Created on 2011-08-04.11:17:16 by erez, last changed by erez.

Files
File name Uploaded Type Edit Remove
issue251-opt.html erez, 2011-08-10.16:11:53 text/html
issue251-sat.html erez, 2011-08-10.16:12:42 text/html
Messages
msg1544 (view) Author: malte Date: 2011-08-10.16:32:30
Looks OK to me, feel free to close if you're happy with hit.
msg1542 (view) Author: erez Date: 2011-08-10.16:12:42
Here's a comparison on first 5 problems from each domain in IPC 2008.
Also, no major differences.
msg1511 (view) Author: malte Date: 2011-08-08.21:42:52
Change looks good to me. Merged.

What remains to be done is to do a before/after comparison of problems solved
and solution lengths. Erez, can you do that?
msg1506 (view) Author: erez Date: 2011-08-08.10:28:05
Actually, I'm not sure the estimates were inadmissible, I'm just not sure they 
were admissible at this point :-)
msg1502 (view) Author: erez Date: 2011-08-08.10:20:44
1. That is correct (I don't think we produced any suboptimal solutions, but it's 
worth checking).

2. Ok

3. I think the smarter way to deal with this is issue156, I'll add it to that 
issue.
msg1500 (view) Author: malte Date: 2011-08-08.10:14:11
1) Just to clarify: that logic bug was also present before the refactoring and
could have led to inadmissible estimates, right? (In other words, we have to
live with the decrease in informativeness?) If that is the case, we should also
open an issue to remind us that we need to rerun the IPC seq-opt configurations
using the merged LM graph to see if any of the results there are lost with the
fixed code, and to check if any of the solutions we produced were suboptimal.

2) Isn't the "cbb" part exactly the same thing as issue156? In that case let's
close this one (once I've merged the code) and keep that one open.

3) Regarding the case where the merged version is worse than RHW on its own, can
you open a separate "wish" issue mentioning the example where this arises so
that we can later look into ways to deal with this in a smarter way?
msg1497 (view) Author: erez Date: 2011-08-08.09:31:08
I fixed the bug in the logic. Unfortunately, now the merged landmarks graph 
loses some orderings and gives a less informative heuristic than the RHW method 
alone (on depots03, using optimal cost partitioning - RHW expanded 53849 merged 
expanded 134568).

I'm marking it as done-cbb to remind us that we can get rid of the merged graph 
and use the factories on the same lm graph (see issue156).
The fix is in my downward-fixes repository, branch issue251.
msg1492 (view) Author: malte Date: 2011-08-07.20:39:37
We discussed this before: In issue139, see msg846, msg847 and msg849 and issue156.

It's usually a very bad idea to add functionality at the same time as doing a
major refactoring. Let's fix the existing bugs before making further
functionality/structure changes, unless a direct fix would be significantly more
complicated than a structure change plus bugfix together (which I doubt).
msg1491 (view) Author: erez Date: 2011-08-07.20:22:07
The landmark code refactoring makes the lm_merged class (or at least the logic 
it uses) needless. The idea is to have a set of factories work on the _same_ 
LandmarkGraph.
However, the code does not support this as is.

Silvan - can you upload the patch to rietveld and I'll make some comments about 
what needs to be changes there?
msg1447 (view) Author: erez Date: 2011-08-04.12:44:30
Actually, my main concern is that I'm not sure if the admissible landmark 
heuristic we had in the IPC (and that I just spent a month running experiments 
with) was actually admissible.
In any case, the fix is very local to the lm_merged class, but I can wait until 
the landmark refactoring and then apply it.
msg1446 (view) Author: malte Date: 2011-08-04.12:41:27
Adding Silvia and Silvan.

Losing orderings is to be expected -- there are cases where "A or B" may be a
useful landmark to have even in the presence of "A" because of its additional
orderings. If I remember correctly, Silvia was aware of this situation in the
original LM_RHW generation code, but decided that dropping the disjunctive LM
and losing the orderings in such as case was an acceptable trade-off.

I would be fine with keeping this behaviour, but the issue (and the fact that
this is a trade-off) should be clearly commented in the code at the respective
place so that future people working on the code know what's going on here.

I should also point out that any fix to this might clash with Silvan's landmark
refactoring. I'll try to land the landmark refactoring branch later today.
msg1444 (view) Author: erez Date: 2011-08-04.11:33:03
It seems like the problem was due to only checking if there exists a disjunctive 
landmark with the same fact, not a simple landmark.
However, the simple solution to this (checking if a simple landmarks exists as 
well) now leads to losing orderings and thus informativeness.
I'm still looking into this.
msg1443 (view) Author: erez Date: 2011-08-04.11:17:15
Running 
./downward-1-debug --heuristic "h=lmcount(lm_merged([lm_rhw(),lm_hm(m=1)]))" --
search "astar(h,mpd=true)" < output
On depots problem 3 causes an assertion error:

downward-1-debug: landmarks/landmarks_graph.cc:164: LandmarkNode& 
LandmarksGraph::landmark_add_disjunctive(const std::set<std::pair<int, int>, 
std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >&): 
Assertion `!landmark_exists(make_pair(it->first, it->second))' failed.
History
Date User Action Args
2011-08-10 16:36:13erezsetstatus: testing -> resolved
2011-08-10 16:32:30maltesetmessages: + msg1544
2011-08-10 16:12:42erezsetfiles: + issue251-sat.html
messages: + msg1542
2011-08-10 16:11:53erezsetfiles: + issue251-opt.html
2011-08-08 21:42:52maltesetstatus: reviewing -> testing
messages: + msg1511
2011-08-08 10:28:05erezsetmessages: + msg1506
2011-08-08 10:20:44erezsetstatus: chatting -> reviewing
messages: + msg1502
2011-08-08 10:14:12maltesetstatus: done-cbb -> chatting
messages: + msg1500
2011-08-08 09:31:08erezsetstatus: in-progress -> done-cbb
messages: + msg1497
2011-08-07 20:39:37maltesetmessages: + msg1492
2011-08-07 20:22:07erezsetmessages: + msg1491
2011-08-04 12:44:31erezsetmessages: + msg1447
2011-08-04 12:41:27maltesetnosy: + silvia, silvan
messages: + msg1446
2011-08-04 11:33:03erezsetmessages: + msg1444
2011-08-04 11:17:16erezcreate