(sequence of states initial --> final )

• break into subproblems
• record and handle interactions (opportunistic)
• put whole plan together

• not decomposable (nearly decomposable)
  small amount of interaction (going to store for food - out of gas?)
• frame problem
  • what changes (e.g. airplane flight
  • what doesn't luggage, fuel)

total states

• *set of possible (likely) outcomes

• (can solution steps be ignored or undone)
• interactions(for a computer, plan => plan, for human actual actions cause problems)

• subproblem (failure local?) (cake: drop egg on floor..clean first?
  what dropped? solid? still do other task first?)
• replanning

• when new plan vs. replan (dependency-directed backtracking)

• too many potential futures, dependencies

Uses: scheduling, graphics

Example: blocks world - robot arm pg. 332-347

Plan:

• record the operator applied

• update data base

How know when done?
• states are a set of relevant properties
  (= state description)
• equivalent states?

  end described from reasoning process

Goal Stacks

I)	II)
On(a,b)	On(b,c)
On(b,c)	On(a,b)
On(a,b) and On(b,c)	On(a,b) and On(b,c)

consider: multiple conjunctions ... permutations

*each time!

On(C,A)	Operator Sequence
Clear(C)	(Plan)
ArmEmpty
Clear(C) and ArmEmpty and On(C,A)	Unstack(C,A)
-Unstack (C,A)	PutDown(C)
ArmEmpty	PickUp(A)
Clear(A) and ArmEmpty and OnTable(A)	Stack(A,B)
-PickUp (A)	.
Clear(B) and Holding (A)	.
-Stack (A,B)	.
On (B,C)
On (A,B) and On(B,C)	picture now
->	world view

On(B,C)

On(A,B) and On(B,C)

.

.

.

->

On(A,B) and On(B,C)

->

On(A,B)

On(A,B) and On(B,C)

Need: method capable of finding efficient way!

linear - no concept of 'ease' ... which first?

additional processing (repair): where perform operation then immediately undo

Complete operation stack

0. UnStack(C,A)
1. PutDown (C)
2. PickUp (A)
3. Stack (A,B)
4. UnStack(A,B)
5. PutDown(A)
6. PickUp(B)
7. Stack (B,C)
8. PickUp(A)
9. Stack (A,B)

wasted p.s. efforts
produce steps

undo (eliminate)

complex tasks
many alternatives

reduction difficult

(interfering operations)

Solution:

do not plan sequentially to achieve compound goals (i.e., consider effects)

nonlinear planning

E.g., hierarchical (degree of difficulty) opportunistic

how do we do it?

how can we implement?

ABSTRIPS

1) Solve problem completely considering only preconditions of high 'critical value' (expected difficulty)

2) work on next highest

* hierarchy of abstraction spaces (doing part ahead?)

(e.g. ArmEmpty easy because we have PutDown(x))

cognitive affirmation .. plan more difficult first

NOAH (also Sacerdoti) Fikes/Nilsson 71,74,75

Nets of Action Hierarchies

• consider "partial plan"
• find required operators
• find required order for these (critics)
• find order of operators to satisfy all required constraints (interactions)

description of description of S J

action action

Goal Phantom Split Join

a goal to goals which

be achieved should be true

by time encountered

(remain to be satisfied)

Level 1 Paint the ceiling & Paint the ladder

Level 2 Paint the ceiling

S J

Paint the ladder

Get Paint Get ladder Apply paint to ceiling

Level 3 S J

(before criticism)

Get Paint Apply paint to ladder

Level 4 Get Paint Get ladder Apply paint to (after criticism to S ceiling

resolve conflicts)

Get Paint J Apply paint to ladder

Critics

each critic is a little program that makes specific observations about the proposed plan

* Resolve Conflicts (1. construct a table listing all mentioned more than once)

* Eliminate Redundant Preconditions

In the following,

Stack(x,y) - y can be table

- includes PickUp(x)

further research

* backtracking

* constraint-posting

* opportunistic planning

* meta-planning (reasoning about plans)

explanation

* adaptive planning (BART)

Notice a communication between "experts" is needed

The Blackboard Approach

HEARSAY-II