Sistemi per il Governo dei Robot

Sistemi per il Governo dei Robot

Silvia Rossi - Lezione 3

I paradigmi per il controllo dei robot

Gerarchico: S-P-A Reattivo: S-A

Ibrido: P, S-A

SENSE ACT

PLAN

Il Paradigma Gerarchico

Gerarchico: S-P-A

SENSE world ACT

PLAN

Il Paradigma Gerarchico

ROBOT

PRIMITIVES SENSE

PLAN

ACT

INPUT

Sensor data

Information (sensed or cognitive) Sensed

information or directives

OUTPUT

Sensed

information Directives

Actuator

commands

Architetture Gerarchiche

Caratteristiche comuni:

Struttura gerarchica

Chiara divisione delle funzionalità

Comunicazione e controllo predeterminati

I livelli alti forniscono i sotto-goal per il livelli più bassi Ha bisogno di rappresentazione simbolica

Appropriate per ambienti strutturati e predicibili

Architetture Gerarchiche

Vantaggi

Funzionamento predicibile ovvero pianificazione a priori dei comportamenti Efficienza e stabilità del sistema

Svantaggi

Alta complessità computazionale dovuta principalmente alla modellazione dell’ambiente e al ragionamento

Poca adattabilità alle modifiche in tempo reale dell’ambiente o bassa reattività Basso parallelismo

Non incrementale

una mancanza di sensibilità in ambienti non strutturati e incerti dovuta sia ai requisiti di modellazione del mondo sia alle limitate vie di comunicazione;

la difficoltà nell’ingegnerizzare sistemi completi con competenze incrementali.

In questo caso, infatti, virtualmente l’intero sistema deve essere costruito

prima di verificare che sia fattibile.

Il Paradigma Reattivo

Reattivo: S-A

SENSE world ACT

PLAN

Il Paradigma Reattivo

Reattivo: S-A

ROBOT

PRIMITIVES SENSE

PLAN

ACT

INPUT

Sensor data

Information (sensed or cognitive) Sensed

Information or directives

OUTPUT

Sensed

information Directives

Actuator

commands

Architetture Reattive

I comportamenti del robot sono reazioni alle informazioni percepite dall’ambiente

Il modulo di base di tali sistemi è costituito quindi da un comportamento (behavior) che è ottenuto da una relazione diretta tra sensori e attuatori

Si parla di behaviour-based robotics o sistemi reattivi, ovvero sistemi capaci di rispondere in

tempo reale agli stimoli provenienti dall'ambiente

circostante

Architetture Reattive

Il robot interagisce con il mondo attraverso sensori e attuatori

Non esiste una rappresentazione del mondo, (“The world is the best model” di R. A. Brooks, 1986): la conoscenza del mondo non è né modellizzata né memorizzata nel robot ma è estratta in tempo

reale dal mondo stesso attraverso i sensori Poiché non esiste un modello del mondo, di

conseguenza non esiste pianificazione a priori

delle azioni del robot

Architetture Reattive

Nelle architetture di controllo reattive l’esecuzione di un compito è suddivisa tra moduli ognuno dei quali ha assegnata una specifica competenza e attua un determinato comportamento del robot Il comportamento complessivo del robot è

determinato dall’insieme dei comportamenti

presenti

Architetture Reattive

Dalla suddivisione orizzontale e sequenziale della catena di informazioni alla suddivisione verticale e parallela

Sensori Attuatori

Identificazione degli

        ^oggetti     Costruzione della

          ^mappa       Explorazione

  Evitamento Ostacoli

Architetture Reattive

Decomposizione verticale che produce flussi multipli di

informazione ciascuno relativo ad una particolare funzione assegnata al robot.

In questo modo, ogni sequenza si occupa di uno specifico aspetto nel funzionamento globale del sistema e può

svilupparsi parallelamente ad altri processi

.. ..

SENSE SENSE

  .

SENSE

ACT ACT

  . ACT

  Behaviour n

Behaviour n-1

    Behaviour 0

Architetture Reattive

Principio di indipendenza: i vari moduli devono essere mutuamente indipendenti tra loro.

Conseguenza immediata all'applicazione di questo principio è l'impossibilità di mantenere un modello del mondo completo, condivisibile tra tutti i moduli.

Principio di località: ciascun sottocompito richiede, per completarsi, solo una parte limitata di tutta

l'informazione sensoriale disponibile. Il robot

risponde solo ad eventi del mondo senza mantenere stati persistenti: la memoria di cui ha bisogno è

realizzata leggendo direttamente la situazione

ambientale che gli indica il modo operativo corrente.

Architetture Reattive

Vantaggi

Non esiste un modello del modo

Alta adattabiltà alle modifiche dell’ambiente (risposte in tempo reale) Bassa complessità di ogni livello e basso costo computazionale

complessivo del sistema

E’ possibile avere parallelismo nel controllo

L’estensione dei comportamenti è relativamente semplice

Svantaggi

Difficoltà nel prevedere a priori il comportamento globale del robot

gestione della concorrenza tra moduli

Subsumption Architecture

Behavioural   ^module

Input Output

  Dock Operate

Wander   Avoid

  ^priority

Find

Lowest priority

Suppressor Inhibitor

  ^Highest

Subsumption Architecture

Reason about behavior of objects Plan changes to the world

  Identify objects Monitor changes

Build maps

  Explore

Wander

Avoid objects

Architetture Reattive

Livello 0: evitare gli ostacoli

Livello 1: navigazione casuale nell’ambiente

Livello 2: esplorazione del mondo e ‘identificazione’ dei punti di interesse

Livello 3: costruzione della mappa dell’ambiente (relazioni tra punti) Livello 4: rilevazione dei cambiamenti dell’ambiente statico

Livello 5: ragionamento sul mondo in termini di esecuzione di task in relazione al rilevamento di determinati oggetti

Livello 6: formulazione ed esecuzione di comportamenti che determinano cambiamenti dello stato del mondo

Livello 7: ragionamento sui comportamenti degli oggetti e modifica dei

piani in accordo

Il Paradigma Ibrido

Ibrido: P, S-A

SENSE world ACT

PLAN

Il Paradigma Ibrido

Ibrido: P, S-A

ROBOT

PRIMITIVES PLAN

SENSE-ACT

INPUT

Information (sensed or cognitive)

Sensor data

OUTPUT

Directives

Actuator

commands

Architetture Ibride

Un approccio puramente reattivo dota il robot della capacità di eseguire compiti semplici in

maniera efficiente, come ad esempio evitare gli ostacoli e adattarsi alle variazioni del mondo, ma non garantisce l’esecuzione di task più complessi, che includono modellizzazione dell’ambiente e

comportamenti più complessi

L’integrazione dei metodi reattivi con i metodi

gerarchici combina l’efficienza della pianificazione

con la flessibilità dei sistemi di controllo reattivo

Architetture Ibride

Tipicamente una architettura ibrida comprende un modulo

pianificatore strategico e un modulo pianificatore tattico per la gestione dei comportamenti di un robot.

Il pianificatore strategico pianifica a lungo termine le azioni del robot,

individuando la sequenza di sotto- obiettivi da realizzare per

raggiungere il goal e passando i risultati per l'esecuzione al

pianificatore tattico.

Il pianificatore tattico inizializza e monitora i comportamenti

prendendosi cura degli aspetti

temporali per la loro coordinazione

Aura

Architetture decentralizzate o distribuite

Un approccio alternativo all’uso di un unico

sistema robotico per l’esecuzione di compiti è

l’uso di un gruppo di sistemi robotici, ciascuno di complessità inferiore, che cooperano per

l’esecuzione dello stesso compito.

L’intelligenza è distribuita tra i vari sistemi, ognuno

dei quali è autonomo

Il controllo dei Robot

DELIBERATIVA REATTIVA

PURAMENTE SIMBOLICA ^RIFLESSIVA VELOCITÀ DI RISPOSTA

CAPACITÀ PREDITTIVE

Dipendenza dalla rappresentazione Indipendenza dalla rappresentazione Lentezza nella risposta Risposta in tempo reale

Alto livello di intelligenza (cognitiva) Basso livello di intelligenza Latenza variabile Computazioni semplici

DIPENDENZA DA UN MODELLO DEL MONDO COMPLETO E ACCURATO

Quanta IA?

Di quali funzioni ha bisogno il robot?

Generazione? Monitor? Selezione? Implementazione? Esecuzione?

Apprendimento?

Qual’e’ l’orizzonte di pianificazione?

Presente, presente+passato, presente+passato+futuro

Quanto velocemente gli algoritmi si devono aggiornare?

Assunzione di mondo chiuso

Di che tipo di modello ha bisogno il robot?

Locale, globale, entrambi

Ridurre al minimo

SENSE ACT world

PLAN

Il Paradigma Gerarchico

Gerarchico: S-P-A

Il robot in maniera sequenziale percepisce con i sensori l’ambiente in cui è immerso e se ne costruisce una

mappa.

Dopo, “ad occhi chiusi”, pianifica tutte le direttive che deve dare agli attuatori per raggiungere il suo goal.

Infine opera iniziando dalla prima direttiva.

SENSE world ACT

PLAN

Il Paradigma Gerarchico

ROBOT

PRIMITIVES SENSE

PLAN

ACT

INPUT

Sensor data

Information (sensed or cognitive) Sensed

information or directives

OUTPUT

Sensed

information Directives

Actuator

commands

Modello

Tutte le informazioni fornite dai sensori vengono messe in una struttura dati a cui accede il

pianificatore.

Questa struttura dati è anche detta modello del mondo del robot.

In questa struttura dati, nel paradigma gerarchico, sono contenuti:

a - una rappresentazione a priori del mondo in cui il robot è immerso b - informazioni sensoriali (mi trovo in questo punto della stanza)

c - ogni ulteriore informazione di tipo cognitivo (es. il goal che deve

perseguire)

Soluzione

Una soluzione di un problema di pianificazione deve avere le seguenti proprietà:

essere efficace, cioè garantire il raggiungimento dell’obiettivo

essere completa, cioè le precondizioni necessarie per ogni azione devono essere verificate e ove necessario attuate attraverso

l’esecuzione delle azioni precedenti

essere consistente, cioè non ci debbono essere contraddizioni derivanti

dall’ordine di esecuzione delle azioni o dall’istanziazione delle variabili

Block words

•A set of blocks, a table and a robot arm.

• All the blocks are equal in size, form and color, distinguished only by name.

• The table has an unlimited extension.

• A block can be on the table, on top of another block or held by the robot.

•The robot arm can only hold one block at a time.

•Solve problems by changing the initial configuration (state) into

a state that meets the goals.

Robotics

Satellites

Manufacturing

Sheet-metal bending machines - Amada Corporation Software to plan the sequence of bends

[Gupta and Bourne, J. Manufacturing Sci. and Engr., 1999]

Control Sequences on Industrial Plants

Games

Bridge Baron - Great Game Products

1997 world champion of computer bridge

[Smith, Nau, and Throop, AI Magazine, 1998]

2004: 2nd place

(NORTH— ♠Q) … …

FinesseFour(P ₄ ; S) PlayCard(P ₁ ; S, R ₁ )

StandardFinesseTwo(P ₂ ; S) LeadLow(P ₁ ; S)

StandardFinesseThree(P ₃ ; S)

EasyFinesse(P ₂ ; S) BustedFinesse(P ₂ ; S) FinesseTwo(P ₂ ; S)

StandardFinesse(P ₂ ; S) Finesse(P ₁ ; S)

Us:East declarer, West dummy Opponents:defenders, South & North

Contract:East – 3NT

On lead:West at trick 3 East:♠KJ74 West: ♠A2 Out: ♠QT98653

(NORTH— 3)

WEST— ♠2

Transportation Logistics

• Set of cities, with airports and post offices

•Set of plans that can fly between cities

•Set of trucks that can only transfer packages between locations in the same city

•Set of packages that need to be distributed to different

locations, possibly in different cities

Tourisms

Military Operations

Civil Emergencies

VideoGames

Classical Planning

Classical planning requires all eight restrictive assumptions Offline generation of action sequences for a deterministic, static, finite system, with complete knowledge, attainment goals, and implicit time

Reduces to the following problem:

Given (Σ, s ₀ , S _g )

Find a sequence of actions (a ₁ , a ₂ , … a _n ) that produces a sequence of state transitions (s ₁ , s ₂ , …, s _n )

such that s _n is in S _g .

This is just path-searching in a graph Nodes = states

Edges = actions

Is this trivial?

Deterministic Planning Approaches

•Strips Algorithms (1970): means-ends analysis, backward chaining search, HACKER, PRODIGY

•Partial Order Planning (1980): search in the plan space, TWEAK, UCPOP, SNLP, UNPOP

•Graphplan Planning (1995): search in a graph plan, GRAPHPLAN, IPP

•SAT Planning (1996): convert a planning problem into a SAT problem, BLACKBOX

•Heuristic Search Planning (1997): HSP, GRT, FF, MIPS, STAN

•Hierarchical Planning (1994) : O-PLAN, UMCP, ABSTRIPS, SHOP,

SIADEX

Major approaches

Situation calculus

State space planning Partial order planning Planning graphs

Hierarchical decomposition (HTN planning) Reactive planning

PLANNING RAPIDLY CHANGING SUBFIELD OF AI

IN BIANNUAL COMPETITION AT AI PLANNING SYSTEMS CONFERENCE:

• FOUR YEARS AGO, BEST PLANNER DID PLAN SPACE SEARCH USING

SAT SOLVER

• THREE YEARS AGO, THE BEST PLANNER DID REGRESSION SEARCH

• LAST YEAR, BEST PLANNER DID FORWARD STATE SPACE SEARCH WITH

AN INADMISSIBLE HEURISTIC FUNCTION

STRIPS (Fikes and Nilsson 1971)

Stanford Research Institute Problem Solver Control System for the Shakey robot

http://www.ai.sri.com/shakey/

Knowledge Representation in Strips

A state is represented as a conjunction of instantiated predicates

at(object1,airport1), at(plane1,airport1),

at(truck1,airport1), at(truck2,post-office2), ...

Normally, it is assumed that the facts not

present in a state are false: closed world

assumption.

States and Goals in Block world

The following predicates can be used:

on(x,y): block x is on top of block y on-table(x): block x is on the table

clear(x): block x has no block above it and is not being held by the robot arm

holding(x): the robot arm is holding block x

arm-empty: the robot arm is not holding a

block

Basic representations for planning

Classic approach first used in STRIPS planner circa 1970

States represented as a conjunction of ground literals

at(Home)

Goals are conjunctions of literals, but may have existentially quantified variables

at(x) ^ have(Milk) ^ have(bananas) ...

Do not need to fully specify state

Non-specified either don’t-care or assumed false Represent many cases in small storage

Often only represent changes in state rather than entire situation

Operator/action representation

Operators contain three components:

Action description

Precondition - conjunction of positive literals

Effect - conjunction of positive or negative literals which describe how situation changes when operator is applied

Example:

Op[Action: Go(there),

Precond: At(here) ^ Path(here,there), Effect: At(there) ^ ~At(here)]

All variables are universally quantified

Situation variables are implicit

preconditions must be true in the state immediately before

operator is applied; effects are true immediately after

Blocks world

The blocks world is a micro-world that consists of a table, a set of blocks and a robot hand.

Some domain constraints:

Only one block can be on another block Any number of blocks can be on the table The hand can only hold one block

Typical representation:

ontable(a) ontable(c) on(b,a)

handempty clear(b)

clear(c)

A B

C

TABLE

State Representation

CONJUNCTION OF PROPOSITIONS:

BLOCK(A), BLOCK(B), BLOCK(C),

ON(A,TABLE), ON(B,TABLE), ON(C,A), CLEAR(B), CLEAR(C), HANDEMPTY

A B C

TABLE

Vacuum-Robot Example

 Two rooms: R ₁ and R ₂

 A vacuum robot

 Dust

R ₁ R ₂

State Representation

In(Robot, R ₁ ) ∧ Clean(R ₁ )

R ₁ R ₂

 CONJUNCTION OF PROPOSITIONS

 NO NEGATED PROPOSITION, SUCH AS ¬CLEAN(R ₂ )

 CLOSED-WORLD ASSUMPTION: EVERY PROPOSITION THAT IS NOT LISTED IN A STATE IS FALSE IN THAT STATE

 NO “OR” CONNECTIVE, SUCH AS IN(ROBOT,R ₁ )∨IN(ROBOT,R ₂ )

 NO VARIABLE, E.G., ∃X CLEAN(X)

Goal Representation

A B C

CONJUNCTION OF PROPOSITIONS:

ON(A,TABLE), ON(B,A), ON(C,B)

THE GOAL G IS ACHIEVED IN A STATE S IF ALL THE

Goal Representation

A GOAL G IS ACHIEVED IN A STATE S IF ALL

THE PROPOSITIONS IN G (CALLED SUB-GOALS) ARE ALSO IN S

EXAMPLE: CLEAN(R ₁ ) ∧ CLEAN(R ₂ )

 CONJUNCTION OF PROPOSITIONS

 NO NEGATED PROPOSITION

 NO “OR” CONNECTIVE

 NO VARIABLE

Action Representation

UNSTACK(X,Y)

• P =HANDEMPTY, BLOCK(X), BLOCK(Y), CLEAR(X), ON(X,Y)

•E =¬HANDEMPTY, ¬CLEAR(X), HOLDING(X),

¬ON(X,Y), CLEAR(Y)

PRECONDITION: CONJUNCTION OF PROPOSITIONS

EFFECT: LIST OF LITERALS

MEANS: REMOVE HANDEMPTY MEANS: ADD

Action Representation

 An action A is applicable to a state S if the propositions in its precondition are all in S

 The application of A to S is a new state

obtained by deleting the propositions in the delete list from S and adding those in the

add list

RIGHT

 PRECONDITION = IN(ROBOT, R ₁ )

 DELETE-LIST = IN(ROBOT, R ₁ )

 ADD-LIST = IN(ROBOT, R ₂ )

I go from home to the store, creating a new situation S’. In S’:

◦The store still sells chips

◦My age is still the same

◦Los Angeles is still the largest city in California…

How can we efficiently represent everything that hasn’t changed?

STRIPS provides a good solution for simple

Example

A B C

UNSTACK(C,A)

• P =HANDEMPTY, BLOCK(C), BLOCK(A), CLEAR(C), ON(C,A)

•E =¬HANDEMPTY, ¬CLEAR(C), HOLDING(C),

¬ON(C,A), CLEAR(A)

BLOCK(A), BLOCK(B), BLOCK(C),

ON(A,TABLE), ON(B,TABLE), ON(C,A),

CLEAR(B), CLEAR(C), HANDEMPTY

Example

A B

C BLOCK(A), BLOCK(B), BLOCK(C),

ON(A,TABLE), ON(B,TABLE), ON(C,A), CLEAR(B), CLEAR(C), HANDEMPTY, HOLDING(C), CLEAR(A)

UNSTACK(C,A)

• P =HANDEMPTY, BLOCK(C), BLOCK(A), CLEAR(C), ON(C,A)

•E =¬HANDEMPTY, ¬CLEAR(C), HOLDING(C),

Action Representation

UNSTACK(X,Y)

• P = HANDEMPTY, BLOCK(X), BLOCK(Y), CLEAR(X), ON(X,Y)

•E = ¬HANDEMPTY, ¬CLEAR(X), HOLDING(X), ¬ ON(X,Y), CLEAR(Y)

STACK(X,Y)

• P = HOLDING(X), BLOCK(X), BLOCK(Y), CLEAR(Y)

• E = ON(X,Y), ¬CLEAR(Y), ¬HOLDING(X), CLEAR(X), HANDEMPTY

PUTDOWN(X)

• P = HOLDING(X)

• E = ON(X,TABLE), ¬HOLDING(X), CLEAR(X), HANDEMPTY

PICKUP(X)

• P = HANDEMPTY, BLOCK(X), CLEAR(X), ON(X,TABLE)

• E = ¬HANDEMPTY, ¬CLEAR(X), HOLDING(X), ¬ ON(X,TABLE)

Key-in-Box Example

 The robot must lock the door and put the key in the box

 The key is needed to lock and unlock the door

 Once the key is in the box, the robot can’t get it back

R ₁ R ₂

Initial State

R ₁ R ₂

Initial State

In(Robot,R ₂ ) ∧ In(Key,R ₂ ) ∧ Unlocked(Door)

R ₁ R ₂

Goal

R ₁ R ₂

Goal

Locked(Door) ∧ In(Key,Box)

[The robot’s location isn’t specified in the goal]

R ₁ R ₂

Actions

Grasp-Key-in-R ₂ Lock-Door

Move-Key-from-R ₂ -into-R ₁ Put-Key-Into-Box

R

R

Actions

Grasp-Key-in-R ₂

P = In(Robot,R ₂ ) ∧ In(Key,R ₂ )

D = ∅

A = Holding(Key) Lock-Door

P = Holding(Key)

D = ∅

A = Locked(Door) Move-Key-from-R ₂ -into-R ₁

P = In(Robot,R ₂ ) ∧ Holding(Key) ∧ Unlocked(Door) D = In(Robot,R ₂ ), In(Key,R ₂ )

A = In(Robot,R ₁ ), In(Key,R ₁ ) Put-Key-Into-Box

P = In(Robot,R ) ∧ Holding(Key)

R

R

Typical BW planning problem

Initial state:

clear(a) clear(b) clear(c)

ontable(a) ontable(b) ontable(c) handempty

Goal:

on(b,c) on(a,b)

ontable(c)

A C B

A B C

A plan:

pickup(b)

stack(b,c)

pickup(a)

stack(a,b)

Another BW planning problem

Initial state:

clear(a) clear(b) clear(c)

ontable(a) ontable(b) ontable(c) handempty

Goal:

on(a,b) on(b,c)

ontable(c)

A C B

A B

A plan:

pickup(a)

stack(a,b)

unstack(a,b)

putdown(a)

pickup(b)

stack(b,c)

pickup(a)

stack(a,b)

Forward Search

Operators are applied until the goals are reached ProgWS(state, goals, actions, path)

If state satisfies goals, then return path else a = choose(actions), s.t.

preconditions(a) satisfied in state if no such a, then return failure

else return

ProgWS(apply(a, state), goals, actions, concatenate(path, a))

First call: ProgWS(IS, G, Actions, ())