Reproduction de : Thèse de doctorat : Intelligence artificielle : Toulouse 3 : 2007. / Titre provenant de l'écran-titre. Bibliogr. p. 120-124.

Revision of Karl Iagnemma's Thesis (Ph. D.)--Massachusetts Institute of Technology, 2001. / Includes bibliographical references (p. [101]-107) and index.

Dans cette thèse, des méthodes dites de Lyapunov sont proposées afin de résoudre des problèmes liés à la coordination distribuée des systèmes multiagent, plus précisément, un groupe de systèmes (agents) non-linéaires formés de robots mobiles non-holonomes est considéré. Pour ce groupe de systèmes, des lois de commande distribuée sont proposées dans le but de résoudre des problèmes de type leader-suiveur en formation et aussi des problèmes de type formation sans-leader par une approche de consensus, sous différentes hypothèses sur le graphe de communication et surtout sur les vitesses du leader.L'originalité de ce travail est dans l'approche proposée pour l'étude de stabilité de la boucle fermée, cette approche consiste à transformer les deux derniers problèmes en des problèmes de stabilisation globale asymptotique d'un ensemble invariant. L’analyse de stabilité est basée sur la construction de fonction de Lyapunov et de fonction de Lyapunov-Karasovskii strictes pour des classes de systèmes non-linéaires variant dans le temps présentant des retards bornés et variant dans le temps. / In this thesis, we propose a Lyapunov based approaches to address some distributedsolutions to multi-agent coordination problems, more precisely, we consider a groupof agents modeled as nonholonomic mobile robots, we provide a distributed controllaws in order to solve the leader-follower and the leaderless consensus problems under different assumptions on the communication graph topology and on the leader’strajectories. The originality of this work relies on the closed-loop analysis approach, that is, it consists on transforming the last two problems into a global stabilization problem of an invariant set. The stability analysis is mainly based on the construction of strict Lyapunov functions and strict Lyapunov-Krasovskii functionals for a classes of nonlinear time-varying and/or delayed systems.

L’adaptation et l’application des méthodes formelles de vérification et de développement à des systèmes et algorithmes distribués est un domaine de recherche très actif. Un des défis principaux réside dans la variété des modèles calculatoires qui existent en algorithmique répartie : des encodages naïfs conduisent à des espaces d’états dont la taille dépasse les capacités des outils les plus puissants de vérification. D’autre part, la complexité intrinsèque de ces algorithmes fait que leur correction n’est pas évidente même pour leurs concepteurs. Dans cette thèse on s’intéresse à l’analyse formelle de protocoles de robots mobiles, un modèle de calcul particulièrement original car les agents ne disposent ni de mémoire (locale ou partagée) ni de la capacité de communiquer par échange de messages. Un cadre général permettant d'exprimer les modèles robotiques est présenté dans cette thèse. Ce modèle a permit d'utiliser à la fois la vérification par model checking d’algorithmes proposés dans la littérature et la synthèse formelle d’algorithmes (optimaux) pour un problème donné, quelque soit le niveau d'asynchronisme du modèle robotique étudié. / The topic of autonomous mobile robots continues to generate a lot of interest in the algorithmic community, both from a purely theoretical perspective and from a more applicative one. The model is now well understood, and the problems under investigation are becoming more and more complex. Correctness proofs are usually very intricate and elaborate, often leaving margin of doubts. This thesis focuses on a new approach to formally study correctness in robots systems and to automatically generate algorithmic solutions. In fact, we propose a general framework to express robot models, and where automated technics like model checking and algorithm synthesis can be used, moreover we show their applicability in robots models under all possible synchronicity levels (from fully synchronous to fully asynchronous).

La foresterie est une industrie majeure dans plusieurs parties du monde. Elle dépend de l’inventaire forestier, qui consiste en la mesure des attributs des arbres. Dans ce mémoire, nous proposons l’utilisation de la cartographie 3D, basée sur l’algorithme itervative closest point, pour automatiquement mesurer des diamètres d’arbres à partir d’observations d’un robot mobile. Bien que des études précédentes démontraient le potentiel d’une telle technologie, elles présentaient des lacunes en terme de rigueur d’analyse et ne fonctionnaient pas dans des environnements forestiers difficiles. Nous avons validé plusieurs méthodes pour l’estimation de diamètre, dont deux nouvelles, avec un jeu de données nouveau et varié comportant quatre sites forestiers, 11 trajectoires de robot totalisant 1458 observations d’arbre et 1.4 hectares de forêt. De plus, nous faisons des recommendations sur le déploiement de robots mobiles dans un contexte forestier. Nous concluons que notre méthode de cartographie est utilisable dans le contexte de l’inventaire forestier automatisé, avec notre meilleure méthode donnant une erreur quadratique de 3:45 cm pour notre jeu de données en entier et 2:04 cm dans des conditions idéales, c’est-à-dire une forêt mature et espacée. / Forestry is a major industry in many parts of the world. It relies on forest inventory, which consists of measuring tree attributes. In this thesis, we propose the use of 3D mapping, based on the iterative closest point algorithm, to automatically measure tree diameters in forests from mobile robot observations. While previous studies showed the potential for such technology, they lacked a rigorous analysis of diameter estimation methods in challenging forest environments. Here, we validated multiple diameter estimation methods, including two novel ones, in a new varied dataset of four different forest sites, 11 trajectories, totalling 1458 tree observations and 1.4 hectares. We provide recommendations for the deployment of mobile robots in a forestry context. We conclude that our mapping method is usable in the context of automated forest inventory, with our best method yielding a root mean square error of 3:45 cm for our whole dataset, and 2:04 cm in ideal conditions consisting of mature forest with well spaced trees.

Ce mémoire présente les résultats d'une recherche ayant pour but d'explorer l'utilisation d'un simulateur pour accélérer l'évolution de contrôleurs d'un robot mobile exécutant une tâche visuelle au sein d'un environnement de réalité augmentée. La tâche retenue pour effectuer la démonstration de l'intégration du système évolutionnaire consiste à suivre une ligne au sol à l'aide d'une caméra. La réalisation de ce projet a nécessité le développement d'une plate-forme de robot mobile compacte, d'une capacité de calcul suffisante pour être complètement autonome. Ce robot est destiné à un environnement synthétique généré à l'aide d'un projecteur à cristaux liquides. La modélisation du robot dans cet environnement a permis l'élaboration d'un simulateur pouvant être déployé sur une grappe d'ordinateurs permettant une accélération considérable de l'évolution grâce à la parallélisation de l'évaluation de la performance des contrôleurs. Les meilleurs contrôleurs obtenus au terme de l'évolution, employant la technique de programmation génétique, ont été transférés avec succès sur le robot.

Ce mémoire présente 2 types de méthodes pour effectuer la réorientation d’un robot sériel en chute libre en utilisant les mouvements internes de celui-ci. Ces mouvements sont prescrits à partir d’algorithmes de planification de trajectoire basés sur le modèle dynamique du robot. La première méthode tente de réorienter le robot en appliquant une technique d’optimisation locale fonctionnant avec une fonction potentielle décrivant l’orientation du système, et la deuxième méthode applique des fonctions sinusoïdales aux articulations pour réorienter le robot. Pour tester les performances des méthodes en simulation, on tente de réorienter le robot pour une configuration initiale et finale identiques où toutes les membrures sont alignées mais avec le robot ayant complété une rotation de 180 degrés sur lui-même. Afin de comparer les résultats obtenus avec la réalité, un prototype de robot sériel plan flottant possédant trois membrures et deux liaisons rotoïdes est construit. Les expérimentations effectuées montrent que le prototype est capable d’atteindre les réorientations prescrites si peu de perturbations extérieures sont présentes et ce, même si le contrôle de l’orientation est effectué en boucle ouverte. / This master’s thesis presents two different types of methods to reorient a free-floating serial manipulator with internal motion using path planning algorithms based on a dynamic model of the manipulator. The first method attempts to reorient the robot with a local optimisation technique using a potential function describing the global orientation of the robot, while the second method applies sinusoidal functions to the joints of the robot in order to reorient it. The proposed methods are tested with a robot that starts from a pose in which all the links are aligned and ends with the same configuration but with the robot having completed a 180 degrees rotation. To verify the simulation results against a real robot, a prototype of a planar robot with three bodies and two revolute joints is built. The experiments conducted show that the prototype is able to achieve the prescribed reorientation if almost no external torque is applied to the system, even though the control of the orientation is implemented in an open-loop mode.

Ce mémoire présente les concepts théoriques et pratiques qui permettront à un groupe de véhicules sans-pilote hétérogène d'estimer la position et l'orientation relative des véhicules voisins en temps réel. Le système de localisation relative leur permettra donc de se coordonner localement afin d'effectuer des missions d'équipe telles que le transport d'une charge et le vol en formation. La localisation relative est effectuée avec une matrice de capteurs ultrasoniques et un algorithme de différence de temps d'arrivée des signaux. Le système présenté peut être monté à bord de véhicules sans-pilote et ne requiert pas d'architecture externe.

Ce travail propose de nouvelles stratégies pour la planification et le contrôle des robots mobiles non-holonomes, de nouveaux algorithmes sont proposés. Tout d'abord, l'identification des différents modèles cinématiques de robot mobiles est discutée, et le problème est formulé comme l'identification en temps réel du signal de commutation d'un système singulier non-linéaire et à commutation. Deuxièmement, sur la base du modèle identifié, un algorithme de planification locale est proposé, et le contour irrégulier de l' obstacle est représenté par des segments. La trajectoire est obtenue en résolvant un problème de commande optimale avec contraintes. Troisièmement, nous appliquons un contrôleur i-PID pour contrôler le robot mobile non-holonome avec la perturbation dans les mesures. Un paramètre de commutation α est proposé en raison de la particularité du système non-holonome. En plus de notre algorithme de planification proposé, une autre approche de planification en utilisant de champs de potentiels est proposée. La nouvelle fonction de champ de potentiel est en mesure de résoudre les problèmes de minima locaux et de produire des forces lisses pour éviter les oscillations. Enfin, une approche de planification coopérative entre robots est proposée en utilisant les informations locales partagées par chaque robot. Le graphe de visibilité est utilisé pour générer une série d'objectifs intermédiaires qui assureront aux robots d'atteindre l'objectif final, et un algorithme est proposé pour étendre les obstacles et fusionner les obstacles lorsque deux obstacles s'entrecroisent

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.