Multiagent Planning
Presentazione
Andrea Bonisoli
Università degli studi di Brescia
24 Novembre 2014
Piani cazione Classica
Le azioni sono deterministiche ed hanno eetto istantaneo;
Lo stato iniziale è completamente noto;
Il goal è raggiungere uno degli stati possibili per cui risulta soddisfatta un insieme proposizioni;
Un piano soluzione è una sequenza di azioni che, quando applicata a partire dallo stato iniziale, porta no ad uno stato goal.
L'agente piani catore suppone di trovarsi da solo isolato in un mondo chiuso di cui può controllare l'evoluzione dello stato.
Running example
Dominio Logistico
Multiagent Planning
Divide et Impera
Alcuni domini presentano una facile e naturale suddivisione dei compiti tra agenti dierenti. Questa struttura potrebbe essere utilizzata per rendere i piani catori più e cienti e più veloci?
Inoltre si vorrebbe rendere esplicita l'interazione tra i vari attuatori che eseguono le azioni nel mondo rispetto all'approccio più astratto di un singolo piani catore.
Si tratta di un campo di ricerca molto vasto, popolare ed in rapida crescita, come si può vedere dai risultati presenti su Google Scholar.
Approcci multiagente
Agenti come Astrazioni
Si vuole decomporre un dominio per un problema di piani cazione classico in un problema di piani cazione multiagente.
Ad esempio il dominio logistico si presta bene ad essere decomposto.
Si vuole ottenere un algoritmo di piani cazione più e ciente (più veloce) per risolvere il problema multiagente in modo da poter dedurre una soluzione per il problema di partenza.
Il contesto è ancora molto simile alla piani cazione classica ma sfrutta tecniche multiprocessore e di programmazione parallela. Poiché risolve con un unico piano il problema viene spesso de nito approccio centralizzato.
Entro quali ipotesi l'algoritmo potrebbe essere più e ciente? Ovvero in quali casi risolvere un insieme di problemi più piccoli è più e cace che risolvere un solo grande problema composto dalla loro unione?
Approcci multiagente
Agenti come Componenti Distribuiti
Si vuole risolvere un problema di piani cazione per un sistema di agenti autonomi e distribuiti (in grado di comunicare tra loro).
Ad esempio un insieme di robot per la ricerca di sopravvissuti in una zona colpita da disastri ambientali.
In generale potrebbero anche ricevere le azioni da eseguire da un cervello centrale che esegue l'algoritmo precedente. In questo caso sacri cherebbero la loro autonomia, ma non è detto che sia sempre una strada possibile.
Si vuole quindi ottenere un algoritmo di piani cazione distribuito tra diversi agenti piani catori/attuatori che produca un piano per ogni agente la cui esecuzione contemporanea sia una soluzione per il problema.
In entrambi questi due casi gli agenti sono completamente cooperativi.
Approcci multiagente
Agenti con Privacy e Goal condivisi
Si vuole risolvere un problema in cui un gruppo di agenti deve raggiungere un goal comune, mantenendo però private alcune informazioni.
Ad esempio diverse compagnie che stanno collaborando su un progetto comune, oppure diversi dipartimenti di una singola azienda.
Se il vincolo sulla privacy è molto forte, potrebbe non essere valido adottare un approccio centralizzato, ma solamente algoritmi distribuiti.
Si vuole però che l'algoritmo di piani cazione distribuito sia anche in grado di mantenere private alcune informazioni degli agenti, evitando anche lo scambio di queste informazioni durante l'esecuzione dell'algoritmo di piani cazione.
Approcci multiagente
Agenti Egoisti con alcuni Goal Condivisi
E se gli agenti non fossero interessati a raggiungere il goal, ma solo al proprio
interesse personale?
In questo caso ogni agente può avere dei goal dierenti ma soprattutto ha una funzione di utilità in generale diversa (senza essere tuttavia in
competizione diretta per il raggiungimento dei goal).
Ad esempio un gruppo di appaltatori che deve costruire delle grandi opere.
Per questo motivo si voglio degli algoritmi e meccanismi che, oltre a mantenere la privacy, garantiscono particolari proprietà (quali la stabilità) rispetto alla soluzione trovata.
Perché suddividere il problema?
Un piani catore classico centrale non è su ciente?
Per alcuni casi potrebbe essere una buona soluzione, ma presenta alcuni problematiche:
È un approccio meno robusto e più soggetto a fallimenti.
Potrebbe non adattarsi bene ad agenti complessi che devono essere implementati tramite un simulatore.
Richiede la possibilità di comunicare in modo e cace con il piani catore centrale, di cui tutti gli agenti devono avere piena ducia e di cui devono seguire le indicazioni ricevute.
Inoltre non consente di mantenere private alcune informazioni, che devono essere comunicate almeno al piani catore centrale.
MA-STRIPS
Un linguaggio per problemi multiagente
Si tratta di una semplice estensione del linguaggio di piani cazione STRIPS per problemi multiagente.
L'unico cambiamento prevede di associare ogni azione con un singolo agente.
L'insieme della azioni diventa quindi una partizione rispetto agli agenti.
Seguono due de nizioni:
Una variabile del problema si de nisce privata se è presente nelle azioni di un solo agente.
Una variabile si de nisce pubblica altrimenti.
Inoltre:
Una azione di un agente si de nisce privata se coinvolge solamente variabili private.
Una azione di un agente si de nisce pubblica altrimenti.
MA-STRIPS
Modello formale
Un problema MA-STRIPS per un insieme di agenti Σ = {αi}ni=1 è una tuple hP, {Ai}ni=1,I , Gi dove:
P è un insieme nito di proposizioni atomiche I ⊆ P è lo stato iniziale del problema
G ⊆ P codi ca le condizioni dello stato goal
Per ogni 1 ≤ i ≤ n, Ai è l'insieme delle azioni che l'agente αi è in grado di eseguire.
Ogni azione a ∈ A = S Ai è de nita come in STRIPS dalle sue precondizioni e dai suoi eetti.
Grafo interazione
Per meglio visualizzare le connessioni tra gli agenti del problema è utile il grafo di interazione.
In questo grafo gli agenti del problema sono rappresentati sui nodi del grafo, uno per agente.
Nel grafo sarà presente un arco tra due nodi se il primo agente possiede una azione che fornisce oppure consuma una precondizione di una azione del secondo agente.
Se il grafo presenta molti archi, gli agenti sono strettamente correlati tra loro perché le loro azioni si in uenzano a vicenda.
Se il grafo fosse completamente connesso ogni agente dipende dalle azioni di ogni altro agente.
Se il grafo non fosse connesso, il problema è scomponibile in in parti separate che non hanno interazioni.
È una misura della correlazione tra gli agenti.
Grafo interazione
Esempio di Grafo
MA-A*
Una estensione di A*
Ogni agente svolge una ricerca separata e indipendente dagli altri agenti con l'algoritmo A*:
Mantiene la sua lista di stati aperti e chiusi.
Espande uno stato utilizzando solo le sue azioni.
Comunica uno stato di ricerca agli altri agenti quando questi ne hanno bisogno.
Calcola una soluzione ottimale rispetto al numero di azioni in modo distribuito.
Nello speci co, ogni agente comunica uno stato di ricerca quando lo raggiunge tramite una delle sue azioni pubbliche, che per de nizione producono uno stato in cui almeno una variabile è interessante per almeno un altro agente.
Quando un agente riceve una comunicazione con uno stato potrebbe decidere se inserirlo nella sua lista di stati aperti oppure chiusi.
MA-A*
Esempio di esecuzione
MA-A*
Esempio di esecuzione
MA-A*
Esempio di esecuzione
MA-A*
Esempio di esecuzione
MA-A*
Esempio di esecuzione
MA-A*
Esempio di esecuzione
Privacy nei problemi multiagente
La de nizione di pubblico e privato non è su ciente per la privacy degli agenti.
Infatti se almeno una proposizione pubblica deve rimanere con denziale tra un sottoinsieme di agenti, nell'algoritmo MA-A* questa viene comunicata pubblicamente a tutti gli agenti del problema.
Inoltre vi sono altre informazioni in un problema di piani cazione che si potrebbe voler mantenere private tra cui:
Fatti di altri agenti
Azioni eseguite da altri agenti Link causali tra le azioni
L'identità o la presenza di alcuni agenti nel problema
Si tratta di un campo di ricerca ancora aperto ed in sviluppo.
