💻 computer science

Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

Cet article introduit l'Anytime Closed-Loop Conflict-Based Search (ACCBS), un nouvel algorithme qui ajuste dynamiquement son horizon de planification et réutilise un arbre de contraintes pour fournir des solutions de haute qualité et asymptotiquement optimales pour la recherche de chemins multi-agents avec une faible latence et une robustesse aux perturbations en ligne.

Auteurs originaux : Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

Publié 2026-06-25

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un entrepôt automatisé massif rempli de centaines de petits robots, tous essayant de déplacer des boîtes du point A au point B sans se cogner les uns les autres. C'est le problème de la Recherche de Chemins Multi-Agents (MAPF - Multi-Agent Path Finding). C'est comme essayer de coordonner une danse où chacun a une destination différente, et si deux danseurs tentent d'occuper le même endroit au même moment, tout le spectacle s'arrête.

Pendant longtemps, les planificateurs de robots ont été confrontés à un problème de « Goldilocks » (le juste milieu) frustrant :

L'approche du « Plan Parfait » : Ces algorithmes essaient de tracer l'intégralité du voyage pour chaque robot avant que le moindre pas ne soit fait. C'est comme un chef d'orchestre qui écrit une symphonie de 3 heures avant la première note. Le problème ? Si l'entrepôt est immense ou encombré, cela prend tellement de temps à écrire la symphonie que les robots restent là à attendre indéfiniment.
L'approche du « Correctif Rapide » : Ces algorithmes regardent simplement l'étape suivante pour décider quoi faire. C'est comme un conducteur qui ne regarde que le pare-chocs devant lui. C'est rapide, mais ils se retrouvent souvent coincés dans des embouteillages ou prennent de mauvaises décisions à long terme parce qu'ils ne peuvent pas voir au-delà du tournant.

Ce document présente une nouvelle méthode appelée ACCBS (Anytime Closed-Loop Conflict-Based Search) qui tente de tirer le meilleur des deux mondes. Voici comment elle fonctionne, en utilisant des analogies simples :

L'idée centrale : Le « Télescope Grandissant »

Imaginez que vous conduisez une voiture dans le brouillard.

Ancienne méthode : Vous attendez que le brouillard se dissipe complètement pour voir votre destination entière avant de démarrer le moteur. (Trop lent).
Méthode simple : Vous ne regardez que la route immédiatement devant vos pneus. (Trop risqué).
Méthode ACCBS : Vous commencez par regarder juste quelques pieds devant vous pour démarrer immédiatement. Mais dès que vous avez une seconde de libre, vous « dézoomez » votre télescope pour voir un peu plus loin. Si vous avez encore plus de temps, vous dézoomez à nouveau.

ACCBS fait exactement cela. Il commence par planifier juste l'étape suivante pour tous les robots afin qu'ils puissent bouger instantanément. Ensuite, il utilise tout le temps informatique restant pour étendre son « champ de vision » (l'horizon de planification) pour voir 2 étapes devant, puis 3, puis 4, et ainsi de suite.

Le tour de magie : Réutiliser la « Carte »

Vous pourriez penser que « si vous continuez à dézoomer, ne devez-vous pas redessiner toute la carte à chaque fois ? ». Cela serait trop lent.

L'innovation ingénieuse du papier est la Réutilisation de l'Arbre de Contraintes (Constraint Tree Reuse).
Considérez le processus de planification comme la construction d'un arbre de scénarios « et si ».

Quand ACCBS regarde 1 étape en avant, il construit un petit arbre de possibilités.
Quand il décide de regarder 2 étapes en avant, il ne jette pas cet arbre. Il se contente d'ajouter de nouvelles branches au sommet de l'arbre existant.
Parce que les mathématiques fonctionnent d'une manière spécifique (appelée « invariance de coût »), la valeur des anciennes branches ne change pas lorsque vous en ajoutez de nouvelles.

C'est comme construire une tour de blocs. Vous ne renversez pas la tour pour la rendre plus haute ; vous continuez simplement à empiler de nouveaux blocs par-dessus. Cela signifie que l'ordinateur ne perd pas de temps à recalculer ce qu'il a déjà résolu.

Pourquoi le terme « Anytime » est crucial

Le terme « Anytime » (en tout temps) est crucial. Cela signifie que l'algorithme est interrompable.

Si l'ordinateur doit prendre une décision en 0,5 seconde, il vous donne le meilleur plan qu'il ait pu trouver en cette demi-seconde (ce qui est généralement juste l'étape suivante sécurisée).
Si vous disposez de 5 secondes, il vous donne un bien meilleur plan qui prévoit plus loin.
Si les robots sont confrontés à une surprise (comme une boîte qui tombe ou un robot qui se déplace plus lentement que prévu), ACCBS ne panique pas. Il arrête simplement le plan actuel, regarde la nouvelle réalité, et recommence son processus de « dézoomage » à partir de la position actuelle.

Les Résultats

Les auteurs ont testé cela sur diverses cartes, allant de pièces vides à des entrepôts encombrés avec des centaines de robots.

Vitesse : C'est beaucoup plus rapide que d'essayer de planifier tout le voyage d'un coup.
Qualité : À mesure que vous lui donnez du temps pour « réfléchir », les chemins qu'il trouve deviennent meilleurs et plus proches de la solution parfaite.
Fiabilité : Contrairement à d'autres méthodes qui pourraient planter ou expirer si la situation devient trop complexe, ACCBS a toujours quelque chose à proposer car il commence par une première étape simple et sûre.

En résumé

ACCBS est comme un contrôleur de trafic intelligent qui n'attend pas un programme parfait à long terme. Au lieu de cela, il met les voitures en mouvement immédiatement avec un plan sûr à court terme, puis affine continuellement le plan à mesure qu'il obtient plus d'informations et de temps, le tout sans jamais avoir à repartir de zéro. Il équilibre le besoin de vitesse avec la nécessité d'une bonne solution, ce qui le rend idéal pour les flottes de robots du monde réel très actives.

Résumé Technique : Recherche Basée sur les Conflits à Horizon Adaptatif pour la Recherche de Chemins Multi-Agents en Boucle Fermée

Énoncé du Problème

La recherche de chemins multi-agents (MAPF - Multi-Agent Path Finding) est un problème de coordination fondamental pour les grandes flottes de robots dans les entrepôts automatisés et la logistique, nécessitant que les agents se déplacent de sommets de départ vers des sommets d'arrivée sur un graphe sans collisions. Bien que la MAPF optimale soit NP-difficile, les solveurs existants sont confrontés à un compromis entre scalabilité et garanties de performance.

Les planificateurs en boucle ouverte (par exemple, la recherche basée sur les conflits standard, CBS) calculent des trajectoires complètes avant l'exécution. Bien qu'ils offrent des garanties d'optimalité, ils souffrent d'une latence de planification élevée et d'une faible scalabilité sur des instances denses à long horizon, retardant ainsi l'exécution des actions.
Les heuristiques en boucle fermée réduisent la latence en replanifiant à partir de l'état actuel, mais manquent souvent de garanties de performance fiables, ce qui limite leur utilité dans les déploiements critiques pour la sécurité.
Les approches à horizon fini (par exemple, Windowed CBS/RHCR) tentent de combler ce fossé mais font face à un « dilemme de sélection de l'horizon » : un horizon de planification fixe doit être choisi a priori. Un horizon court est efficace mais myope, tandis qu'un horizon long améliore la qualité de la solution au prix d'une croissance exponentielle de la recherche. De plus, les méthodes à fenêtre fixe perdent souvent les garanties de complétude et d'optimalité asymptotique de la CBS standard.

Méthodologie : Recherche Basée sur les Conflits en Boucle Fermée à Temps Réel (ACCBS)

Le papier propose ACCBS, un algorithme de MAPF en boucle fermée qui combine la CBS à horizon fini avec un mécanisme d'horizon dynamique inspiré du contrôle prédictif de modèle (MPC).

Mécanismes Fondamentaux

CBS en Boucle Fermée à Horizon Fini :
- Au lieu de résoudre la trajectoire complète, l'algorithme planifie sur un horizon de prévision $H$ .
- Il optimise une fonction de coût comprenant un coût courant (étapes effectuées pour atteindre l'objectif) et un coût terminal (heuristique admissible estimant la distance restante jusqu'à l'objectif).
- À chaque pas de temps $t$ , il résout les conflits uniquement à l'intérieur de la fenêtre de prévision, exécute le premier mouvement, puis replanifie à partir du nouvel état.
Horizon Adaptatif via l'Approfondissement Itératif :
- ACCBS ne fixe pas l'horizon $H$ à l'avance. Au lieu de cela, il maintient un horizon courant $h_r$ qui commence à 1 et croît de manière incrémentale jusqu'à un maximum $H_{max}$ tant que le budget de temps de calcul le permet.
- Cela permet à l'algorithme de retourner immédiatement une solution réalisable à faible latence (avec $h_r=1$ ) et de l'affiner avec des horizons plus longs si du temps reste disponible, présentant ainsi un comportement anytime.
Préfixe Actif et Réutilisation de l'Arbre de Contraintes :
- Pour éviter le coût prohibitif de redémarrer la recherche à chaque fois que l'horizon augmente, ACCBS introduit le concept de préfixe actif. Les conflits ne sont résolus qu'au sein du préfixe actif actuel de longueur $h_r$ ; les conflits au-delà de ce préfixe sont temporairement ignorés.
- Invariance du Coût (Lemme III.1) : Le papier prouve que sous certaines hypothèses de planificateur de bas niveau (les suffixes suivent les chemins les plus courts), le coût d'un nœud reste invariant lorsque l'horizon est étendu.
- Réutilisation de l'Arbre de Contraintes (Proposition III.1) : Parce que les coûts et les relations parent-enfant sont préservés, l'arbre de contraintes construit pour un horizon plus petit $h$ est un sous-arbre valide pour $h+1$ . Cela permet à ACCBS d'étendre de manière transparente l'horizon sans redémarrer la recherche, rendant l'effort de calcul cumulé comparable à une exécution unique au maximum de l'horizon.

Garanties Théoriques

Complétude et Optimalité : Le Théorème III.1 établit que si le budget de temps est infini et que $H_{max}$ est au moins égal à la durée de la solution optimale (makespan), ACCBS est complet et retourne une solution globalement optimale (Somme des Coûts, SOC).
Propriété Anytime : À mesure que le temps d'exécution augmente, le coût de la meilleure solution trouvée est monotone non-décroissant (borné par le coût optimal) et converge vers l'optimum.
Faisabilité à l'Étape Unique : L'algorithme garantit une commande sans collision à chaque pas de temps par construction, car il exécute toujours la première étape d'un nœud possédant un préfixe actif sans conflit (où $h_r \ge 1$ ).

Résultats Expérimentaux

Les auteurs ont évalué ACCBS par rapport à des bases telles que PIBT, EECBS, MAPF-LNS2, et LaCAM2/3, ainsi que RHCR dans des contextes d'exécution en une seule passe (one-shot), à vie (lifelong) et stochastique.

MAPF One-Shot : ACCBS atteint un équilibre favorable entre efficacité computationnelle et qualité de solution. À mesure que le budget de temps par étape augmente, ACCBS réduit la Somme des Coûts (SOC) et se rapproche de l'optimalité, surpassant les heuristiques rapides comme PIBT et évitant les échecs de dépassement de délai (timeout) des solveurs à trajectoire complète comme EECBS sur des cartes denses.
MAPF Lifelong : Dans des scénarios avec des objectifs changeants, ACCBS démontre une capacité de traitement compétitive. Son horizon adaptatif lui permet de passer à l'échelle pour de plus grandes flottes là où les méthodes à fenêtre fixe (RHCR) échouent par timeout.
Incertitudes Stochastiques : Dans des simulations avec des délais d'exécution et des arrivées d'agents, ACCBS surpasse les bases en boucle ouverte. Les méthodes en boucle ouverte sont limitées par la nécessité de replanifier des trajectoires complètes lors de perturbations, tandis qu'ACCBS absorbe naturellement les perturbations en replanifiant à partir de l'état actuel.
Étude d'Ablation : Le papier note que l'ajout de la sélection de conflit priorisé (PC) à ACCBS peut parfois réduire la qualité de la solution sous des budgets fixes, car la charge de travail de la classification des conflits surpasse les bénéfices de la réduction des expansions de l'arbre.

Signification et Revendications

Le papier affirme qu'ACCBS répond au compromis critique entre latence de planification et qualité de solution dans les systèmes multi-agents. Ses principales contributions sont :

Élimination des Choix de Conception Fragiles : En adaptant l'horizon en ligne, ACCBS élimine le besoin de régler manuellement un horizon fixe dépendant des caractéristiques spécifiques de l'instance et des budgets de temps.
Expansion Efficace de l'Horizon : Grâce à l'invariance du coût et à la réutilisation de l'arbre de contraintes, l'algorithme bénéficie de l'approfondissement itératif sans la pénalité de calcul associée au redémarrage des recherches.
Restauration des Garanties : Contrairement aux méthodes en boucle fermée à fenêtre fixe, ACCBS récupère les garanties d'optimalité asymptotique et de complétude de la CBS standard.
Robustesse : La formulation en boucle fermée accommode naturellement les perturbations en ligne (délais, nouveaux agents) sans nécessiter de replanification complète de la trajectoire.

Les auteurs positionnent ACCBS comme une solution pratique pour les déploiements à grande échelle et critiques pour la sécurité, où la flexibilité d'exécution et les garanties de performance sont toutes deux requises.