Recherche de chemins multi-agents robuste et probabiliste

Résumé

Dans un problème de recherche de chemin multi-agents (MAPF), la tâche consiste à déplacer un ensemble d'agents vers leurs emplacements cibles sans conflits. Dans le monde réel, des événements inattendus peuvent retarder certains des agents. Dans cet article, nous étudions donc le problème de trouver une solution p-robuste à un problème MAPF donné, c'est-à-dire une solution qui réussit avec une probabilité d'au moins p, même si des retards inattendus peuvent se produire. Nous proposons deux méthodes pour vérifier que des solutions données sont p-robustes. Nous introduisons également un algorithme optimal basé sur CBS, appelé pR-CBS, et un algorithme sous-optimal rapide, appelé pR-GCBS, pour trouver de telles solutions. Nos expériences montrent qu'une solution p-robuste réduit le nombre de conflits par rapport aux solutions optimales non robustes.