Domain with conditional effects causes parser to fail to terminate

[rpgoldman]

Even with the -k flag to keep conditional effects instead of expanding them, a translation of the SHOP example Satellite domain, which features conditional effects, seems to cause the parser to run forever. Here's the prefix of the output, which shows that the parser is not trying the exponential encoding of conditional effects:

$ time pandaPIparser -k domain.hddl p01.hddl
pandaPIparser is configured as follows
  Colors in output: true
  Mode: parsing mode
  Parameter splitting: true
  Conditional effects: keep
  Disjunctive preconditions as HTN: false
  Replace goal with action: false
  Output: pandaPI format
TUUP sort_for_GroundStation1
TUUP sort_for_GroundStation2
TUUP sort_for_Phenomenon3
TUUP sort_for_Phenomenon4
TUUP sort_for_Phenomenon6
TUUP sort_for_Star0
TUUP sort_for_Star5
TUUP sort_for_image1
TUUP sort_for_spectrograph2
TUUP sort_for_thermograph0
TUUP sort_for_satellite0
TUUP sort_for_GroundStation1
TUUP sort_for_GroundStation2
TUUP sort_for_Phenomenon3
TUUP sort_for_Phenomenon4
TUUP sort_for_Phenomenon6
TUUP sort_for_Star0
TUUP sort_for_Star5

at this point, the parser appears to hang; I stopped it after 5 minutes on my M1 mac

The input data are in this gist

[galvusdamor]

I've just had a look at the input data. The problems is actually not with the conditional effects. The problem lies in the all-done method - or more precisely its method precondition. What happens here is that the forall quantors are compiled out into a conjunction for each possible value of the argument variables (of type direction&mode or satellite&mode respectively). For the first forall, this gives 73=21 instances and forthe second 17 = 7, so this gets overall compiled into a conjunct with 28 elements. This is still ok - the problems now arises as the inner condition is an imply, i.e., a logical or. What the parser here tries to do is to multiply this out into 2^28 different methods, i.e., a good 260 million methods - which won't work. This happens as we don't know a priori whether the antecedant of the imply will be true or false.

I see that this is horrendously inefficient and could be solved in one of two ways:

1. Have a special treatment here for static antecedants of implies (the goal_have_image and goal-pointing are both static).
2. Split the precondition up into multiple precondition actions (which is what we do anyway). This will require only 2*28 in stances.

Lastly, I assume that you actually just want to keep the forall and implies here for the SHOP output, correct? If so, we might just not perform the compilation here at all. I have no idea what kind of consequences this has for the SHOP output (have to take a look at it). But at least for the panda-format output, I don't see an easy solution here apart from the two above.

[rpgoldman]

I was processing this for both PANDA and SHOP3. We (Ugur, Dana Nau, Paul Zaidins and I) were setting up to run some comparison experiments between different plan repair methods. Trying to find a shared set of problems is quite difficult, actually!

For SHOP2 and 3, implication and quantification can be left in the output. The SHOP :forall construct is a bit odd, but will handle this.

Probably some combination of your two methods would be best: this specific issue arose because of translating a goal into a task, a common technique in SHOP domains addressing the IPC problems. I have looked over a number of these in the SHOP examples, and it looks like sometimes the goal facts are deleted when they are made true, and sometimes (as in this case) they are static, and are checked. The static encoding is probably the simplest: if one has conditional goals and tries to delete the goal facts, then one needs to use protections to ensure that the planner doesn't clobber any of its conditional goals.

It's possible that I could make 2 slight variations here for our experiments: for SHOP we encode goals as facts like this, but for PANDA we use the HDDL :goal specification. But I honestly don't know how PANDA handles :goal: is it just used as a post-check at the end of planning? Or does it do subgoaling like a first-principles planner. If it does subgoaling, though, I don't see how it would ever engage any of its methods.

[galvusdamor]

That is nice to hear! Having and maintaining a set of experiments that works for multiple planners is always a pain and take a huge amount of work (see IPC ...).

As for how PANDA interprets the :goal -- we consider the plan correct if its last state satisfies the :goal, i.e., from a semantics point-of-view this is a post-check at the end of planning. However, the planner will use the information that such a state has to be reached to guide the search, i.e., the heuristics try to estimate how "far" we are away from completing the HTN structure in a state that satisfies the goal.

Yea, this type of modelling "goal predicates" in SHOP / HDDL is quite common. What my feeling is - is that you actually want to be able to reference the goal state e.g. in method preconditions (which makes sense! they are a form of search guidance and you should be able to know where the search is going to when performing this guidance). Something like a (:ingoal (at ?x ?l)) which is treated as a normal literal -- and e.g. compiled away or handled specially. I would agree that the static compilation is the easiest one - also from the view of the parser (i.e. the amount of changes needed for the parser to be able to do this).

[rpgoldman]

Coming back to this after working on some other domains...

I see that a number of these all manage to simulate conjunctive goals by adding goal facts to the state and then checking to see if the goals have been achieved to tell whether to terminate a recursive goal-handling method.

Under those circumstances, it seems that the existing explosion in parsing is going to render it impossible to solve many of our domains. I'm looking at the IPC problems that we have been considering for our repair comparisons, Minecraft-player and Snake, and it looks like both of them have worked around the issue of conjunctive goals. The first ducks the problem by only ever building one house. It could build more than one house only because the house specification includes all the spaces involved. If the problems were modified to try to build multiple houses without specifying the set of locations involved, I believe we would hit the same problem -- it wouldn't be possible to extend this domain, because it wouldn't be possible to prevent the planner from trying to build one house on top of another. Similarly, in Snake the snake must always eat all the mice. If we were to ask the snake to eat a specific subset of mice, or a fixed number of mice, again the state encoding of goals would cause the same issue.

So as I think about it, it seems worth modifying the parser so that it can handle implications (or more generally disjunctions) with static facts better, because this encoding pattern is so prevalent. Would this be difficult to do?