Key points are not available for this paper at this time.
La recherche sur la planification de chemins multi-agents (MAPF) s'est récemment orientée vers des variantes de problèmes qui sont plus proches des applications réelles. Ces variantes incluent souvent l'attribution de plusieurs objectifs aux agents. Pour les résoudre, les chercheurs ont étendu l'algorithme de Recherche Basée sur les Conflits (CBS) à des objectifs multiples. Cette extension peut sembler simple à première vue mais elle est délicate et a déjà conduit au développement d'algorithmes qui, bien qu'affirmant être optimaux, renvoient des solutions suboptimales pour certaines instances de MAPF. Dans cet article, nous proposons une analyse détaillée de la question afin de sensibiliser la communauté de recherche pour éviter que cette erreur ne soit perpétuée. En outre, une première évaluation par rapport à une mise en œuvre optimale est réalisée, montrant pourquoi cette question pourrait avoir été difficile à détecter. Dans une seule des instances générées aléatoirement, le comportement suboptimal est apparu.
Mouratidis et al. (Sat,) ont étudié cette question.