Intro to AI Ch. 5 - Planning

STRIPS Approach

A simple representation language for planning

STandford Research Institute Problem Solver

Sublanguage of FOPL, encode states, goals, and actions

Originally made to control robot Shakey

Planning

The process of mechanically and efficiently finding a sequence of actions that achieve a goal, once executed

Assumptions of planning problems

• Goal is a conjunction of sub-goals

• Actions are atomic, sequential, and deterministic

  • Indivisible, cannot be executed concurrently, and no uncertainty

• Planning agent knows all it needs to know about the environment

• ‘Closed World’ - describe a state by listing what is true; anything else is assumed false

Operator

How actions are represented

Have three components:

• Name - to identify action

• Precondition - things that need to be true for action to take place

• Effect - may be to add or delete facts from the problem state

Problem state representation

Represented as a list of facts that are true - ‘a conjunction of positive literals’

Blocks world

A planning domain consisting of a table and blocks, in which only one block may be moved at a time. Used in AI research due to its simplicity

Progression Planning

Searching forward from initial states to goal states. Search strategies are examples of progression planning

Regression Planning

Starting from the goal state and tracing it back to the initial state

Backward chaining

Look for a match between an operator’s add pattern and the goal. Then treat the unsatisfied preconditions of the operator as subgoals and continue backward chaining.

The regression of a goal G through an action A is the least constraining precondition R[G,A] such that: if a state S satisfies R[G,A], then the precondition of A is satisfied in S, and applying A to S yields a state that satisfies G

Establishes/Enabling Links

Links between the add patterns of operators and the goal state (or preconditions of other operators)

The operator that establishes the assertion must appear in the final plan before the operator that requires the assertion

Sussman Anomaly

In adding an assertion needed by one operator, may withdraw an assertion that was previously added to establish a different precondition/goal.

If an operator poses a threat to the establishes link between two operators, the threatening operator cannot appear between them.

Complete plan/Ordering net

A plan in which every goal is satisfied, every precondition is met, and there are no cycles

Total Order Plan

A complete plan in which the ordering of steps has been determined as a linear sequence

Partial Plan

A plan is not complete; some of the goals may not be satisfied, some of the orderings are not defined

Ordering Constraint

Specifies the order in which operators must appear to ensure that additional operators do not conflict

Topological Sort

Used total order plan from a complete, partial order plan

Partial Instantiation

Only instantiate operators as necessary, i.e., when specifics are not necessary, use placeholders (x, y, etc.). Only need to insist that they are bound to the same thing.

Principle of Least Commitment

If there is uncertainty about what move is correct then commit to as little as possible

Action Description Language (ADL)

Can be seen as an extension of STRIPS

Contains typing of parameters

Allows explicit expression of negation

Allows equality of terms in precondition formula

Other STRIPS alternatives such as PDDL, APPL, MA-PDDL, etc.)