Multi-Agent Path Finding (MAPF)

Thèmes abordés

MAPF Multi-Agent Path Finding, Informatique, code informatique, Logistique, IA Intelligence artificielle, collision, algorithme, Stochastic Local Search, algorithme de Dijkstra, deadlock, bottleneck, système multi-agents, Python

Résumé du document

La navigation d'une équipe d'agents dans un environnement partagé est un problème important pour de nombreux domaines d'application existants et émergents. Les exemples de tels domaines incluent : la logistique d'entrepôt, le tri du courrier, la gestion autonome des intersections, la coordination d'essaims de drones, etc. Dans chacun de ces contextes, on fait face à un problème combinatoire NP-difficile connu sous le nom de Multi-Agent Path Finding (MAPF).

Extraits

[...] Illustrons comment le problème de deadlock va être résolu à l'aide du Stochastic Local Search. On peut également appliquer cette méthode à des problèmes de plus grandes dimensions. En général, cela donne de très bons résultats, comme sur l'image suivante : En quelque sorte, on peut dire que l'algorithme de coopératif, appliqué dans le contexte de problème de MAPF, représente intrinsèquement une architecture des agents coopératifs, car ils communiquent entre eux et doivent modifier leur comportement (le chemin) en fonction des actions des autres agents. [...]

[...] Les conclusions En résumé, il n'est pas possible de conclure quel algorithme serait le meilleur dans le cas général, car les trois méthodes ont ses propres avantages et inconvénients. Le classique donne la solution optimale et ne nécessite pas beaucoup de calculs, mais ne marche sans blocages que pour des problèmes de petites dimensions. Le coopératif, d'un autre côté est capable de résoudre des conflits et donne une solution quasiment optimale. Toutefois, il nécessite une connaissance parfaite de toutes les positions de tous les agents et, de plus, il faut effectuer un nombre très important de calculs à chaque tour de simulation. [...]

[...] Il est, de plus, nécessaire de recalculer le chemin de chaque agent à chaque tour, ce qui nécessite un nombre très important de calculs. La résolution du conflit précédent est illustrée sur l'image ci-dessous. Enfin, une autre approche pour résoudre le problème de deadlocks est le Stochastic Local Search. Dans le cadre de ce projet, on utilise une version simplifiée de cette méthode qui consiste essentiellement à tout simplement faire un pas aléatoire lorsqu'on fait face à une situation de blocage (quand deux agents doivent occuper la même case). [...]

[...] Dans le cadre de ce projet, nous nous sommes appuyés sur le tutoriel « Tutorial on Recent Advances in Multi-Agent Path Finding », publié en AAMAS et qui propose un aperçu des techniques courantes de problèmes de MAPF. La problématique Commençons par poser le problème de MAPF. Certaines contraintes sont appliquées. Premièrement, les collisions où les deux agents se retrouveraient sur une même case de la grille sont interdit. Il y a deux types de telles collisions, comme illustrés ci-dessous : Néanmoins, le mouvement « en chaîne » est autorisé. [...]

[...] quand il atteint sa cible), tandis qu'un autre agent doit passer par cette case pour atteindre sa cible à lui, comme illustré sur l'image ci-dessous : En ce qui concerne les aspects des systèmes multi-agents qu'on a dû apprendre, sans doute a-t-on dû, avant tout, comprendre la tâche de MAPF et les algorithmes de Path Finding qui y sont appliqués. Outre cela, il nous fallait également nous familiariser avec un certain nombre des fonctions et des modules de Mesa, en Python, qui n'étaient pas présentés dans le cadre du cours, vu qu'ils sont assez spécifiques. [...]