Planification locale de trajectoire sous contraintes

Le problème de planification de trajectoire sous contraintes et optimisation

Un robot est limité par ses capacités de mouvement décrites selon son modèle cinématique. Un robot holonome peut ainsi effectuer des mouvements de translation qui sont impossibles pour un robot de type unicyle. La succession des actions est également soumise à des contraintes cinématiques et dynamiques liées à la nature même de l’entité commandée : un robot est un assemblage de composants mécaniques et électriques dont la capacité à changer d’état, la capacité à soutenir des efforts et dont l’énergie disponible sont limitées. Des contraintes s’imposent donc, limitant les transitions entre deux configurations. Ce problème est désigné sous le terme de «kinodynamic planning» [Donald et al., 1993].

Contraintes cinématiques

Une contrainte cinématique restreint les possibilités de passage d’une configuration à une autre configuration. Soit c(t) une contrainte cinématique. Les contraintes cinématiques imposent des contraintes dites non-intégrables. Typiquement, ce sont des équations différentielles reflétant le modèle cinématique du robot considéré pour lesquelles il n’existe en général pas de solutions explicites. Entre autres, les contraintes cinématiques sont la vitesse linéaire, l’accélération linéaire, la vitesse angulaire, l’accélération angulaire, les contraintes pour éviter le glissement des roues. . .

Contraintes dynamiques

Nous considérons dans ce manuscrit deux types de contraintes dynamiques. La première est la continuité entre deux trajectoires. Celle-ci peut concerner la continuité sur la position, la vitesse, l’accélération. . .
Le niveau de continuité dépend alors de la dérivabilité de la trajectoire employée par le planificateur. La seconde contrainte vérifiée est la commandabilité du robot : les solutions déterminées doivent être transformables en commandes effectivement réalisables par le robot.

Autres contraintes

Bien entendu, les contraintes ne sont pas uniquement centrées sur le modèle de fonctionnement du robot. D’autres contraintes existent selon le domaine d’application, par exemple, des contraintes liées aux interactions avec des humains [Mainprice et al., 2011].

Difficulté du problème de planification de trajectoire

Complexité :La complexité du problème de planification de trajectoire a été démontrée à l’époque où des solutions directes étaient recherchées. Ce problème est de la classe PSPACE-hard[Reif, 1987]. S’il faut n degrés de liberté pour décrire la mécanique du robot, l’espace des configurations est de dimension n. Comme l’a résumé [Frazzoli et al., 2002], si les obstacles sont définis avec m contraintes polynomiales de degré d, la complexité en temps de l’algorithme est deux fois exponentielle sur n, polynomiale sur m (la littérature parle de complexité géométrique) et polynomiale sur d (complexité algébrique).
Abandon de la complétude :Si des contraintes non intégrables sont ajoutées au problème, par exemple des limites sur la vitesse linéaire ou sur l’accélération linéaire, la complexité devient encore plus importante, en particulier pour des problèmes présentant beaucoup de degrés de liberté. C’est pourquoi la propriété de complétude, c’est-à-dire obtenir une solution si elle existe quelle que soit la situation, est totalement abandonnée dans les approches directes pour la planification de trajectoires sous contraintes cinématiques et dynamiques. Dans ces approches, l’idée est plutôt de trouver des bornes aux temps de calcul.

Le mélange de la planification symbolique avec la planification de trajectoires

Comportements en planification de mouvement

[Reynolds, 1999] propose une approche découplée pour la description des comportements de pilotage utilisés par des personnages autonomes afin qu’ils puissent achever des tâches de haut niveau. Un niveau de sélection d’action décide en premier lieu des objectifs de haut niveau. Ceux-ci sont ensuite transmis à un niveau de planification de mouvement (de locomotion) qui se charge d’effectuer le déplacement.
Les approches centrées sur les comportements proposent d’intégrer le domaine de la planification de comportements dans les applications robotiques [Jones, 2004]. Celles-ci sont pourtant limitées à des architectures réactives s’appuyant sur les capteurs et les contrôleurs des robots [Brooks, 1985]. Il n’y a aucune inférence à propos des capacités de mouvement du robot ou encore de l’accessibilité des objectifs sélectionnés.

Approches mêlant états discrets et continus

Approches cognitives pour bras articulé :Les problèmes de planification de mouvement n’impliquent pas nécessairement un déplacement libre du robot dans l’environnement et donc un espace des configurations potentiellement infini : c’est par exemple le cas des bras articulés et en général des problèmes de manipulation d’objets dont les enjeux sont révélés par [Lozano-Perez et al., 1987]. Des contraintes peuvent apparaître sur les mouvements relatifs entre les éléments du bras, sur la manière d’attraper les objets à manipuler, sur l’équilibre du bras . . . Notons qu’un bras articulé ne peut s’étendre à l’infini. Dans ce contexte, les degrés de liberté sont définis par les angles entre chaque partie du bras dont les valeurs possibles sont limitées. L’espace des configurations qui en résulte est donc fini et peut être complètement calculé à l’avance. Cette possibilité est particulièrement intéressante puisqu’elle rend possible la vérification en ligne des états du robot. Dans ce contexte particulier, de récentes avancées dans [Jaesik et Eyal, 2009] ont ainsi été réalisées en associant la planification « classique » (raisonnement dans un monde symbolique) et la planification de mouvement. La partie descriptive utilise PDDL [McDermott et al., 1998]. L’espace des configurations du bras est représenté dans le niveau de planification des actions, assurant au préalable la faisabilité physique des décisions prises.

Vers une approche cognitive pour la planification de trajectoire

DKP :L’approche que je propose pour la planification de trajectoire par échantillonnage, DKP, construit dans un environnement 2D un arbre d’exploration dans lequel les branches sont des échantillons quadratiques guidées par un critère d’optimisation. DKP est en particulier construit pour les robots à deux roues indépendantes des solutions à base de quadratiques, lesquelles suffisent pour obtenir des commandes respectant leur modèle.
Dans DKP, les robots sont définis selon leurs contraintes cinématiques, telles que des limites sur la vitesse linéaire ou angulaire. De plus, DKP gère l’évitement d’obstacles fixes ou mobiles.
L’originalité du processus de propagation provient de la représentation géométrique du problème. Ce processus définit localement un espace atteignable et continu, appelé espace des paramètres, qui modélise toutes les trajectoires qui peuvent satisfaire toutes les contraintes du problème. D’autres contraintes peuvent être définies pour un robot particulier tant qu’une restriction de l’espace des paramètres peut être exprimée. Dans un processus déterministe, DKP produit alors des échantillons localement optimaux ayant des durées variées et qui respectent les contraintes du problème. Ce processus de propagation permet d’obtenir une exploration expansive de l’espace de travail, évitant l’usage de processus aléatoires pour éviter les minima locaux.
DKP tire avantage de la simplicité de ses échantillons pour totalement séparer le processus de calcul de l’espace atteignable du processus de recherche de solution. Cette simplicité des morceaux de trajectoire, couplée à un processus d’exploration efficace, est largement suffisante pour produire des manœuvres complexes. Comme dans les approches par échantillonnage, des garanties sur la faisabilité des trajectoires sont fournies, tout en obtenant des solutions de bonne qualité. Le point important à mon sens est que les résultats sont reproductibles et que l’on peut établir dans DKP des bornes sur le temps de calcul du niveau de propagation. Le processus de sélection est une variation de l’algorithme A∗: DKP optimise un critère d’exploration. Enfin, l’espace des paramètres est une manière efficace de créer des contraintes spécifiques sur nos robots tout en identifiant clairement l’espace localement atteignable.

Table des matières

Chapitre 1 :Introduction générale
1.1 Problématiques
1.2 Espace des configurations
1.3 L’espace de travail
1.4 L’espace des configurations libres
1.5 Le problème de planification de chemin
1.6 Le problème de planification de trajectoire
1.7 Le problème de planification de trajectoire sous contraintes et optimisation
1.8 Approches communes
1.9 Apports de la thèse
1.10 Organisation de la thèse
Chapitre 2 :État de l’art
2.1 Les approches directes
2.2 Les approches découplées
2.3 Les approches par échantillonnage et leurs améliorations
2.4 Le mélange de la planification symbolique avec la planification de trajectoires
2.5 Résumé
2.6 Vers une approche cognitive pour la planification de trajectoire
Chapitre 3 :Planification locale de trajectoire sous contraintes
3.1 Modèles de trajectoire
3.2 Contraintes
3.3 Architecture de propagation
3.4 Trajectoires et espace des paramètres
3.5 Solutions continues
3.6 Solutions discrètes
3.7 Échantillons à base de quadratiques dans DKP
3.8 Analyse
3.9 Conclusion
Chapitre 4 :Deterministic Kinodynamic Planning
4.1 Introduction à DKP
4.2 Mécanismes d’exploration
4.3 Mise en pratique
4.4 Contrôle de l’exploration
4.5 Étude expérimentale
4.6 Simulations : évaluation de la dynamique de DKP
4.7 Expérimentations
4.8 Discussion critique de DKP
4.9 Conclusion
Chapitre 5 :Raisonnements par comportements de pilotage pour la planification de
trajectoire
5.1 Comportements de pilotage pour la planification de trajectoire
5.2 Contrôle de DKP par des paramètres de pilotage
5.3 Des arbres à la croissance simultanée
5.4 Guidage par roadmap
5.5 Exploration de l’ISEN
5.6 Dépassement
5.7 Conclusion
Chapitre 6 :Conclusion et Perspectives
Chapitre 7 :Annexe : Géométrie constructive de surface pour la planification locale de trajectoire
7.1 Définition
7.2 Opérations sur les surfaces
7.3 Délimitation des surfaces
7.4 Quelques figures de base : disque, rectangle
7.5 Composition de surfaces
7.6 Appartenance d’un point à une surface
7.7 Conclusion

Télécharger le rapport complet