Sistemi per il Governo dei Robot
Silvia Rossi - Lezione 11
THE REACTIVE PARADIGM
Paradigma Reattivo
Il Paradigma Reattivo emerse nei tardi anni ‘80.
Esso è importante da studiare per almeno due motivi.
Primo, i sistemi robotici operanti in domini ristretti con compiti limitati sono ancora oggi costruiti
usando architetture reattive.
Secondo, il Paradigma Reattivo è la base per il
Paradigma Reattivo-Deliberativo Ibrido
Reactive Paradigm Overview
• Two Representative Reactive Architectures:
1) Subsumption
2) Potential Fields Summation
• Reactive Paradigm grew out of the dissatisfaction of the
hierarchical paradigm and with the influx of ideas from
biological intelligence.
Horizontal Decomposition of Hierarchical Model
SENSE PLAN ACT
SENSORS EXTRACT FEATURES
COMBINE FEATURE
S INTO MODEL
PLAN TASKS
TASK EXECUTION
MOTOR
CONTROL ACTUATORS
Vertical Decomposition
• Instead, examination of ethological literature suggests that intelligence is layered in a vertical decomposition:
1. Agent starts with primitive survival behaviours.
2. Evolve new layers of behaviour which either:
a) Reuse the lower, older behaviour b) Inhibit older behaviour
c) Create parallel tracts of more advanced behaviours
3. Parallel tracks can be thought of as vertically stacked layers
4. Each layer has access to sensors and actuators independently of any other layer.
5. If anything happens to the more advanced layer, lower levels should
Vertical Decomposition
SENSE ACT
SENSE ACT
SENSE ACT
SENSE ACT
SENSORS ACTUATORS
AVOID COLLISIONS WANDER
EXPLORE BUILD MAPS
VERTICAL DECOMPOSITION OF TASKS INTO A S-A ORGANISATION, ASSOCIATED
WITH THE REACTIVE PARADIGM
Attributes of Reactive Paradigm
• The fundamental attribute of reactive paradigm is all actions are accomplished through behaviours
• As in ethological systems, behaviours are a direct mapping of sensory inputs to a pattern of motor actions that are then used to achieve a
task.
BEHAVIOUR
SENSE ACT
BEHAVIOUR
SENSE ACT
BEHAVIOUR
SENSE ACT
BEHAVIOUR
SENSE ACT
S-A ORGANISATION OF THE REACTIVE PARADIGM INTO
MULTIPLE, CONCURRENT
BEHAVIOURS
Per gli scopi di questo corso, un behaviour sarà
trattato come uno schema, e consisterà di almeno un schema motore ed uno schema percettivo.
Lo schema percettivo contiene l'algoritmo per estrarre il percetto e la sua forza (o valore), lo
schema motore contiene l'algoritmo per generare il pattern di azione per un attuatore fisico.
Teniamo presente però che solo poche architetture di robot reattivi descrivono i loro behaviour in
termini di schemi. Ma in pratica, le diverse
realizzazioni con behaviour hanno routine motorie e percettive riconoscibili, anche se raramente sono
riportate come schemi.
Attributes of Reactive Paradigm (continued)
• From mathematical perspective, behaviours are simply a transfer function.
• The Reactive Paradigm essential threw away the PLAN component.
• The SENSE & ACT are tightly coupled into behaviours &
sequential or concurrent robotic activities emerge.
• Sensing is local to each behaviour, but sensors may be shared and is immediately available to the behaviour's perceptual
schema which can be computationally inexpensive.
Characteristics of Reactive Behaviours
• Reactive robotic systems execute rapidly (tight coupling of senses permits real-time operation)
• Behaviours can be implemented directly in hardware circuits or low computational complexity algorithms (O(n)).
• Have no memory (limiting behaviours to stimulus-response reflexes)
• Main point “Behaviours controlled by what is happening in the
world, duplicating the spirit of the innate releasing mechanisms,
rather than the program storing & remembering what the robot
last did”
5 Caratteristiche
1) I robot sono agenti situati che operano in una nicchia ecologica.
Come visto nella prima parte, agente situato vuole dire che il robot è una parte integrante del mondo. Un robot ha le sue
proprie mete ed intenzioni. Quando un robot agisce, cambia il mondo, e riceve una reazione immediata dal mondo attraverso i sensori. Quello che il robot percepisce influenza le sue mete e, il tentativo di soddisfarle, genera un nuovo ciclo di azioni.
Attenzione che la situatedness è definita da un ciclo Azione- Percezione alla Neisser.
Similmente, le mete del robot, il mondo nel quale opera e come esso può percepire il mondo formano la nicchia ecologica del robot.
Per enfatizzare questo, molti ricercatori di robotica dicono che
loro stanno lavorando su robotica ecologica.
5 Caratteristiche
2) I behaviour servono come fondamenti di base per le azioni del robot, ed il behaviour complessivo del robot è quello che emerge.
I behaviour sono entità computazionali indipendenti, ed operano concomitantemente. Il behaviour
complessivo emerge di conseguenza: non c'è nessun modulo "controllore" esplicito che determina quello
che sarà fatto, o funzioni che chiamano altre funzioni.
Ci può essere un programma di controllo coordinato nello schema di un behaviour, ma non c'è nessun controllore esterno di tutti i behaviour per un dato compito.
Come con gli animali, l’"intelligenza" del robot è nell'occhio dell'osservatore, piuttosto che in un specifico pezzo di codice. Poiché il behaviour
complessivo di un robot reattivo emerge dal modo con cui i suoi behaviour
individuali interagiscono, le maggiori differenze tra le architetture reattive
5 Caratteristiche
3) Sono permessi solo percetti behaviour-specifico locali.
L'uso di rappresentazioni della conoscenza astratte esplicite nel trattare la percezione, anche se è behaviour-specifico, è evitato.
Qualunque percetto che richiede rappresentazione è espresso mediante coordinate ego-centriche (robot-centriche).
Per esempio, si consideri l’evitare un ostacolo. Una
rappresentazione ego-centrica vuole dire che non è importante
che un ostacolo è nel mondo alle coordinate (x,y,z), ma solamente dove è relativamente al robot.
I dati sensoriali, con l'eccezione del GPS, sono inerentemente ego-centrici (e.g., un range finder ritorna una distanza
dall'oggetto più vicino al transducer), questo elimina
l’elaborazione necessaria per creare un modello del mondo,
mentre estrae solo la posizione degli ostacoli relativamente al
robot
5 Caratteristiche
4) Questi sistemi seguono i buoni principi della progettazione software.
La modularità dei behaviour favorisce la decomposizione di un task in behaviour componenti.
I behaviour sono esaminati indipendentemente, e
possono essere assemblati a partire da behaviour
primitivi.
5 Caratteristiche
5) Modelli di behaviour ispirati ad animali sono
spesso citati come una base per questi sistemi o per un particolare behaviour.
Diversamente dai primi giorni della robotica AI, dove c'era un sforzo consapevole di non imitare l'intelligenza biologica ma di ricorrere alla
matematica e alla logica, nel paradigma reattivo è
accettabile usare gli animali come ispirazione per
una collezione di behaviour.
Advantages of Programming by Behaviour
• Constructing a robotic system under Reactive Paradigm often referred to as programming by behaviour.
• Good Software Engineering since Behaviours are Modular.
• Robot becomes more intelligent by having more behaviours.
• Modules have Low Coupling
can function independently of each other with minimal connections or interfaces promoting easy reuse.
• Modules have High Cohesion
Data and operations contained by a module relate only to the
purpose of that module.
Innate releasing mechanisms created imlicit chaining
because multiple affordances in the world don’t (normally) occur
But if multiple affordances collide:
Equilibrium: animal seems to be frozed
e.g., squirrel being fed
Dominance: winner takes all (inhibition, gains)
e.g., sleepimg or eating
Cancellation: other behaviors arises
e.g., defend, attack = build nest
Categories of Coordination
Reactive Paradigm Representative Architectures
• The overall action of the robot emerges from the multiple concurrent behaviours and the architecture must provide mechanisms for:
1) Triggering behaviours
2) Conflict resolution when multiple behaviours are active at any one time.
• The two most well known Reactive Architectures are
1) Potential Fields – Behaviours combined by summation of fields.
2) Subsumption – Decomposition into layers of task achieving
behaviours.
Subsumption Architecture
Brooks disse (rumorosamente) in una conferenza, "noi non
abbiamo bisogno di rappresentazioni puzzolenti" e scrisse un lavoro dal titolo “Gli elefanti non giocano a scacchi” (1990).
Si dovrebbe notare che spesso la parte di schemi percettivi del behaviour deve usare una rappresentazione behaviour- specifica o una struttura dati per rivelatori specializzati
capace di estrarre affordances.
Per esempio, estrarre una regione rossa in un'immagine è
non-banale per un computer comparato con un animale che vede il rosso.
Il punto è che mentre un programma di computer può dovere
avere strutture dati per simulare un semplice funzionamento
neurale, il behaviour non conta su alcuna rappresentazione
Subsumption Architecture
• Rodney Brooks Subsumption Architecture most influential of the purely Reactive Paradigms.
• Many look like shoe-box sized insects (6 legs and antennae)
• Implementations quite often have the behaviours embedded
directly in the hardware or small micro processors (unheard pre mid 1980’s)
• Robots could now walk, avoid collisions and climb over
obstacles without the move-think-move-think pauses of Shakey.
• A behaviour is a network of sensing and acting modules which accomplish a task.
• The modules are Augmented Finite State Machines (AFSM), or finite state machines which have registers, timers & other
enhancements to permit them to be interfaced with other
modules.
Nelle prime realizzazioni del paradigma reattivo, l'idea di "un sensore, un behaviour" funzionò
bene.
Per behaviour più avanzati, divenne utile fondere l’output di sensori multipli all'interno di uno
schema percettivo per avere maggiore precisione o una migliore misura della forza dello stimolo.
Questo tipo di fusione di sensori è permesso
all'interno del paradigma reattivo finché la fusione
è locale al behaviour.
• Behaviours are released in a stimulus response way, without an external program explicitly coordinating and controlling them.
• Layers of Competence:
The layers reflect a hierarchy of intelligence or competence.
lower layers encapsulate basic survival functions (collisions) higher levels create more goal directed actions (mapping)
Each of the layers can be viewed as an abstract behaviour for a particular task.
Subsumption Architecture (continued)
• Subsumption of lower layers:
- Modules in a higher layer can override or subsume the output from behaviours in the next lower layers.
- Behaviour layers operate concurrently and independently and hence need mechanism to handle potential conflicts winner always takes all (always the highest layer)
Suppression: substitute input going to a module Inhibit: turn off output from a module
Subsumption Architecture (continued)
• No World Model (Internal State)
- No persistence representation of the world model since information comes directly from the world.
- Dangerous to depend on internal state since may diverge from reality.
- Some internal state needed for releasing behaviours (i.e. scared, hungry), but good design minimises this.
Subsumption Architecture (continued)
• Taskable
- Tasks are accomplished by activating the appropriate layer, which then activate the lower layers.
- In practice, Subsumption style systems are not easily taskable, that is, they can’t be ordered to do another task without being
reprogrammed.
Subsumption Architecture (continued)
Ci sono quattro aspetti interessanti della
sussunzione in termini di attivazione e controllo :
1) I moduli sono raggruppati in strati di competenza.
2) I moduli in un strato più alto possono avere la priorità, o sussumere, l’output del behaviour nello strato adiacente più basso.
3) L'uso di stati interni è evitato quando possibile.
4) Un task è portato a termine attivando lo strato
opportuno che poi attiva gli strati più bassi sotto di
lui e così via.
Reading List
Rodney A. Brooks, "Intelligence without representation", Artificial Intelligence Volume 47, Issue 1-3 (January 1991) Pages: 139 - 159
Rodney A. Brooks, "Elephants don't play chess", Robotics and
Autonomous Systems Volume 6, Issue 1-2 (June 1990) Pages: 3 -
15
Development by subsumption
……… …
STAGE n
SYSTEM
time
Situation 2
Situation 1 Situation n
STAGE 1
STAGE 2
STAGE 1
OK
OK
OK
OK
OK OK
0 Step 1 Step 2
…
Step n ResultSTAGE 2
STAGE 1
Obstacle Avoidance Example
• Sensor: A SONAR module that gives the distance to the objects in polar coordinates.
• Internal Modules
– COLLIDE detects if front obstacle is too close (i.e. halt) – FEELFORCE sensor reading acts as repulsive force field – RUNAWAY provides direction to move
• Actuators
– TURN provides motor output to turn robot
– FORWARD switches forward motion on or off
Sonar Module
“robo-centric” view of range readings
0
1
2 3 4
7
6
5 0 1 2 3 4 5 6 7
UNROLLED INTO A PLOT
SONAR MODULE READS THE SONAR RANGES.
POLAR PLOT RANGE READINGS IN POLAR COORDINATES (R,Θ)
SURROUNDING THE ROBOT.
Level 0 Architecture: obstacle avoidance
Se la lettura del range del sonar rivolto in avanti è sotto una
certa soglia, il modulo COLLIDE annuncia una collisione e
spedisce il segnale di alt all'attuatore che gestisce il
FORWARD.
Level 0 Architecture: obstacle avoidance
Nel frattempo, il modulo di FEELFORCE sta ricevendo lo stesso grafico polare.
Esso tratta ogni lettura del sonar come una forza repulsiva che può essere rappresentata come un vettore.
FEELFORCE può essere pensato come un sommatore di
vettori formati da ognuna delle letture sonar. Questo dà
luogo ad un vettore nuovo.
Level 0 Architecture: obstacle avoidance
Il vettore repulsivo è passato poi al modulo di TURN.
Il modulo di TURN fornisce la direzione per girare e la invia all'attuatore di svolta.
TURN passa il vettore anche al modulo FORWARD che usa
la grandezza del vettore per determinare la grandezza del
prossimo movimento in avanti (quanto lontano o quanto
veloce). Così il robot gira e va via per una piccola distanza
Il behaviour osservabile consiste nella verifica che il robot fa di non trovarsi in un spazio occupato.
Questo behaviour si ripete finché un ostacolo non arriva vicino al robot. Se l'ostacolo è su un lato del robot, il robot girerà di 180° nella direzione
opposta e andrà via.
Il robot può reagire ad un ostacolo se l'ostacolo (o
robot) è immobile o in lento movimento; la risposta
è calcolata ad ogni aggiornamento dei sensori.
Se parte dell'ostacolo, o un altro ostacolo, è
messo davanti, il robot si fermerà, poi applicherà i risultati di RUNAWAY. Cioè si fermerà, girerà e
comincerà a muoversi di nuovo in avanti. La fermata impedisce al robot di urtare l'ostacolo mentre sta girandosi.
Il livello 0 mostra come un set abbastanza
complesso di azioni può emergere da moduli
molto semplici.
Per gli scopi di questo corso, un behaviour deve consistere di uno schema percettivo e di uno schema motorio. Gli schemi percettivi sono connessi ad un sensore, mentre gli schemi motori sono connessi ad attuatori.
Per il Livello 0, gli schemi percettivi sarebbero contenuti nei moduli FEELFORCE e COLLIDE.
Gli schemi motori sono i moduli RUNAWAY e COLLIDE.
COLLIDE combina sia il processo percettivo (estrae il vettore dal sonar che guarda
direttamente avanti) sia il pattern attuativo (dà l'alt se c'è una lettura negativa).
I behaviour primitivi riflettono i due percorsi attraverso lo strato.
Uno potrebbe essere chiamato il behaviour di RUNAWAY e l'altro il behaviour di COLLIDE.
Insieme, i due behaviour creano un behaviour per
evitare ostacoli, o uno strato di competenza.
Livello 1
Si noti che i behaviour usano una percezione
diretta, o affordances. La presenza di una lettura di distanza indica che c’è un ostacolo; il robot non sa di che tipo di ostacolo si tratti.
Supponiamo di costruire un robot che va in giro invece di stare immobile, ma è sempre capace di evitare ostacoli. Sulla base dello schema a
sussunzione, può essere aggiunto un secondo
strato di competenza (Livello 1).
In questo caso, il Livello 1 consiste di un modulo WANDER che elabora un andamento casuale ogni n secondi.
L'andamento casuale può essere pensato come un vettore. Esso ha bisogno di passare la sua
indicazione ai moduli TURN e FORWARD. Ma non può essere passato direttamente al modulo TURN.
Questo infatti sacrificherebbe l’evitare gli ostacoli, perché TURN accetta solamente un input. Una
soluzione è di aggiungere un altro modulo al
Livello 1, AVOID che combina il vettore di
Level 1 Architecture: wander
HOW DOES TURN KNOW WHICH MODULE TO TAKE HEADING FROM?
WANDER - CAN’T PASS DIRECTLY ONTO TURN SINCE WILL SACRIFICE OBSTACLE AVOIDANCE
Aggiungendo un nuovo modulo AVOID si offre
un'opportunità di creare una risposta più sofisticata agli ostacoli.
AVOID combina la direzione della forza da evitare con la direzione desiderata. Questo dà luogo alla
direzione attuale che è rivolta più verso una direzione corretta che verso la svolta che il robot avrebbe
dovuto fare facendo un avanzamento diretto.
(Si noti anche che il modulo AVOID è capace di
"spiare" le componenti dello strato più basso).
L’output di una direzione di AVOID ha la stessa
rappresentazione dell’output di RUNAWAY così che
Il problema ora è quello di stabilire quando accettare il vettore di direzione e da quale strato.
La sussunzione rende questo semplice: l’output dal livello più alto sussume l’output dal livello più basso.
La sussunzione è realizzata in uno dei due seguenti modi:
inibizione.
Nell’inibizione, l’output del modulo di sussunzione è
connesso all’output di un altro modulo. Se l’output del
modulo che sussume è "on" o ha un qualunque valore,
l’output del modulo sussunto è spento. L’inibizione
agisce come un rubinetto, cambiando da on a off
Suppression – replaces all other inputs to the module with input
coming from the “suppressing” module.
2. soppressione.
Nella soppressione, l’output del modulo che sussume è connesso all’input di un altro modulo. Se l’output del
modulo che sussume è on, esso sostituisce l’input normale al modulo sussunto.
La soppressione agisce come uno switch, scambiando un input con un altro.
In questo caso, il modulo AVOID sopprime (segnato nel diagramma con una S) l’output da RUNAWAY.
RUNAWAY sta ancora operando, ma il suo output non va
da nessuna parte.
Inhibition – blocks output from the specified module for the
defined time interval.
L'uso di strati e sussunzione permette a nuovi strati di essere costruiti sopra lo strato meno
competente, senza cambiare gli strati più bassi.
Questa è buona ingegneria del software, poichè facilita la modularità e semplifica il test. Essa
aggiunge anche un po' di robustezza nel senso
che se qualche cosa dovesse disabilitare il Livello 1, il Livello 0 è probabile che rimanga intatto.
Il robot sarebbe almeno capace di preservare il
suo meccanismo di autodifesa e quindi di fuggire
quando si avvicina agli ostacoli.
FEELFORCE è usato da RUNAWAY e AVOID.
FEELFORCE è la componente percettiva (nello schema) di ambo i behaviour, con i moduli AVOID e RUNAWAY che sono il componente motorio.
Spesso accade che i behaviour sono chiamati con il nome dell'azione osservabile. Questo vuole dire che il behaviour (che consiste di percezione ed azione) e la componente azione hanno lo stesso nome.
La figura non mostra che i behaviour AVOID e RUNAWAY hanno lo stesso schema percettivo FEELFORCE. Le proprietà object-oriented dello
schema theory facilitano il riuso e la condivisione di
componenti percettive e motorie.
Ora supponiamo di aggiungere un terzo strato per permettere al robot di muoversi lungo un corridoio, il terzo strato nel lavoro originale di Brooks è
"esplorare", perché lui stava considerando un task di mappatura.
Il modulo di LOOK esamina il plot polare del sonar ed identifica un corridoio. (Si noti che questo è un altro esempio di behaviour che condivide gli stessi dati sensoriali ma li usa localmente per scopi
diversi).
Level 2 Architecture: follow corridor
INTEGRATE - ESTIMATES HOW FAR ROBOT HAS TRAVELLED OFF COURSE
SUPPLIES DANGEROUS INTERNAL STATE