In this dissertation, we study two new approaches to fault detection for autonomous robots. The first approach involves the synthesis of software components that give a robot the capacity to detect faults which occur in itself. Our hypothesis is that hardware faults change the flow of sensory data and the actions performed by the control program. By detecting these changes, the presence of faults can be inferred. In order to test our hypothesis, we collect data in three different tasks performed by real robots. During a number of training runs, we record sensory data from the robots both while they are operating normally and after a fault has been injected. We use back-propagation neural networks to synthesize fault detection components based on the data collected in the training runs. We evaluate the performance of the trained fault detectors in terms of the number of false positives and the time it takes to detect a fault.<p>The results show that good fault detectors can be obtained. We extend the set of possible faults and go on to show that a single fault detector can be trained to detect several faults in both a robot's sensors and actuators. We show that fault detectors can be synthesized that are robust to variations in the task. Finally, we show how a fault detector can be trained to allow one robot to detect faults that occur in another robot.<p><p>The second approach involves the use of firefly-inspired synchronization to allow the presence of faulty robots to be determined by other non-faulty robots in a swarm robotic system. We take inspiration from the synchronized flashing behavior observed in some species of fireflies. Each robot flashes by lighting up its on-board red LEDs and neighboring robots are driven to flash in synchrony. The robots always interpret the absence of flashing by a particular robot as an indication that the robot has a fault. A faulty robot can stop flashing periodically for one of two reasons. The fault itself can render the robot unable to flash periodically.<p>Alternatively, the faulty robot might be able to detect the fault itself using endogenous fault detection and decide to stop flashing.<p>Thus, catastrophic faults in a robot can be directly detected by its peers, while the presence of less serious faults can be detected by the faulty robot itself, and actively communicated to neighboring robots. We explore the performance of the proposed algorithm both on a real world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.<p><p>We conclude that i) fault injection and learning can give robots the capacity to detect faults that occur in themselves, and that ii) firefly-inspired synchronization can enable robots in a swarm robotic system to detect and communicate faults.<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Que ce soit dans l’automobile avec des contraintes thermiques ou dans l’aérospatial et lenucléaire soumis à des rayonnements ionisants, l’environnement entraîne l’apparition de fautesdans les systèmes électroniques. Ces fautes peuvent être transitoires ou permanentes et vontinduire des résultats erronés inacceptables dans certains contextes applicatifs. L’utilisation decomposants dits « rad-hard » est parfois compromise par leurs coûts élevés ou les difficultésd’approvisionnement liés aux règles d’exportation.Cette thèse propose une approche conjointe matérielle et logicielle indépendante de la technologied’intégration permettant d’utiliser des composants numériques programmables dans desenvironnements susceptibles de générer des fautes. Notre proposition comporte la définitiond’une Architecture Reconfigurable à Gros Grains (CGRA) capable d’exécuter des codes applicatifscomplets mais aussi l’ensemble des mécanismes matériels et logiciels permettant de rendrecette architecture tolérante aux fautes. Ce résultat est obtenu par l’association de redondance etde reconfiguration dynamique du CGRA en s’appuyant sur une banque de configurations généréepar une chaîne de programmation complète. Cette chaîne outillée repose sur un flot permettantde porter un code sous forme de Control and Data Flow Graph (CDFG) sur l’architecture enobtenant un grand nombre de configurations différentes et qui permet d’exploiter au mieux lepotentiel de l’architecture.Les travaux, qui ont été validés aux travers d’expériences sur des applications du domaine dutraitement du signal et de l’image, ont fait l’objet de publications en conférences internationaleset de dépôts de brevets. / Whether in automotive with heat stress or in aerospace and nuclear field subjected to cosmic,neutron and gamma radiation, the environment can lead to the development of faults in electronicsystems. These faults, which can be transient or permanent, will lead to erroneous results thatare unacceptable in some application contexts. The use of so-called rad-hard components issometimes compromised due to their high costs and supply problems associated with exportrules.This thesis proposes a joint hardware and software approach independent of integrationtechnology for using digital programmable devices in environments that generate faults. Ourapproach includes the definition of a Coarse Grained Reconfigurable Architecture (CGRA) ableto execute entire application code but also all the hardware and software mechanisms to make ittolerant to transient and permanent faults. This is achieved by the combination of redundancyand dynamic reconfiguration of the CGRA based on a library of configurations generated by acomplete conception flow. This implemented flow relies on a flow to map a code represented as aControl and Data Flow Graph (CDFG) on the CGRA architecture by obtaining directly a largenumber of different configurations and allows to exploit the full potential of architecture.This work, which has been validated through experiments with applications in the field ofsignal and image processing, has been the subject of two publications in international conferencesand of two patents.

Les systèmes autonomes, notamment ceux opérant à proximité d'êtres humains, soulèvent des problèmes de sécurité-innocuité puisqu'ils peuvent causer des blessures. La complexité de la commande de ces systèmes, ainsi que leurs interactions avec un environnement peu structuré, rendent difficile l'élimination complète des fautes. Nous adoptons donc une démarche de tolérance aux fautes en considérant un moniteur de sécurité séparé de la commande principale et qui dispose de ses propres moyens d'observation et d'intervention. Le comportement de ce moniteur est régi par des règles qui doivent assurer la sécurité du système tout en lui permettant de remplir ses fonctions. Nous proposons une méthode systématique pour obtenir ces règles de sécurité. Les dangers, déterminés par une analyse de risque, sont modélisés formellement puis un algorithme synthétise des règles sûres et permissives, s'il en existe. Nous avons outillé cette méthode pour les étapes de modélisation et de synthèse en nous appuyant sur l'outil de vérification de modèle NuSMV. L'étude d'un cas industriel illustre l'application de la méthode et des outils sur un robot manufacturier dans un environnement humain. / Autonomous systems operating in the vicinity of humans are critical in that they potentially harm humans. In these systems, fault removal is not sufficient given the command complexity and their interactions with an unstructured environment. By a fault tolerance approach, we consider a safety monitor separated from the main command and able to observe and intervene on the system. The monitor behavior is specified by safety rules that must both ensure safety and permit the system to carry out its tasks in absence of hazard. We propose a systematic method to obtain these safety rules. The hazards, determined by a risk analysis, are formally modeled, then an algorithm synthesizes safe and permissive rules, if any exists. The method is tooled both for modeling and synthesis by use of the model-checker NuSMV. Method and tools are applied to the industrial use case of a robotic co-worker.

Ce travail appartient au domaine de la simulation numérique sur des plates-formes d'exécution distribuées hétérogènes telles que des grilles de calcul. Ce type de plate-forme se caractérise par des possibles changements de condition d'exécution et par une probabilité importante de défaillance de certains composants. Une application qui s'exécute dans un tel environnement se doit d'être adaptable à son contexte d'exécution et tolérante aux pannes. Face à la complexité croissante de la mise en place de cas de calcul sur des grilles de calcul, nous proposons une plateforme logicielle pour la résolution de cas de calcul numérique dans un environnement distribué hétérogène. Nos travaux apportent une solution qui se base sur un système d'agents mobiles, ce qui permet à une application de s'adapter au changement de son environnement d'exécution. Dans un premier temps, nous utilisons le langage pi calcul d'ordre supérieur pour spécifier une « ferme de travailleurs » capable de participer à la résolution de tout type de cas de calcul. Ensuite, nous énonçons des propriétés qui caractérisent le bon fonctionnement de ce système avec une logique temporelle TCTL. Pour cela, nous souhaitons modéliser notre système à l'aide d'automates temporisés à partir des termes définis par la spécification formelle en pi calcul. Dans ce but, nous définissons une transformation de termes écrits en pi calcul en automates temporisés. Les propriétés sont alors vérifiées avec l'outil UppAal. Pour valider ce travail de modélisation, nous avons réalisé le framework MCA (pour Mobile Computing Architecture). Celui-ci propose un ensemble d'outils facilitant la mise en place de composants sur un environnement distribué hétérogène dans le but d'effectuer la résolution de cas de calcul. La librairie avec laquelle sont développés ces composants, qu'ils soient mobiles ou non, est implantée en Java et se base les technologies Jini et JavaSpaces. Enfin, nous réalisons l'évaluation du framework MCA en procédant à la résolution de trois cas de calcul différents. Chacune de ces expériences, réalisées sur une grappe de 20 noeuds, nous permet de montrer les caractéristiques essentielles de notre framework : une simplicité de programmation, un faible surcoût en temps d'exécution sans l'activation de la tolérance aux pannes et une tolérance aux pannes efficace / This work belongs to the domain of numerical simulation on heterogeneous distributed platforms such as grids. This type of platform is characterized by possible changes in execution conditions and a significant probability of some components failure. An application running in such an environment must be adaptable to its execution context and fault tolerant. Facing the growing complexity of implementing computation cases on grid computing, we propose a software platform which solves numerical computation cases in a distributed heterogeneous environment. Our work provides a solution based on a mobile agent system, which allows an application to adapt to change in its execution environment. At first, we use the higher-order pi calculus language to specify a « farm of workers » able to take part in solving any type of computation case. Then we set the properties that characterize the system's correct execution with a temporal logic TCTL. In order to do this, we perform a temporal modeling system based on terms defined by the formal specification in pi calculus. To achieve this transformation, we define a translation of terms written in pi calculus into timed automata. The properties are verified with the UppAal tool. To validate this modeling work, we develop the MCA (for Mobile Computing Architecture) framework. It offers a set of tools which facilitate the implementation of distributed heterogeneous components in order to solve computation cases. These components, mobile or not, are developed with a library written in Java and which uses Jini and JavaSpaces technologies. Finally, our framework is evaluated through the resolution of three different computation cases. Each of these experiments, performed on a 20 node cluster allow us to highlight our framework's main characteristics : programming simplicity, low overhead in execution time without the fault tolerance activation and efficient fault tolerance

Parfois dans le développement logiciel, les fautes potentielles peuvent être omises, par exemple quand la complexité cache les fautes même en présence d’un processus de développement rigoureux, ou quand en raison des contraintes en termes de coûts et de temps sur les démarches de tolérance aux fautes, des risques sont assumés.La première contribution de cette thèse est l’élaboration d’un cadre de développement pour produire des logiciels tolérants aux fautes imprévues, c.à.d. fautes qui ne sont pas couvertes dans la mise en œuvre. Nous proposons 1) l’utilisation d’une architecture multi-agent avec des agents dirigés pas des buts pour le confinement des erreurs et la récupération du système ; 2) des exigences au niveau du langage de programmation ayant pour but de limiter les fautes possibles et de localiser les zones où d’autres fautes peuvent être présentes et 3) des exigences au niveau de la plate-forme d’exécution. Nous illustrons l’approche en étudiant la conception et la mise en œuvre avec un langage de programmation adapté et sa plate-forme.La deuxième contribution concerne la manière dont les agents dirigés par des buts sont programmés. Le problème est que de nombreuses approches pour la modélisation des agents cognitifs autorisent les développeurs à entrelacer les niveaux des plans et des buts, grâce à l’adoption de nouveaux buts à l’intérieur des plans. La complexité résultante peut rendre le comportement des agents difficilement traçable. Nous proposons d’imposer une séparation claire entre les niveaux de raisonnement et d’action des agents. En contraignant le modèle d’agent nous gagnons en lisibilité, avec un bénéfice pour le processus de développement. / There are situations in software development when potential faults can be omitted, e.g. when the complexity hides faults from a rigorous development process, or when due to cost and time constraints on the fault tolerance effort, risks are assumed, either consciously or not. The first contribution of this thesis is a development framework – design, language and platform requirements – for producing software that is tolerant to unforeseen faults, i.e. faults that were not covered in the implementation. We propose (1) the use of a multi-agent architecture with goal-driven agents benefits the confinement of errors and the subsequent system recovery; (2) language requirements that constrain the programmers in order to limit the possible faults and in the same time localise the areas where other faults can be present and (3) execution platform requirements in order to ensure the desired fault tolerance properties. We illustrate the approach by discussing design and implementation using an adapted agent programming language and platform. The second contribution focuses on the way goal-driven agents are programmed. The issue is that many approaches to cognitive agent modelling permit the agent developers to interweave the levels of plans and goals, through the adoption of new goals inside plans. These goals will have plans of their own, and the definition can extend on many levels, with the resulting complexity rendering the agents’ behaviour difficult to trace. We thus propose imposing a clear separation between the reasoning and the acting levels of the agent. We argue that by constraining the agent model we gain in clarity therefore benefiting the development process.

Depuis l'introduction au début des années 2000 du standard ARINC 661 (définissant les interfaces graphiques dans les cockpits), les avions modernes, tels que l'A380, l'A350 ou le B787, intègrent des systèmes interactifs permettant à l'équipage d'interagir avec des applications interactives. Ces applications sont affichées sur des écrans à travers l'utilisation d'un dispositif similaire à un clavier et une souris. Pour des raisons d'exigences de sûreté de fonctionnement, l'utilisation de ces systèmes est limitée, à l'heure actuelle, à la commande et au contrôle de fonctions avioniques non critiques. Cependant, l'utilisation de ces systèmes dans les cockpits d'avions civils apporte de nombreux avantages (tels qu'une amélioration de l'évolutivité du cockpit) qui amènent les industriels à chercher comment l'étendre à la commande et le contrôle de systèmes avioniques critiques. Dans cette optique, nous proposons une approche duale et homogène de prévention et de tolérance aux fautes pour concevoir et développer des systèmes interactifs tolérants aux fautes. Celle-ci repose, dans un premier temps, sur une approche à base de modèles permettant de décrire de manière complète et non ambiguë les composants logiciels des systèmes interactifs et de prévenir les fautes logicielles de développement. Dans un second temps, elle repose sur une approche de tolérance aux fautes naturelles et certaines fautes logicielles résiduelles en opération, grâce à la mise en œuvre d'une solution architecturale fondée sur le principe des composants autotestables. Les contributions de la thèse sont illustrées sur une étude de cas de taille industrielle : une application interactive inspirée du système de commande et contrôle de l'autopilote de l'A380. / Since the introduction of the ARINC 661 standard (that defines graphical interfaces in the cockpits) in the early 2000, modern aircrafts such as the A380, the A350 or the B787 possess interactive systems. The crew interacts, through physical devices similar to keyboard and mouse, with interactive applications displayed on screens. For dependability reasons, only non-critical avionics systems are managed using such interactive systems. However, their use brings several advantages (such as a better upgradability), leading aircraft manufacturers to generalize the use of such interactive systems to the management of critical avionics functions. To reach this goal, we propose a dual and homogeneous fault prevention and fault tolerance approach. Firstly, we propose a model-based approach to describe in a complete and unambiguous way interactive software components to prevent as much as possible development software faults. Secondly, we propose a fault tolerant approach to deal with operational natural faults and some residual software faults. This is achieved through the implementation of a fault tolerant architecture based on the principle of self-checking components. Our approach is illustrated on a real size case study: an interactive application based on the command and control system of the A380 autopilot.

La durée de vie utile résiduelle (RUL) peut être simplement définie comme une prédiction du temps restant pendant lequel un système est capable d'exécuter sa fonction prévue ; elle est mesurée à partir de l'instant présent jusqu'à la défaillance finale. Cette durée prévue dépend principalement de l'état de détérioration des composants du système et de leurs conditions de fonctionnement futures prévues. Ainsi, la prédiction de la RUL est un processus incertain et son contrôle n'est pas une tâche triviale. En général, le but de la prévision de la RUL est d'influencer la prise de décision pour le système. Dans cette thèse, on a présenté un cadre compréhensible pour le contrôle de la RUL. Les incertitudes du modèle ainsi que les perturbations du système ont été prises en compte dans le cadre proposé. Des questions telles que le traitement de l'incertitude et l'inclusion d'objectifs RUL dans la stratégie de contrôle sont étudiées, depuis la modélisation jusqu'à une architecture de contrôle globale finale. On a montré que l'on peut prédire la RUL à partir d'une estimation appropriée de la détérioration et d'hypothèses sur les conditions de fonctionnement futures. Les systèmes d'entraînement par friction sont utilisés pour illustrer l'utilité de l'architecture globale susmentionnée. Pour ce type de système, le frottement est à la fois source du mouvement et source de la détérioration. Ce double caractéristique de frottement est une motivation pour contrôler automatiquement la détérioration du système en maintenant un compromis entre les exigences de mouvement et les valeurs RUL souhaitées. Dans cette thèse, un nouveau modèle orienté contrôle pour les systèmes d'entraînement par friction, qui inclut un modèle dynamique de la détérioration, est proposé. Le degré de détérioration est considéré en fonction de l'énergie dissipée, à la surface de contact, pendant la transmission mécanique de puissance. Une approche est proposée pour estimer l'état actuel de la détérioration d'un système d'entraînement par friction. L'approche est basée sur un Filtre de Kalman Etendu (EKF en anglais) qui utilise un modèle augmenté incluant le système mécanique dynamique et la dynamique de détérioration. L'EKF fournit également des intervalles qui incluent sûrement la valeur de détérioration réelle avec une valeur de probabilité. Une nouvelle architecture de commande de la RUL est proposée, elle comprend : un système de surveillance de l'état de détérioration (par exemple l'EKF proposé), un estimateur de l'état de fonctionnement du système, un système de commande de la RUL et un principe actionneur de la RUL. L'estimateur des conditions de fonctionnement est basé sur l'hypothèse qu'il est possible de quantifier certaines caractéristiques des exigences de mouvement, par exemple le rapport cyclique des couples moteur. Le contrôleur RUL utilise une fonction de coût qui pondère les exigences de mouvement et les valeurs RUL souhaitées pour modifier un filtre à paramètres variables, utilisé ici comme principe actionneur RUL. Le principe actionneur RUL est basé sur une modification des couples exigés, provenant d'un éventuel système de contrôle de mouvement. Les résultats préliminaires montrent qu'il est possible de contrôler la RUL, selon le cadre théorique proposé. / Remaining Useful Lifetime (RUL) can be simply defined as a prediction of the remaining time that a system is able to perform its intended function, from the current time to the final failure. This predicted time mostly depends on the state of deterioration of the system components and their expected future operating conditions. Thus, the RUL prediction is an uncertain process and its control is not trivial task.In general, the purpose for predicting the RUL is to influence decision-making for the system. In this dissertation a comprehensive framework for controlling the RUL is presented. Model uncertainties as well as system disturbances have been considered into the proposed framework. Issues as uncertainty treatment and inclusion of RUL objectives in the control strategy are studied from the modeling until a final global control architecture. It is shown that the RUL can be predicted from a suitable estimation of the deterioration, and from hypothesis on the future operation conditions. Friction drive systems are used for illustrating the usefulness of the aforementioned global architecture. For this kind of system, the friction is the source of motion and at the same time the source of deterioration. This double characteristic of friction is a motivation for controlling automatically the deterioration of the system by keeping a trade-off, between motion requirements and desired RUL values. In this thesis, a new control-oriented model for friction drive systems, which includes a dynamical model of the deterioration is proposed. The amount of deterioration has been considered as a function of the dissipated energy, at the contact surface, during the mechanical power transmission. An approach to estimate the current deterioration condition of a friction drive system is proposed. The approach is based on an Extended Kalman Filter (EKF) which uses an augmented model including the mechanical dynamical system and the deterioration dynamics. At every time instant, the EKF also provides intervals which surely includes the actual deterioration value which a given probability. A new architecture for controlling the RUL is proposed, which includes: a deterioration condition monitoring system (for instance the proposed EKF), a system operation condition estimator, a RUL controller system, and a RUL actuation principle. The operation condition estimator is based on the assumption that it is possible quantify certain characteristics of the motion requirements, for instance the duty cycle of motor torques. The RUL controller uses a cost function that weights the motion requirements and the desired RUL values to modify a varying-parameter filter, used here as the RUL-actuating-principle. The RUL-actuating-principle is based on a modification of the demanded torques, coming from a possible motion controller system. Preliminary results show that it is possible to control de RUL according to the proposed theoretical framework.

Les systèmes réactifs sont de plus en plus présents dans de nombreux secteurs d´activité tels que l´automobile, les télécommunications et l´aéronautique. Ces systèmes réalisent des tâches complexes qui sont souvent critiques. Au vu des conséquences catastrophiques que pourrait entraîner une défaillance dans ces systèmes, suite à la présence de fautes matérielles (processeurs et média de communication), il est essentiel de prendre en compte la tolérance aux fautes dans leur conception. En outre, plusieurs domaines exigent une évaluation quantitative du comportement de ces systèmes par rapport à l'occurrence et à l'activation des fautes. Afin de concevoir des systèmes sûrs de fonctionnement, j'ai proposé dans cette thèse trois méthodologies de conception basées sur la théorie d'ordonnancement et la redondance active et passive des composants logiciels du système. Ces trois méthodologies permettent de résoudre le problème de la génération automatique de distribution et d'ordonnancements temps réel, fiables et tolérants aux fautes. Ce problème étant NP-difficile, ces trois méthodologies sont basées sur des heuristiques de type ordonnancement de liste. Plus particulièrement, les deux premières méthodologies traitent le problème de la tolérance aux fautes matérielles des processeurs et des media de communication, respectivement pour des architectures à liaisons point-à-point et des architectures à liaison bus. La troisième méthodologie traite le problème de l'évaluation quantitative d'une distribution/ordonnancement en terme de fiabilité à l'aide d'une heuristique bi-critère originale. Ces méthodologies offrent de bonnes performances sur des graphes d'algorithme et d'architecture générés aléatoirement.

À l'interface entre informatique distribuée et en génie logiciel, nous présentons trois contributions liées aux problématiques de réutilisation du logiciel dans trois cas représentatifs de systèmes distribués grande échelle: les réseaux logiques pair-à-pair, les protocoles épidémiques, et les intergiciels de grille. Les travaux que nous présentons portent sur trois problématiques différentes mais néanmoins liées de ces systèmes: la tolérance aux pannes modulaire (dans les réseaux pair-à-pair), la programmabilité des systèmes à composants (dans les protocoles épidémiques), et l'analyse interactive de performances (dans les intergiciels de grille). Le message qui se dégage de nos travaux est double. Nos contributions démontrent tout d'abord en termes concrets l'intérêt d'abstractions logicielles réutilisables pour les systèmes distribués grande échelle. Nos travaux illustrent par ailleurs la tension inhérente entre réutilisation et complexité logicielle dans les plates-formes distribuées modernes. Notre travail sur les protocoles épidémiques montre par exemple comment une approche de développement par composants peut être combinée à un langage métier dédié pour une plus grande programmabilité. De même notre analyse d'un intergiciel de grille (Globus) illustre clairement les difficultés introduites par la réutilisation logicielle dans les plates-formes distribuées d'aujourd'hui, et comment ces difficultés peuvent être abordées dans le cas du diagnostic en combinant des principes de rétro-conception architecturale avec une analyse dynamique de performances.

Je présente dans ce document mes résultats de recherche sur la conception sûre de systèmes embarqués sûrs. La première partie concerne la répartition automatique de programmes synchrones. Le caractère automatique de la répartition apporte un réel degré de sûreté dans la conception de systèmes répartis car c'est la partie la plus délicate de la spécification qui est automatisée. Grâce à cela, l'absence d'inter-blocage et l'équivalence fonctionnelle entre le programme source centralisé et le programme final réparti peuvent être formellement démontrées. La deuxième partie traite le sujet de l'ordonnancement et de la répartition de graphes de tâches flots-de-données sur des architectures à mémoire répartie, avec contraintes de tolérance aux fautes et de fiabilité. Je présente principalement des heuristiques d'ordonnancement statique multiprocesseur avec pour but la tolérance aux fautes et la fiabilité des systèmes, mais également l'utilisation de méthodes formelles telles que la synthèse de contrôleurs discrets ou les transformations automatiques de programmes. Enfin, la troisième partie concerne les autoroutes automatisées, avec deux volets : la commande longitudinale de véhicules autonomes et les stratégies d'insertion dans les autoroutes automatisées.