Guidage d’un solveur de contraintes dédié à la planification automatisée de véhicules

Complexité et problèmes proches de la littérature

Exemple et méthode empirique

Le problème décrit ci-avant paraˆıt simple au premier abord. Il est pourtant complexe, et la Méthode d’Elaboration d’une Décision Opérationnelle ´ (MEDO) enseignée en formation militaire n’est d’aucun secours pour l’officier en charge de l’établissement des ordres. Cette méthode est un processus exhaustif de réflexion logique préalable aux décisions, mais n’offre en aucun cas un moyen de résolution de problèmes d’optimisation. En observant l’exemple simple de la figure 1.8, pour lequel quatre solutions possibles (ou non, en fonction des contraintes) sont proposées, on s’aper¸coit qu’il peut ˆetre difficile de juger de la qualité d’une solution en visionnant simplement un graphe ou une carte. Cette difficulté devient plus grande encore si l’on tient compte de contraintes additives qui vont influencer la vitesse du véhicule (par exemple une contrainte de consommation), et par conséquent faire que le chemin le plus court (en distance) ne sera pas forcément le plus rapide. Dans notre exemple, parmi les quatre exemples proposés, la solution (b) semble visuellement la meilleure en termes de distance. Cependant, peut-ˆetre que le nœud précédant G dans le chemin est situé en haut d’une colline, ce qui va augmenter la consommation du véhicule. Si en complément les réserves du véhicule sont très limitées, ce dernier devra ainsi réduire sa vitesse sur le reste de l’itinéraire afin de ne pas tomber en panne. Le temps de la mission sera peut-ˆetre au final plus important que s’il avait pris un autre itinéraire (par exemple le (c)). Nous n’avons représenté que quatre solutions dans cet exemple, mais il en existe bien entendu un grand nombre d’autres, ce nombre croissant rapidement avec la taille du problème. Pour un opérationnel chargé d’établir rapidement de nouveaux ordres en cours de mission, cet exercice représente donc une difficulté majeure. Ci-dessous, nous montrons que le problème étudié peut ˆetre rapproché de deux problèmes de la littérature connus pour leur complexité. Ces problèmes sont NP-difficiles (voir section 2.1). En d’autres termes, les temps de résolution croissent potentiellement de manière exponentielle avec la taille du problème. 

Couvrir un ensemble de nœuds dans un graphe

Les problèmes de couverture de nœuds dans un graphe sont des « classiques » en théorie des graphes, qui n’ont pas tous la mˆeme complexité. 15 Figure 1.8 – Exemples de solutions pour un problème de planification avec quatre objectifs. Les nœuds hachurés sont les objectifs ; les nœuds S et G sont les points de départ et d’arrivée respectivement. Figure 1.9 – Exemple d’arbre couvrant de longueur minimale. 

L’arbre couvrant de poids minimal

Ce problème fait partie des problèmes enseignés très tˆot aux étudiants qui sont initiés à la théorie des graphes. Considérant un graphe G = (V, E) o`u V et E représentent respectivement l’ensemble des nœuds et l’ensemble des arˆetes de G, il consiste à trouver un arbre couvrant de V dans G (c’est-à-dire un graphe partiel connexe G′ = (V, E′ ) de G pour lequel le nombre de sommets |V | = |E′ |+ 1, ce qui exclut tout cycle) et dont le poids est minimal (le poids de l’arbre étant égal à la somme des poids des arˆetes qu’il possède). La figure 1.9 illustre par un exemple la solution à un problème d’arbre couvrant minimal. Ce problème se résout en temps polynˆomial, et possède une complexité en pratique de Θ(|E| log |V |). Cependant, il ne s’applique pas à la définition du problème de nos travaux car, dans notre cas, il ne s’agit pas de couvrir l’ensemble des nœuds du graphe, mais un sous-ensemble d’entre eux seulement. 16 Figure 1.10 – Exemples d’arbre de Steiner de longueur minimale. Les nœuds hachurés représentent les nœuds Vm à couvrir obligatoirement ; les autres nœuds {V \ Vm} désignent ceux pouvant ˆetre empruntés de manière optionnelle. (a) Problème avec quatre nœuds obligatoires. (b) Problème avec cinq nœuds obligatoires. 1.3.2.2 L’arbre de Steiner Le problème de l’arbre de Steiner minimal dans un graphe (en référence à Jakob Steiner, mathématicien suisse du XIXe siècle) est proche de la définition du problème de l’arbre couvrant de poids minimal. Il s’agit de trouver, pour un graphe pondéré non orienté G = (V, E) et un ensemble de nœuds Vm ⊆ V , un arbre de poids minimal couvrant de Vm dans G (c’est-à-dire un sous-graphe partiel connexe G′ = (V ′ , E′ ) de G o`u Vm ⊆ V ′ ⊆ V et |V ′ | = |E′ | + 1). La figure 1.10 donne deux exemples d’arbre de Steiner minimal. Ce problème est plus complexe que le précédent. En effet, cette définition amène à évaluer un bien plus grand nombre de solutions, car il faut considérer les arbres pour toutes les combinaisons de V ′ possibles, et non plus pour un ensemble V de taille fixe. Il a été établi que sa complexité est NP-difficile, et il figure de ce fait dans la liste du Compendium NP [Gare 79, Cres 05] sous le nom de Minimum Steiner Tree. Celui-ci est à bien distinguer du problème de couverture minimale de nœuds appelé Minimum Vertex Cover, un problème de partitionnement qui consiste à trouver le sous-ensemble V ′ de V de cardinalité minimale tel que, pour toute arˆete e = (u, v) ∈ E, au moins u ou v appartient à V ′ . En faisant abstraction des contraintes de capacité, on peut donc ramener le problème présenté à la section 1.2 en une recherche d’arbre de Steiner, o`u G est le graphe de la zone d’opérations et Vm contient la liste des objectifs assignés au véhicule, ainsi que le point initial et le point final. A partir de l’arbre issu de la résolution du problème, il est possible de reconstruire un chemin partant du point initial au point final. Dans l’exemple de la figure 1.10.a, en prenant le nœud A comme point initial et H comme point final, nous pouvons reconstruire le chemin suivant : [A, C, F, E, F, G, H]. Dans cet exemple, le nœud F a trois voisins. En développant le chemin depuis A, il faut donc veiller à visiter E avant d’emprunter le chemin allant de E à H. Il est utile de noter que si un nœud de l’arbre possède plus de trois voisins (ou si le point initial ou final a au moins trois voisins), plusieurs combinaisons dans l’ordre de visite des nœuds sont possibles. On obtient alors plusieurs chemins (de taille équivalente) en solution de notre problème. A noter qu’il peut ˆetre nécessaire de faire quelques modifications dans la définition du problème de l’arbre de Steiner si l’on ne souhaite pas que le véhicule puisse repasser par le point initial ou final. Dans l’exemple de la figure 1.10.b, si A est le point initial et G le point final, aucun chemin ne peut ˆetre trouvé. Il faut donc adapter la définition initiale du problème, 17 établie par le Compendium NP de la manière suivante : – INSTANCE : un graphe G = (V, E), une métrique donnée par des poids s : E → N associés aux arˆetes et un ensemble S ⊆ V de nœuds requis ; – SOLUTION : un arbre de Steiner, c’est-à-dire un sous-arbre G′ = (V ′ , E′ ) de G avec V ′ ⊇ S ; – MESURE : la somme des poids dans le sous-arbre. en ajoutant la contrainte suivante : |E′ s | = |E′ g | = 1 avec Es = {e = (u, v) ∈ E′ | u = vs ∨v = vs} et Eg = {e = (u, v) ∈ E′ | u = vg ∨ v = vg}, o`u vs est la position initiale du véhicule et vg est la position finale.

Le problème du voyageur de commerce (TSP)

Ce problème, que nous désignerons par l’acronyme TSP (pour Traveling Salesman Problem en anglais) dans la suite du document, est peut-ˆetre le plus connu parmi ceux de la liste du Compendium NP. C’est un cas d’étude très utilisé dans l’enseignement de la notion de complexité en théorie des graphes, car il possède un algorithme de complexité factorielle très simple à expliciter. Le but est de trouver, pour un ensemble C de « villes », un tour de C de longueur minimale, c’est-à-dire un circuit passant une et une seule fois par chaque ville de C (aussi appelé circuit hamiltonien). La longueur du tour est définie comme la somme des distances entre deux villes consécutives, la matrice des distances étant fournie en entrée du problème. Comme dans le cas précédent, en ne considérant pas les contraintes de capacité, il est possible de rapprocher le problème décrit en 1.2 d’un problème de voyageur de commerce. En effet, il s’agit de trouver non pas un circuit, mais un chemin hamiltonien de longueur minimale, dont les extrémités sont le point initial et le point final. Voici la définition du problème du voyageur de commerce, donnée dans le Compendium NP, répertorié sous le nom de Minimum Traveling Salesperson [Cres 05] : – INSTANCE : un ensemble C de m villes, les distances d(ci , cj ) ∈ N pour chaque couple de villes ci , cj ∈ C ; – SOLUTION : un tour de C, c’est-à-dire une permutation π : [1..m] → [1..m] ; – MESURE : la longueur du tour, c’est-à-dire d({cπ(m) , cπ(1)}) + Pm i=1 d({cπ(i) , cπ(i+1)}).