Multi-agent MILPs with scalar coupling : a decentralized solution with application to photovoltaic plant inspection

Mixed-Integer Linear Programs (MILPs) are used to model a variety of engineering problems where both physical systems and logical constraints are present. They also arise in problems involving multiple agents, where each agent aims at optimizing a local cost subject to its own operative constraints, but is coupled with the others because of some shared resource. As the number of decision variables (and agents) increases, the solution to the MILP becomes computationally intractable due to the inherent combinatorial complexity of the problem. In this thesis, we focus on constraint-coupled multi-agent MILPs with a single coupling constraint. We introduce a decentralized scheme to find a feasible solution that rests on dual decomposition, with agents solving in parallel lower dimensional MILPs and a central unit enforcing the coupling constraint by appropriately updating the dual variable through the bisection method. The proposed algorithm is easy to implement, requires little design parameter tuning, and is shown to provide better solutions than a state-of-the-art decentralized competitor algorithm. In the second part of the thesis, we test the effectiveness and scalability of the proposed decentralized resolution scheme on a photovoltaic plant automatic inspection problem using a fleet of quad-copters. Given a set of panels to be inspected, a central unit has to decide the optimal assignment of the panels to the quad-copters and plan their trajectories so as to minimize the overall energy consumption and supervision time, compatibly with their dynamics and actuation constraints and subject to an energy budget constraint on the whole fleet. The problem can be formulated as a multi-agent MILP and reduced to a constraint-coupled form with a single coupling constraint by applying a heuristic procedure for the assignment of the inspection tasks. Extensive simulations show that the resulting two-stage approach, where the heuristic assignment is followed by the proposed decentralized resolution strategy, is able to obtain a feasible, highly performing solution at a reduced computational cost, also for size instances of the problem that are not practically solvable via centralized optimization.

I programmi lineari misto-interi~(MILP) sono usati in una grande varietà di applicazioni ingegneristiche per descrivere il comportamento di sistemi con componenti fisiche e logiche, soggetti a vincoli operativi. Vengono spesso usati anche per descrivere problemi che coinvolgono più agenti, in cui ciascuno mira a ottimizzare un indice di performance locale soddisfacendo i propri vincoli operativi ma è accoppiato con gli altri a causa di qualche risorsa condivisa. Purtroppo, la presenza di variabili decisionali discrete rende la complessità del problema intrinsecamente combinatoria tanto che all'aumentare del numero di variabili decisionali (e di agenti), il MILP diventa computazionalmente intrattabile. Questa tesi si concentra su MILP multi-agenti con un singolo vincolo di accoppiamento. Nello specifico, la prima parte propone uno schema decentralizzato per trovare una soluzione ammissibile del problema di ottimizzazione basato sulla decomposizione duale: il problema originale viene suddiviso in MILP di dimensioni ridotte risolti in parallelo dagli agenti, mentre un'unità centrale fa rispettare il vincolo di accoppiamento aggiornando opportunamente la variabile duale attraverso il metodo della bisezione. L'algoritmo proposto è facile da implementare, richiede una minima taratura dei parametri di progettazione, ed è dimostrato fornire soluzioni migliori di un algoritmo decentralizzato concorrente allo stato dell'arte. Nella seconda parte della tesi, testiamo l'efficacia e la scalabilità dello schema di risoluzione decentralizzato proposto su un problema di ispezione automatica di un impianto fotovoltaico utilizzando una flotta di quadricotteri. Dato un insieme di pannelli da ispezionare, un'unità centrale deve decidere l'assegnazione ottimale dei pannelli ai veicoli e pianificare le loro traiettorie in modo da minimizzare il consumo energetico complessivo e il tempo di supervisione, compatibilmente con la loro dinamica e i vincoli di attuazione e ripettando un vincolo di budget energetico che coinvolge l'intera flotta. Il problema viene prima formulato come un MILP multi-agente e poi ridotto a una forma vincolata con un singolo vincolo di accoppiamento applicando una procedura euristica per l'assegnazione degli obiettivi di ispezione. Simulazioni estensive mostrano che ilrisultante approccio a due stadi, dove l'assegnazione euristica è seguita dalla applicazione della strategia di risoluzione decentralizzata proposta, è in grado di ottenere una soluzione ammissibile, altamente performante ad un costo computazionale ridotto, anche per istanze del problema chenon sarebbero risolvibili tramite ottimizzazione centralizzata a causa della loro dimensione.