I consider the problem of planning collision-free trajectories for a robot in timevarying environments (among stationary or moving obstacles). I then propose a framework and show how it leads to fast and efficient algorithms for trajectory planning. The key idea behind this framework is a space-time representation that leads to a natural decomposition of the spatial and temporal aspects of the problem. The basic approach is to partition the whole problem into two sub-problems:​ (i) planning a path to avoid collisions with stationary obstacles. and (ii) planning the velocity along this path to avoid collisions with the moving obstacles. The first sub-problem is called the Path Planning Problem, and the second sub-problem is called the Velocity Planning Problem. I call this the Path-Velocity decomposition.

Within this decomposition paradigm. standard algorithms may be used to solve the path planning problem. Fast and efficient algorithms are then presented to solve the velocity planning problem. The crux of the algorithms lies in an explicit representation of time as an additional dimension. Moving obstacles give rise to time-varying constraints on the path of the robot. These constraints are represented as forbidden regions in the 2-dimensional path-time space. Computational geometric techniques are then used to determine a collision-free velocity profile. Furthermore. in conjunction with these computational geometric techniques. curve approximation splines are used to incorporate smoothness constraints in trajectories. while ensuring that they remain collision-free.

The use of these algorithms is illustrated for (i) a polygonal robot moving among polygonal obstacles. and (ii) motion coordination of multiple polygonal robots. The use of these geometric trajectory planning algorithms with low-level local avoidance strategies in a hierarchical robot control system is explored.

Cette thèse considère le problème de la planification de trajectoire avec évitement d'obstacles pour un robot dans un environment dynamique (les obstacles sont mobiles). Une méthode conduisant à des algorithmes efficaces, est proposée pour ce problème. L'idée de base consiste à introduire une décomposition du problème spatio-temporel en ses deux composantes naturelles. La démarche est donc la suivante:​ (i) planification d'un "chemin" sans collision parmi des obstacle stationnaires, et (ii) planification de la vitesse le long de long de cet chemin de façon à éviter les obstacles mobiles. Le premier sous-problème est appelé "Path Planning Problem" (PPP), et le second sous-problème est appelé "Velocity Plannning Problem" (VPP). On peut qualifier cette décomposition de décomposition "Chemin-Vitesse" (Path-Velocity).

Dans le cadre de ce travail, des algorithmes classiques conduisent à la solution de PPP. Des algorithmes spécifiques sont explicités pour résoudre VPP. La clé de voute de la méthode consiste en une représentation explicite de la dimension temps, considerée comme une dimension additionelle. Les obstacles mobiles introduisent des contraintes fonctions du temps, sur le chemin du robot. Ces contraintes correspondent à des régions interdites dans l'espace à deux dimensions abcisse-temps (path-time). Des techniques empruntées à la géométrie algorithmique sont alors utilisées pour déterminer le profil de vitesse. De plus, des méthodes basées sur les splines (Bézier), associées à la géométrie algorithmique, permettent d'introduire des contraintes de continuité, tout en garantissant l'évitement de collision.

L'utilisation de ces algorithmes est illustrée par des simulations à l'aide de deux exemples:​ (i) Un robot polygonal se déplaçant parmi des obstacles polygonaux, et (ii) la coordination de plusieurs robots. L'utilisation de ces algorithmes de planification en conjonction avec des stratégies locales d'évitement d'obstacles est aussi discutée.