Appunti di Multiagent Systems

Multiagent Systems

2023-2024

Indice

1 AGENTI INTELLIGENTI 2

1.1 Modello di un agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Sistemi multi-agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Paradigmi per creare agenti intelligenti . . . . . . . . . . . . . . . . . . . 11

1.4 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 ROBOT MOTION PLANNING 15

2.1 Soluzioni planning-based . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.1 Approcci geometrici . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1.2 Decomposizione in celle . . . . . . . . . . . . . . . . . . . . . . . 20

2.1.3 Campionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1.4 Semplificazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Algoritmi Bug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.1 Bug 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.2 Bug 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2.3 Bug 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2.4 Confronto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2.5 Tangent Bug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3 Artificial Potential Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.1 Dinamica a singolo integratore . . . . . . . . . . . . . . . . . . . 34

2.3.2 Convergenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 TEORIA DEI GRAFI 41

3.1 Grafi indiretti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2 Connettività di un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3 Laplaciano di un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.3.1 Spettro del Laplaciano . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4 Connettività algebrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.5 Partizione di un grafo e Clustering spettrale . . . . . . . . . . . . . . . . 63

3.5.1 Partizionamento spettrale . . . . . . . . . . . . . . . . . . . . . . 70

4 COORDINAMENTO NEI SISTEMI MULTIAGENTE 75

4.1 Consenso a tempo continuo . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.2 Consenso a tempo discreto . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4.3 Consenso nei grafi diretti . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.4 Coordinamento di un sistema multi-agente . . . . . . . . . . . . . . . . . 104

i

INDICE 1

5 SISTEMI MULTI-ROBOT 108

5.1 Controllo della formazione . . . . . . . . . . . . . . . . . . . . . . . . . . 109

5.2 Coordinamento dei robot . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.2.1 Mantenimento della connettività . . . . . . . . . . . . . . . . . . 114

5.2.2 Evitamento delle collisioni . . . . . . . . . . . . . . . . . . . . . . 116

5.3 Flocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5.4 Copertura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

5.5 Esplorazione e Mappatura . . . . . . . . . . . . . . . . . . . . . . . . . . 122

5.5.1 Griglia di occupazione . . . . . . . . . . . . . . . . . . . . . . . . 123

5.5.2 Mappa basata sulle features . . . . . . . . . . . . . . . . . . . . . 127

5.5.3 Mappa point-cloud . . . . . . . . . . . . . . . . . . . . . . . . . . 131

5.5.4 SLAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

5.5.5 Mappe simboliche . . . . . . . . . . . . . . . . . . . . . . . . . . 135

5.5.6 Esplorazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

6 OTTIMIZZAZIONE E ADDESTRAMENTO MULTI-AGENTE 140

6.1 Addestramento distribuito . . . . . . . . . . . . . . . . . . . . . . . . . . 146

6.2 Consenso per l’ottimizzazione e l’apprendimento distribuito . . . . . . . . 152

6.3 Fusione di informazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

6.3.1 Fusione di informazioni distribuite . . . . . . . . . . . . . . . . . 158

7 REINFORCEMENT LEARNING 161

7.1 Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

7.2 Programmazione dinamica stocastica . . . . . . . . . . . . . . . . . . . . 169

7.2.1 Value iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

7.2.2 Policy iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

7.3 Valutazione delle politiche senza modelli . . . . . . . . . . . . . . . . . . 191

7.3.1 Monte Carlo policy evalutaion . . . . . . . . . . . . . . . . . . . . 192

7.3.2 Apprendimento Temporal Difference . . . . . . . . . . . . . . . . 193

7.4 Q-Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7.4.1 Q-Learning con funzioni di approssimazione . . . . . . . . . . . . 201

7.5 Reinforcement Learning multi-agente . . . . . . . . . . . . . . . . . . . . 204

7.5.1 Global Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

7.5.2 Indipendent Learning . . . . . . . . . . . . . . . . . . . . . . . . 206

Capitolo 1

AGENTI INTELLIGENTI

1.1 Modello di un agente

agente

Un rappresenta un’entità capace di interagire con l’ambiente. Questa interazio-

ne avviene mediante la ricezione di dati o informazioni provenienti da esso (ad esem-

pio, utilizzando sensori) e l’esecuzione di azioni sull’ambiente (ad esempio, mediante

attuatori). fisica

Un agente può essere classificato come un’entità (ad esempio, un essere uma-

virtuale

no, un animale, un robot, un veicolo autonomo, ecc...) oppure un’entità (ad

esempio, un software).

Possiamo modellare l’interazione tra un agente e l’ambiente in cui esso si trova secondo

la seguente relazione: + 1) = (x(t),

x(t f u(t))

dove:

• rappresenta un indice temporale (ovvero, indica come varia lo stato nel tempo).

t stato

• rappresenta lo al tempo con (l’insieme è

∈

= (x (t), (t))

x(t) x t, x(t) X X

a e

spazio degli stati).

detto

In particolare:

– stato configurazione)

rappresenta lo (o dell’agente al tempo

(t)

x t.

a

– stato configurazione)

rappresenta lo (o dell’ambiente al tempo

(t)

x t.

e

• rappresenta l’azione dell’agente al tempo con (l’insieme è detto

∈

u(t) t, u(t) U U

spazio delle azioni).

• rappresenta una funzione che indica come viene modificato lo stato.

f

N.B: l’azione effettuata dall’agente può modificare gli stati sia dell’ambiente che

u(t)

dell’agente stesso.

N.B: gli insiemi ed possono assumere una natura (tipica nella teoria del

continua

X U

controllo), (comune nell’intelligenza artificiale) oppure (ad esempio, nella

discreta ibrida

2

CAPITOLO 1. AGENTI INTELLIGENTI 3

guida autonoma, dove lo spazio delle azioni può essere continuo, come lo sterzo e l’ac-

celerazione, e discreto, come la selezione delle marce). Di conseguenza, lo stesso agente

può essere modellato in modo continuo o discreto, a seconda delle circostanze.

ES (modello continuo di un robot mobile):

Rappresentiamo il modello dei movimenti di base per un robot mobile nel

seguente modo: + 1) = +

x(t x(t) T u(t)

s

dove:

• rappresenta il tempo di campionamento.

T

s

• rappresenta la posizione del robot al tempo In questo caso:

x(t) t.

– se il robot si muove su un piano 2D.

2

∈

x R

– se il robot si muove su uno spazio 3D.

3

∈

x R

• rappresenta il vettore velocità (il robot può muoversi verso

u(t)

infinite direzioni).

ES (modello discreto di un robot mobile):

Per la navigazione, a volte è utile discretizzare la mappa con una griglia.

In questo caso:

• rappresenta la cella occupata dal robot al tempo

x(t) t.

• rappresenta la direzione del movimento. Di conseguenza, lo spazio

u(t)

delle possibili azioni sarà:

U

{(0, −1), −1), −1)}

= 0), (1, 0), (0, 1), (−1, 0), (0, (1, 1), (1, (−1, 1), (−1,

U

N.B: a seconda della mappa e della posizione del robot, alcune azioni

non sono consentite (ad esempio, se il robot è nelle vicinanze di un

ostacolo con cui può collidere).

CAPITOLO 1. AGENTI INTELLIGENTI 4

intelligente

Un agente può essere definito quando soddisfa le seguenti caratteristiche:

Autonomia:

• gli agenti operano in maniera indipendente, senza la necessità di

un controllo diretto da parte di altre entità, avendo il controllo completo sulle

proprie azioni e decisioni (ovvero, deve comportarsi in modo autonomo, senza la

necessità di controlli esterni).

Orientato all’obiettivo goal-oriented):

• (o gli agenti agiscono in modo da

raggiungere un obiettivo specifico, mirando a conseguire risultati desiderati.

Capacità di apprendimento:

• gli agenti sono in grado di trarre insegnamenti

dall’esperienza passata, cioè dalla raccolta e dall’analisi dei dati, migliorando così

le loro performance nel tempo.

Un agente intelligente prende decisioni riguardo alle sue azioni basandosi sull’obiettivo

da perseguire e sulle informazioni di cui dispone.

Dato un orizzonte temporale (finito o infinito), gli obiettivi dell’agente possono essere

T

definiti in termini di: configurazioni desiderate,

• Un insieme di che rappresentano gli sta-

⊂

X X

G

ti attesi per l’agente (ad esempio, la posizione finale che l’agente intende rag-

giungere). In questo contesto, lo stato deve entrare nell’insieme entro

x(t) X G

un orizzonte temporale (finito o infinito):

T

– Se l’orizzonte temporale è finito, allora lo stato deve trovarsi in una

)

T x(T

configurazione desiderata al tempo . Ovvero:

X T

G ∈

)

x(T X G

– Se l’orizzonte temporale è infinito, allora lo stato deve convergere

T x(t)

verso l’insieme all’avanzare del tempo Ovvero:

X t.

G per

−→ −→ ∞

x(t) X t

G

configurazioni ammissibili,

• Un insieme di che rappresentano gli sta-

⊂

X X

A

ti consentiti per l’agente (ad esempio, l’agente può essere posizionato solo nelle

caselle consentite). In questo contesto, assumendo che lo stato iniziale sia ammis-

sibile (cioè ), il requisito è che lo stato rimanga ammissibile per

∈

x(0) X x(t)

A

qualsiasi istante temporale Ovvero:

t. per ogni

∈ ≥ 0

x(t) X t

A

funzione di ricompensa reward function)

• Una (o da massimizzare oppure,

R

funzione di costo cost function)

equivalentemente, una (o da minimizzare.

J

In particolare, definiamo:

– Ricompensa istantanea instantaneous reward)

(o al tempo ad ogni

t:

istante temporale un agente riceve una ricompensa sulla base dello stato

t,

in cui si trova e dell’azione che esso compie. Ovvero:

x(t) u(t)

r(t, x(t), u(t))

CAPITOLO 1. AGENTI INTELLIGENTI 5

– Ricompensa totale ritorno utilità):

(anche detta o rappresenta la som-

ma di tutte le ricompense ottenute ad ogni istante fino all’orizzonte tempo-

t

rale . Ovvero:

T T

X

=

R r(t, x(t), u(t))

t=0

N.B: total reward)

la ricompensa totale (o dipende dallo stato iniziale

e dalla sequenza di decisioni − 1).

x(0) u(0), u(1), ..., u(T

N.B: possiamo sempre trasformare un problema di massimo in un problema di

minimo.

Figura 1.1: La figura illustra il contesto in cui un agente, con stato iniziale ammissibile (ovvero

x(0)

), deve essere guidato verso uno stato desiderato (ovvero ) senza mai uscire dall’insie-

∈ ∈

x(0) X x X

A G

me delle configurazioni ammissibili .

X

A

Per affrontare il problema di decisione sequenziale, è possibile adottare due approcci

distinti:

• (o In questo approccio, si

Approccio basato sulla pianificazione planning-based).

pianificano in anticipo le azioni che l’agente deve intraprendere sull’ambiente per

modificare lo stato e raggiungere l’obiettivo desiderato. Quindi, si vuole trovare la

migliore sequenza di decisioni che permette di raggiungere l’obiettivo desiderato,

massimizzando la performance. Ovvero: − 1)

u(0), u(1), ..., u(T

Questo approccio richiede una conoscenza completa dell’ambiente. Quindi, non è

adatto nel caso in cui le condizioni ambientali risultano essere incerte, poiché non

è possibile pianificare con certezza le azioni da intraprendere.

• (o In questo approccio, le decisioni

Approccio basato su una politica policy-based).

vengono prese in tempo reale, adattandosi dinamicamente all’ambiente e alle in-

formazioni disponibili. Quindi, si vuole trovare la migliore politica di decisione γ

al tempo massimizzando la performance. Ovvero:

t, =

u(t) γ(t, x(t))

Questo approccio consente di adattarsi a situazioni incerte, ad esempio quando le

conoscenze sull’ambiente sono parziali o si verificano eventi imprevisti. In questo

contesto, l’obiettivo principale è quello di elaborare una politica decisionale che

γ

consenta all’agente di raggiungere i suoi obiettivi in modo efficace.

CAPITOLO 1. AGENTI INTELLIGENTI 6

In molti casi, le transizioni dal tempo al tempo non sono deterministiche. In altre

t t+1

parole, l’esito delle azioni intraprese al tempo è incerto e non sempre porta allo stato

t

previsto. In tali circostanze, è possibile modellare una transizione probabilistica

+ 1)

x(t densità di Markov

attraverso la che quantifica la probabilità di transitare dallo

φ,

stato allo stato quando viene effettuata l’azione Ovvero:

+ 1)

x(t) x(t u(t).

|

+ 1)

φ(x(t x(t), u(t))

ritorno atteso expected return)

In questo contesto, possiamo definire il (o conside-

rando le transizioni incerte: T

" #

X

=

R r(t, x(t), u(t))

E r=0

Markov Decision Process

Il modello risultante prende il nome di (MDP).

ES (Tetris):

Consideriamo il gioco del Tetris come caso di studio:

• lo stato è rappresentato da tra componenti:

Stato:

– La configurazione attuale del tabellone, che indica come è disposta la

griglia al tempo t.

– Il pezzo corrente che deve essere posizionato, specificando sia la sua

forma che il suo orientamento.

– Il pezzo successivo che verrà fornito al giocatore, importante per la

pianificazione di strategie future.

• le azioni che possiamo intraprendere comprendono la scelta

Azione:

dell’orientamento del pezzo corrente e la colonna in cui inserirlo.

• lo stato dell’azione non è deterministico (o Markoviano), poiché il

Stato:

pezzo successivo può essere scelto tra possibili opzioni. Di conseguenza, la

7

configurazione non può essere pianificata per raggiungere l’obiettivo.

Pertanto, è necessario progettare una politica decisionale che guidi le scelte

basate sulla conoscenza della configurazione al tempo t.

• il gioco termina quando il tabellone si riempe fino alla cima.

Obiettivo:

• la ricompensa è determinata dal punteggio associato alla

Ricompensa:

configurazione ottenuta dopo aver posizionato il pezzo.

CAPITOLO 1. AGENTI INTELLIGENTI 7

Quando non è possibile ottenere una conoscenza completa dell’ambiente in anticipo, di-

venta fondamentale effettuare delle osservazioni (ad esempio, mediante l’utilizzo di sen-

sori) per acquisire informazioni rilevanti. In questo modo, le decisioni prese dall’agente

si basano sulle osservazioni effettuate al tempo t.

modello di osservazione obser-

In questo contesto, introduciamo il concetto di (o

vation model) che ci permette di modellare le informazioni catturate dall’agente al

tempo Questo modello può essere rappresentato come:

t. =

y(t) h(x(t))

In particolare, possiamo definire:

Informazione completa,

• se l’agente è in grado di osservare tutti gli aspetti

dello stato al tempo (ovvero =

t y(t) x(t)).

Informazione parziale,

• se solo una parte dello stato può essere osservata (ovve-

ro è una rappresentazione incompleta dello stato effettivo).

y(t)

N.B: l’osservazione può dipendere dall’azione intrapresa dall’agente all’istan-

∈

y(t) Y

te (ovvero Inoltre, lo spazio delle osservazioni può essere continuo,

− −

1 1)).

t u(t Y

discreto oppure ibrido.

Le decisioni sono basate su un vettore informativo che memorizza tutte le osservazioni

effettuate e le azioni intraprese in ogni istante temporale. A questo scopo, definiamo il

vettore informativo information vector)

(o che riassume tutte le informazioni

I(t),

raccolte fino al tempo t:  

y(0)

u(0)

 

 

 

y(1)

 

..

=

I(t)  

.

 

 

 

− 1)

u(t

 

 

y(t)

In altre parole, l’agente utilizza il vettore informativo per prendere decisioni sulle azioni

da intraprendere in modo da massimizzare la sua performance nel contesto dell’ambien-

te osservato. Ovvero: =

u(t) γ(t, I(t))

N.B: nel caso di un’informazione completa, dove di solito lo stato

=

y(t) x(t), x(t)

riassume già tutte le informazioni storiche. Pertanto, possiamo semplificare il vettore

informativo come =

I(t) x(t).

ES (Poker):

Per illustrare i concetti precedentemente discussi, consideriamo il gioco di

carte del Poker come caso di studio. Nel Poker, ciascun giocatore ha una

mano di carte che è nascosta agli avve