Si les graphes en tant que tels représentent des modèles naturels pour de nombreuses applications réseaux (routiers, télécommunications…), des généralisations, prenant en compte la variabilité du réseau, peuvent être définies. Dans ce projet, on considère des graphes pour lesquels le statut de certaines arêtes est incertain, autrement dit nous ne sommes pas sûrs qu’elles soient fonctionnelles. Cela peut se formaliser, par exemple, en indiquant un ensemble d’arêtes et un entier k, signifiant que potentiellement k arêtes de l’ensemble présentent un dysfonctionnement. Ou encore, on peut imaginer associer à chaque arête une probabilité, indiquant ses chances d’être opérationnelle.

De tels modèles sont utilisés dans plusieurs domaines applicatifs. Pour les réseaux routiers, la présence d’arêtes bloquées peut modéliser une rue en travaux ou un embouteillage. Dans un entrepôt où se déplacent des robots VGA, une arête bloquée indique une impossibilité de passage sur une allée. Enfin, dans le domaine militaire, le graphe peut représenter une carte et l’incertitude repose sur la présence de mines/explosifs qu’un robot doit éviter [1].

Certains problèmes faciles à résoudre (temps polynomial) sur un graphe « classique » deviennent beaucoup plus difficiles lorsque ce dernier est incertain. C’est le cas du problème du Plus Court Chemin. Sa généralisation, le problème du Voyageur Canadien, est PSPACE-complet [2], impliquant qu’il ne peut pas être résolu en temps polynomial. Dans le problème du Voyageur Canadien, l’instance de départ est un graphe ainsi qu’un entier k indiquant le nombre d’obstacles. Le voyageur part d’un nœud source s et son objectif est d’arriver à la destination t. Cependant, certaines arêtes du graphe (au plus k) sont bloquées et nous ne connaissons pas leur identité. Elles sont découvertes seulement lorsque le voyageur arrive à une de leur extrémité.  L’enjeu est de parcourir le moins de distance possible : ainsi, il faut déterminer un trajet robuste à la présence de blocages. Par exemple, la stratégie naturelle visant à parcourir le plus court chemin entre s et t, puis lorsqu’on est bloqué à recalculer le plus court chemin depuis notre position, peut s’avérer catastrophique en terme de performance [3].

L’étude du Voyageur Canadien, et plus généralement des problèmes de navigation sur des graphes incertains, repose sur l’algorithmique online. Les algorithmes que l’on conçoit doivent s’adapter à l’apparition de blocages.

L’objectif du projet est de poursuivre et de généraliser l’étude des problèmes de navigation sur des graphes incertains [4,5]. D’abord, de nombreuses questions restent ouvertes sur des problèmes existants et nous souhaitons les résoudre. En particulier, sur le problème du Voyageur Canadien, on ne sait pas si les algorithmes probabilistes peuvent nous permettre d’obtenir de meilleures performances que les algorithmes déterministes. Répondre positivement à cette question nous offrirait des méthodes algorithmiques efficaces pour optimiser en moyenne les trajets sur des graphes incertains.

De plus, nous souhaitons poursuivre l’élaboration de nouveaux modèles d’incertitude en adéquation avec des applications pratiques. Par exemple, récemment, Bampis et al. [6] ont proposé un nouveau modèle où l’incertitude est anticipée par une prédiction et où l’on doit proposer un algorithme qui est très efficace si la prédiction est vraie et également relativement robuste en cas d’échec de la prédiction.

Références

[1] Aksakalli V., Sahin O. F., Ari I., An AO* based exact algorithm for the Canadian Traveler Problem, INFORMS Journal on Computing, 28(1):96-111, 2016

[2] Bar-Noy A., Schieber B., The Canadian Traveler Problem. Proc. Of SODA, 261-270, 1991

[3] Xu Y., Hu M., Su B., Zhu B., Zhu Z., The Canadian Traveller Problem and its competitive analysis, J. Comb. Optim., 18(2):195-205, 2009

[4] Bergé P., Hemery J., Rimmel A., Tomasik J., On the competitiveness of memoryless strategies for the k-Canadian Traveller Problem, Proc. Of COCOA, 566-576, 2018

[5] Bergé P., Salaün L., The influence of maximum (s,t)-cuts on the competitiveness of deterministic strategies for the Canadian Traveller Problem, Theor. Computer Science, 941:221-240, 2023

[6] Bampis E., Escoffier B., Xefteris M., Canadian Traveller Problem with Predictions, Proc. Of WAOA, 116-133, 2022