Issue310

Title new greedy bisimulation definition taking into account action costs
Priority feature Status resolved
Superseder Nosy List jendrik, joerg, malte, raznis
Assigned To malte Keywords
Optional summary

Created on 2011-12-20.14:21:11 by malte, last changed by malte.

Messages
msg2237 (view) Author: malte Date: 2012-05-26.22:21:18
Forgot to close this one.
msg2033 (view) Author: malte Date: 2012-01-23.12:09:53
Done. As discussed a while ago, I've also removed "greedy=somewhat", so we just
have "greedy={false,true}" left.
msg2032 (view) Author: malte Date: 2012-01-15.23:12:30
Results are in:
http://www.informatik.uni-freiburg.de/~helmert/exp-issue310-eval-abs-d.html
http://www.informatik.uni-freiburg.de/~helmert/exp-issue310-eval-abs-p.html

Explanations:
- M{mlcgl,mlrl} stands for the two merge strategies we've been using
- Rt means label reduction is on (always)
- G{f,l,t} means greediness = false/legacy (= old definition)/true (= new
definition)
- B{10k,100k,inf} gives the abstract state bound
- T{1,10k} gives the threshold before abstraction kicks in
(We only consider certain combinations of the last two; otherwise we consider
all combinations.)

What we expect to see:
1. on domains with unit cost, configs with Gl vs. Gt should behave identically
- on general-cost domains, configs with Gt should do OK compared to domains with Gl

What we see:
- regarding 1., I didn't check very thoroughly, but in the cases I saw, this is
indeed the case
- regarding 2., in 4 out of 6 direct comparisons, we do better with Gt compare
to Gl. We do much worse in the remaining two cases, which have infinite bound
and threshold 1. My guess is that this happens because with infinite bound, we
often fail to build the bisimulation in these cases. I would expect these
bisimulated transition systems to typically be more complicated than in the
unit-cost case, since general cost would tend to reduce the number of equivalent
states. (For example, states with different h* cannot be equivalent, and there
tend to be more different h* values with general cost.)

So I think this should be fine, and I'd merge this and remove the "legacy"
greediness option from the code unless there are objections. (I'll wait for a
few days.)
msg2004 (view) Author: malte Date: 2011-12-20.14:21:11
We'll implement a new definition of greedy bisimulation that is like the old
"very greedy", but generalizes to domains with general action costs more nicely.
Specifically, we respect exactly those edges which lie on some optimal abstract
path, i.e., (s,a,s') with h*(s) + cost(a) = h*(s').

I'll call that one "greedy=true" and rename the old "greedy = true" option to
"greedy=legacy" for now. (Eventually we should get rid of it and also of
greedy=somewhat once we have experimental results that justify the sanity of
doing this.)
History
Date User Action Args
2012-05-26 22:21:18maltesetstatus: chatting -> resolved
messages: + msg2237
2012-01-23 12:09:53maltesetmessages: + msg2033
2012-01-15 23:12:31maltesetmessages: + msg2032
2011-12-30 23:42:56jendriksetnosy: + jendrik
2011-12-20 14:21:11maltecreate