4. State-Based Planning (Classical Planning)

History of State-Based Planning (STRIPS)

STRIPS (Stanford Research Institute Problem Solver)

History:

• developed by Fikes and Nilsson (1971)

• foundation of modern state-based planners (PDDL)

Features of STRIPS

• States: represented by sets of atoms (= building blocks of the states)

• Operators: can act directly on states (that’s why it’s called state-based)

• Planning: can be performed by Classical Search or Tailor-made Algorithms

• STRIPS uses Closed-World Assumption

  (if something is not stated explicitly to be true, it is false)

States in STRIPS

• State Descriptions correspond to sets of ground atoms

  • Domain D = {a, b, c, d}

  • Predicates P = {ontable^1, clear^1, on^2}

  • s = {ontable(a), notable(c), on(b,c), …}

    
    

• Goals are usually also sets of ground atoms

  • G = {on(b,c), ontable(c)}

    
    

• Goal State: A state is called a goal state if G ⊆ s

  (state s is called a goal state if it contains a subset which satisfies the goal)

  
  

• Closed-World Assumption:

  all atoms in state s are assumed to be true, all others are assumed to be false (we’re just interested in true ones)

Operator Scheme (STRIPS)

Operator Scheme consists of

• an operator name followed be a sequence of variables and

• 3 lists that represent

  • PRE (preconditions)

  • ADD (positive effects)

  • DEL (negative effects)

Variables serve as placeholders for domain objects

Operator put:

Operator: put(X,Y)

PRE: {ontable(X), clear(X), clear(Y)}

ADD: {on(X,Y)}

DEL: {ontable(X), clear(Y)}

Operator Instantiation

We apply an operator by instantiating the variables (before: variables = placeholders) in the operator scheme

—> Applying a Substitution

Operator Application

• Instantiated operator o can be applied in a state s if Pre(o) ⊆ s

  (if atoms from pre-list are present, then we can apply operator)

• Applying o will change current state s to a new state s’ s’ = (s \ Del(o)) U Add(o)

  (delete elements from the del-list and add elements from add-list)

State-Space Model

• Operator application spans a search space

• si is connected to sj iff sj results from si when applying a single operator

State space: built by transitions and actions (we can apply any search algorithm, then we have state space)

State Space Model / Search-Space is not a Search Tree —> in search space we can go in 2 directions (in search tree we cannot)

STRIPS versus Situation Calculus

In STRIPS, everything we don’t change explicitly, remains unchanged (therefore we don’t need frame axioms) —> we assume all the time that our atoms are the only true facts (we don’t need Situations)

Situation Calculus

• Effect Axioms: preconditions and results of actions

  —> PRE, ADD, DEL inSTRIPS

• Frame Axioms: things that remain unchanged

  —> implicit in STRIPS

Planning Problems in STRIPS (Challenges of Planning)

Qualification Problem:

—> PRE-List

(prerequisites for an operator to be applicable, but doesn’t solve how many preconditions I have to mention)

Frame Problem:

—> STRIPS transfers everything to the next state automatically if not stated otherwise (DEL-List)

Ramification Problem:

—> ADD-List, DEL-List

(after each action, we are keeping track of all changes that happened; new + old no longer valid)

In Theory: all problems are covered

STRIPS solves the Frame Problem and allows a more convenient problem representation

Planning versus Classical Search

• Planning in STRIPS can be seen as a Classical Search Problem

  (starting from initial state, we want to reach goal state, path/sequence is important)

  
  

• States are sets of atoms

  
  

• Successors in search space are obtained by applying operators

  • one successor for each applicable operator

  • successor state is obtained from current state by deleting elements from DEL-list and adding elements from ADD-list

(—> In Local Search: we obtained neighbors by applying actions or the transition function to states)

Planning Algorithms

Classical Search (Forward Planning):

• Uninformed Search: usually variants of depth-first search (performance)

• Informed Search: variants of A*

Backward Planning (Relevant-State Search):

• Start from goal and apply operators backwards until a sequence of operators is found that reaches an initial state

• Advantage: may consider less irrelevant steps

  (when starting at goal state, I can limit the number of exploration, because of better guesses)

Planning Heuristics

• Search must be guided by good Heuristics (which way to go / which actions to make)

Heuristic: estimates the cost from state to goal state

• This can be achieved by relaxing the problem to an easier problem and solving the Relaxed Problem (e.g. removing some restrictions)

Ignore PRE-DEL Heuristic

• relax problem by ignoring PRE- and DEL-List of operators (only interested in ADD-List, so we see only the result of an action)

• each operator then satisfies a number of goals (goal state is a state that has goal as a subset)

• given a state, compute minimal number of operators that must be applied to satisfy goal

—> corresponds to Set-Cover Problem (still NP-hard)

- Set-Cover Problem: each operator is a subset because it adds some atoms —> so we need to know how many are needed to reach the goal state

• we can do better by using an approximate greedy solution that can be computed in polynomial time (or apply local search)

  (could be better in time, but could give incomplete solution & in Planning we need complete and correct solution)

• however, greedy solution may overestimate the cost

• hence, the corresponding heuristic is not admissible (A* guarantees optimality only for admissible heuristics)

  (heuristic give estimate to get from current to goal state)

  (overestimation: could give huger cost and would therefore exclude states that could be the goal state —> makes us ignore path-leading goal state)

Blocksworld

• In Blocksworld, goal can be identified with

  U = {onTable(C), on(B,C), on(A,B)}

• Each operator can be identified with a subset of U (only via the ADD-List)

  • Put(A,B): {on(A,B)}

    (this operator satisfies one of the atoms in the goal state we need to reach)

  • Put(A,C): {}

  • Put(B,C): {on(B,C)}

  • …

• Estimated cost comes down to the number of unsatisfied literals

  • we removed all preconditions, so we can so everything (= everything is possible)

  • so if we have one literal satisfied, we can satisfy the other two in 2 steps

Warehouse

• goal can be identified with set (e.g. order at location) U = {ItemAt(i1, x, y), ItemAt(i2, x, y), ItemAT(i3, x, y)} —> goal state: we need all items to be in location x and y

• we can think of U as a set of items

• PSUs correspond to subsets of U (the items in U that they carry)

• the minimal set cover of U corresponds to PSUs that we have to carry to location (x, y)

• Estimated Cost comes down to minimal number of PSUs that we have to carry (to reach this goal)

  
  

Ignore DEL Heuristic

• relax problem by ignoring only DEL-List of operators

• no operator will undo goals in relaxed problem

  (if goal state is reached, nothing can undo it, because the delete will never happen)

• relaxed problem is still NP-hard

• approximate solution can again be computed in polynomial time

  (can still give incorrect solution / incomplete / overestimates heuristic)

• corresponding heuristic is again not admissible

Summary STRIPS (= state-based planning)

• States: represented by sets of atoms (each state is a set that contains certain atoms describing certain parts of the world)

• Operators: are described by 3 lists (PRE, ADD, DEL) (complex, therefore relaxation)

• Frame problem is ‘solved‘ by leaving everything unchanged that is not changed explicitly

• Planning comes down to Classical Search (we are looking at structure all the time)

• State-Based Planning can be more efficient than deductive planning, but planning remains hard in general

Beyond STRIPS

• Planning Domain Definition Language (PDDL) extends STRIPS

• Development is driven by the International Planning Competition (IPC) since 1998

PDDL supports in particular

• Numeric Fluents

  • Contains(P, I, 100): PSU P contains 100 instances of item I

    —> gives number of items (makes it easier to control)

• Derived Predicates

  • PSUAt(P,X,Y) :- Carries(R,P), RobotAt(R,X,Y)

  • ItemAt(I,X,Y) :- Contains(P,I,N), N>0, PSUAt(P,X,Y)

    —> helps with ramification problem and the preconditions

PDDL Syntax is LISP-like and might look unfamiliar at first

• Syntax is simple:

  • Instead of f(x,y,z) as in modern languages, we have (f x y z)

    (Name of function and variables as arguments)

• PDDL representation contains at least

  • a domain definition (types, actions)

  • a problem definition (initial state, goal)

• PDDL is a declarative language that represents knowledge

• can be used with many different search and planning algorithms