L'espérance de vie a augmenté dans les dernières décennies et devrait continuer à croître dans les prochaines années. Cette augmentation entraîne de nouveaux défis concernant l'autonomie et l'indépendance des personnes âgées. Le développement d'habitats intelligents est une piste pour répondre à ces défis et permettre aux personnes de vivre plus longtemps dans un environnement sûr et confortable. Rendre un habitat intelligent consiste à y installer des capteurs, des actionneurs et un contrôleur afin de pouvoir prendre en compte le comportement de ses habitants et agir sur leur environnement, pour améliorer leur sécurité, leur santé et leur confort. La plupart de ces approches s'appuient sur la localisation en temps réel des habitants dans leur habitat. Dans cette thèse, une nouvelle approche complète permettant la localisation d'un nombre a priori inconnu d'habitants basée sur le modèle est proposée. Cette approche tire parti des paradigmes, de la théorie et des outils des Systèmes à Événements Discrets. L'utilisation des automates à états finis pour modéliser le mouvement détectable des habitants ainsi que des méthodes permettant de construire ces modèles ont été développées. A partir de ces modèles automates finis, plusieurs algorithmes permettant de localiser de manière efficace les habitants ont été définis. Enfin, plusieurs approches pour l'évaluation des performances de l'instrumentation d'un habitat intelligent pour un objectif de localisation ont été proposées. La méthode a également été totalement implémentée et mise à l'épreuve. Tout au long de cette thèse, les différentes contributions sont illustrées à l'aide de cas d'étude. / Life expectancy has continuously increased in most countries over the last decades and will probably continue to increase in the future. This leads to new challenges relative to the autonomy and the independence of elderly. The development of Smart Homes is a direction to face these challenges and to enable people to live longer in a safe and comfortable environment. Making a home smart consists in placing sensors, actuators and a controller in the house in order to take into account the behavior of their inhabitants and to act on their environment to improve their safety, health and comfort. Most of these approaches are based on the real-time indoor Location Tracking of the inhabitants. In this thesis, a whole new approach for model-based Location Tracking of an a priori unknown number of inhabitants is proposed. This approach is based on Discrete Event Systems paradigms, theory and tools. The usage of Finite Automata (FA) to model the detectable motion of the inhabitants as well as different methods to create such FA models have been developed. Based on these models, algorithms to perform efficient Location Tracking are defined. Finally, several approaches aiming at evaluating the relevance of the instrumentation of a Smart Home with the objective of Location Tracking are proposed. The approach has also been fully implemented and tested. Throughout the thesis, the different contributions are illustrated on case studies. / In den meisten Industrieländern ist die Lebenserwartung in den letzten Jahrzehnten fortlaufend gestiegen und wird höchstwahrscheinlich noch weiter steigen. Dieser Anstieg führt zu neuen Herausforderungen hinsichtlich der Autonomie und Unabhängigkeit von älteren Menschen. Die Entwicklung von intelligenten Wohnungen ist ein Weg diesen Herausforderungen zu begegnen und es den Menschen zu ermöglichen länger in einer sicheren und komfortablen Umgebung zu leben. Dazu stattet man solcheWohnungen mit Sensoren, Aktoren sowie einem Controller aus. Dies erm öglicht es, in Abhängigkeit vom Verhalten der Bewohner, dieWohnumgebung so zu beein_ussen, dass sich Sicherheit, Gesundheit und Komfort verbessern. Ansätze, die dies zum Ziel haben, basieren meistens auf Methoden, die es ermöglichen Menschen innerhalb ihrer Wohnung in Echtzeit zu lokalisieren. In dieser Dissertation wird daher ein neuer Ansatz für eine modellbasierte Lokalisierung einer a priori unbekannten Anzahl von Bewohnern vorgestellt. Dieser Ansatz fuÿt auf der Theorie, den Paradigmen und den Werkzeugen aus dem Gebiet der ereignisdiskreten Systeme. Es werden endliche Automaten eingesetzt, um die von den Sensoren erfassbaren Bewohnerbewegungen zu modellieren. Verschiedene Verfahren zur Erzeugung solcher Automaten werden gezeigt. Basierend auf diesen Modellen warden Algorithmen de_niert, mittels derer die Bewohner wirksam lokalisiert werden können. Abschlieÿend werden Methoden vorgeschlagen, die dazu dienen die Relevanz der Sensorinstrumentierung für die Lokalisierung zu bewerten. Die entwickelten Verfahren werden in der Dissertation durchgehend anhand von Fallbeispielen erläutert. Der gesamte Ansatz wurde implementiert und erprobt.

Fault isolation is the process of reasoning required to find the cause of a system failure. In a model-based approach, the available information is a model of the system and some observations. Using knowledge of how the system generally behaves, as given in the system model, together with partial observations of the events of the current situation the task is to deduce the failure causing event(s). In our setting, the observable events manifest themselves in a message log. We study post mortem fault isolation for moderately concurrent discrete event systems where the temporal order of logged messages contains little information. To carry out fault isolation one has to study the correlation between observed events and fault events of the system. In general, such study calls for exploration of the state space of the system, which is exponential in the number of system components. Since we are studying a restricted class of all possible systems we may apply aggressive specialized abstraction policies in order to allow fault isolation without ever considering the often intractably large state space of the system. In this thesis we describe a mathematical framework as well as a prototype implementation and an experimental evaluation of such abstraction techniques. The method is efficient enough to allow for not only post mortem fault isolation but also design time diagnosability analysis of the system, which can be seen as a non-trivial way of analyzing all possible observations of the system versus the corresponding fault isolation outcome. This work has been supported by VINNOVA’s Competence Center ISIS.

Life expectancy has continuously increased in most countries over the last decades and will probably continue to increase in the future. This leads to new challenges relative to the autonomy and the independence of elderly. The development of Smart Homes is a direction to face these challenges and to enable people to live longer in a safe and comfortable environment. Making a home smart consists in placing sensors, actuators and a controller in the house in order to take into account the behavior of their inhabitants and to act on their environment to improve their safety, health and comfort. Most of these approaches are based on the real-time indoor Location Tracking of the inhabitants. In this thesis, a whole new approach for model-based Location Tracking of an a priori unknown number of inhabitants is proposed. This approach is based on Discrete Event Systems paradigms, theory and tools. The usage of Finite Automata (FA) to model the detectable motion of the inhabitants as well as different methods to create such FA models have been developed. Based on these models, algorithms to perform efficient Location Tracking are defined. Finally, several approaches aiming at evaluating the relevance of the instrumentation of a Smart Home with the objective of Location Tracking are proposed. The approach has also been fully implemented and tested. Throughout the thesis, the different contributions are illustrated on case studies.

It is well known that the optimal nonblocking supervisory control problem of timed discrete event systems is NP-hard, subject in particular to state space explosion that is exponential in the number of system components. In this thesis, we propose to manage complexity by organizing the system as a Timed State Tree Structure (TSTS). TSTS are an adaptation of STS to timed Supervisory Control Theory (SCT). Based on TSTS we present an e±cient recursive symbolic algorithm that can perform nonblocking supervisory control design for systems of state size 10^12 and higher. Failure diagnosis is the process of detecting and identifying deviations of a system from its normal behavior using the information available through sensors. A method for fault diagnosis of the TSTS model is proposed. A state based diagnoser is constructed for each timed holon of TSTS. Fault diagnosis is accomplished using the state estimates provided by the timed holon diagnosers. The diagnosers may communicate among each other in order to update their state estimates. At any given time, only a subset of the diagnosers are operational, and as a result, instead of the entire model of the system, only the models of the timed holons associated with the operational diagnosers are used. It is shown that the computational complexity of constructing and storing the transition systems required for diagnosis in the proposed approach is polynomial in the number of system components, whereas in the original monolithic approach the computational complexity is exponential.

It is well known that the optimal nonblocking supervisory control problem of timed discrete event systems is NP-hard, subject in particular to state space explosion that is exponential in the number of system components. In this thesis, we propose to manage complexity by organizing the system as a Timed State Tree Structure (TSTS). TSTS are an adaptation of STS to timed Supervisory Control Theory (SCT). Based on TSTS we present an e±cient recursive symbolic algorithm that can perform nonblocking supervisory control design for systems of state size 10^12 and higher. Failure diagnosis is the process of detecting and identifying deviations of a system from its normal behavior using the information available through sensors. A method for fault diagnosis of the TSTS model is proposed. A state based diagnoser is constructed for each timed holon of TSTS. Fault diagnosis is accomplished using the state estimates provided by the timed holon diagnosers. The diagnosers may communicate among each other in order to update their state estimates. At any given time, only a subset of the diagnosers are operational, and as a result, instead of the entire model of the system, only the models of the timed holons associated with the operational diagnosers are used. It is shown that the computational complexity of constructing and storing the transition systems required for diagnosis in the proposed approach is polynomial in the number of system components, whereas in the original monolithic approach the computational complexity is exponential.

The aim of this study is to solve Fault Detection and Diagnosis (FDD) problems occurring in nonlinear dynamical systems by using model and knowledge-based FDD methods and to give a priority and a degree about faults. For this purpose, three model-based FDD approaches, called FDD by utilizing principal component analysis (PCA), system identification based FDD and inverse model based FDD are introduced. Performances of these approaches are tested on different nonlinear dynamical systems starting from simple to more complex. New fuzzy discrete event system (FDES) and fuzzy discrete event dynamical system (FDEDS) concepts are introduced and their applicability to an FDD problem is investigated. Two knowledge-based FDD methods based on FDES and FDEDS structures using a fuzzy rule-base are introduced and they are tested on nonlinear dynamical systems. New properties related to FDES and FDEDS such as fuzzy observability and diagnosibility concepts and a relation between them are illustrated. A dynamical rule-base extraction method with classification techniques and a dynamical and a static diagnoser design methods are also introduced. A nonlinear and event based extension of the Luenberger observer and its application as a diagnoser to isolate faults are illustrated. Finally, comparisons between the proposed model and knowledge-based FDD methods are made.

Depuis plusieurs années, de nombreuses recherches ont été menées autour du diagnostic. Cependant, il est impératif de se préoccuper dès la phase de conception d’un système des objectifs de diagnostic à atteindre. Aussi, de nombreux travaux se sont intéressés à analyser et à caractériser les propriétés de la diagnosticabilité d’un système. La diagnosticabilité est la propriété d’un système garantissant qu’il génère des observations permettant de détecter et discriminer les fautes en temps fini après leur occurrence.Le sujet de cette thèse porte sur les méthodes permettant d’établir les propriétés de la diagnosticabilité des systèmes à événements discrets dans le cadre distribué, sans construction du modèle global du système. Ce cadre est de première importance pour les applications réelles : systèmes naturellement distribués, systèmes trop complexes pour traiter leur modèle global, confidentialité des modèles locaux les uns par rapport aux autres. L’analyse de la diagnosticabilité de tels systèmes distribués se fonde sur des opérations de synchronisation des modèles locaux, par les observations et les communications. D’abord, nous étudions comment optimiser cette analyse de la diagnosticabilité en faisant abstraction de l’information nécessaire et suffisante à partir des objets locaux pour décider la diagnosticabilité globale. L'efficacité de l’algorithme peut être grandement améliorée par la synchronisation des objets locaux et abstraits en comparaison avec celle des objets locaux et non abstraits.Ensuite, nous proposons, dans le cadre distribué, l'algorithme de la diagnosticabilité de motifs d'événements particuliers a priori inobservables dans les systèmes. Ces motifs peuvent être simplement l’occurrence, brutale ou graduelle, d’une faute permanente ou transitoire, plusieurs occurrences d’une faute, plusieurs fautes en cascade, etc. Dans le cadre distribué, la reconnaissance du motif d’événements s’effectue d’abord progressivement dans un sous-système et ensuite la diagnosticabilité de ce motif peut être déterminée par la méthode abstraite et distribuée. Nous prouvons la correction et l'efficacité de notre algorithme à la fois en théorie et en pratique par la mise en œuvre de l’implémentation sur des exemples.Finalement, nous étudions le problème de la diagnosticabilité dans les systèmes distribués avec composants autonomes, où l’information observable est distribuée au lieu d’être centralisée comme jusqu’alors. En d'autres termes, chaque composant ne peut appréhender que ses propres événements observables. Nous donnons la définition de la diagnosticabilité conjointe. Et puis nous discutons de l'indécidabilité de diagnosticabilité conjointe dans le cas général, c'est à dire, les événements de communication ne sont pas observables, avant de proposer un algorithme pour tester sa condition suffisante. De plus, nous obtenons également un résultat de décidabilité et de l'algorithme lorsque les communications sont observables. / Over the latest decades, much research work has been done on automatic fault diagnosis. However, it is imperative to analyze at system design stage how correctness and efficiency and diagnosis algorithm can achieve. Thus many studies were interested in analyzing and characterizing the properties of diagnosability of a system. Diagnosability is the property of a system ensuring that it generates observations for detecting and discriminating faults in finite time after their occurrence.In this thesis, we investigate how to optimize distributed diagnosability analysis by abstracting necessary and sufficient information from local objects to decide global diagnosability decision. The algorithm efficiency can be greatly improved by synchronization of abstracted local objects compared to that of non abstracted local ones.Then we extend the distributed diagnosability algorithm from fault event first to simple pattern and then to general pattern, where pattern can describe more general objects in the diagnosis problem, e.g., multiple faults, multiple occurrences of the same fault, ordered occurrences of significant events, etc. In the distributed framework, the pattern recognition is first incrementally performed normally in a subsystem and then pattern diagnosability can be determined by adjusting abstracted method used in fault event case. We prove the correctness and efficiency of our proposed algorithm both in theory through proof and in practice through implementation.Finally we study joint diagnosability problem in systems with autonomous components, i.e., observable information is distributed instead of centralized. In other words, each component can only observe its own observable events. We give joint diagnosability definition. And then we discuss the undecidability of joint diagnosability in the general case, i.e., communication events are not observable, before proposing an algorithm to test its sufficient condition. In addition, we also get a decidability result and algorithm when communications are observable.

Les modèles à événements discrets sont, souvent, réalisés afin d’être simulés et par conséquent exécutés sur ordinateur.Certains codeurs de simulation optent pour une programmation impérative pour implémenter les comportements décrits par leurs machines à états.D’autres codeurs optent plutôt pour une programmation orientée objet.Ce paradigme de programmation, basé sur la notion d’objet, décline une nouvelle façon de voir un programme et son architectureToutes les solutions proposées manquent de clarté.Elles sont extrêmement coûteuses en terme de maintenabilité du code implémenté.L’utilisation exclusive des instructions conditionnelles rend toute correction au niveau du code difficile à réaliser, voire impossible dans certains cas. Aussi, elles souffrent au niveau de la réutilisabilité d’une partie du code. En effet, l’utilisation de telles instructions produit un code compacte, avec une forte cohésion entre les variables et fonctions du modèle implémenté. Par conséquent, le concepteur pourra réutiliser ce code qu’en un seul bloc.Toute dislocation du code est impossiblePour toutes ces raisons, nous proposons une nouvelle conception des modèles à événements discrets afin d’améliorer les qualités du code produit. Cette solution est basée sur le paradigme objet pour exploiter pleinement ses avantages tout en contournant ses limites. A cet effet, la solution proposée et détaillée dans cette thèse est un nouveau patron. Dans ce patron, les états et les événements sont réifiés pour avoir plus d’abstraction et de clarté. La réification permettra aux événements d’encapsuler des données et des comportements. Ainsi, nous pouvons déléguer aux événements de nouvelles responsabilités / Discrete event systems (State machine or Discrete Event system Specification) are often modeled in order to be simulated and therefore executed on a computer. Some simulation designers choose for imperative programming to implement the behaviors described by their state machines and others. Whereas, few of them choose for object-oriented programming: this paradigm of computer programming, based on the notion of object, declines a new way of seeing a program and its architecture.All of the proposed solutions found in the litterature lack clarity. They are extremely expensive in terms of debugging, reusing and changing the implemented model. The exclusive use of conditional statements if-else or switch case makes any code correction difficult to perform, even impossible in some cases. They also suffer from the reusability of some parts of the code. Indeed, the use of such instructions produces a compact code, with a strong cohesion (coupling) between the variables and functions of the implemented model. Therefore, the designer can reuse the corresponding code only in one block. Any extraction of a a piece of code which corresponds to a piece of behavior is impossible.For all these reasons, we propose a new design of discrete event systems, from the state machine to the DEVS, in order to improve the producted code qualities. This solution is based on the object paradigm to fully exploit its advantages while circumventing its limits. To this end, the solution proposed and detailed in this thesis is a new State-Event Design Pattern and its variants. Thus, the designer of simulation models will have a library of patterns to choose in order to satisfy his design requirements.

Neste trabalho à apresentada uma proposta de conversÃo de modelos de cÃlulas de manufatura (FMS) em Redes de Petri Coloridas (RPC) para Ladder Logic Diagram (LLD). Explora-se modelos de RPC controlados - construidos usando-se como metodologia de controle supervisÃrio as RestriÃÃes de Controle sobre Cores Decompostas (RCCD) - e modelos nÃo controlados. Enfatiza-se a transformaÃÃo de RPC nÃo controlada para LLD e a facilidade de inclusÃo do controle. Os resultados aqui descritos demonstram que a metodologia facilita o trabalho de um programador de CLP em LLD minimizando os possÃveis erros durante a fase de programaÃÃo. Para exemplificar a metodologia foi desenvolvido um conversor de RPC para LLD, produzido em ambiente JAVA, afim de evidenciar a dinÃmica de conversÃo. Para a validaÃÃo dos resultados do conversor à usado um robà articulado vertical controlado via CLP, que opera comparativamente com e sem supervisÃo, o qual fora modelado primeiramente em RPC sem supervisÃo, depois aplicada a tÃcnica RCCD, a supervisÃo e a conversÃo para LLD. / In this dissertation, is presented a proposal of conversion of models of manufacturing cell (FMS) from Colored Petri Nets (CPN) to Ladder Logic Diagram (LLD). It explores the controlled CPN models - constructed using the methodology of supervisory Control Restrictions on Decomposed Colors (CRDC) - and not controlled models. It emphasizes the transformation of CPN not controlled for the LLD and ease for inclusion of control. The results described herein demonstrate that the methodology facilitates the work of a PLC programmer in LLD minimizing possible errors during the programming phase. To illustrate the methodology we developed a converter from CPN to LLD, produced in JAVA, in order to clarify the dynamic conversion environment. To validate the results of the converter, is controlled by PLC, a vertical articulated robot which works compared with and without supervision which had been firstly modeled in CPN without supervision, then applied to CRDC, the supervision and the conversion technique for LLD.

This master’s thesis deals with analysis of state machines for embedded applications. The issue of finite-state machine is described theoretically. The document also contains a proposal for funding for modeling finite state machines in Matlab/Simulink. It is designed data representation of finite automaton. Over this data representation algorithm of minimization is applied. Finally, the algorithm is implemented to generate code in C language.