Author malte
Recipients jendrik, malte, silvan
Date 2015-07-25.23:48:03
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.
Date User Action Args
2015-07-25 23:48:03maltesetmessageid: <>
2015-07-25 23:48:03maltesetrecipients: + malte, jendrik, silvan
2015-07-25 23:48:03maltelinkissue561 messages
2015-07-25 23:48:03maltecreate