Understanding How FD's Translator Works

[Nishanth Kumar]

Hi everyone,

I have a specific question (apologies if it is simple and I'm just missing something) about one component of how FD's translator works. I've noticed the translator is able to delete some state-variables that are completely irrelevant to the PDDL planning particular problem. As a concrete, simple example of what I'm taling about, I created a variant of the Gripper domain (Domain File: https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/domain.pddl, Problem File: https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/prob04.pddl) where the balls to be picked and placed by the gripper have different colors. I added a 'paint-ball' action that allows the agent to arbitrarily change the colors of various balls. I then created a standard problem instance (linked above) where the gripper simply has to move different balls to specific rooms (the color of the balls to be moved is not specified anywhere in the goal conditions).  When I ran FD's translator on this domain and problem instance, the resulting SAS+ file (https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/gripper-paint-4.sas) does not include any state-variables corresponding to the color of the balls, nor does it include any of the 'paint-ball' actions.

I'm confused about this because after reading the FD JAIR paper as well as this paper about FD's translator, my understanding was that the translation + grounding process detects constant and one-way predicates, and also merges or deletes some predicates by inferring invariants/mutex-constraints. However, the 'ball-color' predicate is not constant or one-way, nor are different ball-color values unreachable in either the forward or backward direction (i.e: the 'paint-ball' action can be used to modify the ball color from the initial state, and doing so does not result in a dead-end). If my understanding here is correct (please do point out if it's wrong), what mechanism does FD's translator use to delete these state-variables and actions? In particular, if there is an existing paper/line of papers explaining how such variables and actions can be pruned during grounding, I'd very much appreciate some pointers and links to these!

Best,

Nishanth

[Gabriele Röger]

Dear Nishanth,

after the transformation to the SAS representation, we do a relevance analysis
based on the causal graph. You find this implemented in
variable_order.find_and_apply_variable_order(...).

You can disable it with option --keep-unimportant-variables:

./translate.py --keep-unimportant-variables domain.pddl prob04.pddl


Best,

Gabi

On 20.04.21 23:01, Nishanth Kumar wrote:
> Hi everyone,
>
> I have a specific question (apologies if it is simple and I'm just missing
> something) about one component of how FD's translator works. I've noticed the
> translator is able to delete some state-variables that are completely irrelevant
> to the PDDL planning particular problem. As a concrete, simple example of what
> I'm taling about, I created a variant of the Gripper domain (Domain File:
> https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/domain.pddl

> <https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/domain.pddl>,
> Problem File:
> https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/prob04.pddl
> <https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/prob04.pddl>)

> where the balls to be picked and placed by the gripper have different colors. I
> added a 'paint-ball' action that allows the agent to arbitrarily change the
> colors of various balls. I then created a standard problem instance (linked
> above) where the gripper simply has to move different balls to specific rooms
> (the color of the balls to be moved is not specified anywhere in the goal
> conditions).  When I ran FD's translator on this domain and problem instance,
> the resulting SAS+ file
> (https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/gripper-paint-4.sas

> <https://github.com/NishanthJKumar/gripper-painting-pddl/blob/main/gripper-paint-4.sas>)

> does not include any state-variables corresponding to the color of the balls,
> nor does it include any of the 'paint-ball' actions.
>
> I'm confused about this because after reading the FD JAIR paper as well as this
> paper about FD's translator,

> <https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.5522&rep=rep1&type=pdf>

> my understanding was that the translation + grounding process detects constant
> and one-way predicates, and also merges or deletes some predicates by inferring
> invariants/mutex-constraints. However, the 'ball-color' predicate is not
> constant or one-way, nor are different ball-color values unreachable in either
> the forward or backward direction (i.e: the 'paint-ball' action can be used to
> modify the ball color from the initial state, and doing so does not result in a
> dead-end). If my understanding here is correct (please do point out if it's
> wrong), what mechanism does FD's translator use to delete these state-variables
> and actions? In particular, if there is an existing paper/line of papers
> explaining how such variables and actions can be pruned during grounding, I'd
> very much appreciate some pointers and links to these!
>
> Best,
> Nishanth
>

> --
> You received this message because you are subscribed to the Google Groups "Fast
> Downward" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to fast-downwar...@googlegroups.com
> <mailto:fast-downwar...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/fast-downward/a0273c6d-4677-4444-a58b-962ffe046bc0n%40googlegroups.com
> <https://groups.google.com/d/msgid/fast-downward/a0273c6d-4677-4444-a58b-962ffe046bc0n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Malte Helmert]

On 20.04.21 23:01, Nishanth Kumar wrote:

> I'm confused about this because after reading the FD JAIR paper as well
> as this paper about FD's translator,

> <https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.5522&rep=rep1&type=pdf>

> my understanding was that the translation + grounding process detects
> constant and one-way predicates, and also merges or deletes some
> predicates by inferring invariants/mutex-constraints. However, the
> 'ball-color' predicate is not constant or one-way, nor are different
> ball-color values unreachable in either the forward or backward
> direction (i.e: the 'paint-ball' action can be used to modify the ball
> color from the initial state, and doing so does not result in a
> dead-end). If my understanding here is correct (please do point out if
> it's wrong), what mechanism does FD's translator use to delete these
> state-variables and actions? In particular, if there is an existing
> paper/line of papers explaining how such variables and actions can be
> pruned during grounding, I'd very much appreciate some pointers and
> links to these!

Dear Nishanth,

Gabi already explained what Fast Downward does there (and how to disable
it). Let me add why it is not described in the translator paper and give
you some literature pointers.

At the time the two papers you mention were published, Fast Downward
consisted of three separate parts:

1. translation
2. preprocessing (called "knowledge compilation" in the Fast Downward
JAIR paper)
3. search

The state variable pruning technique that you see here was originally
part of the preprocessing component and is described in Section 5.2.2 of
the Fast Downward paper, specifically this sentence: "Any state
variables which are not found to be goal ancestors are eliminated from
the planning task and causal graph, and associated operators and axioms
are removed".

In the years since these papers were written, all functionalities of the
preprocessor have been moved into the other two components, and today
Fast Downward only has the translation and search components. This
pruning technique ended up in the translation component.


I should also point out that better (= more powerful and fine-grained,
though also more time-consuming) pruning techniques of this kind exist.
A commonly used one is described in this paper:

Vidal Alcázar, Álvaro Torralba.
A Reminder about the Importance of Computing and Exploiting
Invariants in Planning.
Proc. ICAPS 2015, pp. 2-6.

Álvaro Torralba's home page has a link to an implementation. See
"h2-based preprocessor" on https://people.cs.aau.dk/~alto/software.html.

Best regards,
Malte

[Nishanth Kumar]

Thank you Malte and Gabi, this is very helpful!

Regards,

Nishanth