Existentially Quantified Variables

[harshakokel]

Hello,

How to ignore the existentially quantified variables in the successor generator?

Regards, Harsha Kokel

[abcorrea]

Hi Harsha,

I think there are two ways we can define "existentially quantified variables" in this case:

1. In the ICAPS 2020 paper on lifted successor generators, a variable is existentially quantified if it appears in the precondition but not in the effect. The successor generator using the Yannakakis' algorithms deals with it. (You can use this successor generator with the command line option-s yannakakis.) The way it deals with it is not by ignoring it, but by keeping a single instantiation for each of these variables. There is no current way to completely ignore (i.e., discard) them because this could make the successor generation incorrect.
2. In ADL, there are variables that can be existentially quantified using the keyword exists. (See the airport-adl domain from the IPC 2004 for an example.) Unfortunately, Powerlifted currently only supports STRIPS and hence the ADL fragment of PDDL is not supported.

Best, Augusto

[harshakokel]

Hello Augusto,

Thank you for your prompt reply, appreciate it.

I am wandering how would the following scenario be handled in this case. Say we have an action as below, where ?y is an existentially quantified variable which occurs in precondition but not in effect. Would in such case the single instance for y variable obtained be made consistent across predicates near and has? If so, how would the join between these two predicates happen without querying for y variable?

(:action hypothetical-action
:parameters (?x  ?y)
:precondition (and 
    (at ?x)
    (near ?y)
    (has ?y)
)
:effect (and
     (in ?x))
)

[abcorrea]

Hi,

We still query the variable y. The difference is that we keep a single answer to the query, instead of all. For example, if our state s is defined as

s = {at(A), near(B), near(C), near(D), has(B), has(C), has(D)}

then there are three possible instantiations for x and y in the hypothetical-action, namely (A,B),(A,C),(A,D). The successor generator would automatically infer that all three instantiations lead to the same successor -- because y is existentially quantified -- and it would use only one of them.

I think the procedure is more clear if we make the action slightly more complicated. Let us say that we have the following action:

(:action hypothetical-action2
:parameters (?x  ?y ?z)
:precondition (and 
    (at ?x ?z)
    (near ?x ?y)
    (has ?y)
)
:effect (and
     (in ?x))
)

Once again, y is existentially quantified, and so is z. Roughly speaking, we can start by joining (has ?y) and (near ?x ?y). After we join these, we can keep a single tuple for each different value of x. For example, if we had (near A B), (near A C), (near D B), (near D C) and (has B), (has C), the join of these two relations would have tuples (A B), (A C), (D B), (D C). But keeping only one tuple for each value of x -- in this case, A and D -- would still guarantee that we generate all successors. For example, we could keep only (A B) and (D B). When we join with (at ?x ?z), we have only to join two tuples instead of four.

Note that we first actually compute the complete join and then project out the existentially quantified variables. However, one could also do that whenever it joins a new tuple.

[harshakokel]

Thank you. This makes sense.