Made available in DSpace on 2014-12-17T14:54:56Z (GMT). No. of bitstreams: 1 AndreMS_TESE_1-100.pdf: 5113772 bytes, checksum: 19386f80f787c926c4fb29b85bac4ecf (MD5) Previous issue date: 2011-02-11 / The goal of this work is to propose a SLAM (Simultaneous Localization and Mapping) solution based on Extended Kalman Filter (EKF) in order to make possible a robot navigates along the environment using information from odometry and pre-existing lines on the floor. Initially, a segmentation step is necessary to classify parts of the image in floor or non floor . Then the image processing identifies floor lines and the parameters of these lines are mapped to world using a homography matrix. Finally, the identified lines are used in SLAM as landmarks in order to build a feature map. In parallel, using the corrected robot pose, the uncertainty about the pose and also the part non floor of the image, it is possible to build an occupancy grid map and generate a metric map with the obstacle s description. A greater autonomy for the robot is attained by using the two types of obtained map (the metric map and the features map). Thus, it is possible to run path planning tasks in parallel with localization and mapping. Practical results are presented to validate the proposal / O objetivo desta tese ? apresentar uma t?cnica de SLAM (Localiza??o e Mapeamento Simult?neos) adequada para ambientes planos com linhas presentes no ch?o, de modo a permitir que o rob? navegue no ambiente fundindo informa??es de odometria e de vis?o monocular. Inicialmente, ? feita uma etapa de segmenta??o para classificar as partes da imagem em ch?o e n?o-ch?o . Em seguida, o processadomento de imagem identifica linhas na parte ch?o e os par?metros dessas linhas s?o mapeados para o mundo, usando uma matriz de homografia. Finalmente, as linhas identificadas s?o usadas como marcos no SLAM, para construir um mapa de caracter?sticas. Em paralelo, a pose corrigida do rob?, a incerteza em rela??o ? pose e a parte n?och?o da imagem s?o usadas para construir uma grade de ocupa??o, gerando um mapa m?trico com descri??o dos obst?culos. A utiliza??o simult?nea dos dois tipos de mapa obtidos (m?trico em grade e de caracter?sticas) d? maior autonomia ao rob?, permitindo acrescentar tarefas de planejamento em simult?neo com a localiza??o e mapeamento. Resultados pr?ticos s?o apresentados para validar a proposta

The focus of this thesis is to theoretically design, describe, implement and verify thefunctionality of the selected concept for race track mapping. The theoretical part ofthe thesis describes the ORB-SLAM2 algorithm for vehicle localization. It then furtherdescribes the format of the map - occupancy grid and the method of its creation. Suchmap should be in a suitable format for use by other trajectory planning systems. Severalcameras, as well as computer units, are described in this part, and based on parametersand tests, the most suitable ones are selected. The thesis also proposes the architectureof the mapping system, it describes the individual units that make up the system, aswell as what is exchanged between the units, and in what format the system output issent. The individual parts of the system are first tested separately and subsequently thesystem is tested as a whole. Finally, the achieved results are evaluated as well as thepossibilities for further expansion.

In this thesis, an exploration mode for the PUREi9 robotic vacuum cleaner is implemented. This exploration would provide information for optimizing the cleaning path beforehand, and would allow the robot to relocalize itself or the charger more easily in case it gets lost. Two elements are needed in order to implement an exploration mode; first, an exploration algo-rithm which will decide the next position of the robot in order to obtain useful information about the environment (unknown areas, empty spaces, obstacles...), and second, an exploration map which stores that information and is updated each time a new relevant position is reached. These elements are related and generally both are required for performing successfully the exploration of a specific environment. A frontier-based strategy is adopted for the exploration algorithm, together with occupancy grid maps. This strategy has long been regarded as a key method for autonomous robots working in unknown or changing environments. The idea of frontier-based algorithms is to divide the environ-ment into cells of regular size and drive the robot to the frontiers between cells with no obstacles and cells for which no information has been gathered. It plans one step ahead by choosing a lo-cation which provides new environment information, instead of planning in advance all locations where the robot needs to acquire new sensor information. Based on frontier strategy, two different exploration algorithms are implemented in the project. The first one is called "random frontier strategy", which chooses arbitrarily the frontier to go among the frontiers set. The second is called "closest frontier strategy", which chooses the closest frontier as the NBV (Next Best View) the robot should drive to. A path planning algorithm, based on Dijkstra’s algorithm and a node graph, has also been implemented in order to guide the robot towards the frontiers. The two methods have been compared by means of simulations in different environments. In addition, both exploration strategies have been tested on a real device. It is found that the closest frontier strategy is more efficient in terms of path length between scanning points, while both methods give a similar exploration ratio, or percentage of fully explored cells within the final map. Some additional work is required in order to improve the performance of the exploration method in the future, such as detecting unreachable frontiers, implementing a more robust path planning algorithm, or filtering the laser measurements more extensively. / I den här rapporten har vi implementerat en utforskningsmod för robotdammsugaren Pure i9. Sådan utforskning skulle ge underlag för att optimera städmönstret i förhand och låta roboten relokalisera sig själv eller laddaren om den tappar bort sig. För att implementera utforskning behövs två saker. För det första krävs en algoritm för utforsk-ning, som bestämmer nästa position för roboten, med målet att samla användbar information om omgivningen (okända eller fria områden, hinder etc.) För det andra krävs en karta som lagrar informationen och uppdateras varje gång roboten når en relevant ny position. Dessa två hänger ihop och i allmänhet krävs båda för att framgångsrikt utforska ett specifikt område. Vi har valt en front-baserad strategi för utforskningsalgoritmen, tillsammans med en rutnäts-karta med sannolikheten för hinder. Denna strategi har länge betraktats som en nyckelmetod för autonoma robotar som arbetar i okända eller föränderliga miljöer. Idén med front-baserade strate-gier är att köra roboten till fronterna mellan celler utan hinder och celler där information saknas. Den planerar ett steg framåt genom att välja en plats som ger ny information om miljön, istället för att i förväg planera alla platser där roboten behöver samla in ny sensorinformation. Baserat på front-strategi, har vi implementerat två utforskningsalgoritmer i projektet. Den första är en slumpmässig strategi, som godtyckligt väljer en front att åka till, ur hela mängden av fronter. Den andra är en närmaste fronten-strategi som väljer den närmaste fronten som den nästa bästa utsiktspunkt som roboten ska åka till. Vi har också implementerat en algoritm för banplanering, baserad på Dijkstras algoritm och en nod-graf, för att styra roboten mot fronterna. Vi har jämfört de två metoderna genom simulering i olika miljöer. Dessutom har båda utforsk-ningsstrategierna testats på en riktig enhet. Närmaste fronten-strategin är effektivare med avse-ende på banlängd mellan skanningspunkter, medan båda metoderna ger liknande utforsknings-grad, eller samma procentandel av fullt utforskade celler inom den slutliga kartan.