La compétitivité des entreprises manufacturières dépend fortement de la productivité des machines etdes moyens de production. Pour garantir un haut niveau de productivité il est indispensable de minimiser lestemps d'arrêt dus aux fautes ou dysfonctionnements. Cela nécessite des méthodes efficaces pour détecter et isolerles fautes apparues dans un système (FDI). Dans cette thèse, une méthode FDI à base de modèles est proposée.La méthode est conçue pour la classe des systèmes à événements discrets industriels composés d'une bouclefermée du contrôleur et du processus. En comparant les comportements observés et attendus par le modèle, il estpossible de détecter et d'isoler des fautes. A la différence de la plupart des approches FDI des systèmes àévénements discrets, une méthode basée sur des modèles du comportement normal au lieu de modèles descomportements fautifs est proposée. Inspiré par le concept des résidus bien connu pour le diagnostic dessystèmes continus, une nouvelle approche pour l'isolation des fautes dans les systèmes à événements discrets aété développée. La clé pour l'application des méthodes FDI basées sur des modèles est d'avoir un modèle justedu système considéré. Comme une modélisation manuelle peut être très laborieuse et coûteuse pour dessystèmes à l'échelle industrielle, une approche d'identification pour les systèmes à événements discrets enboucle fermée est développée. Basée sur un algorithme connu pour l'identification des modèles monolithiques,une adaptation distribuée est proposée. Elle permet de traiter de grands systèmes comportant un haut degré deparallélisme. La base de cette approche est une décomposition du système en sous systèmes. Cettedécomposition est automatisée en utilisant un algorithme d'optimisation analysant le comportement observé dusystème. Les méthodes conçues dans cette thèse ont été mises en oeuvre sur une étude de cas et sur uneapplication d'échelle industrielle.

La planification est un domaine de l'intelligence artificielle qui a pour but de proposer des méthodes permettant d'automatiser la recherche et l'ordonnancement d'ensembles d'actions afin d'atteindre un objectif donné. Un ensemble ordonné d'actions solution d'un problème de planification est appelé un plan. Parfois, les actions disponibles peuvent avoir un coût - on souhaite alors trouver des plans minimisant la somme des coûts des actions les constituant. Ceci correspond en fait à la recherche d'un chemin de coût minimal dans un graphe, et est donc traditionnellement résolu en utilisant des algorithmes tels que A*. Dans cette thèse, nous nous intéressons à une approche particulière de la planification, dite factorisée ou modulaire. Il s'agit de décomposer un problème en plusieurs sous-problèmes (généralement appelés composants) le plus indépendants possibles, et d'assembler des plans pour ces sous-problèmes en un plan pour le problème d'origine. L'intérêt de cette approche est que, pour certaines classes de problèmes de planification, les composants peuvent être bien plus simples à résoudre que le problème initial. Dans un premier temps, nous présentons une méthode de planification factorisée basée sur l'utilisation d'algorithmes dits à passage de messages. Une représentation des composants sous forme d'automates à poids nous permet de capturer l'ensemble des plans d'un sous-problème, et donc de trouver des plans de coût minimal, ce que ne permettaient pas les approches précédentes de la planification factorisée. Cette première méthode est ensuite étendue~: en utilisant des algorithmes dits « turbos », permettant une résolution approchée des problèmes considérés, puis en proposant une représentation différente des sous-problèmes, afin de prendre en compte le fait que certaines actions ne font que lire dans un composant. Ensuite, nous proposons une autre approche de la planification factorisée, basée sur une version distribuée de l'algorithme A*. Dans chaque composant, un agent réalise la recherche d'un plan local en utilisant sa connaissance du sous-problème qu'il traite, ainsi que des informations transmises par les autres agents. La principale différence entre cette méthode et la précédente est qu'il s'agit d'une approche distribuée de la planification modulaire. / Automated planning is a field of artificial intelligence that aims at proposing methods to chose and order sets of actions with the objective of reaching a given goal. A sequence of actions solving a planning problem is usually called a plan. In many cases, one does not only have to find a plan but an optimal one. This notion of optimality can be defined by assigning costs to actions. An optimal plan is then a plan minimizing the sum of the costs of its actions. Planning problems are standardly solved using algorithms such as A* that search for minimum cost paths in graphs. In this thesis we focus on a particular approach to planning called factored planning or modular planning. The idea is to consider a decomposition of a planning problem into almost independent sub-problems (or components). One then searches for plans into each component and try to assemble these local plans into a global plan for the original planning problem. The main interest of this approach is that, for some classes of planning problems, the components considered can be planning problems much simpler to solve than the original one. First, we present a study of the use of some message passing algorithms for factored planning. In this case the components of a problem are represented by weighted automata. This allows to handle all plans of a sub-problems, and permits to perform factored cost-optimal planning. Achieving cost-optimality of plans was not possible with previous factored planning methods. This approach is then extended by using approximate resolution techniques ("turbo" algorithms) and by proposing another representation of components for handling actions which read-only in some components. Then we describe another approach to factored planning: a distributed version of the famous A* algorithm. Each component is managed by an agent which is responsible for finding a local plan in it. For that, she uses information about her own component, but also information about the rest of the problem, transmitted by the other agents. The main difference between this approach and the previous one is that it is not only modular but also distributed.

Cette thèse porte sur la synthèse de superviseurs pour des systèmes a événements discrets temps-réel (SEDTRs) modélisés par des automates temporises (ATs). Comme l'espace d'états d'un AT est en général infini, et que la théorie du contrôle supervise de RAMADGE et WONHAM, que nous avons adaptée, est opérationnelle pour des automates a états finis (AEFs), nous avons utilisé l'approche consistant à transformer les ATs modélisant le procédé et la spécification sous la forme d'AEFs. Nous avons donc tout d'abord étendu et amélioré une méthode de transformation des ATs en AEFs particuliers appelés automates Set-Exp (ASEs). Cette méthode de transformation, appelée SetExp, permet de réduire le problème d'explosion des états et est appropriée pour le contrôle supervise de SEDTRs. Nous avons ensuite amélioré et étendu une méthode de contrôle centralise fondée sur SetExp, c'est-à-dire que les ATs modélisant le procédé et la spécification sont d'abord transformes en ASEs et le problème est résolu en adaptant la théorie de RAMADGE et WONHAM aux ASEs. Pour la résolution du problème de contrôle centralise, nous avons identifié les conditions d'existence de solution et avons proposé une procédure algorithmique pour la synthèse du superviseur le moins restrictif. Suite à cela, nous avons développé une méthode de contrôle modulaire, fondée sur SetExp et la méthode de contrôle centralise. Pour le contrôle modulaire également, nous avons identifié les conditions d'existence de solution et propose une procédure de synthèse de superviseurs modulaires les moins restrictifs. D'autre part, nous avons étendu la méthode de contrôle centralise fondée sur SetExp au cas où le superviseur a une observation partielle des événements du procédé. Pour cette méthode de contrôle sous observation partielle des événements, nous avons identifié les conditions d'existence de solution et propose une procédure pour synthétiser un superviseur sous observation partielle. Enfin, nous avons réalisé un outil logiciel appelé SEAtool, qui implémente la transformation SetExp et les méthodes de contrôle centralise et modulaire. Nous avons étudié, à l'aide de SEAtool, l'application de nos méthodes de contrôles centralise et modulaire a des systèmes concrets simples.

La compétitivité des entreprises manufacturières dépend fortement de la productivité des machines etdes moyens de production. Pour garantir un haut niveau de productivité il est indispensable de minimiser lestemps d'arrêt dus aux fautes ou dysfonctionnements. Cela nécessite des méthodes efficaces pour détecter et isolerles fautes apparues dans un système (FDI). Dans cette thèse, une méthode FDI à base de modèles est proposée.La méthode est conçue pour la classe des systèmes à événements discrets industriels composés d’une bouclefermée du contrôleur et du processus. En comparant les comportements observés et attendus par le modèle, il estpossible de détecter et d’isoler des fautes. A la différence de la plupart des approches FDI des systèmes àévénements discrets, une méthode basée sur des modèles du comportement normal au lieu de modèles descomportements fautifs est proposée. Inspiré par le concept des résidus bien connu pour le diagnostic dessystèmes continus, une nouvelle approche pour l’isolation des fautes dans les systèmes à événements discrets aété développée. La clé pour l’application des méthodes FDI basées sur des modèles est d’avoir un modèle justedu système considéré. Comme une modélisation manuelle peut être très laborieuse et coûteuse pour dessystèmes à l’échelle industrielle, une approche d’identification pour les systèmes à événements discrets enboucle fermée est développée. Basée sur un algorithme connu pour l’identification des modèles monolithiques,une adaptation distribuée est proposée. Elle permet de traiter de grands systèmes comportant un haut degré deparallélisme. La base de cette approche est une décomposition du système en sous systèmes. Cettedécomposition est automatisée en utilisant un algorithme d’optimisation analysant le comportement observé dusystème. Les méthodes conçues dans cette thèse ont été mises en oeuvre sur une étude de cas et sur uneapplication d’échelle industrielle. / The competitiveness of manufacturing companies strongly depends on the productivity of machinesand production processes. To guarantee a high level of productivity, downtimes occurring due to faults have tobe kept as short as possible. This necessitates efficient fault detection and isolation (FDI) methods. In this work,a model-based FDI method for the widely used class of industrial closed-loop Discrete Event Systems isproposed. The considered systems consist of the closed-loop of plant and controller. Based on the comparison ofobserved and modeled system behavior, it is possible to detect and to isolate faults. Unlike most known methodsfor FDI in Discrete Event Systems, this work proposes working with a model of the fault-free behavior ratherthan working fault models. Inspired by the concept of residuals known from FDI in continuous systems, a newapproach for fault isolation based on fault-free Discrete Event System models is developed. The key of anymodel-based diagnosis method is to have an accurate model of the considered system. Since manual modelbuildingcan be very difficult for large industrial systems, an identification approach for this class of systems isintroduced. Based on an already existing monolithic identification algorithm, a distributed adaptation isdeveloped which allows treating large, concurrent systems. The key of the proposed approach is an automaticdecomposition of a given closed-loop Discrete Event System using an optimization approach which analyzesobserved system behavior. The methods developed in this thesis are applied to a mid-sized laboratory system andto an industrial winder to show their scalability.

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.

Ce mémoire de thèse prèsente une approche pour la surveillance des systèmes à événements discrets commandés. L'étude se restreint aux défauts interruptibles : intermittents et permanents. Le comportement acceptable de ces systèmes est introduit afin d'accroître la disponibilité des systèmes commandés. Ce comportement présente une tolérance aux défauts intermittents. Une démarche de construction du système de surveillance est présentée. Nous modélisons, dans un premier temps, le comportement du système sujet aux défauts interruptibles par un automateà chronomètres. Nous appliquons, dans un deuxième temps, une procédure de synthèse à cet automate. Cette procédure est basée aux opérateurs d'analyse en avant et en arriérer de l'automate. Un nouveau modèle appelé réseaux de Petri à chronomètres post- et Pré-initialisés est également présenté. Ce modèle général du RdP a été utilisé, dans le cadre de ce mémoire, pour modéliser le comportement des systèmes sujets aux défauts interruptibles. L'implémentation de notre méthode de surveillance se fait par un automate programmable industriel. Pour ce faire, le système de surveillance étant sous la forme d'un automate àchronomètres est traduit structurellement en programme SFC.

Nous nous intéressons au diagnostic de systèmes à événements discrets modélisés par un automate. Pour pouvoir prendre en compte des observations incertaines, nous les représentons sous la forme d'un automate. Le diagnostic est alors défini comme la synchronisation des deux automates. Pour permettre un calcul incrémental et en-ligne du diagnostic, nous définissons une structure appelée chaîne d'automates qui représente les observations par périodes appelées fenêtres.<br />Le diagnostic peut s'effectuer sur chacune de ces périodes, et on peut raffiner le résultat en vérifiant l'égalité entre l'état final d'une fenêtre et l'état initial de la suivante. Puisque le modèle global d'un système réel est trop grand pour être calculé, nous avons adapté les techniques de diagnostic décentralisé à notre approche. Enfin, nous avons étendu nos résultats aux systèmes reconfigurables, c'est-à-dire dont certains composants ainsi que les connexions entre ceux-ci peuvent être ajoutés, modifiés ou supprimés.

Ce manuscrit a été rédigé en vue d'obtenir l'habilitation à diriger des recherches. J'y présente mon implication dans l'enseignement supérieur et la recherche au sein de l'Université d'Angers depuis mon recrutement en tant que maître de conférences, et plus précisément en tant qu'enseignant à l'ISTIA et en tant que chercheur au LISA. Au LISA, dirigé par Jean-Louis Ferrier au moment de mon recrutement, j'ai intégré l'équipe Modèles et Systèmes Dynamiques. Mon travail de recherche a profité des interactions avec les différents membres de cette équipe, et en particulier avec Jean-Louis Boimond (comme le laisseront apparaître les références dans la suite de ce manuscrit). Il concerne le comportement temporisé des systèmes à événements discrets en utilisant des modèles définis sur une structure algébrique de semi-anneau idempotent, encore appelée dioïde. Le document est structuré de la manière suivante. - Le premier chapitre présente mon curriculum vitae ainsi qu'un survol général de mes activités de recherche. - Le deuxième chapitre fait une synthèse plus détaillée de travaux motivés par deux préoccupations principales durant ces onze dernières années : élargir la classe des modèles relevant de la théorie des systèmes sur l'algèbre des dioïdes ; appliquer les résultats de la théorie des systèmes sur les dioïdes à l'analyse des systèmes de transport. En annexe, trois publications sont jointes pour que le lecteur puisse trouver plus de détails sur ces travaux. - Dans le troisième et dernier chapitre, je tire un bilan et envisage des perspectives à mes travaux.

Dans ce travail, nous proposons une méthode systématique et facile de mise en œuvre pour la synthèse du contrôle des systèmes à événements discrets. Nous modélisons les systèmes par des modèles RdP saufs. Deux idées distinctes sont utilisées : 1) ajout de places de contrôle pour empêcher l'atteignabilité des états interdits, et 2) ajout de conditions pour les transitions contrôlables. Nous avons alors été confrontés au problème des transitions incontrôlables pour garantir l'optimalité et à la complexité apportée par le nombre des places de contrôles qui peut être très grand. <br />Dans la première idée, nous avons utilisé le théorème introduit par Guia, qui permet de passer d'un ensemble d'états interdits vers un ensemble de contraintes linéaires. Nous avons proposé des méthodes originales de simplification des contraintes. Il est alors possible de réduire le nombre et la borne des contraintes et ainsi de construire un modèle contrôlé simple. Les méthodes de simplification présentées sont applicables sur les RdP saufs. Nous avons déterminé les conditions nécessaires et suffisantes pour avoir un contrôleur maximal permissif. L'avantage principal de ces méthodes de synthèse de contrôleurs est que le modèle RdP contrôlé est très proche du modèle initial. <br />La deuxième idée qui a été utilisée pour la synthèse est l'utilisation des conditions pour le franchissement des transitions contrôlables. Les méthodes qui utilisent cette technique, ont en général besoin d'un calcul long en temps réel. En appliquant notre méthode de simplification, nous arrivons à un contrôleur simple.

Les systèmes à événements discrets qui mettent en jeu des phénomènes de synchronisation possèdent une description linéaire dans l'algèbre (max,+). Une théorie des systèmes linéaires dans les dioïdes, développée par analogie à la théorie conventionnelle des systèmes, a alors vu le jour. Dans ce mémoire, nous abordons des problèmes de commande des systèmes (max,+)-linéaires. Jusque-là, les commandes de systèmes linéaires dans les dioïdes ont principalement considéré le critère du juste-à-temps et des objectifs de commande comme la poursuite d'une trajectoire de référence ou la poursuite d'un transfert de référence. La première contribution à la commande réside dans la prise en compte d'un nouvel objectif pour la commande en juste-à-temps. Plus précisément, on considère des spécifications sous la forme de contraintes sur l'état du système. Ensuite, nous abordons un nouveau critère de commande. On s'intéresse à la synthèse d'un correcteur qui ralentit le moins possible le transfert du système tout en assurant un objectif de commande défini par un ensemble de contraintes sur l'état. Les réseaux de transport admettent une description linéaire dans l'algèbre (max,+). La dernière partie de ce mémoire est consacrée à leur étude. Plus précisément, on propose des outils pour l'évaluation de performances et la commande de ces systèmes. Le problème de synthèse de tables d'horaires est notamment formulé en un problème de commande de système (max,+)-linéaire.