Optimal control of large scale stochastic hybrid systems with a finite control space

In recent years, the interest for the class of hybrid and possibly also stochastic systems has grown, motivated by the large variety of applications where continuous and discrete dynamics are strongly interacting and are affected by uncertainty. Modeling, analysis, and control design of such systems raise severe methodological questions. This thesis addresses optimal control design for discrete time Stochastic Hybrid Systems characterized by a finite control space, and relies on the theoretical frameworks of Markov Decision Processes, Dynamic Programming and Reinforcement Learning to this purpose. The main challenge herein is represented by the so--called curse of dimensionality, since, when the state dimension is large, classical approximate dynamic programming techniques may become computationally intractable. In this thesis we develop two control strategies for systems characterized by a finite control spaces and high dimensional continuous state spaces. Both the approaches share the same idea of effectively partitioning the state space into regions identified by the same optimal control action. In the first part of the thesis we address the optimal control of discrete--time switched systems, described by a finite set of operating modes, each one associated with an affine dynamics, and with a random initial state. The objective is the design of the switching law so as to minimize an infinite--horizon expected cost, while penalizing frequent switchings. Starting from the observation that a control policy associates a mode to each state and, as such, can be viewed as a classifier, we propose a novel classification--based algorithm that trains such classifier--like controller with a set of training data in the form of optimal state--mode pairs. In the considered setting, the generation of the training set involves solving a Mixed Integer Quadratic Program (MIQP) for each pair. The optimal switching law is computed off--line, which allows an efficient on--line operation of the system via a state feedback policy. A key feature of the proposed approach is the use of a classification method that provides guarantees on the generalization properties of the classifier. Exploiting this peculiarity, we provide theoretical guarantees on the performance of the resulting policy: the sub--optimality of the approximate policy obtained by the proposed algorithm can be made arbitrarily small, provided that a suitable number of training data are generated. Interestingly, the number of samples required is independent of the state space dimension, which makes the algorithm amenable for large scale systems. The algorithm is tested on a multi--room heating control problem to show the viability of the approach. In the second part of the thesis we turn to the optimal control of more general discrete--time stochastic hybrid systems, and cope with the curse of dimensionality by searching for the optimal control policy in a restricted parametrized policy space. In particular we introduce a novel policy parametrization that adopts particles to describe the map from the state space to the action space, each particle representing a region of the state space that is mapped into a certain action. The locations and actions associated to the particles describing a policy can be tuned by means of a recently introduced policy gradient method with parameter-based exploration, called PGPE. The main advantage of such parametrization is its ability to exploit a particle to represent an entire region of the state space. Note that, by changing the granularity of the particles over the state space, it is possible to achieve any desired accuracy in the policy approximation. The task of selecting an appropriately sized set of particles is then solved through an iterative policy building scheme that adds new particles to improve the policy performance and is also capable of removing redundant particles. The iterative nature of the algorithm helps to alleviate its sensitivity with respect to the parameters initialization and to reduce the risk of getting stuck in local optima. Experiments on two benchmarks problems demonstrate the scalability of the proposed approach as the dimensionality of the state space grows.

Negli ultimi anni, l'interesse per la classe dei sistemi ibridi e possibilmente anche stocastici è cresciuta, motivata dalla varietà di applicazioni dove dinamiche continue e discrete interagiscono strettamente e sono affette da incertezza. La modellizzazione, l'analisi e il controllo di tali sistemi solleva importanti questioni metodologiche. Questa tesi affronta la progettazione di algoritmi di controllo ottimo per Sistemi Ibridi Stocastici a tempo discreto e caratterizzati da un uno spazio di controllo finito, e per questo obiettivo fa affidamento sulla teoria dei Processi Decisionali di Markov, della Programmazione Dinamica e del Reinforcement Learning. Qui la principale sfida è rappresentata dalla così detta "curse of dimensionality" (maledizione della dimensionalità), dal momento che, per sistemi di grande dimensione, le classiche tecniche di programmazione dinamica approssimata possono divenire computazionalmente intrattabili. In questa tesi sviluppiamo due strategie di controllo per sistemi caratterizzati da uno spazio delle azioni finito e uno spazio di stato continuo e ad alta dimensionalità. Entrambi gli approcci condividono la stessa idea di partizionare lo spazio di stato in regioni caratterizzate dalla medesima azione ottima di controllo. Nella prima parte della tesi affrontiamo il controllo ottimo di sistemi a commutazione a tempo discreto, descritti da un insieme finito di modi operativi, ciascuno associato con una dinamica affine, e da uno stato iniziale casuale. L'obiettivo è la progettazione della legge di commutazione che minimizzi il valore atteso del funzionale di costo sull'orizzonte di tempo infinito, e che al contempo penalizzi commutazioni frequenti dei modi del sistema. Iniziando con l'osservare che una politica di controllo associa a ogni stato del sistema un particolare modo e che, di conseguenza, può essere vista come un classificatore, proponiamo un nuovo algoritmo basato su classificatori che addestra tale tipo di controllore tramite un insieme di dati nella forma di coppie stato--modo ottimo. Nel contesto considerato, la creazione di tale insieme di dati implica la soluzione di un problema di ottimizzazione quadratica con variabili intere per ogni coppia di campioni. La legge di commutazione ottima è calcolata off--line, consentendo un efficiente funzionamento on--line del sistema complessivo tramite una politica di controllo in retroazione sullo stato del sistema stesso. Una caratteristica chiave dell'approccio proposto è l'uso di un algoritmo di classificazione che prevede garanzie sulla capacità di generalizzazione del classificatore risultante. Sfruttando questa peculiarità, dimostriamo alcune garanzie teoriche sul comportamento della politica di controllo risultante dall'algoritmo proposto: in particolare, il suo livello di approssimazione può essere reso arbitrariamente piccolo, a condizione che vengano generati un adeguato numero di dati di addestramento. E' interessante notare che tale numero di campioni è indipendente dalle dimensioni dello stato del sistema, e questo rende l'algoritmo applicabile a sistemi su larga scala. L'algoritmo è testato su un problema di controllo che concerne il riscaldamento di più stanze per mostrare l'applicabilità dell'approccio. Nella seconda parte della tesi ci occupiamo del controllo ottimo di generici sistemi ibridi stocastici a tempo discreto, e superiamo le difficoltà connesse con la "curse of dimensionality" effettuando la ricerca della politica di controllo ottima in un ristretto e parametrizzato spazio delle politiche. In particolare introduciamo una nuova parametrizzazione per la politica, la quale adotta particelle per descrivere la mappa tra lo spazio di stato e delle azioni, dal momento che ogni particella rappresenta una regione dello spazio di stato che è associata a una certa azione. Le posizioni e le azioni associate alle particelle che definiscono la politica possono essere raffinate tramite l'applicazione di un recente algoritmo di ottimizzazione che segue la direzione del gradiente direttamente nello spazio dei parametri della politica, e chiamato Policy Gradient with Parameter--based Exploration. Il principale vantaggio di tale parametrizzazione è la sua capacità di sfruttare una singola particella per rappresentare una intera regione dello spazio di stato. Si noti che, cambiando la granularità delle particelle sullo spazio di stato, è possibile raggiungere qualsivoglia livello di accuratezza nell'approssimazione della politica. Il compito di selezionare un insieme di particelle di opportune dimensioni è svolto per mezzo di una procedura iterativa per la costruzione della politica, la quale aggiunge nuove particelle e rimuove quelle eventualmente ridondanti per migliorare il comportamento della legge di controllo. La natura iterativa dell'algoritmo aiuta ad attenuare l'eventuale sensibilità rispetto all'inizializzazione dei parametri e a ridurre il rischio di restare bloccati in ottimi locali. Esperimenti numerici su due problemi di riferimento dimostrano la scalabilità dell'approccio proposto al crescere della dimensionalità dello spazio di stato del sistema.