Plan
``````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     :
At(Home,S0)&-Have(Milk,S0)&-Have(Bananas,S0)&(-Have(Drill,S0)
Goal state         :
#s At(Home,s)&Have(Milk,s)&Have(Bananas,s)&(Have(Drill,s)
Operators         :
\$a,s Have(Milk, Result(a,s)) <=>

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

FOL的缺點：(效率)
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)

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)
RESOLVE-THREAT(plan)
end

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

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
end

example : Shoes and Socks Problem
Step : S[]
S[0] (ACTION:Start, PRECOND:NIL, EFFECT:NIL)
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),
Finish:Op(ACTION:Finish,
PRECOND:RightShoeOn & LeftShoeOn)}
ORDERING     : {Start < Finish}
BINDING      : {}

1 : MAKE-MINIMAL-PLAN
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)

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 ..

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

Resources
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,
Plan(STEPS:{S1:Build(Foundation),
S2:Build(Frame),
S3:Build(Roof),
S4:Build(Walls),
S5:Build(Interior)}
ORDERING:{S1<S2<S3<S5, S2<S4<S5},
BINDINGS:{}

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])
RESOLVE-THREATS(plan)
end

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)
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:..,..}
中，至少有一個step的precondition與effect與Operator完全相同。

Sharing : getMerried↗ honeyMoon
↘haveBaby

input
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

Disjunctive goal :
implement : 很難處理。

Universal quantification
example :
Op(ACTION:  Carry(bag,x,y),
PRECOND:Bag(bag)&At(bat,x),
EFFECT: At(bag,x),-At(bag,x)&\$i Item(i) => At(i,y)&-At(i,x)) when In(i,bag))

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 :
Op(ACTION:Start,
Effect: Cash := \$(12.50) &
GasLevel := Gallons(5)
..)
Effect:Have(x)&
Cash:=Cach-Price(x,store))

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)
+(Seconds(10)/Gallons(1))*Gallons(15)-GasLevel))

Chapter 13 Planning and Action

Conditional Planning (contingency planning) :  （事先規劃）
including sensing action in the plan to test for the appropriate
condition
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,

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.
(參考405頁的圖)

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.```
```
page revision: 1, last edited: 18 Sep 2010 10:25