This paper proposes a novel methodology for path generation in known and congested multi-obstacle environments. Our aim is to solve an open problem in navigation within such environments: the feasible space partitioning in accordance with the distribution of obstacles. It is shown that such a partitioning is a key concept towards the generation of a corridor in cluttered environments. Once a corridor between an initial and a final position is generated, the selection of a path is considerably simplified in comparison with the methods which explore the original non-convex feasible regions of the environment. The core of the methodology presented here is the construction of a convex lifting which boils down to a convex optimization. The paper covers both the mathematical foundations and the computational details of the implementation and aims to illustrate the concepts with geometrical examples.
The maximal positive invariant (MPI) set results from a finite set recurrence instantiated by the intersection of input and state bounds (e.g., the stage constraints of the linear model predictive control problem). When these constraints take the form of hyper-rectangles, zonotopes or constrained zonotopes, the resulting polyhedral MPI set may be succinctly described as a constrained zonotope, eliminating the need for explicit enumeration of its halfspaces. In this paper we discuss the various MPI computation algorithms (with both exact and sufficient stop conditions), recasted in the framework of constrained zonotopes. We analyze one of these variations over a dynamical system whose dimension can be arbitrarily increased in order to asses changes in computation time and storage requirements with respect to the polyhedral case (under the simplifying assumption of closed-loop invertibility of the state matrix).
The maximal positively invariant (MPI) set is obtained through a backward reachability procedure involving the iterative computation and intersection of predecessor sets under state and input constraints. However, standard static feedback synthesis may place some of the closed-loop eigenvalues at zero, leading to rank-deficient dynamics. This affects the MPI computation by inducing projections onto lower-dimensional subspaces during intermediate steps. By exploiting the Schur decomposition, we explicitly address this singular case and propose a robust algorithm that computes the MPI set in both polyhedral and constrained-zonotope representations.
Stratégies de navigation en sécurité dans un environnement encombré: Cette thèse se rapporte à la navigation et le contrôle par optimisation dans des environnements multi-obstacles. Le problème de conception est généralement énoncé dans la littérature en termes de problème d'optimisation sous contrainte sur un domaine non convexe. Ainsi, en s'appuyant sur la combinaison du contrôle prédictif de modèle et des concepts de la théorie des ensembles, on a développe des méthodes constructives basées sur l'interprétation géométrique. Dans sa première partie, la thèse se concentre sur la représentation de l'environnement multi-obstacles, basée sur une analyse approfondie des résultats récents dans le domaine. Ainsi, on a choisi d'exploiter une classe particulière d'ensembles convexes (dotés de la propriété de symétrie) afin de modéliser l'environnement, réduire la complexité et améliorer les performances. De plus, on a résolve un problème ouvert dans la navigation dans des environnements encombrés : le partitionnement de l'espace faisable en fonction de la distribution des obstacles. Le cœur de cette méthodologie est la construction d'un convex lifting qui se résume à une optimisation convexe. On a couvré à la fois les fondements mathématiques et les détails informatiques de l'implémentation. Enfin, on a illustré les concepts par des exemples géométriques et on a complété l'étude en fournissant des garanties de faisabilité globale et en améliorant le contrôle effectif au niveau stratégique.
We consider a plant affected by multiple faults (modeled through a piecewise affine formalism). Using a bank of finite-window observers and an artificially-induced feedback delay we provide an exact fault detection and isolation (FDI) mechanism, integrated into the overall fault tolerant control scheme. We use zonotopic characterizations for the sets of interest in order to provide explicit conditions for FDI exactness (such that a fault occurrence can be signaled unambiguously) and to alleviate the numerical issues specific to set operations.