Méthodes probabilistes pour la planification réactive de mouvements
Résumé
Current motion planning techniques are now capable of planning motions for complex mechanisms in cluttered environments. Nevertheless the adaptation of these planners to scenes with both static and mobile obstacles has been limited so far. One of the reasons is the cost to reflect during queries the dynamic changes of the scene into the data structure preprocessed to capture the free configuration space connectivity. Our main contribution is the proposition of a new planner able to deal with static and mobile obstacles. This hybrid planner combines the PRM framework, originally designed for solving multiple-query problems and that we extended for operating in dynamic scenes with improved diffusion techniques designed to solve single queries without requiring any preprocessing. In practice this planner is also based on several lazy evaluation mechanisms to improve the efficiency of the approach. The design of this new planer has led to the main following development: - The proposition of an original architecture for this planner dedicated to changing environments. This architecture include several lazy evaluation mechanisms to make the planner really efficient. - A new diffusion planner to locally reconnect portions of the roadmap broken by mobile obstacles. We call it Dynamic-Domain RRT planner. This new extension of the original RRT method is able to automatically balance refinement of already explored regions and expansion toward new unknown regions. - Two methods to create cyclic roadmaps to initialise the planner. The first one use the assumption that mobile obstacles are confined to some regions of the space to build roadmap specifically to changes of the obstacles positions. The second one is a general method to capture the connectivity but also the homotopical classes of the free configuration space in a condensed data structure. All these methods are implemented within the software platform Move3D developed at LAAS and evaluated on different kind o f complex 3D examples.
Les techniques de planification de mouvement actuelles sont maintenant capables de résoudre des problèmes mettant en jeu des mécanismes complexes plongés au sein d'environnements encombrés. Néanmoins, l'adaptation de ces planificateurs à des scènes comprenant à la fois des obstacles statiques et des obstacles mobiles s'est avérée limitée jusqu'ici. Une des raisons en est le coût associé à la mise à jour des structures de données qui sont précalculées pour capturer la connexité de l'espace libre. Notre contribution principale concerne la proposition d'un nouveau planificateur capable de traiter des problèmes comprenant à la fois obstacles statiques et obstacles mobiles. Ce planificateur hybride combine deux grandes familles de techniques. D'une part les techniques dites PRM, initialement conçues pour résoudre des problèmes à requêtes multiples et que nous avons étendu à des problèmes de scènes dynamiques. D'autre part, de nouvelles techniques de diffusion, alors que celles-ci sont généralement dédiées aux problèmes simple requête ne nécessitant aucune opération de prétraitement. Les principaux développements accompagnant la construction de ce planificateur sont les suivants : - La proposition d'une architecture originale pour le planificateur dédié aux environnements changeants. Cette architecture inclut notamment plusieurs mécanismes dits d' "évaluation paresseuse" qui permettent de minimiser les test de collision et ainsi d'assurer de bonnes performances. - Le développement d'une nouvelle méthode de diffusion permettant de reconnecter localement certaines portions du réseau invalidées par la présence des obstacles mobiles. Cette méthode, appelée RRT à Domaine Dynamique correspond en fait une extension des planificateur bien connus à bases de RRTs. Un des intérêt propre à notre approche est d'équilibrer automatiquement deux comportements propres au planificateur : l'exploration vers des régions encore inconnues et l'affinage du modèle des régions de l'espac e déjà explorées. - Deux méthodes originales de création de réseaux cycliques qui servent à initialiser notre planificateur. La première assume que les obstacles mobiles sont confinés dans une région donnée, pour construire un réseau adapté aux différents types de changements de position possibles. La seconde est une méthode qui construit des réseaux appelés "réseaux de rétraction". A l'aide d'une structure de donnée de faible taille, cette structure parvient à capturer les différentes variétés de chemins de l'espace, à travers notamment chacune des classes d'homotopie de l'espace libre. Toutes ces méthodes sont implémentées au sein de la plate-forme de travail Move3D développée au LAAS-CNRS et sont évaluées sur différents types de systèmes mécaniques plongés au sein d'environnements 3D.
Loading...