Planning
Chapters 11 and 12
Thanks: Professor Dan Weld, University of Washington
1
Planning

Input




Description of initial state of world (in some
KR)
Description of goal (in some KR)
Description of available actions (in some KR)
Output


Sequence of actions
Or, a partial order of actions
2
Input Representation

Description of initial state of world



Description of goal (i.e. set of desired worlds)




Set of propositions:
((block a) (block b) (block c) (on-table a) (on-table b) (clear a)
(clear b) (clear c) (arm-empty))
Logical conjunction
Any world that satisfies the conjunction is a goal
(:and (on a b) (on b c)))
Description of available actions
3
How Represent Actions?

Simplifying assumptions





Atomic time
Agent is omniscient (no sensing necessary).
Agent is sole cause of change
Actions have deterministic effects
STRIPS representation


World = set of true propositions
Actions:


Precondition: (conjunction of literals)
Effects (conjunction of literals)
north11
a
W0
a
W1
north12
a
W2
4
STRIPS Actions



Action = a function from world-state to world-state
Precondition says when function defined
Effects say how to change set of propositions
north11
a
W0
north11
precond: (and (agent-at 1 1)
(agent-facing north))
a
W1
effect: (and (agent-at 1 2)
(not (agent-at 1 1)))
5
Action Schemata



Instead of defining: pickup-A and pickup-B and …
Variables: ?x. For example, ?ob1
Define a schema:
(:operator pick-up
:parameters ((block ?ob1))
:precondition (and (clear ?ob1) (on-table ?ob1) (arm-empty))
:effect (and (not (on-table ?ob1))
(not (clear ?ob1))
(not (arm-empty))
(holding ?ob1)))
6
STRIPS vs ADL








Positive/Negative conditions
Closed world assumption
Negated Effects
Quantified Effects
Goals as conjunctions and disjunctions
Conditional Effects (when …)
Equality
Predicate Typing
7
Examples



Air Cargo Domain
Spare Tire Problem
The blocks world
8
Planning as Search

Nodes

Arcs
World states
Actions

Initial State
The state satisfying the complete description of the initial conds

Goal State
Any state satisfying the goal propositions
9
Forward-Chaining World-Space Search
Initial
State
C
A B
Goal
State
A
B
C
10
Backward-Chaining World-Space Search


Problem: Many possible goal
states are equally acceptable.
From which one does one search?
A
B
C D E
A D
B
C
E
Initial State is
completely defined
C
D
A B E
***
A
B
C
D
E
11
Backward Planning



Try out
http://www.cs.ubc.ca/labs/lci/CIspace/Version
4/planning/ at UBC which shows goaldirected planning
Shows blocks world planning
Idea: find a first subgoal



Achieve it by selecting an action
Regress to discover new subgoals from the
action’s preconditions
Continue
12
Planning as Search 2

Nodes
Partially specified plans

Arcs
Adding + deleting actions or constraints (e.g. <) to plan

Initial State
The empty plan

Goal State
A plan which when simulated achieves the goal
13
Plan-Space Search and Partial Order
Planning
pick-from-table(C)
put-on(C,B)
pick-from-table(C)
pick-from-table(B)


How represent plans?
How test if plan is a solution?
14
Terminologies








Partial Ordering
Linearization
Ordering constraints
Causal Links
Achieves
Conflicts
Open Preconditions
Consistent Plans
15
Planning as Search 3

Phase 1 - Graph Expansion



Necessary (insufficient) conditions for plan existence
Local consistency of plan-as-CSP
Phase 2 - Solution Extraction

Variables


action execution at a time point
Constraints


goals, subgoals achieved
no side-effects between actions
16
Planning Graph
Proposition
Init State
Action
Time 1
Proposition
Time 1
Action
Time 2
17
Constructing the planning graph…

Initial proposition layer


Action layer i



Just the initial conditions
If all of an action’s preconds are in i-1
Then add action to layer I
Proposition layer i+1

For each action at layer i


Add all its effects at layer i+1
Also allow propositions at layer i to persist to i+1
18
Mutual Exclusion (or Mutex)

Actions A,B exclusive (at a level) if




A deletes B’s precond, or
B deletes A’s precond, or
A & B have inconsistent preconds (so they cannot be
executed at the same time)
Propositions P,Q inconsistent (at a level) if

all ways to achieve P exclude all ways to achieve Q
19
Graphplan


Create level 0 in planning graph
Loop


If goal  contents of highest level (nonmutex)
Then search graph for solution


If find a solution then return and terminate
Else Extend graph one more level
20
Searching for a Solution

For each goal G at time t

For each action A making G true @t



If A isn’t mutex with a previously chosen action, select it
If no actions work, backup to last G (breadth first search)
Recurse on preconditions of actions selected, t-1
Proposition
Init State
Action
Time 1
Proposition
Time 1
Action
Time 2
21
Dinner Date
Initial Conditions: (:and (cleanHands) (quiet))
Goal:
(:and (noGarbage) (dinner) (present))
Actions:
(:operator carry :precondition
:effect (:and (noGarbage) (:not (cleanHands)))
(:operator dolly :precondition
:effect (:and (noGarbage) (:not (quiet)))
(:operator cook :precondition (cleanHands)
:effect (dinner))
(:operator wrap :precondition (quiet)
:effect (present))
22
Planning Graph
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop23
Are there any exclusions?
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop24
Do we have a solution?
noGarb
carry
cleanH
cleanH
dolly
quiet
quiet
cook
dinner
wrap
present
0 Prop
1 Action
2 Prop
3 Action
4 Prop25
Extend the Planning Graph
noGarb
carry
cleanH
noGarb
carry
cleanH
dolly
quiet
cleanH
dolly
quiet
cook
quiet
cook
dinner
wrap
dinner
wrap
present
0 Prop
1 Action
2 Prop
present
3 Action
4 Prop26
One (of 4) possibilities
noGarb
carry
cleanH
noGarb
carry
cleanH
dolly
quiet
cleanH
dolly
quiet
cook
quiet
cook
dinner
wrap
dinner
wrap
present
0 Prop
1 Action
2 Prop
present
3 Action
4 Prop27
Planning Languages


PDDL Tutorials
FF Planner
28
Robot Architectures (page787)
Function Based Architecture:
Task Planning and Learning
Map based Navigation
Vision Inferencing
Sensors and Actuators
Problem: low level action takes too long to reason about!
29
Behavior-based Robotics (page 788)

Rodney Brooks designed
behavior-based robotics


Agent design should not be
function based (I.e., should
not be based on learning,
task planning, sensing, etc).
Instead, it should be sensors
indepdent modules


Each has own sensing,
inferencing, and acting
Higher level modules more
intelligent, and can access
sensors independently, and
can modify outputs of
lower-level modules
Plan ahead
learn
vision
explore
actuators
wonder
Avoid objects
30
Robot Insect Video

Rodney Brooks’ robots in a video

http://www.youtube.com/watch?v=C9p8B7-5MTI
31
Summary Planning



Reactive systems vs. planning
Planners can handle medium to large-sized
problems
Relaxing assumptions





Atomic time
Agent is omniscient (no sensing necessary).
Agent is sole cause of change
Actions have deterministic effects
Generating contingent plans

Large time-scale Spacecraft control
32
Descargar

Outline for 4/2 - Hong Kong University of Science and