Planification de mouvement

La planification de mouvement (en anglais motion planning) est un ensemble de techniques mathématiques et informatiques permettant de calculer des trajectoires pour un système cinématique, avec pour contrainte l'absence de collision. Il existe deux principales catégories de méthodes pour la planification de mouvement : La première est composée de méthodes dites déterministes, appelées ainsi car elles permettent de retrouver le même chemin à chaque exécution, sous réserve d'avoir des conditions initiales équivalentes. Les méthodes déterministes sont dites complètes en résolution car elles garantissent de trouver une solution, ou d'indiquer s'il n'y a pas de solution. Quelques algorithmes bien connus : champs de potentiel, décomposition cellulaire, diagrammes de Voronoï... La seconde catégorie est composée des méthodes probabilistes. Ces méthodes ne sont pas complètes en résolution, mais elles garantissent de trouver une solution s'il en existe une. On dit qu'elles sont complètes en probabilité. Ces méthodes ne trouveront pas forcément le même chemin à chaque exécution, même avec des conditions initiales similaires. Les méthodes probabilistes peuvent être subdivisées en deux sous catégories : les méthodes d'échantillonnage et les méthodes de diffusion. Les premières cherchent à approximer l'environnement de l'objet qui doit être déplacé, afin de construire une carte réutilisable (de la même manière qu'une carte routière). Les secondes effectuent une recherche aléatoire dans l'environnement, jusqu'à trouver la configuration finale désirée. Quelques algorithmes bien connus : algorithme du fil d'Ariane, probabilistic roadmap (PRM) pour les méthodes d'échantillonnage, rapidly-exploring random trees (RRT) pour les méthodes de diffusion. Un logiciel mettant en œuvre ces techniques est nommé un planificateur de mouvement (en anglais path planner).