I sistemi multiagente nell’ambito dell’intelligenza artificiale cominciano a profilarsi come soluzione a un problema sempre più comune.
Sappiamo che l’intelligenza artificiale (IA) si diffonde sempre più, in moltissimi ambiti applicativi, dagli assistenti virtuali alle automobili autonome.
Inizia quindi a diventare rilevante la questione di come affrontare e, possibilmente, governare situazioni in cui diversi sistemi di IA si trovano ad operare nello stesso ambiente.
Il problema dei tanti sistemi di AI che vivono assieme
I contesti in cui questa questione è rilevante (o lo sarà a breve) sono numerosi e comprendono, per esempio, il trading autonomo (o algoritmico), dove diversi sistemi computazionali indipendenti, tipicamente operanti per conto di organizzazioni diverse, effettuano ordini decidendo autonomamente i volumi da acquistare o vendere all’interno di un certo mercato; le automobili autonome che, per conto di utenti diversi, percorrono le stesse strade per raggiungere le proprie destinazioni in modo sicuro ed efficiente; e i robot autonomi impiegati nella logistica per la movimentazione di merci che operano all’interno di un magazzino, in ultima analisi per migliorare il profitto dell’azienda che li impiega.
Dal punto di vista della progettazione e realizzazione dei sistemi di IA, la soluzione più semplice, ma anche la più inefficiente, sarebbe lasciare le interazioni fra i questi sistemi non coordinate e non governate, con ovvie conseguenze sulla affidabilità e sulle prestazioni. Si pensi, per esempio, alle inefficienze di una automobile autonoma che non consideri le altre automobili autonome come entità indipendenti, ma semplicemente come ostacoli da evitare. In molte situazioni l’automobile potrebbe rimanere ferma a debita distanza dalle altre automobili per evitare di avvicinarsi troppo a quelli che considera come ostacoli, perdendo la possibilità di effettuare movimenti sulla base del comportamento atteso delle altre automobili, che può essere determinato solo riconoscendole come entità autonome dotate di certe capacità, con obiettivi da raggiungere e sottostanti a limitazioni relative al codice della strada.
I sistemi multiagente, cosa sono
Forme di coordinamento fra sistemi di IA operanti in uno stesso ambiente appaiono quindi necessarie. Questo è l’obiettivo dell’area di ricerca che, nell’ambito dell’IA, studia i cosiddetti sistemi multiagente [3,4]. L’astrazione che si usa per rendere lo studio indipendente dagli specifici contesti applicativi considera i sistemi di IA come agenti autonomi che agiscono in un ambiente prendendo delle decisioni su cosa fare sulla base delle informazioni raccolte dall’ambiente e comunicate dagli altri agenti. Si noti che gli ambienti possono essere sia fisici, come nel caso di robot e automobili autonome, sia virtuali, come nel caso di sistemi per il trading automatico o degli assistenti virtuali. A partire da tale astrazione, il campo dei sistemi multiagente si propone di studiare, progettare e realizzare i meccanismi di interazione fra gli agenti autonomi.
In generale, i meccanismi con cui gli agenti autonomi possono interagire fra loro sono classificabili in due grandi categorie: meccanismi competitivi e cooperativi. Nel primo caso, si assume, con qualche semplificazione, che ogni agente sia “egoista”, cioè persegua unicamente il proprio obiettivo locale, anche a scapito del raggiungimento degli obiettivi locali degli altri agenti. La situazione tipica è quella del trading automatico dove ogni sistema cerca di massimizzare il proprio guadagno indipendentemente e, spesso, a svantaggio del guadagno degli altri agenti. Nel secondo caso, sempre con qualche semplificazione, è possibile individuare un obiettivo globale per il sistema multiagente nel suo complesso ed è possibile assumere che gli agenti siano “benevolenti”, cioè che contribuiscano, ognuno per le proprie capacità, a raggiungere tale obiettivo. Un esempio tipico è relativo ai robot per la logistica, per i quali l’obiettivo globale è la massimizzazione della produttività o la minimizzazione dei tempi di attesa per la consegna della merce.
Molte situazioni del mondo reale coinvolgono aspetti sia competitivi sia cooperativi. Si pensi, per esempio, alle automobili autonome in circolazione in una città. Da un lato, questi agenti competono per occupare lo spazio comune e arrivare prima alle proprie destinazioni percorrendo le stesse strade. Da un altro lato, gli agenti cooperano nel rispettare le regole della strada e nell’evitare incidenti.
Soluzioni per governare le interazioni cooperative
Nel seguito ci concentriamo sull’illustrazione di alcune soluzioni utilizzate per governare le interazioni cooperative fra agenti che operano nello stesso ambiente e, in particolare, su due approcci, uno per le interazioni fra agenti che operano in ambienti virtuali e l’altro per le interazioni fra agenti che operano in ambienti fisici.
Ottimizzazione distribuita
Consideriamo la situazione in cui degli assistenti virtuali intelligenti, ognuno dei quali gestisce l’agenda di una persona diversa, debbano coordinarsi per decidere la data di una riunione. Ad oggi, il problema è spesso risolto “manualmente” dagli utenti, tramite piattaforme come Doodle oppure tramite l’imposizione di una data da parte di chi convoca la riunione o del partecipante con i vincoli più stringenti. In un prossimo futuro, assistenti virtuali intelligenti si faranno carico di individuare la data più opportuna per la riunione.
Il problema può essere rappresentato come un problema di ottimizzazione distribuita [1] nel modo seguente. Sulla base degli impegni e delle abitudini del proprio utente, ogni agente ha un certo insieme di opzioni disponibili per la data della riunione. Non è in generale possibile trovare una data per la riunione semplicemente lasciando che ogni agente scelga casualmente una delle proprie opzioni (che, in generale, saranno diverse per ogni agente). Il problema richiede il rispetto di alcuni vincoli sulle date scelte dagli agenti singoli. Il più banale è quello che impone che tutti gli agenti scelgano la stessa data. Si possono definire anche vincoli più complessi, per esempio imponendo che il maggior numero possibile di partecipanti sia presente alla riunione oppure che almeno una persona appartenente a un sottogruppo (per esempio, quello delle persone di uno stesso dipartimento all’interno di una azienda o con competenze simili) possa partecipare alla riunione. Solitamente tali vincoli sono rappresentati attribuendo, a ogni combinazione di date che possono essere scelte dagli agenti, un valore numerico legato a quanto bene la combinazione soddisfa i vincoli. L’obiettivo per ogni agente è di scegliere una data fra quelle possibili in modo tale che la combinazione delle date scelte soddisfi i vincoli nel modo migliore. Questo problema di ottimizzazione è distribuito, in quanto non esiste un singolo decisore centralizzato, ma ogni agente è in ultima analisi co-responsabile dalla data scelta, nel rispetto dei vincoli che sono stati definiti.
Esistono numerosi algoritmi per la risoluzione di questo tipo di problemi, sia ottimi (che garantiscono di trovare la soluzione ottima), ma poco efficienti dal punto di vista computazionale, sia sub-ottimi ma generalmente più efficienti. Esistono anche numerose varianti del problema base illustrato sopra, che per esempio consentono di preservare la privacy dei partecipanti (nel nostro caso, evitando che gli agenti esplicitino le date disponibili per i loro utenti) e che ottimizzano più obiettivi.
Oltre al problema di decidere una data condivisa per una riunione, numerosi altri problemi sono attualmente modellati e risolti seguendo l’approccio dell’ottimizzazione distribuita. Per esempio, il coordinamento di mezzi autonomi di soccorso in operazioni di ricerca e soccorso, l’inseguimento di un bersaglio tramite droni autonomi e telecamere intelligenti e la gestione del consumo energetico di elettrodomestici e altri dispositivi, come i satelliti.
Consideriamo ora un gruppo di robot mobili per la logistica che si muovono nello stesso ambiente fisico, per esempio un magazzino. In questo caso, ogni robot, o agente, ha un compito da svolgere che, semplificando, possiamo rappresentare come il compito di muoversi da un punto A ad un punto B in un ambiente noto. Durante i loro movimenti, i robot non devono ovviamente scontrarsi. Il problema è quindi quello di pianificare i percorsi per tutti gli agenti in modo tale che, quando i robot seguono tali percorsi, tutti raggiungano le loro destinazioni partendo dalle posizioni iniziali, che non ci siano collisioni e che una determinata funzione obiettivo sia ottimizzata, come per esempio la lunghezza complessiva dei percorsi o la lunghezza del percorso più lungo. Questo problema, chiamato multiagent path planning oppure multiagent path finding [3], è recentemente affrontato con grande interesse per la sua rilevanza non solo per la logistica, ma anche per la movimentazione degli aeroplani negli aeroporti e per i videogiochi.
Soluzioni ai problemi di multiagent path finding
Numerosi approcci sono stati proposti per affrontare problemi di multiagent path finding. Si possono dividere in approcci centralizzati e distribuiti. Nei primi, un singolo decisore pianifica il percorso di tutti gli agenti, ovviamente evitando i conflitti e potenzialmente trovando soluzioni ottime. Nei secondi, ogni agente pianifica il proprio percorso e lo “armonizza” con quelli pianificati dagli altri agenti. Una possibilità, per esempio, è ordinare gli agenti secondo qualche criterio. Il primo agente nell’ordinamento pianifica il proprio percorso senza considerare vincoli, il secondo agente pianifica il proprio percorso considerando il percorso del primo come dato e quindi evitando collisioni con esso, il terzo agente pianifica il proprio percorso considerando i percorsi del primo e del secondo agente come dati ed evitando collisioni con essi, e così via. Lo svantaggio di tale approccio è che, considerando fissi di volta in volta i percorsi di un numero sempre maggiore di agenti, gli ultimi agenti a pianificare potrebbero non essere in grado di trovare percorsi per raggiungere le proprie destinazioni. Quello appena descritto è un esempio di una famiglia di approcci che prevede che ogni agente inizialmente pianifichi il proprio percorso e che, in una fase successiva, questi percorsi siano armonizzati.
Una seconda famiglia di approcci, invece, considera una “pianificazione condivisa” dei percorsi. Per esempio, gli agenti comunicano gli uni agli altri i movimenti che hanno deciso di effettuare come prime azioni dei loro percorsi per raggiungere le proprie destinazioni a partire dalle loro posizioni iniziali. Se un sottoinsieme di questi movimenti previsti provoca un conflitto, gli agenti interessati possono modificare le proprie azioni per fare in modo che le prime azioni previste da tutti gli agenti siano senza conflitti. Il processo procede in questo modo fino a pianificare percorsi completi e privi di conflitti.
Una terza famiglia di approcci, infine, prevede la istituzione di “regole sociali”, simili a quelle del codice della strada, che gli agenti sono obbligati a rispettare. In questo modo, ogni agente può pianificare indipendentemente il proprio percorso e, mentre lo percorre, gli eventuali conflitti sono risolti sulla base delle regole stabilite. Per esempio, si può evitare che due robot occupino la stessa posizione dell’ambiente definendo regole di precedenza (come: passa prima il robot che arriva da destra).
In conclusione, l’ambito dei sistemi multiagente è molto attivo a livello scientifico. Possiamo citare l’apprendimento in contesti caratterizzati dalla presenza di più agenti (che qui non abbiamo trattato) come tema di grande interesse attuale. Come abbiamo visto, la rilevanza dei sistemi multiagente si sta estendendo a moltissimi domini applicativi, nei quali più sistemi intelligenti si trovano ad operare nello stesso ambiente, favorito anche dalla crescente disponibilità di piattaforme (solitamente in Java o Python) per lo sviluppo software di tali sistemi e di librerie che implementano le soluzioni algoritmiche più efficaci. Sia scientificamente sia praticamente, quindi, le sfide poste dal coordinamento di diversi sistemi di IA rappresentano una delle direzioni di maggiore interesse per l’ulteriore sviluppo della disciplina.
___________________________________________________________________
Bibliografia
- Ferdinando Fioretto, Enrico Pontelli, William Yeoh, Distributed Constraint Optimization Problems and Applications: A Survey, Journal of Artificial Intelligence Research, 61:623-698, 2018
- Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Eli Boyarski, Roman Bartak, Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks, Proceedings of the Twelfth International Symposium on Combinatorial Search (SoCS), 151-158, 2019
- Gerhard Weiss, Multiagent Systems (Second Edition), The MIT Press, 2013
- Michael Wooldridge, An Introduction to MultiAgent Systems (Second Edition), Wiley, 2009
