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 evaluation . . . . . . . . . . . . . . . . . . . . 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

Un agente rappresenta un’entità capace di interagire con l’ambiente. Questa interazione avviene mediante la ricezione di dati o informazioni provenienti da esso (ad esempio, utilizzando sensori) e l’esecuzione di azioni sull’ambiente (ad esempio, mediante attuatori).

Un agente può essere classificato come un’entità fisica (ad esempio, un essere umano, un animale, un robot, un veicolo autonomo, ecc...) oppure un’entità virtuale (ad esempio, un software).

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

x(t + 1) = f(x(t), u(t))

dove:

• t rappresenta un indice temporale (ovvero, indica come varia lo stato nel tempo).
• x(t) rappresenta lo stato al tempo t, con x(t) ∈ X = (xa(t), xe(t)) e l’insieme X è detto spazio degli stati.

In particolare:

• xa(t) rappresenta lo stato (o configurazione) dell’agente al tempo t.
• xe(t) rappresenta lo stato (o configurazione) dell’ambiente al tempo t.

• u(t) rappresenta l’azione dell’agente al tempo t, con u(t) ∈ U e l’insieme U è detto spazio delle azioni.
• f rappresenta una funzione che indica come viene modificato lo stato.

N.B: l’azione u(t) effettuata dall’agente può modificare gli stati sia dell’ambiente che dell’agente stesso.

N.B: gli insiemi X ed U possono assumere una natura continua (tipica nella teoria del controllo), discreta (comune nell’intelligenza artificiale) oppure ibrida (ad esempio, nella guida autonoma, dove lo spazio delle azioni può essere continuo, come lo sterzo e l’accelerazione, e discreto, come la selezione delle marce). Di conseguenza, lo stesso agente può essere modellato in modo continuo o discreto, a seconda delle circostanze.

2 Capitolo 1. Agenti intelligenti 3

ES (modello continuo di un robot mobile): Rappresentiamo il modello dei movimenti di base per un robot mobile nel seguente modo:

x(t + 1) = x(t) + Ts u(t)

dove:

• Ts rappresenta il tempo di campionamento.
• x(t) rappresenta la posizione del robot al tempo t. In questo caso:

• x ∈ R2 se il robot si muove su un piano 2D.
• x ∈ R3 se il robot si muove su uno spazio 3D.

• u(t) rappresenta il vettore velocità (il robot può muoversi verso infinite direzioni).

ES (modello discreto di un robot mobile): Per la navigazione, a volte è utile discretizzare la mappa con una griglia.

In questo caso:

• x(t) rappresenta la cella occupata dal robot al tempo t.
• u(t) rappresenta la direzione del movimento. Di conseguenza, lo spazio delle possibili azioni sarà:

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

N.B: a seconda della mappa e della posizione del robot, alcune azioni non sono consentite (ad esempio, se il robot è nelle vicinanze di uno ostacolo con cui può collidere).

Capitolo 1. Agenti intelligenti 4

Un agente può essere definito intelligente 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 (o goal-oriented): 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 T (finito o infinito), gli obiettivi dell’agente possono essere definiti in termini di:

• Un insieme di configurazioni desiderate, XG ⊂ X, che rappresentano gli stati attesi per l’agente (ad esempio, la posizione finale che l’agente intende raggiungere). In questo contesto, lo stato x(t) deve entrare nell’insieme XG entro un orizzonte temporale T (finito o infinito):

• Se l’orizzonte temporale T è finito, allora lo stato x(T) deve trovarsi in una configurazione desiderata al tempo T. Ovvero: x(T) ∈ XG
• Se l’orizzonte temporale T è infinito, allora lo stato x(t) deve convergere verso l’insieme XG all’avanzare del tempo t. Ovvero: x(t) −→ XG per t −→ ∞

• Un insieme di configurazioni ammissibili, XA ⊂ X, che rappresentano gli stati consentiti per l’agente (ad esempio, l’agente può essere posizionato solo nelle caselle consentite). In questo contesto, assumendo che lo stato iniziale sia ammissibile (cioè x(0) ∈ XA), il requisito è che lo stato x(t) rimanga ammissibile per qualsiasi istante temporale t. Ovvero: x(t) ∈ XA per ogni t ≥ 0
• Una funzione di ricompensa (o reward function) R da massimizzare oppure, equivalentemente, una funzione di costo (o cost function) J da minimizzare.

In particolare, definiamo:

• Ricompensa istantanea (o instantaneous reward) al tempo t: ad ogni istante temporale t, un agente riceve una ricompensa sulla base dello stato x(t) in cui si trova e dell’azione u(t) che esso compie. Ovvero:

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

Capitolo 1. Agenti intelligenti 5

• Ricompensa totale (anche detta ritorno o utilità): rappresenta la somma di tutte le ricompense ottenute ad ogni istante fino all’orizzonte temporale T. Ovvero:

R = ∑_t=0^T r(t, x(t), u(t))

N.B: la ricompensa totale (o total reward) dipende dallo stato iniziale x(0) e dalla sequenza di decisioni u(0), u(1), ..., u(T − 1).

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 x(0) (ovvero x(0) ∈ XA), deve essere guidato verso uno stato desiderato x (ovvero x ∈ XG) senza mai uscire dall’insieme delle configurazioni ammissibili XA.

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

• Approccio basato sulla pianificazione (o planning-based). In questo approccio, si 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: u(0), u(1), ..., u(T − 1)

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.

• Approccio basato su una politica (o policy-based). In questo approccio, le decisioni vengono prese in tempo reale, adattandosi dinamicamente all’ambiente e alle informazioni disponibili. Quindi, si vuole trovare la migliore politica di decisione γ al tempo t, massimizzando la performance. Ovvero:

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 t al tempo t + 1 non sono deterministiche. In altre parole, l’esito delle azioni intraprese al tempo t è incerto e non sempre porta allo stato previsto. In tali circostanze, è possibile modellare una transizione probabilistica x(t + 1) attraverso la densità di Markov φ, che quantifica la probabilità di transitare dallo stato x(t) allo stato x(t + 1) quando viene effettuata l’azione u(t). Ovvero:

φ(x(t + 1) | x(t), u(t))

In questo contesto, possiamo definire il ritorno atteso (o expected return) considerando le transizioni incerte:

R = E [∑_t=0^T r(t, x(t), u(t))]

Il modello risultante prende il nome di Markov Decision Process (MDP).

ES (Tetris): Consideriamo il gioco del Tetris come caso di studio:

• Stato: lo stato è rappresentato da tre componenti:

• 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.

• Azione: le azioni che possiamo intraprendere comprendono la scelta dell’orientamento del pezzo corrente e la colonna in cui inserirlo.
• Stato: lo stato dell’azione non è deterministico (o Markoviano), poiché il pezzo successivo può essere scelto tra 7 possibili opzioni. Di conseguenza, la 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.
• Obiettivo: il gioco termina quando il tabellone si riempie fino alla cima.
• Ricompensa: la ricompensa è determinata dal punteggio associato alla configurazione ottenuta dopo aver posizionato il pezzo.

Capitolo 1. Agenti intelligenti 7

Quando non è possibile ottenere una conoscenza completa dell’ambiente in anticipo, diventa fondamentale effettuare delle osservazioni (ad esempio, mediante l’utilizzo di sensori) per acquisire informazioni rilevanti. In questo modo, le decisioni prese dall’agente si basano sulle osservazioni effettuate al tempo t.

In questo contesto, introduciamo il concetto di modello di osservazione (o observation model) che ci permette di modellare le informazioni catturate dall’agente al tempo t. Questo modello può essere rappresentato come:

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 t (ovvero y(t) = x(t)).
• Informazione parziale, se solo una parte dello stato può essere osservata (ovvero y(t) è una rappresentazione incompleta dello stato effettivo).

N.B: l’osservazione y(t) ∈ Y può dipendere dall’azione intrapresa dall’agente all’istante t − 1 (ovvero u(t − 1)). Inoltre, lo spazio delle osservazioni Y può essere continuo, 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 (o information vector) I(t), che riassume tutte le informazioni raccolte fino al tempo t:

I(t) = [y(0), u(0), y(1), ..., u(t − 1), 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’ambiente osservato. Ovvero:

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

N.B: nel caso di un’informazione completa, dove di solito y(t) = x(t), lo stato 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