State estimation in logical and stochastic discrete event systems

Abstract

This thesis studies state estimation in complex networked systems that are modeled as discrete event systems (DES) or stochastic discrete event systems (SDES). One of the main motivations for looking into state estimation problems is their crucial role in classification and fault diagnosis applications. Specifically, this thesis aims to explore the notions of detectability, diagnosability, and classification, using state estimation methods appropriate for DES and SDES. We pursue investigations of such problems in nondeterministic and probabilistic finite automata, under three di erent observation settings (namely, centralized, decentralized, and distributed). In particular, we explore diagnosability in distributed settings for nondeterministic finite automata under communication constraints. Furthermore, we introduce stochastic notions for the problems of detectability and diagnosability, and analyze the asymptotic behaviour of the resulting state estimation processes. Finally, we discuss the classification among two hidden Markov models (HMMs), and develop various methods for computing asymptotically tight bounds on the probability of misclassification, under established sufficient conditions.

Η παρούσα διδακτορική διατριβή μελετά τη διαδικασία της εκτίμησης κατάστασης (state estimation) σε πολύπλοκα διασυνδεδεμένα συστήματα, τα οποία μοντελοποιούνται σαν συστήματα διακριτών γεγονότων (discrete event systems) ή στοχαστικά συστήματα διακριτών γεγονότων (stochastic discrete event systems). Ένα από τα σημαντικά κίνητρα για να ασχοληθούμε με τα προβλήματα που σχετίζονται με την εκτίμηση κατάστασης, είναι ο σημαντικός ρόλος που διαδραματίζουν σε θεωρητικά προβλήματα, όπως την κατηγοριοποίηση (classification) και την ανίχνευση σφαλμάτων (fault diagnosis). Ιδιαίτερα, η παρούσα διατριβή έχει σκοπό της να εξερευνήσει τις έννοιες της ακριβούς εκτίμησης κατάστασης (detectability), της ανίχνευσης σφαλμάτων, και της κατηγοριοποίησης, χρησιμοποιώντας τεχνικές εκτίμησης κατάστασης, κατάλληλες για συστήματα διακριτών γεγονότων και στοχαστικά συστήματα διακριτών γεγονότων. Ερευνούμε αυτά τα προβλήματα σε μη ντετερμινιστικά και στοχαστικά πεπερασμένα αυτόματα, σε τρεις διαφορετικές περιπτώσεις (συγκεκριμένα, μονολιθικά, αποκεντρωμένα και κατανεμημένα συστήματα). Ειδικότερα, ερευνούμε την έννοια της ανίχνευσης σφαλμάτων σε κατανεμημένα συστήματα, για μη- ντετερμινιστικά πεπερασμένα αυτόματα, σε συνθήκες περιορισμένης επικοινωνίας. Επίσης, εισάγουμε και επαληθεύουμε στοχαστικές έννοιες για τα προβλήματα της ακριβούς εκτίμησης κατάστασης και ανίχνευσης σφαλμάτων αναλύοντας την ασυμπτωτική συμπεριφορά των συστημάτων. Τέλος, προτείνουμε και συζητούμε διάφορες μεθόδους στο πρόβλημα της κατηγοριοποίησης σε κρυφά μαρκοβιανά μοντέλα (hidden Markov models). Αναπτύσσουμε διάφορες μεθόδους υπολογισμού ανωτάτων ορίων για την πιθανότητα λάθους κατηγοριοποίησης, που ασυμπτωτικά τείνουν στο μηδέν, κάτω από καθορισμένες ικανές συνθήκες.