程序代写代做代考 flex AI Unit4-Planning

Unit4-Planning

Course: C231 Introduction to AI

Introducing AI Planning
• Informal definition

• Formalising a planning problem

• Different types of planning

• Reasoning about events

• Abductive planning

• Examples

Course: C231 Introduction to AI

What is planning?

Planning is about how an agent
achieves its goals.

Delivery robot

Find a sequence of actions to
solve a goal.

To reason about what to do,
an agent must have:

Ø goals,
Ø model of the world,
Ø model of consequences of actions.

Unit 4 – Planning, slide 2

Course: C231 Introduction to AI

Example: delivery robot

State features Coffee
shop

John’s
office

Mail
Room

Lab

rhc, rhm, mw, swc, cs, off, mr, lab
Actions

move clockwise (mc), deliver mail (dm),
pick up a coffee (puc), deliver the coffee (dc),
pick up mail (pum), move unticlockwise (mcc),

Action specification
Actions Precond Postcond

puc not rhc ∧ cs rhc’
dc rhc∧ off not swc’
pum wm∧ mr rhm’
dm rhm∧ off

Explicit state space
representation is a set
of triples

But too many states and representation not very flexible
Unit 4 – Planning, slide 3

Course: C231 Introduction to AI

Feature-centric representation

For each action
precondition specifies when the action can be carried out.

For each feature:

• causal rules that specify when the feature gets a new value

• frame rules that specify when the feature keeps its value.

e.g.
cs’← cs∧ not mcc ∧ not mc
rhc’ ← rhc∧ not dc

e.g., rhc’ ← puc

Unit 4 – Planning, slide 4

Course: C231 Introduction to AI

Action-centric representation

For each action
• Preconditions – features that must be true for an action to occur
• Effects – values of feature that change as result of the actions

STRIPS representation
• Underlying assumption:

Ø Primitive features not mentioned in action descriptions are
assumed to be unchanged by the action performance.

Ø Derived features are defined, using definite clauses, in terms
of primitive features in a given state.

Example:
Precondition: [cs, not rhc]
Effect: [rhc]

action puc action dc
Precondition: [off, rhc]
Effect: [not rhc, not swc]

Unit 4 – Planning, slide 5

Course: C231 Introduction to AI

Planning with certainty

Main assumptions

Ø Deterministic actions.
• agent capable of predicting the consequences of its actions.

Ø No exogenous events that change the state of the world.

Ø World state fully observable

Ø Time progresses discretely from one state to the next.

Ø Goals are predicates about a state that must be achieved or
maintained.

Unit 4 – Planning, slide 6

Course: C231 Introduction to AI

Forward Planning

A state-space graph is a graph whose nodes are states, and arcs
are actions from one state to the other.

A deterministic plan is a sequence of actions that can achieve a goal
from a given starting state.

A deterministic planner that behaves as a problem solver for
computing deterministic plans.

A forward planner treats the planning problem as a path finder in a
state-space graph, searching the graph from the initial state to a state
that satisfies a goal description.

Unit 4 – Planning, slide 7

Course: C231 Introduction to AI

Example

Course: C231 Introduction to AI

Regression Planning

final goal property

sub-goal property

Unit 4 – Planning, slide 9

Course: C231 Introduction to AI

Language for planning

Example of 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 applicable in a state s:
There exists a substitution 𝜃, such that s ∧ PRECOND𝜃 is satisfiable.

Result of action is a state s’:
s’ = s \ {𝜑 | not 𝜑∈ EFFECT𝜃} ∪ {𝜙 | 𝜙∈ EFFECT𝜃}

Most common standardised language for planning is PDDL
(Planning Domain Definition Language)

International Planning Competition
(http://www. icaps.conference.org/index.php/Main/Competition)

Course: C231 Introduction to AI

Reasoning about (effects of) events

Event Calculus
Logical framework for representing and reasoning about events
and effects of events over time.
Ontology consists of events, fluents and time.

Predicates Meaning
initiates(e, f, t) Fluent f starts to hold after event e at time t

terminates(e, f, t) Fluent f stops to hold after event e at time t
initially(f) Fluent f holds at the beginning (starting time 0)

happens(e,t) Event e happens at time t
holdsAt(f, t) Fluent f holds at time t

clipped(t1, f, t2) Fluent f is terminated between times t1 and t2

Signature includes the following sorted predicates:

Course: C231 Introduction to AI

Event Calculus Axiomatisation

Every Event Calculus description includes two theories:

describes general principles for deciding when fluents
hold or do not hold at particular time-points

Ø domain independent theory

Ø domain dependent theory
describe particular effects of events or actions using the
predicates initiates(.) and terminates(.). It may also
include sentences stating the full initial state (using the
predicate initially(.), and a narrative of instances of events
occur at particular time-points, using predicate happens(.).

Course: C231 Introduction to AI

Domain-independent theory

Three general (commonsense) principles:

(ii) fluents that have been initiated by event occurrences continue
to hold until events occur that terminate them

holdsAt(f,t2) ← initiates(a,f,t1), happens(a,t1), t1 < t2, not clipped(t1,f,t2) (iii) fluents only change status via occurrences of terminating events (i) fluents that were initially true continue to hold until events occur that terminate them holdsAt(f, t2) ← initially(f), not clipped(0, f, t2) clipped(t1,f,t) ← happens(a, t2), terminates(e, f, t2), t1 < t2, t2 < t Course: C231 Introduction to AI © Alessandra Russo Unit 4 – Planning, slide 14 Domain-dependent theory Defines instead effects of actions and a given initial state. It depends on the particular problem that is formalised. Includes rules defining specific cases of: initiates(e, f, t) ← BODY terminates(e, f, t) ← BODY initially(f) The BODY conditions can include literals about “holdsAt” and “happens” as well as any other “static” domain specific predicate. Integrity constraints could also be expressed to capture constraints on the occurrence of events. These are normally considered in addition to the domain-dependent axiomatisation. Course: C231 Introduction to AI Event Calculus Abductive Planning © Alessandra Russo Unit 4 – Planning, slide 15 Given: DI domain independent EC theory DD domain dependent EC theory IC integrity constraints G goal state An EC plan P is a tuple where
As = {happens(ei, ti), happens(ej, tj},…}
TC = {ti < tj,…}, set of temporal constraints such that Ø DI ∪DD∪P ⊨ G Ø DI∪DD∪P ∪IC is consistent Ø KB∪∆ ⊨ G Ø KB∪∆ ∪IC ⊭ ⊥ KB ∆ Course: C231 Introduction to AI A small planning example © Alessandra Russo Unit 4 – Planning, slide 16 Consider a simple shopping trip planning, where an agent has to go to different places to buy different items. We formulate the problem as an Event Calculus Abductive Planning problem: DI (domain independent theory) holds(F, T) :- time(T), initially(F), not clipped(0, F, T). holds(F, T) :- time(T1), time(T), 0 < T1, T1 < T, happens(A, T1), initiates(A, F, T1), \+ clipped(T1, F, T). clipped(T1, F, T) :- time(T1), time(T), time(T2), T1 < T2, T2 < T, happens(A, T2), terminates(A, F, T2). Course: C231 Introduction to AI © Alessandra Russo Unit 4 – Planning, slide 17 A small planning example DD (domain dependent theory) initiates(goto(X), at(X), T) :- place(X). terminates(goto(X), at(Y), T) :- place(X), place(Y), X =/= Y. initiates(buy(Item, Place), have(Item), T) :- sells(Place, Item), item(Item), holds(at(Place), T). time(T) :- T in 0..8. fluents at(Place) have(Item) actions goto(Place) buy(Item, Place) DD (initial state and static facts) initially(at(home)). sells(sm, milk). place(sm). item(drill). sells(sm, banana). place(hws). item(milk). sells(hws, drill). place(home). item(banana). Course: C231 Introduction to AI © Alessandra Russo Unit 4 – Planning, slide 18 IC (integrity constraints) ic :- happens(E1, T), happens(E2, T), E1 =/= E2. A (abducible) abducible(happens(_,_)). Instance of Event Calculus Abductive Planning

Goal:
holds(have(banana), 5) ∧
holds(have(drill), 5)

Plan:
happens(goto(hws), 1),
happens(buy(drill, hws), 2),
happens(goto(sm), 3),
happens(buy(banana, sm), 4).

A small planning example

Course: C231 Introduction to AI

EC Abductive Planning with unground goals
Unground Goals

Compute plans that take the agent to a state that satisfies the given goal.

General EC Abductive Proof Procedure
Observations are conjunction of unground literals. Abductive solutions are
tuples (As, Cs, Ns), where

As: conjunction of (skolemised) abducibled
Cs: set of arithmetic constraints over time point variables
Ns: set of dynamic constraints (dynamic denials).

Forcing grounding of finite domain variables in solutions:
| ?- use_module(library(terms)).
| ?- use_module(library(clpfd)).

Abductive procedure grounds variables asap during inference:
| ?- enforce labeling(true)

Course: C231 Introduction to AI

Conclusion

Ø Notion of planning

Ø Forward planning

Ø Regression planning

Ø Event Calculus

Ø Event Calculus Abductive Planning

Related Posts