Planning
Motivation
Technical Solution
Illustration by a Larger Example
Extensions
Summary
References
Motivation
Goal: Buy 1 liter of milk
It may sound like a simple task, but if you break it down, there are many small tasks involved:



TECHNICAL SOLUTIONS
Use a Heuristic function to estimate G or Idistance, respectively – prefer states that have a lower heuristic value.
It will also introduce partialorder planning as a more flexible approach
REPRESENTATION
A problem to be solved by a planning system is called a planning problem
The world in which planning takes place is often called the domain or application domain.
A state is a point in the search space of the application
A planning problem is characterized by an initial state and a goal state .
The initial state is the state of the world just before the plan is executed
The goal state is the desired state of the world that we want to reach
after the plan has been executed. A goal state is also refer as simply goal
Stanford Research Institute Problem Solver (STRIPS) is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 [Nilsson & Fikes, 1970]
STRIPS is also the name of the planning language used for the STRIPS planner
A state (excluding the goal state) is represented in STRIPS as a conjunction of functionfree ground literals
e.g. on(A, Table) ^ on (B, A) ^ ¬ clear(A) ^ clear(B)
(block A is on the Table, block B is on block A, block A has something on top, block B has nothing on top)
A conjunction of functionfree ground literals is also know as a fact
A goal is represented in STRIPS as a conjunction of literals that may contain variables
e.g. on(B, Table) ^ on (A, B) ^ clear(A) ^ ¬ clear(B)
(block B is on the Table, block A is on block B, block B has something on top, block A has nothing on top)
Definition – Action
Let P be a set of facts. An action a is a triple a = ( pre(a ), add(a ), del(a )) of subsets of P , where add(a ) \ del(a ) = Ø
pre(a ) , add(a ) , and del(a ) are called the action precondition , add list , and delete list , respectively
Delete List: list of formulas to be deleted from the description of state before the action is performed
The action pickup in the Blocks World domain can be modeled as follows in STRIPS
pickup(x)
Preconditions : on(x, Table) ^ handEmpty ^ clear(x)
Add List : holding(x)
Delete List : on(x, Table) ^ handEmpty ^ clear(x)
Definition – Task
A task is a quadruple (P,A,I,G) where P is a (finite) set of facts, A is a (finite) set of actions, and I and G are subsets of P, I being the initial state and G the goal state.
A goal state i.e. the desired state of the world that we want to reach
result(s , ‹a , a1› ) = result(result(s , ‹ a › ), ‹a1› ) = result(s1, ‹a1› ) = s1 ∪ add(a1)) \ del(a1)
= ((holding (A) ^ clear(B ) ∪ holding(x ) ^ on(x,y ) ^ handEmpty ^ clear(x )) \ holding(x ) ^ clear(y )
= on(A,B ) ^ handEmpty ^ clear(A )
Precondition hoding(x ) ^ clear(y ) is fulfilled in state s1 = holding(A ) ^ clear(B )
Definition – Minimal Plan
Let (P,A,I,G) be a task. A plan ‹a_{1}, . . . ,a_{n}› for the task is minimal if ‹a_{1}, . . . , a_{i}1, a_{i}+1, . . . ,a_{n}› is not a plan for any i.
Definition – Optimal Plan
Let (P,A,I,G) be a task. A plan ‹a_{1}, . . . ,a_{n}› for the task is optimal if there is no plan with less than n actions


ALGORITHMS
We now present particular algorithms related to (direct) statespace search:
Progression based search also know as forward search
Regression based search also know as backward search
Heuristic Functions and Informed Search Algorithms
Definition – Search Scheme
A search scheme is a tuple (S, s_{0}, succ, Sol):
the set S of all states s ∈ S,
the start state s_{0} ∈ S,
the successor state function succ : S → 2^{S}, and
the solution states Sol ⊆ S.
Solution paths s_{0} →, ... , → s_{n} ∈ Sol correspond to solutions to our problem
Regression algorithm:
Start with the goal
Choose an action that will result in the goal
Replace that goal with the action’s preconditions
Repeat steps 23 until you have reached the initial state
Regression is not as nonnatural as you might think: if you plan a trip to Thailand, do you start with thinking about the train to Frankfurt?
Definition – Heuristic Function
Let (S, s _{ 0 } , succ , Sol) be a search scheme. A heuristic function is a function h : S → N _{ 0 } ∪ { ∞ } from states into the natural numbers including 0 and the ∞ symbol. Heuristic functions , or heuristics , are efficiently computable functions that estimate a state’s “solution distance”.
A heuristic function for Blocks World domain could be:
h1(s) = n – sum(b(i )) , i =1… n , where
b(i )=0 in state s if the block i is resting on a wrong thing
b(i )=1 in state s if the block i is resting on the thing it is supposed to be resting on;
n is the total number of blocks
h1(I) = 3 – 1 (because of block B) – 0 (because of block C) – 0 (because of block A) = 2
h1(G) = 3 – 1 (because of block B) – 1 (because of block C) – 1 (because of block A) = 0
Definition – Solution Distance
Let (S, s _{ 0 } , succ , Sol) be a search scheme. The solution distance sd(s ) of a state s ∈ S is the length of a shortest succ path from s to a state in Sol , or 1 if there is no such path. Computing the real solution distance is as hard as solving the problem itself.
Definition – Admissible Heuristic Function
Let (S, s_{0} , succ , Sol) be a search scheme. A heuristic function h is admissible if h(s ) ≤ sd(s ) for all s ∈ S .
In other words, an admissible heuristic function is a heuristic function that never overestimates the actual cost i.e. the solution distance.
e.g. h1 heuristic function defined below is admissible
h1(s) = n – sum(b(i )) , i =1… n , where
b(i )=0 in state s if the block i is resting on a wrong thing
b(i )=1 in state s if the block i is resting on the thing it is supposed to be resting on;
n is the total number of blocks
COMPLEXITY AND DECIDABILITY
Its time complexity : in the worst case, how many search states are expanded?
Its space complexity : in the worst case, how many search states are kept in the open list at any point in time?
Is it complete , i.e. is it guaranteed to find a solution if there is one?
Is it optimal , i.e. is it guaranteed to find an optimal solution?
Definition  PLANSAT
Let PLANSAT denote the following decision problem. Given a STRIPS task (P, A, I, G), is the task solvable?
Theorem
PLANSAT is PSPACEcomplete. Proof in see [Bylander, 1994]
Definition – Bounded PLANSAT
Let BoundedPLANSAT denote the following decision problem. Given a STRIPS task (P, A, I, G) and an integer b . Is there a plan with at most b actions?
ILLUSTRATION BY A LARGER EXAMPLE
PROGRESSION
s12 = result(s0, ‹pickup(B)›) = on(A, Table) ^ on(B, Table) ^ on(C, Table) ^ on(D, C) ^ clear(A) ^ clear(B) ^ clear(D) ^ handEmpty ∪ holding(x) \ on(x, Table) ^ handEmpty ^ clear(x) = on(A, Table) ^ on(C, Table) ^ on(D, C) ^ clear(A) ^ clear(D) ^ holding(B)
s13 = result(s0, ‹unstack(D,C)›) = on(A, Table) ^ on(B, Table) ^ on(C, Table) ^ on(D, C) ^ clear(A) ^ clear(B) ^ clear(D) ^ handEmpty ∪ holding(x) ^ clear(y) \ on(x, y) ^ handEmpty ^ clear(x) = on(A, Table) ^ on(B, Table) ^ on(C, Table) ^ clear(A) ^ clear(B) ^ clear(C) ^ holding(D)
REGRESSION
Step 3:
sn1=regress(G, stack(C,A)) = G \ add(stack ) ∪ pre(stack ) = on(A, Table) ^ on(D, Table) ^ on(C, A) ^ on(B,D) ^ clear(C) ^ clear(B) ^ handEmpty \ on(C,A) ^ handEmpty ^ clear(C) ∪ holding(C) ^ clear(A) = on(A, Table) ^ on(D, Table) ^ on(B, D) ^ clear(B) ^ clear(A) ^ holding(C)
sn2=regress(G, stack(B,D)) = G \ add(stack ) ∪ pre(stack ) = on(A, Table) ^ on(D, Table) ^ on(C, A) ^ on(B,D) ^ clear(C) ^ clear(B) ^ handEmpty \ on(B,D) ^ handEmpty ^ clear(B) ∪ holding(B) ^ clear(D) = on(A, Table) ^ on(D, Table) ^ on(C, A) ^ clear(C) ^ clear(D) ^ holding(B)
EXTENSIONS
Forward and backward statespace search are both forms of totallyordered plan search – explore linear sequences of actions from initial state or goal.
As such they cannot accomodate problem decomposition and work on subgraphs separately.
A set of open preconditions not achieved by any action in the current plan


Partial Order Plan:

Total Order Plans:




Compared with a classical search procedure, viewing a problem as one of constraint satisfaction can reduce substantially the amount of search.
Constrainbased search involved complex numerical or symbolic variable and state constraints
ConstraintBased Search:
1. Constraints are discovered and propagated as far as possible.
2. If there is still not a solution, then search begins, adding new constraints.
Constrain the task by a time horizon, b
Formulate this as a constraint satisfaction problem and use backtracking methods to solve it: “do x at time t yes/no”, “do y at time t ’ yes/no”,
If there is no solution, increment b
Inside backtracking : constraint propagation, conflict analysis are used
ConstraintBased Searcg is an “undirected” search i.e. there is no fixed timeorder to the decisions done by backtracking
SUMMARY
REFERENCES
Questions?