Transcript 74.419 Artificial Intelligence 2002 Description Logics

74.419 Artificial
Intelligence 2005/06
Partial Order Planning
Socks & Shoes
Total Order Plans:
Partial Order Plan:
Start
Start
Left
Sock
Right
Sock
Left Sock
on
Right
Sock on
Left
Shoe
Left
Shoe on
Right
Shoe
Finish
Right
Shoe on
Start
Start
Start
Start
Right
Sock
Right
Sock
Left
Sock
Left
Sock
Left
Sock
Left
Sock
Right
Sock
Right
Sock
Right
Shoe
Left
Shoe
Right
Shoe
Left
Shoe
Left
Sock
Right
Sock
Right
Shoe
Left
Shoe
Right
Shoe
Finish
Finish
Finish
Right
Shoe
Left
Sock
Left
Shoe
Right
Shoe
Finish
Finish
Left
Shoe
Finish
Right
Sock
Start
Left
Sock
Partially Ordered Plans
Partially Ordered Plans - or:
"How Do You Put Your Shoes On?"
Partially Ordered Plans:
• no strict sequence
• partly parallel
• observe threats
Resource Constraints in Planning



Resources
 physical quantities, e.g. money, fluids etc.
 time
Integrate Measures into Action Description and
Planning
 representation of physical quantities and
reasoning / calculation, e.g. for buy-action: effect:
cash := cash – price (x)
 time system / time logic, e.g. go-to-action: effect:
time := time + 30 (Minutes)
Backtracking on Constraint Violation
Least Commitment Strategy
Partially Instantiated Plans
Least Commitment Strategy
In general, make as little concrete as possible,
i.e. leave things undetermined until you have to
determine them and become concrete.
Partially Instantiated Plans
During planning, variables have not necessarily
to be instantiated immediately.
Instantiation can wait, until binding becomes
necessary
Partial Order Planning 1
Start with a rough plan and refine iteratively.
First plan consists only of start and finish actions:
 start - T as precondition, initial world state as effect
 finish - goal as precondition, NIL as effect
Select actions to achieve sub-goals separately, quasi
in parallel  partial-order plan
Fulfill open preconditions (sub-goals), until no more
unsatisfied preconditions are left (last one is T of
start)
Partial Order Planning - Causal Links
 Add causal links to connect effects from actions
to matching preconditions for plan, e.g.
 move(A,B,x) has effect clear(B)
 clear(B) is precondition for move(B,y,z)
 Causal links specify a partial order.
effect of move (A,y,B) is
on(A,B) is precondition
for finish (goal state)
causal link
Partial Order Planning - Threats
 Recognize threats - the effect of an action A
destroys the precondition of another action B, e.g.
 move(A,x,B) destroys clear(B) (in DELETE-list)
 clear(B) is precondition for move(B,y,z)
 thus, move(B,Fl,C) has to be done before move
(A,Fl,B)
 Add threats as partial order to plan: b<a (do b before
a).
effect of a = move(A,Fl,B)
includes DEL Clear(B)
a
precond of c = move(B,Fl,C)
includes Clear(B)
threat!
c<a
threat
b<c
b
c
Partial Order Planning - Threats
partial order plan = set of action strings (partial plans)
Problem:
Detect and resolve threats, i.e. conflicts between actions
– where the precondition of one action is deleted by
another action – by choosing an adequate ordering of
actions: if action b is a threat to action a, then a<b, i.e. a
has to occur before b.
(see also Russell/Norvig textbook, The POP Planner)
Partial Order Planning - Overall
Use plan transformation operators to refine the partial plan
and construct a complete plan:
 add an action (operator),
 reorder actions (operators),
 instantiate actions (operators).
A partial order plan consists of a set of action sequences
(partial plans; action strings) which together achieve the
complete set of goal literals.
Threats induce an additional partial order of these action
sequences.
Additional References
Nils J. Nilsson: Artificial Intelligence – A New Synthesis.
Morgan Kaufmann, San Francisco, 1998.
Konolidge, K. and K. Myers: The Saphira Architecture for
Autonomous Mobile Robots (Robot Soccer Class Project)
Guzzoni, D. et al.: Many Robots Make Short Work. (AAAI’96
Robot Competition - Meeting Scheduling)
Martina Veloso, MIT (RoboCup)