Chapter 11 Planning

1.     Open up representation : (state, goal, action)
    Precondition => Action => Effect
2.     Free to add action : Planner is free to add action to the plan wherever they are needed, rather than in an incremental sequence starting at the initial state.
3.     Independent : Most parts of the world are independent of most other part. May use Divide and Conquer .

Planning in Situation Calculus
Initial state     : 
Goal state         :
  #s At(Home,s)&Have(Milk,s)&Have(Bananas,s)&(Have(Drill,s)
Operators         :
  $a,s Have(Milk, Result(a,s)) <=> 
  [(a = Buy(Milk)&At(Supermarket,s)|(Have(Milk,s) & a≠Drop(Milk)))]

Basic assumpution :
  $s Result([],s) = s
  $a,p,s Result([a|p],s) = Result(p, Result(a,s))

1.     s = Result(A-1, Result(A,s)) // 這種情形是做白工,必須避免。

STRIP Language :
State : conjunction of function free ground literal.
Goal  : conjunction of literal may contain variable.
Operator : Precondition => Action => Effect

Progression planner : 
  search forward from initial state to goal state.

Regression planner  : 
  search backward from goal state to initial state.

Partial planner     : 
  expanding the partial plan into a complete plan.

Representations for plans

least commitment : one should only make choice about things that you currently care about, leaving the other choice to be worked out later.

Partial Order planner v.s. Total Order planner

Component of Plan : 
1.     Plan Steps : operator set.
Example :
  Start     :Op(ACTION:Start), 
  Finish    :Op(ACTION:Finish,PRECOND:RightShoeOn & LeftShoeOn)}
2.     Ordering constraint (Si < Sj)
Example : Start < Finish
3.     Variable binding constraint

4.     Causal links : Si –-- (c) ----> Sj 
    (Si achieve the precondition of Sj)
    Start –--(LeftShoeOn, RightShoeOn)---> Finish

Achieved : Si achieved a precondition c of the Sj iff
  1. Si < Sj and C in EFFECTS(Si)
2.     !# Sk, Si<Sk<Sj and (-c) in EFFECTS(Sk)

Contradiction :
Ordering contradiction     : Si < Sj and Sj < Si 
Binding contradiction     : v = A and v = B

Complete Plan         : 
  Every precondition of every step is achieved by some other step.

Consistent Plan     :
  No Contradiction in the ordering or binding constraint.

Partial Order Planning Algorithm
function POP(initial, goal, operator) returns plan
  plan := MAKE-MINIMAL-PLAN(initial, goal)
  loop do
    if SOLUTION?(plan) then return plan
S[need], C := SELECT-SUBGOAL(plan)
CHOOSE-OPERATOR(plan, operators, S[need], C)

function SELECT-SUBGOAL(plan) return S[need], C
  pick an plan step S[need] from STEPS(plan)
     with a precondition C that has not been achieved
  return S[need], C

procedure CHOOSE-OPERATOR(plan, operator, S[need], C)
  choose a step S[add] from operators or STEPS(plan) that has C as effect
  if there is no such step then fail
  add the causal link S[add]---(c)---> S[need] to LINK(plan)
  add the ordering constraint S[add]---(c)---> S[need] to ORDERINGS(plan)
  if S[add] is a newly added step from operator then
add S[add] to STEPS(plan)
add Start < S[add] < Finish to ORDERINGS(plan)

procedure RESOLVE-THREATS(plan)
  for each S[threat] that threatens a link Si --(c)-->Sj in LINK(plan) do
choose either
   Promotion     : Add S[threat] to ORDERINGS(plan)
   Demotion      : Add Sj < S[threat] to ORDERINGS(plan)
if not CONSISTENT(plan) then fail

example : Shoes and Socks Problem
Step : S[]
  S[∞](ACTION:Finish, PRECOND:RightShoeOn & LeftShoeOn)
Operator : Op[]
  Op[1]:(ACTION:LeftSock,  PRECOND:NIL, EFFECT:LeftSockOn)
  OP[2]:(ACTION:RightSock, PRECOND:NIL, EFFECT:RightSockOn)
  OP[3]:(ACTION:LeftShoe,  PRECOND:LeftSockOn, EFFECT:LeftShoeOn)
  OP[4]:(ACTION:RightShoe, PRECOND:RightSockOn,EFFECT:RightShoeOn)
Condition : C[]
  C[1] : LeftSockOn
  C[2] : LeftShoeOn
  C[3] : RightSockOn
  C[4] : RightShoeOn

initial plan :
Plan = STEP:{Start :Op(ACTION:Start),
                            PRECOND:RightShoeOn & LeftShoeOn)}
                ORDERING     : {Start < Finish}
                BINDING      : {}
                LINKS         : {}

   Start(S0) ---(LeftShoeOn, RightShoeOn) ---> Finish(S5)

2 : S[need], C = SELECT-SUBGOAL(plan)
   S[need] = LeftShoeOn, C = NULL

3 : S[need], C = CHOOSE-OPERATOR(plan, op[], S[need], C)
   S[need] = OP3(LeftShoe)
   OP3(LeftShoe)--(LeftShoeOn)--> Finish //S[add]--(c)--> S[need]

Chapter 12 Practical Planning

Operation Research : PERT chart, critical path method.

4 concept that STRIP does not support
Hierarchical Plans
STRIP doesn’t allow abstract step 
example :
high level       : Build(House)
middle level     : Install(floor)
low level          : Hammer(Nail)

Complex conditions
STRIP allow variable only use in limit way
example : $x ..

STRIP is based on situation calculus
example : concurrency , deadline, duration action

STRIP cannot handle constraints on resources efficiently.

Least commitment

Hierarchical Decomposition
example :
               Own land               Have house
  Buy land -------------> Build -------------> Move in
  Get loan -------------> House                   
               Have money

         Own land                                     
  Buy land-->Obtain Permit↘Construct-> Pay Builder--> Move in
               Hire Builder↗            ↗
  Get loan--------------------------

Primitive operator 
ex : Hammer(Nail)
Nonprimitive operator
ex : Install(FloorBoards)

Decomposition Method : Decompose(operator, plan)
ex : Decompose(Construction, 
                ORDERING:{S1<S2<S3<S5, S2<S4<S5},
              LINKS:{S1->S2, S2->S3, S2->S4, S3->S5, S4->S5}))

p correctly implement o iff
1.     p is complete and consistent 
2.     Effect(o) in Effect(p)
3.     Precondition(Pi) in (Effect(Pi) + Precondition(o))

function HD-POP(plan, operators, methods) returns plan
  input : plan, an abstract plan with start and goal steps
  loop do
if SOLUTION?(plan) then return plan
S[need], C := SELECT-SUB-GOAL(plan)
CHOOSE-OPERATOR(plan, operator, S[need], C)
S[nonprim] := SELECT-NONPRIMITIVE(plan)
CHOOSE-DECOMPOSITION(plan, methods, S[nonprim])

Data structure
  STEPS        += STEPS(Decompose(o,p)) - nonprim(o,p)
  BINDING    += BINDING(Decompose(o,p))
  ORDERING    : 
    Sa < S[nonprim] => add Sa < Sm, ($j Sm !< Sj)
    S[nonprim] < Sz => add Sm < Sz, ($j Sj !> Sm)
  LINK        : 
    Si -(c)-> S[nonprim] => Si -(c)-> Sm($j Sm !< Sj)
    S[nonprim] -(c)-> Si => Si -(c)-> Sm($j Sj !> Sm)

Analysis of Hierarchical Decomposition
  downward solution property : 
  abstract-solution(p) => primitive-solution(x) & abstract(x,p)
  upward solution property     : 
  primitive-solution(x) => abstract-solution(p) & abstract(x,p)

Complexity of POP          : b^s^d  = O(b^s^d)
Complexity of HD-POP     : Σbs^i = O(b*s^d)
b: branching factor
s: steps in a decomposition method
d: depth of the hierarchical plan

unique main subaction condition
  Decompose(Operator, Plan(STEPS:{S1:..,S2:..,..}
                ORDERING:.. BINDINGS:.. LINKS:..)

Sharing : getMerried↗ honeyMoon

Critics : plan -----> critics -----> modified plan

Hierarchical Decomposition : 
  abstract, nonprimitive can be decomposed into a more complex network of step

Abstract Hierarchy (approximation hierarchy) : 
critical condition in level1            ex : Buy1
critical condition in level1+level2    ex : Buy2

critical : 買奶粉時,可能找對商店很重要,買房子時,有錢才是most critical condition.

Confrontation (對質): -c’ when p, 
may resolve threat by making sure that p doesn’t hold.

Negate :
  unify(p, --p)
  unify(-p, -p) & unify(-p, initial has no p)

Disjunctive precondition:
implement :  e when p|q => e when p, e when q
如此可以使back track容易 implement。

Disjunctive goal :
ex: Flip(coin) => Heads(coin)|Tails(coin)
implement : 很難處理。

Universal quantification
example :
Op(ACTION:  Carry(bag,x,y),
  EFFECT: At(bag,x),-At(bag,x)&$i Item(i) => At(i,y)&-At(i,x)) when In(i,bag))
注意:加上universal quantifier後,仍然不是FOL,因為只允許finite, static, typed universe of object
static : object cannot change type or be destroyed.
Implement : 
  $x T(x) => C(x) --> C(x1)&C(x2)&..&C(xn)
example :
  Initial state    : Bag(B)&Milk(M1)&Milk(M2)&Milk(M3)
  Expression         : $x Milk(x) => In(x,B)
  Expansion            : In(M1,B)&In(M2,B)&In(M3,B)

actual - non actual object
  加上actual property可以解決無法dynamic create object的問題。

Resource Constraint
  measures fluents : 隨時間而變動的measures.
  Example :
       Effect: Cash := $(12.50) & 
                GasLevel := Gallons(5)

  Rough Check : by minimum and maximum possible constraint
  if minimum(x) < measure(x) < maximum(x) then go on
                                                 else fail
  Temporal Constraint :
  example : 
suppose it takes 10 seconds to pump each gallon of gas , 
then the time consume by Fillup action is :
Time := Time + Minutes(3) 

Chapter 13 Planning and Action

Conditional Planning (contingency planning) :  (事先規劃)
including sensing action in the plan to test for the appropriate 
example :
  $x,s Tire(x)=>KnowsWhether(“Intact(x)”,Result(CheckTire(x),s))
  Op(ACTION: CheckTire(x), 
     PRECOND: Tire(x), 
     EFFECT: KnowWhether(“Intact(x)”))
  CheckTire(x) is called conditional step, 
  Links from CheckTire is called conditional link.

Parameterized plans :
example :
  Color(Chair, c) & Color(Table, c)

Run time variable :
example : 
  $x,s #c KnowWhat(“Color(x,c)”, Result(SenseColor(x),s))

  Op(ACTION: SenseColor(x), 
     EFFECT: KnowWhat(“Color(x,c)”))

Execution monitoring (replanning) : (事後治療)
  monitoring is any things goes wrong, if “yes” then replanning.

Cause of plan failure :
  Bounded indeterminacy (可事先列舉的): 
  Unbounded indeterminacy (不可事先列舉的):

Triangle table : 比較precondition of plan和percept
Action monitoring : 比較precondition of action 和percept

Situated agent continuously monitors the world, updating its world model from new percepts even if its deliberations are still continuing.
Example :
  block world with impatient teacher move the block before agent move it and clumsy agent drop block in incorrect position.

Coercion (強制): reduce uncertainty about world by forcing it into a known state regard the initial state.
Example : paint table and chair together to make sure they are in the same color.

Abstraction : ignore detail of a problem about which it may not have exact and complete knowledge.
Example : Fly(London, Paris)

Aggregation : individual uncertainty eliminated by statistic.
Example : Government plan its cash flows.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License