We present an algorithm to explore an orthogonal polygon using a team of p robots. This algorithm combines ideas from information-theoretic exploration algorithms and computational geometry based exploration algorithms. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the offline optimal exploration algorithm. We discuss how this strategy can be adapted to real-world settings to deal with noisy sensors. In addition to theoretical analysis, we investigate the performance of our algorithm through simulations for multiple robots and experiments with a single robot. / Master of Science / In applications such as disaster recovery, the layout of the environment is generally unknown. Hence, there is a need to explore the environment in order to effectively perform search and rescue. Exploration of unknown environments using a single robot is a well studied problem. We present an algorithm to perform the task with a team of p robots for the specific case of orthogonal polygons, i.e. polygonal environments where each side is aligned with either the X or the Y axis. The algorithm is based on a single-robot polygon exploration algorithm and a tree exploration algorithm. We show that the exploration time of our algorithm is competitive (as a function of p) with respect to the optimal offline algorithm. We then optimize the information gain of the path followed by the robots by allowing local detours in order to decrease the entropy in the map.

This thesis provides strategies for multiple vehicles to explore unknown environments in a cooperative and systematic manner. These strategies are called Simultaneous Cooperative Exploration and Networking (SCENT) strategies. As the basis for development of SCENT strategies, we first tackle the motion control and planning for one vehicle with range sensors. In particular, we develop the curve-tracking controllers for autonomous vehicles with rigidly mounted range sensors, and a provably complete exploration strategy is proposed so that one vehicle with range sensors builds a topological map of an environment. The SCENT algorithms introduced in this thesis extend the exploration strategy for one vehicle to multiple vehicles. The enabling idea of the SCENT algorithms is to construct a topological map of the environment, which is considered completely explored if the map corresponds to a complete Voronoi diagram of the environment. To achieve this, each vehicle explores its local area by incrementally expanding the already visited areas of the environment. At the same time, every vehicle deploys communication devices at selected locations and, as a result, a communication network is created concurrently with a topological map. This additional network allows the vehicles to share information in a distributed manner resulting in an efficient exploration of the workspace. The efficiency of the proposed SCENT algorithms is verified through theoretical investigations as well as experiments using mobile robots. Moreover, the resulting networks and the topological maps are used to solve coordinated multi-robot tasks, such as capturing intruders.

Cette thèse s'inscrit dans le cadre du projet Cart-O-Matic mis en place pour participer au défi CAROTTE (CArtographie par ROboT d'un TErritoire) organisé par l'ANR et la DGA. Le but de ce défi est de construire une carte en deux et trois dimensions et de localiser des objets dans un environnement inconnu statique de type appartement. Dans ce contexte, l'utilisation de plusieurs robots est avantageuse car elle permet d'augmenter l'efficacité en temps de la couverture. Cependant, comme nous le montrons, le gain est conditionné par le niveau de coopération entre les robots. Nous proposons une stratégie de coopération pour une cartographie multirobot efficace. Une difficulté est la construction d'une carte commune, nécessaire, afin que chaque robot puisse connaître les zones de l'environnement encore inexplorées. Pour obtenir une bonne coopération avec un algorithme simple nous proposons une technique de déploiement fondée sur le choix d'une cible par chaque robot. L'algorithme proposé cherche à distribuer les robots vers différentes directions. Il est fondé sur le calcul partiel de champs de potentiels permettant à chaque robot de calculer efficacement son prochain objectif. En complément de ces contributions théoriques, nous décrivons le système robotique complet mis en oeuvre au sein de l'équipe Cart-O-Matic ayant permis de remporter la dernière édition du défi CAROTTE / This thesis is part of Cart-O-Matic project set up to participate in the challenge CARROTE (mapping of a territory) organized by the ANR and the DGA. The purpose of this challenge is to build 2D and 3D maps of a static unknown 'apartment-like' environment. In this context, the use of several robots is advantageous because it increases the time efficiency to discover fully the environment. However, as we show, the gain is determined by the level of cooperation between robots. We propose a cooperation strategy for efficient multirobot mapping. A difficulty is the construction of a common map, necessary so that each robot can know the areas of the environment which remain unexplored.For a good cooperation with a simple algorithm we propose a deployment technique based on the choice of a target by each robot. The proposed algorithm tries to distribute the robots in different directions. It is based on calculation of the partial potential fields allowing each robot to compute efficiently its next target. In addition to these theoretical contributions, we describe the complete robotic system implemented in the Cart-O-Matic team that helped win the last edition of the CARROTE challenge

Cette thèse explore les capacités d’une intelligence ambiante équipée d’un réseau de capteurs de pression au sol. Elle traite le problème de la perception d’un environnement au travers un réseau de capteurs de basse résolution. Les difficultés incluent l’interpretation des poids dispersés pour des objets avec multiples supports, l’ambiguïté de poids entre des objets, la variation du poids des personnes pendant les activités dynamiques, etc. Nous introduisons des nouvelles techniques, partiellement inspirées du domaine de la vision par l’ordinateur, pour la détection, le suivi et la reconnaissance des entités qui se trouvent sur le sol. Nous introduisons également des nouveaux modes d’interaction entre les environnements équipés de tels capteurs aux sols, et les robots qui évoluent dans ces environnements. Ceci permet l’interprétation non-intrusive des événements qui ont lieu dans des environnements dotés d’une intelligence ambiante, avec des applications dans l’assistance automatisée à domicile, l’aide aux personnes âgées, le diagnostic continu de la santé, la sécurité, et la navigation robotique / This thesis explores the capabilities of an ambient intelligence equipped with a load-sensing floor. It deals with the problem of perceiving the environment through a network of low-resolution sensors. Challenges include the interpretation of spread loads for objects with multiple points of support, weight ambiguities between objects, variation of persons’ weight during dynamic activities, etc. We introduce new techniques, partly inspired from the field of computer vision, for detecting, tracking and recognizing the entities located on the floor. We also introduce new modes of interaction between environments equipped with such floor sensors and robots evolving inside them. This enables non-intrusive interpretation of events happening inside environments with embedded ambient intelligence, with applications in assisted living, senile care, continuous health diagnosis, home security, and robotic navigation