La planification de mouvement est le domaine de l’informatique qui a trait au développement de techniques algorithmiques permettant la génération automatique de trajectoires pour un système mécanique. La nature d’un tel système varie selon les champs d’application. En animation par ordinateur il peut s’agir d’un avatar humanoïde. En biologie moléculaire cela peut être une protéine. Le domaine d’application de ces travaux étant la robotique aérienne, le système est ici un UAV (Unmanned Aerial Vehicle: véhicule aérien sans pilote) à quatre hélices appelé quadrirotor. Le problème de planification de mouvements consiste à calculer une série de mouvements qui amène le système d’une configuration initiale donnée à une configuration finale souhaitée sans générer de collisions avec son environnement, la plupart du temps connu à l’avance. Les méthodes habituelles explorent l’espace des configurations du système sans tenir compte de sa dynamique. Cependant, la force de poussée qui permet à un quadrirotor de voler est par construction parallèle aux axes de rotation des hélices, ce qui implique que certains mouvements ne peuvent pas être effectués. De plus, l’intensité de cette force de poussée, et donc l’accélération linéaire du centre de masse, sont limitées par les capacités physiques du robot. Pour toutes ces raisons, non seulement la position et l’orientation doivent être planifiées, mais les dérivées plus élevées doivent l’être également si l’on veut que le système physique soit en mesure de réellement exécuter le mouvement. Lorsque c’est le cas, on parle de planification kinodynamique de mouvements. Une distinction est faite entre le planificateur local et le planificateur global. Le premier est chargé de produire une trajectoire valide entre deux états du système sans nécessairement tenir compte des collisions. Le second est l’algorithme principal qui est chargé de résoudre le problème de planification de mouvement en explorant l’espace d’état du système. Il fait appel au planificateur local. Nous présentons un planificateur local qui interpole deux états comprenant un nombre arbitraire de degrés de liberté ainsi que leurs dérivées premières et secondes. Compte tenu d’un ensemble de limites sur les dérivées des degrés de liberté jusqu’au quatrième ordre (snap), il produit rapidement une trajectoire en temps minimal quasi optimale qui respecte ces limites. Dans la plupart des algorithmes modernes de planification de mouvements, l’exploration est guidée par une fonction de distance (ou métrique). Le meilleur choix pour celle-ci est le cost-to-go, c.a.d. le coût associé à la méthode locale. Dans le contexte de la planification kinodynamique de mouvements, il correspond à la durée de la trajectoire en temps minimal. Le problème dans ce cas est que calculer le cost-to-go est aussi difficile (et donc aussi coûteux) que de calculer la trajectoire optimale elle-même. Nous présentons une métrique qui est une bonne approximation du cost-to-go, mais dont le calcul est beaucoup moins coûteux. Le paradigme dominant en planification de mouvements aujourd’hui est l’échantillonnage aléatoire. Cette classe d’algorithmes repose sur un échantillonnage aléatoire de l’espace d’état afin de l’explorer rapidement. Une stratégie commune est l’échantillonnage uniforme. Il semble toutefois que, dans notre contexte, ce soit un choix assez médiocre. En effet, une grande majorité des états uniformément échantillonnés ne peuvent pas être interpolés. Nous présentons une stratégie d’échantillonnage incrémentale qui diminue considérablement la probabilité que cela ne se produise. / Motion planning is the field of computer science that aims at developing algorithmic techniques allowing the automatic computation of trajecto- ries for a mechanical system. The nature of such a system vary according to the fields of application. In computer animation it could be a humanoid avatar. In molecular biology it could be a protein. The field of application of this work being aerial robotics, the system is here a four-rotor UAV (Unmanned Aerial Vehicle) called quadrotor. The motion planning problem consists in computing a series of motions that brings the system from a given initial configuration to a desired final configuration without generating collisions with its environment, most of the time known in advance. Usual methods explore the system’s configuration space regardless of its dynamics. By construction the thrust force that allows a quadrotor to fly is tangential to its attitude which implies that not every motion can be performed. Furthermore, the magnitude of this thrust force and hence the linear acceleration of the center of mass are limited by the physical capabilities of the robot. For all these reasons, not only position and orientation must be planned, higher derivatives must be planned also if the motion is to be executed. When this is the case we talk of kinodynamic motion planning. A distinction is made between the local planner and the global planner. The former is in charge of producing a valid trajectory between two states of the system without necessarily taking collisions into account. The later is the overall algorithmic process that is in charge of solving the motion planning problem by exploring the state space of the system. It relies on multiple calls to the local planner. We present a local planner that interpolates two states consisting of an arbitrary number of degrees of freedom (dof) and their first and second derivatives. Given a set of bounds on the dof derivatives up to the fourth order (snap), it quickly produces a near-optimal minimum time trajectory that respects those bounds. In most of modern global motion planning algorithms, the exploration is guided by a distance function (or metric). The best choice is the cost-to-go, i.e. the cost associated to the local method. In the context of kinodynamic motion planning, it is the duration of the minimal-time trajectory. The problem in this case is that computing the cost-to-go is as hard (and thus as costly) as computing the optimal trajectory itself. We present a metric that is a good approximation of the cost-to-go but which computation is far less time consuming. The dominant paradigm nowadays is sampling-based motion planning. This class of algorithms relies on random sampling of the state space in order to quickly explore it. A common strategy is uniform sampling. It however appears that, in our context, it is a rather poor choice. Indeed, a great majority of uniformly sampled states cannot be interpolated. We present an incremental sampling strategy that significantly decreases the probability of this happening.

Le but de cette thèse est d'étendre l'état de l'art par des contributions sur le comportement collectif d'un groupe de robots volants, à savoir des quadrirotors UAV. Afin de pouvoir sûrement naviguer dans un environnement, ces derniers peuvent se reposer uniquement sur leurs capacités à bord et non sur des systèmes centralisés (e.g., Vicon ou GPS). Nous réalisons cet objectif en offrant une possible solution aux problèmes de contrôle en formation et de localisation à partir de mesures à bord et via une communication locale. Nous abordons ces problèmes exploitant différents concepts provenant de la théorie des graphes algébriques et de la théorie de la rigidité. Cela nous permet de résoudre ces problèmes de façon décentralisée et de proposer des algorithmes décentralisés capables de prendre en compte également des limites sensorielles classiques. Les capacités embarquées que nous avons mentionnées plus tôt sont représentées par une caméra monoculaire et une centrale inertielle (IMU) auxquelles s'ajoute la capacité de chaque robot à communiquer (par RF) avec certains de ses voisins. Cela est dû au fait que l'IMU et la caméra représentent une possible configuration économique et légère pour la navigation et la localisation autonome d'un quadrirotor UAV. / The aim of this Thesis is to give contributions to the state of the art on the collective behavior of a group of flying robots, specifically quadrotor UAVs, which can only rely on their onboard capabilities and not on a centralized system (e.g., Vicon or GPS) in order to safely navigate in the environment. We achieve this goal by giving a possible solution to the problems of formation control and localization from onboard sensing and local communication. We tackle these problems exploiting mainly concepts from algebraic graph theory and the so-called theory of rigidity. This allows us to solve these problems in a decentralized fashion, and propose decentralized algorithms able to also take into account some typical sensory limitations. The onboard capabilities we referred to above are represented by an onboard monocular camera and an inertial measurement unit (IMU) in addition to the capability of each robot to communicate (through RF) with some of its neighbors. This is due to the fact that an IMU and a camera represent a possible minimal, lightweight and inexpensive configuration for the autonomous localization and navigation of a quadrotor UAV.

Cette thèse développe une nouvelle approche de contrôle pour les avions à échelle réduite. Les lois de commande proposées exploitent un modèle non linéaire simple mais pertinent des forces aérodynamiques appliquées à l’aéronef. Ils reposent sur une structure hiérarchique de contrôle non linéaires, et sont synthétisées sur la base d’analyse de stabilité et de convergence théoriques. Ils sont conçus pour fonctionner sur un large domaine de vol. En particulier, ils évitent les singularités associées à la paramétrisation de l'attitude et la direction de la vitesse. Dans un premier temps, le problème de stabilisation de trajectoires de référence est résolu en étendant la méthode du "thrust vectoring", utilisée pour les véhicules à voilure tournante, au cas des aéronefs à voilure fixe. Dans le cas des avions, le principal défi est de prendre en compte les forces aérodynamiques dans la conception des systèmes de commande. Afin de résoudre ce problème, le contrôle proposé est conçu et analysé sur la base du modèle de forces aérodynamique proposé. Le domaine d'utilisation de cette loi de commande est élargi et englobe les trajectoires d'équilibre (trim trajectories) qui sont classiquement utilisées dans la littérature. Cette solution est ensuite adaptée au problème de suivi de chemin, afin de concevoir des lois de guidage cinématique et de contrôle dynamique applicables à presque tout chemin 3D régulier. Les lois de contrôle proposées contiennent des termes intégraux qui robustifient le contrôle vis-à-vis de dynamiques non modélisées. Plusieurs problèmes pratiques sont adressés et les lois de commande proposées sont validées par des simulations du type "hardware-in-the-loop". Enfin, des résultats d'essais en vol illustrent la performance des lois de contrôle proposées. / The present thesis develops a new control approach for scale-model airplanes. The proposed control solutions exploit a simple but pertinent nonlinear model of aerodynamic forces acting on the aircraft. Nonlinear controllers are based on a hierarchical structure, and are derived on the basis of theoretical stability and convergence analyses. They are designed to operate on a large spectrum of operating conditions. In particular, they avoid the singularities associated with the parameterization of the attitude and the heading of the vehicle, and do not rely on a decoupling between longitudinal and lateral dynamics. First, the trajectory tracking problem is addressed by extending the thrust vectoring method used for small rotor vehicles to the case of fixed wing vehicles. In the case of airplanes, the main challenge is to take into account the aerodynamic forces in the design of control systems. In order to solve this problem, the proposed control is designed and analyzed on the basis of the proposed aerodynamic forces model. The flight envelope is thus broadened beyond trim trajectories which are classically used in the literature. This solution is then adapted to the path following problem, and kinematic guidance and dynamic control laws are developed within a single coherent framework that applies to almost any regular 3D path. The proposed control laws incorporate integral terms that robustify the control with respect to unmodelled dynamics. Several practical issues are addressed and the proposed control laws are validated via hardware-in-the-loop simulations. Finally, successful flight test results illustrate the soundness and performance of the proposed control laws.

Dans un contexte industriel aéronautique où les problématiques de sécurité constituent un facteur différentiateur clé, l’objectif de cette thèse est de répondre à la problématique ambitieuse de la réduction des accidents de type opérationnel. Les travaux de recherche s’inscrivent dans le domaine des systèmes d’alarmes pour l’évitement de collision qui ne font pas une analyse approfondie des solutions d’évitement par rapport à la situation de danger. En effet, les situations d’urgence en vol ne bénéficient pas à ce jour d’une représentation et d’un guide des solutions associées formels. Bien que certains systèmes d’assistance existent et qu’une partie de la connaissance associée aux situations d’urgence ait pu être identifiée, la génération dynamique d’une séquence de manœuvres sous fortes contraintes de temps et dans un environnement non connu à l’avance représente une voie d’exploration nouvelle. Afin de répondre à cette question et de rendre objective la notion de danger, les travaux de recherche présentés dans cette thèse mettent en confrontation la capacité d’évolution d’un aéronef dans son environnement immédiat avec une enveloppe physique devenant contraignante. Afin de mesurer ce danger, les travaux de recherche ont conduit à construire un module de trajectoires capable d’explorer l’espace en 3D. Cela a permis de tirer des enseignements en terme de flexibilité des manœuvres d’évitement possibles à l’approche du sol. De plus l’elicitation des connaissances des pilotes et des experts d’Airbus Helicopters (ancien Eurocopter) mis en situation d’urgence dans le cas d’accidents reconstitués en simulation a conduit à un ensemble de paramètres pour l’utilisation de la méthode multicritère PROMETHEE II dans le processus de prise de décision relatif au choix de la meilleure trajectoire d’évitement et par conséquent à la génération d’alarmes anti-collision. / In the aeronautics industrial context, the issues related to the safety constitute a highly differentiating factor. This PhD thesis addresses the challenge of operational type accident reduction. The research works are positioned and considered within the context of existing alerting equipments for collision avoidance, who don’t report a thorough analysis of the avoidance manoeuvres with respect to a possible threat. Indeed, in-flight emergency situations are various and do not all have a formal representation of escape procedures to fall back on. Much of operational accident scenarios are related to human mistakes. Even if systems providing assistance already exist, the dynamic generation of a sequence of manoeuvres under high constraints in an unknown environment remain a news research axis, and a key development perspective. In order to address this problematic and make the notion of danger objective, the research works presented in this thesis confront the capabilities of evolution of an aircraft in its immediate environment with possible physical constraints. For that purpose, the study has conducted to generate a module for trajectory generation in the 3D space frame, capable of partitioning and exploring the space ahead and around the aircraft. This has allowed to draw conclusions in terms of flexibility of escape manoeuvres on approach to the terrain. Besides, the elicitation of the Airbus Helicopters (former Eurocopter) experts knowledge put in emergency situations, for reconstituted accident scenarios in simulation, have permitted to derive a certain number of criteria and rules for parametrising the multicriteria method PROMETHEE II in the process for the relative decision-making of the best avoidance trajectory solution. This has given clues for the generation of new alerting rules to prevent the collisions.