Pianificazione multiagente

La pianificazione multiagente è un tipo di pianificazione adottata quando due o più agenti operano nello stesso ambiente con azioni in grado di influenzarsi reciprocamente. Nella pianificazione multiagente gli agenti ( soggetti ) possono perseguire il medesimo obiettivo o intraprendere le stesse azioni, in un contesto in cui le risorse sono scarse. La pianificazione multiagente è anche detta Multi Agent Planning. Ad esempio, nel seguente schema due agenti ( A e B ) eseguono la propria pianificazione. I piani di azioni sono caratterizzati da obiettivi e azioni differenti ma sono accomunati dalla presenza del medesimo stato S₃, nel quale può transitare un solo agente alla volta. Gli agenti giungono in modo differente allo stato S₃ compiendo azioni differenti (a₂ o a₆). Quando i piani di azione sono sfasati rispetto a S₃ gli agenti riescono a eseguire correttamente la propria sequenza di azioni senza influenzare il piano dell'altro agente.

Viceversa, quando i piani di azione sono sincroni rispetto a S₃ gli agenti entrano in conflitto in quanto eseguono contemporaneamente le azioni a₂ e a₆ che conducono al medesimo stato S₃. In questo caso nessun agente riesce a raggiungere lo stato S₃ ed entrambi i piani di azione A e B si bloccano. Ad esempio, in una strada con un'unica corsia può transitare un solo veicolo alla volta, quando due veicoli tentano di accedere contemporaneamente sulla strada si urtano reciprocamente e il cammino si blocca per entrambi.

In questi casi gli agenti pianificano adottando delle strategie differenti che possono essere basate sulla cooperazione o sulla competizione.

• Cooperazione. Nella cooperazione gli agenti organizzano una sequenza di azioni comune ( piano congiunto ) per massimizzare il vantaggio complessivo oppure per raggiungere un obiettivo che singolarmente nessun agente riuscirebbe a raggiungere.
• Competizione. Nella competizione gli agenti organizzano singolarmente la propria sequenza di azioni tenendo conto del comportamento atteso dell'altro soggetto, al fine ultimo di massimizzare il proprio vantaggio personale.

Le strategie di cooperazione e di competizione sono soltanto alcune, le principali, tra le varie forme di comportamento possibili.

---

• Teoria dei giochi. Sulla materia si è sviluppata una disciplina scientifica detta teoria dei giochi che studia le decisioni dei soggetti e le possibili strategie adottabili. La teoria dei giochi è nata in ambito economico, per studiare le scelte dei soggetti economici, ma è applicabile anche allo studio delle decisioni in altri contesti ( problem solving, intelligenza artificiale, robotica, ecc. ).
• Comunicazione multiagente. Gli agenti possono eliminare le situazioni di conflitto comunicando tra loro in fase di esecuzione del piano, senza dover necessariamente prevedere tutti gli eventi conflittuali nella fase di pianificazione. In una comunicazione multiagente, l'agente avvisa tutti gli altri agenti prima di accedere a una risorsa comune. Quando due agenti comunicano di voler fare la stessa azione utilizzando una medesima risorsa scarsa, questi sono costretti a cooperare e accordarsi su un piano di azione comune. Ad esempio, l'agente A utilizza per primo la risorsa e l'agente B sospende l'esecuzione del piano fin quando la risorsa è occupata.
  
  La comunicazione tra agenti consente di evitare le situazioni di conflitto ( interazione negativa ). Ha però un costo, in quanto tutti gli agenti devono essere dotati di un dispositivo di trasmissione e di ricezione e devono essere in grado di capirsi, ossia di comunicare utilizzando un medesimo protocollo. Inoltre, la comunicazione multiagente evita le interazioni negative ( conflitti ) ma non aiuta a trovare le eventuali interazioni positive tra i piani degli agenti.
• Coordinamento centrale. Il coordinamento centrale è gestito da un'autorità centrale alla quale si rivolgono gli agenti nelle situazioni conflittuali. Nel coordinamento centrale gli agenti si limitano a constatare una situazione di conflitto e la comunicano all'autorità centrale, a cui spetta il compito di definire l'ordine di esecuzione dei piani in conflitto. Le comunicazioni inter-agenti sono limitate. Sono, invece, molto numerose le comunicazioni tra gli agenti e l'autorità centrale.
• Sincronizzazione perfetta dei piani di azione. La sincronizzazione perfetta degli attuatori è una soluzione efficace ma anche molto costosa. Nella fase di pianificazione sono determinati i piani di azione per ogni dispositivo attuatore sulla base dei piani di azione degli altri dispositivi attuatori ( azioni congiunte ). L'operazione di pianificazione congiunta ( pianificazione centralizzata ) potrebbe essere molto dispendiosa in termini di risorse computazionali, in quanto la complessità cresce in modo esponenziale. Dati n dispositivi attuatori e N_a azioni possibili, il pianificatore deve elaborare N_aⁿ combinazioni.
  
  La complessità cresce esponenzialmente rispetto ai dati. Ad esempio, se nel sistema operano due attuatori (n=2), ognuno dei quali può compiere tre azioni (N_a=3), le combinazioni possibili da analizzare sono 3² ossia nove (C=9). Aggiungendo un altro dispositivo attuatore (n=3) le combinazioni crescono in modo esponenziale a 3³ e diventano ventisette (C=27). Con quattro dispositivi attuatori (n=4) le combinazioni diventano 3⁴ ( C=81 ) e così via. In conclusione la sincronizzazione non è una strada sempre percorribile in termini di complessità computazionale. La complessità del problema può essere ridotta suddividendo il problema in due o più sottoproblemi indipendenti ( scomposizione in sottoproblemi indipendenti ). Ad esempio, il problema dei quattro dispositivi attuatori (n=4) può essere scomposto in due sottoproblemi S1 e S2. In ogni sottoproblema sono analizzate le combinazioni tra due agenti (n₁=n₂=2). Il numero delle combinazioni da analizzare diventa N_a^n₁ + N_a^n₂ ossia 3²+3² ( 18 ). L'accoppiamento consente di ridurre la complessità del problema dalle 81 combinazioni dell'unico problema originale alle 18 combinazioni dei due sottoproblemi disgiunti. La tecnica della scomposizione è efficace soltanto se le azioni degli agenti di un sottoproblema S1 sono indipendenti dalle azioni degli agenti dell'altro sottoproblema S2.
• Coordinamento senza comunicazione. Le interazioni negative possono essere ridotte attraverso la comunicazione tra agenti ma questo comporta un costo aggiuntivo, in quanto gli agenti devono essere dotati di un sistema di comunicazione, trasmittente e ricevente, e devono comunicare nella stessa lingua ( protocollo ) per capirsi. Per ridurre il costo della comunicazione è consigliabile disciplinare il rapporto tra gli agenti tramite delle norme o convenzioni. Nel caso delle norme comuni gli agenti potrebbero essere in grado di coordinarsi senza dover comunicare l'uno con l'altro. Un esempio di convenzione del mondo reale è il codice della strada. Gli automobilisti guidano osservando i segnali stradali. Ad esempio, mantengono la destra sulla corsia, si fermano allo stop, danno la precedenza a chi viene da destra, ecc. Queste convenzioni consentono di ridurre il numero degli incidenti. Lo stesso principio può essere utilizzato per il coordinamento decentrato degli agenti artificiali. Le convenzioni disciplinano i rapporti tra gli agenti senza comunicare tra loro. Ogni agente rispetta le norme comuni e, così facendo, riconosce il piano di azione degli altri agenti. È comunque opportuno mantenere una forma di comunicazione diretta inter-agenti e/o un'autorità centrale di coordinamento per gestire le situazioni più critiche, le ambiguità e i casi non previsti dalle norme stesse.
• Cooperazione senza pianificazione centrale. Nella cooperazione gli agenti comunicano tra loro per scambiarsi i piani di azione. La comunicazione consente agli agenti di riconoscere il piano di azione degli altri e adattare il proprio comportamento a quello degli altri. Il problema sorge quando gli agenti non hanno un'autorità di pianificazione centrale. In questi casi gli agenti devono accordarsi per un piano congiunto e non sempre però è possibile. Spesso le decisioni devono essere prese in poco tempo. Ad esempio, i giocatori di una squadra di calcio deducono il piano di azione dei propri compagni osservando il loro comportamento, in pochi secondi e senza parlare. L'allenatore della squadra di calcio può impostare la formazione, le tattiche e gli schemi di gioco... ma gran parte della partita si gioca sull'improvvisazione dei singoli giocatori e sulla loro capacità di coordinarsi con gli altri. Lo stesso problema accade nella cooperazione multiagente senza coordinamento.