Planification de chemins collective et collaborative dans des grands graphes

Cet article étudie les algorithmes de planification de chemins pour deux agents dans des graphes où ils sont affectés à des états initiaux et buts indépendants mais sont incités, par réduction de la fonction de coût globale quand ils se déplacent en formation, à partager une partie de leur parcours. Les applications de ces algorithmes vont du covoiturage au vol en formation. Après avoir présenté un algorithme optimal mais ne passant pas à l’échelle, nous proposons une approche découplée qui sépare les raisonnements spatial et temporel en, dans un premier temps, trouvant dans le graphe les nœuds de convergence et divergence, puis dans une seconde étape, synchronisant temporellement les agents au nœud de convergence par adaptation de leurs vitesses le long de leur chemin dans le graphe. Nous introduisons également une fonction heuristique originale qui prend en compte les chemins partagés potentiels dans le graphe et qui est utilisée pour guider une recherche A* sur un graphe produit croisé qui représente le déplacement coordonné des agents. Finalement, nous expérimentons notre cadre de travail et comparons ses variantes sur des problèmes de type grille.