SAS translator over determinized PDDLs

[ssardina]

Yes it is working well. Now that's another discussion for us working on FOND and will apply to your PRP+ planner and ours. When I wanted to use the lifted determinization we have in this fond-utils repo, we cannot just use the standard SAS translator Chris. The reason is that such translator may simplify actions that are the result of determinization, for example, because the effect gets trivialized. We need to keep those derived DETUP actions.

Because of that I have elaborated the translate-fond I had with two translators (the one that does both determinization and SAS, and the standard classical SAS but without deleting actions that are determinizations). You will need to also deal with this Chris in your PRP

Originally posted by @ssardina in #11 (comment)

[ssardina]

@haz pointed out in #11 (comment):

Don't they have us covered with the right command line options to disable parts? https://github.com/QuMuLab/pr2/blob/main/pr2#L138

[ssardina]

I thought the --keep-unimportant-variables was in regards to variables, not operators, but I had seconds thoughts whether operators are also "variables" for the translator. When I modified the translator (to avoid dropping determinized effects) I didn't see that option affecting anything wrt operators.

That option means:

  --keep-unimportant-variables
                        keep variables that do not influence the goal in the causal graph

I tested on the example I attach here and indeed: the no-op effect operator is gone anyways. 🤷

Now, I may have missed something, but it seems that option (and others) are not used at all. Look:

$ grep -r keep *
axiom_rules.py:            continue   # Required to keep one of multiple identical axioms.
options.py:        "--keep-unreachable-facts",
options.py:        help="keep facts that can't be reached from the initial state")
options.py:        "--keep-unimportant-variables",
options.py:        help="keep variables that do not influence the goal in the causal graph")
pddl_parser/parsing_functions.py:            # We use add-after-delete semantics, keep positive effect
translate.py:                # and we do not want to keep an effect whose condition contradicts

I would have expected options.keep_unimportant_variables to be named/checked! 😕 If this is true, no surprise that when I ran the translator on the example attached, both proposition r and operator sq_DETDUP_2 are removed!

Said so Chris, even so there are two issues that may not make using the translator "as is" the best option:

1. We may still want to simplify actions that are not the result of non-determiniozation and also predicates that are irrelevant. Would be too hard to just not simplify anything, that is one of the main features of the translator I would say.
2. I am not sure how smart the translator is, but it may simplify actions that make the goal unachievable. For classical planning it makes sense, but we need to keep them for FOND: these are nd effects that will lead to a dead-end.

sas-nd.zip

Check this:

(define (domain nooptest)
    (:requirements :strips)
    (:predicates (p) (q) (r))
    (:action sq_DETDUP_1
        :parameters ()
        :precondition (p)
        :effect (q)
    )
     (:action sq_DETDUP_2
        :parameters ()
        :precondition (p)
        :effect (and )
    )
)


(define (problem nooptest-p01)
    (:domain nooptest)
    (:init
        (p)
    )

    (:goal
        (q)
    )

)

Then I run:

$  ~/PROJECTS/planning/FOND/parsers/translator-fond.git/original-translators/downward-release-24.06.0/src/translate/translate.py --keep-unimportant-variables output/domain_02_all_outcomes.pddl test/no-op/p1.pdd

cat output.sas
begin_version
3
end_version
begin_metric
0
end_metric
1
begin_variable
var0
-1
2
Atom q()
NegatedAtom q()
end_variable
0
begin_state
1
end_state
begin_goal
1
0 0
end_goal
1
begin_operator
sq_detdup_1 
0
1
0 0 -1 0
1
end_operator
0

As we can see, proposition r is gone and so is action sq_detdup_2

[haz]

Ah, ok. Let me bring Basel in on this.

I think it would be fine to prune an action because it's not reachable/executable ever (if you get rid of one determinized action because of this, all will go). I don't think it's fine to prune an action because it doesn't seem relevant for the goal (noop actions need to be kept, etc).

@FlorianPommerening : Any chance we have a no-code opportunity to get the behaviour we want from the FD translator? I.e., we'd rather not modify the translator at all -- just pass in the command-line option that will keep the seemingly irrelevant actions around.

@ssardina : Think it's worth having a utility done up to cross-reference the names? Given (1) a determinized domain file, (2) indication what the detdup suffix is, and (3) a sas file...check and see if all the determinized actions appear (if a ground action is there in the sas file, all of the sibling outcomes are also there).

[ssardina]

I think it would be fine to prune an action because it's not reachable/executable ever (if you get rid of one determinized action because of this, all will go).

fine with that, it would mean that the static analysis figures out that the action is unreachable (precondition never true), which would not be complete. Not sure where in the translate code that happens, but in that case we would eliminate ALL the determinized versions of the original action (as they all share the same precondition)

I don't think it's fine to prune an action because it doesn't seem relevant for the goal (noop actions need to be kept, etc).

It does for classical planning; these actions can be removed right away, no need to consider them in the search. It is however not right to remove them for FOND in general

@FlorianPommerening : Any chance we have a no-code opportunity to get the behaviour we want from the FD translator? I.e., we'd rather not modify the translator at all -- just pass in the command-line option that will keep the seemingly irrelevant actions around.

Certainly we would rather not modify the FD translator and use it "as is'. But what is the feature we would like to have? Not really completely disabling full simplification of irrelevant operators. I think what we would like is to be able to state exceptions to those simplification and be able to state that some operators should not be simplified/removed. In the simplest form, would like to be able to state that actions containing a substring should not be dropped, something like:

--keep-operators <string>

telling the translator to not drop any action containing <string>. I have that already with <string> fixed to DETDUP, but it is easy for me to generalized it to the option above (just add one entry to options.).

@ssardina : Think it's worth having a utility done up to cross-reference the names? Given (1) a determinized domain file, (2) indication what the detdup suffix is, and (3) a sas file...check and see if all the determinized actions appear (if a ground action is there in the sas file, all of the sibling outcomes are also there).

Do you mean a utility in this repo that checks that a .sas file contains all the determinized actions of a domain? Kind of a "checker" that the translator used was good? Is that what you mean?

[FlorianPommerening]

Hi all,

--keep-unimportant-variables will skip the step that removes variables which are not relevant for the goal. Removing a variable means removing it in all places where it occurs and this can make some operators no-ops. So removing irrelevant variables typically also means removing the irrelevant operators. If you want to keep the operators, you have to keep the variables. So I think --keep-unimportant-variables would do what you want.

The reason you didn't find a usage with grep is that the option is called differently internally (don't ask me why)

    argparser.add_argument(
        "--keep-unimportant-variables",
        dest="filter_unimportant_vars", action="store_false",
        help="keep variables that do not influence the goal in the causal graph")

The dest="filter_unimportant_vars" means that internally, the option is called filter_unimportant_vars (and action="store_false" means that the semantics are flipped). It is used here: https://github.com/aibasel/downward/blob/main/src/translate/translate.py#L613

[ssardina]

Hi @FlorianPommerening , silly me, yes I wrongly assumed the options will keep the same name, very naive on me not checking well the options file. I did read it and saw they are loaded into the module.

OK good, I was very confused that it wasn't implemented and be there for so man years! 🤦

If you want to keep the operators, you have to keep the variables. So I think --keep-unimportant-variables would do what you want

I am OK domain variables being dropped, it may make the problem simpler to solve, but I want to keep (certain) operators, even if they are (eventually) no-ops.

Question @FlorianPommerening : could the operator simplification ever involve more sophisticated cases like an operator making the goal impossible? I would think so, it could happen, say an operator that makes the precondition of a must action false forever. Would that be dropped in general? If so, would the flag above avoid that being dropped?

[FlorianPommerening]

As far as I know, there is no fine-grained control over what is dropped and what is kept. My understanding is that there first is a reachability analysis that is done as part of the grounding. That means only facts/actions that are reachable in the delete-relaxation will be grounded. Static facts (constants) are compiled away in this step as well. Then, there is an optional second step that does a relevance analysis. It computes a causal graph, marks the goal as relevant, and then iteratively marks facts as relevant that can have an influence on other relevant facts. Everything not marked in this way is not relevant for the goal and is removed (facts and actions that become no-ops after removing the facts). With the option --keep-unimportant-variables this second step is skipped completely.

In your example, I'm assuming "must action" means action landmark? But in that case, an action destroying the landmark's precondition forever could not be pruned: let's say L is an action landmark and o is an operator that makes L's precondition false forever. There could still be a plan that first uses L and then uses o afterwards. Anyway, as far as I know, the translator only does the relevance analysis, nothing else.

[ssardina]

Thanks @FlorianPommerening

Yes, a landmark was what I was thinking of. Yes it may very well be that you need the "bad" action after the landmark actions has been done, but in other cases it is irrelevant to the goal except sending you to a dead-end. But as you said, the translator doesn't go that far. I tried this example with goal q:

(define (domain nooptest)
	(:requirements :strips)
	(:predicates
		(p)
		(q)
	)

	;; deterministically make q true
	(:action setq
		:parameters ()
		:precondition (p)
		:effect (q) 
	)
	(:action bad
		:parameters ()
		:precondition ()
		:effect (not (p))
	)
)

and the bad action is still there, it is not dropped.

I will try --keep-unimportant-variables more tomorrow, I remember trying it on simple cases and it still dropped the operator. I wonder whether my example had the trivial effect already in the input, rather than being trivialized by the translator.

In any case, @haz ,as far as I can do, we would need a translator that can take exceptions on operators to drop. There seems no way out...

[haz]

Could you point us to the part in the translator code, @FlorianPommerening , that would be removing these unnecessary actions? Noops are a good example of them.

[FlorianPommerening]

I think the call stack would be this one:

• main() https://github.com/aibasel/downward/blob/main/src/translate/translate.py#L747
• pddl_to_sas(task) https://github.com/aibasel/downward/blob/main/src/translate/translate.py#L718
• find_and_apply_variable_order(...) https://github.com/aibasel/downward/blob/main/src/translate/translate.py#L615
• apply_to_task(sas_task) https://github.com/aibasel/downward/blob/main/src/translate/variable_order.py#L284
• _apply_to_operators(sas_task.operators) https://github.com/aibasel/downward/blob/main/src/translate/variable_order.py#L198
• new_ops.append(op) https://github.com/aibasel/downward/blob/main/src/translate/variable_order.py#L251 (guarded by if pre_post above to only include operators that have an effect after removing the irrelevant variables)

@ssardina in your example, p is not recognized as irrelevant because q is relevant and setq affects q and has p as a precondition. So p is relevant and bad affects p (the causal graph doesn't make a distinction between adding or deleting the variable). I'm not sure, but it feels like adding reasoning that would catch cases like this would make the problem at least NP-hard.

[ssardina]

Agree @FlorianPommerening , I didn't think those kind of powerful reasoning were being done, as they would make the problem intractable. But I don't know if there are other cases that could end up removing actions that yield a dead-end; even making the goal false (and nothing else) would be OK and not simplified.

So yes I think that from the semantic point of view, the operators that end up being simplified are the ones that end up behaving like "no-ops" (immediately or due to predicate simplifications).

@haz , if you see my repo of the modified FD translator, I have documented the changes I did to avoid dropping our determinized actions. Note this is NOT the same as the option --keep-unimportant-variables, which presumably is stronger; the changes I did still allow predicates to be simplified, just that some actions (wrt their name) that become "no-op" are not dropped.

[ssardina]

@FlorianPommerening , consider this domain + problem:

; p1: easy should have both strong and strong-cyclic solutions - just do sq and get the goal
(define (domain nooptest)
	(:requirements :strips)
	(:predicates
		(p)
		(q)
		(r)	;; totally irrelevant predicate
	)

	;; deterministically make q true
	(:action setq
		:parameters ()
		:precondition (p)
		:effect (q) 
	)
)


(define (problem nooptest-p01)
    (:domain nooptest)
    (:init (p) )

    (:goal (q))
)

would you agree that r is irrelevant, right? Well, let's use the option --keep-unimportant-variables¨:

$ downward-release-24.06.0/src/translate/translate.py test/no-op/domain_01.pddl test/no-op/p1.pddl --keep-unimportant-variables

$ cat output.sas
begin_version
3
end_version
begin_metric
0
end_metric
1
begin_variable
var0
-1
2
Atom q()
NegatedAtom q()
end_variable
0
begin_state
1
end_state
begin_goal
1
0 0
end_goal
1
begin_operator
setq 
0
1
0 0 -1 0
1
end_operator
0

r is nonetheless gone right?

[haz]

Can you make r fluent and not static? In that case would --keep-unimportant-variables play a role?

I think what caused the original example to lose the noop was that it had no prepost -- likely due to the fluent being removed due to it being static.

[haz]

Do you mean a utility in this repo that checks that a .sas file contains all the determinized actions of a domain? Kind of a "checker" that the translator used was good? Is that what you mean?

I do indeed. It's common for many FOND planners to use FD (of some sort) as a base. The test I would hope to use:

1. Normalize + determinize the PDDL.
2. Convert with the FD translator.
3. Collect all the instances of operators in the SAS file.
4. Cross reference so that if we have a ground instance of determinized action A in the SAS, we also have all of the other ground instances for the related outcomes of action A.

There may be some groundings that never happen (preconditions not reachable), but if you have one outcome in the SAS file, all the others should be there with the same grounding.

I'm starting to suspect that PRP+PR2+MyND+Paladinus all used the same assumption of --keep-unimportant-variables as their modified use to the FD translator, and I'm curious as to how benign or damaging that is, given the benchmarks we've come across. I've visualized most (if not all) of these domains, and haven't noticed wonky things like missing effects, and ditto with plan validation (naive grounding there means that we don't discard noop actions), but it's not impossible that we've been missing something for over a decade...

[ssardina]

Good, issue created to track that new feature, I agree it is a useful tool to have. 👍

@haz , added this action to the PDDL:

	;; deterministically make q true
	(:action setnr
		:parameters ()
		:precondition ()
		:effect (not (r))
	)

Now r is a fluent: still gone even with the keep option. If I change the effect to be (and q (not r)), then it is kept always because it is now relevant to the goal q.

Note we are doing hit and miss here; the right thing is to study the code well 😉 The bottom line Chris is that it is not clear that we can use the FD translator off the shelf (and even if we do, may not be the best as I don't want to switch off all simplifications!)

[FlorianPommerening]

With the original version of the domain, r was static, so I would have expected it to be removed. In the modified version, did you add r to the initial state? Otherwise it is still static: it is false in the initial state and will remain false throughout the task because there is no way to set it to true.

[ssardina]

Good one. If it is in the initial state then it will not be static and we get the right behavior: dropped without the keep option, but kept if we state to keep the unimportant: 👍

Atom r()
NegatedAtom r()
end_variable
begin_variable
var1
-1
2

[ssardina]

@haz , I think I know understand a bit better (not fully) the limits of FD translator and the requirements needed for us.

I have documented 3 test cases and explained a bit here with concrete simple examples

The bottom line: it is not enough to use the --keep-unimportant-variables option. We need more than that:

1. Operators that are already trivial from the start are removed regardless of that option.
2. We still want to take advantage of FD translator simplifications, not just disable it completely - see example 3

So, unless we convinced them to add an option:

--keep-operators xxx

to keep all operators containing xxx in their names, we would need to patch the translator I am afraid.. 🤷

[haz]

We still want to take advantage of FD translator simplifications, not just disable it completely - see example 3

Sure 'bout this? What would be the downstream impact on performance if we had --keep-unimportant-operators available to us, and it just didn't toss away noops? We'd save all the nondet outcomes we need, and unless there are boatloads of prunable/irrelevant ones created, I can't see how it would impact the heuristics or other data structure wrangling that happens inside of the planner for FOND searches.

[ssardina]

We still want to take advantage of FD translator simplifications, not just disable it completely - see example 3

Sure 'bout this? What would be the downstream impact on performance if we had --keep-unimportant-operators available to us, and it just didn't toss away noops? We'd save all the nondet outcomes we need, and unless there are boatloads of prunable/irrelevant ones created, I can't see how it would impact the heuristics or other data structure wrangling that happens inside of the planner for FOND searches.

Not sure I am following you.. If we use --keep-unimportant-operators, then the FD translator will not simplify predicates that otherwise would be simplified (irrelevant propositions that do not affect the goal). What I am saying is that may NOT want to use that option: we do want to get the benefits of simplifying the PDDL.

Are you saying that such simplifications have no impact on the actual search on planners? If so I would not think that is the case in general.

I think we want the default behavior of FD translator that simplifies the input via static analysis. However, we want to keep all non-det operators.

A special case is: what if all the determinized effects become trivial no-op, or what happens if the non-deterministic operator has a false precondition always? In this case we can drop ALL the determinized actions (I don't do that now)

[haz]

Aye, I'm questioning if the actual potential improvement is present in any of the examples we see. What about a double-pass?

1. Run the translator with all simplifications
2. Note the original non-det action names (grounded) that remain (i.e., have at least one determinized action present)
3. Run the translator with simplifications disabled (vars and operators)
4. Filter that second generated SAS file to keep only those ground actions corresponding to those found in step 2

[ssardina]

Seems like a hack @haz ... Not sure the impact on the current problems, but I believe it does have significant impact in many classical planning tasks, and those can always be converted into FOND versions easily right? We want a solution that is not over-fitting to the current tasks.

Haven't thought about the double pass, it´s clever but again I see two problems;

1. in some problems the translation does take a long time. maybe not if we
2. comparing the two will not be trivial, as kept actions in the second pass would refer to propositions that are gone in the first pass

I don't know, but it looks too much work and going around when we can trivially get exactly what we want by a slight modification of the original translator. In fact, I would say it can be beneficial to extend the official translator with a regular expression match: those actions that match the regular expressions are kept.