Soutenance mémoire
Les mondes virtuels sont aujourd’hui utilisés dans de nombreux domaines applicatifs. Ces mondes virtuels sont généralement peuplés à l’aide d’agents autonomes qui rendent ces environnements plus vivants. Dans le cadre de cette thèse nous nous sommes intéressés à la navigation de tels agents autonomes au sein de ces environnements virtuels. La planification de chemin est une tâche cruciale pour ces agents puisqu’elle va influencer directement leur autonomie de mouvement et leur capacité à agir au sein de ces mondes. Nous nous sommes focalisés au cours de nos travaux sur la planification de chemin pour des agents peuplant des environnements dynamiques dont la configuration évolue au cours de la simulation de manière non connue a priori. Afin de répondre aux contraintes temporelles imposées par de nombreuses applications interactives, telles que les jeux vidéo, nous nous sommes également donné l’objectif de proposer une solution de planification assez performante pour être compatible avec de telles applications.
Introduction à la planification de chemin
La problématique de la planification de chemin est définie ainsi : étant donné un robot possédant un nombre variable de degrés de liberté, et une description de l’environnement où ce robot est immergé, comment trouver un chemin libre de toutes collisions entre deux configurations du robot au sein de l’environnement. De nombreux exemples illustrant cette problématique peuvent être cités. Le rôle de la planification va être par exemple de déterminer un chemin entre deux positions dans un environnement. Il peut s’agir ainsi d’un agent virtuel cherchant son chemin dans un environnement tel qu’un Personnage Non Joueur (PNJ) dans un jeu vidéo. On peut également s’intéresser au déplacement d’un bras mécanique industriel possédant de nombreux degrés de libertés et étant placé dans un environnement très contraint. La nature du robot (ou de l’agent) considéré ainsi que les propriétés de l’environnement dans lequel il va évoluer vont définir différents types de problèmes. Vu la grande variété de problèmes abordés, la planification de chemin a fait l’objet de nombreuses recherches durant les dernières décennies, de nombreux résultats sont discutés dans les états de l’art proposés par Latombe [Lat91], Choset [CLH+05] et LaValle [LaV06].
La planification de chemin dépend en grande partie de l’environnement dans lequel l’agent va évoluer. La formulation des problèmes de planification de chemin va donc généralement reposer sur la représentation qui est faite de cet environnement, aussi appelée « espace de travail » ou workspace. Les différentes méthodes de planification proposées explorent une représentation duale de l’espace de travail afin d’identifier le chemin désiré. Cette représentation duale de l’espace de travail est appelée l’espace des configurations ou C-Space [Lp83]. Cet espace des configurations est défini comme un espace à N dimensions dans lequel chacun des N axes de la base représente un degré de liberté du robot. Dans cet espace, une configuration est un vecteur de dimension N représentant une posture entièrement définie de l’agent en fixant la valeur de ces N degrés de liberté. Une courbe dans cette espace des configurations va donc représenter une séquence de postures de l’agent et donc un mouvement de celui ci. Afin d’identifier un chemin pour l’agent dans l’environnement, les algorithmes de planification de chemin vont donc chercher une séquence de configurations réalisables dans l’espace des configurations. Cet espace des configurations est généralement divisé en deux sous-ensembles : C-Free et C-Obstacle. C-Free représente l’ensemble des configurations admissibles, c’est-à-dire l’ensemble des configurations pour lesquelles l’agent n’entre pas en collision avec lui-même ou avec l’environnement. À l’opposé, C-Obstacle représente l’ensemble des configurations invalides, c’est-à-dire où l’agent est en collision avec lui-même ou son environnement. Planifier un chemin pour un agent au sein de son environnement revient donc à trouver une séquence valide de configurations dans le C-Space entre la configuration initiale de l’agent et une configuration cible. Afin d’être valide, cette trajectoire doit être composée d’une séquence de configurations appartenant à C-Free. Les méthodes de planification de chemin s’intéressent donc en grande partie à proposer une représentation de C-Free adaptée en particulier à un type de problèmes. La recherche de chemin lors de la planification va également être guidée par des critères tendant à optimiser le chemin généré. Certaines méthodes vont se focaliser sur la génération de chemin les plus courts possibles tandis que d’autres vont se concentrer sur des critères de sécurité de l’agent en cherchant par exemple à éloigner au maximum le chemin des obstacles.
Le problème de la planification de chemin a été démontré comme étant PSPACEcomplet [Rei79, Can88]. Cette complexité implique donc de devoir faire des approximations ou de sacrifier des critères d’optimalité afin de simplifier le problème. Ces approximations peuvent porter sur la qualité des planifications effectuées ou par exemple sur l’occupation mémoire dédiée à l’algorithme ou au temps de calcul qui lui est alloué. Il est également possible de simplifier le problème en diminuant la dimension de l’espace de recherche (i.e. l’espace des configurations) et donc par conséquent en réduisant le nombre de degrés de liberté de l’agent considéré. Enfin, la complexité de latâche de navigation vaégalement être dépendante de la complexité de l’environnementconsidéré.Nousallons nous intéresser au cours de cette étude bibliographique à troisfamilles distinctes de problèmes de planification et aux solutions qui ont été proposéesafin d’y répondre. Nous verrons ainsi, dans un premier temps, les méthodes proposées pour la planification à l’intérieur d’environnement statique. Nous aborderons ensuite le cas des environnements majoritairement statiques mais où il est possible d’avoir des obstacles mobiles, se déplaçant dans le temps. Nous finirons par des environnements entièrement dynamiques au cours de la simulation, considérant les objets mobiles à la fois comme des obstacles, mais également comme des aides à la navigation. Enfin, la planification de chemin et le mouvement de l’agent le long de ce chemin étant corrélés, nous verrons dans une dernière partie différentes méthodes qui ont été proposées afin de lier le chemin généré au mouvement de l’agent et également comment il est possible d’adapter les postures de celui-ci pour planifier des chemins tenant compte de contraintes environnementales variées.
Planification de chemin en environnements statiques
Les environnements statiques se caractérisent par leur structure qui n’est pas amenée à évoluer au cours du temps. Cette propriété implique donc qu’il n’y a pas de nouvelles accessibilités ou obstructions créées pendant le déroulement de la simulation. Puisque la configuration de ces environnements ne change pas, il est donc possible d’effectuer des précalculs afin de proposer des structures de données performantes lors de requêtes de planification de chemin ultérieures. Les méthodes proposées pour caractériser les environnements navigables vont se diviser principalement en deux familles. D’un côté, les méthodes de décomposition en cellules vont représenter l’espace navigable à l’aide de zones interconnectées de formes prédéfinies permettant d’appréhender les limites de C-Free et de C Obstacles. D’un autre côté, les méthodes utilisant les cartes de cheminement vont représenter un sous-ensemble de C-Free par un ensemble de chemins standardisés permettant la navigation de l’agent.
Décomposition en cellules
La décomposition en cellules propose de diviser l’espace des configurations en cellules de formes prédéfinies. Celles-ci sont ensuite caractérisées selon leur appartenance à C-Free ou C-Obstacle afin de construire une structure de données plus adaptée à la planification de chemin. Les méthodes de décomposition en cellules se répartissent en deux familles : les décompositions approchées et les décompositions exactes. Les décompositions approchées construisent une représentation approchée de l’environnement en ne cherchant pas à caractériser précisément C-Free mais en en définissant un sous-ensemble dont la représentation est plus simple. Les décompositions exactes sont des structures généralement plus coûteuses à calculer mais qui permettent une description plus fine de l’environnement en décrivant exactement C-Free et, par conséquent, C-Obstacle.
Décomposition approchée en cellules
Les méthodes de décompositions approchées proposent l’utilisation d’une forme prédéfinie de cellules afin de caractériser l’environnement [Lat91, Kuf98, Kuf04, SYN01, LC03, Li04]. Ces cellules représentent des sous-ensembles de l’espace des configurations et sont interconnectées afin de capturer la connectivité de l’environnement. Les cellules obstruées par une partie de C-Obstacles sont ensuite annotées et interdites à la navigation lors de la planification de chemin. Lors de l’utilisation de décompositions approchées, le rôle de la planification va être d’identifier une séquence de cellules interconnectées et appartenant à C-Free permettant de relier la position courante de l’agent à son but. Ces décompositions en cellules sont généralement effectuées à l’aide de grilles régulières 2D composées de cellules carrées [Kuf98]. Les obstacles de l’environnement sont ensuite projetés dans cette grille permettant de marquer les cellules obstruées . La représentation de l’environnement sous la forme d’une grille régulière 2D permet de projeter les obstacles de l’environnement dans une bitmap 2D et de pouvoir ainsi profiter de la carte graphique afin d’accélérer la planification de chemin lors des requêtes. Au cours de cette planification, chaque cellule dans C-Free permet l’accès à ses 8 cellules avoisinantes si celles-ci appartiennent également à C-Free (4 cellules directement voisines, 4 cellules dans les diagonales). Cette exploration de la grille régulière peut également être améliorée en utilisant des heuristiques afin d’empêcher les changements de direction trop brusques de l’agent ce qui permet également de réduire l’espace de recherche [Kuf04]. Afin de gérer des environnements plus complexes, certaines techniques proposent l’utilisation de plusieurs grilles régulières dans un même environnement afin de pouvoir représenter simultanément plusieurs capacités de déplacement [SYN01]. Ceci permet également de supprimer la contrainte 2D amenée par l’utilisation d’une unique grille régulière et de gérer en conséquence des environnements 3D avec différents étages [LC03, Li04]. En se basant sur les caractéristiques de l’agent, cette approche permet, en plus, de localiser dans la grille régulière les accès existants entre des zones déconnectées de l’environnement, gérant ainsi la planification de chemin au sein d’environnements non connexes.
|
Table des matières
Introduction
1 Contexte de recherche
2 Problématique
3 Contributions
4 Organisation de ce mémoire
1 Bibliographie
1 Introduction à la planification de chemin
2 Planification de chemin en environnements statiques
2.1 Décomposition en cellules
2.2 Cartes de cheminement
3 Planification de chemin en environnements statiques avec des éléments dynamiques
3.1 Adaptation ponctuelle de la représentation de l’environnement pour la planification de chemin
3.2 Adaptation dynamique de la représentation de l’environnement pour la planification de chemin
3.3 Planification de trajectoire
4 Planification de chemin en environnements complexes dynamiques
5 Planification de chemin et mouvements de l’agent
6 Conclusion
2 Représentation de l’agent et des objets de l’environnement
1 Représentation de l’agent
1.1 Découpler animation de l’agent et planification de son chemin
1.2 Caractérisation de l’agent
2 Caractérisation des objets
2.1 Préambule
2.2 Les Volumes d’Interaction : Caractérisation de l’impact topologique d’un objet
2.3 Mouvements des objets et Volumes d’Interaction
3 Conclusion
3 Représentation dynamique de la topologie
1 Caractérisation des relations entre deux objets de l’environnement
1.1 Caractérisation des accessibilités et obstructions entre deux objets
1.2 Détection des interactions entre objets
2 Représentation de la topologie globale et de son évolution au cours du temps
2.1 Le Graphe Topologique
2.2 Représentation de la topologie et de son évolution au cours du temps
2.3 Suivi des modifications de Volumes d’Interaction
3 Conclusion
4 Planification de trajectoire en environnement dynamique
1 Planification de la trajectoire locale
1.1 Représentation de la topologie locale à un élément
1.2 Anticipation de l’évolution des obstructions locales dans le domaine spatio-temporel
1.3 Planification locale dans le domaine spatio-temporel
1.4 Réactivité de l’agent pendant la navigation
2 Planifier le déplacement de l’agent dans l’environnement dynamique
2.1 Raffinement des relations topologiques
2.2 Calcul et optimisation du chemin topologique
3 Planification hiérarchique
3.1 Association de la planification globale et locale
3.2 Gestion d’une obstruction de la Surface Navigable
4 Conclusion
5 Présentation des résultats obtenus
1 Architecture globale
2 Définition des environnements
2.1 Représentation de l’agent
2.2 Représentation pratique des éléments de l’environnement virtuel
3 Environnements de tests
4 Performances observées
5 Conclusion
Conclusion
