Applications spatiales et optimisation combinatoire

Initialisées avec le lancement du satellite Spoutnik en 1957, les missions spatiales furent d’abord développées dans un but d’exploration de l’Univers et pour le rayonnement scientifique et militaire des principales puissances mondiales de l’après-guerre. L’étude de la Terre et de l’Espace fait aujourd’hui encore l’objet de nombreuses missions scientifiques par l’envoi de satellites, sondes ou vols habités. Parallèlement à cela, les progrès technologiques rapides et l’apparition de besoins nouveaux dans les domaines des télécommunications et de l’observation de la Terre ont conduit, essentiellement à partir des années 80, au développement d’un autre type de missions dont le but principal est de proposer des services (communication de différents types d’informations sur toute la planète, localisation pour la navigation, surveillance de la Terre, cartographie, etc.).

Dans tous les cas, ces missions spatiales, à vocation scientifique, militaire ou commerciale, mettent en jeu des systèmes d’une grande complexité technologique et nécessitent toujours d’importants investissements en termes de moyens, d’études scientifiques et de temps de travail. Ce sont ainsi des projets de grande envergure, qui posent des problèmes d’optimisation des décisions dans de nombreux domaines (pour la définition du système, la mise et le maintien à poste, la planification des opérations de la mission). En particulier, des problèmes combinatoires complexes relatifs à la gestion des ressources du système – telles que l’énergie, la mémoire, les antennes de communication, divers instruments de mesure – émergent lors des phases de planification d’une mission spatiale, avec un niveau croissant d’exigence sur la fiabilité et l’optimisation des résultats. Ces problèmes présentent des caractéristiques communes en termes de problématiques et de contraintes, liées en particulier à une forte limitation des ressources disponibles et du temps et à la dynamique des systèmes satellitaires. De plus en plus, les approches de résolution de ces problèmes font appel aux méthodes et techniques issues des domaines de la Recherche Opérationnelle et de l’Intelligence Artificielle, avec, en général, le développement d’heuristiques pour fournir des solutions.

Applications spatiales et optimisation combinatoire

Problèmes d’optimisation combinatoire dans les applications spatiales

Les systèmes spatiaux, de leur conception à leur maintenance, impliquent toujours des investissements lourds en termes de moyens, de compétences scientifiques et de temps de travail. Les missions spatiales utilisant ces systèmes doivent satisfaire des critères de performance et de qualité de service de plus en plus élevés. De la gestion de ces systèmes spatiaux découlent des problèmes d’optimisation de différentes natures. D’une part, on a des problèmes qui sont fortement liés à une étude complexe de la mécanique spatiale et des technologies employées, où les domaines de variables sont principalement continus (par exemple, recherche d’une géométrie optimale d’un système spatial, étude du maintien à poste d’une constellation à moindre coût [Brochet 99]). D’autre part, on a des problèmes qui concernent plus précisément la planification des missions d’un point de vue de la gestion des ressources et qui font principalement intervenir des variables à domaines discrets. C’est ce deuxième type de problèmes, fortement combinatoires, auquel nous nous intéressons dans ce travail. Après une présentation de problèmes classiques d’optimisation combinatoire, ce premier chapitre passe en revue les méthodes de modélisation et de résolution (issues le plus souvent des communautés de la Recherche Opérationnelle et de l’Intelligence Artificielle) proposées pour traiter les problèmes d’optimisation combinatoire émergeant dans le cadre de la planification de missions spatiales.

Problèmes classiques d’optimisation combinatoire

Un problème d’optimisation consiste à chercher une instanciation d’un ensemble de variables soumises à des contraintes, de façon à maximiser ou minimiser un critère. Lorsque les domaines de valeurs des variables sont discrets, on parle alors de problèmes d’optimisation combinatoire.

Nous présentons rapidement ici quatre problèmes classiques d’optimisation combinatoire : le problème du sac-à-dos, le problème d’affectation, le problème du voyageur de commerce et le problème d’ordonnancement.

Problème du sac-à-dos

Le « problème du sac-à-dos » est un problème de sélection qui consiste à maximiser un critère de qualité sous une contrainte linéaire de capacité de ressource. Il doit son nom à l’analogie qui peut être faite avec le problème qui se pose au randonneur au moment de remplir son sacà-dos : il lui faut choisir les objets à emporter de façon à avoir un sac le plus « utile » possible, tout en respectant son volume. Plus formellement, on peut le décrire de la façon suivante. Soit un ensemble de n éléments et une ressource disponible en quantité limitée, b. Pour j = 1 à n, on note pj le profit associé à la sélection de l’élément j et on note aj la quantité de ressource que nécessite l’élément j, s’il est sélectionné. Les coefficients pj et aj prennent des valeurs positives pour tout j = 1 à n. Le problème du sac-à-dos consiste à choisir un sous-ensemble des n éléments qui maximise le profit total obtenu, en respectant la quantité de ressource disponible [Nemhauser & Wolsey 88].

Dans le cas où l’on a plusieurs contraintes de ce type (par exemple, le randonneur peut considérer non seulement un volume maximal, mais également un poids maximal, que son sac peut supporter), on parle de problème de sac-à-dos « multidimensionnel ». Le problème du sac-à-dos a fait l’objet de différents travaux proposant des méthodes exactes de résolution. Un état de l’art détaillé de ces approches est présenté dans [Martello et al. 00]. Les algorithmes proposés relèvent de trois principaux types de méthodes. Premièrement, des algorithmes de type séparation et évaluation  ont été proposés dans les années 70, permettant de traiter efficacement des instances de petite taille. Ces performances ont par la suite été améliorées par l’adjonction de contraintes supplémentaires pour renforcer les bornes dans l’arbre de recherche. Deuxièmement, des algorithmes se basant sur l’identification d’une variable critique et d’un sous-ensemble associé de variables, sur lequel on applique une recherche arborescente tronquée, ont permis, à partir des années 80, d’augmenter la taille des instances pouvant être résolues (jusqu’à n = 100000). Troisièmement, des algorithmes efficaces de programmation dynamique ont été proposés. En particulier, dans [Martello et al. 99], la programmation dynamique est combinée avec l’identification d’une variable critique et l’utilisation de techniques de renforcement des bornes. Concernant le problème de sac-à-dos multidimensionnel, nous renvoyons à la lecture de [Oliva et al. 01] qui détaille les différentes approches existantes.

Problème du voyageur de commerce 

Le « problème du voyageur de commerce », ou TSP (pour Traveling Salesman Problem), est le suivant : un représentant de commerce ayant n villes à visiter souhaite établir une tournée qui lui permette de passer exactement une fois par chaque ville et de revenir à son point de départ pour un moindre coût, c’est-à-dire en parcourant la plus petite distance possible. C’est un des problèmes les plus anciennement et largement étudiés en optimisation combinatoire. Ses applications sont nombreuses. Par exemple, des problèmes de séquencement de processus de fabrication ou d’optimisation de parcours en robotique peuvent s’exprimer directement sous forme d’un TSP et certains problèmes, comme les problèmes de transport, sont plus complexes que le TSP mais présentent une structure sous-jacente de type TSP.

Soit G = (X,U), un graphe dans lequel l’ensemble X des sommets représente les villes à visiter, ainsi que la ville de départ de la tournée, et U, l’ensemble des arcs de G, représente les parcours possibles entre les villes. À tout arc (i,j) ∈ U, on associe la distance de parcours di,j de la ville i à la ville j. La longueur d’un chemin dans G est la somme des distances associées aux arcs de ce chemin. Le TSP se ramène alors à la recherche d’un circuit hamiltonien (i.e., un chemin fermé passant exactement une fois par chacun des sommets du graphe) de longueur minimale dans G. Dans le cas où il existe certains arcs (i,j) ∈ U pour lesquels di,j ≠ dj,i, on parle de TSP asymétrique [Nemhauser & Wolsey 88].

Table des matières

Introduction
I Applications spatiales et optimisation combinatoire
1 Problèmes d’optimisation combinatoire dans les applications spatiales
1.1 Introduction
1.2 Problèmes classiques d’optimisation combinatoire
1.2.1 Problème du sac-à-dos
1.2.2 Problème d’affectation
1.2.3 Problème du voyageur de commerce
1.2.4 Problème d’ordonnancement
1.3 Problèmes d’optimisation combinatoire issus d’applications spatiales
1.3.1 Spécificité des problèmes posés
1.3.2 Modélisation et résolution : revue des méthodes utilisées
1.3.2.1 Heuristiques et algorithmes dédiés
1.3.2.2 Approches par contraintes, méthodes d’Intelligence Artificielle
1.3.2.3 Méthodes exactes
1.3.2.4 Approches par simulation : utilisation des Réseaux de Petri
1.4 Conclusion
2 Techniques de résolution retenues
2.1 Introduction
2.2 Propagation de contraintes
2.2.1 Propagation de contraintes temporelles
2.2.1.1 Problèmes temporels simples
2.2.1.2 Problèmes temporels généraux
2.2.2 Propagation de contraintes de partage de ressources
2.2.2.1 Opérations locales, opérations globales
2.2.2.2 Raisonnement énergétique
2.3 Programmation linéaire
2.3.1 Définitions
2.3.2 Résolution des programmes linéaires
2.3.2.1 Principaux algorithmes
2.3.2.2 Méthode du simplexe
2.3.3 Programmation linéaire en nombres entiers
2.4 Génération de colonnes pour les problèmes de grande dimension
2.4.1 Principe de résolution par génération de colonnes
2.4.2 Convergence de la méthode
2.4.3 Décomposition de Dantzig-Wolfe (1960)
2.4.4 Résolution de PLNE par génération de colonnes
2.4.4.1 Décomposition des PLNE
2.4.4.2 Algorithme générateur
2.4.4.3 Recherche de solutions entières : “branch and price”
2.5 Conclusion
II Étude de trois projets spatiaux : analyse et modélisation des problèmes de planification
3 Skybridge : une constellation basse altitude pour la communication
3.1 Présentation du projet Skybridge
3.1.1 Constellations basse altitude de télécommunication
3.1.2 Architecture de la constellation Skybridge
3.2 Problématique
3.3 Analyse du problème
3.4 Modélisation du problème
3.5 Travaux connexes
3.6 Bilan de l’étude sur Skybridge
4 Netlander : projet d’exploration de la planète MARS
4.1 Présentation de la mission
4.2 Problématique
4.3 Analyse du problème
4.3.1 Revue de la littérature
4.3.2 Proposition d’une décomposition
4.3.3 Sous-problème de planification des communications orbiteur/sondes
4.3.3.1 Analyse du problème
4.3.3.2 Modélisation
4.3.4 Sous-problème de planification des expériences
4.3.4.1 Analyse du problème
4.3.4.2 Modélisation
4.4 Conclusion
5 Pléiades : Satellites d’observation de la Terre
5.1 Présentation du projet
5.2 Problématique
5.3 Analyse du problème
5.3.1 Revue de la littérature
5.3.2 Modélisation
5.4 Étude de la complexité du problème Pléiades .
5.5 Conclusion
III Résolution de problèmes de planification dans les projets Netlander et Pléiades
Conclusion

Lire le rapport complet