Seminario di logica Fuzzy

Seminario di logica Fuzzy(G. Ulivi, S. Panzieri)

Applicazioni alla robotica mobile:Applicazioni alla robotica mobile:Costruzione di mappe

LocalizzazioneObstacle avoidance

Roma TRE – DIA – S. Panzieri 2

Applicazioni e Aree di Ricerca

Esplorazione spazialeEsplorazione spazialeMonitoraggio delle aree pericoloseMonitoraggio delle aree pericoloseSorveglianza di grandi aree Sorveglianza di grandi aree Pulitura di ampie superficiPulitura di ampie superficiAGV industrialiAGV industrialiDistribuzione della posta negli ufficiDistribuzione della posta negli ufficiIrrorazione di campi coltivati e serreIrrorazione di campi coltivati e serreAssistenza ai disabiliAssistenza ai disabiliNuove funzionalitNuove funzionalitàà automobilisticheautomobilistiche

Controllo Controllo ““ClassicoClassico”” & & ““IntelligenteIntelligente””Problemi di StimaProblemi di StimaProblemi di MeccanicaProblemi di Meccanica

Task planningTask planningPath planningPath planningTrajectory trackingTrajectory trackingSensing and sensor fusionSensing and sensor fusionEnvironment mapping Environment mapping LocalizationLocalizationObstacle avoidanceObstacle avoidanceServo controlServo control

An intelligent system has the ability to act appropriately in an uncertain environment... (Antsaklis)


La Percezione del mondo ed i Sensori

OstacoloOstacolo

Ester. Ester. senssens..

MappaMappa

Propr. sens.

Sensori EsterocettiviEsterocettivi•Usati per misurare distanze dagli ostacoli

•Poca risoluzione

Sensori PropriocettiviPropriocettivi•Usati per misurare lo spazio percorso

•Gli errori si accumulanoMappaMappa

•Una struttura di dati in cui l’informazione spaziale è ricavata dalle misure oppure fornita a priori


Alcuni casi tipici di Navigazione

Ambiente• Noto• Sconosciuto• Statico• Dinamico

Sensori• Esatti• Reali


Ambiente noto & Sensori Esatti

FunzionalitFunzionalitàà richiesterichieste

Path Planning• Trovare il miglior

percorso

Trajectory tracking• Rimanere sul percorso

pianificato

!!


Ambiente Statico e noto & Sensori Reali


Path planning

Stima della posizione del Robot (Localizzazione)

• Comparando le misure esterocettive attuali con quelle attese dall’ambiente (di cui si ha una mappa)

Trajectory tracking


Amb. Statico e sconosciuto & Sensori Esatti


Percezione• Stima della posizione degli

ostacoli

Costruzione di Mappe• Mappa composta passo

dopo passo

Planning parziale

Trajectory tracking• (nell’area conosciuta)

iterare


Ambiente statico sconosciuto & Sensori Reali

Un problema apertoSoluzioni euristiche e parziali


Ambiente Dinamico

Alcune aree possono modificarsi, e.g.: Porta che si apre

• Mappe dinamiche

Ostacoli inattesi• Obstacle avoidance

In genere un modulo di Obstacle Avoidance è sempre presente per rendere il sistemadi navigazione più robusto.


Problemi connessi alla Navigazione

La coordinazione e sincronizzazione di tutte le funzioni sono un problema successivo

…gestione del caricopianificazione del compito e della missionesicurezzaMMI

Localization

Map building

Path planning

Trajectory tracking

Obstacle avoidance

Servo control

sens

ori

Este

roce

ttivi

sens

ori

Prop

rioce

ttivi


Quando il Controllo Intelligente?

Complessità del Task

Incertezze

Elevato costo della conoscenza quantitativa

Metodi“Rule based” o “Algoritmici”( fuzzy )

La conoscenza qualitativa è disponibile ed utile?

Approcci ad Apprendimento (Learning)( Neural and genetic )

Si

No

Task ben posti

Modelli affidabili

Conoscenza quantitative

Metodi di Controlloclassici

•manutenzione

•leggibilità

•aggiornamento

•Richiesta ampia conoscenza

•Scrittura e adattamento delle regole

Controllo intelligente


Elaborazione Fuzzy della Percezione

• Costruzione di Mappe Fuzzy GlobaliMappe Fuzzy Globali a partire da sensori ad ultrasuoni

• Pianificazione di un percorso ottimo su mappe fuzzy

• Estrazione della struttura di un ambiente (mappa topology-based)

• Costruzione di Mappe Fuzzy LocaliMappe Fuzzy Locali• Localizzazione all’interno di una mappa topology-

based

• Costruzione dell’Orizzonte FuzzyOrizzonte Fuzzy• Obstacle avoidance


Ambienti “mappabili”

Un robot mobile spesso necessita di una mappa per costruire un percorso dallo start al goal.

Ostacolo

Percezione

MappaS

G

Per avere una vera autonomia dobbiamo assumere che nessuna conoscenza “a priori” sia disponibile e che il robot debba affidarsi completamente ai suoi sensori


Il Sensore Ultrasonico

Un “wave burst” è trasmessoe l’eco è ricevuta

La distanza è calcolata in base al tempo di volo

T

R

Spesso è usato un solo trasduttore∆t

Passaggiomancato!

Nessuna eco!Positione?


Modellazione fuzzy del sensore Ultrasonico

Quando il sensore fornisce una misura di distanza abbiamo

• una certezza di occupazione

• una certezza di vuoto

esse svaniscono• Con la distanza ρ• Con l’angolo θ dall’asse

del sensore

1

1

ρd

1

1

θMa il sensore è soggetto a false riflessioni !

ρ

ρ

∀ θ

∀ θ

∀ θ

∀ ρ


Fuzzy set dello spazio occupato

Combinando (con il prodotto - intersezione) i precedenti concetti:

d

Lobo di radiazione


Fuzzy set dello spazio vuoto

Combinando (con il prodotto - intersezione) i precedenti concetti:

d


Mappe & Fuzzy SetsPer motivi computazionali l’ambiente èdiscretizzato in celle

L’ambiente coincide con l’insieme bidimensionale di tutte le celle (U)

Vogliamo definire

•l’insieme delle celle vuote (E)

•l’insieme delle celle occupate (O)

Vogliamo anche definire una mappa di navigazione (N) che contenga tutte le informazioni utili a muoversi nell’ambiente

Nel caso ideale ogni cella dovrebbe essere vuota o occupata

(vuota = 0 = bianca, occupata = 1 = nera)

L’incertezza sensoriale produce gray-levelmaps


Approccio con i Fuzzy sets (1)

Per ogni cella, le varie misure forniscono evidenza alle due proposizioni:

• Questa cella appartiene all’insieme fuzzy delle celle vuote• Questa cella appartiene all’insieme fuzzy delle celle occupate

Mettendo in OR (unione) i risultati delle varie misure si ottiene la mappa delle delle celle vuote (E) e la mappa delle celle piene (O)

La mappa di navigazione più semplice può quindi essere ottenuta come

Naturalmente: µE(Ci) + µO(Ci) ≠ 1

N O E= ∩


Approccio con i fuzzy sets (2)

•Celle ambigue• Piene e occupate

•Celle indeterminate• Ne piene ne occupate

•Celle sicure• Quelle “molto” vuote meno le

occupate e le indeterminate

•Celle insicure• Quelle non sicure

A E O= ∩

I E O= ∩

2S E O A I= ∩ ∩ ∩

M S=


Approccio Probabilistico (1)

Inizialmente introdotto da Moravec (1988) ed Elfes (1990).Ogni cella ha solo due stati mutuamente esclusivi:s(C)=E oppure s(C)=O; P[s(C)=E] = 1- P[s(C)=O]

Il sensore è modellato da p[d|r], la densità di probabilità di una lettura d, supposto che l’ostacolo più vicino sia ad una distanza r.Le false riflessioni sonomodellate come outliers

r d



La mappa di navigazione è data da 1-P[s(C)=O] ed è ottenuta dalla applicazione sequenziale della regola di regola di BayesBayes:

P s(Ci ) = O d[ ]=P d s(Ci ) = O[ ]p s(Ci ) = O[ ]

P d s(Ci ) = O[ ]p s(Ci ) = O[ ]+ P d s(Ci ) = E[ ]p s(Ci ) = E[ ]

ma questo non è il modello del sensoreAssumendo un sensore perfetto, una singola misura afferma che

- le celle 1, 2, 3 sono vuote- la cella 4 è occupata- le celle 5, 6, ... sono indeterminate

Deve essere usato Il teorema di teorema di KolmogorovKolmogorovper reperire le probabilità condizionali necessarie.Questo costituisce un carico computazionale elevato!

1 2 3 4 5 6 celle



Il processo è avviato ipotizzando uno stato di massima entropia:

P[s(C)=E] = P[s(C)=O] = 0.5Inoltre, ogni cella è assunta indipendente da quelle adiacenti.Queste assunzioni possono produrre delle situazioni paradossali:

• C’è un ostacolo adiacente al robot con probabilità 0.5• La probabilità della esistenza di un ostacolo di una data

dimensione dipende dalla dimensione delle celle

1 2 3 4 5 6 celle

0.5 0.5 0.25

Questi effetti svaniscono con un rate pari a k/√n (Hill, Spall, SMC 2, 94)


Commenti

Vincoli

Approccio Fuzzy sets• nessuno

Approccio Probabilistico• P(E)=1-P(O)

Aggiornamento della base di conoscenza

Approccio Fuzzy logic• Qualsiasi operatore di

aggregazione

Approccio Probabilistico• Regola di Bayes


Comparazioni (Fuzzy sets vs. Probabilistico)

0

0.2

0.4

0.6

0.8

1

0 0.5 1 1.5 20

0.2

0.4

0.6

0.8

1

0 0.5 1 1.5 2

•Consideriamo solo distribuzioni radiali•Dopo 9 misure "corrette" (0.5m), c’è una false riflessione (1m).

Approccio fuzzy logic Approccio probabilistico

µ P(O)

1

1

9910

10

O EU

Dopo solo una misura, questa area risulta vuota

Questo èperso dopo un solo outlier

sconosciuto

unknown


Map by Probability


Map by Fuzzy Logic


Commenti

Approccio Probabilistico• Complesso e “time consuming”• Troppo sensibile agli outliers• Lento nella convergenza partendo da completa

ignoranza

Approccio Fuzzy sets• Ampia (troppo?) scelta di operatori• Una specie di normalizzazione dovrebbe essere

introdotta man mano che la conoscenza si accumula• Buoni risultati• Implementazione veloce


Utilizzo delle mappe Fuzzy

• Pianificazione del cammino ottimo• A*

• Analisi degli ambienti e deduzione di mappe con elementi topologici

• Morfologia matematica• Topologia digitale fuzzy

• Localizzazione• Fuzzy local map


Pianificazione del cammino con A*

• E’ possibile trovare un percorso non solo “collisioncollision freefree” ma anche “a rischio minimoa rischio minimo” che connettesse lo start con il goal

• Si possono minimizzareminimizzare:• la somma dei rischi

delle celle attraversate• Il massimo rischio

sopportato


Mappe “topology-based”Estrazione dell’informazione sulla struttura dello spazio applicando concetti di topologia generaleDescrizione dell’ambiente in termini di forma dello spazio:

spazi aperti connessi da passaggi strettiL’informazione iniziale sullo spazio libero è rappresentata da una mappa a griglia, che può essere considerata come un’ immagine

A

B

C D

A

B C D


AlgoritmoCostruzione della mappa a griglia

Trasformazione della mappa iniziale per trovare spazi aperti connessi da passaggi stretti (morfologia matematica)

Segmentazione della mappa in componenti connesse fuzzy (topologia digitale)

Costruzione del grafoA D

B EC


Morfologia matematica binariaEstrae informazioni sulla forma nell’immagine Si basa sui seguenti concetti

• Elemento strutturante ES: definisce la forma da studiare

• Filtraggio dell’immagine con l’EStraslato in tutte le locazioni

Gli operatori fondamentali sono la Dilatazionee l’Erosione

Tutte le operazioni possono essere definite a partire da un opportuno ES e da una sequenza di operatori fondamentali

D

E


Morfologia matematica: Apertura e Chiusura

Combinando dilatazione ed erosione è possibile ottenere trasformazioni più complesse

Per esempio l’operatore AperturaAperturaè definito come una Erosioneseguita da una Dilatazione con lo stesso elemento strutturante

Notiamo che l’apertura cancella i buchi bianchi più piccoli del disco


Morfologia matematica: Binaria FuzzyFuzzy gridmap I and fuzzy structural element k

In the binary case the formal definition of dilation isD(I,k)(x)=1 iff ∃ y∈ Nk(x): (µ(y) ∧ ν(y-x))

Fuzzy extension D(I,k)(x)= supy∈ N(x) min (µ(y), ν(y-x))

In the binary case the formal definition of erosion isE(I,k)(x)=1 iff ∀ y∈ Nk(x): (ν(y-x) → µ(y) )

Fuzzy extensionE(I,k)(x)= infy∈ N(x) max (µ(y), 1-ν(y-x))

We can interpret a fuzzy transformation as a stacking of binarytransformations, level by level


Morfologia matematica Fuzzy

Trovare il grado di “spaziosità”(clearance) di ogni vano può essere effettuato applicando una erosione con un elemento strutturante fuzzy

Un elemento strutturante conicofornisce la clearance usando la distanza euclidea

Un elemento strutturante piramidalesi basa sulla distanza “chessboard”


Topologia digitale: Binaria Fuzzy

La topologia digitale studia le proprietà topologiche di immagini a livelli di grigio, adattando concetti dalla topologia generale ad insiemi finitiNozioni importanti

• Intorno• Cammino• Componente connessa fuzzy• Adiacenza tra

componenti connesse


Risultati sperimentaliAmbiente interno tipo ufficioLa fuzzy gridmap è ottenuta a partire da dati sonar (Oriolo, Ulivi e Vendittelli, 1996)

A B

CD

FE G

H

I L


CommentiUso di trasformazioni morfologiche per lo studio di forma dello spazio

E’ robusto rispetto ai parametri (no thresholding)Il metodo può essere esteso al caso di differenti sensori o ambienti

Complessità computazionale: per estrarre la topologia da una mappa di (180x150) celle, sono necessari 390 ms su un Pentium2 a 450 Mhz

Direzioni correnti• Arricchire il grafo con informazione geometrica utile per la

navigazione e la localizzazione• Uso del grafo per la pianificazione di strategie di

navigazione


Usando due mappe: una Topology Based...End-

corridor(go out)

Corridor(follow)

T-junction(turn left)

Corridor(no action)

Corridor(follow)

left right

Corner(turn)

Corridor(stop)

End-corridor

(no action)

Un grafo dove i nodisono posti e gli archiconnettono due nodi se sono adiacenti nella realtàI nodi sono marcaticon

o Strategie di movimento

o Attributi (metriche approssimate o numero di porte)

Home

Gol


... e una Mappa Fuzzy Locale (FLM)

Una rappresentazione localedel modo attorno al robot• è una grid map (mappa metrica)• ma anche una mappa fuzzy

Alcuni vantaggi di una fuzzy local map• Limitato uso di memoria

(all’interno del range dei sensori)• Valutazione della affidabilità delle

misure• Consente la fusione sensoriale

(ultrasuoni, laser, visione)

Campo di visione del Robotcon sensori ad ultrasuoni


FLM

CorridoioCorridoio

Strettoia=Strettoia=CorridoioCorridoio

Incrocio a TIncrocio a T

AngoloAngolo


World Mark (WM)Una rappresentazione fuzzy dell’orizzonte intorno al robot

Dalla FLM è estratto, per ogni direzione, il massimo valore di “occupancy”Per migliorare la localizzazione il WM ècalcolato a partire dal centro di massa della FLM

e.g. : corridor

emptyempty

full full

empty


Fuzzy sets di riferimento

Corridor

CoRner

T-junction

End corridor

Open space


Primo Riconoscimento: Similitudine FuzzyUna similitudine deve soddisfare le seguenti regole:• Un oggetto deve essere simile a se stesso• Se A è simile a B allora B è simile ad A con lo stesso grado• Se A è simile a B e B è simile a C nonnon segue che A è simile a C

Per calcolare il grado di matching tra due fuzzy sets può essere usata, ad esempio, la funzione di similarità di Sokal and Michener:

sim card cardcard card card

( ) ( ) ( )( ) ( ) ( )

M LM L M L

M L M L U, =

∩ + ∩∩ + ∩ +

U insieme universaleM world markL fuzzy set di riferimento

L deve ruotare per ottenere

Il valore massimo per “sim(M,L)”


Localizzazione1. Collezione dei dati

• Sensori ad ultrasuoni• Laser e visione• FLM

2. Primo Riconoscimento• Costruzione del World mark• Fuzzy sets di riferimento (per esempio)• Valutazione della Similitudine

3. Riconoscimento combinato• Per combinare l’informazione passata con

quella corrente e con quella che può provenire da altri agenti indipendenti


Esempio: Corridor

Fuzzy map World mark

similitudine


Applicazione della Morfologia Fuzzy alle FLM


Metodi alternativi

Dal lavoro iniziale di Shafer (1976) che forniva un modello matematico per trattare e quantificare l’incertezza (belief functions+Dempster’s rule of combination) due grossi filoni:

• The upper and lower probability model• Basato sull’idea che per ogni proposizione esiste una

probabilità ma di questa si conoscono solo i limiti superiore ed inferiore (posto anche in lavori precedenti di Good, Smith e Dempster)

• The transferable belief model (TBM)• Un modello che non usa alcun concetto della

probabilità (Smets)


AssiomatizzazioneAssiomatizzazione Teoria della PossibilitTeoria della Possibilitàà

• Assiomi Costruzione di una teoria matematicaMigliore comprensione delle operazioni

• Assiomi Maggiore distanza dalle condizioni sperimentali

• L’assiomatizzazione della teoria della possibilità- si basa sulle misure fuzzy - porta ai fuzzy sets come distribuzioni di possibilità- comprende come caso particolare la probabilità


L’Universo del Discorso

Sia fissata una algebra Booleana finita di proposizioni Ω sulle quali costruiremo una serie di “belief” (giudizio di veridicità)

Alcune proposizioni saranno più “believed” di altre.

Normalmente le proposizioni non comprese in Ω sono dichiarate impossibili

In realtà per ogni possibile proposizione abbiamo 3 casi possibili:• KP known as possible• UP unknon propositions (vuoto nell’approccio Bayesiano )• KI known impossible (non finiscono in Ω)

Quindi due alternative• Closed-world UP vuoto• Open-world UP non vuoto


Quantificazione del grado di belief e TBM

Sia KP una algebra Booleana finita di proposizioni ΩSia ∆ l’insieme di proposizioni elementari appartenenti ad ΩNormalmente Ω è il power set di ∆

Supponiamo di avere una evidenza che ci induca a supporre vera alcune proposizioni A di Ω: postuliamo allora che esista una quantità di belief complessivo (una massa normalizzata ad 1) che possa essere distribuita tra le varie proposizioni A

La massa m(A) che viene allocata alla proposizione A è chiamata basic belief mass e definisce una funzione detta basic beliefassignement:

m: Ω [0,1]


Le proposizioni possono essere esiti di una Le proposizioni possono essere esiti di una misuramisura

• Se conoscessimo le probabilità dei singoli eventi elementariavremmo la minima incertezza (eventi dissonanti), Ma solo ∆ èvisibile.

• Le letture possibili non sono necessariamente disgiunte, - lo stesso evento può produrre misure diverse, - noi non siamo in grado di mettere in relazione certa eventi e misure (incertezza)

A BC∆ :A,B,C

U: ui=

Spazio delle Misure

Eventi Elementari:Singletons


Basic belief assignement

Abbiamo definito la funzione detta basic belief assignement:

m: Ω [0,1]

Per questa vale

Dove la somma è fatta su tutte le proposizioni A di Ω che supportino la tautologia 1Ω (la disgiunzione di tutti gli elementi di ∆)

Il modello di Shafer include il seguente requisito:

m(0Ω)=0 (massa dell’insieme vuoto)

che, secondo Smets, conduce a dei risultati non soddisfacenti nel momento in cui si fa l’ipotesi di Open-world e quindi la rimuove nel TBM

1( ) 1

Am A

Ω→

=∑


Definizione di Belief e Plausability

Il grado di belief dato alla proposizione A di Ω è quantificato dalla funzione di belief

bel:Ω [0,1]con

Il grado di plausability dato ad una proposizione è definito, invece,

0

( ) ( )

(0 ) 0

B AB

bel A m B

belΩ

→≠

Ω

=

=

∑

( ) ( ) (1 ) ( )B A

pl A m B bel bel AΩ→ ¬

= = − ¬∑


Misure fuzzy e Misure fuzzy e beliefbelief

: P( ) [0,1]g ∆ →Una funzione è una misura fuzzy (FM) se:∆, non Ω !

( ) 0 ( ) 1g g∅ = ∆ =Condizioni al contorno:

, P( ), ( ) ( )A B A B g A g B∀ ∈ ∆ ⊆ ⇒ ≤Monotonicità

g(A∪B) ≥ max g(A),g(B)[ ]g(A∩B) ≤ min g(A),g(B)[ ]

n.b. “+” > “max”“*” < “min”

Continuità (si applica se Ω ha infiniti elementi, molto tecnica)

Warnings: gli insiemi sono crispstiamo completamente abbandonando l’idea di frequenzaovvero di probabilità a posteriori.


BeliefBelief e e PlausibilityPlausibility

• All’incirca: Belief è la minima certezza supportata dai fattiPlausibility è la massima certezza che non contrasta coi fatti

• Assiomi per Shafer e conseguenze per Smets (versione per 2 insiemi)

• Commento: Se gli insiemi sono disgiunti la prima assomiglia alla probabilità

• Altre proprietà:

( ) ( ) ( ) ( )( ) ( ) ( ) ( )

bel A B bel A bel B bel A Bpl A B pl A pl B pl A B

∪ ≥ + − ∩∩ ≥ + − ∪

( ) ( ) 1; ( ) ( ) 1( ) 1 ( ); ( ) 1 ( )

bel A bel A pl A pl Apl A bel A bel A pl A

+ ¬ ≤ + ¬ ≥= − ¬ = − ¬


Misure di probabilitMisure di probabilitàà

• Rafforzando la condizione sull’unione,

si arriva alla probabilità convenzionale.

• Theo: una misura bel su Ω è una misura di probabilità ssel’assegnazione dei valori è fatta sui singletons ui, e su tutti gli altri (unioni di singletons) è nulla (dati dissonanti).

• bel e P coincidono, infatti:

essendo p(u) una distribuzione di probabilità (perché la somma su ∆ è 1)

• In generale, invece,

P(A ∪B) = P(A) + P(B) iff A ∩B = ∅

( ) ( ) ( ) ( )i

iu A

P A p u Pl A Bel A∈

= = =∑

( ) P( ) ( )bel A A pl A≤ ≤


Combinazione dei belief

Supponiamo di avere due belief function bel1 e bel2 indotte da due distinte evidenzeCome si definisce la belief function che combina le due precedenti?

bel12=bel1⊕bel2Dempster’s rule of combination

Per Shafer, che postula m(0Ω)=0, bisogna introdurre un fattore di normalizzazione e dividere per un fattore

1,2 1 2( ) ( ) ( )X Y A

m A m X m Y∩ =

= ⋅∑

1,2 1 21 (0 ) 1 ( ) ( )X Y

m m X m YΩ∩ =∅

− = − ⋅∑


TransferableTransferable BeliefBelief Model (Model (SmetsSmets and and KennesKennes))

Combine past and current information coming from fuzzy similarity

Add robustness w.r.t. disturbancies due toMultiple reflectionsUnexpected obstacles (furniture, walking people)

Definition of the Universal set∆=Corridor, coRner, T-junction, End-corridor, Open-space

Definition of the set of all the possible events (atomic or not) on wich a Boolean Algebra R is defined

Ω = Power(∆) = CR T E O ... CRTEO(Ω R): propositional space


Transferable Belief Model (Smets and Kennes)

Credal levelLet’s consider an agent T giving a belief about the “true” universe

A basic mass assignement m(F) specifies how the belief of anagent T supports the event F member of Ω

In our case the agent T is the static recongnition stage

Many possible BMAs! E.g.:Each similarity supports with its value the atomic event L and withits negate both the complementary and the unknow events:

sim(L) L(1-sim(L))/2 not L(1-sim(L))/2 CRTEO


Basic Mass Assignment

Alternatively:• The higher similarity

level supports the associated atomicelement as far asthe second level

supports C

supportsunknown


Transfer of Belief and Pignistic level

To update the past BMA mk-1(F) and combine it with the new BMA mk(F) we use the Smets rule of combination:

o “The product of two bbm m1(X) e m2(Y) coming from two distinctagents supports X∩Y”

m A m X YX Y A

12 1( ) ( )= ⋅∩ =∑ ( ) m 2

The probability function BetP, used to make decisions, can be writtenas

o A possible approach is to equally distribute the mass of event A among its atoms:

BetP ( )( ):

x m AAA A x

=∩ ≠

∑0


Determinazione della Determinazione della ““possibilepossibile”” featurefeature tramite il TBMtramite il TBM

Calcolo delle “basic belief masses” per le credibilità degli eventi atomici e non atomici

Integrazione dei belief con i valori precedenti (per filtrare eventuali errori e per avere un passaggio più dolce)

Calcolo valori di scommessa BetP solo per gli eventi atomici A (distribuendo le masse)


Navigazione


Evitare gli ostacoli

• Obstacle Avoidance is essential for a mobile robot in anunstructured environment

• OA modifies desired heading and speed on the basis of obstacle perception to reduce risks

• A tradoff is neededbetween high reactivity and smooth behavior, soadd some local memory

• Implementation must be very efficient, soavoid rules based systems

• As no planning is involved and OA is local, use an egocentric representation


Semplice modello cinematico

cos( )sin( )

x uy u

ϑϑ

ϑ ω

=⎧⎪ =⎨⎪ =⎩

x

y

θθ

O

• Modello tempo continuo dell’uniciclo

x

y

θθ

O


Comportamento di “Obstacle Avoidance”Usiamo dei sensori ad ultrasuoni

5 “wide beam” range finders con un cono di radiazione di circa 70°• Grandi spazi con un numero di sensori ridotto• Elevata incertezza nella collocazione degli ostacoli• Riflessioni multiple

Tecnica basata sulla Fuzzy logic: “Metodo degli Orizzonti”• Input:

• Direzione di navigazione desiderata θdes e velocità desiderata vdes

• Letture sonar• Informazioni odometriche fornite dagli encoder montati sugli assi dei motori

• Output:• Direzione di navigazione di riferimento θref e velocità vref che garantiscano

una navigazione priva di collisioni nella direzione più vicina possibile a quella desiderata


Orizzonti Fuzzy

• Gli Orizzonti Fuzzysono fuzzy setsdefiniti su 360°

• Possono essere usati per rappresentare differenti caratteristichedell’ambiente intorno al robot

0° 360°Esempio: il rischio di

prendere una direzione!


Quali caratteristiche?

Per ogni direzione è possibile valutare le seguenti quantità:• Compatibilità con la direzione desiderata• Rischio di collisione• Compatibilità con i vincoli cinematici del robot

Queste definiscono le funzioni di appartenenza di un fuzzy set chiamato “orizzonte”L’algoritmo inizia con la valutazione, ad oggni passo, dei tre orizzonti:

• attrattivo A• repulsivo R• cinematico K

Combinando questi tre si può valutare il costo del movimento in ogni direzione e calcolare un nuovo orizzonte D


Orizzonti Attrattivo e Cinematico• Orizzonte Attrattivo

• Un fuzzy set triangolare centrato nella direzione di movimento desiderata

• La larghezza è“proporzionale” alla libertà di scelta.

• Orizzonte Cinematico• Molto simile ma

centrato nella direzione attuale di moto

• Rende i cambi di direzione meno accettabili

0° 360°


Orizzonte Repulsivo

Stessa misura di distanza Nessuna eco

• I sensori hanno una scarsa risoluzione angolare

• Possono addirittura mancare un ostacolo

30°

• Il rischio indotto da un ostacolo ad una distanza d è modellato da un FS triangolare con una altezza pari a min(1,k/d)

• I rischi sono fusi (messi in OR) attraverso l’operatore di “Bounded Sum” in un unico fuzzy set


Orizzonte repulsivo in un caso reale

-400

-300

-200

-100

0

100

200

300

400

Dopo 4 -400

-300

-200

-100

0

100

200

300

400

Dopo 8 misremisure

Verde: proiezioni degli ostacoli Rosso: l’orizzonte di rischio

L’ostacolo è di fronte a destra Rimane un passaggio sufficiente a sinistra


Metodo degli Orizzonti

vref è invece calcolata come

θref è calcolata minimizzando D, la funzione di appartenenza calcolata come

v vD

Dref desref

th

= −RST

UVWmax , (

( ))0 1

θD A R K( ) ( ) ( ) ( )θ θ θ θ= ∪ ∪

D

A

R

180

1

θref-180


Aggiungendo un po’ di memoria…• Le letture sensoriali possono cambiare enormemente

durante il movimento del robot a causa del largo cono di radiazione

• Come conseguenza, il percorso del robot può essere “vagabondante”

• Ricordare un certo numero di letture passate riduce questo fenomeno, ma rende l’OA più lenta nella reazione

• Le vecchie letture sono pesate con la loro età: più vecchie, meno attendibili

• Le misure più vecchie devono essere rimappatesull’orizzonte attuale tenendo conto anche del movimento del robot


Modulo di Obstacle Avoidance

Seminario di logica Fuzzy

Documents

Transcript of Seminario di logica Fuzzy