Il est fondamental pour un robot d'être capable de se déplacer de manière complètement autonome afin d'accomplir une mission qui lui a été confiée, et ce avec un budget énergétique fini, dans un laps de temps contraint et sans connaissances préalables de l’environnement. Afin d'atteindre un objectif dans le plan ou l'espace, un robot doit à minima être capable d'accomplir quatre tâches: maintenir une représentation abstraite de l'environnement (une carte), être capable de se localiser à l'intérieur de cette représentation, utiliser la représentation pour planifier des itinéraires et naviguer le long de la trajectoire prévue tout en s'adaptant aux dynamiques de l'environnement et en évitant les obstacles. Chacun de ces problèmes a été étudié par la communauté de la robotique. Cependant, ces quatre composants sont en général étudiés séparément et sont par conséquent incompatibles entre eux pour l'essentiel. De plus, étant donné qu'humains et robots ne disposent que de ressources computationelles et mémorielles finies, les algorithmes de planification, navigation et SLAM devraient être capables de fonctionner avec des données incomplètes ou compressées tout en garantissant que le ou les objectifs fixés soient atteints. Dans cette thèse, la planification, la navigation et le SLAM dans des environnements arbitrairement grands et avec des ressources computationelles et mémorielles finies sont vues comme un seul problème, créant un nouveau paradigme que nous appelons Navigation Exploratoire au long de la Vie ou Lifelong Exploratory Navigation. / One of the yet unresolved canonical problems of robotics is to have robots move completely autonomously in order to accomplish any mission they are charged with, with time and resource constraints and without prior knowledge of the environment. Reaching a goal requires the robot to perform at least four tasks: maintaining an abstract representation of the environment (map), being able to localize itself within this representation, using the representation to plan paths and navigating on the planned paths while handling dynamics of the environment and avoiding obstacles. Each of these problems has been studied extensively by the robotics community. However, the four components are usually studied separately, and as a result are mostly incompatible with each other. Additionally, since humans as well as robots have to operate with finite memory and computing resources, long running planning, navigation and SLAM algorithms may have to operate on incomplete or compressed data while guaranteeing that the goal(s) can still be reached. In this thesis, planning, navigation and SLAM in arbitrarily large environments with finite computing resources and memory are considered as one single problem, for a new bio-inspired paradigm which we call Lifelong Exploratory Navigation.

Le Cloud Computing est un nouveau paradigme qui fournit des ressources informatiques sous forme de services à la demande via internet fondé sur le modèle de facturation pay-per-use. Il est de plus en plus utilisé pour le déploiement et l’exécution des processus métier en général et des processus métier à base de services (SBPs) en particulier. Les environnements cloud sont généralement très dynamiques. À cet effet, il devient indispensable de s’appuyer sur des agents intelligents appelés gestionnaires autonomiques (AMs), qui permettent de rendre les SBPs capables de se gérer de façon autonome afin de faire face aux changements dynamiques induits parle cloud. Cependant, les solutions existantes sont limitées à l’utilisation soit d’un AM centralisé, soit d’un AM par service pour gérer un SBP. Il est évident que la deuxième solution représente un gaspillage d’AMs et peut conduire à la prise de décisions de gestion contradictoires, tandis que la première solution peut conduire à des goulots d’étranglement au niveau de la gestion du SBP. Par conséquent, il est essentiel de trouver le nombre optimal d’AMs qui seront utilisés pour gérer un SBP afin de minimiser leur nombre tout en évitant les goulots d’étranglement. De plus, en raison de l’hétérogénéité des ressources cloud et de la diversité de la qualité de service (QoS) requise par les SBPs, l’allocation des ressources cloud pour ces AMs peut entraîner des coûts de calcul et de communication élevés et/ou une QoS inférieure à celle exigée. Pour cela, il est également essentiel de trouver l’allocation optimale des ressources cloud pour les AMs qui seront utilisés pour gérer un SBP afin de minimiser les coûts tout en maintenant les exigences de QoS. Dans ce travail, nous proposons un modèle d’optimisation déterministe pour chacun de ces deux problèmes. En outre, en raison du temps nécessaire pour résoudre ces problèmes qui croît de manière exponentielle avec la taille du problème, nous proposons des algorithmes quasi-optimaux qui permettent d’obtenir de bonnes solutions dans un temps raisonnable / Cloud Computing is a new paradigm that provides computing resources as a service over the internet in a pay-per-use model. It is increasingly used for hosting and executing business processes in general and service-based business processes (SBPs) in particular. Cloud environments are usually highly dynamic. Hence, executing these SBPs requires autonomic management to cope with the changes of cloud environments implies the usage of a number of controlling devices, referred to as Autonomic Managers (AMs). However, existing solutions are limited to use either a centralized AM or an AM per service for managing a whole SBP. It is obvious that the latter solution is resource consuming and may lead to conflicting management decisions, while the former one may lead to management bottlenecks. An important problem in this context, deals with finding the optimal number of AMs for the management of an SBP, minimizing costs in terms of number of AMs while at the same time avoiding management bottlenecks and ensuring good management performance. Moreover, due to the heterogeneity of cloud resources and the diversity of the required quality of service (QoS) of SBPs, the allocation of cloud resources to these AMs may result in high computing costs and an increase in the communication overheads and/or lower QoS. It is also crucial to find an optimal allocation of cloud resources to the AMs, minimizing costs while at the same time maintaining the QoS requirements. To address these challenges, in this work, we propose a deterministic optimization model for each problem. Furthermore, due to the amount of time needed to solve these problems that grows exponentially with the size of the problem, we propose near-optimal algorithms that provide good solutions in reasonable time

Bausteine auf dem Weg zur in-vivo Roboterevolution. Ein in unbekannter Umgebung agierender autonomer Roboter muss Probleme der Positionsbestimmung, Navigation, Rückkehr zur Basisstation etc. sicher lösen, um seine eigentliche Aufgabe durchführen zu können. In der Vergangenheit wurden verschiedene Ansätze entwickelt, um z.B. die Positionsbestimmung [HPG97][SG98] und Navigation [MLP+98][MM80] zu verbessern oder um effiziente Controller zu entwickeln. Dabei zeigte sich, dass viele Verfahren, die mit Computersimulation entwickelt wurden, nur nach starken Anpassungen für eine bestimmte Hardware ausreichend gut funktionierten. Die bei den meist vereinfachten Computermodellen weggelassenen Eigenschaften der Hardware und die Differenzen von simulierter und realer Welt verursachen oft unvorhergesehene Nebeneffekte. Deshalb ist es notwendig, die neuen Algorithmen und Verfahren auch an 'richtiger' Hardware zu erproben. Im folgenden wird eine Entwicklungsumgebung vorgestellt, mit der neue Algorithmen an konkreter Hardware getestet werden können.

Diese Diplomarbeit gliedert sich in zwei Teile. Der erste Teil beschäftigt sich mit der Implementation einer Bibliothek zur Simulation künstlicher neuronaler Netze. Der zweite Teil untersucht und vergleicht verschiedene Lernverfahren zur Steuerung autonomer Roboter. Bei der Implementation der Lernverfahren wird dabei die Netzwerk-Bibliothek als Grundlage benutzt.

Ein alltagstauglicher autonomer Assistenzroboter in einem gemeinsamenArbeitsumfeld mit dem Menschen erfordert, dass der Roboter sämtliche Hindernisse in seiner Umgebung wahrnimmt und diesen sicher ausweicht. Stand der Technik ist jedoch, dass meist nur 2D-Sensordaten zur Navigation herangezogen werden. Oder es werden3D-Verfahren verwendet, die ausschließlich mit einer speziellen Sensorkonfiguration arbeiten. Diese Arbeit untersucht im Rahmen des LiSA-Projekts wie 3D-Sensordaten effizient und flexibel zur sicheren Navigation eines autonomenAssistenzsystems eingesetzt werden können. Dazu wird in dieser Arbeit mit der Virtual Range Scans (VRS)-Methode ein Verfahren zurHindernisvermeidung entwickelt, das beliebige Konfigurationen von Abstandssensoren in den Hindernisvermeidungsprozess integriert. Das Verfahren nutztklassische Verfahren zur 2D-Hindernisvermeidung, um 3D-Hindernisvermeidung zu realisieren. Dadurch wird das VRS-Verfahren unabhängig von der Hindernisvermeidungsstrategie und kann flexibel bestehende Verfahren wiederverwenden. Neben der Hindernisvermeidung wird gezeigt, wie die reichereUmgebungsinformation, die in 3D-Sensordaten vorhanden ist, zur robusteren Selbstlokalisierung des Roboters genutzt werden kann. Hier wird eineffizientes Verfahren vorgestellt, das Abstandssensordaten mit 3D-Umgebungsmodellen vergleicht. Ferner wird ein Verfahren vorgestellt, das Semantikim Umfeld des Roboters verankert und sie zur Navigation des Roboters nutzt.

Damit mobile Roboter vielfältige komplexe Aufgaben autonom erfüllen können, benötigen sie Planung, um so entsprechend der Gegebenheiten ihrer Umgebung zu handeln. Durch die stetig zunehmenden Fähigkeiten der Roboterhardware gewinnt die Handlungsplanung und deren Integration in das Gesamtsystem zunehmend an Bedeutung. Die vorliegende Arbeit versucht, einen weiteren Schritt Richtung planbasierter Robotersteuerung zu gehen. Dabei wird zunächst die Verwendung des HTN-Planers SHOP2 in einem Robotersystem, das sich das Lernen aus Erfahrungen zum Ziel gesetzt hat, beschrieben und Wege aufgezeigt, wie die Robustheit des Systems durch die Integration mit anderen Komponenten erhöht werden kann. Mobilen Robotern stehen unterschiedliche Formen von Wissen, wie temporales oder räumliches Wissen oder Informationen über Ressourcen zur Verfügung. Diese können von SHOP2 jedoch nicht genutzt werden. Um diese Anforderung zu erfüllen, wird in dieser Arbeit der hybride hierarchische Planer CHIMP präsentiert, der die Vorteile hierarchischer Planung und der hybriden Planung als Meta-CSP, das die Integration verschiedener Wissensformen erlaubt, kombiniert. Des Weiteren können seine Pläne parallel ausführbare Aktionen enthalten, und zusätzliche Aufgaben können während der Ausführung in den bestehenden Plan integriert werden.

Internet est le résultat de l’interaction des milliers de réseaux qui le composent. On les appelle les systèmes autonomes, chacun est identifié par un numéro unique (ASN). Les politiques de routage des AS et les accords économiques restent confidentiels normalement. Afin de mieux comprendre le routage dans l’Internet, les chercheurs modèlent le routage. Le model souvent utilisé c’est la représentation d’un AS par un atome. Nous présentons trois contributions dans ce travail. On montre d’abord des contradictions entre les décisions de routage réellement faites et les inférences à partir d’un ensemble d’hypothèses souvent utilisées. 70% des instances de ce qu’on appelle «plusieurs sorties» montrent des incohérences. Le routage est appelé à plusieurs sorties quand un AS utilise simultanément plusieurs routes vers la même destination, et chacune passe par un AS différent. Notre deuxième contribution est sur les routes BGP erronées causées par des mauvaises configurations liées à la transaction de la représentation des ASNs de 16-bits à 32-bits et l’utilisation d’AS23456 pour assurer la compatibilité. Nous montrons que tels erreurs sont encore présentes, ensuite nous montrons les effets des routes qui contiennent AS23456 sur les travaux qui emploient ces routes. Notre dernière contribution concerne les dynamiques de de routage dans l’Internet. Nous proposons une méthode pour quantifier ces dynamiques dans chaque AS afin d’en extraire ceux les plus dynamiques. Ensuite, on se concentre sur l’AS Level 3, l’AS le plus dynamique. Nous expliquons que la raison pour ce grand nombre de dynamique c’est l’équilibration de charge entre des routeurs qui avait plusieurs liens physiques. / Internet is the result of interaction of the thousands of networks that compose it. Each of them is called an autonomous system (AS) and has a unique number (ASN). Routing policies of ASes and business agreements remain in most cases confidential. To understand Internet routing, researchers use routing models. A large family of models represents an AS as an atomic structure. We make in this work three contributions. We look first on a set of commonly made assumptions to show using what we call multi-exit routing contradictions in routing decisions between real routing observed in publicly available measurements and that inferred from the assumptions. Sometimes, more than 70% of multi-exit instances show incoherencies. Multi-exit routing happens when an AS uses simultaneously different routes to a destination, each passing through a different AS. Our second contribution concerns erroneous BGP routes due to misconfigurations in BGP routers related to AS_TRANS, the solution introduced to assure the compatibility with old BGP routers when the change was made to represent ASNs on 32-bits instead of 16-bits. We show that such errors are indeed present, then we show how they can affect work making use of routes carrying this ASN. Our last contribution concerns routing dynamics in the Internet. We propose a method to quantity routing dynamics in each AS, then we look on ASes that have a large proportion of dynamics. After that, we focus on the AS Level 3, one of the ASes that we observe to be most dynamic. We explain that one of the reasons of a large part of the observed dynamics is load balancing between routers that have multiple physical links between each of them.

Cette thèse s'inscrit dans le cadre de la conception de véhicules autonomes, et plus spécifiquement de la vérification de contrôleurs de tels véhicules. Nos contributions à la résolution de ce problème sont les suivantes : (1) fournir une syntaxe et une sémantique pour un modèle de systèmes hybrides, (2) étendre les fonctionnalités du model checker statistique Cosmos à ce modèle et (3) valider empiriquement la pertinence de notre approche sur des cas d'étude typiques du véhicule autonome.Nous avons choisi de combiner le modèle des réseaux de Petri stochastiques de haut niveau (qui était le formalisme d'entrée de Cosmos) avec le formalisme d'entrée de Simulink afin d'atteindre un pouvoir d'expression suffisant. En effet Simulink est très largement utilisé dans le domaine automobile et de nombreux contrôleurs sont spécifiés avec cet outil. Or Simulink n'a pas de sémantique formellement définie. Ceci nous a conduit à concevoir une telle sémantique en deux temps : tout d'abord en introduisant une sémantique dite exacte mais qui n'est pas opérationnelle puis en la complétant par une sémantique approchée intégrant le facteur d'approximation recherché.Afin de combiner le modèle à événements discrets des réseaux de Petri et le modèle continu spécifié en Simulink, nous avons proposé au niveau syntaxique une interfacereposant sur de nouveaux types de transitions et au niveau sémantique une extension de la boucle de simulation. L'évaluation de ce nouveau formalisme a été entièrement implémentée dans Cosmos.Grace à ce nouveau formalisme, nous avons développé et étudié les deux cas d'étude suivants : d'une part une circulation dense sur une section d'autoroute et d'autre part l'insertion du véhicule dans une voie rapide. L'analyse des modélisations correspondantes a démontré la pertinence de notre approche. / This thesis takes place in the context of autonomous vehicle design, and concerns more specifically the verification of controllers of such vehicles. Our contributions are the following: (1) give a syntax and a semantics for a hybrid system model, (2) extend the capacities of the model-checker Cosmos to that kind of models, and (3) empirically confirm the relevance of our approach on typical case studies handling autonomous vehicles.We chose to combine high-level stochastic Petri nets (which is the input formalism of Cosmos) with the input formalism of Simulink, to obtain an adequate expressive power. Indeed, Simulink is largely used in the automotive industry and numerous controllers have been specified using this tool. However, there is no formal semantics for Simulink, which lead us to define such a semantics in two steps:first, we propose an exact (but not operational) semantics, then we complete it by an approximate semantics that includes the targeted approximation level.In order to combine the discrete event model of Petri nets and the continous model specified in Simulink, we define a syntactic interface that relies on new transition types; its semantics consists of an extension of the simulation loop. The evaluation of this new formalism has been entirely implemented into Cosmos.Using this new formalism, we have designed and studied the two following case studies: on one hand, a heavy traffic on a motorway segment, and on the other hand the insertion of a vehicle into a motorway. Our approach has been validated by the analysis of the corresponding models.

La principale difficulté pour la navigation autonome d'un robot dans un environnement partiellement ou totalement inconnu vient naturellement du manque d'informations sur l'environnement : on ne peut assurer que le chemin calculé soit aussi court et aussi sûr que le chemin calculé avec une connaissance parfaite de l'environnement. Les informations sur l'environnement sont obtenues au fur et à mesure de la navigation avec un degré variable de certitude qui dépend de l'environnement lui-même, des capacités de perception et la localisation du véhicule, et c'est l'acquisition des informations pertinentes pour la tâche de navigation qui conditionne sa bonne réalisation. Les travaux proposés sont réalisés dans ce contexte : ils définissent une stratégie de navigation qui est basée sur la détermination des zones où l'information est nécessaire au robot pour atteindre le but. / The main difficulty of autonomous navigation of a mobile robot in a partially comes from the lack of information about the environment. One can not assure the calculated navigation path is as short and as safe as the path calculated if we had all the necessary information on the environment. Information is gathered along the moves of the mobile robot with a varying degree of certainty. This uncertainty come from the environment itself, the perception abilities and the localisation abilities of the robot. Only relevant information acquisitions can help a good execution of the navigation task.The proposed approach is realised in this context : it consists of a navigation strategy based on the determination of zones where information is necessary for the robot to rally its objective.

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