Fundamentals of Artiﬁcial Intelligence Chapter 10: Classical Planning Roberto Sebastiani

(1)

Fundamentals of Artificial Intelligence Chapter 10: Classical Planning

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it http://disi.unitn.it/rseba/DIDATTICA/fai_2020/

Teaching assistant: Mauro Dragoni–dragoni@fbk.eu http://www.maurodragoni.com/teaching/fai/

M.S. Course “Artificial Intelligence Systems”, academic year 2020-2021

Last update: Friday 4^thDecember, 2020, 17:37

Copyright notice: Most examples and images displayed in the slides of this course are taken from [Russell & Norwig, “Artificial Intelligence, a Modern Approach”, Pearson, 3^rded.], including explicitly figures from the above-mentioned book, and their copyright is detained by the authors.

A few other material (text, figures, examples) is authored by (in alphabetical order):

Pieter Abbeel,Bonnie J. Dorr,Anca Dragan,Dan Klein,Nikita Kitaev,Tom Lenaerts,Michela Milano,Dana Nau,Maria Simi, who detain its copyright. These slides cannot can be displayed in public without the permission of the author.

1 / 65

(2)

Outline

1 The Problem

2 Search Strategies and Heuristics Forward and Backward Search Heuristics

3 Planning Graphs, Heuristics and Graphplan Planning Graphs

Heuristics Driven by Planning Graphs The Graphplan Algorithm

4 Other Approaches (hints) Planning as SAT Solving Planning as FOL Inference

2 / 65

(3)

Outline

1 The Problem

3 / 65

(4)

Automated Planning (aka “Planning”)

Automated Planning

Synthesize asequence of actions (plan)to be performed by an agent leading from aninitial stateof the world to aset of target states (goal)

Planning is both:

an application per se

a common activity in many applications

(e.g.design & manufacturing,scheduling,robotics,...) Similar to problem-solving agents (Ch.03), but with factored/structured representation of states

“Classical” Planning(this chapter): fully observable, deterministic, static environments with single agents

4 / 65

(5)

Automated Planning (aka “Planning”)

Automated Planning

Planning is both:

4 / 65

(6)

Automated Planning (aka “Planning”)

Automated Planning

Planning is both:

4 / 65

(7)

Automated Planning (aka “Planning”)

Automated Planning

Planning is both:

4 / 65

(8)

Automated Planning [cont.]

Automated Planning Given:

an initial state

a set of actions you can perform a (set of) state(s) to achieve (goal) Find:

aplan: a partially- or totally-ordered set of actions needed to achieve the goal from the initial state

5 / 65

(9)

Automated Planning [cont.]

an initial state

5 / 65

(10)

Automated Planning [cont.]

an initial state

5 / 65

(11)

A Language for Planning: PDDL

Planning Domain Definition Language (PDDL)

Astateis a conjunction offluents:ground, function-less atoms ex:Poor ∧ Unknown,At(Truck₁,Melbourne) ∧ At(Truck₂,Sydney ) ex of non-fluents:At(x , y )(non ground),¬Poor (negated),

At(Father (Fred ), Sydney )(not function-less)

closed-world assumption: all non-mentioned fluents are false unique names assumption: distinct names refer to distinct objects Actionsare described by a set ofaction schemata

concise description:describe which fluent change

=⇒ the other fluents implicitly maintain their values

Action Schema: consists inaction name, alist of variablesin the schema, theprecondition, theeffect(akapostcondition)

precondition and effect areconjunctions of literals (positive or negated atomic sentences)

lifted representation: variables implicitlyuniversally quantified Can be instantiated into (ground) actions

6 / 65

(12)

A Language for Planning: PDDL

6 / 65

(13)

A Language for Planning: PDDL

6 / 65

(14)

A Language for Planning: PDDL

6 / 65

(15)

A Language for Planning: PDDL

6 / 65

(16)

A Language for Planning: PDDL

6 / 65

(17)

A Language for Planning: PDDL

6 / 65

(18)

PDDL: Example

Action schema:

Action(Fly (p, from, to),

PRECOND : At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to) EFFECT : ¬At(p, from) ∧ At(p, to))

Action instantiation:

Action(Fly (P₁,SFO, JFK ),

PRECOND : At(P₁,SFO) ∧ Plane(P₁) ∧Airport(SFO) ∧ Airport(JFK ) EFFECT : ¬At(P₁,SFO) ∧ At(P₁,JFK ))

7 / 65

(19)

PDDL: Example

Action schema:

7 / 65

(20)

PDDL: Example

Action schema:

7 / 65

(21)

A Language for Planning: PDDL [cont.]

Precondition: must hold to ensure the action can be executed defines the states in which the action can be executed

action isapplicablein state s if the preconditions are satisfied by s Effect: represent the effects of the action on the world

defines the result of executing the action

Add list (ADD(a)): the positive literals in the action’s effects ex:{At(p, to)}

Delete list (DEL(a)): (the fluents in) the negative literals in the action’s effects

ex:{At(p, from)}

Result of action a in state s: RESULT(s,a)^def=(s\DEL(a) ∪ ADD(a)) start from s

remove the fluents that appear as negative literals in effect add the fluents that appear as positive literals in effect

ex:Fly (P₁,SFO, JFK )=⇒removeAt(P₁,SFO), addAt(P₁,JFK )

8 / 65

(22)

A Language for Planning: PDDL [cont.]

ex:{At(p, from)}

8 / 65

(23)

A Language for Planning: PDDL [cont.]

ex:{At(p, from)}

8 / 65

(24)

A Language for Planning: PDDL [cont.]

ex:{At(p, from)}

8 / 65

(25)

A Language for Planning: PDDL [cont.]

ex:{At(p, from)}

8 / 65

(26)

PDDL: Example [cont.]

Action schema:

Action(Fly (P1,SFO, JFK ),

PRECOND : At(P1,SFO) ∧ Plane(P1) ∧Airport(SFO) ∧ Airport(JFK ) EFFECT : ¬At(P1,SFO) ∧ At(P1,JFK ))

s : At(P₁,SFO) ∧ Plane(P₁) ∧Airport(SFO) ∧ Airport(JFK ) ∧ ...

=⇒ s⁰:At(P₁,JFK )∧ Plane(P1) ∧Airport(SFO) ∧ Airport(JFK ) ∧ ...

Sometimes we want topropositionalizea PDDL problem: replace each action schema with a set of ground actions.

Ex:...At_P₁_SFO ∧ Plane_P₁∧ Airport_SFO ∧ Airport_JFK )...

9 / 65

(27)

PDDL: Example [cont.]

Action schema:

9 / 65

(28)

PDDL: Example [cont.]

Action schema:

9 / 65

(29)

PDDL: Example [cont.]

Action schema:

9 / 65

(30)

A Language for Planning: PDDL [cont.]

Time in PDDL

Fluents do not explicitly refer to time

Times and states areimplicitin the action schemata:

the precondition always refers to time t the effect to time t+1.

PDDL Problem

A set of action schemata defines aplanning domain

PDDL problem: aplanning domain, aninitial stateand agoal theinitial stateis aconjunction of ground atoms(positive literals)

closed-world assumption: any not-mentioned atoms are false thegoalisa conjunction of literals (positive or negative)

may contain variables, which are implicitlyexistentially quantified a goal g may represent aset of states(the set of states entailing g)

Ex:goal: At(p, SFO) ∧ Plane(p):

“p” implicitly means “for some plane p”

the statePlane(Plane1) ∧At(Plane1,SFO) ∧ ...entails g

10 / 65

(31)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(32)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(33)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(34)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(35)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(36)

A Language for Planning: PDDL [cont.]

Time in PDDL

PDDL Problem

10 / 65

(37)

A Language for Planning: PDDL [cont.]

Planning as a search problem All components of a search problem

aninitial state anACTIONSfunction aRESULTfunction and agoal test

11 / 65

(38)

Example: Air Cargo Transport

( c S. Russell & P. Norwig, AIMA)

One solution:

[Load (C1,P1,SFO), Fly (P1,SFO, JFK ), Unload (C1,P1,JFK ), Load (C2, P2, JFK ), Fly (P2, JFK , SFO), Unload (C2, P2, SFO)]

12 / 65

(39)

Example: Spare Tire Problem

One solution:

[Remove(Flat, Axle), Remove(Spare, Trunk ), PutOn(Spare, Axle)]

13 / 65

(40)

Example: Blocks World

14 / 65

(41)

Example: Blocks World [cont.]

One solution: [MoveToTable(C, A), Move(B, Table, C), Move(A, Table, B)]

15 / 65

(42)

Decidability and Complexity

PlanSAT: the question of whether there exists any plan that solves a planning problem

decidable for classical planning

with function symbols, the number of states becomes infinite

=⇒undecidable in PSPACE

Bounded PlanSAT: the question of whether there exists any plan that of a given length k or less

can be used for optimal-length plan decidable for classical planning

decidable even in the presence of function symbols in PSPACE, NP for many problems of interest

16 / 65

(43)

Decidability and Complexity

16 / 65

(44)

Decidability and Complexity

16 / 65

(45)

Outline

1 The Problem

17 / 65

(46)

Outline

1 The Problem

18 / 65

(47)

Two Main Approaches

(a) Forward search(akaprogression search) start in the initial state

use actions to search forward for a goal state (b) Backward search(akaregression search)

start from goal states

use reverse actions to search forward for the initial state

( c S. Russell & P. Norwig, AIMA) 19 / 65

(48)

Two Main Approaches

(a) Forward search(akaprogression search) start in the initial state

use actions to search forward for a goal state (b) Backward search(akaregression search)

start from goal states

use reverse actions to search forward for the initial state

( c S. Russell & P. Norwig, AIMA) 19 / 65

(49)

Forward Search

Forward search(akaprogression search)

choose actions whose preconditions are satisfied add positive effects, delete negative

Goal test: does the state satisfy the goal?

Step cost: each action costs 1

=⇒ We can use any of the search algorithms from Ch. 03, 04 need keeping track of the actions used to reach the goal Breadth-firstandbest-first

Sound: if they return a plan, then the plan is a solution

Complete: if a problem has a solution, then they will return one Require exponential memorywrt. solution length! =⇒unpractical Depth-first searchandgreedy search

Sound Not complete

may enter in infinite loops

(classical planning only): made complete by loop-checking Require linear memorywrt. solution length

20 / 65

(50)

Forward Search

Sound Not complete

20 / 65

(51)

Forward Search

Sound Not complete

20 / 65

(52)

Forward Search

Sound Not complete

20 / 65

(53)

Forward Search

Sound Not complete

20 / 65

(54)

Forward Search

Sound Not complete

20 / 65

(55)

Branching Factor of Forward Search

Planning problems can have huge state spaces

Forward search can have a very large branching factor ex:pickup(a1),pickup(a2), ...,pickup(a500)

=⇒ Forward-search can waste time trying lots of irrelevant actions

=⇒ Need a good heuristic to guide the search

( c of Dana Nau, CMSC21, U. Maryland, Licensed under Creative Commons)

21 / 65

(56)

Branching Factor of Forward Search

21 / 65

(57)

Branching Factor of Forward Search

21 / 65

(58)

Branching Factor of Forward Search

21 / 65

(59)

Backward Search (aka Regression or Relevant-States)

Predecessor stateg’ of ground goal g via ground action a:

Pos(g⁰)^def= (Pos(g) \ Add (a)) ∪ Pos(Precond (a)) Neg(g⁰)^def= (Neg(g) \ Del(a)) ∪ Neg(Precond (a)) Note: Both g and g⁰ represent many states

irrelevant ground atoms unassigned

Consider the goalAt(C₁,SFO) ∧ At(C₂,JFK ) Consider the ground action:

Action(Unload (C₁,P₁,SFO), PRECOND :

In(C₁,P₁) ∧At(P₁,SFO) ∧ Cargo(C₁) ∧Plane(P₁) ∧Airport(SFO) EFFECT : At(C₁,SFO) ∧ ¬In(C₁,P₁))

This produces the sub-goal g⁰:

In(C₁,P₁) ∧At(P₁,SFO) ∧ Cargo(C₁) ∧Plane(P₁) ∧ Airport(SFO) ∧ At(C₂,JFK )

Both g⁰ and g represent many states e.g. truth value ofIn(C3,P2)irrelevant

22 / 65

(60)

Backward Search (aka Regression or Relevant-States)

22 / 65

(61)

Backward Search (aka Regression or Relevant-States)

22 / 65

(62)

Backward Search (aka Regression or Relevant-States)

22 / 65

(63)

Backward Search (aka Regression or Relevant-States)

22 / 65

(64)

Backward Search (aka Regression or Relevant-States)

22 / 65

(65)

Backward Search (aka Regression or Relevant-States)

22 / 65

(66)

Backward Search [cont.]

Idea: deal with partially un-instantiated actions and states avoid unnecessary instantiations

=⇒ no need to produce a goal for every possible instantiation use themost general unifier

standardizeaction schemata first (rename vars into fresh ones)

Consider the goalAt(C₁,SFO) ∧ At(C₂,JFK ) Consider the partially-instantiated action:

Action(Unload (C₁,p⁰,SFO), PRECOND :

In(C₁,p⁰) ∧At(p⁰,SFO) ∧ Cargo(C₁) ∧Plane(p⁰) ∧Airport(SFO) EFFECT : At(C1,SFO) ∧ ¬In(C1,p⁰))

In(C₁,p⁰) ∧At(p⁰,SFO) ∧ Cargo(C₁) ∧Plane(p⁰) ∧ Airport(SFO) ∧ At(C₂,JFK )

Represents states with all possible planes

=⇒ no need to produce a subgoal for every plane P1,P2,P3, ...

23 / 65

(67)

Backward Search [cont.]

Idea: deal with partially un-instantiated actions and states avoid unnecessary instantiations

=⇒ no need to produce a goal for every possible instantiation use themost general unifier

standardizeaction schemata first (rename vars into fresh ones)

Consider the goalAt(C₁,SFO) ∧ At(C₂,JFK ) Consider the partially-instantiated action:

Action(Unload (C₁,p⁰,SFO), PRECOND :

In(C₁,p⁰) ∧At(p⁰,SFO) ∧ Cargo(C₁) ∧Plane(p⁰) ∧Airport(SFO) EFFECT : At(C1,SFO) ∧ ¬In(C1,p⁰))

In(C₁,p⁰) ∧At(p⁰,SFO) ∧ Cargo(C₁) ∧Plane(p⁰) ∧ Airport(SFO) ∧ At(C₂,JFK )

Represents states with all possible planes

=⇒ no need to produce a subgoal for every plane P1,P2,P3, ...

23 / 65