While refactoring the code that generates the atomic transition systems, I
noticed two things:
1. In the atomic transition system for variable v, it looks like we
generate self-loops for each value of v and each operator o that does not
mention v. So if there are N values and M irrelevant operators, this will
take time and space O(NM). I assume that the self-loops for the different
irrelevant operators are then combined into one in label normalization,
reducing the representation to O(N). It might be worth checking out if we
can get a performance boost from avoiding the O(NM) intermediate
representation, instead generating a "normalized" representation for the
irrelevant operators from the start.
2. If we have conditional effects, then we might get more transitions than
necessary because each conditional effect is considered in isolation.
Let's consider a variable with domain {0, 1, 2} and an operator with
no preconditions and three conditional effects:
if v = 0, then v := 1
if v = 1, then v := 2
if v = 2, then v := 0
We would like this to only generate three transitions: 0->1, 1->2 and
2->0. But because we consider each effect in isolation, we will also
get 0->0 (from the second and third effect), 1->1 (from the first and
third) and 2->2 (from the first and second). This is a bit of a pity,
and it can also lead to a severe blowup in representation before
normalization takes place: if we have M values in the domain, then
*each* effect can generate O(M) self-loops, so with K effect, we have
an intermediate size of O(MK), even though the many parallel self-loops
will disappear after normalization. Bearing in mind that some tasks have
tens of thousands of conditional effects in a single operator, this can
be a problem.
Silvan, did I read the code correctly?
I don't think we need to act on these two points immediately, but I wanted to
record them while I still understand this part of the code, which is quite nasty
(a single 126-line function in master; in the branch, it's split up into smaller
parts, but the largest function there still has 71 lines).
If we should decide to act on these later, no. #2 in particular will very likely
have no effect on our standard M&S benchmark suite (which has no conditional
effects, I think), and it's very easy to mess the conditional effect code up if
we don't test the right domains. |