Abstract FR:

Les travaux presentes dans cette these s'inscrivent dans le cadre de la planification de trajectoires optimales en presence d'obstacles pour des robots mobiles de type voiture et pour des robots a pattes. Le modele de robot de type voiture etudie est celui de dubins. Il s'agit grossierement d'une voiture se deplacant en marche avant uniquement et dont le rayon de braquage est minore. Nous presentons un algorithme exact polynomial pour le calcul de trajectoires optimales en longueur lorsque le robot se deplace en presence d'obstacles dont les bords sont de courbure bornee et constitues de segments de droite et d'arcs de cercle. L'algorithme calcule un graphe et recherche un plus court chemin dans ce graphe. Le calcul de ce graphe est effectue grace a des techniques de geometrie algorithmique et par la resolution de systemes algebriques dont nous montrons, a l'aide de resultants, qu'ils ont un nombre fini de solutions. Nous proposons egalement un algorithme polynomial pour le calcul d'enveloppes convexes de courbure bornee d'un ensemble de points du plan, c'est-a-dire d'un convexe contenant tous les points et dont le bord est de courbure bornee et de perimetre minimal. L'algorithme presente est base sur l'optimisation d'une fonction convexe sous contraintes. Nous avons egalement etudie le probleme de la planification de trajectoires pour des robots a pattes dont le corps est ponctuel et dont toutes les pattes sont attachees au meme point. Les pattes du robot ont une longueur bornee et ne sont autorisees a se poser que dans certaines regions polygonales du plan. Nous presentons un algorithme quasi-optimal pour le calcul de l'ensemble des positions du corps du robot en equilibre 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 deplacant en presence d'obstacles