Planification de trajectoire pour un robot polygonal non holonome dans un environnement polygonal

摘要

Nous etudions les robots non holonomes de type voiture et leurs trajectoires optimales en longueur. Ces robots sont soumis a deux contraintes cinematiques : son orientation est toujours tangente a la trajectoire, qui a une courbure majoree par une constante strictement positive. Dans un premier temps, nous partons des resultats de dubins limitant les formes des trajectoires optimales pour un robot se deplacant en marche avant dans un environnement plan sans obstacle. Nous calculons la synthese de ce probleme d'optimisation. Nous obtenons alors une partition de l'espace des configurations du robot. Puis en decoule l'etude des iso-distances associees a la pseudo-distance entre configurations, ainsi que les regions d'accessibilite. Ensuite nous abordons deux problemes de planification utilisant des chemins optimaux. Le premier consiste a planifier un chemin optimal entre deux configurations passant par une suite donnee de points. Nous montrons que ce probleme est np-dur et qu'une restriction de ce probleme admet une unique solution. Nous proposons deux methodes de resolution. Le second est plus classique : le robot polygonal est en mouvement plan au milieu d'obstacles polygonaux. Nous proposons un algorithme utilisant nos resultats sur les chemins optimaux en presence d'obstacles, trouvant une approximation du plus court chemin. La complexite et la qualite de l'approximation sont analysees. L'algorithme a ete implante en langage c et des resultats sont presentes