Cette thèse est une contribution au calcul des variations et à la théorie du contrôle optimal dans les cadres discret, plus généralement time scale, et fractionnaire. Ces deux domaines ont récemment connu un développement considérable dû pour l’un à son application en informatique et pour l’autre à son essor dans des problèmes physiques de diffusion anormale. Que ce soit dans le cadre time scale ou dans le cadre fractionnaire, nos objectifs sont de : a) développer un calcul des variations et étendre quelques résultats classiques (voir plus bas); b) établir un principe du maximum de Pontryagin (PMP en abrégé) pour des problèmes de contrôle optimal. Dans ce but, nous généralisons plusieurs méthodes variationnelles usuelles, allant du simple calcul des variations au principe variationnel d’Ekeland (couplé avec la technique des variations-aiguilles), en passant par l’étude d’invariances variationnelles par des groupes de transformations. Les démonstrations des PMPs nous amènent également à employer des théorèmes de point fixe et à prendre en considération la technique des multiplicateurs de Lagrange ou encore une méthode basée sur un théorème d’inversion locale conique. Ce manuscrit est donc composé de deux parties : la Partie 1 traite de problèmes variationnels posés sur time scale et la Partie 2 est consacrée à leurs pendants fractionnaires. Dans chacune de ces deux parties, nous suivons l’organisation suivante : 1. détermination de l’équation d’Euler-Lagrange caractérisant les points critiques d’une fonctionnelle Lagrangienne ; 2. énoncé d’un théorème de type Noether assurant l’existence d’une constante de mouvement pour les équations d’Euler-Lagrange admettant une symétrie ; 3. énoncé d’un théorème de type Tonelli assurant l’existence d’un minimiseur pour une fonctionnelle Lagrangienne et donc, par la même occasion, d’une solution pour l’équation d’Euler-Lagrange associée (uniquement en Partie 2) ; 4. énoncé d’un PMP (version forte en Partie 1, version faible en Partie 2) donnant une condition nécessaire pour les trajectoires qui sont solutions de problèmes de contrôle optimal généraux non-linéaires ; 5. détermination d’une condition de type Helmholtz caractérisant les équations provenant d’un calcul des variations (uniquement en Partie 1 et uniquement dans les cas purement continu et purement discret). Des théorèmes de type Cauchy-Lipschitz nécessaires à l’étude de problèmes de contrôle optimal sont démontrés en Annexe. / This dissertation deals with the mathematical fields called calculus of variations and optimal control theory. More precisely, we develop some aspects of these two domains in discrete, more generally time scale, and fractional frameworks. Indeed, these two settings have recently experience a significant development due to its applications in computing for the first one and to its emergence in physical contexts of anomalous diffusion for the second one. In both frameworks, our goals are: a) to develop a calculus of variations and extend some classical results (see below); b) to state a Pontryagin maximum principle (denoted in short PMP) for optimal control problems. Towards these purposes, we generalize several classical variational methods, including the Ekeland’s variational principle (combined with needle-like variations) as well as variational invariances via the action of groups of transformations. Furthermore, the investigations for PMPs lead us to use fixed point theorems and to consider the Lagrange multiplier technique and a method based on a conic implicit function theorem. This manuscript is made up of two parts : Part A deals with variational problems on time scale and Part B is devoted to their fractional analogues. In each of these parts, we follow (with minor differences) the following organization: 1. obtaining of an Euler-Lagrange equation characterizing the critical points of a Lagrangian functional; 2. statement of a Noether-type theorem ensuring the existence of a constant of motion for Euler-Lagrange equations admitting a symmetry;3. statement of a Tonelli-type theorem ensuring the existence of a minimizer for a Lagrangian functional and, consequently, of a solution for the corresponding Euler-Lagrange equation (only in Part B); 4. statement of a PMP (strong version in Part A and weak version in Part B) giving a necessary condition for the solutions of general nonlinear optimal control problems; 5. obtaining of a Helmholtz condition characterizing the equations deriving from a calculus of variations (only in Part A and only in the purely continuous and purely discrete cases). Some Picard-Lindelöf type theorems necessary for the analysis of optimal control problems are obtained in Appendices.

Le problème d’ordre linéaire (LOP) a reçu beaucoup d’attention dans différents domaines d’application, allant de l’archéologie à l’ordonnancement en passant par l’économie et même de la psychologie mathématique. Ce problème est aussi connu pour être parmi les problèmes NP-difficiles. Nous considérons dans cette thèse une variante de (LOP) sous contrainte de cardinalité. Nous cherchons donc un ordre linéaire d’un sous-ensemble de sommets du graphe de préférences de cardinalité fixée et de poids maximum. Ce problème, appelé (FCLOP) pour ’fixed-cardinality linear ordering problem’, n’a pas été étudié en tant que tel dans la littérature scientifique même si plusieurs applications dans les domaines de macro-économie, de classification dominante ou de transport maritime existent concrètement. On retrouve en fait ses caractéristiques dans les modèles étendus de sous-graphes acycliques. Le problème d’ordre linéaire est déjà connu comme un problème NP-difficile et il a donné lieu à de nombreuses études, tant théoriques sur la structure polyédrale de l’ensemble des solutions réalisables en variables 0-1 que numériques grâce à des techniques de relaxation et de séparation progressive. Cependant on voit qu’il existe de nombreux cas dans la littérature, dans lesquelles des solveurs de Programmation Linéaire en nombres entiers comme CPLEX peuvent en résoudre certaines instances en moins de 10 secondes, mais une fois que la cardinalité est limitée, ces mêmes instances deviennent très difficiles à résoudre. Sur les aspects polyédraux, nous avons étudié le polytope de FCLOP, défini plusieurs classes d’inégalités valides et identifié la dimension ainsi que certaines inégalités qui définissent des facettes pour le polytope de FCLOP. Nous avons introduit un algorithme Relax-and-Cut basé sur ces résultats pour résoudre les instances du problème. Dans cette étude, nous nous sommes également concentrés sur la relaxation Lagrangienne pour résoudre ces cas difficiles. Nous avons étudié différentes stratégies de relaxation et nous avons comparé les bornes duales par rapport à la consolidation obtenue à partir de chaque stratégie de relâcher les contraintes afin de détecter le sous-ensemble des contraintes le plus approprié. Les résultats numériques montrent que nous pouvons trouver des bornes duales de très haute qualité. Nous avons également mis en place une méthode de décomposition Lagrangienne. Dans ce but, nous avons décomposé le modèle de FCLOP en trois sous-problèmes (au lieu de seulement deux) associés aux contraintes de ’tournoi’, de ’graphes sans circuits’ et de ’cardinalité’. Les résultats numériques montrent une amélioration significative de la qualité des bornes duales pour plusieurs cas. Nous avons aussi mis en oeuvre une méthode de plans sécants (cutting plane algorithm) basée sur la relaxation pure des contraintes de circuits. Dans cette méthode, on a relâché une partie des contraintes et on les a ajoutées au modèle au cas où il y a des de/des violations. Les résultats numériques montrent des performances prometteuses quant à la réduction du temps de calcul et à la résolution d’instances difficiles hors d’atteinte des solveurs classiques en PLNE. / Linear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from transportation and scheduling to economics and even archeology and mathematical psychology. It is classified as a NP-hard problem. Assume a complete weighted directed graph on V n , |V n |= n. A permutation of the elements of this finite set of vertices is a linear order. Now let p be a given fixed integer number, 0 ≤ p ≤ n. The p-Fixed Cardinality Linear Ordering Problem (FCLOP) is looking for a subset of vertices containing p nodes and a linear order on the nodes in S. Graphically, there exists exactly one directed arc between every pair of vertices in an LOP feasible solution, which is also a complete cycle-free digraph and the objective is to maximize the sum of the weights of all the arcs in a feasible solution. In the FCLOP, we are looking for a subset S ⊆ V n such that |S|= p and an LOP on these S nodes. Hence the objective is to find the best subset of the nodes and an LOP over these p nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution of the FCLOP is a complete cycle-free digraph on S plus a set of n − p vertices that are not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of the linear ordering problem as well as various exact and heuristic solution methods. The fixed cardinality linear ordering problem is presented for the first time in this PhD study, so as far as we know, there is no other study in the literature that has studied this problem. The linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature that can be solved by CPLEX in less than 10 seconds (when p = n), but once the cardinality number is limited to p (p < n), the instance is not anymore solvable due to the memory issue. We have studied the polytope corresponding to the FCLOP for different cardinality values. We have identified dimension of the polytope, proposed several classes of valid inequalities and showed that among these sets of valid inequalities, some of them are defining facets for the FCLOP polytope for different cardinality values. We have then introduced a Relax-and-Cut algorithm based on these results to solve instances of the FCLOP. To solve the instances of the problem, in the beginning, we have applied the Lagrangian relaxation algorithm. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable subproblem. Numerical results show that some of the relaxation strategies result better dual bound and some other contribute more in reducing the computational time and provide a relatively good dual bound in a shorter time. We have also implemented a Lagrangian decomposition algorithm, decom-6 posing the FCLOP model to three subproblems (instead of only two subproblems). The interest of decomposing the FCLOP model to three subproblems comes mostly from the nature of the three subproblems, which are relatively quite easier to solve compared to the initial FCLOP model. Numerical results show a significant improvement in the quality of dual bounds for several instances. We could also obtain relatively quite better dual bounds in a shorter time comparing to the other relaxation strategies. We have proposed a cutting plane algorithm based on the pure relaxation strategy. In this algorithm, we firstly relax a subset of constraints that due to the problem structure, a very few number of them are active. Then in the course of the branch-and-bound tree we verify if there exist any violated constraint among the relaxed constraints or. Then the characterized violated constraints will be globally added to the model. (...)

The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning. First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature. In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above. The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization. We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.

L'implantation en Virgule Flottante (VF) d'une fonction à valeurs réelles est réalisée avec arrondi correct si le résultat calculé est toujours égal à l'arrondi de la valeur exacte, ce qui présente de nombreux avantages. Mais pour implanter une fonction avec arrondi correct de manière fiable et efficace, il faut résoudre le «dilemme du fabricant de tables» (TMD en anglais). Deux algorithmes sophistiqués (L et SLZ) ont été conçus pour résoudre ce problème, via des calculs longs et complexes effectués par des implantations largement optimisées. D'où la motivation d'apporter des garanties fortes sur le résultat de ces pré-calculs coûteux. Dans ce but, nous utilisons l'assistant de preuves Coq. Tout d'abord nous développons une bibliothèque d'«approximation polynomiale rigoureuse», permettant de calculer un polynôme d'approximation et un intervalle bornant l'erreur d'approximation à l'intérieur de Coq. Cette formalisation est un élément clé pour valider la première étape de SLZ, ainsi que l'implantation d'une fonction mathématique en général (avec ou sans arrondi correct). Puis nous avons implanté en Coq, formellement prouvé et rendu effectif 3 vérifieurs de certificats, dont la preuve de correction dérive du lemme de Hensel que nous avons formalisé dans les cas univarié et bivarié. En particulier, notre «vérifieur ISValP» est un composant clé pour la certification formelle des résultats générés par SLZ. Ensuite, nous nous sommes intéressés à la preuve mathématique d'algorithmes VF en «précision augmentée» pour la racine carré et la norme euclidienne en 2D. Nous donnons des bornes inférieures fines sur la plus petite distance non nulle entre sqrt(x²+y²) et un midpoint, permettant de résoudre le TMD pour cette fonction bivariée. Enfin, lorsque différentes précisions VF sont disponibles, peut survenir le phénomène de «double-arrondi», qui peut changer le comportement de petits algorithmes usuels en arithmétique. Nous avons prouvé en Coq un ensemble de théorèmes décrivant le comportement de Fast2Sum avec double-arrondis. / The Floating-Point (FP) implementation of a real-valued function is performed with correct rounding if the output is always equal to the rounding of the exact value, which has many advantages. But for implementing a function with correct rounding in a reliable and efficient manner, one has to solve the ``Table Maker's Dilemma'' (TMD). Two sophisticated algorithms (L and SLZ) have been designed to solve this problem, relying on some long and complex calculations that are performed by some heavily-optimized implementations. Hence the motivation to provide strong guarantees on these costly pre-computations. To this end, we use the Coq proof assistant. First, we develop a library of ``Rigorous Polynomial Approximation'', allowing one to compute an approximation polynomial and an interval that bounds the approximation error in Coq. This formalization is a key building block for verifying the first step of SLZ, as well as the implementation of a mathematical function in general (with or without correct rounding). Then we have implemented, formally verified and made effective 3 interrelated certificates checkers in Coq, whose correctness proof derives from Hensel's lemma that we have formalized for both univariate and bivariate cases. In particular, our ``ISValP verifier'' is a key component for formally verifying the results generated by SLZ. Then, we have focused on the mathematical proof of ``augmented-precision'' FP algorithms for the square root and the Euclidean 2D norm. We give some tight lower bounds on the minimum non-zero distance between sqrt(x²+y²) and a midpoint, allowing one to solve the TMD for this bivariate function. Finally, the ``double-rounding'' phenomenon can typically occur when several FP precision are available, and may change the behavior of some usual small FP algorithms. We have formally verified in Coq a set of results describing the behavior of the Fast2Sum algorithm with double-roundings.

The aim of this thesis is to present new results concerning duality in scalar optimization. We show how the theory can be applied to optimization problems arising in the theory of risk measures, portfolio optimization and machine learning. First we give some notations and preliminaries we need within the thesis. After that we recall how the well-known Lagrange dual problem can be derived by using the general perturbation theory and give some generalized interior point regularity conditions used in the literature. Using these facts we consider some special scalar optimization problems having a composed objective function and geometric (and cone) constraints. We derive their duals, give strong duality results and optimality condition using some regularity conditions. Thus we complete and/or extend some results in the literature especially by using the mentioned regularity conditions, which are weaker than the classical ones. We further consider a scalar optimization problem having single chance constraints and a convex objective function. We also derive its dual, give a strong duality result and further consider a special case of this problem. Thus we show how the conjugate duality theory can be used for stochastic programming problems and extend some results given in the literature. In the third chapter of this thesis we consider convex risk and deviation measures. We present some more general measures than the ones given in the literature and derive formulas for their conjugate functions. Using these we calculate some dual representation formulas for the risk and deviation measures and correct some formulas in the literature. Finally we proof some subdifferential formulas for measures and risk functions by using the facts above. The generalized deviation measures we introduced in the previous chapter can be used to formulate some portfolio optimization problems we consider in the fourth chapter. Their duals, strong duality results and optimality conditions are derived by using the general theory and the conjugate functions, respectively, given in the second and third chapter. Analogous calculations are done for a portfolio optimization problem having single chance constraints using the general theory given in the second chapter. Thus we give an application of the duality theory in the well-developed field of portfolio optimization. We close this thesis by considering a general Support Vector Machines problem and derive its dual using the conjugate duality theory. We give a strong duality result and necessary as well as sufficient optimality conditions. By considering different cost functions we get problems for Support Vector Regression and Support Vector Classification. We extend the results given in the literature by dropping the assumption of invertibility of the kernel matrix. We use a cost function that generalizes the well-known Vapnik's ε-insensitive loss and consider the optimization problems that arise by using this. We show how the general theory can be applied for a real data set, especially we predict the concrete compressive strength by using a special Support Vector Regression problem.

The goal of this thesis is two-fold. On the one hand, it pursues to provide a contribution to the conjugate duality by proposing a new duality concept, which can be understood as an umbrella for different meaningful perturbation methods. On the other hand, this thesis aims to investigate minimax location problems by means of the duality concept introduced in the first part of this work, followed by a numerical approach using epigraphical splitting methods. After summarizing some elements of the convex analysis as well as introducing important results needed later, we consider an optimization problem with geometric and cone constraints, whose objective function is a composition of n+1 functions. For this problem we propose a conjugate dual problem, where the functions involved in the objective function of the primal problem are decomposed. Furthermore, we formulate generalized interior point regularity conditions for strong duality and give necessary and sufficient optimality conditions. As applications of this approach we determine the formulae of the conjugate as well as the biconjugate of the objective function of the primal problem and analyze an optimization problem having as objective function the sum of reciprocals of concave functions. In the second part of this thesis we discuss in the sense of the introduced duality concept three classes of minimax location problems. The first one consists of nonlinear and linear single minimax location problems with geometric constraints, where the maximum of nonlinear or linear functions composed with gauges between pairs of a new and existing points will be minimized. The version of the nonlinear location problem is additionally considered with set-up costs. The second class of minimax location problems deals with multifacility location problems as suggested by Drezner (1991), where for each given point the sum of weighted distances to all facilities plus set-up costs is determined and the maximal value of these sums is to be minimized. As the last and third class the classical multifacility location problem with geometrical constraints is considered in a generalized form where the maximum of gauges between pairs of new facilities and the maximum of gauges between pairs of new and existing facilities will be minimized. To each of these location problems associated dual problems will be formulated as well as corresponding duality statements and necessary and sufficient optimality conditions. To illustrate the results of the duality approach and to give a more detailed characterization of the relations between the location problems and their corresponding duals, we consider examples in the Euclidean space. This thesis ends with a numerical approach for solving minimax location problems by epigraphical splitting methods. In this framework, we give formulae for the projections onto the epigraphs of several sums of powers of weighted norms as well as formulae for the projection onto the epigraphs of gauges. Numerical experiments document the usefulness of our approach for the discussed location problems.

<p>A time-discrete formulation of the variational principle of mechanics is used to provide a consistent theoretical framework for the construction and analysis of low order integration methods. These are applied to mechanical systems subject to mixed constraints and dry frictional contacts and impacts---machines. The framework includes physics motivated constraint regularization and stabilization schemes. This is done by adding potential energy and Rayleigh dissipation terms in the Lagrangian formulation used throughout. These terms explicitly depend on the value of the Lagrange multipliers enforcing constraints. Having finite energy, the multipliers are thus massless ghost particles. The main numerical stepping method produced with the framework is called SPOOK.</p><p>Variational integrators preserve physical invariants globally, exactly in some cases, approximately but within fixed global bounds for others. This allows to product realistic physical trajectories even with the low order methods. These are needed in the solution of nonsmooth problems such as dry frictional contacts and in addition, they are computationally inexpensive. The combination of strong stability, low order, and the global preservation of invariants allows for large integration time steps, but without loosing accuracy on the important and visible physical quantities. SPOOK is thus well-suited for interactive simulations, such as those commonly used in virtual environment applications, because it is fast, stable, and faithful to the physics.</p><p>New results include a stable discretization of highly oscillatory terms of constraint regularization; a linearly stable constraint stabilization scheme based on ghost potential and Rayleigh dissipation terms; a single-step, strictly dissipative, approximate impact model; a quasi-linear complementarity formulation of dry friction that is isotropic and solvable for any nonnegative value of friction coefficients; an analysis of a splitting scheme to solve frictional contact complementarity problems; a stable, quaternion-based rigid body stepping scheme and a stable linear approximation thereof. SPOOK includes all these elements. It is linearly implicit and linearly stable, it requires the solution of either one linear system of equations of one mixed linear complementarity problem per regular time step, and two of the same when an impact condition is detected. The changes in energy caused by constraints, impacts, and dry friction, are all shown to be strictly dissipative in comparison with the free system. Since all regularization and stabilization parameters are introduced in the physics, they map directly onto physical properties and thus allow modeling of a variety of phenomena, such as constraint compliance, for instance.</p><p>Tutorial material is included for continuous and discrete-time analytic mechanics, quaternion algebra, complementarity problems, rigid body dynamics, constraint kinematics, and special topics in numerical linear algebra needed in the solution of the stepping equations of SPOOK.</p><p>The qualitative and quantitative aspects of SPOOK are demonstrated by comparison with a variety of standard techniques on well known test cases which are analyzed in details. SPOOK compares favorably for all these examples. In particular, it handles ill-posed and degenerate problems seamlessly and systematically. An implementation suitable for large scale performance and accuracy testing is left for future work.</p>

A time-discrete formulation of the variational principle of mechanics is used to provide a consistent theoretical framework for the construction and analysis of low order integration methods. These are applied to mechanical systems subject to mixed constraints and dry frictional contacts and impacts---machines. The framework includes physics motivated constraint regularization and stabilization schemes. This is done by adding potential energy and Rayleigh dissipation terms in the Lagrangian formulation used throughout. These terms explicitly depend on the value of the Lagrange multipliers enforcing constraints. Having finite energy, the multipliers are thus massless ghost particles. The main numerical stepping method produced with the framework is called SPOOK. Variational integrators preserve physical invariants globally, exactly in some cases, approximately but within fixed global bounds for others. This allows to product realistic physical trajectories even with the low order methods. These are needed in the solution of nonsmooth problems such as dry frictional contacts and in addition, they are computationally inexpensive. The combination of strong stability, low order, and the global preservation of invariants allows for large integration time steps, but without loosing accuracy on the important and visible physical quantities. SPOOK is thus well-suited for interactive simulations, such as those commonly used in virtual environment applications, because it is fast, stable, and faithful to the physics. New results include a stable discretization of highly oscillatory terms of constraint regularization; a linearly stable constraint stabilization scheme based on ghost potential and Rayleigh dissipation terms; a single-step, strictly dissipative, approximate impact model; a quasi-linear complementarity formulation of dry friction that is isotropic and solvable for any nonnegative value of friction coefficients; an analysis of a splitting scheme to solve frictional contact complementarity problems; a stable, quaternion-based rigid body stepping scheme and a stable linear approximation thereof. SPOOK includes all these elements. It is linearly implicit and linearly stable, it requires the solution of either one linear system of equations of one mixed linear complementarity problem per regular time step, and two of the same when an impact condition is detected. The changes in energy caused by constraints, impacts, and dry friction, are all shown to be strictly dissipative in comparison with the free system. Since all regularization and stabilization parameters are introduced in the physics, they map directly onto physical properties and thus allow modeling of a variety of phenomena, such as constraint compliance, for instance. Tutorial material is included for continuous and discrete-time analytic mechanics, quaternion algebra, complementarity problems, rigid body dynamics, constraint kinematics, and special topics in numerical linear algebra needed in the solution of the stepping equations of SPOOK. The qualitative and quantitative aspects of SPOOK are demonstrated by comparison with a variety of standard techniques on well known test cases which are analyzed in details. SPOOK compares favorably for all these examples. In particular, it handles ill-posed and degenerate problems seamlessly and systematically. An implementation suitable for large scale performance and accuracy testing is left for future work.

The main body of this thesis consists of six appended papers. In the  first two, different  cooperative surveillance problems are considered. The second two consider different aspects of the trajectory planning problem, while the last two deal with observer design for mobile robotic and Euler-Lagrange systems respectively.In Papers A and B,  a combinatorial optimization based framework to cooperative surveillance missions using multiple Unmanned Ground Vehicles (UGVs) is proposed. In particular, Paper A  considers the the Minimum Time UGV Surveillance Problem (MTUSP) while Paper B treats the Connectivity Constrained UGV Surveillance Problem (CUSP). The minimum time formulation is the following. Given a set of surveillance UGVs and a polyhedral area, find waypoint-paths for all UGVs such that every point of the area is visible from  a point on a waypoint-path and such that the time for executing the search in parallel is minimized.  The connectivity constrained formulation  extends the MTUSP by additionally requiring the induced information graph to be  kept recurrently connected  at the time instants when the UGVs  perform the surveillance mission.  In these two papers, the NP-hardness of  both these problems are shown and decomposition techniques are proposed that allow us to find an approximative solution efficiently in an algorithmic manner.Paper C addresses the problem of designing a real time, high performance trajectory planner for an aerial vehicle that uses information about terrain and enemy threats, to fly low and avoid radar exposure on the way to a given target. The high-level framework augments Receding Horizon Control (RHC) with a graph based terminal cost that captures the global characteristics of the environment.  An important issue with RHC is to make sure that the greedy, short term optimization does not lead to long term problems, which in our case boils down to two things: not getting into situations where a collision is unavoidable, and making sure that the destination is actually reached. Hence, the main contribution of this paper is to present a trajectory planner with provable safety and task completion properties. Direct methods for trajectory optimization are traditionally based on a priori temporal discretization and collocation methods. In Paper D, the problem of adaptive node distribution is formulated as a constrained optimization problem, which is to be included in the underlying nonlinear mathematical programming problem. The benefits of utilizing the suggested method for  online  trajectory optimization are illustrated by a missile guidance example.In Paper E, the problem of active observer design for an important class of non-uniformly observable systems, namely mobile robotic systems, is considered. The set of feasible configurations and the set of output flow equivalent states are defined. It is shown that the inter-relation between these two sets may serve as the basis for design of active observers. The proposed observer design methodology is illustrated by considering a  unicycle robot model, equipped with a set of range-measuring sensors. Finally, in Paper F, a geometrically intrinsic observer for Euler-Lagrange systems is defined and analyzed. This observer is a generalization of the observer proposed by Aghannan and Rouchon. Their contractivity result is reproduced and complemented  by  a proof  that the region of contraction is infinitely thin. Moreover, assuming a priori bounds on the velocities, convergence of the observer is shown by means of Lyapunov's direct method in the case of configuration manifolds with constant curvature. / QC 20100622 / TAIS, AURES

<p>The main body of this thesis consists of four appended papers. The first two consider different aspects of the trajectory planning problem, while the last two deal with observer design for mobile robotic and Euler-Lagrange systems respectively.</p><p>The first paper addresses the problem of designing a real time, high performance trajectory planner for aerial vehicles. The main contribution is two-fold. Firstly, by augmenting a novel safety maneuver at the end of the planned trajectory, this paper extends previous results by having provable safety properties in a 3D setting. Secondly, assuming initial feasibility, the planning method is shown to have finite time task completion. Moreover, in the second part of the paper, the problem of simultaneous arrival of multiple aerial vehicles is considered. By using a time-scale separation principle, one is able to adopt standard Laplacian control to this consensus problem, which is neither unconstrained, nor first order.</p><p>Direct methods for trajectory optimization are traditionally based on<i> a</i> <i>priori </i>temporal discretization and collocation methods. In the second paper, the problem of adaptive node distribution is formulated as a constrained optimization problem, which is to be included in the underlying nonlinear mathematical programming problem. The benefits of utilizing the suggested method for online trajectory optimization are illustrated by a missile guidance example.</p><p>In the third paper, the problem of active observer design for an important class of non-uniformly observable systems, namely mobile robotics systems, is considered. The set of feasible configurations and the set of output flow equivalent states are defined. It is shown that the inter-relation between these two sets may serve as the basis for design of active observers. The proposed observer design methodology is illustrated by considering a unicycle robot model, equipped with a set of range-measuring sensors.</p><p>Finally, in the fourth paper, a geometrically intrinsic observer for Euler-Lagrange systems is defined and analyzed. This observer is a generalization of the observer recently proposed by Aghannan and Rouchon. Their contractivity result is reproduced and complemented by a proof that the region of contraction is infinitely thin. However, assuming <i>a</i> <i>priori </i>bounds on the velocities, convergence of the observer is shown by means of Lyapunov's direct method in the case of configuration manifolds with constant curvature.</p>