Class Notes on STRIPS

Assumptions in PDDL and STRIPS action schemas

Here is a brief outline of the constraints used for action schemas in STRIPS and PDDL. PDDL is more general than STRIPS, it allows preconditions and goals to contain negative literals.

Initial State:	conjunction of function free ground literals. In STRIPS no negative literals can be used in the initial state. In PDDL negative literals are allowed, but with the closed world assumption, whatever is not explicitely stated is assumed to be false.
Goal:	conjunction of literals. variables are allowed. (Implicitely) they are considered existentially quantified. In STRIPS no variables are allowed in goals, but there can be variables in PDDL.
Preconditions:	conjunction of literals. In STRIPS no negative literals can be used in the preconditions. Variables are allowed. Most of the time, the variables used are the ones in the list of variables for the action schema. If they are not, (implicitely) they are considered existentially quantified.
Effects:	conjunction of positive and negative literals. The interpretation is that positive literals describe what is added to the world as an effect of the action and negative literals describe what is deleted from the world.

Why the differences between STRIPS and PDDL add complexity

+ indicates what is available in PDDL but not in STRIPS

Goal:	conjunction of positive ground literals + conjunction of negative literals This requires unification to match "p" and "not not p", It also requires goals with negative literals to be matched against the initial state. "not p" is satified in the initial state unless "p" is in the initial state. + disjunction of positive or negative literals Adding disjunction is simple, it requires a non deterministic choice when selecting a goal. + variables are (implicitely) considered existentially quantified. + universally quantified variables are allowed Universally quantified variables require assuming the world to be finite, static, and typed, so the quantification is satisfied by enumeration. All objects must be in the initial state and must have a type. Example: forall(p) passenger(p) implies served (p) Example: forall(o) object(o) implies at(o,Home)
Preconditions:	conjunction of positive literals. + disjunction of positive literals. A disjunction such as "p or q" requires a non deterministic choice. The same effect could be achieved less efficiently by writing two separate operators, one with "p" and one with "q" as precondition. Example: part-of(p,w) or single(p) + existentially quantified variables are allowed + universally quantified variables allowed Universally quantified variables require assuming the world to be finite, static, and typed, so the quantification is satisfied by enumeration. All objects must be in the initial state and have a type. Example: forall(x) block(x) implies not on(x,b) Example: forall(r) resource(r) implies committed(r,p) existentially quantified variables allowed
Effects:	conjunction of positive and negative literals. Disjunctions are not allowed since this would introduce non determinism. + universally quantified variables allowed Universally quantified variables require assuming the world to be finite, static, and typed, so the quantification is satisfied by enumeration. All objects must be in the initial state and must have a type. + conditional effects, where both the antecedent (or condition) and the consequent (or effect) are conjunctions of literals. The antecedent refers to the world before the action is executed, the consequent refers to the world afther the action is executed. Example: at(car,city2) and not at(car,city1) when connected(car,engine) Example: forall(p) passenger(p) implies served(p) when destination(p,f)

Goal:

conjunction of positive ground literals

+ conjunction of negative literals
This requires unification to match "p" and "not not p", It also requires goals with negative literals to be matched against the initial state. "not p" is satified in the initial state unless "p" is in the initial state.

+ disjunction of positive or negative literals
Adding disjunction is simple, it requires a non deterministic choice when selecting a goal.

+ variables are (implicitely) considered existentially quantified.

+ universally quantified variables are allowed
Universally quantified variables require assuming the world to be finite, static, and typed, so the quantification is satisfied by enumeration. All objects must be in the initial state and must have a type.
Example: forall(p) passenger(p) implies served (p)
Example: forall(o) object(o) implies at(o,Home)

Preconditions:

conjunction of positive literals.
+ disjunction of positive literals.
A disjunction such as "p or q" requires a non deterministic choice. The same effect could be achieved less efficiently by writing two separate operators, one with "p" and one with "q" as precondition.
Example: part-of(p,w) or single(p)

+ existentially quantified variables are allowed

+ universally quantified variables allowed
Universally quantified variables require assuming the world to be finite, static, and typed, so the quantification is satisfied by enumeration. All objects must be in the initial state and have a type.
Example: forall(x) block(x) implies not on(x,b)
Example: forall(r) resource(r) implies committed(r,p) existentially quantified variables allowed

Effects:

conjunction of positive and negative literals.
Disjunctions are not allowed since this would introduce non determinism.

+ conditional effects, where both the antecedent (or condition) and the consequent (or effect) are conjunctions of literals.
The antecedent refers to the world before the action is executed, the consequent refers to the world afther the action is executed. Example: at(car,city2) and not at(car,city1) when connected(car,engine)
Example: forall(p) passenger(p) implies served(p) when destination(p,f)