Recherche multidirectionnelle

Résumé

Dans le problème de la réunion multi-agents (MAM), la tâche consiste à trouver un lieu de réunion pour plusieurs agents, ainsi qu'un chemin pour chaque agent vers ce lieu. Dans cet article, nous présentons MM*, un algorithme de recherche heuristique multidirectionnelle qui trouve le lieu de rencontre optimal sous différentes fonctions de coût. MM* généralise l'algorithme de recherche bidirectionnelle Meet in the Middle (MM) au cas de la recherche d'un lieu de rencontre optimal pour plusieurs agents. Plusieurs heuristiques admissibles sont proposées, et des expériences démontrent les avantages de MM*.