Narrow Passage Problem

• Aussi appelé: narrow passages
• Catégorie: Planning & manipulation › Motion planning
• Mots-clés: motion-planning, sampling-based-planning, configuration-space, planner-failure-modes

Difficulté qu'ont les planificateurs par échantillonnage avec les couloirs minces de l'espace libre : les échantillons aléatoires y tombent rarement, si bien que la planification ralentit ou se contente d'un long détour.

Définition

Le problème des passages étroits (narrow passage problem) est la faiblesse la plus connue des planificateurs de mouvement par échantillonnage tels que les cartes de routes probabilistes et les arbres aléatoires à exploration rapide. Ces planificateurs explorent l'espace de configuration en tirant des échantillons aléatoires et en les reliant par de courts mouvements sans collision. Si le seul itinéraire, ou le plus court, traverse une région de l'espace libre qui est mince dans une ou plusieurs directions, la probabilité qu'un échantillon uniforme y tombe est proportionnelle à son volume, qui est minuscule. Même un échantillon qui y tombe peut ne pas se connecter à des voisins des deux côtés. Le planificateur a alors besoin d'un très grand nombre d'échantillons pour trouver le passage, ou il trouve d'abord un itinéraire plus long.

L'effet croît avec la dimension. Un interstice un peu plus large que le robot sur une carte 2D est facile à échantillonner, mais pour un bras à 7 articulations qui atteint l'intérieur d'une étagère, insère une cheville dans un trou ou fait passer une pièce dans un montage, les configurations valides peuvent former une mince lamelle dans un espace à nombreuses dimensions, et leur fraction de volume devient extrêmement faible. Les analyses théoriques des planificateurs par échantillonnage, comme l'expansivité (expansiveness) et l'ε-qualité (ε-goodness) de l'espace libre, rendent cette dépendance explicite : les garanties de convergence restent valables, mais le nombre d'échantillons nécessaires augmente fortement à mesure que les passages se resserrent.

De nombreux remèdes orientent l'échantillonnage vers les bords et les interstices de l'espace libre. L'échantillonnage gaussien conserve les échantillons proches des surfaces des obstacles, le test du pont conserve les milieux de courts segments dont les deux extrémités sont en collision, les échantillonneurs fondés sur les obstacles et sur l'axe médian poussent les échantillons vers le bord ou le milieu des couloirs, et les échantillonneurs appris prédisent où se trouvent les configurations utiles. D'autres méthodes élargissent temporairement l'espace libre en rétrécissant les obstacles ou en relâchant les contraintes, planifient dans le problème plus facile, puis réparent le chemin. Dans la pratique de l'ingénierie, choisir des points de passage intermédiaires ou des régions de but bien placés fonctionne souvent.

Pourquoi c'est important

De nombreuses tâches réelles sont des problèmes de passages étroits : insertion, atteinte dans des étagères et des bacs encombrés, passage par des portes ou des montages serrés. Reconnaître le problème explique les dépassements de délai et les détours du planificateur, et oriente vers des corrections dans l'échantillonneur plutôt que vers une simple hausse de la limite de temps.

Applications principales

• Insertion cheville-trou (peg-in-hole) et assemblage dans des montages
• Mouvements de bras dans des étagères, des armoires et des bacs
• Robots mobiles et véhicules passant par des portes et des couloirs étroits
• Analyse du démontage et de la maintenabilité de pièces mécaniques
• Évaluation comparative et conception de stratégies d'échantillonnage pour planificateurs de mouvement

En pratique

Un bras doit placer une pièce dans un montage avec quelques millimètres de jeu de chaque côté. Avec un échantillonneur uniforme, le planificateur dépasse souvent son délai ou renvoie des chemins qui font un large détour autour du montage. L'équipe confirme la cause en réduisant légèrement les maillages de collision et en constatant que la planification devient rapide. Elle ajoute ensuite une pose de pré-insertion au-dessus du montage comme but intermédiaire, remplace l'approche finale par un déplacement cartésien en ligne droite vérifié contre les collisions, et ajoute un échantillonneur qui concentre les échantillons près des surfaces des obstacles pour le reste du mouvement libre. Le temps de planification baisse et les détours disparaissent.

Idées reçues

• Un passage étroit est un interstice physiquement étroit — il est étroit dans l'espace de configuration ; une porte large peut rester un passage étroit pour un objet long qui doit être tourné avec précision
• Plus de temps suffit toujours — le nombre d'échantillons nécessaires peut croître fortement avec la dimension et l'étroitesse, si bien qu'un meilleur échantillonnage ou une décomposition aident généralement davantage
• La complétude probabiliste signifie que le planificateur trouvera vite le passage — la complétude promet seulement un succès à terme
• Seuls les planificateurs par échantillonnage en souffrent — la recherche sur grille et l'optimisation peinent aussi avec les régions minces de l'espace libre, à cause des limites de résolution ou de mauvaises estimations initiales

Qui devrait le savoir

• Ingénieurs en planification de mouvement utilisant OMPL, MoveIt ou des bibliothèques similaires
• Ingénieurs en manipulation travaillant sur l'insertion et l'assemblage
• Chercheurs qui développent des stratégies d'échantillonnage pour planificateurs
• Étudiants qui étudient la planification par échantillonnage

Technologies associées

• Échantillonnage gaussien (Gaussian sampling)
• Échantillonnage par test du pont (bridge test)
• PRM fondé sur les obstacles (Obstacle-based PRM)
• PRM sur l'axe médian (Medial-axis PRM)
• Distributions d'échantillonnage apprises
• OMPL

Termes associés

• Probabilistic Roadmap
• Rapidly-exploring random tree
• Configuration Space
• RRT*
• Homotopy Class
• Peg-in-hole insertion

Projets associés

• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
• Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines
• NeuPAN: Real-time end-to-end planner that maps raw lidar points directly to robot actions