Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes
Choisir la langue : FR | EN

70documents trouvés

18586
06/12/2018

Planification et ordonnancement de projets sous contraintes de ressources complexes

P.MORIN

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 6 Décembre 2018, 140p., Président: J.C.BILLAUT, Rapporteurs: S.DEMASSEY, N.TRAUTMANN, Examinateurs: C.BRIAND, F.CLAUTIAUX, Directeurs de thèse: A.HAIT, C.ARTIGUES , N° 18586

Lien : https://hal.laas.fr/tel-02053199

Diffusable

Plus d'informations

Abstract

The project structure arises in many fields of industry and services. It consists in performing a set of activities that may be linked by precedence relations, and use resources whose capacity is limited. The objective is to minimize a criterion usually linked to the duration or the cost of the project. Most of project scheduling problems in the literature assume that the same time scale should be used to determine activity start and completion dates and check resource constraints at each time. However, although it is often required in practice to build a precise schedule specifying the execution range of each activity, the resource usage can be evaluated on an aggregated basis, like worker shifts. In this thesis, a new model that enables the integration of these two time scales is presented in order to define the periodically aggregated resource-constrained project scheduling problem (PARCPSP). This problem is studied within the framework of complexity theory and several structural properties are established, highlighting major differences with the standard resource-constrained project scheduling problem (RCPSP). These properties allow deriving exact formulations based on integer linear programming, whose linear relaxations are compared. Moreover, several heuristics, such as schedule generations schemes, or an approached method based on a multi time scale iterative process, are proposed. Experimental results show the interest of these different methods and point out the intractability of the problem.

Résumé

La structure de projet se retrouve dans de nombreux contextes de l’industrie et des services. Il s’agit de réaliser un ensemble d’activités pouvant être connectées par des liens logiques de séquence (antériorité), en faisant appel à des ressources disponibles en quantité limitée. L’objectif est la minimisation d’un critère généralement lié à la durée ou au coût du projet. La plupart des problèmes d’ordonnancement de projet dans la littérature considèrent une unité de temps commune pour la détermination des dates d’exécution des activités et pour l’évaluation instantanée du respect des capacités des ressources qu’elles utilisent. Or, s’il est souvent nécessaire en pratique d’obtenir un calendrier détaillé des plages d’exécution des activités, l’utilisation des ressources peut être évaluée sur un horizon plus agrégé, comme par exemple les quarts de travail des employés. Dans cette thèse, un nouveau modèle intégrant ces deux échelles de temps est présenté afin de définir le problème d’ordonnancement de projet avec agrégation périodique des contraintes de ressources (PARCPSP). Ce problème est étudié du point de vue de la théorie de la complexité et des propriétés structurelles sont établies, mettant notamment en évidence des différences majeures avec le problème classique d’ordonnancement de projet sous contraintes de ressources (RCPSP). De ces propriétés sont dérivées des formulations exactes basées sur la programmation linéaire en nombres entiers, comparées en termes de qualité de la relaxation linéaire. Par ailleurs, plusieurs heuristiques, telles que des algorithmes de liste, ou une méthode approchée basée sur une résolution itérative qui exploite différentes échelles de temps, sont proposées. Les résultats expérimentaux montrent l’intérêt de ces différentes méthodes et illustrent la difficulté du problème.

Mots-Clés / Keywords
Planification; Ordonnancement; Projet; Optimisation combinatoire; Programmation linéaire en nombres entiers; Planning; Scheduling; Project; Combinatorial optimization; Integer linear programming;

146755
18414
03/12/2018

Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique

I.HAMAZ

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 3 Décembre 2018, 148p., Président: A.ROSSI, Rapporteurs: P.CHRETIENNE, M.POSS, Examinateurs: C.ARTIGUES, Directeurs de thèse: L.HOUSSIN, S.CAFIERI , N° 18414

Lien : https://hal.laas.fr/tel-01975512

Diffusable

Plus d'informations

Abstract

Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by ("the" a effacer) uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.

Résumé

Plusieurs problèmes d’ordonnancement cyclique ont été étudiés dans la littérature. Cependant, la plupart de ces travaux considèrent que les paramètres sont connus avec certitude et ne prennent pas en compte les différents aléas qui peuvent survenir. Par ailleurs, un ordonnancement optimal pour un problème déterministe peut très vite devenir le pire ordonnancement en présence d’incertitude. Parmi les incertitudes que nous pouvons rencontrer dans les problèmes d’ordonnancement, la variation des durées des tâches par rapport au valeurs estimées, pannes des machines, incorporation de nouvelles tâches qui ne sont pas considérées au départ, etc. Dans cette thèse, nous étudions des problèmes d’ordonnancement cyclique où les durées des tâches sont affectées par des incertitudes. Ces dernières sont décrites par un ensemble d’incertitude où les durées des tâches sont supposées appartenir à des intervalles et le nombre de déviations par rapport aux valeurs nominales est contrôlé par un paramètre appelé budget d’incertitude. Nous étudions deux problèmes en particulier. Le premier est le problème d’ordonnancement cyclique de base (BCSP). Nous formulons celui-ci comme un problème d’optimisation robuste bi-niveau et, à partir des propriétés de cette formulation, nous proposons différents algorithmes pour le résoudre. Le deuxième problème considéré est le problème du jobshop cyclique. De manière similaire au BSCP, nous proposons une formulation en termes de problème d’optimisation bi-niveau et, en exploitant les algorithmes développés pour le problème d’ordonnancement cyclique de base, nous développons un algorithme de Branch-and-Bound pour le résoudre. Afin d’évaluer l’efficacité de notre méthode nous l’avons comparé à des méthodes de décomposition qui existent dans la littérature pour ce type de problèmes. Enfin, nous avons étudié une version du problème du jobshop cyclique où les durées des tâches prennent des valeurs dans des intervalles d’une manière uniforme et dont l’objectif est de minimiser la valeur moyenne du temps de cycle. Pour résoudre ce problème nous avons adopté un algorithme de Branch-and-Bound où chaque sous-problème de l’arbre de recherche consiste à calculer le volume d’un polytope. Enfin, pour montrer l’efficacité de chacune de ses méthodes, des résultats numériques sont présentés.

Mots-Clés / Keywords
Ordonnancement cyclique; Optimisation robuste; Optimisation combinatoire; Cyclic scheduling; Robust optimization; Combinatorial optimization;

145533
18424
31/10/2018

Stabilité de Lyapunov de systèmes couplés impliquant une équation de transport

M.SAFI

MAC

Doctorat : ISAE de Toulouse, 31 Octobre 2018, 103p., Président: S.TARBOURIECH, Rapporteurs: F.MAZENC, , Examinateurs: M.DI LORETO, F.DI MEGLIO, Directeurs de thèse: L.BAUDOUIN, A.SEURET , N° 18424

Lien : https://hal.laas.fr/tel-01975119

Diffusable

Plus d'informations

Abstract

This thesis in control theory aims at proposing a novel approach for the stability study of an infinite dimensional system where an ordinary differential equation is coupled to a transport equation through boundary terms. The idea is to exploit recent works on delay systems to quantify the stability of a system coupling a partial differential equations to ordinary differential equations. These works rely on Legendre’s polynomials and Bessel’s inequality to construct a novel approach of stability by the Lyapunov method and the use of linear matrix inequalities. Legendre’s polynomials allow construct a new structure of Lyapunov functional based partly on a polynomial approximation of the state of the transport equation (which is of infinite dimension). The manuscript is divided into several stages. After the presentation of a simple model coupling ordinary differential equations with one transport equation, the approximation of the infinite dimensional state using projection on Legendre polynomials is described. The Lyapunov method is then developed and it requires the production of stability conditions taking the shape of linear matrix inequalities. These conditions allow the production of numerical tests performed on academic examples. More difficult cases are discussed throughout the document, from a single equation of transport to several equations with different speeds, taking into account a term of coupling between them via a potential or the boundary of the domain. Finally, since such a coupling of a finite dimensional system with a transport equation can be an alternative description of a delay system, a study of the stability of the latter is developed using different models of the coupled system, in order to reduce the complexity of the stability conditions given in the form of matrix inequalities.

Résumé

Les travaux développés dans cette thèse concernent la théorie du contrôle ont pour objectif de proposer une nouvelle approche pour l’étude de stabilité d’un système de dimension infinie où une équation différentielle ordinaire est couplée à une équation de transport par les termes de bord du domaine spatial. L’idée est d’exploiter des travaux récents effectués dans le cadre des systèmes à retard pour quantifier la stabilité d’un système couplant une équation aux dérivées partielles à des équations différentielles. Ces travaux s’appuient sur les polynômes de Legendre et l’inégalité de Bessel, pour construire une approche de la stabilité par la méthode de Lyapunov et l’utilisation d’inégalités matricielles linéaires. Les polynômes de Legendre servent à la construction d’une fonctionnelle de Lyapunov basée en partie sur une approximation polynomiale de l’état de l’équation de transport (qui est de dimension infinie). Le manuscrit s’articule en plusieurs étapes. Après la présentation d’un simple modèle couplant des équations différentielles ordinaires avec une équation de transport, l’approximation de l’état de dimension infinie utilisant une projection sur les polynômes de Legendre est décrite. La méthode de Lyapunov est ensuite développée et son fonctionnement nécessite la production de conditions de stabilité sous forme d’inégalités matricielles linéaires. Ces conditions permettent des tests numériques effectués sur des exemples académiques. Des cas plus difficiles sont abordés au fil du document, allant d’une unique équation de transport à plusieurs équations aux vitesses différentes, la prise en compte d’un terme de couplage entre celles ci via un potentiel ou via le bord du domaine. Enfin, un tel couplage avec une équation de transport pouvant être une description alternative d’un système à retard, une étude de la stabilité de ce dernier est développée en utilisant des modèles différents du système couplé, dans le but de réduire la complexité des conditions de stabilité données sous forme des inégalités matricielles.

Mots-Clés / Keywords
Systèmes à retards; Equation de transport; Equations aux dérivées partielles; Théorème de Lyapunov; Systèmes à paramètres distribués; Time-delay systems; Transport equation; Partial differential equations; Lyapunov theory; Distributed parameter systems;

145653
18328
17/10/2018

Embedded and validated control algorithms for the spacecraft rendezvous

P.R.ARANTES GILZ

MAC

Doctorat : Université de Toulouse III - Paul Sabatier, 17 Octobre 2018, 162p., Président: L.ZACCARIAN, Rapporteurs: A.HERNAN GONZALEZ, E.KERRIGAN, Examinateurs: E.COURTIAL, M.VASILE, Directeurs de thèse: M.JOLDES, C.LOUEMBET , N° 18328

Lien : https://hal.laas.fr/tel-01922288

Diffusable

Plus d'informations

Résumé

L’autonomie est l’une des préoccupations majeures lors du développement de missions spatiales que l’objectif soit scientifique (exploration interplanétaire, observations, etc) ou commercial (service en orbite). Pour le rendez-vous spatial, cette autonomie dépend de la capacité embarquée de contrôle du mouvement relatif entre deux véhicules spatiaux. Dans le contexte du service aux satellites (dépannage, remplissage additionnel d’ergols, correction d’orbite, désorbitation en fin de vie, etc), la faisabilité de telles missions est aussi fortement liée à la capacité des algorithmes de guidage et contrôle à prendre en compte l’ensemble des contraintes opérationnelles (par exemple, saturation des propulseurs ou restrictions sur le positionnement relatif entre les véhicules) tout en maximisant la durée de vie du véhicule (minimisation de la consommation d’ergols). La littérature montre que ce problème a été étudié intensément depuis le début des années 2000. Les algorithmes proposés ne sont pas tout à fait satisfaisants. Quelques approches, par exemple, dégradent les contraintes afin de pouvoir fonder l’algorithme de contrôle sur un problème d’optimisation efficace. D’autres méthodes, si elles prennent en compte l’ensemble du problème, se montrent trop lourdes pour être embarquées sur de véritables calculateurs existants dans les vaisseaux spatiaux. Le principal objectif de cette thèse est le développement de nouveaux algorithmes efficaces et validés pour le guidage et le contrôle impulsif des engins spatiaux dans le contexte des phases dites de “hovering” du rendez-vous orbital, i.e. les étapes dans lesquelles un vaisseau secondaire doit maintenir sa position à l’intérieur d’une zone délimitée de l’espace relativement à un autre vaisseau principal. La première contribution présentée dans ce manuscrit utilise une nouvelle formulation mathématique des contraintes d’espace pour le mouvement relatif entre vaisseaux spatiaux pour la conception d’algorithmes de contrôle ayant un traitement calculatoire plus efficace comparativement aux approches traditionnelles. La deuxième et principale contribution est une stratégie de contrôle prédictif qui assure la convergence des trajectoires relatives vers la zone de “hovering”, même en présence de perturbations ou de saturation des actionneurs. Un travail spécifique de développement informatique a pu démontrer l’embarquabilité de ces algorithmes de contrôle sur une carte contenant un microprocesseur LEON3 synthétisé sur FPGA certifié pour le vol spatial, reproduisant les performances des dispositifs habituellement utilisés en vol. Finalement, des outils d’approximation rigoureuse de fonctions ont été utilisés pour l’obtention des solutions validées des équations décrivant le mouvement relatif linéarisé, permettant ainsi une propagation certifiée simple des trajectoires relatives via des polynômes et la vérification du respect des contraintes du problème.

Abstract

Autonomy is one of the major concerns during the planning of a space mission, whether its objective is scientific (interplanetary exploration, observations, etc.) or commercial (service in orbit). For space rendezvous, this autonomy depends on the on-board capacity of controlling the relative movement between two spacecraft. In the context of satellite servicing (troubleshooting, propellant refueling, orbit correction, end-of-life deorbit, etc.), the feasibility of such missions is also strongly linked to the ability of the guidance and control algorithms to account for all operational constraints (for example, thruster saturation or restrictions on the relative positioning between the vehicles) while maximizing the life of the vehicle (minimizing propellant consumption). The literature shows that this problem has been intensively studied since the early 2000s. However, the proposed algorithms are not entirely satisfactory. Some approaches, for example, degrade the constraints in order to be able to base the control algorithm on an efficient optimization problem. Other methods accounting for the whole set of constraints of the problem are too cumbersome to be embedded on real computers existing in the spaceships. The main object of this thesis is the development of new efficient and validated algorithms for the impulsive guidance and control of spacecraft in the context of the so-called "hovering" phases of the orbital rendezvous, i.e. the stages in which a secondary vessel must maintain its position within a bounded area of space relatively to another main vessel. The first contribution presented in this manuscript uses a new mathematical formulation of the space constraints for the relative motion between spacecraft for the design of control algorithms with more efficient computational processing compared to traditional approaches. The second and main contribution is a predictive control strategy that has been formally demonstrated to ensure the convergence of relative trajectories towards the "hovering" zone, even in the presence of disturbances or saturation of the actuators. Specific computational developments have demonstrated the embeddability of these control algorithms on a board containing a FPGAsynthesized LEON3 microprocessor certified for space flight, reproducing the performance of the devices usually used in flight. Finally, tools for rigorous approximation of functions were used to obtain validated solutions of the equations describing the linearized relative motion, allowing a simple certified propagation of the relative trajectories via polynomials and the verification of the respect of the constraints of the problem.

Mots-Clés / Keywords
Spacecraft rendezvous; Model predictive control; Impulsive systems; Embedded algorithms; Validated algorithms; Symbolic computation; Rendez-vous orbital; Commande prédictive; Systèmes impulsifs; Calcul embarqué; Algorithmes certifiés; Calcul formel;

144937
18290
03/10/2018

Computing Approximations and Generalized Solutions Using Moments and Positive Polynomials

T.WEISSER

MAC

Doctorat : Université de Toulouse III - Paul Sabatier, 3 Octobre 2018, 146p., Président: M.SAFEY EL DIN, Rapporteurs: S.KUHLMANN, E.TRELAT, Examinateurs:J.MALIK, H.ZIDANI , Directeurs de thèse: J.B.LASSERRE, D.HENRION , N° 18290

Lien : https://hal.laas.fr/tel-01894578

Diffusable

Plus d'informations

Résumé

Le problème généralisé des moments (PGM) est un problème d’optimisation linéaire sur des espaces de mesures. Il permet de modéliser simplement un grand nombre d’applications. En toute généralité il est impossible à résoudre mais si ses données sont des polynômes et des ensembles semi-algébriques alors on peut définir une hiérarchie de relaxations semidéfinies (SDP) – la hiérarchie moments-sommes-de-carrés (moments-SOS) – qui permet en principe d’approcher la valeur optimale avec une précision arbitraire. Le travail contenu dans cette thèse adresse deux facettes concernants le PGM et la hiérarchie moments-SOS: Une première facette concerne l’évolution des relaxations SDP pour le PGM. Le degré des poids SOS dans la hiérarchie moments-SOS augmente avec l’ordre de relaxation. Lorsque le nombre de variables n’est pas modeste, on obtient rapidement des programmes SDP de taille trop grande pour les logiciels de programmation SDP actuels, sauf si l’on peut utiliser des symétries ou une parcimonie structurée souvent présente dans beaucoup d’applications de grande taille. On présente donc un nouveau certificat de positivité sur un compact semi-algébrique qui (i) exploite la parcimonie présente dans sa description, et (ii) dont les polynômes SOS ont un degré borné à l’avance. Grâce à ce nouveau certificat on peut définir une nouvelle hiérarchie de relaxations SDP pour le PGM qui exploite la parcimonie et évite l’explosion de la taille des matrices semidéfinies positives liée au degré des poids SOS dans la hiérarchie standard. Une deuxième facette concerne (i) la modélisation de nouvelles applications comme une instance particulière du PGM, et (ii) l’application de la méthodologie moments-SOS pour leur résolution. En particulier on propose des approximations déterministes de contraintes probabilistes, un problème difficile car le domaine des solutions admissibles associées est souvent non-convexe et même parfois non connecté. Dans notre approche moments-SOS le domaine admissible est remplacé par un ensemble plus petit qui est le sous-niveau d’un polynôme dont le vecteur des coefficients est une solution optimale d’un certain SDP. La qualité de l’approximation (interne) croît avec le degré du polynôme et la taille du SDP. On illustre cette approche dans le problème du calcul du flux de puissance optimal dans les réseaux d’énergie, une application stratégique où la prise en compte des contraintes probabilistes devient de plus en plus cruciale (e.g., pour modéliser l’incertitude liée á l’énergie éolienne et solaire). En outre on propose une extension des cette procedure qui est robuste à l’incertitude sur la distribution sous-jacente. Des garanties de convergence sont fournies. Une deuxième contribution concerne l’application de la méthodologie moments-SOS pour l’approximation de solutions généralisés en commande optimale. Elle permet de capturer le comportement limite d’une suite minimisante de commandes et de la suite de trajectoires associée. On peut traiter ainsi le cas de phénomènes simultanés de concentrations de la commande et de discontinuités de la trajectoire. Une troisième contribution concerne le calcul de solutions mesures pour les lois de conservation hyperboliques scalaires dont l’exemple typique est l’équation de Burgers. Cette classe d’EDP non linéaire peut avoir des solutions discontinues difficiles à approximer numériquement avec précision. Sous certaines hypothèses, la solution mesurepeut être identifiée avec la solution classique (faible) à la loi de conservation. Notre approche moment-SOS fournit alors une méthode alternative pour approcher des solutions qui contrairement aux méthodes existantes évite une discrétisation du domaine.

Abstract

The generalized moment problem (GMP) is a linear optimization problem over spaces of measures. It allows to model many challenging mathematical problems. While in general it is impossible to solve the GMP, in the case where all data are polynomial and semialgebraic sets, one can define a hierarchy of semidefinite relaxations – the moment-sums-of-squares (moment-SOS) hierachy – which in principle allows to approximate the optimal value of the GMP to arbitrary precision. The work presented in this thesis addresses two facets concerning the GMP and the moment-SOS hierarchy: One facet is concerned with the scalability of relaxations for the GMP. The degree of the SOS weights in the moment-SOS hierarchy grows when augmenting the relaxation order. When the number of variables is not small, this leads quickly to semidefinite programs (SDPs) that are out of range for state of the art SDP solvers, unless one can use symmetries or some structured sparsity which is typically present in large scale applications. We provide a new certificate of positivity which (i) is able to exploit the structured sparsity and (ii) only involves SOS polynomials of fixed degree. From this, one can define a new hierarchy of SDP relaxations for the GMP which can take into account sparsity and at the same time prevents from explosion of the size of SDP variables related to the increasing degree of the SOS weights in the standard hierarchy. The second facet focusses on (i) modelling challenging problems as a particular instance of the GMP and (ii) solving these problems by applying the moment-SOS hierarchy. In particular we propose deterministic approximations of chance constraints a difficult problem as the associated set of feasible solutions is typically non-convex and sometimes not even connected. In our approach we replace this set by a (smaller) sub-level-set of a polynomial whose vector of coefficients is a by-product of the moment-SOS hierarchy when modeling the problem as an instance of the GMP. The quality of this inner approximation improves when increasing the degree of the SDP relaxation and asymptotic convergence is guaranteed. The procedure is illustrated by approximating the feasible set of an instance of the chance-constrained AC Optimal Power Flow problem (a nonlinear problem in the management of energy networks) which nowadays becomes more and more important as we rely increasingly on uncertain energy sources such as wind and solar power. Furthermore, we propose an extension of this framework to the case where the underlying distribution itself is uncertain and provide guarantees of convergence. Another application of the moment-SOS methodology discussed in this thesis consider measure valued solutions to optimal control problems. We show how this procedure can capture the limit behavior of an optimizing sequence of control and its corresponding sequence of trajectories. In particular we address the case of concentrations of control and discontinuities of the trajectory may occur simultaneously. In a final contribution, we compute measure valued solutions to scalar hyperbolic conservation laws, such as Burgers equation. It is known that this class of nonlinear partial differential equations has potentially discontinuous solutions which are difficult to approximate numerically with accuracy. Under some conditions the measure valued solution can be identified with the classical (weak) solution to the conservation law. In this case our moment-SOS approach provides an alternative numerical scheme to compute solutions which in contrast to existing methods, does not rely on discretization of the domain.

Mots-Clés / Keywords
Moments; Positive polynomials; Sparsity; Chance constraints; Measure valued solutions; Semidefinite relaxations; Polynômes positifs; Parcimonie; Contraintes probabilistes; Solutions mesures; Relaxations semidéfinies;

144655
18429
19/09/2018

Diagnostic : étude d’un raisonnement complexe et multi-dimensionnel

Y.PENCOLE

DISCO

Habilitation à diriger des recherches : 19 Septembre 2018, 229p., Président: P.DAGUE, Rapporteurs: A.GRALL, S.HAAR, P.MARQUIS, Examinateurs: M.COMBACAU, Directrice: L.TRAVE-MASSUYES , N° 18429

Lien : https://hal.laas.fr/tel-01984666

Diffusable

Plus d'informations

Abstract

Diagnosing is a general reasoning task that aims at identifying the nature of a situation (misbehaviour, illness, problem,..) by interpreting output signs (observations, measurements, alarms). This type of reasoning can be applied in many social and economical domains. This defense will present a synthesis of the contributions for the development of diagnostic agents on a various type of systems (from statical logical-based systems till timed discrete event systems). The way such agents are involved in decision processes such as corrective and predictive maintenance will be also discussed.

Résumé

Le diagnostic est un raisonnement général qui consiste à identifier la nature d'une situation (dysfonctionnement, maladie, problème...) par l'interprétation de signes extérieurs (observations, mesures, alarmes). Par sa nature, ce type de raisonnement peut s’appliquer à de nombreux domaines socio-économiques. Cette soutenance a pour objectif de présenter une synthèse des contributions à la mise en œuvre effective d’agents diagnostiqueurs sur des types de systèmes variés (allant des systèmes logiques statiques à des systèmes à événements discrets temporels) ainsi que de leur intégration dans des systèmes d’aide à la décision, notamment pour la maintenance corrective et prévisionnelle de systèmes.

Mots-Clés / Keywords
Diagnostic; Raisonnement; Systèmes à événements discrets; Systèmes temporels; Maintenance;

145753
18376
11/09/2018

Earth observation systems optimization for free-space optical communications

M.CAPELLE

ROC

Doctorat : INSA de Toulouse, 11 Septembre 2018, 146p., Président: J.C.BILLAUT, Rapporteurs: O.PETON, S.DEMASSEY, Examinateurs: C.PRALET, F.CLAUTIAUX, Directeurs de thèse: M.J.HUGUET, N.JOZEFOWIEZ , N° 18376

Non diffusable

Plus d'informations

Résumé

Depuis plusieurs années, les satellites sont utilisés pour explorer, surveiller et photographier la Terre depuis l’espace. Ces satellites prennent un nombre croissant d’images avec une résolution de plus en plus de plus élevée, générant ainsi de gros volumes de données qui doivent être envoyés vers la Terre. Afin de transférer de telles quantités de données, de nouvelles technologies de communication sont étudiées. Parmi elles, les liaisons optiques en espace libre sont considérées aujourd’hui comme une alternative intéressante aux technologies actuelles basées sur les radio-fréquences. Avec des débits bien supérieurs à ceux actuels, les liaisons optiques sont capables de transférer d’important volumes de données journaliers en à peine quelques minutes. Cependant, les liaisons optiques sont fortement perturbées par les turbulences atmosphériques et, en particulier, les nuages. Afin de limiter l’impact de la couverture nuageuse, il est nécessaire de créer des réseaux de stations sol optiques efficacement réparties dans le monde. De plus, les prévisions météorologiques n’étant pas exactes, des procédures opérationnelles doivent être établies afin de pouvoir planifier les transferts d’images depuis le satellite vers la Terre, en prenant en compte les incertitudes liées aux nuages et aux prévisions de couverture nuageuse. Dans cette thèse, nous nous intéressons à l’utilisation de communications optiques pour la télémétrie image. Dans un premier temps, nous considérons le problème de la création de réseaux terrestres de stations optiques prenant en compte l’impact des nuages. Nous résolvons ce problème en combinant un algorithme de programmation dynamique avec un algorithme de type branch-and-bound. Dans un second temps, nous nous intéressons au problème de planification des transferts d’images d’un point de vue opérationnel, en prenant en compte les incertitudes sur les volumes des images acquises (dues à la compression bord) et celles liées aux communications optiques. Nous proposons une approche flexible où le processus de décision est partagé entre le système sol (centre mission) et le système à bord du satellite.

Abstract

For many years, satellites have been used to explore, analyse and monitor Earth from space. Nowadays, low-earth orbiting satellites are taking a steadily increasing number of pictures, with higher and higher precision, thus generating huge volumes of data that needs to be downloaded. In order to manage such amount of data, new communication technologies are investigated. In this context, free-space optical communications are seen as a key alternative to current radio-frequency ones. With their orders of magnitude higher data rates, free-space optical communications could be able to download daily acquisition volumes in a matter of minutes. Unfortunately, optical communications are strongly impacted by atmospheric turbulence and clouds. In order to cope with the latter, it is necessary to design efficient distributed networks of optical ground stations. Furthermore, since weather forecasts are imperfect, custom operational procedures should be established to schedule the downloads of acquisitions using optical communications to take into account uncertainties regarding clouds. In this thesis, we investigate the use of free-space optical communications for image telemetry. We first consider the problem of designing efficient networks of optical ground stations taking into account the impact of clouds. We solve this problem using a combination of a dynamic programming algorithm and a branch-and-bound algorithm. Then, we look at the operational problem of planning downloads of acquisitions under download channel and image volume uncertainties. We propose a flexible approach where the decision process is shared between ground and on-board systems.

Mots-Clés / Keywords
Optimisation combinatoire; Observation spatiale; Communications optiques; Combinatorial optimization; Spatial observation; Optical telecommunications;

145257
18200
11/07/2018

Vers des systèmes plus autonomes : contributions autour de la tâche de diagnostic dans une architecture embarquée

E.CHANTHERY

DISCO

Habilitation à diriger des recherches : 11 Juillet 2018, 155p., Président: J.ZAYTOON, Rapporteurs: V.COCQUEMPOT, P.DAGUE, D.LEFEBVRE, Examinateurs: A.SUBIAS, Référente: L.TRAVE-MASSUYES , N° 18200

Lien : https://hal.archives-ouvertes.fr/tel-01882329

Diffusable

Plus d'informations

Abstract

In my presentation, I will first review my teaching activities at INSA Toulouse, as well as my various responsibilities. In a second step, I will give the major axes of my research whose objective is to increase the autonomy of systems by designing appropriate and effective fault diagnosis modules. The detection and isolation of faults help the system to react correctly to the different situations it has to face, thus contributing greatly to its autonomy. I will focus on two major points. Firstly, the link between diagnosis and prognosis will be developed in the context of hybrid dynamic systems. The prognosis aims at predicting the future states of the system. A health management architecture will be presented and then a common modeling framework. I will show that this work has made it possible to standardize the joint formalisms of diagnosis and prognosis. A diagnostic algorithm whose results can be interpreted by the prognostic module will be presented. This algorithmic work, followed by an application in the real case of a rover, constitutes a major contribution for the intrinsic coupling of diagnostic and prognostic algorithms. The second point will be distributed and decentralized diagnosis for continuous dynamics systems. Structural analysis will be proposed as a solution for test generation in complex systems. Despite its apparent simplicity, it provides a powerful set of tools for analyzing and inferring information about the system. Moreover, it has the advantage of being applied indifferently to linear and non-linear systems. The presentation will show how the notions of diagnosis have been adapted in the decentralized and distributed framework, up to the formulation of an optimization problem linked to the choice of a subset of subsystem-level diagnostic tests. . Finally, the last part of my presentation will focus on my research project and present my perspectives for future years.

Résumé

Dans ma présentation d’HDR, j’exposerai dans un premier temps mes activités d’enseignement à l’INSA de Toulouse, ainsi que mes diverses responsabilités et investissements. Dans un deuxième temps, je donnerai les grands axes de ma recherche dont l’objectif est d’accroitre l’autonomie des systèmes en concevant des modules de diagnostic de fautes efficaces et adaptés. La détection et l’isolation des fautes qui peuvent survenir permettent en effet au système de réagir correctement aux différentes situations dans lesquelles il se trouve, contribuant ainsi grandement à son autonomie. Je me focaliserai sur deux points particuliers. Tout d’abord le lien entre le diagnostic et le pronostic sera développé dans le cadre des systèmes à dynamiques hybrides, le pronostic consistant à prédire les états futurs du système. Une architecture de gestion de santé sera présentée puis un cadre commun de modélisation. Je montrerai que ce travail a permis d’uniformiser les formalismes conjoints de diagnostic et de pronostic. Un algorithme de diagnostic dont les résultats sont interprétables par le module de pronostic sera présenté. Ce travail algorithmique, suivi d'une application dans un cas réel de rover, constitue une contribution majeure pour le couplage intrinsèque d’algorithmes de diagnostic et de pronostic. Le deuxième point portera sur le diagnostic décentralisé et distribué pour des systèmes à dynamique continue. L’analyse structurelle sera proposée comme solution pour la génération de tests dans le cadre des systèmes complexes. Malgré son apparente simplicité, cette dernière fournit un ensemble d'outils puissants pour analyser et inférer des informations sur le système. Par ailleurs, elle a l'avantage de s'appliquer indifféremment aux systèmes linéaires et non linéaires. L’exposé montrera comment les notions de diagnostic ont été adaptées dans le cadre décentralisé et distribué, jusqu’à la formulation d’un problème d'optimisation lié au choix d'un sous-ensemble de tests de diagnostic au niveau des sous-systèmes. Enfin, la dernière partie de mon exposé portera sur mon projet de recherche et présentera mes perspectives pour les années futures.

Mots-Clés / Keywords
Diagnostic; Pronostic; Systèmes autonomes; Approche décentralisée; Approche distribuée; Sélection de tests; Autonomous systems; Decentralized approach; Distributed approach; Test selection;

144117
18393
03/07/2018

Codes et jeux de soustraction et de poursuite dans les graphes

P.COUPECHOUX

ROC

Doctorat : INSA de Toulouse, 3 Juillet 2018, 118p., Président: M.J.HUGUET, Rapporteurs: E.DUCHENE, A.QUILLOT, Examinateurs: P.VALICOV, A.PINLOU, Directeurs de thèse: J.MONCEL , N° 18393

Lien : https://tel.archives-ouvertes.fr/tel-01948357

Diffusable

Plus d'informations

Abstract

Identifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game! , where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results.

Abstract

Les codes identifiants ont été introduits en 1998 par Karpovsky, Chakrabarty et Levitin. Un code identifiant est un sous-graphe tel que chaque sommet est identifié de manière unique par les sommets du code qui l'entourent. Il existe plusieurs variantes de ces codes, dont notamment une version colorée dans laquelle les sommets sont identifiés par les couleurs dans leur voisinage. Dans cette thèse, nous cherchons en particulier à construire un cycle le plus grand possible qui admette une coloration identifiante, étant donné un nombre de couleurs fixé. Nous avons aussi étudié le problème des codes identifiants sur une classe particulière de graphes orientés : les tournois. Dans une seconde partie, nous avons aussi étudié deux jeux particuliers. Le premier est une généralisation des jeux octaux - qui se jouent normalement sur un tas - aux graphes. Plus précisemment, le jeu 0.33 ; chaque joueur peut retirer un ou deux sommets voisins d'un graphe, sans déc! onnecter ce dernier. Le premier qui ne peut plus jouer perd. Nous avons été capable de caractériser les issues de ce jeu dans des classes de graphes particulières, les étoiles subdivisées et les bi-étoiles subdivisées. Le second jeu est appelé le jeu du Pompier (Firefighter). Il consiste à arrêter un feu qui se propage dans un graphe en protégeant des sommets à chaque tour. Nous avons résolu une conjecture sur ce jeu, et introduit la version online, pour laquelle nous avons pu donner des résultats d'approximation.

Mots-Clés / Keywords
Théorie des graphes; Théorie des jeux; Codes identifiants; Colorations identifiantes; 0.33; Firefighter; Graphs theory; Game theory; Identifying codes;

145353
18350
28/06/2018

Le contrôle d’attitude des satellites, support et projet de recherche en automatique

C.PITTET

MAC

Habilitation à diriger des recherches : 28 Juin 2018, 236p., Président: J.P.RAYMOND, Rapporteurs: L.DUGARD, H.PIET-LAHANIER, B.CLEMENT, Examinateurs: J.DAAFOUZ, E.LAROCHE, Directeurs de thèse: S.TARBOURIECH , N° 18350

Non diffusable

Plus d'informations

Abstract

The research activities presented deal with satellite attitude control which is the control of the position and angular velocity of the three axes of rotation of the solid body around its center of inertia. This problem, which obviously has several existing and commonly used solutions in the industry, is an interesting and more complex application than it appears for automatic control research activities. The research results come either from internal work carried out at CNES or from work carried out with external partners (industrial contractors and research laboratories) in the context of research and technology (R&T) studies or PhDs. The work is divided into two main parts: attitude control, first as a research application, then as a research project. In the first part, we present different control results and attitude estimation based on either a linearized model (robustness analysis and control, linear time varying control) or a nonlinear model of the satellite (constrained control, dynamic inversion). In the second part, short-term and longer-term research perspectives are discussed.

Résumé

Les activités de recherche présentées portent sur le contrôle d’attitude des satellites, c’est-à-dire l’asservissement de la position et vitesse angulaire des trois axes de rotation du corps solide autour de son centre d’inertie. Ce problème qui a évidemment plusieurs solutions existantes et couramment utilisées dans l’industrie, est un support intéressant et plus complexe qu’il n’y parait pour des activités de recherche en automatique. Les résultats de recherche sont issus soit de travaux internes menés au CNES, soit de travaux menés avec des partenaires extérieurs (maîtres d’œuvre industriels et laboratoires de recherche) dans le cadre d’études de recherche et technologies (R&T) ou de thèses. Les travaux s’articulent en deux grandes parties : le contrôle d’attitude d’abord comme support de recherche, puis comme projet de recherche. Dans la première partie, nous présentons différents résultats de commande et estimation d’attitude basés soit sur un modèle linéarisé (commande et analyse robuste, commande linéaire à temps variant), soit sur un modèle non-linéaire du satellite (commande contrainte, inversion dynamique). Dans la deuxième partie, des perspectives de recherche à court et plus long terme sont abordées.

Mots-Clés / Keywords
Contrôle d’attitude de satellite; Satellites; Modélisation; Commande; Estimation; Attitude control (AOCS); Modelling; Control;

145073
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/