Planification de trajectoires de robots mobiles non-holonomes et de robots à pattes

The work presented in this thesis deals with optimal motion planning, in the presence of obstacles, of car-like robots and legged robots. The model of car-like robot studied is the one of Dubins. That is, roughly speaking, a car moving forward with a minimum turning radius. We consider the problem of computing a convex hull of bounded curvature of a set S of points in the plane, that is a set containing S and whose boundary is a curve of bounded curvature of minimal length. We prove that, if the radius of the smallest disk that contains S is greater than 1, such a hull is unique. We show that the computation of a convex hull of bounded curvature reduces to convex programming or to solving a set of algebraic systems. We also present an exact polynomial-time algorithm for computing a shortest path for the Dubins robot moving amidst moderate obstacles, that is obstacles whose boundaries are curves of bounded curvature made of line segments and arcs of circle. Such obstacles can be found by computing convex hulls of bounded curvature of polygonal obstacles. The algorithm computes a graph and finds a shortest path in this graph. The graph is computed using computational geometry methods and resolution of algebraic systems. We also worked on the motion planning problem of a legged robot whose body is a single point and whose legs are attached to the body. The legs have a bounded length and the robot can only put its feet in some polygonal regions of the plane. We present an almost optimal time algorithm for computing the set of stable placements of the body of the robot. By a clever transformation, we turn the problem into the computation of the free space of a half-disk robot moving amidst obstacles.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