A decentralized approach to multi-agent cooperative control

In this thesis, we address multi-agent cooperative control, where a set of agents need to jointly complete given tasks while sharing some resources. The problem then becomes how to coordinate the agents so that the tasks are optimally assigned and executed given the limited amount of resources available. In particular, we consider the RoboFlag game where a set of agents called defenders need to protect a region of the playing field from the incursion of multiple attackers. A task is then represented by capturing one attacker, and the goal of the defenders team is to capture as many attackers as possible, compatibly with an overall energy budget constraint. Under the assumption that the strategy of the attackers is fixed and known, a Mixed Integer Linear Problem (MILP) with both integer and continuous optimization variables can be formulated so as to determine the best defenders strategy. As the number of defenders and attackers increases, the MILP may become intractable, which calls for a decomposition into smaller MILPs, which can be solved in parallel, one per defender. The main contribution of this thesis is the introduction of a two-stage approach where we first assign tasks (attackers) to each defender and then, we apply a decentralized scheme to design the strategies of the defenders so as to meet the overall energy budget. The proposed approach is validated on several game configurations.

Questa tesi riguarda problemi di controllo cooperativo multi-agente, in cui un insieme di agenti deve collaborare per realizzare certi obiettivi, utilizzando risorse condivise limitate. Si affronta in particolare il problema di come coordinare gli agenti, assegnando loro i vari obiettivi da raggiungere e stabilendo come ognuno di loro debba agire per portarli a termine, nel rispetto delle risorse a disposizione. In particolare, si considera il gioco RoboFlag, in cui un insieme di agenti, chiamati difensori, devono proteggere una regione del campo di gioco dall’incursione di alcuni attaccanti. Un obiettivo consiste nella cattura di un attaccante, e lo scopo della squadra dei difensori è di catturare il maggior numero di attaccanti, rispettando un vincolo sull’energia complessiva a disposizione della squadra. Assumendo che la strategia degli attaccanti sia fissata e nota ai difensori, si può determinare la strategia ottima della squadra dei difensori come soluzione di un problema di programmazione lineare mista intera (MILP -- Mixed Integer Linear Program), le cui variabili di ottimizzazione sono sia intere sia continue. Al crescere del numero di attaccanti e difensori, il MILP diventa computazionalmente intrattabile da risolvere. Pertanto, si rende necessario decomporlo in sotto-problemi di dimensione ridotta, uno per ogni difensore, che possono essere risolti in parallelo. Il principale contributo di questa tesi consiste nell’introduzione di un approccio articolato in due fasi, dove, nella prima fase, gli attaccanti vengono assegnati a diversi difensori e, nella seconda fase, si applica un approccio decentralizzato per definire le strategie dei difensori, nel rispetto dell’energia complessiva disponibile. L’approccio proposto è validato per simulazione su varie configurazioni del gioco.