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

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)}).

Table des matières

Introduction
1 Navigation de véhicules terrestres en environnement hostile
1.1 L’enjeu de la navigation dans le domaine militaire
1.1.1 L’émergence des armées modernes
1.1.2 La navigation dans l’Armée de Terre
1.1.2.1 Systèmes de commandement
1.1.2.2 Véhicules terrestres
1.1.2.3 Drones aériens
1.1.2.4 Robots du combattant
1.1.2.5 ORTAC, un outil de préparation de mission militaire
1.1.3 Une capacité clé : l’adaptation à l’environnement
1.2 Description du problème
1.2.1 Présentation informelle
1.2.2 Formalisation générique du problème
1.3 Complexité et problèmes proches de la littérature
1.3.1 Exemple et méthode empirique
1.3.2 Couvrir un ensemble de nœuds dans un graphe
1.3.2.1 L’arbre couvrant de poids minimal
1.3.2.2 L’arbre de Steiner
1.3.2.3 Le problème du voyageur de commerce (TSP)
1.3.3 Minimiser un plus court chemin sous contraintes
1.4 Modélisation du problème
1.4.1 Hypothèses de départ
1.4.2 Modélisation du problème et de la fonction de coˆut
1.4.3 Modélisation d’un chemin
1.4.4 Expression de la fonction de coˆut
1.4.5 Contraintes de capacité
1.5 Conclusion
2 Etat de l’art des méthodes de résolution pour la planification d’itinéraires
2.1 Classes de complexité .
2.2 Algorithmes de plus court chemin
2.2.1 Algorithmes de base
2.2.2 Les algorithmes avec heuristique
2.2.3 L’algorithme A⋆
2.2.3.1 Algorithmes A⋆ à caractère anytime
2.2.3.2 Algorithmes A⋆ avec restriction d’espace mémoire
2.2.3.3 Algorithmes A⋆ pour environnements dynamiques ou incertains
2.2.4 Algorithmes pour le problème de plus court chemin sous contraintes
2.2.4.1 Approches géométriques
2.2.4.2 Approches algébriques
2.2.4.3 Approches pour le problème généralisé
2.3 La Programmation Linéaire en Nombres Entiers (PLNE)
2.3.1 La Programmation Linéaire (PL)
2.3.2 Présentation générale de la PLNE
2.3.3 Les coupes de Gomory
2.3.4 La méthode par Séparation-Evaluation
2.4 La programmation logique avec contraintes (PLC)
2.4.1 Historique et présentation générale
2.4.2 PLC dans les domaines finis
2.4.3 Résolution d’un problème de satisfaction de contraintes
2.4.4 La propagation de contraintes
2.4.5 L’énumération
2.4.6 Le solveur ORTAC
2.4.6.1 Présentation .
2.4.6.2 Stratégie de résolution
2.5 Métaheuristiques pour l’optimisation combinatoire
2.5.1 Présentation
2.5.2 Méthodes de construction d’une solution
2.5.3 Méthodes de recherche locale
2.5.4 Métaheuristiques à solution courante unique
2.5.4.1 La méthode du recuit simulé
2.5.4.2 La recherche tabou
2.5.5 Métaheuristiques à base de population
2.5.5.1 Les algorithmes évolutionnaires
2.5.5.2 Les algorithmes de colonies de fourmis
2.5.5.3 L’optimisation par essaim particulaire
3 Une méthode de sonde à base de métaheuristiques
3.1 Un guidage efficace pour une résolution rapide
3.1.1 Rappel des objectifs
3.1.2 Bases techniques des travaux
3.1.3 Précisions sur la méthode de sonde
3.1.4 Description de la nouvelle approche
3.1.5 Justification et originalité de l’approche
3.2 Les colonies de fourmis pour la couverture des points obligatoires
3.2.1 Description de l’algorithme
3.2.2 Implémentation et paramétrage
3.2.3 Méthodologie d’expérimentation
3.2.4 Résultats et discussion
3.2.4.1 Comparaison des méthodes de construction
3.2.4.2 Comparaison de notre approche avec des approches concurrentes
3.3 Intégration des colonies de fourmis dans la résolution globale
3.3.1 Méthodologie d’analyse et d’expérimentation
3.3.2 Résultats et discussion
3.3.3 Conclusion
3.4 Aller plus loin dans le guidage
3.4.1 Limites du guidage actuel
3.4.2 Intégration du LARAC dans la méthode de résolution partielle
3.4.3 Dynamiser la recherche ACO
3.4.4 Cadre d’expérimentation
3.4.5 Résultats et discussion
3.4.6 Conclusion
4 Application de l’approche à des problèmes de planification spécifiques
4.1 Navigation sous contraintes d’énergie
4.1.1 Présentation du problème
4.1.1.1 Motivation
4.1.1.2 Formalisation du problème d’optimisation
4.1.1.3 Contraintes d’énergie
4.1.1.4 Paramètres
4.1.2 Résolution du problème
4.1.2.1 Modélisation en Programmation par Contraintes
4.1.2.2 Amélioration du modèle logique de chemins
4.1.2.3 Résolution
4.1.2.4 Guidage du solveur de contraintes
4.1.2.5 Implémentation du solveur partiel
4.1.3 Résultats
4.1.4 Conclusion
4.2 Gestion des communications radio pour véhicules en mission
4.2.1 Présentation du problème
4.2.2 Modèle de liaisons radio
4.2.3 Résolution
4.2.4 Solveur partiel
4.2.5 Solveur global
4.2.6 Résultats
4.2.7 Discussion
4.2.8 Conclusion
4.3 Exploration de zones d’intérˆet en robotique mobile
4.3.1 Présentation du problème
4.3.2 Adaptation de l’approche
4.3.2.1 Modèle logique
4.3.2.2 Approche de résolution partielle
4.3.2.3 Guidage avancé du solveur
4.3.3 Expérimentation et résultats
4.3.4 Conclusion
5 Extensions du modèle de navigation
5.1 Modèle de flots multiples
5.1.1 Nouvelle modélisation
5.1.2 Propagateur pour flots multiples
5.1.3 Résultats et discussion
5.2 Planification robuste
5.2.1 Présentation
5.2.2 Modélisation avec système de flots unique
5.2.2.1 Modélisation de l’optimisation pire temps
5.2.2.2 Modélisation de l’optimisation temps total
5.2.3 Modélisation avec système de flots double
5.2.4 Méthode de guidage
5.2.4.1 Résultats et discussion
5.3 Vers une méthode de sonde dynamique ?
5.3.1 Objectifs
5.3.2 Description et implémentation
5.3.3 Ne pas réévaluer l’espace déjà visité
5.3.4 Discussion
Conclusion des travaux
Perspectives futures
Annexes
Evaluation du solveur de contraintes
Evaluation de l’approche LARAC-ACO
Détails de l’expérimentation pour la gestion d’énergie
Détails de l’expérimentation pour la gestion des communications radio
Références bibliographiques
Publications

projet fin d'etudeTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *