Comment un robot peut-il estimer si une tâche est réalisable ou pas dans un envi ronnement donné ? De nombreux travaux en robotique s'appuient pour répondre sur les affordances de la psychologie écologique. Apprendre quelles sont les actions permises nécessite selon nous d'apprendre les relations de dépendances locales et globales entre capteurs et effecteurs au cours de l'action.<br />Pour cela nous assimilons le robot à un réseau sensorimoteur aléatoire, et pour représenter son activité nous introduisons des mesures de dépendance probabilist es et statistiques. Celles-ci nous permettent de construire des matrices, graphes et complexes simpliciaux aléatoires dont nous étudions les propriétés spectrales, topologiques et homologiques.<br />Puis nous vérifions expérimentalement l'intérêt des outils proposés à l'aide d'un robot mobile simulé, autour de la capacité de pousser les objets de l'environnement, dans le cadre de tâches de classification supervisée et non supervisée.

Dans cette thèse, nous présentons tout d'abord une contribution visant à pallier ce problème de robustesse pour la reconnaissance d'instances, puis une extension directe de cette contribution à la reconnaissance et la localisation de classes d'objets. Dans un premier temps, nous avons développé une méthode inspiré de l'appariement de graphe (i.e. graph matching) afin de traiter le problème de la reconnaissance rapide d'instances d'objets spécifiques dans des conditions bruitées. Cette méthode permet de rajouter facilement un nombre quelconque d’autres types de caractéristiques locales (e.g. contours, textures…) moins affectées par le bruit tout en contournant le problème de la normalisation et sans pénaliser la vitesse de détection. Nos expériences sur plusieurs bases de test ont montré la pertinence de notre approche. Notre approche est globalement légèrement moins robuste à l'occultation que les approches existantes, mais elle produit des performances supérieures aux approches standard en conditions bruitées. Dans un second temps, nous avons développé une approche pour la détection de classes d'objets dans le même esprit que celui du sac de mots visuels. Pour cela, nous utilisons nos cascades de micro-classifieurs pour reconnaître des mots visuels plus distinctifs que les mots basés simplement sur des points d'intérêts. L'apprentissage se divise en deux parties: dans un premier temps, nous générons des cascades de micro-classifieurs servant à reconnaître des parties locales des images modèles ; puis dans un second temps, nous utilisons un classifieur afin de modéliser la frontière de décision entre les images de classe et celles de non-classe. Nous montrons que l'association de mots classiques (à partir de points d'intérêts) et de nos mots plus distincts produit une amélioration significative des performances pour un temps de calcul assez faible. / In this thesis, we first present a contribution to overcome this problem of robustness for the recognition of object instances, then we straightly extend this contribution to the detection and localization of classes of objects. In a first step, we have developed a method inspired by graph matching to address the problem of fast recognition of instances of specific objects in noisy conditions. This method allows to easily combine any types of local features (eg contours, textures ...) less affected by noise than keypoints, while bypassing the normalization problem and without penalizing too much the detection speed. Unlike other methods based on a global rigid transformation, our approach is robust to complex deformations such as those due to perspective or those non-rigid inherent to the model itself (e.g. a face, a flexible magazine). Our experiments on several datasets have showed the relevance of our approach. It is overall slightly less robust to occlusion than existing approaches, but it produces better performances in noisy conditions. In a second step, we have developed an approach for detecting classes of objects in the same spirit as the bag-of-visual-words model. For this we use our cascaded micro-classifiers to recognize visual words more distinctive than the classical words simply based on visual dictionaries. Training is divided into two parts: First, we generate cascades of micro-classifiers for recognizing local parts of the model pictures and then in a second step, we use a classifier to model the decision boundary between images of class and those of non-class. We show that the association of classical visual words (from keypoints patches) and our disctinctive words results in a significant improvement. The computation time is generally quite low, given the structure of the cascades that minimizes the detection time and the form of the classifier is extremely fast to evaluate.

Dans cette thèse, nous nous intéressons au problème du suivi en convoi, désigné en anglais par le terme platooning, où un train de robots essaie de suivre un chemin décrit par le leader. Ce chemin, n'étant pas prédéfini mais généré au cours du suivi, est inconnu de tous les robots suiveurs. Dans ce travail, nous choisissons une approche décentralisée locale où chaque robot du convoi observe son voisinage et calcule son contrôle de façon à avoir un suivi stable (absence d'oscillations) et précis (erreur latérale aussi faible que possible). Cette thèse étudie plus précisément le comportement latéral d'un robot du convoi et propose deux contrôleurs s'appuyant sur la mémorisation du chemin suivi par son prédécesseur. Un premier algorithme de contrôle Memo-LAT (Memorization and Look-Ahead Target) calcule une commande latérale continue en utilisant une loi de contrôle analytique. La stabilité de Memo-LAT n'étant pas toujours garantie, nous proposons l'algorithme de contrôle NOC (Non-Oscillatory Convergence) qui prend en compte la courbure du chemin à suivre dans le calcul du comportement latéral. NOC combine une approche géométrique avec une recherche heuristique pour calculer une commande discrète permettant au robot de suivre avec précision le chemin de son prédécesseur sans oscillation. / This thesis deals with the platooning problem which aims to concieve a control algorithm allowing a convoy of vehicles to follow their leader's path. This path, which is initially undefined and unknown to all the following robots, is generated as the leader moves. In this thesis, we choose a local decentralized approach in which each robot of the platoon uses its local perceptions to compute its own commands aiming to achieve a stable (no oscillations) and precise (with a lateral error as small as possible) platooning. More precisely, this thesis studies the lateral behavior of a platoon's robot and introduces two controllers based on the memorization of the robot's predecessor's path. The first algorithm, Memo-LAT (Memorization and Look-Ahead Target), computes a continuous lateral command using an analytic control law. As the stability of Memo-LAT is not always guaranteed, we present NOC (Non-Oscillatory Convergence), a control algorithm which takes into account the path's curvature in the robot's lateral behavior's computation. NOC combines a geometric approach to a heuristic search method to compute a discrete command allowing the robot to follow precisely and without oscillations its predecessor's path

Le travail présenté dans cette thèse se place dans le contexte de l'automatisation des mouvements de véhicules évoluant dans un environnement dynamique semi-structuré. Le sous-problème adressé est celui du contrôle réactif des mouvements de ces véhicules dans des environnements de type "parking aménagé" et "voie de circulation dédiée". La topologie des environnements considérés est alors connue a priori, mais divers obstacles statiques ou dynamiques peuvent à tout moment se trouver dans l'espace d'évolution du véhicule considéré. Il est donc nécessaire, d'une part, de planifier les mouvements de celui-ci sur la base d'un horizon temporel limité associé à une connaissance partielle du monde et, d'autre part, de mettre en place un mécanisme d'exécution réactif du plan nominal ainsi produit. C'est à ce niveau que se situe le travail présenté dans le mémoire. L'approche considérée pour aborder ce problème consiste à coupler un planificateur ciné-dynamique avec un contrôleur d'exécution réactif apte à amender en temps-réel le plan nominal produit régulièrement par le planificateur. Notre contrôleur est constitué d'un ensemble de comportements de base (suivi de trajectoires, évitement d'obstacles, etc.) activés en parallèle. Ces comportements sont ensuite combinés dans le but d'obtenir un comportement global correspondant à l'exécution des mouvements planifiés. La programmation de notre contrôleur repose sur la logique floue, au travers de l'utilisation d'un contrôleur flou de type Mamdani. L'intérêt essentiel de cette approche est de coder les comportements désirés sous la forme de règles pondérées, exprimées dans un langage proche du langage humain. Les résultats obtenus en simulation nous ont conduit naturellement à des expérimentations sur un véhicule réel dans le cadre du projet INRIA/INRETS Praxitèle qui constitue le cadre d'application de notre contrôleur d'exécution de mouvements.

Ce mémoire d'Habilitation à Diriger les Recherches présente les principales activités de recherche que j'ai menées depuis 2002 en tant que Maître de Conférences, tout d'abord à l'Université de Technologie de Belfort-Montbéliard, jusqu'en 2006, puis à l'Université Henri Poincaré dans l'équipe Maia au LORIA. Ce mémoire synthétise une partie de mes contributions au domaine de la résolution collective de problème, en informatique et en robotique. Il s'agit d'une approche inspirée du vivant, reposant sur les interactions d'un grand nombre d'agents simples entre eux et avec leur environnement, capable de faire émerger des structures ou des organisations constituant des solutions à des problèmes donnés. Cette approche est connue pour générer des solutions robustes et auto-adaptatives aux conditions variables et inconnues de l'environnement ou du système. La principale motivation de ces travaux est de modéliser ces comportements d'auto-organisation pour mieux les comprendre et les utiliser dans la définition de processus de résolution de problème ou de contrôle de flottilles de robots. Dans ce cadre, le mémoire présente les recherches menées selon deux approches possibles des interactions entre agents. Dans un premier temps, nous considérons des interactions directes entre agents ou robots, essentiellement par signaux/perceptions, et montrons comment la coordination réactive peut être efficace pour la résolution de problèmes spatiaux, ainsi que pour la navigation en formation. Dans un deuxième temps, nous examinons des modèles de coopération indirecte, c'est-à-dire fondés sur le marquage et la lecture d'informations dans l'environnement. Nous focalisons sur l'étude des processus d'auto-organisation engendrés par ce principe, puis examinons des approches pour leur implémentation réelle et robotique. Enfin, le mémoire présente mes perspectives de recherche en détaillant des pistes pour la définition d'une approche générique de résolution collective de problème fondée sur la construction de champs dynamiques dans l'environnement, et pour son déploiement en robotique dans des environnements réels et large échelle.

Des avancées importantes ont été réalisées dans le domaine de la robotique mobile. L'usage croissant des robots terrestres et des drones de petite taille, n'est possible que par l'apport de capacités d'autonomie de mouvement dans l'environnement d'évolution. La problématique de la localisation du système, par la mise en correspondance de mesures issues des capteurs embarqués avec des primitives contenues dans une carte, est primordiale. Ce processus, qui s'appuie sur la mise en oeuvre de techniques de fusion, a été très étudié. Dans cette thèse, nous proposons de définir des méthodes de planification du mouvement d'un mobile, avec pour objectif de garantir une performance de localisation à partir d'une carte incertaine donnée a priori, et ce lors de l'exécution. Une méthode de génération contrôlée de réalisations de cartes bruitées, exploitant la théorie des processus ponctuels, est d'abord présentée. Cette base de cartes permet de construire des cartes multi-niveaux pour la localisation. Le critère d'optimisation est défini à partir de fonctionnelles de la borne de Cramèr-Rao a posteriori, qui tient compte de l'incertitude sur la dynamique du mobile et de la cartographie incertaine. Nous proposons différentes approches, basées sur la méthode de cross-entropie, pour obtenir des stratégies de déplacement avec des modèles de dynamique discret et continu. La qualité des solutions optimales fournies par ces approches heuristiques est analysée en utilisant des résultats de la théorie des valeurs extrêmes. Enfin, nous esquissons une démarche pour l'amélioration ciblée de cartes sous contrainte de ressources afin d'améliorer la performance de localisation.

Le travail présenté dans cette thèse vise à améliorer la planification de chemins pour un robot similaire à une voiture. Ainsi, seul l'aspect géométrique du mouvement est considéré (les vitesses sont ignorées) et le robot est soumis à deux contraintes qui limitent ses déplacements : sa direction instantanée de déplacement reste parallèle à son axe principal, et son rayon de braquage est minoré. Les travaux antérieurs sur ce sujet n'ont donné lieu qu'à des solutions produisant des chemins (dits chemins de Dubins) formés d'arcs de cercles de rayon minimum reliés tangentiellement par des segments. Ces chemins sont localement optimaux, mais la discontinuité de leur courbure ne permet pas à un véhicule de les suivre correctement (le véhicule doit s'arrêter à chaque discontinuité pour réorienter ses roues directrices). C'est pourquoi on a développé une approche qui permet de produire des chemins ayant un profil de courbure continu et une dérivée bornée de la courbure (cette dernière contrainte correspond au fait que la vitesse de rotation du volant du véhicule est elle aussi bornée). La contribution majeure de cette thèse est donc de définir des chemins respectant ces contrain tes, tout en étant très proches des chemins de Dubins localement optimaux. Ce mémoire de thèse est constitué de trois parties. La première s'appuie sur une analyse de l'existant en matière de planification de chemins en robotique mobile, pour fixer précisément les caractéristiques du problème de planification abordé (en termes de commandabilité du robot et de nature des chemins optimaux) et pour justifier l'approche choisie. La seconde partie du mémoire de thèse présente une première approche de planification de chemins à courbure continue, dans laquelle seule la contrainte de continuité de la courbure est ajoutée au problème classique de planification de chemins sans manoeuvre. La dernière partie du mémoire de thèse reprend dans son intégralité le problème énoncé dans la première partie, et propose une solution sous-optimale. Dans les parties deux et trois, un planificateur local (non complet) est d'abord défini, puis un planificateur global (complet) est construit à partir de ce planificateur local. Les résultats obtenus sont illustrés par des expérimentations en simulation et sur véhicule.

L'un des challenges des roboticiens consiste à gérer un grand nombre de variabilités. Ces dernières concernent les concepts liés au matériel et aux logiciels du domaine de la robotique. Par conséquent, le développement des applications de robotique est une tâche complexe. Non seulement, elle requiert la maîtrise des détails de bas niveau du matériel et du logiciel mais aussi le changement du matériel utilisé dans une application entraînerait la réécriture du code de celle-ci. L'utilisation de l'ingénierie dirigée par les modèles dans ce contexte est une voie prometteuse pour (1) gérer les problèmes de dépendance de bas niveau des applications des détails de bas niveau à travers des modèles stables et (2) faciliter le développement des applications à travers une génération automatique de code vers des plateformes cibles. Les langages de modélisation spécifiques aux domaines mettent en oeuvre les techniques de l'ingénierie dirigée par les modèles afin de représenter les concepts du domaine et permettre aux experts de celui-ci de manipuler des concepts qu'ils ont l'habitude d'utiliser. Cependant, ces concepts ne sont pas suffisants pour représenter tous les aspects d'une application car ils très généraux. Il faudrait alors s'appuyer sur une démarche pour extraire des abstractions à partir de cas d'utilisations concrets et ainsi définir des abstractions ayant une sémantique opérationnelle. Le travail de cette thèse s'articule autour de deux axes principaux. Le premier axe concerne la contribution à la conception d'un langage de modélisation spécifique au domaine de la robotique mobile (RobotML). Nous extrayons à partir d'une ontologie du domaine les concepts que les roboticiens ont l'habitude d'utiliser pour la définition de leurs applications. Ces concepts sont ensuite représentés à travers une interface graphique permettant la représentation de modèles afin d'assurer une facilité d'utilisation pour les utilisateurs de RobotML. On offre ainsi la possibilité aux roboticiens de représenter leurs scénarios dans des modèles stables et indépendants des plateformes cibles à travers des concepts qu'ils ont l'habitude de manipuler. Une génération de code automatique à partir de ces modèles est ensuite possible vers une ou plusieurs plateformes cibles. Cette contribution est validée par la mise en oeuvre d'un scénario aérien dans un environnement inconnu proposé par l'ONERA. Le deuxième axe de cette thèse tente de définir une approche pour rendre les algorithmes résistants aux changements des détails de ba niveau. Notre approche prend en entrée la description d'une tâche de robotique et qui produit : un ensemble d'abstractions non algorithmiques représentant des requêtes sur l'environnment y compris le robot ou des actions de haut niveau , un ensemble d'abstractions algorithmiques encapsulant un ensemble d'instructions permettant de réaliser une sous-tâche de la tâche étudiée , algorithme générique configurable défini en fonction de ces abstractions. Ainsi, l'impact du changement du matériel et des stratégies définies dans les sous-tâches n'est pas très important. Il suffit d'adapter l'implantation de ces abstractions sans avoir à modifier l'algorithme générique. Cette approche est validée sur six variantes d'une famille d'algorithmes de navigation appelée Bug.

Nous nous sommes intéressés dans cette thèse au problème d'ordonnancement temps réel dur multiprocesseur tolérant aux fautes pour des tâches non préemptives périodiques strictes pouvant être combinées avec des tâches préemptives. Nous avons proposé des solutions à ce problème et les avons implantées dans le logiciel SynDEx puis nous les avons testées sur une application de suivi de véhicules électriques CyCabs. Nous avons d'abord présenté un état de l'art sur les systèmes temps réel embarqués et plus précisément sur l'ordonnancement classique monoprocesseur et multiprocesseur de tâches préemptives périodiques. Comme nous nous intéressons aux applications de contrôle/commande temps réel critiques, les traitements de capteurs/actionneurs et les traitements de commande de procédés ne doivent pas avoir de gigue. Pour ces raisons nous avons aussi présenté un état de l'art sur l'ordonnancement des tâches non-préemptives périodiques strictes. Par ailleurs nous avons présenté un état de l'art sur la tolérance aux fautes. Comme nous nous sommes intéressés aux fautes matérielles, nous avons présenté les deux types de redondances : logicielle et matérielle. Les analyses d'ordonnançabilité existantes de tâches non préemptives périodiques strictes dans le cas monoprocesseur ayant de faibles taux de succès d'ordonnancement, nous avons proposé une nouvelle analyse d'ordonnançabilité. Nous avons présenté une stratégie d'ordonnancement qui consiste à ordonnancer une tâche candidate avec un ensemble de tâches déjà ordonnancée. Nous avons utilisé cette stratégie pour ordonnancer des tâches harmoniques et non harmoniques, et nous avons proposé des nouvelles conditions d'ordonnançabilité. Afin d'améliorer le taux de succès d'ordonnancement de tâches non préemptives périodiques strictes, nous avons proposé de garder certaines tâches non préemptives périodiques strictes et d'y ajouter des tâches préemptives périodiques non strictes ne traitant ni les entrées/sorties ni le contrôle/commande. Nous avons ensuite étudié le problème d'ordonnancement multiprocesseur selon une approche partitionnée. Ce problème est résolu en utilisant trois algorithmes. Le premier algorithme effectue une analyse d'ordonnançabilité monoprocesseur et assigne chaque tâche sur éventuellement plusieurs processeurs. Le deuxième algorithme transforme le graphe de tâches dépendantes en un graphe déroulé où chaque tâche est répétée un nombre de fois égal au rapport entre le PPCM des autres périodes et sa période. Le troisième algorithme exploite les résultats des deux algorithmes précédents pour choisir sur quel processeur ordonnancer une tâche et calculer sa date de début d'exécution. Nous avons ensuite proposé d'étendre l'étude d'ordonnançabilité temps réel multiprocesseur précédente pour qu'elle soit tolérante aux fautes de processeurs et de bus de communication. Nous avons proposé un algorithme qui permet de transformer le graphe de tâches dépendantes en y ajoutant des tâches et des dépendances de données répliques et des tâches de sélection permettant de choisir la réplique de tâches allouée à un processeur non fautif. Nous avons étudié séparément les problèmes de tolérance aux fautes pour des processeurs, des bus de communication, et enfin des processeur et des bus de communication. Finalement nous avons étendu les trois algorithmes vus précédemment d'analyse d'ordonnançabilité, de déroulement et d'ordonnancement afin qu'ils soient tolérants aux fautes. Nous avons ensuite présenté les améliorations apportées au logiciel SynDEx tant sur le plan de l'analyse d'ordonnançabilité et l'algorithme d'ordonnancement, que sur le plan de la tolérance aux fautes. Finalement nous avons présenté les travaux expérimentaux concernant l'application de suivi de CyCabs. Nous avons modifié l'architecture des CyCabs en y intégrant des microcontrôleurs dsPICs et nous avons testé la tolérance aux fautes de dsPICs et du bus CAN sur une application de suivi de CyCab.

L'objectif dans ce travail est d'étudier la locomotion humaine. Notre approche met en évidence le rapport qui existe entre la forme géométrique des trajectoires locomotrices et le modèle cinématique simplifié d'un robot mobile à roues. Ce type de système a déjà été longtemps étudié dans le domaine de la robotique. D'un point de vue purement cinématique, la particularité d'un robot à roues est la contrainte non holonome qui impose au robot de se déplacer toujours selon la tangente à son axe principal. Dans le cas de la marche humaine, les observations nous montrent que les humains marchent vers l'avant et la direction instantanée du corps est tangente à la trajectoire qu'ils réalisent (dû à certains restrictions mécanique, anatomique... du corps au moment de la marche). Ce couplage entre la direction et la position du corps impose une contrainte non holonome parce qu'elle ne restreint pas la dimension de l'espace accessible à partir d'une configuration quelconque. Du point de vue du conducteur, une voiture possède deux commandes : l'accélérateur et le volant. La première question abordée ici peut être formulée de la manière suivante : où se trouve le ''volant'' du corps humain ? Plusieurs repères ont été associés aux différents parties du squelette (tête, tronc et bassin). Dans notre étude expérimentale nous montrons qu'il existe un repère qui prend en compte la nature non holonome de la locomotion humaine et que c'est le tronc qui joue le rôle du "volant". Nous avons validé notre modèle avec une base de données de 1560 trajectoires enregistrées à partir des trajectoires faites par 7 sujets. La deuxième question abordée dans ce travail est la suivante : parmi toutes les trajectoires possibles qui existent pour atteindre une position avec une orientation données, pourquoi l'humain effectue une trajectoire au lieu d'une autre ? Afin de donner une possible réponse à cette question, nous avons fait appel à la commande optimale : les trajectoires ont été choisies sel on un critère à optimiser. Dans cette perspective, le sujet est vu comme un système de commande, donc, la question devient : quel est le critère à optimiser ? est-ce la longueur de la trajectoire ? ou le temps parcouru ? ou la secousse minimale ?... Dans cet étude nous montrons que les trajectoires locomotrices peuvent être approximées par les géodésiques d'un système différentiel minimisant la norme de la commande. Ces géodésiques sont composés de morceaux de clothoides. Une clothoide, ou spirale de Cornu, est une courbe dont la courbure varie linéairement en fonction de l'abscisse curviligne. Nous montrons que le 90% des trajectoires faites par les 7 sujets ont été approximées avec une erreur moyenne de moins de 10cm. Dans la dernière partie de ce travail nous réalisons la synthèse numérique de trajectoires optimales dans l'espace atteignable. Il s'agit de partitionner l'espace des configurations par rapport aux différents types de trajectoires optimales qui peuvent relier l'origine à un point dans cet espace. Deux points appartiennent à une même cellule si les trajectoires parcourues sont de même type. Dans la plupart des cas le passage entre deux cellules adjacentes se fait par une déformation continue des trajectoires. Il est remarquable de noter que les rares cas de discontinuités du modèle proposé correspondent précisément aux changements de stratégies observées chez les sujets.