Search

Wireless Sensor networks are attracted many activities of research and development during the last decade. Yet, the distributed behavior of a WSN remains centered on two main objectives: sensing and routing. This thesis advocates the introduction of an additional feature, which can be considered interesting from a functional point of view and potentially from the power consumption one: starting from a designer-specified requirement, implement a multiple level synergy between (groups of) nodes, based on adequate interaction. This is achieved by automatic generation and distribution of correct-by-construction code, relying on the Supervisory Control Theory. The Discrete Controller Synthesis (DCS) technique is an application of this theoretic framework. In this thesis, we show how DCS can be used for WSN. Thus, its potential is at two levels. The intra-cluster scheduling of a redundant group of sensors with specifications expressing the mutual exclusion during the activation of a sensor within a cluster, essential to save the energy within the network and then a multicriteria automatic generation of an optimal routing functionality. Specifically, an optimal path should have both a minimal length and go through nodes having maximal residual energy. The cited formal tools lean on a modelling approach based on communicating finite state machines (CFSM). The scientific challenges are generally related to the nature of the WSN as well as to its size. The DCS can only generates a monoblock controllers, while the WSN’s behavior is essentially distributed. The issue is how to distribute a global controller, who appears in the form of a logical constraint expressed on the global state of the network, into local controllers while adding the necessary synchronization to guarantee a distributed functioning equivalent to the initially generated controller.; Les réseaux de capteurs sans fil ont attiré beaucoup d’activités de recherche et développement au cours de la dernière décennie. Pourtant, leur utilisation est restreinte, à ce jour, à la surveillance et l’acheminement des informations détectées. Cette thèse vise à introduire un nouvel aspect intéressant de point de vue fonctionnel. Partant d’une exigence spécifiée initialement, mettre en oeuvre une synergie à plusieurs niveaux entre un ensemble des noeuds, tout en se basant sur une interaction adéquate. Ceci est réalisé par la génération automatique de code (correct par construction) et sa distribution par la suite en s’appuyant sur la théorie de contrôle par supervision. La synthèse de contrôleurs discrets SCD est une application de ce cadre théorique. Dans ce manuscrit, nous montrons comment la technique de la SCD peut être utilisée dans le domaine de réseaux de capteurs sans fil. Ainsi son potentiel se décline à deux niveaux. L’ordonnancement intra-cluster (groupe redondant de capteurs) avec des spécifications exprimant l’exclusion mutuelle lors de l’activation d’un capteur au sein d’un cluster, essentielle pour économiser l’énergie du réseau ainsi que la génération automatique d’un algorithme de routage optimal et multicritères pour les réseaux de capteurs. Spécifiquement, un chemin optimal devrait avoir à la fois une longueur minimale en termes de distance tout en évitant des chemins composés de noeuds dits « maillons faibles » (ayant un niveau d’énergie plus bas que la majorité). Les outils formels cités s’appuient sur une démarche de modélisation basée sur des machines à états finis communicantes. Les verrous scientifiques sont liés à la nature d’un réseau de capteurs ainsi qu’à sa taille. La SCD génère des contrôleurs monobloc, alors qu’au sein d’un réseau de capteurs le traitement est essentiellement distribué. La problématique est celle de la distribution d’un contrôleur global, qui se présente sous forme d’une contrainte logique exprimée sur l’état global du réseau, sur chacun des noeuds du réseau, en ajoutant la synchronisation nécessaire pour garantir un fonctionnement distribué équivalent au contrôleur initialement généré.

Wireless Sensor networks are attracted many activities of research and development during the last decade. Yet, the distributed behavior of a WSN remains centered on two main objectives: sensing and routing. This thesis advocates the introduction of an additional feature, which can be considered interesting from a functional point of view and potentially from the power consumption one: starting from a designer-specified requirement, implement a multiple level synergy between (groups of) nodes, based on adequate interaction. This is achieved by automatic generation and distribution of correct-by-construction code, relying on the Supervisory Control Theory. The Discrete Controller Synthesis (DCS) technique is an application of this theoretic framework. In this thesis, we show how DCS can be used for WSN. Thus, its potential is at two levels. The intra-cluster scheduling of a redundant group of sensors with specifications expressing the mutual exclusion during the activation of a sensor within a cluster, essential to save the energy within the network and then a multicriteria automatic generation of an optimal routing functionality. Specifically, an optimal path should have both a minimal length and go through nodes having maximal residual energy. The cited formal tools lean on a modelling approach based on communicating finite state machines (CFSM). The scientific challenges are generally related to the nature of the WSN as well as to its size. The DCS can only generates a monoblock controllers, while the WSN’s behavior is essentially distributed. The issue is how to distribute a global controller, who appears in the form of a logical constraint expressed on the global state of the network, into local controllers while adding the necessary synchronization to guarantee a distributed functioning equivalent to the initially generated controller., Les réseaux de capteurs sans fil ont attiré beaucoup d’activités de recherche et développement au cours de la dernière décennie. Pourtant, leur utilisation est restreinte, à ce jour, à la surveillance et l’acheminement des informations détectées. Cette thèse vise à introduire un nouvel aspect intéressant de point de vue fonctionnel. Partant d’une exigence spécifiée initialement, mettre en oeuvre une synergie à plusieurs niveaux entre un ensemble des noeuds, tout en se basant sur une interaction adéquate. Ceci est réalisé par la génération automatique de code (correct par construction) et sa distribution par la suite en s’appuyant sur la théorie de contrôle par supervision. La synthèse de contrôleurs discrets SCD est une application de ce cadre théorique. Dans ce manuscrit, nous montrons comment la technique de la SCD peut être utilisée dans le domaine de réseaux de capteurs sans fil. Ainsi son potentiel se décline à deux niveaux. L’ordonnancement intra-cluster (groupe redondant de capteurs) avec des spécifications exprimant l’exclusion mutuelle lors de l’activation d’un capteur au sein d’un cluster, essentielle pour économiser l’énergie du réseau ainsi que la génération automatique d’un algorithme de routage optimal et multicritères pour les réseaux de capteurs. Spécifiquement, un chemin optimal devrait avoir à la fois une longueur minimale en termes de distance tout en évitant des chemins composés de noeuds dits « maillons faibles » (ayant un niveau d’énergie plus bas que la majorité). Les outils formels cités s’appuient sur une démarche de modélisation basée sur des machines à états finis communicantes. Les verrous scientifiques sont liés à la nature d’un réseau de capteurs ainsi qu’à sa taille. La SCD génère des contrôleurs monobloc, alors qu’au sein d’un réseau de capteurs le traitement est essentiellement distribué. La problématique est celle de la distribution d’un contrôleur global, qui se présente sous forme d’une contrainte logique exprimée sur l’état global du réseau, sur chacun des noeuds du réseau, en ajoutant la synchronisation nécessaire pour garantir un fonctionnement distribué équivalent au contrôleur initialement généré.

Several formal methods of supervisory control of discrete events systems (DES), based on Petri nets (PN) have been developed. However, they are partially structural because of the need to construct the marking graph, which is an automaton, to determine the states forbidden by the specification. Some of those methods are limited to a particular class of Petri nets. Our work focused on the labeled Petri nets (LPN), which offers a better structure for defining the languages and automata. Among the based methods based on Petri nets, the invariant place method (simple and efficient) is the most used, although it does not guarantee in the general an optimal solution. In order to overcome this problem, we have developed a completely structural method, without construction of the marking graph for ordinary labeled Petri nets. It consists in determining in a way structural, admissible constraints for the invariant method place. It is based on the structural condition of controllability of closed loop SED LPN states, got by synchronous product of the process and specification LPN. In addition, we have proved that the structural condition of controllability, defined by the marking condition of entrance places of an uncontrollable synchronous transition, is equivalent to the condition of controllability defined by the languages of the LPN. This condition defines the equation of a separator hyperplan which ensures separation of the admissible states from the forbidden states in the SED. Constraints derived from hyperplane separator are admissible and can be simplified systematically. They provide a one-to-one link between the theory of supervisory control of Ramadge and Wonham and the calculation of maximum permissive controller by the invariant place method. Although for some complex structures (great scale), the maximum permissive solution cannot be guarantee directly; our approach gave the optimal controller in the real case studies considered., Plusieurs méthodes formelles de commande par supervision des systèmes à événements discrets (SED) basées sur les réseaux de Petri (RdP) ont été développées. Cependant, elles sont partiellement structurelles à cause de la nécessité de construire le graphe de marquage, qui est un automate, pour déterminer les états interdits par la spécification. Certaines de ces méthodes sont limitées à une classe particulière de RdP. Notre travail s'est focalisé en particulier sur le RdP synchronisé (RdPS), qui offre une meilleure structure pour définir les langages et les automates. Parmi les méthodes basées sur les RdP, la méthode des invariants (simple et efficace) est la plus utilisée bien qu’elle ne garantisse pas en général une solution de contrôle optimale. Pour pallier ce problème, nous avons développé une méthode complètement structurelle, sans construction du graphe de marquage, pour les RdPS ordinaires ou généralisés. Elle consiste à déterminer de manière structurelle les contraintes admissibles pour la méthode des invariants. Elle est basée sur la condition de contrôlabilité structurelle des états du RdPS du SED en boucle fermée, obtenu par produit synchrone des RdPS du procédé et de la spécification. En outre, nous avons prouvé que la condition de contrôlabilité structurelle, définie par la condition de marquage des places d’entrée d’une transition synchrone incontrôlable, est équivalente à la condition de contrôlabilité définie par les langages du RdPS. Cette condition définit l’équation d’un hyperplan séparateur qui assure la séparation des états admissibles des états interdits dans le SED. Les contraintes dérivées de d’hyperplan séparateur sont admissibles et peuvent être simplifiées systématiquement. Elles permettent de faire un lien biunivoque entre la théorie de commande par supervision de Ramadge et Wonham et la méthode des invariants pour le calcul d’un contrôleur optimal au sent maximal permissif. Même si pour certaines structures très complexes (à grande échelle), la solution maximale permissive ne peut être garantie directement, notre approche a donné le contrôleur optimal dans les études de cas réels considérés.

The discrete event system (DES) control theory was initially developed usingfinite state automata, with the aim of guaranteeing a priori operation in conformity with thespecifications which are generally decline as forbidden states.The automata represent apowerful modeling formalism of the DESs, despite their great sensitivity to the combinatorialexplosion problem of the number of states. This disadvantage is minimized when the modelingis carried out by the Petri nets (PN). However, this advantage in concision iscounterbalanced by the loss of the optimality of the results provided by the automata.However, among many methods of synthesis of supervisory control by PN, the invariantsmethod is the most used for the However, among many methods of synthesis of supervisorycontrol by PN, the invariants method is the most used for computing the controller.Unfortunately, this approach does not generally guarantee an optimal solution if it is used ina conventional way, and especially in the case where the synchronization of the PNs of theDES is carried out by uncontrollable transitions. The solution consists in identifying theadmissible constraints suitable for the synthesis of the maximum permissive (optimal)controller. We proposed a fusion approach based on the Kumar algorithm to determine theconstraints related to the forbidden boundary states, for computing the controller. But theneed to explore the state space of the PN, namely the marking graph, led us to represent themarking graph by its transition function, namely, the transition matrix. The coding of theelements of the matrix, according to the DES specification enabled us to identify the statesconstituting the hyperplane (decision function) and the appropriate boundary states, La théorie de commande par supervision des systèmes à événements discrets (SED) a été initialement développé à base des automates à états finis (AFD), avec pour objet de garantir à priori un fonctionnement conforme aux spécifications qui se déclinent généralement en états interdits. Les automates représentent un puissant formalisme de modélisation des SED, malgré leur grande sensibilité au problème d’explosion combinatoire du nombre d’états. Cet inconvénient est minimisé lorsque la modélisation est effectuée par les réseaux de Petri (RdP). Cependant, cet avantage en concision est contrebalancé par la perte de l’optimalité des résultats fournis par les automates. Toutefois, parmi de nombreuses méthodes de synthèse de commande par supervision à base RdP la méthode des invariants est la plus utilisée pour le calcul du contrôleur. Malheureusement, cette approche ne garantit pas en général une solution optimale si elle est utilisée de manière classique, et surtout dans le cas où la synchronisation des RdP du SED est réalisée par des transitions incontrôlables. La solution consiste à identifier les contraintes admissibles adéquates à la synthèse du contrôleur maximal permissif (optimal). Nous avons proposé une approche fusionnelle basée sur l’Algorithme de Kumar afin déterminer les contraintes liées aux états interdits frontières, pour le calcul du contrôleur. Mais, la nécessité d’explorer l’espace d’états du RdP , à savoir le graphe de marquage nous a conduit à représenter le graphe de marquage par sa fonction de transition, à savoir, la matrice de transition. La codification des éléments de la matrice, selon la spécification du SED nous a permis d’identifier les états constituants l’hyperplan (fonction de décision) et les états interdits frontières adéquats.

Trust in automation is an essential characteristic of supervised control. Indeed, counter performance of man-machine duo caused by poor trust level (overtrust or undertrust) can lead to material or human damage. It is therefore necessary to assess the trust of the man to anticipate such situations and prevent their realization. Therefore, in this thesis, we propose an evaluation model of trust. For this, we defined two models. The first is a model of dialogue based on the theory of grounding and specific for supervised control. The second is an evaluation model of trust which describes the relationship between user trust and observation of his strategy dialogue obtained trough the first model. The theoretical contribution is accompanied by two experiments. They are contextualized in the field of multi-UAV control and more specifically for patrol and interception missions. The first experiment, with exploratory purposes, highlights the existence of a link between trust and dialogue. The second checks our evaluation model of trust. This thesis therefore provides the basis for an objective assessment of trust with the observation of man-machine dialogue., La confiance de l'homme envers la machine est une caractéristique essentielle du contrôle supervisé. En effet, des contres performances du couple homme-machine provoquées par un mauvais niveau de confiance (insuffisant ou excessif) peuvent conduire à des dégâts matériels ou humains. Il est donc nécessaire d'évaluer la confiance de l'homme pour anticiper de telles situations et ainsi empêcher leur réalisation. C'est pourquoi, dans cette thèse, nous proposons un modèle d'évaluation de la confiance. Pour cela, nous avons défini deux modèles. Le premier est un modèle de dialogue basé sur la théorie du grounding et spécifique au contrôle supervisé. Le second est un modèle d'évaluation de la confiance qui décrit le lien entre la confiance de l'homme et l'observation de sa stratégie de dialogue à l'aide du premier modèle. Cet apport théorique est accompagné de deux expérimentations. Elles sont contextualisées dans le domaine du contrôle multi-drones et plus spécifiquement pour les opérations de surveillance et d'interception. La première expérience, à but exploratoire, met en évidence l'existence d'un lien entre confiance et dialogue. La seconde permet de tester la validation de notre modèle d'évaluation de la confiance. Cette thèse apporte donc les bases d'une approche objective de l'évaluation de la confiance à partir de l'observation du dialogue homme-machine.

Trust in automation is an essential characteristic of supervised control. Indeed, counter performance of man-machine duo caused by poor trust level (overtrust or undertrust) can lead to material or human damage. It is therefore necessary to assess the trust of the man to anticipate such situations and prevent their realization. Therefore, in this thesis, we propose an evaluation model of trust. For this, we defined two models. The first is a model of dialogue based on the theory of grounding and specific for supervised control. The second is an evaluation model of trust which describes the relationship between user trust and observation of his strategy dialogue obtained trough the first model. The theoretical contribution is accompanied by two experiments. They are contextualized in the field of multi-UAV control and more specifically for patrol and interception missions. The first experiment, with exploratory purposes, highlights the existence of a link between trust and dialogue. The second checks our evaluation model of trust. This thesis therefore provides the basis for an objective assessment of trust with the observation of man-machine dialogue.; La confiance de l'homme envers la machine est une caractéristique essentielle du contrôle supervisé. En effet, des contres performances du couple homme-machine provoquées par un mauvais niveau de confiance (insuffisant ou excessif) peuvent conduire à des dégâts matériels ou humains. Il est donc nécessaire d'évaluer la confiance de l'homme pour anticiper de telles situations et ainsi empêcher leur réalisation. C'est pourquoi, dans cette thèse, nous proposons un modèle d'évaluation de la confiance. Pour cela, nous avons défini deux modèles. Le premier est un modèle de dialogue basé sur la théorie du grounding et spécifique au contrôle supervisé. Le second est un modèle d'évaluation de la confiance qui décrit le lien entre la confiance de l'homme et l'observation de sa stratégie de dialogue à l'aide du premier modèle. Cet apport théorique est accompagné de deux expérimentations. Elles sont contextualisées dans le domaine du contrôle multi-drones et plus spécifiquement pour les opérations de surveillance et d'interception. La première expérience, à but exploratoire, met en évidence l'existence d'un lien entre confiance et dialogue. La seconde permet de tester la validation de notre modèle d'évaluation de la confiance. Cette thèse apporte donc les bases d'une approche objective de l'évaluation de la confiance à partir de l'observation du dialogue homme-machine.

The main objectives of this thesis are to propose dynamic models in order to describe road traffic by adapting models of fluid mechanics and based on these models to design and implement control algorithms. Road traffic is seen as a complex system organized in a decentralized structure. At the highest level of complexity there is the traffic network, considered as a part of a city’s road infrastructure. At the next level, the network is decomposed into traffic objects represented by road sections (streets) and intersections. At the last level of complexity there are the road segments that are parts of a road section.The thesis is organized into six chapters. The first chapter presents specific problems of road traffic networks, as well as control models and algorithms found in literature. The second chapter presents the main tools needed to describe a macroscopic traffic model, and some ways of representing the flow of vehicles. In the third chapter, dynamic models are proposed for different road segments and sections. The fourth chapter is devoted to designing algorithms for traffic control and optimization, including a robustness analysis to evaluate the system’s tolerance to model nonlinearities. The fifth chapter presents a control strategy for the road network, using the representation with compartmental models and the concept of positive dynamic. In the last chapter of the thesis, the author’s contributions are highlighted and some perspectives for further development of the research are presented; Les principaux objectifs de la thèse sont de proposer des modèles dynamiques pour décrire la circulation routière en adaptant des modèles de la mécanique des fluides et à partir de ces modèles de concevoir et mettre en œuvre des algorithmes de contrôle. La circulation routière est considérée comme un système complexe organisé dans une structure décentralisée à trois niveaux: au plus haut niveau il y a le réseau routier, décomposé, au niveau suivant, en objets routiers (tronçons et intersections), aussi décomposés, au dernier niveau, en éléments (segments) routiers.La thèse est organisée en six chapitres. Le premier chapitre présente les problèmes spécifiques aux réseaux de circulation routière, ainsi que des modèles et des algorithmes de contrôle trouvés dans la littérature. Le deuxième chapitre présente les principaux outils nécessaires pour décrire un modèle de trafic macroscopique et des façons pour représenter le flux de véhicules. Dans le troisième chapitre, des modèles dynamiques sont proposés pour différents segments et tronçons routiers. Le quatrième chapitre est consacré à la conception d’algorithmes pour le contrôle du trafic et l’optimisation de la circulation, y compris une analyse de robustesse pour évaluer la tolérance du système aux non-linéarités du modèle. Le cinquième chapitre présente une stratégie de contrôle pour le réseau routier, en utilisant la représentation par des modèles à compartiments et le concept de dynamique positive. Dans le dernier chapitre de la thèse, les contributions de l’auteur sont mises en évidence et quelques perspectives pour le développement ultérieur de la recherche sont présentées

The main objectives of this thesis are to propose dynamic models in order to describe road traffic by adapting models of fluid mechanics and based on these models to design and implement control algorithms. Road traffic is seen as a complex system organized in a decentralized structure. At the highest level of complexity there is the traffic network, considered as a part of a city’s road infrastructure. At the next level, the network is decomposed into traffic objects represented by road sections (streets) and intersections. At the last level of complexity there are the road segments that are parts of a road section.The thesis is organized into six chapters. The first chapter presents specific problems of road traffic networks, as well as control models and algorithms found in literature. The second chapter presents the main tools needed to describe a macroscopic traffic model, and some ways of representing the flow of vehicles. In the third chapter, dynamic models are proposed for different road segments and sections. The fourth chapter is devoted to designing algorithms for traffic control and optimization, including a robustness analysis to evaluate the system’s tolerance to model nonlinearities. The fifth chapter presents a control strategy for the road network, using the representation with compartmental models and the concept of positive dynamic. In the last chapter of the thesis, the author’s contributions are highlighted and some perspectives for further development of the research are presented; Les principaux objectifs de la thèse sont de proposer des modèles dynamiques pour décrire la circulation routière en adaptant des modèles de la mécanique des fluides et à partir de ces modèles de concevoir et mettre en œuvre des algorithmes de contrôle. La circulation routière est considérée comme un système complexe organisé dans une structure décentralisée à trois niveaux: au plus haut niveau il y a le réseau routier, décomposé, au niveau suivant, en objets routiers (tronçons et intersections), aussi décomposés, au dernier niveau, en éléments (segments) routiers.La thèse est organisée en six chapitres. Le premier chapitre présente les problèmes spécifiques aux réseaux de circulation routière, ainsi que des modèles et des algorithmes de contrôle trouvés dans la littérature. Le deuxième chapitre présente les principaux outils nécessaires pour décrire un modèle de trafic macroscopique et des façons pour représenter le flux de véhicules. Dans le troisième chapitre, des modèles dynamiques sont proposés pour différents segments et tronçons routiers. Le quatrième chapitre est consacré à la conception d’algorithmes pour le contrôle du trafic et l’optimisation de la circulation, y compris une analyse de robustesse pour évaluer la tolérance du système aux non-linéarités du modèle. Le cinquième chapitre présente une stratégie de contrôle pour le réseau routier, en utilisant la représentation par des modèles à compartiments et le concept de dynamique positive. Dans le dernier chapitre de la thèse, les contributions de l’auteur sont mises en évidence et quelques perspectives pour le développement ultérieur de la recherche sont présentées

Colloque avec actes et comité de lecture. internationale.; International audience; Nous proposons, dans cet article, une méthode de synthèse de superviseurs basés sur les réseaux de Petri, pour résoudre le problème d'états interdits en présence d'évènements non contrôlables et en intégrant la contrainte de vivacité. l'approche proposée dans cet article combine l'approche de Ramadge-Wonham et la théorie des régions, une théorie récemment proposée pour la synthèse de réseaux de Petri à partir de graphes de marquage. l'espace des états admissibles est d'abord déterminé, puis la théorie des régions est utilisée pour concevoir, quand c'est possible, le superviseur sous forme de places de réseau de Petri. La puissance de l'approche proposée est illustrée particulièrement par le traitement d'un problème d'évitement de blocage avec des transitions non contrôlables. || This paper addresses the forbidden state problem of Petri nets with liveness requirement and uncontrollable transitions. The proposed approach synthesizes in two steps an optimal Petri net-based controller, whenever such a controller exists. First, the be