Hybrid system identification using a randomized method

Hybrid systems provide a uniform framework for handling the modeling problem of complex systems exhibiting a switching behavior among a set of local (non)-linear dynamics. This thesis proposes several methods for the identification of hybrid systems, i.e., the task consisting in the estimation of both the local models (modes) and the mode transition mechanism. This task amounts to a combinatorial mixed-integer optimization problem that involves both discrete variables (the switching mechanism) and continuous variables (the parameterizations of the local models). According to the interpretation of the switching mechanism, hybrid systems are typically modeled as either switched systems (where the switching rule is independent of the system state) or piece-wise affine (PWA) systems (where the switching is associated with the state transition). The primary challenge in hybrid system identification lies in the combinatorial complexity, as the number of possible switching mechanisms (represented by sample-mode assignments) grows exponentially with the size of the training dataset. Additionally, as noted in the literature, some samples are "ambiguous" and can be fitted equally well by multiple local models. Assigning these samples based solely on fitting performance may sometimes introduce outliers. While misclassifying such ambiguous samples does not significantly affect the accuracy of the local model estimates or their fitting performance, it can severely impact the correct estimation of the switching mechanism. Notably, even with accurate local models, employing an incorrect switching mechanism can result in entirely unsatisfactory model behavior. This thesis addresses the challenges of combinatorial complexity and sample classification ambiguity by associating clusters of samples with their correct modes, rather than adopting a point-wise assignment approach. This reduces combinatorial complexity (since there are far fewer clusters than individual samples) and minimizes the impact of outliers (as ambiguous samples are influenced by unambiguous ones within the same cluster). Throughout the thesis, cluster-mode assignment is consistently addressed using a randomized method. This approach involves extracting potential assignments from a probability distribution, estimating and evaluating local models based on corresponding subsets of data, and iteratively updating the distribution to favor better-performing assignments. The updates continue until the distribution converges to a limit distribution mass centered on the optimal cluster-mode assignment. However, this method is effective only if clusters are "pure" (i.e., all samples within a cluster are generated by the same mode), which motives the development of a procedure to refine the initial clusters. Specific refinement strategies are developed for switched and PWA systems. In the context of switched system identification, it is assumed that switching occurs only at fixed time instants. Consequently, clusters are represented as collections of samples within time intervals defined by hypothesized switching locations. One proposed solution alternates between cluster-mode assignment and cluster refinement, formalizing a two-stage iterative approach. Since the randomized method for cluster-mode assignment is computationally expensive, a one-stage solution is also developed. This method simultaneously estimates switching locations and performs cluster-mode assignment within a randomized framework, eliminating the need for a separate refinement stage. A third contribution is a distributed solution tailored to handle the increased combinatorial complexity arising from a large number of clusters. For PWA systems, the state space is partitioned into multiple regions, each corresponding to the operational region of a specific mode. Assigning a sample involves determining the mode associated with the corresponding state space region. Samples that are close in the state space are therefore more likely to belong to the same mode, leading to clusters being initially formed based on spatial proximity. Unlike switched systems, which rely on the division of the time horizon, these clusters are defined in a high-dimensional state space. To handle this complexity, a specialized cluster refinement procedure has been developed and integrated with the randomized method, forming an alternating optimization framework for cluster-mode assignment and cluster refinement. Simulation analysis shows that these methods achieve high classification accuracy, albeit with a slight reduction in fitting performance, enabling a more precise analysis of the switching mechanism.

I sistemi ibridi offrono un quadro uniforme per affrontare il problema della modellizzazione di sistemi complessi che presentano un comportamento di commutazione tra un insieme di dinamiche locali (non)-lineari. Questa tesi propone diversi metodi per l'identificazione di sistemi ibridi, ovvero il compito di stimare sia i modelli locali (modi) sia il meccanismo di transizione tra i modi. Questo compito si traduce in un problema di ottimizzazione combinatoria a variabili miste, che coinvolge sia variabili discrete (il meccanismo di commutazione) sia variabili continue (le parametrizzazioni dei modelli locali). A seconda dell'interpretazione del meccanismo di commutazione, i sistemi ibridi sono tipicamente modellati come sistemi commutati (dove la regola di commutazione è indipendente dallo stato del sistema) o come sistemi affini a tratti (PWA), in cui la commutazione è associata alla transizione dello stato. La principale sfida nell'identificazione di sistemi ibridi risiede nella complessità combinatoria, poiché il numero di possibili meccanismi di commutazione (rappresentati dagli assegnamenti campione-modo) cresce esponenzialmente con la dimensione del dataset di addestramento. Inoltre, come evidenziato in letteratura, alcuni campioni sono "ambigui" e possono essere rappresentati con uguale efficacia da molteplici modelli locali. L'assegnazione di questi campioni basandosi esclusivamente sulle prestazioni di adattamento può talvolta introdurre outlier. Sebbene una classificazione errata di tali campioni ambigui non influenzi significativamente l'accuratezza delle stime dei modelli locali o delle loro prestazioni di adattamento, può compromettere gravemente la stima corretta del meccanismo di commutazione. In particolare, anche con modelli locali accurati, l'uso di un meccanismo di commutazione errato può portare a un comportamento del modello completamente insoddisfacente. Questa tesi affronta le sfide della complessità combinatoria e dell'ambiguità nella classificazione dei campioni associando cluster di campioni ai modi corretti, anziché adottare un approccio di assegnamento punto per punto. Questo riduce la complessità combinatoria (poiché i cluster sono molto meno numerosi dei singoli campioni) e minimizza l'impatto degli outlier (dato che i campioni ambigui sono influenzati da quelli non ambigui all'interno dello stesso cluster). In tutta la tesi, l'assegnamento cluster-modo è affrontato costantemente utilizzando un metodo randomizzato. Questo approccio consiste nell'estrarre assegnamenti potenziali da una distribuzione di probabilità, stimare e valutare i modelli locali sulla base dei sottoinsiemi di dati corrispondenti e aggiornare iterativamente la distribuzione per favorire gli assegnamenti con prestazioni migliori. Gli aggiornamenti continuano fino a quando la distribuzione converge verso una distribuzione limite centrata sull'assegnamento cluster-modo ottimale. Tuttavia, questo metodo è efficace solo se i cluster sono "puri" (cioè tutti i campioni in un cluster sono generati dallo stesso modo), il che motiva lo sviluppo di una procedura per affinare i cluster iniziali. Sono state sviluppate strategie di affinamento specifiche per i sistemi commutati e i sistemi PWA. Nel contesto dell'identificazione di sistemi commutati, si assume che la commutazione avvenga solo in istanti temporali fissi. Di conseguenza, i cluster sono rappresentati come insiemi di campioni all'interno di intervalli temporali definiti dalle posizioni di commutazione ipotizzate. Una soluzione proposta alterna tra l'assegnamento cluster-modo e l'affinamento dei cluster, formalizzando un approccio iterativo in due fasi. Poiché il metodo randomizzato per l'assegnamento cluster-modo è computazionalmente oneroso, è stata sviluppata anche una soluzione in una sola fase. Questo metodo stima contemporaneamente le posizioni di commutazione ed esegue l'assegnamento cluster-modo all'interno di un quadro randomizzato, eliminando la necessità di una fase di affinamento separata. Un terzo contributo è una soluzione distribuita progettata per gestire la crescente complessità combinatoria derivante da un numero elevato di cluster. Per i sistemi PWA, lo spazio degli stati è suddiviso in più regioni, ciascuna corrispondente alla regione operativa di un modo specifico. Assegnare un campione implica determinare il modo associato alla regione dello spazio degli stati corrispondente. I campioni che sono vicini nello spazio degli stati hanno quindi maggiori probabilità di appartenere allo stesso modo, portando alla formazione iniziale di cluster basati sulla prossimità spaziale. A differenza dei sistemi commutati, che si basano sulla divisione dell'orizzonte temporale, questi cluster sono definiti in uno spazio degli stati ad alta dimensionalità. Per gestire questa complessità, è stata sviluppata e integrata una procedura specializzata di affinamento dei cluster con il metodo randomizzato, formando un quadro di ottimizzazione alternata per l'assegnamento cluster-modo e l'affinamento dei cluster. L'analisi delle simulazioni mostra che questi metodi raggiungono un'elevata accuratezza di classificazione, sebbene con una lieve riduzione delle prestazioni di adattamento, consentendo un'analisi più precisa del meccanismo di commutazione.