Transcript 74.419 Artificial Intelligence 2002 Description Logics

74.419 Artificial
Intelligence 2005/06
Hierarchical Planning
and Other Stuff
Russell and Norvig, Chapter 11
STRIPS – Plan Schemata
 Concrete plans can also be seen as
instantiations of Plan Schemata.
 Shakey was able to generalize generated
concrete plans into such plan schemata.
( plan generalization, learning)
Plan Learning / Plan Abstraction
Shakey generated plan schemata, so-called MACROPs
(Macro-Operators), from concrete plans it had
constructed earlier (i.e. “it learns plans”).
The learning process is based on describing the plan in
a triangle-table (preconditions and effects of sequential
actions in rows, actions in columns). Then substitute
constants with variables, in a kind of inverse variable
binding process with unification. (substitute the same
constant with one variable)
Thus, an abstract plan schema is generated from the
concrete plan.
Triangle Table


Generate Plan with STRIPS
Set up Triangle Table:



left of action: precondition
below action: effects (add-list) - record only
literals needed by subsequent actions or as part
of the goal clause.
Generalization (abstraction)

Substitute constants with variables.
"effect" of start-action 
initial state
precond. of move(A,B,Fl)
effect of move(A,B,Fl)
precond. of move(B,C,Fl)
effect of move(B,C,Fl)
precond. of finish
Generate Plan Schema


Generalization (abstraction) of concrete
plan.
Substitute constants with variables:




Fl remains Fl
Ax
By
Cz
Abstract Planning
ABSTRIPS
Consider different criticality values of preconditions in
planning.
Start with global, abstract plan.
Then refine plan by trying to fulfill preconditions of
abstract plan:
• Choose preconditions with highest criticality
values first ( = most difficult to achieve).
• Then lower criticality value and continue with
planning.
Hierarchical Planning
Principle
 hierarchical organization of 'actions'
 complex and less complex (or: abstract) actions
 lowest level reflects directly executable actions
Procedure
 planning starts with complex action on top
 plan constructed through action decomposition
 substitute complex action with plan of less complex
actions (pre-defined plan schemata; or learning of
plans/plan abstraction)
 overall plan must generate effect of complex action
Hierarchical Planning
Hierarchical Planning / Plan Decomposition
Plans are organized in a hierarchy. Links between
nodes at different levels in the hierarchy denote a
decomposition of a “complex action” into more
primitive actions (operator expansion).
Example:
move (x, y, z)
operator
expansion
pickup (x, y)
putdown (x, z)
The lowest level corresponds to executable actions of
the agent.
Hierarchical Plan - Example
Travel (source, dest.)
Take-Plane
Take-Bus
Take-Car
Goto (bus, source) Buy-Ticket (bus) Hop-on (bus) Leave (bus, dest.)
Goto (counter)
Request (ticket) Pay (ticket)
Extensions and Modifications
to Basic Planning Methods
ADL - Action Definition Language
ADL
Can be seen as extension of the STRIPS language.
Contains typing of parameters (sorts).
Allows explicit expression of negation.
Allows equality of terms in precondition formula.
Example:
Fly (p: plane; from: airport; to: airport; c: cargo)
precondition: at(p,to)  at(c,to)  in(c,p)  tofrom
effect: at(p,to)  at(c,to)  at(p,from)  at(c,from)
From Russell & Norvig, Chapter 11
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
Other Issues in Planning
Disjunctive Preconditions
 planning with alternatives
Disjunctive Effects
 parallel future worlds to consider
All-Quantified Variables (in preconditions and effects)
 only for finite, static Universe of objects
Conditional Planning
 action depends on conditions
 specified concretely only at plan execution time
 typically based on percepts/sensor information
 integrate into partial order planning with threats
Real World Agents 1

Consider Sensors and Effectors





perception of environment, e.g. vision
ensure correspondence between internal map of
robot and environment, e.g. locating robot
low-level body control, e.g. Motion Control (behaviour
routines, e.g. Fuzzy or Neural Network Controller)
other sensor information for body control and
environment mapping, e.g. bumpers, radar
sensors for other information channels and cognitive
processes, e.g. speech – language
Real World Agents 2

Low-level Processing and Control




Motion Control
Audio Recording and low-level analysis
Medium-level Processing

Navigation / Route Planning

Robot Location
Higher-level Processing



Speech Recognition, NLP, ...
Strategies, Planning
BDI (Belief-Desire-Intention) - Architecture
Real World Agents 3
Multi-Agents
 Language / Communication
 communicating agents
 Mental Models of other Agents
 cooperating agents
 Strategies
 cooperating agents
 Deontic Systems
 Trust
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)