CS计算机代考程序代写 AI algorithm 3b_Planning.dvi

3b_Planning.dvi

COMP9414 Planning 1

This Lecture

� Reasoning About Action

� STRIPS Planner

� GraphPlan

� Planning as Constraint Satisfaction

UNSW ©W. Wobcke et al. 2019–2021

COMP9414: Artificial Intelligence

Lecture 3b: Planning

Wayne Wobcke

e-mail:w. .au

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 3

Reasoning About Action

� Semantics: Divide the world into a sequence of (notional) time points

◮ Situation is a (complete) state of world at a time point

◮ Action is a transition between situations

◮ Nothing (of relevance) happens between situations

� Planner: Maintain an incomplete description of situations

◮ Confusingly, also called a state of the world

◮ Search for path from initial state to a goal state

◮ State transitions correspond to actions

◮ Major problem is to specify actions

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 2

Planning Agent

� Environment changes due to the performance of actions

� Planning scenario

◮ Agent can control its environment

◮ Only atomic actions, not processes with duration

◮ Only single agent in the environment (no interference)

◮ Only changes due to agent executing actions (no evolution)

� More complex examples

◮ Robocup dog

◮ Delivery robot

◮ Self-driving car

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 5

Specifying Actions (STRIPS)

� Action Description – name of action

� Preconditions – action can be performed in a situation only if

precondition holds in situation prior to action being performed

� Delete List – literals to be deleted from the state (description) after

action is performed

� Add List – literals to be added to the state (description) after action is

performed

� STRIPS Assumption – any literals in the state (description) not

contained in the delete list remain the same after the action is

performed (c.f. frame problem)

Assumes actions are executed perfectly (reasonable for planning?)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 4

The Blocks World

� Blocks can be placed on the table and can be stacked on one another

� All blocks the same size and table large enough to hold all blocks

Table

State: on(C, A), on(A, Table), on(B, Table), clear(B), clear(C)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 7

Problems in Reasoning About Action

� Frame Problem

◮ How to characterize what in the state does not change by

performing an action

• Problem is there are a lot of such facts

• Both “epistemological” and “computational” problem

� Ramification Problem

◮ What are the direct and indirect effects of performing an action?

• Problem is that indirect effects depend on initial situation

� Qualification Problem

◮ What preconditions are required in a specification of an action?

• Problem is that qualifications depend on context

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 6

Blocks World Actions (STRIPS)

� Action Description: move(x, y, z) (x 6= y 6= z?)

� Preconditions: on(x, y), clear(x), clear(z)

� Delete List: clear(z), on(x, y)

� Add List: on(x, z), clear(y), clear(Table)

◮ Add clear(Table) to ensure table is always clear

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 9

Simple Planning Algorithms

� Forward search and goal regression

(a)

(b)

At(P1, A)
Fly(P1, A, B)

Fly(P2, A, B)

Fly(P1, A, B)

Fly(P2, A, B)

At(P2, A)

At(P1, B)

At(P2, A)

At(P1, A)

At(P2, B)

At(P1, B)

At(P2, B)

At(P1, B)

At(P2, A)

At(P1, A)

At(P2, B)

� Problem with forward search is state space can be very large

� Problem with regression is that it is hard and doesn’t always work

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 8

Planning

� Plan – sequence (or ordered set) of actions to achieve some goal

� Planner – problem solver that produces plans

� Goal – typically a conjunction of literals

� Initial State – typically a conjunction of literals

� Blocks World Example for goal on(B, C)∧on(C, Table)

◮ move(C, A, Table),move(B, Table, C)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 11

Forward Search with Plan Graphs

• Only consider “propositional” plans

• Si contains all literals that could hold at time i

• Ai contains all actions that could have preconditions satisfied at time i

• Actions linked to preconditions

• Literals that persist from time i to time i+1 linked via actions

• Mutual exclusion (mutex) links between actions/literals at same time

Bake(Cake)

Eat(Cake)

Have(Cake)

S0 A0 S1 A1 S2

Have(Cake) Have(Cake) Have(Cake)

Have(Cake)

Eaten(Cake)

Eaten(Cake) Eaten(Cake)Eaten(Cake)

Eaten(Cake)

Eat(Cake)

¬ ¬

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 10

Nonlinear Planning

� Start with goal regression and try to fix “flaws” in the plan

FinishAt(Spare,Axle)Start
At(Flat,Axle)

At(Spare,Trunk)

Remove(Spare,Trunk)At(Spare,Trunk)

PutOn(Spare,Axle)
At(Spare,Ground)

At(Flat,Axle)
FinishAt(Spare,Axle)Start

At(Flat,Axle)

At(Spare,Trunk)

Start

Remove(Spare,Trunk)At(Spare,Trunk)

Remove(Flat,Axle)At(Flat,Axle)

PutOn(Spare,Axle)
At(Spare,Ground)

At(Flat,Axle)
FinishAt(Spare,Axle)

At(Flat,Axle)

At(Spare,Trunk)

� Least commitment: execution can be in any permissible order

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 13

GraphPlan Expansion Step

� Add actions to Ai whose preconditions are at Si

� Add “persistence actions” to Ai for literals from Si

� Add mutex links to Ai for actions that cannot occur together

� Add effects of all actions in Ai to Si+1

� Add literals to Si+1 for persistence actions from Ai

� Add mutex links to Si+1 for literals that cannot occur together

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Planning 12

Mutual Exclusion

� Actions

◮ Inconsistent effects: One action negates an effect of the other

◮ Interference: Effect of one action is the negation of a precondition

of the other

◮ Competing needs: Precondition of one action is mutually

exclusive with a precondition of the other

� Literals

◮ One literal is the negation of the other

◮ Inconsistent support: Each possible pair of actions that could

achieve the two literals is mutually exclusive

COMP9414 Planning 15

GraphPlan Example

� After expansion to Level 2

S0 A1 S2

At(Spare,Trunk)

At(Flat,Axle)

At(Spare,Axle)

At(Flat,Ground)

At(Spare,Ground)

At(Spare,Trunk)

At(Flat,Axle)

At(Spare,Axle)

At(Flat,Ground)

At(Spare,Ground)

At(Spare,Axle)

At(Spare,Trunk)

At(Flat,Axle)

At(Spare,Axle)

At(Flat,Ground)

At(Spare,Ground)

PutOn(Spare,Axle)

LeaveOvernight

Remove(Flat,Axle)

Remove(Spare,Trunk)

Remove(Flat,Axle)

LeaveOvernight

A0 S1

COMP9414 Planning 14

GraphPlan Algorithm

� Graph = Initial plan graph with initial state S0

� nogoods = empty set

� For t = 0, · · ·

◮ If all goals are non-mutex in St

• Extract solution from graph

◦ Graph as CSP with variables T/F for when action in the plan

◦ Or heuristically guided regression from St to S0

• If valid solution, return solution

◮ If graph and nogoods didn’t change then return failure

◮ Expand graph to next level

COMP9414 Planning 17

Conclusion

� Reasoning about action interesting from philosophical point of view

� Recent advances in planning give great improvements in efficiency

� Planning makes use of CSP framework with heuristics

� Multi-agent systems, dynamic worlds much more complex

COMP9414 Planning 16

Planning as Constraint Satisfaction

CSP for each planning horizon k (vary k as needed)

� Variables

◮ Create a variable for each literal and time 0, · · · ,k

◮ Create a variable for each action and time 0, · · · ,k−1

� Constraints

◮ State constraints: literals at time t

◮ Precondition constraints: actions and states at time t

◮ Effect constraints: actions at time t, literals at times t and t +1

◮ Action constraints: actions at time t (mutual exclusion)

◮ Initial state constraints: literals at time 0

◮ Goal constraints: literals at time k

Related Posts