Introduction to AI -Search-
Introduction to AI
-Planning-
Francesca Toni
Outline
• Classical planning
• Planning as search
• Planning algorithms: graph-plan
Recommended reading:
(most of) Chapter 10
Additional reading:
Chapter 6
2
(Classical) planning
• Intelligent agents have goals
•Plans are sequences of actions allowing to achieve
those goals, from a given initial state
•Planning amounts to selecting (optimal) plans
•Plans then need to be executed in the world
3
Which problems can be solved by classical planning?
Environment is
• Observable
• Current state known
• Discrete
• From each state finitely many next states by executing actions
• Deterministic
• Each action has exactly one outcome (next state)
• Known
• Possible actions and next states for each state
4
Classical planning = Search?
5
Representations for planning: vacuum world example
Start: Goal: no dirt Search Graph:
Start: In(A)∧ 𝐷𝑖𝑟𝑡(𝐴) ∧ 𝐷𝑖𝑟𝑡(𝐵)
Goal:¬Dirt(𝐴) ∧ ¬𝐷𝑖𝑟𝑡(𝐵)
Action descriptions:
action(𝑆(𝑥)), precondition(𝑆(𝑥),𝐼𝑛(𝑥)), postcondition(𝑆(𝑥),¬Dirt(x)) 𝑺(𝒙)
𝐼𝑛(𝑥)
¬Dirt(x)
6
STRIPS (STanford Research Institute Problem Solver)
Special purpose, restricted language for planning
• States are conjunctions of (function-free) ground atoms (positive fluents)
• Goals are conjunctions of (function-free) literals* (positive or negative fluents – possibly
containing variables, implicitly existentially quantified)
• Operators (schemata – may contain variables, implicitly universally quantified):
• Action description = name of action
• Precondition = conjunction of literals*
• Postcondition (Effect) = conjunction of literals
• Every variable in effect must appear in precondition
• Actions are fully instantiated operators: different instances of the same operator are
different actions
action
Precondition
Postcondition/Effect
*atoms in the
original STRIPS
STRIPS – syntactic assumptions
• 𝐼𝑛(𝑥) cannot be part of a state (as non-ground)
• ¬Dirt(𝐴) cannot be part of a state (as not an atom)
• 𝐼𝑛(𝐴𝑑𝑗𝑎𝑐𝑒𝑛𝑡(𝑥)) cannot be part of a state (as 𝐴𝑑𝑗𝑎𝑐𝑒𝑛𝑡 is a function)
• ∀𝑥 ¬Dirt(𝑥) cannot be a goal (as universally quantified)
• ¬ Dirt(𝑥) can be a goal (implicitly amounting to ∃𝑥 ¬Dirt(𝑥)
• cannot be an action schema (as 𝑦 does not occur in 𝑃(𝑥))
7
𝑨(𝒙)
𝑃(𝑥)
Q (x,y)
STRIPS – “semantic” assumptions
• Fluents not “mentioned” in a state representation are (implicitly) false
• Fluents persist (do not change) unless they are explicitly changed by an action
• Time is implicit
8
𝑺(𝒙)
𝐼𝑛(𝑥)
¬Dirt(x))
In(A)∧ 𝐷𝑖𝑟𝑡(𝐴) ∧ 𝐷𝑖𝑟𝑡(𝐵) 𝑆(𝐴) In(A)∧ 𝐷𝑖𝑟𝑡(𝐵)
In(A)∧ 𝐷𝑖𝑟𝑡 𝐴 ∧ 𝐷𝑖𝑟𝑡 𝐵 : implicitly¬In(B)
𝑺(𝒙)
𝐼𝑛(𝑥)
¬Dirt(x))
Time t
Time t+1
Execution of an action
• The action needs to be applicable in the current state:
the state entails the preconditions of the action
• The result is a new state, modifying the current state “using the fluents in
the effects”:
new state= current state – negation of negative fluents in effects
+ positive fluents in effects
9
𝑺(𝒙)
𝐼𝑛(𝑥)
¬Dirt(x)
In(A)∧ 𝐷𝑖𝑟𝑡(𝐴) ∧ 𝐷𝑖𝑟𝑡(𝐵)𝑆(𝐴) is applicable in current state
In(A)∧ 𝐷𝑖𝑟𝑡(𝐵)executing 𝑆(𝐴) in current state removes 𝐷𝑖𝑟𝑡 𝐴 giving
Solving a planning problem
10
Find a sequence of actions from the initial state to a state in which the
goal holds (i.e. entailing the goal)
Start: In(A)∧ 𝐷𝑖𝑟𝑡(𝐴) ∧ 𝐷𝑖𝑟𝑡(𝐵)
Goal:¬Dirt(𝐴) ∧ ¬𝐷𝑖𝑟𝑡(𝐵)
A plan: S(.), R(.), S(.) Another plan: R(.),S(.),L(.),S(.)
The blocks’ world
𝑀𝑜𝑣𝑒(𝑏, 𝑥, 𝑦)
𝑂𝑛 𝑏, 𝑥 , 𝐶𝑙𝑒𝑎𝑟 𝑏 , 𝐶𝑙𝑒𝑎𝑟 𝑦 , 𝑏 ≠ 𝑥 ≠ 𝑦, 𝑏 ≠ 𝑇𝑎𝑏𝑙𝑒, 𝑦 ≠ 𝑇𝑎𝑏𝑙𝑒
𝑂𝑛 𝑏, 𝑦 , 𝐶𝑙𝑒𝑎𝑟 𝑥 , ¬𝑂𝑛 𝑏, 𝑥 , ¬𝐶𝑙𝑒𝑎𝑟 𝑦
𝑀𝑜𝑣𝑒2𝑇𝑎𝑏𝑙𝑒 𝑏, 𝑥
𝑂𝑛 𝑏, 𝑥 , 𝐶𝑙𝑒𝑎𝑟 𝑏 , 𝑏 ≠ 𝑥 ≠ 𝑇𝑎𝑏𝑙𝑒
𝑂𝑛 𝑏, 𝑇𝑎𝑏𝑙𝑒 , 𝐶𝑙𝑒𝑎𝑟 𝑥 , ¬𝑂𝑛 𝑏, 𝑥
A plan: 𝑀𝑜𝑣𝑒2𝑇𝑎𝑏𝑙𝑒 𝐶, 𝐴 , 𝑀𝑜𝑣𝑒 𝐵, 𝑇𝑎𝑏𝑙𝑒, 𝐶 , 𝑀𝑜𝑣𝑒 𝐴, 𝑇𝑎𝑏𝑙𝑒, 𝐵
12
• Progression planning (forward)
• (blind or heuristic) search with the graph obtained from
the specification of the planning problem
• Regression planning (backward)
• (blind or heuristic) search backwards from the goal (using
predecessors of actions)
Planning as search
START STATE
GOAL STATE
𝐹𝑙𝑦 𝑝, 𝑥, 𝑦
𝐴𝑡 𝑝, 𝑥 , 𝑃𝑙𝑎𝑛𝑒(𝑝), 𝐴𝑖𝑟𝑝𝑜𝑟𝑡(𝑥)
𝐴𝑡 𝑝, 𝑦 , ¬𝐴𝑡 𝑝, 𝑥
13
Planning problems tend to have
• large search spaces, with
•many (irrelevant) actions
Good heuristics from “relaxed” problems, e.g.
1. add edges (e.g. by ignoring preconditions and
effects not in goal)
Progression planning needs good heuristics
Non-interleaved regression planning is incomplete
(Sussman anomaly)
14
Non-interleaved (regression) planner: 2 subgoals 𝑂𝑛 𝐵, 𝐶 , 𝑂𝑛(𝐴, 𝐵)
•Either start with: 𝑀𝑜𝑣𝑒(𝐵, 𝑇𝑎𝑏𝑙𝑒, 𝐶)
•Or start with: 𝑀𝑜𝑣𝑒2𝑇𝑎𝑏𝑙𝑒(𝐶, 𝐴), 𝑀𝑜𝑣𝑒(𝐴, 𝑇𝑎𝑏𝑙𝑒, 𝐵)
15
graph-plan algorithm
Planning graph
16
𝐸𝑎𝑡(𝑐𝑎𝑘𝑒)
𝐻𝑎𝑣𝑒(𝐶𝑎𝑘𝑒)
¬𝐻𝑎𝑣𝑒 𝐶𝑎𝑘𝑒 , Eaten(Cake)
𝐵𝑎𝑘𝑒(𝑐𝑎𝑘𝑒)
¬𝐻𝑎𝑣𝑒(𝐶𝑎𝑘𝑒)
𝐻𝑎𝑣𝑒 𝐶𝑎𝑘𝑒
START STATE
GOAL STATE
Planning graph – level Si
17
START STATE
GOAL STATE
• i=0: Start state + literals that “could” hold at the start
• i>0: all literals that “could” hold at Si , depending on actions at Ai-1
Planning graph – level Ai
18
START STATE
GOAL STATE
• Each action at Ai connected to its precondition at Si and effect at Si+1
• No-op actions (□): a literal persists if no action negates it
Planning graph – mutex (mutual exclusions) between actions
19
START STATE
GOAL STATE
• Inconsistent effects
(e.g. 𝐸𝑎𝑡(𝐶𝑎𝑘𝑒) and □)
• Interference: effect of one action= ¬ precondition of the other
(e.g. 𝐸𝑎𝑡(𝐶𝑎𝑘𝑒) and □)
• Competing needs: mutex preconditions
(e.g. 𝐸𝑎𝑡(𝐶𝑎𝑘𝑒) and 𝐵𝑎𝑘𝑒(𝐶𝑎𝑘𝑒) )
Planning graph – mutex (mutual exclusions) between literals
20
START STATE
GOAL STATE
• Complementary literals
(e.g. 𝐻𝑎𝑣𝑒(𝐶𝑎𝑘𝑒) and ¬ 𝐻𝑎𝑣𝑒(𝐶𝑎𝑘𝑒))
• Inconsistent support: each possible pair of actions achieving them are mutex
(e.g. 𝐻𝑎𝑣𝑒(𝐶𝑎𝑘𝑒) and 𝐸𝑎𝑡𝑒𝑛(𝐶𝑎𝑘𝑒) at S1 )
Planning graph: levelling off
21
START STATE
GOAL STATE
S1 =S2
Graph-plan algorithm – idea
• Construct S0 , let 𝑖 = 0
• If goal non-mutex in Si then extract plan (backwards, if any) from Si
• Else expand planning graph (construct Ai and Si+1) and increment 𝑖
22
23
Extract plan
• To extract a plan P for a non-empty set G of goals at t:
1. select a set A of actions at t-1 for the goals in G, given {}
2. extract a plan P’ for the preconditions of actions in A at t-1, and return P=A∪P’
• To extract a plan P for an empty set G of goals at t:
1. Return P={}
• To select a set A of actions at t-1 for the goals in a non-empty set G, given
A’
1. pick g in G and some action a at t-1 having g as add-effect and such that a is not
mutex of any action in A’
2. select a set A” of actions at t-1 for the goals in G-{g}, given A’∪{a}, and return
A=A”∪{a}
• To select a set A of actions at t-1 for the goals in an empty set G, given A’
1. Return A={}
Omitted
•Planning and acting in the real-world (under uncertainty)
•Hierarchical planning
•Multi-agent planning
24
Planning – today (example – non-examinable)
25
Planning – today (example – non-examinable)
26
Planning today (non-examinable)
27
International Conference on Automated Planning and Scheduling
Planning – summary
• Formulation of planning problems
• Understanding planning as search
• Tailored planning algorithms are useful
• Graph-plan as a seminal planning algorithm
28