Le chapitre 1 est pour l'essentiel une brève introduction générale qui donne le contexte générale de la planification et présente l'organisation du document dans son ensemble et quelques uns des points clés retenus : robot humanoïde, environnement non statique, perception par vision artificielle, et représentation de cet environnement par grilles d'occupation. Dans le chapitre 2, après une revue de littérature bien menée, l'auteur propose de considérer les points de repère de l'environnement dès la phase de planification de chemin afin de rendre plus robuste l'exécution des déplacements en cas d'évolution de l'environnement entre le moment où la planification est menée et celui où le robot se déplace ( évolution étant entendu comme liée à une amélioration de la connaissance par mise à jour, ou due à un changement de l'environnement lui-même). Le concept est décrit et une formalisation proposée. Le chapitre 3 s'intéresse en détail à la planification dans le cas d'environnements dynamiques. Les méthodes existantes, nombreuses, sont tout d'abord analysées et bien présentées. Le choix est fait ici de décrire l'environnement comme étant décomposé en cellules, regroupant elles-mêmes des voxels, éléments atomiques de la représentation. L'environnement étant changeant, l'auteur propose de réévaluer le plan préétabli à partir d'une bonne détection de la zone qui a pu se trouver modifiée dans l'environnement. L'approche est validée expérimentalement en utilisant une des plateformes robotiques du LAAS qui dispose de bonnes capacités de localisation : le manipulateur mobile Jido étant à ce jour plus performant sur ce plan que l'humanoïde HRP2, c'est lui qui a été utilisé. Ces expérimentations donnent des indications concordantes sur l'efficacité de l'approche retenue. Notons également que la planification s'appuie sur une boite englobante de l'humanoïde, et non pas sur une représentation plus riche (multi-degré-deliberté). En revanche, c'est bien de planification pour l'humanoïde considéré dans toute sa complexité qu'il s'agit au chapitre 4 : on s'intéresse ici à tous les degrés de liberté du robot. L'auteur propose des évolutions de méthodes existantes et en particulier sur la manière de tirer profit de la redondance cinématique. L'approche est bien décrite et permet d'inclure une phase d'optimisation de la posture globale du robot. Des exemples illustrent le propos et sont l'occasion de comparaison avec d'autres méthodes. Le chapitre 5 s'intéresse à la manière de modéliser l'environnement, sachant qu'on s'intéresse ici au cas d'une perception par vision artificielle, et précisément au cas de l'humanoïde, robot d'assurer lui-même cette perception au fur et à mesure de son avancée dans l'environnement. On est donc dans le cadre de la recherche de la meilleure vue suivante qui doit permettre d'enrichir au mieux la connaissance qu'a le robot de son environnement. L'approche retenue fait à nouveau appel à la boite englobante de l'humanoïde et non à sa représentation complète ; il sera intéressant de voir dans le futur ce que pourrait apporter la prise en compte des degrés de liberté de la tête ou du torse à la résolution de ce problème. Le chapitre 6 décrit la phase d'intégration de tous ces travaux sur la plateforme HRP2 du LAAS-CNRS, partie importante de tout travail de roboticien. / This thesis starts by proposing a new framework for motion planning using stochastic maps, such as occupancy-grid maps. In autonomous robotics applications, the robot's map of the environment is typically constructed online, using techniques from SLAM. These methods can construct a dense map of the environment, or a sparse map that contains a set of identifiable landmarks. In this situation, path planning would be performed using the dense map, and the path would be executed in a sensor-based fashion, using feedback control to track the reference path based on sensor information regarding landmark position. Maximum-likelihood estimation techniques are used to model the sensing process as well as to estimate the most likely nominal path that will be followed by the robot during execution of the plan. The proposed approach is potentially a practical way to plan under the specific sorts of uncertainty confronted by a humanoid robot. The next chapter, presents methods for constructing free paths in dynamic environments. The chapter begins with a comprehensive review of past methods, ranging from modifying sampling-based methods for the dynamic obstacle problem, to methods that were specifically designed for this problem. The thesis proposes to adapt a method reported originally by Leven et al.. so that it can be used to plan paths for humanoid robots in dynamic environments. The basic idea of this method is to construct a mapping from voxels in a discretized representation of the workspace to vertices and arcs in a configuration space network built using sampling-based planning methods. When an obstacle intersects a voxel in the workspace, the corresponding nodes and arcs in the configuration space roadmap are marked as invalid. The part of the network that remains comprises the set of valid candidate paths. The specific approach described here extends previous work by imposing a two-level hierarchical structure on the representation of the workspace. The methods described in Chapters 2 and 3 essentially deal with low-dimensional problems (e.g., moving a bounding box). The reduction in dimensionality is essential, since the path planning problem confronted in these chapters is complicated by uncertainty and dynamic obstacles, respectively. Chapter 4 addresses the problem of planning the full motion of a humanoid robot (whole-body task planning). The approach presented here is essentially a four-step approach. First, multiple viable goal configurations are generated using a local task solver, and these are used in a classical path planning approach with one initial condition and multiple goals. This classical problem is solved using an RRT-based method. Once a path is found, optimization methods are applied to the goal posture. Finally, classic path optimization algorithms are applied to the solution path and posture optimization. The fifth chapter describes algorithms for building a representation of the environment using stereo vision as the sensing modality. Such algorithms are necessary components of the autonomous system proposed in the first chapter of the thesis. A simple occupancy-grid based method is proposed, in which each voxel in the grid is assigned a number indicating the probability that it is occupied. The representation is updated during execution based on values received from the sensing system. The sensor model used is a simple Gaussian observation model in which measured distance is assumed to be true distance plus additive Gaussian noise. Sequential Bayes updating is then used to incrementally update occupancy values as new measurements are received. Finally, chapter 6 provides some details about the overall system architecture, and in particular, about those components of the architecture that have been taken from existing software (and therefore, do not themselves represent contributions of the thesis). Several software systems are described, including GIK, WorldModelGrid3D, HppDynamicObstacle, and GenoM.

Ce travail de thèse s'inscrit dans le développement d'un véhicule autonome en milieu autoroutier. Plus précisément, il s'agit de proposer une architecture unifiée de génération de trajectoires avec une prise de décision prenant en compte les limitations de l'environnement et des informations disponibles actuellement sur un véhicule automatisé.La méthode propose d'une part de générer des trajectoires sous forme de sigmoı̈de dans une représentation spatiotemporelle continue de l'espace de navigation, préalablement réduit par la modélisation d'intervalles sans collision en conditionnominale de conduite. Les paramètres de la sigmoı̈de sont ensuite optimisés par une stratégie de recuit simulé utilisant l'algorithme de prise de décision comme fonction d'évaluation de la trajectoire générée. De cette manière, les problèmes de discrétisation et de découplage position/vitesse sont évités. D'autre part, l'agrégation des théories de logique floue etdes croyances permet une prise de décision sur des critères hétérogènes et des données incertaines. Le formalisme présenté offre la possibilité d'adapter le comportement du véhicule aux passagers, notamment selon leur perception du risque et leur souhait d'une conduite souple ou sportive.L'approche développée a finalement été évaluée et validée en environnement de simulation puis sur un véhicule de test. La brique de planification a alors été intégrée à l'architecture existante du véhicule, en aval des briques de localisation et de perception des obstacles et en amont de la brique de contrôle. / This thesis work is part of the development of a self-driving car in highway environments. More precisely, it aims to propose a unified architecture of trajectory planner and decision-maker taking into account the limitations of the environment and the available data within the current development of sensors technologies (distance limitations, uncertainties).On the one hand, the method generates sigmoid trajectories in a continuous spatiotemporal representation of the evolution space, which is reduced beforehand by modeling collision-free intervals in nominal conditions of driving. The sigmoid parameters are subsequently optimized with a simulated annealing approach that uses the decision-maker algorithm as the evaluation function for the generated trajectory. It thus makes it possible to elude both the discretization and position/speed decoupling problems. On the other hand, the aggregation of fuzzy logic and belief theory allows decision making on heterogeneous criteria and uncertain data. The proposed framework also handles personalization of the vehicle's behavior, depending on the passengers' risk perception and an aggressive or conservative driving style.The presented approach was finally evaluated and validated in a simulation environment, and then in a test vehicle. The planning block was integrated into the existing vehicle's architecture, interfaced with the localization, obstacles' perception and control blocks.

abstract: Robot motion planning requires computing a sequence of waypoints from an initial configuration of the robot to the goal configuration. Solving a motion planning problem optimally is proven to be NP-Complete. Sampling-based motion planners efficiently compute an approximation of the optimal solution. They sample the configuration space uniformly and hence fail to sample regions of the environment that have narrow passages or pinch points. These critical regions are analogous to landmarks from planning literature as the robot is required to pass through them to reach the goal. This work proposes a deep learning approach that identifies critical regions in the environment and learns a sampling distribution to effectively sample them in high dimensional configuration spaces. A classification-based approach is used to learn the distributions. The robot degrees of freedom (DOF) limits are binned and a distribution is generated from sampling motion plan solutions. Conditional information like goal configuration and robot location encoded in the network inputs showcase the network learning to bias the identified critical regions towards the goal configuration. Empirical evaluations are performed against the state of the art sampling-based motion planners on a variety of tasks requiring the robot to pass through critical regions. An empirical analysis of robotic systems with three to eight degrees of freedom indicates that this approach effectively improves planning performance. / Dissertation/Thesis / Masters Thesis Computer Science 2020

Afin que les robots humanoïdes puissent travailler avec les humains et être en mesure de résoudre des tâches répétitives, nous devons leur permettre de planifier leurs mouvements de façon autonome. La planification de mouvement est un problème de longue date en robotique, et tandis que sa fondation algorithmique a été étudiée en profondeur, la planification de mouvement est encore un problème NP-difficile et qui manque de solutions efficaces. Nous souhaitons ouvrir une nouvelle perspective sur le problème en mettant en évidence sa structure: le comportement du robot, le système mécanique du robot et l’environnement du robot. Nous allons nous intéresser à l’hypothèse que chaque composante structurelle peut être exploitée pour créer des algorithmes de planification de mouvement plus efficaces. Nous présentons trois algorithmes exploitant la structure, basés sur des arguments géométriques et topologiques: d’abord, nous exploitons le comportement d’un robot de marche en étudiant la faisabilité des transitions des traces de pas. L’algorithme qui en résulte est capable de planifier des traces de pas tout en évitant jusqu’à 60 objets situés sur une surface plane 6 mètres carrés. Deuxièmement, nous exploitons le système mécanique d’un robot humanoïde en étudiant les structures des liaisons linéaires de ses bras et de ses jambes. Nous introduisons le concept d’une trajectoire irréductible, qui est une technique de réduction de dimension préservant la complétude. L’algorithme résultant est capable de trouver des mouvements dans des environnements étroits, où les méthodes d’échantillonnage ne pouvaient pas être appliquées. Troisièmement, nous exploitons l’environnement en raisonnant sur la structure topologique des transitions de contact. Nous montrons que l’analyse de l’environnement est une méthode efficace pour pré-calculer les informations pertinentes pour une planification de mouvement efficace. En s’appuyant sur ces résultats, nous arrivons à la conclusion que l’exploitation de la structure est une composante essentielle de la planification de mouvement efficace. Il en résulte que tout robot humanoïde, qui veut agir efficacement dans le monde réel, doit être capable de comprendre et d’exploiter la structure. / If humanoid robots should work along with humans and should be able to solve repetitive tasks, we need to enable them with a skill to autonomously plan motions. Motion planning is a longstanding core problem in robotics, and while its algorithmic foundation has been studied in depth, motion planning is still an NP-hard problem lacking efficient solutions. We want to open up a new perspective on the problem by highlighting its structure: the behavior of the robot, the mechanical system of the robot, and the environment of the robot. We will investigate the hypothesis that each structural component can be exploited to create more efficient motion planning algorithms. We present three algorithms exploiting structure, based on geometrical and topological arguments: first, we exploit the behavior of a walking robot by studying the feasibility of footstep transitions. The resulting algorithm is able to plan footsteps avoiding up to 60 objects on a 6 square meters planar surface. Second, we exploit the mechanical system of a humanoid robot by studying the linear linkage structures of its arms and legs. We introduce the concept of an irreducible motion, which is a completeness-preserving dimensionality reduction technique. The resulting algorithm is able to find motions in narrow environments, where previous sampling-based methods could not be applied. Third, we exploit the environment by reasoning about the topological structure of contact transitions. We show that analyzing the environment is an efficient method to precompute relevant information for efficient motion planning. Based on those results, we come to the conclusion that exploiting structure is an essential component of efficient motion planning. It follows that any humanoid robot, who wants to act efficiently in the real world, needs to be able to understand and to exploit structure.

In this thesis we modified a sampling-based motion planning algorithm to improve sampling efficiency. First, we modify the RRT* motion planning algorithm with a local motion planner that guarantees collision-free state trajectories without explicitly checking for collision with obstacles. The control trajectories are generated by solving a sequence of quadratic programs with Control Barrier Functions (CBF) constraints. If the control trajectories satisfy the CBF constraints, the state trajectories are guaranteed to stay in the free subset of the state space. Second, we use a stochastic optimization algorithm to adapt the sampling density function of RRT* to increase the probability of sampling in promising regions in the configuration space. In our approach, we use the nonparametric generalized cross-entropy (GCE) method is used for importance sampling, where a subset of the sampled RRT* trajectories is incrementally exploited to adapt the density function. The modified algorithms, the Adaptive CBF-RRT* and the CBF-RRT*, are demonstrated with numerical examples using the unicycle dynamics. The Adaptive CBF-RRT* has been shown to yield paths with lower cost with fewer tree vertexes than the CBF-RRT*. / 2022-03-27T00:00:00Z

This dissertation addresses the problem of motion planning and control for nonholonomic mobile robots, particularly wheeled and tracked mobile robots, working in extreme environments, for example, desert, forest, and mine. In such environments, the mobile robots are highly subject to external disturbances (e.g., slippery terrain, dusty air, etc.), which essentially introduce uncertainties to the robot systems. The complexity of the motion planning problem is due to taking both nonholonomic and uncertainty constraints into account simultaneously. As a result, none of the conventional nonholonomic motion planning can be directly applied. The control problem is even more challenging since state constraints posed by obstacles in the environments must also be considered along with the nonholonomic and uncertainty constraints. In this research, we systematically develop a new type of motion planning technique that determines an optimal path for a mobile robot in a given environment. This motion planning technique is based on the idea of a maximum allowable uncertainty, which is a number assigned to each free configuration in the environment. The optimal path is a path connecting given initial and goal configurations through a series of configurations respecting the nonholonomic constraint and possessing the highest maximum allowable uncertainty. Both linear and quadratic approximations of the maximum allowable uncertainty, including their corresponding motion planners, have been studied. Additionally, we develop the first real-time robust control algorithm for the mobile robot under uncertainty to follow given paths safely and accurately in cluttered environments. The control algorithm also utilizes the concept of the maximum allowable uncertainty as well as the robust control theory. The simulation results have shown the effectiveness and robustness of the control algorithm in steering the mobile robot along a given path amidst obstacles without collisions even when the level of robot uncertainty is high. / Ph. D.

Recently, formal methods have gained significant traction for describing, checking, and synthesizing the behaviors of cyber-physical systems. Among these methods, temporal logics stand out as they offer concise mathematical formulas to express desired system properties. In this thesis, our focus revolves around two primary applications of temporal logics in describing the behavior of autonomous system. The first involves integrating temporal logics with machine learning techniques to deduce a temporal logic specification based on the system's execution traces. The second application concerns using temporal logics to define traffic rules and develop a control scheme that guarantees compliance with these rules for autonomous vehicles. Ultimately, our objective is to combine these approaches, infer a specification that characterizes the desired behaviors of autonomous vehicles, and ensure that these behaviors are upheld during runtime. In the first study of this thesis, our focus is on learning Signal Temporal Logic (STL) specifications from system execution traces. Our approach involves two main phases. Initially, we address an offline supervised learning problem, leveraging the availability of system traces and their corresponding labels. Subsequently, we introduce a time-incremental learning framework. This framework is designed for a dataset containing labeled signal traces with a common time horizon. It provides a method to predict the label of a signal as it is received incrementally over time. To tackle both problems, we propose two decision tree-based approaches, with the aim of enhancing the interpretability and classification performance of existing methods. The simulation results demonstrate the efficiency of our proposed approaches. In the next study, we address the challenge of guaranteeing compliance with traffic rules expressed as STL specifications within the domain of autonomous driving. Our focus is on developing control frameworks for a fully autonomous vehicle operating in a deterministic or stochastic environment. Our frameworks effectively translate the traffic rules into high-level decisions and accomplish low-level vehicle control with good real-time performance. Compared to existing literature, our approaches demonstrate significant enhancements in terms of runtime performance. / 2025-01-17T00:00:00Z

No description available.

No description available.

No description available.