Multi-Agent Path Finding

Aussi appelé: MAPF, multi-agent pathfinding, multi-robot path planning
Catégorie: Learning & autonomy › Multi-robot
Mots-clés: multi-robot, path-planning, warehouse-automation, coordination, graph-search

Le problème du calcul de chemins sans collision pour de nombreux agents se déplaçant simultanément sur un graphe partagé, comme des robots d'entrepôt sur une grille, afin que chaque agent atteigne son but sans conflit.

Définition

Recherche de chemins multi-agents (Multi-Agent Path Finding, MAPF) : problème de planification des chemins d'un groupe d'agents qui partagent un environnement, de sorte que chaque agent aille de son départ à son but sans que deux agents occupent le même endroit au même moment ni échangent leurs places le long d'une même arête. L'environnement est généralement modélisé par un graphe, souvent une grille, et le temps est divisé en pas discrets au cours desquels chaque agent se déplace vers un sommet voisin ou attend.

Les solutions MAPF sont généralement jugées sur la somme des coûts (sum of costs), le temps total que mettent tous les agents à atteindre leurs buts, ou sur le makespan, le temps jusqu'à l'arrivée du dernier agent. Trouver une solution optimale selon ces objectifs est NP-difficile en général, aussi le domaine a-t-il développé des algorithmes qui échangent l'optimalité contre la vitesse. Parmi les méthodes optimales figure Conflict-Based Search (CBS), qui planifie chaque agent indépendamment puis résout les collisions en ajoutant des contraintes dans un arbre de recherche. Les méthodes sous-optimales, comme la planification par priorités, où les agents planifient l'un après l'autre et traitent les agents précédents comme des obstacles mobiles, passent à l'échelle d'équipes bien plus grandes.

Le MAPF continu (lifelong MAPF) est une variante dans laquelle les agents reçoivent de nouveaux buts dès qu'ils atteignent les anciens, ce qui correspond au fonctionnement réel des robots d'entrepôt et de tri. La planification tourne alors en continu, souvent sur une fenêtre de temps limitée, et le débit devient la mesure principale.

Les robots réels enfreignent aussi les hypothèses des manuels : ils ont une taille, des limites d'accélération et des retards d'exécution, si bien que les plans MAPF sont généralement exécutés avec une couche de coordination supplémentaire qui maintient les robots en sécurité lorsque certains prennent du retard. Les méthodes fondées sur l'apprentissage, y compris l'apprentissage par imitation à partir de planificateurs fondés sur la recherche, sont une direction de recherche active pour passer à l'échelle de très grandes flottes.

Pourquoi c'est important

Les entrepôts, les usines et les centres de tri exploitent des flottes croissantes de robots mobiles sur des surfaces partagées, et leur débit dépend de la qualité de la coordination de ces robots. Le MAPF fournit les algorithmes qui maintiennent les robots en mouvement sans collisions ni interblocages à mesure que les flottes grandissent.

Applications principales

Flottes de robots d'entrepôts et de centres de traitement des commandes
Systèmes de tri de colis avec de nombreux robots mobiles
Coordination de véhicules à guidage automatique (AGV) dans les usines
Coordination multidrone et du trafic au sol des aéroports
Déplacement de personnages dans les jeux vidéo et simulation de foules

En pratique

Une équipe qui exploite une flotte d'entrepôt modélise généralement la surface comme une grille ou un graphe de type carte de routes, chaque cellule étant dimensionnée pour un robot. Un planificateur central reçoit les buts du système de commandes et calcule des chemins coordonnés, souvent avec une recherche par priorités ou à fenêtre temporelle qui replanifie toutes les quelques secondes plutôt que de résoudre tout le problème de façon optimale. Les chemins sont convertis en points de passage horodatés et envoyés aux robots, et une couche d'exécution, comme un graphe de dépendances d'actions (action dependency graph), garantit qu'un robot n'entre pas dans une cellule tant que le robot qui le précède ne l'a pas libérée. Les ingénieurs mesurent le débit, le temps d'attente et la fréquence des interblocages en simulation à la taille réelle de la flotte avant de modifier l'agencement de la surface ou l'algorithme sur le système réel.

Idées reçues

Chaque robot peut planifier son propre plus court chemin indépendamment — des chemins indépendants entrent en collision, les robots doivent donc être coordonnés dans le temps comme dans l'espace
Le MAPF optimal passe à l'échelle de n'importe quelle taille de flotte — la résolution optimale est NP-difficile, les grandes flottes reposent donc sur des méthodes sous-optimales ou à fenêtre temporelle
Un plan MAPF peut être exécuté exactement tel qu'il a été calculé — les robots réels sont en avance ou en retard, l'exécution a donc besoin de sa propre couche de sécurité et de coordination

Qui devrait le savoir

Ingénieurs en automatisation d'entrepôts et en gestion de flottes
Chercheurs en planification multirobot
Intégrateurs de systèmes AMR et AGV
Chercheurs en recherche opérationnelle travaillant sur la logistique

Technologies associées

Conflict-Based Search
Planification par priorités (Prioritized Planning)
Recherche A (A Search)
Systèmes de gestion de flotte (Fleet Management Systems)
Apprentissage par imitation (Imitation Learning)

Termes associés

Projets associés

Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
Open X-Embodiment (OXE): Largest open robotics dataset: 1M+ episodes from 22 embodiments
IR-SIM: Lightweight pure-Python 2D robot simulator for navigation, control and RL research
Mesh Navigation: Robot navigation on 3D triangle meshes for rough outdoor terrain, from Nature Robots