Problèmes d’optimisation dans les graphes paramétrés

L’utilisation par les humains de moyens pour estimer des quantités remonte au début de leur Histoire. En effet ceux-ci ont éprouvé très tôt le besoin de calculer. Ainsi nous en retrouvons des traces précoces. Par exemple, une des plus anciennes sources écrites découverte à ce jour montre la présence de calculs à la fin du IVe millénaire avant J.-C, en Mésopotamie. Ces données archéologiques se présentent sous la forme d’une tablette de compatibilité gravée dans l’argile  . On observe une grande diversité des usages et des calculs deviennent nécessaires, des méthodes se développent dans de nombreux champs pour organiser les activités quotidiennes comme dans l’agriculture, les activités marchandes, les déplacements ou encore les activités militaires mais également dans le développement des sciences et des connaissances de façon générale telles que la géométrie, l’architecture, l’astronomie, etc. Au fil du temps, les besoins d’outils et de méthodes n’ont fait que croître pour répondre à des problèmes de plus en plus complexes. Les progrès technologiques ont notamment apporté des questionnements supplémentaires et une nécessité de pousser le développement de ces méthodes.

La complexification des problèmes à résoudre implique une charge supplémentaire pour l’être humain qui atteint certaines limites : erreurs de calcul, coût en temps très important, etc. Ainsi des méthodes ont vu le jour afin de rendre les calculs plus efficaces et plus fiables. Les algorithmes sont des méthodes de calcul qui ont été particulièrement développées et sophistiquées pour permettre une assistance à la résolution de ces problèmes complexes. Ce sont des suites d’opérations à suivre pas à pas, suites d’opérations qui peuvent ensuite être automatisées notamment avec l’aide d’outils informatiques, remplaçant ainsi le travail fastidieux et moins fiable des humains.

Vérification formelle

Une des techniques utilisées est celle des méthodes dites formelles. Les méthodes formelles sont des techniques permettant une rigueur mathématique et l’utilisation de la logique afin de s’assurer de la fiabilité du résultat. Il s’agit dans un premier temps d’abstraire le problème avec un modèle mathématique ce qui permet de l’isoler et de le considérer en lui même, indépendamment d’éléments contextuels liés aux cas particuliers. Dans un second temps le problème ainsi abstrait est résolu. Il est ensuite possible, dans un dernier temps, d’appliquer la solution ainsi trouvée au problème concret.

Nous pouvons rapidement comprendre les avantages à utiliser un modèle. Cela permet de manipuler un objet purement mathématique. Il est ainsi possible de s’affranchir de la réalité qui implique de nombreuses difficultés dans le déroulement de résolutions de problèmes. En effet, le modèle permet de ne pas prendre en compte certaines spécificités relatives aux cas particuliers afin de généraliser le problème. Les algorithmes interviennent dans l’identification ou la vérification de propriétés mathématiques sur le modèle. Il est ensuite possible d’apporter la preuve mathématique que les solutions ainsi déterminées sont correctes (sur le modèle).

Cependant des méthodes mathématiques entraînent un surcoût lors des phases de développement qui sont alors plus longues. Ce défaut est néanmoins compensé par le niveau de fiabilité supérieur apporté par de telles méthodes qui peuvent rendre plus rapides les phases de validation mais qui sont surtout nécessaires dans de nombreux domaines qui ne peuvent pas se permettre une fiabilité moindre. En effet si lors d’une réunion par visioconférence la perte d’une image ne sera pas dommageable pour la qualité, la fluidité ou la compréhension de la conversation, dans des domaines tels que la sûreté nucléaire ou les systèmes embarqués il est indispensable d’avoir des algorithmes beaucoup plus fiables. Nous pouvons donc dégager deux grands axes à cette méthode. D’une part les informations importantes et nécessaires à la résolution du problème sont identifiées puis traduites en un modèle adapté. D’autre part, le problème est résolu mathématiquement dans ce modèle. Tous ces éléments appartiennent à des domaines différents des mathématiques. Le travail de cette thèse s’inscrit dans ce dernier axe, celui des méthodes mathématiques utilisées pour résoudre des problèmes sur les modèles abstraits.

Ces méthodes, dites formelles [Woo+09], permettent d’avoir des outils mathématiques à disposition, applicables à tout problème une fois abstrait, qu’il soit initialement connu ou non. Une fois une situation modélisée, la méthode est applicable indépendamment de la nature du problème et fournit une solution clés en main sur le modèle et donc des pistes privilégiées de solutions pour le problème réel, même s’il n’a pas encore été étudié spécifiquement. Nous avons choisi ici de nous intéresser à la famille d’abstractions mathématiques que sont les graphes.

Graphes

Prenons un exemple. Imaginons que nous souhaitions abstraire un réseau routier. Il est alors possible de symboliser les villes par des points et les routes par des traits. Deux points seront donc reliés par un trait si une route existe dans la réalité entre ces deux villes. Nous pouvons nous poser une question, un problème, plutôt simple pour commencer : puis-je aller de la ville A à la ville B par la route ? Ce qui revient à se demander s’il existe un réseau de routes suffisant pour relier A et B sans discontinuité. En effet, nous pourrions aisément imaginer des cas où deux villes A et B ne seraient pas reliées par des routes, si une des deux villes se trouve sur une île ou un autre continent par exemple. Ainsi sur notre modèle la question revient à savoir si en partant du point correspondant à la ville A, il est possible, en passant de trait en trait, d’aller jusqu’au point correspondant à la ville B. Ce type de modèle s’appelle un graphe. On notera qu’au sein des graphes ce que nous avons appelé des points et des traits se nomment respectivement des sommets et des arcs non orientés. La question posée revient quant à elle à se demander si A et B appartiennent à la même composante connexe de ce graphe. Ici le modèle permet de traiter le problème en excluant les données non nécessaires telles que la largeur des routes ou encore le nombre de voies.

Un des avantages majeurs de ces modélisations est, comme évoqué plus tôt, leur généralisation à des problèmes divers. Ainsi les outils qui permettent de répondre à ce type de problème permettent également de répondre à des problèmes appartenant à d’autres domaines. Prenons l’exemple du domaine des réseaux sociaux. Il est possible, à l’instar de notre exemple précédent, de modéliser les composantes d’un réseau social par des sommets et des arcs non orientés. Les sommets représenteront les personnes au lieu des villes et les arcs non orientés représenteront les relations entre des personnes au lieu des routes. Par exemple, un arc non orienté peut être considéré comme une relation « d’ami » sur Facebook, Snapchat ou encore Whatsapp, la particularité de ces réseaux sociaux étant le caractère symétrique des relations. Sur ces réseaux sociaux deux personnes doivent être « amies » pour pouvoir échanger des contenus dans les deux sens et étudier la structure des graphes peut aider à comprendre certains processus sociaux à l’œuvre comme par exemple l’étude des liens sociaux des organisations terroristes [CNM06]. Dans le cas des réseaux sociaux la question que nous nous posons pourrait être de savoir quel utilisateur du réseau social pourra potentiellement voir le contenu partagé par un autre utilisateur. Par exemple si un utilisateur A partage une photo, est-ce que l’utilisateur B pourra la voir ? Au même titre que dans l’exemple du réseau routier cette question revient à se demander si A et B appartiennent à la même composante connexe de ce graphe. Ainsi le même algorithme appliqué à cette même modélisation permettra de répondre aussi bien aux deux questions : Peut-on se rendre de la ville A à la ville B par la route ? L’utilisateur B du réseau social pourra t-il voir le contenu partagé par l’utilisateur A ? La même technique de résolution peut ainsi être appliquée à des problèmes différents.

Il est possible de complexifier ce modèle de graphe pour prendre en compte des subtilités supplémentaires en faisant non pas des arcs non orientés mais des arcs qui bénéficieront d’une orientation, ce qui revient à symboliser des relations possibles dans un seul sens plutôt que dans les deux. Ainsi dans notre exemple de réseau routier un arc allant d’un point A à un point B signifierait que la route est en sens unique, les usagers de la route pouvant se rendre de la ville A à la ville B par ce biais mais pas de la ville B à la ville A. Sur notre exemple des réseaux sociaux un arc allant d’un point A à un point B signifierait une relation asymétrique entre la personne A et la personne B. C’est le cas par exemple dans des réseaux sociaux tels que Twitter, Instagram ou TikTok où la personne A suit la personne B. La personne A reçoit alors du contenu de la part de la personne B sans que l’inverse ne soit vrai, B pouvant ne pas suivre A. On retrouve aussi ces modèles dans le fonctionnement des abonnements des plateformes telles que Twitch ou Youtube.

Ce modèle est un graphe orienté et les méthodes qui seront utilisées sur ce graphe seront les mêmes, indépendamment de la nature du problème réel modélisé, que ce soit une carte routière, un réseau social [NMD18] ou tout autre problème qui puisse être abstrait dans ce modèle.

Énergies

À l’instar de notre exemple de réseau routier nous pouvons aisément imaginer des problèmes plus complexes, impliquant davantage de variables. Prenons pour exemple le cas de la consommation énergétique d’un robot. Les différentes positions du robot, modélisées à nouveau par un graphe, sont notées A, B, C, etc. Dans ce contexte deux positions différentes du robot sont reliées par des actions et différentes actions ou séries d’actions peuvent permettre de passer de la position A à la position B (par des successions d’arcs différents). Une action pourrait être un déplacement par exemple. Il est également possible de considérer que le robot effectue une action sans changer de position. Cette action pourrait être de se recharger par exemple. L’arc reliera alors le point A à ce même point A. La question serait alors de savoir quelles actions seraient les plus à même de réaliser une tâche donnée. Il est possible de complexifier de nouveau le modèle pour répondre à cette problématique. Cela serait représenté sur le graphe par des nombres que nous associerions aux arcs et qui correspondent dans notre exemple à l’énergie de l’action symbolisée par cet arc. Bien que ces nombres soient parfois appelés « coût » ou « poids» des arcs, nous avons choisi de les appeler « énergie » des arcs pour la suite. En effet le terme d’énergie correspond mieux aux problèmes que nous étudierons dans cette thèse. Dans notre exemple de robot ces nombres représentent l’énergie utilisée par le robot pour effectuer l’action considérée ce qui peut permettre de modéliser l’autonomie de la batterie du robot mais cela pourrait également correspondre à tout autre consommation d’énergie. Ces valeurs peuvent alors être positives, l’action apporte de l’énergie au robot, ou négatives, comme dans des cas où le robot utilise de l’énergie pour effectuer une action ou que l’arc symbolise de la déperdition d’énergie comme sur une batterie inactive. Par exemple, l’arc qui se verrait attribuer l’énergie −12, 7 entre la position A et la position B indiquerait qu’il existe une action permettant de passer de la position A à la position B et qu’il faut consommer 12, 7 unités d’énergie pour l’effectuer. Une fois cette modélisation réalisée, elle permet de considérer plusieurs questions : quelles sont les actions optimales (qui consomment le moins d’énergie par exemple) pour mettre le robot dans une position donnée ou encore comment effectuer une série d’actions en conservant une énergie positive (ne pas tomber à court de batterie) ? Résoudre ce genre de problèmes devient possible dans ce modèle où nous associons des énergies aux arcs. Le modèle alors utilisé est appelé graphe orienté pondéré puisqu’il inclut les deux possibilités de complexification : l’orientation des relations entre les éléments modélisés et l’ajout d’énergie aux arcs. Le terme « pondéré » est ici employé pour des raisons historiques. En effet, nous avons vu que le terme « poids » est une autre appellation possible pour l’énergie associée à un arc. Ces graphes peuvent servir à répondre à des problèmes tels que ceux posés aux robots comme dans notre exemple mais ne s’y limitent pas. Ils peuvent également s’appliquer à de nombreux problèmes tels que des problèmes d’organisations de réseau de télécommunication ou encore a des problèmes de gestions de stock. L’abstraction mathématique constitue ainsi un moyen d’étudier des problèmes potentiellement inconnus uniquement à la condition qu’ils puissent être modélisés par un objet mathématique connu, ce qui permet de ne pas devoir commencer l’étude d’un tel nouveau problème en créant des méthodes et outils  spécifiques à partir de rien. Lorsque des méthodes pour résoudre ce nouveau problème sur le modèle existent, seule la modélisation du problème réel et l’application de la solution à ce problème sont à faire.

Table des matières

Introduction
1 Introduction
1.1 Motivations générales
1.1.1 Vérification formelle
1.1.2 Graphes
1.1.3 Énergies
1.1.4 Paramètres
1.2 Définitions
1.2.1 Graphes orientés à énergie paramétrée
1.2.2 Machine à compteurs
1.2.3 Problèmes
1.3 État de l’art
1.3.1 Plus courts chemins
1.3.2 Problèmes d’accessibilité paramétrée en dimension 1
1.3.3 Accessibilité avec contraintes sur l’énergie dans les graphes non paramétrés
1.3.4 Problèmes multi-dimensionnels
1.4 Contributions et plan
2 Arbres des plus courts chemins
2.1 Introduction
2.2 Définitions
2.2.1 Graphes paramétrés
2.2.2 Arbres sur des graphes paramétrés
2.2.3 Contraintes et zones associées aux arbres
2.3 Présentation de notre algorithme de calcul des énergies minimales
2.4 Présentation formelle de notre algorithme
2.4.1 L’algorithme
2.4.2 Preuve de l’algorithme
2.4.3 Complexité
2.5 Cas avec des paramètres à valeurs entières
2.6 Conclusion
3 Accessibilité multi-dimensionnelle à énergie paramétrée bornée
3.1 Introduction
3.2 Problème LU total avec paramètres à valeurs entières
3.3 Problème LU total avec paramètres à valeurs rationnelles
3.4 Conclusion
4 Jeux de parité à énergie paramétrée
4.1 Introduction
4.2 Définitions
4.3 Cas à un joueur
4.3.1 Définitions
4.3.2 Transformation d’un chemin en schéma d’itération
4.3.3 Transformation d’un chemin en schéma multiple d’itération
4.3.4 Chemins gagnants
4.3.5 Complexité
4.4 Cas à deux joueurs
4.4.1 Définitions
4.4.2 Stratégies particulières
4.4.3 Complexité
4.5 Conclusion
5 Conclusion
Conclusion

Lire le rapport complet