Les systèmes d'aide à la conduite, en général, et plus particulièrement les systèmes d'aide à l'évitement de collision sont de plus en plus en présents dans les véhicules car ils ont un très fort potentiel de réduction du nombre d'accidents de la circulation.En effet, ces systèmes ont pour rôle d'assister le conducteur, voire de se substituer à lui lorsque la situation de conduite indique un risque de collision important. Cette thèse traite du développement de ces systèmes en abordant quelques problématiques rencontrées.Afin de réagir convenablement, le système a d'abord besoin d'une représentation aussi fidèle que possible de l'environnement du véhicule. La perception est faite au moyen de capteurs extéroceptifs qui permettent de détecter les objets et d'en mesurer divers paramètres selon leur principe de mesure. La fusion des données individuelles des capteurs permet d'obtenir une information globale plus juste, plus certaine et plus variée. Ce travail traite en profondeur des méthodes de suivi d'objets par fusion de données multi-capteur, multimodale au niveau piste. Les approches proposées ont été évaluées puis approuvées grâce à des données de roulage réel et sur des données de conduite simulées.Il est ensuite nécessaire de faire une analyse de la scène perçue au cours du temps afin d'évaluer le risque de collision encouru par le véhicule porteur du système. Cette thèse propose des méthodes de prédiction de trajectoire et de calcul de probabilité de collision, à divers horizons temporels afin de quantifier le risque de collision et d'établir ainsi divers niveaux d'alerte au conducteur. Un simulateur de scénarios automobiles a été utilisé pour valider la cohérence des méthodes d'analyse de scène.Enfin, lorsque le risque de collision atteint un seuil jugé critique, le système doit calculer une trajectoire d'évitement de collision qui sera ensuite automatiquement exécutée. Les principales approches de planification de trajectoires ont été revues et un choix a été fait et motivé en accord avec le contexte de système d'aide à la conduite.

L'approximation de fonctions et de données discrètes est fondamentale dans des domaines tels que la planification de trajectoire ou le traitement du signal (données issues de capteurs). Dans ces domaines, il est important d'obtenir des courbes conservant la forme initiale des données. L'utilisation des splines L1 semble être une bonne solution au regard des résultats obtenus pour le problème d'interpolation de données discrètes par de telles splines. Ces splines permettent notamment de conserver les alignements dans les données et de ne pas introduire d'oscillations résiduelles comme c'est le cas pour les splines d'interpolation L2. Nous proposons dans cette thèse une étude du problème de meilleure approximation au sens de la norme L1. Cette étude comprend des développements théoriques sur la meilleure approximation L1 de fonctions présentant une discontinuité de type saut dans des espaces fonctionnels généraux appelés espace de Chebyshev et faiblement Chebyshev. Les splines polynomiales entrent dans ce cadre. Des algorithmes d'approximation de données discrètes au sens de la norme L1 par procédé de fenêtre glissante sont développés en se basant sur les travaux existants sur les splines de lissage et d'ajustement. Les méthodes présentées dans la littérature pour ces types de splines peuvent être relativement couteuse en temps de calcul. Les algorithmes par fenêtre glissante permettent d'obtenir une complexité linéaire en le nombre de données. De plus, une parallélisation est possible. Enfin, une approche originale d'approximation, appelée interpolation à delta près, est développée. Nous proposons un algorithme algébrique avec une complexité linéaire et qui peut être utilisé pour des applications temps réel. / Data and function approximation is fundamental in application domains like path planning or signal processing (sensor data). In such domains, it is important to obtain curves that preserve the shape of the data. Considering the results obtained for the problem of data interpolation, L1 splines appear to be a good solution. Contrary to classical L2 splines, these splines enable to preserve linearities in the data and to not introduce extraneous oscillations when applied on data sets with abrupt changes. We propose in this dissertation a study of the problem of best L1 approximation. This study includes developments on best L1 approximation of functions with a jump discontinuity in general spaces called Chebyshev and weak-Chebyshev spaces. Polynomial splines fit in this framework. Approximation algorithms by smoothing splines and spline fits based on a sliding window process are introduced. The methods previously proposed in the littérature can be relatively time consuming when applied on large datasets. Sliding window algorithm enables to obtain algorithms with linear complexity. Moreover, these algorithms can be parallelized. Finally, a new approximation approach with prescribed error is introduced. A pure algebraic algorithm with linear complexity is introduced. This algorithm is then applicable to real-time application.

La conduite autonome a attiré une attention croissante au cours des dernières décennies en raison de son potentiel impact socio-économique, notamment concernant la réduction du nombre d'accidents de la route et l'amélioration de l'efficacité du trafic. Grâce à l'effort de plusieurs instituts de recherche et d'entreprises, les véhicules autonomes ont déjà accumulé des dizaines de millions de kilomètres parcourus dans des conditions de circulation réelles. Cette thèse porte sur la conception d'une architecture de contrôle pour les véhicules autonomes et coopératifs dans l'optique de leur déploiement massif. La base commune des différentes architectures proposées dans cette thèse est le Contrôle-Commande Prédictif, reconnu pour son efficacité et sa polyvalence. Nous présentons tout d'abord une architecture classique de contrôle hiérarchique, qui utilise la commande prédictive pour planifier un déplacement (choix de trajectoire), puis déterminer un contrôle permettant de suivre cette trajectoire. Toutefois, comme nous le montrons dans un deuxième temps, cette architecture simple n'est pas capable de gérer certaines contraintes logiques, notamment liées aux règles de circulation et à l'existence de choix de trajectoires discrets. Nous proposons donc approche hybride de la commande prédictive, que nous utilisons pour développer une architecture de contrôle pour un véhicule autonome individuel. Nous étudions le problème de contrôler un ensemble de véhicules autonomes circulant en convoi, i.e. maintenir une formation prédéterminée sans intervention humaine. Pour ce faire, nous utilisons à nouveau une architecture hiérarchique basée sur la commande prédictive, composée d'un superviseur de convoi et de contrôleurs pour chaque véhicule individuel. Enfin, nous proposons encore une architecture pour le problème de coordonner un groupe de véhicules autonomes dans une intersection sans feux de circulation, en utilisant un contrôleur d'intersection et en adaptant les contrôleurs des véhicules individuels pour leur permettre de traverser l'intersection en toute sécurité. / Autonomous driving has been gaining more and more attention in the last decades, thanks to its positive social-economic impacts including the enhancement of traffic efficiency and the reduction of road accidents. A number of research institutes and companies have tested autonomous vehicles in traffic, accumulating tens of millions of kilometers traveled in autonomous driving. With the vision of massive deployment of autonomous vehicles, researchers have also started to envision cooperative strategies among autonomous vehicles. This thesis deals with the control architecture design of individual autonomous vehicles and cooperative autonomous vehicles. Model Predictive Control (MPC), thanks to its efficiency and versatility, is chosen as the building block for various control architectures proposed in this thesis. In more detail, this thesis first presents a classical hierarchical control architecture for individual vehicle control that decomposes the controller into a motion planner and a tracking controller, both using nonlinear MPC. In a second step, we analyze the inability of the proposed planner in handling logical constraints raised from traffic rules and multiple maneuver variants, and propose a hybrid MPC based motion planner that solves this issue. We then consider the convoy control problem of autonomous vehicles in which multiple vehicles maintain a formation during autonomous driving. A hierarchical formation control architecture is proposed composing of a convoy supervisor and local MPC based vehicle controllers. Finally, we consider the problem of coordinating a group of autonomous vehicles at an intersection without traffic lights. A hierarchical architecture composed of an intersection controller and multiple local vehicle controllers is proposed to allow vehicles to cross the intersection smoothly and safely.

Le déploiement des futurs véhicules autonomes promet d'avoir un impact socio-économique majeur, en raison de leur promesse d'être à la fois plus sûrs et plus efficaces que ceux conduits par des humains. Afin de satisfaire à ces attentes, la capacité des véhicules autonomes à planifier des trajectoires sûres et à manœuvrer efficacement dans le trafic sera capitale. Cependant, le problème de planification de trajectoire au milieu d'obstacles statiques ou mobiles a une combinatoire forte qui est encore aujourd'hui problématique pour les meilleurs algorithmes.Cette thèse explore une nouvelle approche de la planification de mouvement, basée sur l'utilisation de la notion de décision de conduite comme guide pour structurer le problème de planification en vue de faciliter sa résolution. Cette approche peut trouver des applications pour la conduite coopérative, par exemple pour coordonner plusieurs véhicules dans une intersection non signalisée, ainsi que pour la conduite autonome où chaque véhicule planifie sa trajectoire. Dans le cas de la conduite coopérative, les décisions correspondent au choix d'un ordonnancement des véhicules qui peut être avantageusement encodé comme un graphe. Cette thèse propose une représentation similaire pour la conduite autonome, où les décisions telles que dépasser ou non un véhicule sont nettement plus complexes. Une fois la décision prise, il devient aisé de déterminer la meilleure trajectoire y correspondant, en conduite coopérative comme autonome. Cette approche basée sur la prise de décision peut permettre d'améliorer la robustesse et l'efficacité de la planification de trajectoire, et ouvre d'intéressantes perspectives en permettant de combiner des approches mathématiques classiques avec des techniques plus modernes d'apprentissage automatisé. / The deployment of future self-driving vehicles is expected to have a major socioeconomic impact due to their promise to be both safer and more traffic-efficient than human-driven vehicles. In order to live up to these expectations, the ability of autonomous vehicles to plan safe trajectories and maneuver efficiently around obstacles will be paramount. However, motion planning among static or moving objects such as other vehicles is known to be a highly combinatorial problem, that remains challenging even for state-of-the-art algorithms. Indeed, the presence of obstacles creates exponentially many discrete maneuver choices, which are difficult even to characterize in the context of autonomous driving. This thesis explores a new approach to motion planning, based on using this notion of driving decisions as a guide to give structure to the planning problem, ultimately allowing easier resolution. This decision-based motion planning approach can find applications in cooperative driving, for instance to coordinate multiple vehicles through an unsignalized intersection, as well as in autonomous driving where a single vehicle plans its own trajectory. In the case of cooperative driving, decisions are known to correspond to the choice of a relative ordering for conflicting vehicles, which can be conveniently encoded as a graph. This thesis introduces a similar graph representation in the case of autonomous driving, where possible decisions -- such as overtaking the vehicle at a specific time -- are much more complex. Once a decision is made, planning the best possible trajectory corresponding to this decision is a much simpler problem, both in cooperative and autonomous driving. This decision-aware approach may lead to more robust and efficient motion planning, and opens exciting perspectives for combining classical mathematic programming algorithms with more modern machine learning techniques.

Les robots industriels ont évolué fondamentalement ces dernières années pour répondre aux exigences industrielles de machines et mécanismes toujours plus performants. Ceci se traduit aujourd’hui par de nouveaux robots anthropomorphes plus adaptés laissant entrevoir la réalisation de tâches plus complexes comme la découpe d’objets déformables telle que la découpe de viande ou soumis à de fortes sollicitations comme l’usinage. L’étude du comportement des robots anthropomorphes, à structures parallèles ou hybrides montre une anisotropie aussi bien cinématique, que dynamique, impactant la précision attendue. Ces travaux de thèse étudient l’intégration des redondances cinématiques qui permettent de pallier en partie ce problème en positionnant au mieux la tâche à réaliser dans un espace de travail compatible avec les capacités attendues. Ces travaux ont suivi une démarche en trois étapes : la modélisation analytique de cellules robotiques par équivalent sériel basée sur la méthode TCS, la formalisation des contraintes des processus de découpe de viande et d’usinage et une résolution par optimisation multicritère. Une première originalité de ces travaux réside en le développement d’un modèle à 6 degrés de liberté permettant d’analyser les gestes de l’opérateur qui optimise naturellement le comportement de son bras pour garantir la tâche qu’il réalise. La seconde originalité concerne le placement optimisé des redondances structurales (cellules à 9 ddls) où les paramètres de positionnement sont incorporés comme des variables pilotables (cellule à 11 ddls). Ainsi, ces travaux de thèse apportent des contributions à : - la définition de critères adaptés à la réalisation de tâches complexes et sollicitantes pour la gestion des redondances cinématiques ; - l’identification du comportement des structures sous sollicitations par moyen métrologique (Laser tracker) et l’auto-adaptation des trajectoires par l’utilisation d’une commande en effort industrielle ; - l’optimisation du comportement permettant l’amélioration de la qualité de réalisation des différents processus de coupe (découpe de viande et usinage). / Industrial robots have evolved fundamentally in recent years to reach the industrial requirements. We now find more suitable anthropomorphic robots leading to the realization of more complex tasks like deformable objects cutting such as meat cutting or constrained to high stresses as machining. The behavior study of anthropomorphic robots, parallel or hybrid one highlights a kinematic and dynamic anisotropy, which impacts the expected accuracy. This thesis studied the integration of the kinematic redundancy that can partially overcome this problem by well setting the task to achieve it in a space compatible with the expected capacity. This work followed a three-step approach: analytical modeling of robotic cells by serial equivalent based on the TCS method, formalizing the constraints of meat cutting process and machining process and a multicriteria optimization.The first originality of this work focuses on the development of a 6 DoFs model to analyze the operator actions who naturally optimizes his arm behavior to ensure the task it performs. The second originality concerns the optimized placement of structural redundancy (9 DoFs robotic cell) where positioning parameters are incorporated as controllable variables (11 DoFs robotic cell). Thus, the thesis makes contributions to : - the definition of criteria adapted to the realization of complex and under high stress task for the management of the kinematic redundancy; - the structural behavior identification, under stress, by metrology tools (Laser tracker ) and the self- adaptation paths by using an industrial force control; - the behavior optimization to improve the cutting process quality (meat cutting and machining).

Ce mémoire présente une étude de l'implantation optimale d'un robot en fonction de la tâche à réaliser, en prenant en compte les contraintes de non collisions. La démarche proposée s'est appuyée sur un système de C.A.O. classique. Elle se fonde sur une définition des tâches en termes de trajectoire de référence, définie par des points d'arrêt induits par le processus de fabrication et des points de passages disposés pour assurer la non collision avec les obstacles. Elle aboutit à une méthode permettant d'optimiser la trajectoire du robot de manière conjointe avec son implantation, en étendant le concept de variables articulaires à l'ensemble des variables décrivant les possibilités d'implantation du robot. Ces points de passage sont mis en place au cours du processus d'optimisation générale en fonction de l'implantation du robot et de la disposition des obstacles. Cette approche est introduite par une étude de la planification de trajectoires, à travers une méthode locale dissociant les objectifs de réalisation du process des objectifs d'anti-collision, suivie d'une étude du domaine d'implantation du robot. Ces travaux ont été appliqués aux problèmes de l'industrie automobile à travers l'exemple des postes de soudure par points et des postes de montage.

Les robots industriels ont évolué fondamentalement ces dernières années pour répondre aux exigences industrielles de machines et mécanismes toujours plus performants. Ceci se traduit aujourd’hui par de nouveaux robots anthropomorphes plus adaptés laissant entrevoir la réalisation de tâches plus complexes et soumis à de fortes sollicitations comme durant l’usinage. L’étude du comportement des robots anthropomorphes, à structures parallèles ou hybrides montre une anisotropie aussi bien cinématique, que dynamique, impactant la précision attendue. Ces travaux de thèse étudient l’intégration des redondances cinématiques qui permettent de pallier en partie ce problème en positionnant au mieux la tâche à réaliser dans un espace de travail compatible avec les capacités attendues. Ces travaux ont permis d’améliorer notre outil d’optimisation et de le tester à la fois sur un modèle Eléments Finis du robot et sur le robot réel. Ainsi, ces travaux de thèse apportent des contributions à : - la définition de critères adaptés à la réalisation de tâches complexes et sollicitantes pour la gestion des redondances cinématiques ; - l’identification du comportement des structures sous sollicitations par moyen métrologique (Laser tracker) ; - l’optimisation du comportement permettant l’amélioration de la qualité de réalisation des opérations d’usinage ; - la modélisation Eléments Finis des robots prenant en compte l’identification des rigidités des corps et articulaires. / Industrial robots have evolved fundamentally in recent years to reach the industrial requirements. We now find more suitable anthropomorphic robots leading to the realization of more complex tasks like deformable objects cutting such as meat cutting or constrained to high loading like during machining. The behavior study of anthropomorphic robots, parallel or hybrid one highlights a kinematic and dynamic anisotropy, which impacts the expected accuracy.This thesis studied the integration of the kinematic redundancy that can partially overcome this problem by well setting the task to achieve it in a space compatible with the expected capacity.This work helped us to improve our optimization tool and to try it on both FE model of the robot and real robot.Thus, the thesis makes contributions to: - the definition of criteria adapted to the realization of complex and under high loading task for the management of the kinematic redundancy; - the structural behavior identification, under loading, by metrology tools (Laser tracker) ; - the behavior optimization to improve the cutting process quality during machining ; - robots finite elements modeling using stiffness identification for both bodies and joints.

Ce travail étudie l'apport de l'algèbre différentielle à deux problématiques principales de la robotique mobile à roues, la localisation et la navigation. La première problématique consiste à être capable de dire où le robot se situe dans son environnement. Nous supposons ici que nous possédons un certain nombre de points d'intérêt de l'espace dont les coordonnées dans cette espace sont connues. En fonction du nombre de points d'intérêt, il est possible ou non de localiser le robot. Cette notion de localisabilité est définie et étudiée dans le cadre algébrique. Nous montrons que ce cadre d'étude est plus intéressant que le cadre géométrique en ce sens que non seulement il permet l'étude de la localisabilité mais en plus il permet de construire des estimateurs d'états permettant de reconstruire la posture du robot. Cette étude est effectuée dans cinq cas d'études pour quatre des cinq classes de robots mobiles à roues. La deuxième problématique étudiée est celle de la navigation d'une flottille décentralisée de robots dans un environnement complexe. Ce travail présente une architecture pouvant être utilisée dans une large classe de problème et bénéficiant des avantages des approches discrètes et des approches continues. En effet, à haut niveau, un bloc stratégie spécifie l'objectif, les contraintes et leurs paramètres ainsi que la fonction coût utilisée, à bas niveau, une trajectoire est calculée afin de minimiser la fonction coût en respectant l'objectif et les contraintes du problème. Cette minimisation est faite sur un horizon glissant de manière à pouvoir prendre en compte des modifications de l'environnement ou de la mission en cours de navigation / This work investigates the contribution of differential algebra to two main issues of wheel mobile robotics, localization and navigation. The first issue is to be able to tell where the robot is in its environment. We assume that we have a number of landmarks in space whose coordinates are known in this area. Depending on the number of landmarks, it is possible or not to localize the robot. This notion of localizability is defined and studied in the algebraic framework. We show that this framework is more interesting than the geometric framework in the sense that it not only allows the study of localizability, but it also allows us to construct estimators states to reconstruct the posture of the robot. This study was conducted in five cases study for four of the five classes of wheeled mobile robots. The second problem studied is that of a robot decentralized swarm navigation in a complex environment. This work presents an architecture that can be used in a wide class of problems and enjoying the benefits of discrete approaches and continuous approaches. Indeed, high-level block strategy specifies the goal, constraints and parameters as well as the cost function, a low-level block is used to compute a trajectory that minimize the cost function in accordance with the objective and the problem constraints. This minimization is done on a sliding window so it is possible to take changes in the environment or mission during navigation into account

Le but de ce doctorat est de déterminer dans quelle mesure les algorithmes issus de l’intelligence artificielle, principalement les Algorithmes Evolutionnaires et la Programmation Génétique, pourraient aider les algorithmes de l’automatique classique afin de permettre aux engins autonomes de disposer de capacités bien supérieures, et ce dans les domaines de l’identification, de la planification de trajectoire, du pilotage et de la navigation.De nouveaux algorithmes ont été développés, dans les domaines de l’identification, de la planification de trajectoire, de la navigation et du contrôle, et ont été testés sur des systèmes de simulation et des aéronefs du monde réel (Oktokopter du ST2I, Bebop.Drone de la société Parrot, Twin Otter et F-16 de la NASA) de manière à évaluer les apports de ces nouvelles approches par rapport à l’état de l’art.La plupart de ces nouvelles approches ont permis d’obtenir de très bons résultats comparés à l’état de l’art, notamment dans le domaine de l’identification et de la commande, et un approfondissement des travaux devraient être engagé afin de développer le potentiel applicatifs de certains algorithmes. / The object of this PhD has consisted in elaborating evolutionary computing algorithms to find interesting solutions to important problems in several domains of automation science, applied to aircrafts mission conduction and to understand what could be the advantages of using such approaches, compared to the state-of-the-art, in terms of efficiency, robustness, and effort of implementation.New algorithms have been developed, in Identification, Path planning, Navigation and Control and have been tested on simulation and on real world platforms (AR.Drone 3.0 UAV (Parrot), Oktokopter UAV, Twin Otter and military fighter F-16 (NASA LaRC)), to assess the performances improvements, given by the new proposed approaches.Most of these new approaches provide very interesting results; and research work (on control by evolutionary algorithms, identification by genetic programming and relative navigation) should be engaged to plan potential applications in different real world technologies.

Cette thèse porte sur la navigation d'agents dans un environnement manufacturier. Le cadre général du travail relève de la navigation d'AGVs (véhicules autoguidés), transportant librement et intelligemment leur produit. L'objectif est de proposer des outils permettant la navigation autonome et coopérative d’une flotte d’AGVs dans des systèmes de production manufacturiers où les contraintes temporelles sont importantes. Après la présentation d'un état de l'art sur chaque domaine (systèmes manufacturiers et navigation d'agents), les impacts de la mutualisation entre ceux-ci sont présentés. Ensuite, deux problématiques, liées à la navigation d'agents mobiles dans des environnements manufacturiers, sont étudiées. La première problématique est centrée sur la planification de trajectoire décentralisée où une fonction d'ordonnancement est combinée au planificateur pour chaque agent. Cette fonction permet de choisir une ressource lors de la navigation afin d'achever l'opération du produit transporté le plus tôt possible. La première solution consiste en une architecture hétérarchique où les AGVs doivent planifier (ou mettre à jour) leur trajectoire, ordonnancer leur produit pour l'opération en cours et résoudre leurs propres conflits avec les agents à portée de communication. Pour la seconde approche, une architecture hybride à l'aide d'un superviseur, permettant d'assister les agents durant leur navigation, est proposée. L'algorithme de planification de trajectoire se fait en deux étapes. La première étape utilise des informations globales fournies par le superviseur pour anticiper les collisions. La seconde étape, plus locale, utilise les données par rapport aux AGVs à portée de communication afin d'assurer l'évitement de collisions. Afin de réduire les temps de calcul des trajectoires, une optimisation par essaims particulaires est introduite. La seconde problématique se focalise sur la commande coopérative permettant un rendez-vous d'agents non holonomes à une configuration spécifique. Ce rendez-vous doit être atteint en un temps donné par un cahier des charges, fourni par le haut-niveau de contrôle. Pour résoudre ce problème de rendez-vous, nous proposons une loi de commande à temps fixe (i.e. indépendant des conditions initiales) par commutation permettant de faire converger l’état des AGVs vers une resource. Des résultats numériques et expérimentaux sont fournis afin de montrer la faisabilité des solutions proposées. / This thesis is focused on agent navigation in a manufacturing environment. The proposed framework deals with the navigation of AGVs (Automated Guided Vehicles), which freely and smartly transport their product. The objective is to propose some tools allowing the autonomous and cooperative navigation of AGV fleets in manufacturing systems for which temporal constraints are important. After presenting the state of the art of each field (manufacturing systems and agent navigation), the impacts of the cross-fertilization between these two fields are presented. Then, two issues, related to the navigation of mobile agents in manufacturing systems, are studied. The first issue focuses on decentralized motion planning where a scheduling function is combined with the planner for each agent. This function allows choosing a resource during the navigation to complete the ongoing operation of the transported product at the soonest date. The first proposed approach consists in a heterarchical architecture where the AGVs have to plan (or update) their trajectory, schedule their product and solve their own conflict with communicating agents. For the second approach, hybrid architecture with a supervisor, which assists agents during the navigation, is proposed. The motion planning scheme is divided into two steps. The first step uses global information provided by the supervisor to anticipate the future collisions. The second step is local and uses information from communicating agents to ensure the collision avoidance. In order to reduce the computational times, a particle swarm optimization is introduced. The second issue is focused on the cooperative control, allowing a rendezvous of nonholomic agents at a specific configuration. This rendezvous must be achieved in a prescribed time, provided by the higher level of control. To solve this rendezvous, a fixed time (i.e. independent of initial conditions) switching control law is proposed, allowing the convergence of agent states towards a resource configuration. Some numerical and experimental results are provided to show the feasibility of the proposed methods.