Abstract :
[en] Trajectory planning is one of the fundamental problems in mobile robotics. A wide variety of approaches have been proposed over the years to deal with the various issues of this problem. This thesis presents an original and complete solution to tackle the motion planning problem for nonholonomic mobile robots in two-dimensional space. Given a set of obstacles, an initial and a goal configuration, the problem consists in computing efficiently a physically feasible trajectory that reaches the specified target as fast as possible. One of the original aspects of this work lies in the decomposition of the general problem into several simpler subproblems, for which very efficient solutions are developed. Their combination provides a complete trajectory planning approach that is one of the most computationally effective method suited for the motion of cylindrically shaped wheeled mobile robots in the presence of polygonal obstacles. This complete solution consists of three main steps. The first one is aimed at finding a short path that avoids obstacles and manages to reach the destination, without taking into account nonholonomic constraints of the robot. Our path planning method relies on an original refinement procedure of a constrained Delaunay triangulation of the obstacles, that outperforms other existing planning techniques. The second step consists in interpolating paths into smooth curves that can be followed by a real robot without slowing down excessively. By joining only two arcs of clothoids for moving from one curvature to another, our approach is simpler and also computationally cheaper than other interpolation methods. Finally, thanks to the introduction of an original discretization scheme, an efficient algorithm for computing a time-optimal speed profile for arbitrary paths is presented. The speed profile that results from this procedure not only allows the robot to follow the synthesized path as fast as possible while taking into account a broad class of velocity and accelerations constraints, but also provides the accurate advance information necessary to implementing coordinated actions during the displacement of the robot (e.g., between the locomotion system and other actuators).
[fr] La planification de trajectoires est un des problèmes fondamentaux de la robotique mobile. Ces dernières années, une grande variété de solutions ont donc été proposées afin de répondre au mieux aux différents aspects de ce problème.
Cette thèse s’inscrit dans cette démarche et présente une solution complète et originale pour résoudre le problème de planification de mouvements pour des robots mobiles non-holonomes se déplaçant dans un espace à deux dimensions. Étant donné un robot, un ensemble d’obstacles, et une configuration de départ et d’arrivée, le problème consiste à calculer une trajectoire qui est non seulement réalisable par ce robot, mais qui de plus lui permet d’atteindre sa destination le plus rapidement possible.
Une des originalités de la méthode présentée dans cette thèse réside dans la décomposition du problème en plusieurs sous-problèmes, pour lesquels, des solutions très efficaces sont développées. La combinaison de ces différentes solutions permet de répondre au problème posé et forme, à notre connaissance, une des méthodes les plus efficace dédiée à la planification de mouvements pour des robots cylindriques à roues se déplaçant parmi des
obstacles polygonaux.
Cette solution complète comporte trois grande étapes. La première consiste à trouver un chemin court qui évite les obstacles et qui permet d’atteindre la destination, sans tenir compte des contraintes de non-holonomie du robot. Notre méthode repose sur une procédure originale de raffinement d’une triangulation de Delaunay contrainte, qui surpasse la plupart des autres méthodes existantes.
La deuxième étape consiste en une interpolation des chemins en des courbes lisses pouvant être suivies plus rapidement par un robot car demandant de moins ralentir lors des changements d’orientation. En utilisant seulement des paires de clothoïdes pour passer d’une courbure à une autre, notre méthode est plus simple et plus rapide que d’autres méthodes d’interpolation.
Finalement, grâce à l’introduction d’une procédure de discrétisation originale, une méthode efficace de calcul d’un profil de vitesse optimal en temps est présentée. Celui-ci permet au robot de suivre le chemin calculé le plus rapidement possible tout en tenant compte d’une large gamme de contraintes de vitesse et d’accélération. Il fourni aussi les informations sur les configurations futures du robot qui sont nécessaires à l’élaboration d’actions coordonnées (e.g., entre le système de locomotion et d’autres actuateurs).
