Algorithms for the design of stabilizing switching graphs for discrete-time switched linear systems

We developed four algorithms, implementing different heuristics, for the automatic generation of switching graphs that stabilize a given discrete-time switched linear system. The algorithms iteratively check (by means of tree-based algorithms recently developed by Professors Dercole and Della Rossa) the stability of the system constrained by the switching graph, that is iteratively modified until a stabilizing solution is reached. The procedure starts either from the graph allowing arbitrary switching or from an application-specific graph under which the system is unstable. In order to modify the graph, we exploit an important theoretical result (due to Professor Dai) that tightly lower bounds the system's constrained joint spectral radius---bounding the long-term average growth rate of the system's trajectories---by looking at the stability of matrix products computed along cycles of the switching graph. This result allows us to modify the switching graphs by iteratively cutting unstable cycles (cycles with unstable matrix product), by preventing in different ways to indefinitely repeat them. The procedure eventually terminates with a graph free of unstable cycles, thus resulting in a stable system. The final graphs from all algorithms are either stabilizing, or empty (0 nodes). There are, however, important trade-offs between their speed and restrictiveness. The first two algorithms are faster and produce switching graphs that are more restrictive, while Algorithms 3 and 4 are slower and produce less-restrictive switching graphs; termination for the latter algorithms has not been proven yet. Accordingly, the choice of algorithm should be application driven. In some cases, the resulting switching graph could be improved in different ways to fit a given application better, even by adding some of the freedom lost during the heuristic. This can be done manually, by someone with knowledge about the system and using the result from our algorithms as the starting point, or automatically, e.g., by applying Algorithm 1 or 2 (granting fast termination) starting from a large (possibly unstable) graph produced by Algorithm 3 or 4).

In questa tesi sono stati sviluppati quattro algoritmi per la generazione automatica di grafi di commutazione che stabilizzino un determinato sistema lineare a commutazione (switched) a tempo discreto. Gli algoritmi modificano iterativamente il grafo di commutazione, controllando di volta in volta la stabilità del sistema mediante metodi diretti (ad albero di prodotti di matrici) recentemente sviluppati dal gruppo del Professor Dercole ([11] e [12]). La procedura inizia da un grafo assegnato, specifico dell’applicazione considerata o dal grafo che consente la commutazione arbitraria, rispetto al quale il sistema risulta instabile. Per modificare il grafo, sfruttiamo un importante risultato teorico (dovuto al Professor Dai [10]) che mostra come un maggiorante stretto al raggio spettrale congiunto (joint) del sistema a commutazione vincolata—estremo superiore del tasso di crescita medio a lungo termine delle traiettorie—possa essere ottenuto osservando la stabilità dei prodotti di matrici lungo i cicli del grafo di commutazione. Questo risultato ci permette di modificare il grafo tagliandone iterativamente i cicli instabili (cicli con prodotto di matrici instabile). I quattro algoritmi proposti si differenziano per l’euristica utilizzata a tal fine, essenzialmente per impedire di ripetere indefinitamente il ciclo instabile individuato, con l’obiettivo di terminare con un grafo privo di cicli instabili, quindi risultante in un sistema a commutazione stabile. I grafi finali di tutti gli algoritmi sono stabilizzanti o vuoti (0 nodi). Vi sono, tuttavia, importanti compromessi tra la loro velocità e le restrizioni che impongono alla commutazione. I primi due algoritmi proposti sono veloci, ma producano grafi di commutazione severamente restrittivi, mentre i due successivi algoritmi impongono meno vincoli, permettendo di percorrere i cicli instabili un numero limitato di volte. Essi richiedono tempi di calcolo maggiori e, per il momento, non abbiamo dimostrato la loro sicura terminazione. La scelta dell’algoritmo più idoneo dipende quindi dalla specifica applicazione e dal tempo e potenza di calcolo disponibili. In alcuni casi, il grafico di commutazione risultante potrebbe essere migliorato in modi diversi per adattarsi meglio al caso specifico considerato, anche reintroducendo parte della libertà di commutazione persa con l’euristica dell’algoritmo. Questo può essere fatto manualmente, secondo direttive suggerite dall’applicazione stessa, o automaticamente, per esempio usando in modalità mista gli algoritmi proposti: prima l’algoritmo 3 o 4 per arrivare ad un grafo stabilizzante, magari molto grande, o addirittura fermandosi ad un risultato parziale non stabilizzante; poi l’algoritmo 1 o 2 per snellire il grafo e garantire terminazione ad un grafo stabilizzante. Possibili sviluppi futuri, idee per formalizzare le dimostrazioni di terminazione degli algoritmi 3 e 4, ed approcci complementari sono brevemente discussi in conclusione di questo lavoro.