Planning

Question 1

What is a STRIPS operator?

Answer 1

It is a combination of three things:

• Action description: Defines what action does.
• Precondition. Defines what must be true before action can be used. A conjunction of positive literals.
• Effect: Defines what is true after using operator. A conjunction of literals (either polarity).

Question 2

What does a plan consist of?

Answer 2

Question 3

A plan is solution iff it is complete and consistent.

What does it mean by ‘complete’ and ‘consistent’?

Answer 3

• Complete: Each precondition of each step is achieved by another previous step in the solution, and no other step cancels the precondition.
• Consistent: No contradictions exist in the binding constraints or in the proposed ordering. That is, we don’t bind a variable to multiple distinct constants, and we won’t have loops in casual ordering.

Question 4

What does it mean by a threat?

How can a planner attempt to fix a threat?

Answer 4

A step that might invalidate/clobber a previously achieved precondition is called a threat.

A planner can try to fix a threat by introducing an ordering constraint (promotion/demotion).

Question 5

How do we construct a planning graph?

Answer 5

A planning graph is constructed in levels:

• Level 0 corresponds to the start state.
• At each level we keep approximate track of all things that could be true at the corresponding time.
• At each level we keep approximate track of what actions could be applicable at the corresponding time.

Question 6

What are the five different types of mutex links that can be applied in a planning graph?

Answer 6

1. [Actions] The effect of one action negates the effect of another.
2. [Actions] The effect of an action negates the precondition of another.
3. [Actions] The precondition for an action is mutually exclusive with the precondition for another.
4. [State] Pair consists of a proposition and its negation.
5. [State] All pairs of actions that could achieve the pair of propositions are mutex.

Question 7

How do we extract plans from graphs?

Answer 7

We start from bottom-most state - the level where all goals appear and no pair has mutex link.

Extraction can be formalized as a search problem.

• For any state S with level S_i, select any set X of actions in A_i such that no pairs of actions and corresponding preconditions have mutex link. The action should achieve some propositions in S.
• Each action has cost 1, and we search from bottom of graph to root.