Nous presentons une methode generale de planification : L'algorithme Fil d'Ariane. Cette methode est appliquee au probleme de la planification automatique de trajectoires. L'originalite de la methode reside dans son adaptation automatique a la complexite du probleme pose. La planification automatique de trajectoires est transformee en un probleme d'optimisation d'une fonctionnelle de<br />l'espace des plans dans $R^+$. Cette optimisation permet d'explorer<br />les positions accessibles a partir d'une configuration initiale. La<br />methode ne construit pas l'espace des configurations; par contre, a<br />mesure que le temps passe, une approximation de plus en plus fine de<br />l'espace accessible est construite. Cette approximation est faite par<br />un premier algorithme appele l'algorithme $EXPLORE$ qui garantit la<br />completude pour une resolution donnee de la methode. D'autre part,<br />un deuxieme algorithme, l'algorithme $SEARCH$, permet d'accelerer<br />la recherche d'un chemin et d'atteindre la configuration finale. En<br />resume, la methode proposee permet de construire un planificateur<br />complet pour une resolution donnee qui exploite d'une maniere<br />efficace l'espace des plans pour explorer l'espace des configurations.<br />Nous avons implante deux planificateurs bases sur l'algorithme Fil<br />d'Ariane : le premier est un planificateur de trajectoires pour un<br />robot mobile holonome, et le deuxieme, notre experimentation<br />principale, un planificateur de trajectoires pour un bras manipulateur<br />a six degres de liberte. Pour ce dernier, nous avons realise une<br />implantation de notre algorithme sur une machine massivement<br />parallele et planifie les mouvements d'un bras a 6 degres de<br />liberte.<br />Pour optimiser les fonctions des algorithmes EXPLORE et SEARCH nous<br />avons utilise les algorithmes genetiques. Ces algorithmes<br />sont des methodes d'optimisation stochastiques facilement<br />parallelisables.

L’intelligence artificielle est un domaine de l’informatique étudiant la conception d’agents intelligents. Un agent est une entité acquérant de l’information sur son environnement par ses capteurs et agissant sur son environnement à travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vidéo, alors que d’autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vidéo et de la robotique partagent certaines caractéristiques, dont la nécessité de prendre des décisions en temps réel dans un environnement dynamique ainsi qu’une vue incomplète sur cet environnement. Ce mémoire est divisé en deux chapitres. Le premier chapitre traite d’une approche de planification de trajectoires exploitant la géométrie d’une classe particulière de robots omnidirectionnels non-holonomes afin de calculer des chemins adéquats leur permettant d’atteindre une destination désirée. Les résultats obtenus avec cette approche tendent à démontrer qu’elle est plus efficace que les algorithmes traditionnels de planification de trajectoires grâce à l’information additionnelle prise en compte lors du calcul. Le second chapitre décrit l’architecture décisionnelle de l’agent intelligent SPAR qui est en mesure de jouer de façon autonome des parties de StarCraft : Brood War, un jeu de stratégie en temps réel. L’architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires à ceux du premier chapitre. Elle permet de faire face plus facilement et de façon plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficultés propres à ce type de jeu. Ces difficultés incluent un degré élevé de concurrence dans les actions et une multitude d’unités à contrôler dans un contexte temps réel. L’agent SPAR a participé aux volets 2011 et 2012 de la compétition AIIDE de StarCraft et à l’édition 2012 de la compétition SSCAI où il a obtenu à chaque fois des résultats honorables.

Les systèmes de transport intelligents (STI) sont conçus pour améliorer les transports, réduire les accidents, le temps de transport et la consommation de carburant, tout en augmentant la sécurité, le confort et l'efficacité de conduite. L'objectif final de ITS est de développer ADAS pour faciliter les tâches de conduite, jusqu'au développement du véhicule entièrement automatisé. Les systèmes actuels ne sont pas assez robustes pour atteindre un niveau entièrement automatisé à court terme. Les environnements urbains posent un défi particulier, car le dynamisme de la scène oblige les algorithmes de navigation à réagir en temps réel aux éventuels changements, tout en respectant les règles de circulation et en évitant les collisions avec les autres usagers de la route. Sur cette base, cette thèse propose une approche de la planification locale en deux étapes pour apporter une solution au problème de la navigation en milieu urbain. Premièrement, les informations statiques des contraintes de la route et du véhicule sont considérées comme générant la courbe optimale pour chaque configuration de virage réalisable, où plusieurs bases de données sont générées en tenant compte de la position différente du véhicule aux points de début et de fin des courbes, permettant ainsi une analyse réaliste. planificateur de temps pour analyser les changements de concavité en utilisant toute la largeur de la voie. Ensuite, la configuration réelle de la route est envisagée dans le processus en temps réel, où la distance disponible et la netteté des virages à venir et consécutifs sont étudiées pour fournir un style de conduite à la manière humaine optimisant deux courbes simultanément, offrant ainsi un horizon de planification étendu. Par conséquent, le processus de planification en temps réel recherche le point de jonction optimal entre les courbes. Les critères d’optimalité minimisent à la fois les pics de courbure et les changements abrupts, en recherchant la génération de chemins continus et lisses. Quartic Béziers est l'algorithme d'interpolation utilisé en raison de ses propriétés, permettant de respecter les limites de la route et les restrictions cinématiques, tout en permettant une manipulation facile des courbes. Ce planificateur fonctionne à la fois pour les environnements statiques et dynamiques. Les fonctions d'évitement d'obstacles sont présentées en fonction de la génération d'une voie virtuelle qui modifie le chemin statique pour effectuer chacune des deux manoeuvres de changement de voie sous la forme de deux courbes, convertissant le problème en un chemin statique. Ainsi, une solution rapide peut être trouvée en bénéficiant du planificateur local statique. Il utilise une discrétisation en grille de la scène pour identifier l'espace libre nécessaire à la construction de la route virtuelle, où le critère de planification dynamique consiste à réduire la pente pour les changements de voie. Des essais de simulation et des tests expérimentaux ont été réalisés pour valider l'approche dans des environnements statiques et dynamiques, adaptant la trajectoire en fonction du scénario et du véhicule, montrant la modularité du système. / Intelligent Transportation Systems (ITS) developments are conceived to improve transportation reducing accidents, transport time and fuel consumption, while increasing driving security, comfort and efficiency. The final goal of ITS is the development of ADAS for assisting in the driving tasks, up to the development of the fully automated vehicle. Despite last ADAS developments achieved a partial-automation level, current systems are not robust enough to achieve fully-automated level in short term. Urban environments pose a special challenge, since the dynamism of the scene forces the navigation algorithms to react in real-time to the eventual changes, respecting at the same time traffic regulation and avoiding collisions with other road users. On this basis, this PhD thesis proposes a two-staged local planning approach to provide a solution to the navigation problem on urban environments. First, static information of both road and vehicle constraints is considered to generate the optimal curve for each feasible turn configuration, where several databases are generated taking into account different position of the vehicle at the beginning and ending points of the curves, allowing the real-time planner to analyze concavity changes making use of the full lane width.Then, actual road layout is contemplated in the real-time process, where both the available distance and the sharpness of upcoming and consecutive turns are studied to provide a human-like driving style optimizing two curves concurrently, offering that way an extended planning horizon. Therefore, the real-time planning process searches the optimal junction point between curves. Optimality criteria minimizes both curvature peaks and abrupt changes on it, seeking the generation of continuous and smooth paths. Quartic Béziers are the interpolating-based curve algorithm used due to their properties, allowing compliance with road limits and kinematic restrictions, while allowing an easy manipulation of curves. This planner works both for static and dynamic environments. Obstacle avoidance features are presented based on the generation of a virtual lane which modifies the static path to perform each of the two lane change maneuvers as two curves, converting the problem into a static-path following. Thus, a fast solution can be found benefiting from the static local planner. It uses a grid discretization of the scene to identify the free space to build the virtual road, where the dynamic planning criteria is to reduce the slope for the lane changes. Both simulation and experimental test have been carried out to validate the approach, where vehicles performs path following on static and dynamic environments adapting the path in function of the scenario and the vehicle, testing both with low-speed cybercars and medium-speed electic platforms, showing the modularity of the system.

La notion de platitude aété bien définie et largement étudiée pour les systèmes dynamiques de dimension finie. Une des conséquences marquantes de cette propriété est de permettre la paramétrisation des trajectoires (état et commande) par des fonctions libres et leurs dérivées, rendant ainsi aisée la solution d'un problème important en contrôle des systèmes dynamiques: la planification de trajectoires. Pour les systèmes linéaires de dimension finie, on a coïncidence exacte entre platitude et commandabilité, via la mise sous forme de Brunovsky. La possibilité de définir une notion convenable de platitude en dimension infinie, et d'étendre la notion de forme de Brunovsky à certaines classes de systèmes de dimension infinie est examinée, et une définition de la platitude est proposée pour ces systèmes. L'étude de la platitude de l'équation générale de diffusion à une variable d'espace est complètement traitée. Une méthode d'obtention d'une paramétrisation d'une famille dense de trajectoires est proposée, et la canonicité de la représentation de ces trajectoires est démontrée. Divers cas d'étude sont proposés, avec des applications à la planification de trajectoires. L'étude complète de l'équation de Korteweg-De Vries mono-dimensionnelle linéaire est réalisée, ainsi que celle d'un problème de diffusion à deux variables d'espace, montrant les possibilités d'extension de la méthode à un cadre beaucoup plus général.

Le contexte de la robotique de service est caractérisé par la présence de l'homme dans l'espace de travail du robot. Les mouvements de ces robots ne doivent perturber ni la sécurité de l'homme ni son confort. D'un point de vu planification de mouvement, le planificateur doit d'une part éviter de heurter l'homme ou l'environnement et d'autre part adapter les limites cinématiques du robot en fonction de la proximité de l'homme. A chaque niveau du système (planification et exécution/contrôle), le robot doit garantir la sécurité et le confort de l'homme. Nous proposons une approche de la planification et du contrôle de mouvement basée sur des trajectoires polynomiales. Dans une première partie, nous présentons un générateur de trajectoires qui limite la vitesse, l'accélération et le jerk. Il génère des trajectoires composées de suites de segments de courbes cubiques. Le cas mono-dimensionnel est d'abord présenté puis étendu au cas multi-dimensionnel. Dans une deuxième partie, nous proposons d'approximer les trajectoires par des suites de triplets de segments de courbes cubiques. Cette méthode permet de calculer des trajectoires respectant une erreur maximale donnée. Ces générateurs de trajectoire sont intégrés au planificateur de chemin et produisent des trajectoires directement exécutables. Une application originale de l'approximation permet d'approximer une trajectoire définie dans l'espace cartésien par une trajectoire définie dans l'espace articulaire. Cette approche simplifie la structure du contrôleur du robot. La présence de l'homme dans l'espace de travail du robot nécessite une adaptation des trajectoires pendant l'exécution. Nous proposons une méthode pour adapter la loi de mouvement de la trajectoire multidimensionnelle pendant l'exécution. Ces travaux, menés dans le cadre du projet européen DEXMART et du projet ANR ASSIST, ont été intégrés et validés sur les plateformes Jido et PR2 du LAAS-CNRS.

Un des buts de la recherche et du développement des systèmes de transport intelligents est d'augmenter le confort et la sécurité des passagers, tout en réduisant la consommation d'énergie, la pollution de l'air et le temps de déplacement. L'introduction de voitures complètement autonomes sur la voie publique nécessite la résolution d'un certain nombre de problèmes techniques et en particulier de disposer de modules de planification de trajectoire robustes. Ce travail de thèse s'inscrit dans ce cadre. Il propose une architecture modulaire pour la planification de trajectoire d'un véhicule autonome. La méthode permet de générer des trajectoires constituées de courbes interpolées adaptées à des environnements complexes comme des virages, des ronds-points, etc., tout en garantissant la sécurité et le confort des passagers. La prise en compte de l'incertitude des systèmes de perception, des limites physiques du véhicule, de la disposition des routes et des règles de circulation est aussi assurée dans le calcul de la trajectoire. L'algorithme est capable de modifier en temps réel la trajectoire prédéfinie de façon à éviter les collisions. Le calcul de la nouvelle trajectoire maintient les accélérations latérales à leur minimum, assurant ainsi le confort du passager. L'approche proposée a été évaluée et validée dans des environnements simulés et sur des véhicules réels. Cette méthode permet d'éviter les obstacles statiques et dynamiques repérés par le système de perception.Un système d'aide à la conduite pour le contrôle partagé basé sur cette architecture est introduit. Il prend en compte l'arbitrage, la surveillance et le partage de la conduite tout en maintenant le conducteur dans la boucle de contrôle. Il laisse le conducteur agir tant qu'il n'y a pas de danger et interagit avec le conducteur dans le cas contraire. L'algorithme se décompose donc en deux processus : 1) évaluation du risque et, s'il y a un risque avéré 2) partage du contrôle à l'aide de signaux haptiques via le volant.La méthode de planification de trajectoire présentée dans cette thèse est modulaire et générique. Elle peut être intégrée facilement dans toute architecture d'un véhicule autonome. / Developments in the Intelligent Transportation Systems (ITS) field show promising results at increasing passengers comfort and safety, while decreasing energy consumption, emissions and travel time. In road transportation, the appearance of automated vehicles is significantly aiding drivers by reducing some driving-associated tedious tasks. However, there is still a long way to go before making the transition between automated vehicles (i.e. vehicles with some automated features) and autonomous vehicles on public roads (i.e. fully autonomous driving), specially from the motion planning point of view. With this in mind, the present PhD thesis proposes the design of a generic modular architecture for automated vehicles motion planning. It implements and improves curve interpolation techniques in the motion planning literature by including comfort as the main design parameter, addressing complex environments such as turns, intersections and roundabouts. It will be able to generate suitable trajectories that consider measurements' incertitude from the perception system, vehicle’s physical limits, the road layout and traffic rules. In case future collision states are detected, the proposed approach is able to change---in real-time---the current trajectory and avoid the obstacle in front. It permits to avoid obstacles in conflict with the current trajectory of the ego-vehicle, considering comfort limits and developing a new trajectory that keeps lateral accelerations at its minimum. The proposed approach is tested in simulated and real urban environments, including turns and two-lane roundabouts with different radii. Static and dynamic obstacles are considered as to face and interact with other road actors, avoiding collisions when detected. The functional architecture is also tested in shared control and arbitration applications, focusing in keeping the driver in the control loop to addition the system's supervision over drivers’ knowledge and skills in the driving task. The control sharing advanced driver assistance system (ADAS) is proposed in two steps: 1) risk assessment of the situation in hand, based on the optimal trajectory and driving boundaries identified by the motion planning architecture and; 2) control sharing via haptic signals sent to the driver through the steering wheel. The approach demonstrates the modularity of the functional architecture as it proposes a general solution for some of today's unsolved challenges in the automated driving field.

Les travaux présentés dans cette thèse s'inscrivent dans la cadre de la planification de trajectoires optimales en présence d'obstacles pour des robots mobiles de type voiture et pour des robots à pattes. Le modèle de robot de type voiture étudié est celui de Dubins. Il s'agit grossièrement d'une voiture se déplaçant en marche avant uniquement et dont le rayon de braquage est minoré par 1. Nous avons considéré le problème du calcul d'une enveloppe convexe de courbure bornée d'un ensemble S de points du plan, c'est-à-dire d'un ensemble contenant S et dont le bord est de courbure bornée et de périmètre minimal. Nous montrons que si le rayon du plus petit disque contenant S est supérieur à 1, une telle enveloppe est unique. Nous montrons que le calcul d'une enveloppe convexe de courbure bornée se ramène à un problème d'optimisation convexe ou à la résolution d'un ensemble de systèmes algébriques. Nous proposons également un algorithme exact polynomial pour le calcul de trajectoires optimales en longueur lorsque le robot se déplace en présence d'obstacles dont les bords sont de courbure bornée et constitués de segments de droite et d'arcs de cercle. De tels obstacles peuvent être obtenu comme enveloppes convexes de courbure bornée d'obstacles polygonaux. L'algorithme calcule un graphe et recherche un plus court chemin dans ce graphe. Le calcul de ce graphe est effectué grâce à des techniques de géométrie algorithmique et par la résolution de systèmes algébriques dont nous montrons, à l'aide de résultants, qu'ils ont un nombre fini de solutions. Nous avons également étudié le problème de la planification de trajectoires pour des robots à pattes dont le corps est ponctuel et dont toutes les pattes sont attachées au même point. Les pattes du robot ont une longueur bornée et ne sont autorisées à se poser que dans certaines régions polygonales du plan. Nous présentons un algorithme quasi optimal pour le calcul de l'ensemble des positions du corps du robot en équilibre stable. Par une transformation judicieuse, nous nous ramenons au calcul de l'espace libre d'un robot de la forme d'un demi disque se déplaçant en présence d'obstacles.

L'objet de cette thèse est l'étude et la mise en oeuvre d'un système de gestion automatique de la configuration d'une formation d'avions sans pilote, ou drones. Les objectifs sont, d'une part, d'améliorer la sécurité et l'efficacité d'un groupe de drones de combat, et, d'autre part, de faire le lien entre les niveaux de planification de missions et les niveaux fonctionnels de contrôle de la formation. Le vol en formation est particulièrement bien adapté pour des applications militaires en milieux hostiles, qui requièrent des synchronisations pour l'arrivée sur les cibles ou du support mutuel pour le brouillage. L'une des difficultés soulevées est le choix autonome de la configuration. Notre approche est de mettre en oeuvre, entre les niveaux décisionnels et les niveaux fonctionnels, une couche intermédiaire dédiée à la formation et à la gestion autonome de sa configuration. La configuration ainsi déterminée doit être affectée aux avions de la formation en tenant compte des contraintes tactiques et des ressources de chacun. Enfin, la sécurité du vol est un élément primordial. Il faut donc pouvoir planifier des manoeuvres de reconfiguration pour passer d'une configuration à une autre, en respectant les distances minimales entres avions. Des solutions ont été développées à partir de l'algorithme Branch & Bound pour résoudre les problèmes d'allocations, et de l'algorithme A* pour la planification de trajectoires dans la formation. De plus, un contrôle de vol de la formation a été implémenté. Ceci a permis de valider notre approche par des simulations et des expérimentations réelles.

Un système robotique agit par le mouvement dans un monde physique. La capacité de planification de mouvement est une composante essentielle de son autonomie. C'est le thème des travaux présentés dans ce mémoire. Ils s'articulent selon quatre axes.Le premier concerne l'algorithmique géométrique du mouvement. La ligne forte qui se retrouve dans nos travaux est de privilégier des méthodes effectives de planification. En effet, la plupart des problèmes réels résistent aux approches algorithmiques exactes; nous présentons des approches de nature différente, qui en satisfaisant une forme plus faible de complétude (e.g. complétude probabiliste) sont capables de mieux répondre aux besoins des applications en termes d'efficacité et de robustesse algorithmique. Nous considérons ensuite des problèmes plus riches que la seule planification de mouvement, et plus directement liés à la notion de tâches en robotique. La seconde partie porte sur la planification de tâches de manipulation d'objets. La formulation géométrique que nous présentons permet d'étendre le concept d'espace des configurations à la planification automatique de ces tâches. D'autre part, les mouvements d'un robot s'effectuant dans un monde réel, la robustesse algorithmique doit être étendue à la robustesse de la boucle planification/contrôle des mouvements vis à vis des incertitudes dans les modèles manipulés par le raisonnement ou des imprécisions liées à l'exécution. C'est le thème de la troisième partie qui présente une approche combinant planification avec incertitude et modes réactifs: les algorithmes de planification utilisent la connaissance a priori sur la tâche pour produire des primitives référencées capteurs adaptées à la robotique mobile. Enfin, la dernière partie porte sur la planification de mouvements pour des robots mobiles évoluant dans des environnements naturels non structurés. Les techniques prése ntées permettent de traiter des systèmes de locomotion complexes et des terrains fortement accidentés.

L???intelligence artificielle est un domaine de l???informatique ??tudiant la conception d???agents intelligents. Un agent est une entit?? acqu??rant de l???information sur son environnement par ses capteurs et agissant sur son environnement ?? travers ses actionneurs. Certains agents existent seulement dans le domaine logiciel, comme par exemple un agent intelligent pour un jeu vid??o, alors que d???autres existent dans le monde physique, tels les robots mobiles. Les domaines des jeux vid??o et de la robotique partagent certaines caract??ristiques, dont la n??cessit?? de prendre des d??cisions en temps r??el dans un environnement dynamique ainsi qu???une vue incompl??te sur cet environnement. Ce m??moire est divis?? en deux chapitres. Le premier chapitre traite d???une approche de planification de trajectoires exploitant la g??om??trie d???une classe particuli??re de robots omnidirectionnels non-holonomes afin de calculer des chemins ad??quats leur permettant d???atteindre une destination d??sir??e. Les r??sultats obtenus avec cette approche tendent ?? d??montrer qu???elle est plus efficace que les algorithmes traditionnels de planification de trajectoires gr??ce ?? l???information additionnelle prise en compte lors du calcul. Le second chapitre d??crit l???architecture d??cisionnelle de l???agent intelligent SPAR qui est en mesure de jouer de fa??on autonome des parties de StarCraft : Brood War, un jeu de strat??gie en temps r??el. L???architecture de SPAR inclut entre autres des algorithmes de planification de trajectoires similaires ?? ceux du premier chapitre. Elle permet de faire face plus facilement et de fa??on plus rigoureuse, en comparaison avec les architectures existantes, aux nombreuses difficult??s propres ?? ce type de jeu. Ces difficult??s incluent un degr?? ??lev?? de concurrence dans les actions et une multitude d???unit??s ?? contr??ler dans un contexte temps r??el. L???agent SPAR a particip?? aux volets 2011 et 2012 de la comp??tition AIIDE de StarCraft et ?? l?????dition 2012 de la comp??tition SSCAI o?? il a obtenu ?? chaque fois des r??sultats honorables.