Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L'intervalle de confiance le plus connu pour une différence de deux proportions est l'intervalle de Wald. Cet intervalle a l'avantage d'être simple à construire, mais il est anti-conservateur. Il existe plusieurs intervalles alternatifs à l'intervalle deWald qui performent beaucoup mieux. Dans ce mémoire, on s'intéressera particulièrement à l'intervalle d'Agresti-Coull et à l'intervalle bayésien approximatif. Ces intervalles performent très bien tout en étant simples à construire. On regardera d'abord la performance de ces intervalles lorsqu'on a deux échantillons indépendants de tailles fixées au départ. On regardera aussi leur performance lorsque le nombre d'observations dépend des vraies proportions, soit dans une expérience à étapes multiples, soit dans une expérience à allocations séquentielles ou un plan adaptatif est utilisé.

Depuis quelques années, la méthode de séparation et évaluation par intervalles (Interval Branch and Bound) est de plus en plus utilisée pour résoudre les problèmes d’optimisation globale sous contraintes (Constrained Global Optimisation), notamment ceux qui sont non convexes. Contrairement à un grand nombre de ses concurrents, cette méthode permet de prouver l’optimalité d’une solution avec un niveau de précision donné. En revanche, son processus d’exploration arborescent implique une complexité exponentielle en temps et en mémoire dans le pire cas. De ce fait, le développement de techniques permettant d’accélérer la convergence de cette méthode définit un pan de recherche important.Une première contribution concerne les méthodes de contraction destinées à réduire l’espace de recherche. Nous proposons une nouvelle méthode de contraction, nommée TEC, qui généralise à plusieurs dimensions le principe de la disjonction constructive utilisée par la méthode de contraction CID. TEC construit un sous- arbre d’exploration par un processus de bissection et de contraction avant d’effectuer l’union des espaces de recherche associés aux feuilles de ce sous-arbre. Nous proposons deux variantes de TEC exploitant sa structure arborescente. La première, nommée Graham-TEC, permet d’apprendre des contraintes linéaires implicites utilisées pour améliorer la contraction. La seconde, nommée TEC-UB, permet d’apporter une amélioration à la recherche de solutions en faisant appel à une heuristique de recherche de solutions sur les feuilles du sous-arbre.Une deuxième contribution concerne les stratégies de parcours de l’arbre d’exploration. Nous étudions une stratégie récente qui fait un compromis entre un parcours en meilleur d’abord et un parcours en profondeur d’abord. Nous proposons des variantes de cet algorithme qui privilégient l’exploration des régions faisables.Les algorithmes proposés, testés sur un banc d’essai reconnu par la communauté, obtiennent des temps comparables à l’état de l’art. / In recent years, the Interval Branch and Bound method has been used more and more to solve constraint global optimization problems, especially those which are non-convex. Unlike many of its competitors, this method makes it possible to prove the optimality of a solution with a given level of accuracy. On the other hand, its tree exploration process implies an exponential complexity in time and memory in the worst case. That is why, the development of acceleration techniques defines an important piece of research.A first contribution concerns the interval filtering operators designed to reduce the search space. We propose a new interval filtering operator, named TEC, that generalizes to several dimensions the constructive disjunction principle used by the existing CID operator. TEC constructs a bounded subtree using a branch and contract process and returns the parallel-to-axes hull of the leaf domains/boxes. We propose two variants of TEC exploiting its tree structure. The first variant, named Graham-TEC, learns implicit linear constraints, used for improving the contraction. The second one, named TEC-UB, searches for a good feasible point inside a leaf box of the TEC subtree.A second contribution concerns the node selection strategies. We have studied a recent strategy that makes a compromise between a best-first search and a depth-first search and have proposed variants of this algorithm that favor the exploration of feasible regions.

Les systèmes micro mécatroniques intègrent dans un volume très réduit des fonctions de natures différentes (électrique, mécanique, thermique, magnétique ou encore optique). Ces systèmes sont des produits finaux ou sont dans des systèmes de taille macroscopique. La tendance à la miniaturisation et à la complexité des fonctions à réaliser conduit à des microsystème en trois dimensions et constitué´es de composants provenant de processus de (micro)fabrication parfois incompatibles. L’assemblage microbotique est une réponse aux challenges de leur réalisation. Pour assurer les opérations d’ assemblage avec des précisions et des résolutions élevées, des capteurs adaptés au micro monde et des outils particuliers de manipulation doivent être utilisés. Les éléments principaux constituants les systèmes de micromanipulation sont les micro-actionneurs.Ces derniers sont souvent faits à base de matériaux actifs parmi lesquels les matériaux Piézoélectriques . Les actionneurs piézoélectriques sont caractérisés par leur très haute résolution (souvent nanométrique), leur grande bande-passante (plus du kHz pour certains micro-actionneurs) et leur grande densité de force. Tout ceci en fait des actionneurs particulièrement intéressants pour le micro-assemblage et la micromanipulation. Cependant,ces actionneurs présentent, en plus de leur comportement non-linéaire, une forte dépendance à l’environnement et aux tâches considérées. De plus, ces tâches de micromanipulation et de micro-assemblage sont confrontées à un manque de capteurs précis et compatibles avec les dimensions du micromonde. Ceci engendre des incertitudes sur les paramètres du élaboré lors de l’identification. En présence du verrou technologique lié à la réalisation des capteurs et des propriétés complexes des actionneurs, il est difficile d’obtenir les performances de haut niveau requises pour réussir les tâches de micromanipulation et de micro-assemblage. C’est notamment la mise au point d’outils de commande convenables qui permet d’atteindre les niveaux de précision et de résolution nécessaires.Les travaux de cette thèse s’inscrivent dans ce cadre. Afin de réussir les tâches de micromanipulation et de micro-assemblage, plusieurs méthodes de commande prenant en compte des incertitudes liées au modèle, comme les approches de commande robustes de type H-inf ont déjà utilisées pour commander les actionneurs piézoélectriques.L’un des inconvénients majeurs de ces méthodes est la dérivation de régulateurs d’ordre élevé qui sont coûteux en calcul et peuvent difficilement être embarqués dans les microsystèmes. Afin de prendre en compte les incertitudes paramétriques des modèles des Systèmes à commander, nous proposons une solution alternative basée sur l’utilisation du calcul par intervalles. Ces techniques du calcul par intervalles sont combinées avec les outils de l’automatique pour modéliser et commander les microsystèmes. Nous chercherons également à montrer que l’utilisation de ces techniques permet d’associer la robustesse et la simplicité des correcteurs dérivés / Micromechatronic systems integrate in a very small volume functions with differentnatures. The trend towards miniaturization and complexity of functions to achieve leadsto 3-dimensional microsystems. These 3-dimensional systems are formed by microroboticassembly of various microfabricated and incompatible components. To achieve theassembly operations with high accuracy and high resolution, adapted sensors for themicroworld and special tools for the manipulation are required. The microactuators arethe main elements that constitute the micromanipulation systems. These actuators areoften based on smart materials, in particular piezoelectric materials. The piezoelectricmaterials are characterized by their high resolution (nanometric), large bandwidth (morethan kHz) and high force density. This why the piezoelectric actuators are widely usedin the micromanipulation and microassembly tasks. However, the behavior of the piezoelectricactuators is non-linear and very sensitive to the environment. Moreover, thedeveloppment of the micromanipulation and the microassembly tasks is limited by thelack of precise and compatible sensors with the microworld dimensions. In the presenceof the difficulties related to the sensors realization and the complex characteristics ofthe actuators, it is difficult to obtain the required performances for the micromanipulationand the microassembly tasks. For that, it is necessary to develop a specific controlapproach that achieves the wanted accuracy and resolution.The works in this thesis deal with this problematic. In order to success the micromanipulationand the microassembly tasks, robust control approaches such as H∞ havealready been tested to control the piezoelectric actuators. However, the main drawbacksof these methods is the derivation of high order controllers. In the case of embedded microsystems,these high order controllers are time consuming which limit their embeddingpossibilities. To address this problem, we propose in our work an alternative solutionto model and control the microsystems by combining the interval techniques with theautomatic tools. We will also seek to show that the use of these techniques allows toderive robust and low-order controllers.

Les contraintes sont un moyen générique de représenter les règles qui gouvernent notre monde. Étant donné un ensemble de contraintes, une question centrale est de savoir s'il existe une possibilité de toutes les satisfaire simultanément. Cette problématique est au cœur de la programmation par contraintes, un paradigme puissant pour résoudre efficacement des problèmes qui apparaissent dans de nombreux domaines de l'activité humaine. Initialement dédiée, dans les années 1980, à la résolution de problèmes d'intelligence artificielle à variables entières, c'est dans les années 1990 que la programmation par contraintes a été employée à la résolution de problèmes à variables réelles. Cependant, les problèmes mixtes —utilisant à la fois variables entières et réelles— n'ont été que très peu considérés jusqu'ici par la programmation par contraintes. Dans cette thèse, nous nous plaçons du point de vue de la résolution de problèmes continus. Nous proposons et mettons en oeuvre différentes améliorations de ce cadre de résolution : • Intégration de la notion de recherche rigoureuse d'optimum au cadre classique de résolution sans objectif, afin de modéliser et résoudre un problème de conception en robotique ; • Collaboration de deux solveurs, l'un discret l'autre continu, plus efficace que chacun des outils pour résoudre les problèmes utilisant contraintes continues et contraintes discrètes ; • Comparaison des différentes modélisations et filtrages possibles de la contrainte globale discrète alldifferent, permettant de l'utiliser dans un solveur dédié au continu ; • Spécialisation des techniques de filtrage basées sur l'arithmétique des intervalles, augmentant la puissance de filtrage des contraintes arithmétiques discrètes et mixtes.

La modélisation des systèmes dynamiques requiert la prise en compte d'incertitudes liées à l'existence inévitable de bruits (bruits de mesure, bruits sur la dynamique), à la méconnaissance de certains phénomènes perturbateurs mais également aux incertitudes sur la valeur des paramètres (spécification de tolérances, phénomène de vieillissement). Alors que certaines de ces incertitudes se prêtent bien à une modélisation de type statistique comme par exemple les bruits de mesure, d'autres se caractérisent mieux par des bornes, sans autre attribut. Dans ce travail de thèse, motivés par les observations ci-dessus, nous traitons le problème de l'intégration d'incertitudes statistiques et à erreurs bornées pour les systèmes linéaires à temps discret. Partant du filtre de Kalman Intervalle (noté IKF) développé dans [Chen 1997], nous proposons des améliorations significatives basées sur des techniques récentes de propagation de contraintes et d'inversion ensembliste qui, contrairement aux mécanismes mis en jeu par l'IKF, permettent d'obtenir un résultat garanti tout en contrôlant le pessimisme de l'analyse par intervalles. Cet algorithme est noté iIKF. Le filtre iIKF a la même structure récursive que le filtre de Kalman classique et délivre un encadrement de tous les estimés optimaux et des matrices de covariance possibles. L'algorithme IKF précédent évite quant à lui le problème de l'inversion des matrices intervalles, ce qui lui vaut de perdre des solutions possibles. Pour l'iIKF, nous proposons une méthode originale garantie pour l'inversion des matrices intervalle qui couple l'algorithme SIVIA (Set Inversion via Interval Analysis) et un ensemble de problèmes de propagation de contraintes. Par ailleurs, plusieurs mécanismes basés sur la propagation de contraintes sont également mis en oeuvre pour limiter l'effet de surestimation due à la propagation d'intervalles dans la structure récursive du filtre. Un algorithme de détection de défauts basé sur iIKF est proposé en mettant en oeuvre une stratégie de boucle semi-fermée qui permet de ne pas réalimenter le filtre avec des mesures corrompues par le défaut dès que celui-ci est détecté. A travers différents exemples, les avantages du filtre iIKF sont exposés et l'efficacité de l'algorithme de détection de défauts est démontré.

Le pré-dimensionnement se situe en amont du processus de conception d'un système : à partir d'un ensemble d'exigences, il consiste à déterminer un ensemble de solutions techniques possibles dans un espace de recherche souvent très grand et structuré par une connaissance partielle et incertaine du futur système et de son environnement. Bien avant de penser au choix définitif des composants et au dimensionnement précis du système complet, les concepteurs doivent s'appuyer sur un premier cahier des charges, des modélisations des principaux phénomènes et divers retours d'expériences pour formaliser des contraintes, faire des hypothèses simplificatrices, envisager diverses architectures et faire des choix sur des données imprécises (i.e. caractérisées sous la forme d'intervalles, de listes de valeurs possibles, etc…). Les choix effectués lors du pré-dimensionnement pouvant être très lourds de conséquences sur la suite du développement, il est primordial de détecter au plus tôt d'éventuelles incohérences et de pouvoir vérifier la satisfaction des exigences dans un contexte incertain. Dans ce travail, une méthodologie de vérification des exigences basée sur l'échange de modèles ensemblistes entre donneurs d'ordre et fournisseurs est proposée. Elle s'inscrit dans le cadre d'un paradigme de conception basé sur la réduction d'incertitudes. Après un travail portant sur la modélisation des systèmes mécatroniques, une attention particulière est portée à la prise en compte d'incertitudes déterministes sur des grandeurs continues : des techniques basées sur l'analyse par intervalles telles que la satisfaction de contraintes (CSP), des calculs d'atteignabilité pour des modèles dynamiques de connaissances ou encore l'identification de modèles de comportements ensemblistes sont ainsi mis en œuvre et développés afin d'outiller la méthodologie proposée et contribuer à répondre à l'objectif d'une vérification à couverture garantie. / The pre-sizing takes place upstream to the process of designing a system: from a set of requirements, it consists in determining a set of possible technical solutions in an often very large search space which is structured by the uncertain and partial knowledge available about the future system and its environment. Long before making the final choice and the final sizing of the system components, the designers have to use specifications, models of the main phenomena, and experience feedbacks to formalize some constraints, make simplifying assumptions, consider various architectures and make choices based on imprecise data (i.e. intervals, finite sets of possible values, etc…). The choices made during the pre-sizing process often involving strong commitments for the further developments, it is very important to early detect potential inconsistencies and to verify the satisfaction of the requirements in an uncertain context. In this work, a methodology based on the exchange of set-membership models between principals and suppliers is proposed for the verification of requirements. This methodology is fully consistent with a design paradigm based on the reduction of uncertainties. After a work dedicated to the modeling of mechatronic systems, a special attention is paid to dealing with deterministic uncertainties affecting continuous values: some techniques based on interval analysis such as constraint satisfaction (interval CSP), reachability computations for knowledge dynamic models or identification of set-membership behavioral models are used and developed, so providing a set of tools to implement the proposed methodology and contribute to reach the goal of a verification with a full and guaranteed coverage.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objectif de cette thèse est de proposer des méthodes pour étalonner un robot parallèle à câbles de grande dimension. Afin d'améliorer le comportement global d'un robot, il est nécessaire d'identifier au mieux les paramètres de son modèle. Pour cela, il est important d'obtenir des informations redondantes en mesurant l'état du robot dans différentes configurations. Cependant, le modèle choisi est un compromis entre sa capacité à représenter le comportement réel du manipulateur et les informations disponibles pour le renseigner. Dans le cas particulier des robots à câbles de grande dimension, la masse et l'élasticité des câbles ont une influence non négligeable sur le comportement du robot mais sont difficiles à modéliser. En effet, le modèle physique des câbles est complexe et nécessite de connaître la tension à laquelle ils sont soumis. Les capteurs disponibles ne pouvant nous fournir cette information avec une précision suffisante pour renseigner un modèle de câble réaliste, nous proposons d'utiliser un modèle simplifié. Dans le but de proposer un étalonnage efficace, il est donc nécessaire de définir les conditions pour l'emploi de ce modèle simplifié. Ensuite, nous avons adapté et implanté d'une part plusieurs techniques classiques pour l'étalonnage des robots parallèles mais nous avons également élaboré des approches plus innovantes. Nous proposons en effet un modèle pour les robots à câbles reposant sur une représentation des incertitudes de modélisation, de mesures et de paramètres au moyen d'intervalles. / The main objective of this thesis is to propose new methods for the calibration of a large scale cable-driven robot. The principal method to improve the global behavior of a robot consists to identify the parameters of the model. For this, it is important to get redundant information by measuring the state of the robot in different configurations. However, the model used is a compromise between its ability to represent the actual behavior of the manipulator and the information available to fill in it. In the special case of the large scale cable-driven robots, mass and elasticity of the cables have a significant influence on the behavior of the robot but they are difficult to model. Indeed, the physical model of the cable is complex and requires knowledge of the tension inside it. Available sensors cannot provide this information with a sufficient accuracy to fill in a model of a realistic cable, we thus propose to use a simplified model. In order to provide an efficient calibration, it is necessary to fix the requirements to use this simplified model. Then, we have adapted and implemented some classical techniques for the calibration of parallel robots, but we also developed more innovative approaches. We propose a model for cable robots based on a representation of the uncertainties from modeling, measurements and parameters using intervals. By exploiting the interval analysis, we have developed various approaches to identify with certification the geometric parameters of the structure. We thus propose a new approach and associated algorithms to characterize and compute different kind of solutions for the calibration problem.

Cette thèse étudie le problème de la localisation et de la cartographie simultanée (SLAM), dans des environnements non structurés, c'est-à-dire, qui ne peuvent pas être décrits par des équations ou des formes géométriques. Ces types d'environnements sont souvent rencontrés dans le domaine sous-marin. Contrairement aux approches classiques, l'environnement n'est pas modélisé par une collection de descripteurs ou d'amers ponctuels, mais directement par des ensembles. Ces ensembles, appelés forme ou shape, sont associés à des caractéristiques physiques de l'environnement, comme par exemple, des textures, du relief ou, de manière plus symbolique, à l'espace libre autour du véhicule. D'un point de vue théorique, le problème du SLAM, basé sur des formes, est formalisé par un réseau de contraintes hybrides dont les variables sont des vecteurs de Rn et des sous-ensembles de Rn. De la même façon que l'incertitude sur une variable réelle est représentée par un intervalle de réels, l'incertitude sur les formes sera représentée par un intervalle de forme. La principale contribution de cette thèse est de proposer un formalisme, basé sur le calcul par intervalle, capable de calculer ces domaines. En application, les algorithmes développés ont été appliqués au problème du SLAM à partir de données bathymétriques recueillies par un véhicule sous-marin autonome (AUV). / This thesis deals with the simultaneous localization and mapping (SLAM) problem in unstructured environments, i.e. which cannot be described by geometrical features. This type of environment frequently occurs in an underwater context.Unlike classical approaches, the environment is not described by a collection of punctual features or landmarks, but directly by sets. These sets, called shapes, are associated with physical features such as the relief, some textures or, in a more symbolic way, the space free of obstacles that can be sensed around a robot. In a theoretical point of view, the SLAM problem is formalized as an hybrid constraint network where the variables are vectors and subsets of Rn. Whereas an uncertain real number is enclosed in an interval, an uncertain shape is enclosed in an interval of sets. The main contribution of this thesis is the introduction of a new formalism, based on interval analysis, able to deal with these domains. As an application, we illustrate our method on a SLAM problem based on bathymetric data acquired by an autonomous underwater vehicle (AUV).