Thesis (MScEng)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: This project concerns motion planning for a rotary wing UAV, where vehicle controllers are already in place, and map data is readily available to a collision detection module. In broad terms, the goal of the motion planning algorithm is to provide a safe (i.e. obstacle free) flight path between an initial- and goal waypoint. This project looks at two specific motion planning algorithms, the Rapidly Exploring Random Tree (or RRT*), and the Probabilistic Roadmap Method (or PRM). The primary focus of this project is learning how these algorithms behave in specific environments and an in depth analysis is done on their differences. A secondary focus is the execution of planned paths via a Simulink simulation and lastly, this project also looks at the effect of path replanning. The work done in this project enables a rotary wing UAV to autonomously navigate an uncertain, dynamic and cluttered environment. The work also provides insight into the choice of an algorithm for a given environment: knowing which algorithm performs better can save valuable processing time and will make the entire system more responsive. / AFRIKAANSE OPSOMMING: ’n Tipiese vliegstuuroutomaat is daartoe in staat om ’n onbemande lugvaartvoertuig (UAV) so te stuur dat ’n stel gedefinieerde punte gevolg word. Die punte moet egter vooraf beplan word, en indien enige verandering nodig is (bv. as gevolg van veranderinge in die omgewing) is dit nodig dat ’n menslike operateur betrokke moet raak. Vir voertuie om ten volle outonoom te kan navigeer, moet die voertuig in staat wees om te kan reageer op veranderende situasies. Vir hierdie doel word kinodinamiese beplanningsalgoritmes en konflikdeteksiemetodes gebruik. Hierdie projek behels kinodinamiese beplanningsalgoritmes vir ’n onbemande helikopter, waar die beheerders vir die voertuig reeds in plek is, en omgewingsdata beskikbaar is vir ’n konflikdeteksie-module. In breë terme is die doel van die kinodinamiese beplanningsalgoritme om ’n veilige (d.w.s ’n konflikvrye) vlugpad tussen ’n begin- en eindpunt te vind. Hierdie projek kyk na twee spesifieke kinodinamiese beplanningsalgoritmes, die “Rapidly exploring Random Tree*” (of RRT*), en die “Probabilistic Roadmap Method” (of PRM). Die primêre fokus van hierdie projek is om die gedrag van hierdie algoritmes in spesifieke omgewings te analiseer en ’n volledige analise te doen op hul verskille. ’n Sekondêre fokus is die uitvoering van ’n beplande vlugpad d.m.v ’n Simulink-simulasie, en laastens kyk hierdie projek ook na die effek van padherbeplanning. Die werk wat gedoen is in hierdie projek stel ’n onbemande helikopter in staat om outonoom te navigeer in ’n onsekere, dinamiese en besige omgewing. Die werk bied ook insig in die keuse van ’n algoritme vir ’n gegewe omgewing: om te weet watter algoritme beter uitvoertye het kan waardevolle verwerkingstyd bespaar, en verseker dat die hele stelsel vinniger kan reageer.

Veículos autônomos são objeto de crescente estudo em todo o mundo. Face à Engenharia de Transportes, é tema que deve provocar uma revolução nas próximas décadas, pois é concreta a tendência ao uso destes veículos na sociedade. Podem se citar como grandes beneficiados a segurança, a logística, o fluxo de trânsito, o meio ambiente e também os portadores de deficiências. Com o objetivo de fazer um veículo atingir um ponto com coordenadas conhecidas de forma autônoma, uma plataforma veicular terrestre em escala foi utilizada, a qual recebeu um sistema computacional micro controlado e tecnologias para proporcionar mobilidade através de motores elétricos para tração e servo-motores para direcionamento; posicionamento por satélite através de receptor GNSS e bússola eletrônica para orientação; sensoriamento por ultra-som para evitar colisões; e comunicação sem fio, a fim de se realizar remotamente monitoramento e instrução em tempo real através de um aplicativo para computador pessoal (PC). Foi desenvolvido um algoritmo de navegação que, fazendo uso dos recursos disponíveis, proporcionou autonomia ao veículo, de forma a navegar para pontos com coordenadas conhecidas sem controle humano. Os testes realizados visaram avaliar a capacidade de autonomia do veículo, a trajetória de navegação realizada e a acurácia de chegada aos pontos de destino. O veículo foi capaz de atingir os pontos em todos os testes realizados, sendo considerado funcional seu algoritmo de navegação e também os sistemas de mobilidade, posicionamento, sensoriamento e comunicação. / Autonomous vehicles are an on growing research target around the world. Face to Transports Engineering, it is a subject which is expected to make a revolution on the next decades. The great benefits are on security, logistic, traffic flow, environment and handicap. With the goal to make a vehicle navigate autonomously to known geodesics coordinates, a reduced scale terrestrial vehicular platform was used. This platform received a microcontrolled computational system and technologies to give it mobility, through electrical motors for traction and servo-motors for direction; satellite positioning, through a GNSS receiver and magnetic compass for orientation; ultrasound sensing in order to avoid collision; and wireless communication, in order to do remote monitoring and instruction at real time through a PC application. It was developed a navigation algorithm which, from the available resources, gave autonomy to the vehicle, in order to navigate to known geodesics coordinates without human control. The test set was intended to evaluate the autonomy capacity of the vehicle, the navigation trajectory that was done and the arrival accuracy to the destination points. The vehicle reached the destination points on all tests done, being evaluated as functional its navigation algorithm and also the mobility, positioning, sensing and communication systems.

A navegação autônoma é uma tarefa fundamental na robótica móvel. Para que esta tarefa seja realizada corretamente é necessário um sistema inteligente de controle e navegação associado ao sistema sensorial. Este projeto apresenta o desenvolvimento de um sistema de controle para a navegação de veículos e robôs móveis autônomos. A abordagem utilizada neste trabalho utiliza Redes Neurais Artificiais para o aprendizado de Autômatos Finitos de forma que os robôs possam lidar com os dados provenientes de seus sensores mesmo estando sujeitos a imprecisões e erros e ao mesmo tempo permite que sejam consideradas as diferentes situações e estados em que estes robôs se encontram (contexto). Dessa forma, é possível decidir como agir para realizar o controle da sua movimentação, e assim executar tarefas de controle e navegação das mais simples até as mais complexas e de alto nível. Portanto, esta dissertação visa utilizar Redes Neurais Artificiais para reconhecer o estado atual (contexto) do robô em relação ao ambiente em que está inserido. Uma vez que seja identificado seu estado, o que pode inclusive incluir a identificação de sua posição em relação aos elementos presentes no ambiente, o robô será capaz de decidir qual a ação/comportamento que deverá ser executado. O sistema de controle e navegação irá implementar um Autômato Finito que a partir de um estado atual define uma ação corrente, sendo capaz de identificar a mudança de estados, e assim alternar entre diferentes comportamentos previamente definidos. De modo a validar esta proposta, diversos experimentos foram realizados através do uso de um simulador robótico (Player-Stage), e através de testes realizados com robôs reais (Pioneer P3-AT, SRV-1 e veículos automatizados) / Autonomous navigation is a fundamental task in mobile robotics. In order to accurately perform this task it is necessary an intelligent navigation and control system associated to the sensorial system. This project presents the development of a control system for autonomous mobile robots and vehicles navigation. The adopted approach uses Artificial Neural Networks for Finite State Machine learning, allowing the robots to deal with sensorial data even when this data is not precise and correct. Simultaneously, it allows the robots to consider the different situations and states they are inserted in (context detection). This way, it is possible to decide how to proceed with motion control and then execute navigation and control tasks from the most simple ones until the most complex and high level tasks. So, this work uses Artificial Neural Networks to recognize the robots current state (context) at the environment where it is inserted. Once the state is detected, including identification of robots position according to environment elements, the robot will be able to determine the action/- behavior to be executed. The navigation and control system implements a Finite State Machine deciding the current action from current state, being able to identify state changes, alternating between different previously defined behaviors. In order to validade this approach, many experiments were performed with the use of a robotic simulator (Player-Stage), and carrying out tests with real robots (Pioneer P3-AT, SRV-1 and autonomous vehicles)

Este trabalho apresenta um novo método de detecção de obstáculos usados para navegação de um barco autônomo. O método desenvolvido é baseado em visão computacional e permite medir a distância e direção do obstáculo à câmera de video. A distância do possível obstáculo à câmera de vídeo, e o vetor de contorno predominante da imagem são os parâmetros usados para identificar os obstáculos. Imagens estereoscópicas adquiridas nas margens da lago do clube Náutico de Araraquara, usando bóias de navegação como obstáculos, foram usadas para extrair as características significantes das experiências. Para validar a experiência, foram utilizadas imagens do Reservatório do Broa (Itirapina, SP). A proposta desenvolvida mostrou ser mais eficiente que o método tradicional usando a teoria de Campos Potenciais. As imagens foram propositadamente tomadas contra o sol, onde o brilho das ondas são erroneamente indicadas como obstáculos pelo método de campos potenciais. Esta proposta filtra as ondas de forma a diminuir sua interferência no diagnóstico. / This work presents the results of new obstacle detection methods used for an autonomous boat navigation. The developed method is based on computer vision and allows to measure the distance and direction of the obstacle to the boat. The distance of the possible obstacle to the camera, and the obstacle outline predominant vector are the parameters used to identify the obstacles. Stereo images acquired from the margins of the Nautical Araraquara lake, using navigation buoys as obstacles, were used to extract the meaningful characteristics of the experiments. To validate the experiment, images from the Broa Reservoir (Itirapina, SP) where used. The developed proposal showed to be more efficient than the traditional method using the potential fields theory. The images were taken willfully against the sun, where the brightness of the waves are erroneously identified as obstacles by the method of potential fields. This method filters the waves so as to reduce its interference in the diagnosis.

Este trabalho apresenta um sistema de navegação autônoma para veículos terrestres com foco em ambientes não estruturados, tendo como principal meta aplicações em campos abertos com vegetação esparsa e em cenário agrícola. É aplicada visão computacional como sistema de percepção principal utilizando uma câmera estéreo em um veículo com modelo cinemático de Ackermann. A navegação é executada de forma deliberativa por um planejador baseado em malha de estados sobre um mapa de custos e localização por odometria e GPS. O mapa de custos é obtido através de um modelo de ocupação probabilístico desenvolvido fazendo uso de uma OctoMap. É descrito um modelo sensorial para atualizar esta OctoMap a partir da informação espacial proveniente de nuvens de pontos obtidas a partir do método de visão estéreo. Os pontos são segmentados e filtrados levando em consideração os ruídos inerentes da aquisição de imagens e do processo de cálculo de disparidade para obter a distância dos pontos. Os testes foram executados em ambiente de simulação, permitindo a replicação e repetição dos experimentos. A modelagem do veículo foi descrita para o simulador físico Gazebo de acordo com a plataforma real CaRINA I (veículo elétrico automatizado do LRM-ICMC/USP), levando-se em consideração o modelo cinemático e as limitações deste veículo. O desenvolvimento foi baseado no ROS (Robot Operating System) sendo utilizada a arquitetura básica de navegação deste framework a partir da customização dos seus componentes. Foi executada a validação do sistema no ambiente real em cenários com terreno irregular e obstáculos diversos. O sistema apresentou um desempenho satisfatório tendo em vista a utilização de uma abordagem baseada em apenas uma câmera estéreo. Nesta dissertação são apresentados os principais componentes de um sistema de navegação autônoma e as etapas necessárias para a sua concepção, assim como resultados de experimentos simulados e com o uso de um veículo autônomo real / This work presents a system for autonomous vehicle navigation focusing on unstructured environments, with the primary goal applications in open fields with sparse vegetation, unstructured environments and agricultural scenario. Computer vision is applied as the main perception system using a stereo camera in a car-like vehicle with Ackermann kinematic model. Navigation is performed deliberatively using a path planner based on a lattice state space over a cost map with localization by odometry and GPS. The cost map is obtained through a probabilistic occupation model developed making use of an OctoMap. It is described a sensor model to update the spatial occupancy information of the OctoMap from a point cloud obtained by stereo vision. The points are segmented and filtered taking into account the noise inherent in the image acquisition and calculation of disparity to obtain the distance from points. Tests are performed in simulation, allowing replication and repetition of experiments. The modeling of the vehicle is described to be used in the Gazebo physics simulator in accordance with the real platform CaRINA I (LRM-ICMC/USP automated electrical vehicle) taking into account the kinematic model and the limitations of this vehicle. The development is based on ROS (Robot Operating System) and its basic navigation architecture is customized. System validation is performed on real environment in scenarios with different obstacles and uneven terrain. The system shows satisfactory performance considering a simple configuration and an approach based on only one stereo camera. This dissertation presents the main components of an autonomous navigation system and the necessary steps for its conception as well as results of experiments in simulated and using a real autonomous vehicle

L’autonomie d’un agent mobile se définit par sa capacité à naviguer dans un environnement sans intervention humaine. Cette tâche s’avère très demandée pour les robots d’assistance à la personne. C’est pour cela que notre contribution s’est portée en particulier sur l’instrumentation et l’augmentation de l’autonomie d’un fauteuil roulant pour les personnes à mobilité réduite. L’objectif de ce travail est de concevoir des lois de commande qui permettent à un robot de naviguer en temps réel et en toute autonomie dans un environnement inconnu. Un cadre de perception virtuelle unifié est introduit et permet de projeter l’espace navigable obtenu par des observations éventuellement multiples. Une approche de navigation autonome et sûre a été conçue pour se déplacer dans un environnement peu encombré dont la structure peut être assimilée à un couloir (lignes au sol, murs, délimitation herbes, routes...). La problématique a été résolue en utilisant le formalisme de l’asservissement visuel. Les caractéristiques visuelles utilisées dans la loi de commande ont été construites à partir de la représentation virtuelle (à savoir la position du point de fuite et l’orientation de la ligne médiane du couloir). Pour assurer une navigation sûre et lisse, même lorsque ces paramètres ne peuvent pas être extraits, nous avons conçu un observateur d’état pour estimer les caractéristiques visuelles dans le but de maintenir la commande fonctionnelle du robot. Cette approche permet de faire naviguer un robot mobile dans un couloir même en cas de défaillance sensorielle (données non fiables) et/ou de perte de mesure. La première contribution de cette thèse a été étendue en traitant tout type d’environnement encombré statique ou dynamique. Cela a été réalisé en utilisant le diagramme de Voronoï. Le diagramme de Voronoï généralisé, également appelé squelette, est une représentation puissante de l’environnement. Il définit un ensemble de chemins à la distance maximale des obstacles. Dans ce travail, une approche d’asservissement visuel basée sur le squelette extrait en temps réel était proposée pour une navigation autonome et sûre des robots mobiles. La commande est basée sur une approximation du DVG local en utilisant le Delta Medial axis, un algorithme de squelettisation rapide et robuste. Ce dernier produit un squelette filtré de l’espace libre entourant le robot en utilisant un paramètre qui prend en compte la taille du robot. Cette approche peut faire face aux bruits de mesure au niveau de la perception et au niveau de la commande à cause des glissement des roues. C’est pour cela que nous avons conçu une approche d’asservissement visuel sur une prédiction d’une linéarisation du DVG. Une analyse complète a été réalisée pour montrer la stabilité des lois de commandes proposées. Des simulations et des tests expérimentaux valident l’approche proposée. / The autonomy of a mobile agent is defined by its ability to navigate in an environment without human intervention. This task is very required for personal assistance robots. That’s why our contribution has been particularly focused on instrumentation and increasing the autonomy of a wheelchair for reduced mobility peaple. The objective of this work is to design control laws that allow a robot to navigate in real time and independently in an unknown environment. A unified virtual perception framework is introduced and allows to project the navigable space obtained by possibly multiple observations. First we designed an autonomous and safe navigation approach in environment whose structure can be assimilated to a corridor (lines on the ground, walls, delimitation of grasses, roads ...). We have solved this problem by using the formalism of visual servoing. The visual characteristics used in the control law were constructed from the virtual representation (ie the position of the vanishing point and the orientation of the center line of the corridor). To ensure safe and smooth navigation, even when these parameters can not be extracted, we have designed a finite-time state observer to estimate the visual characteristics in order to maintain the robot’s control efficient. This approach let a mobile robot navigate in a corridor even in in the case of sensory failure (unreliable data) and/or loss of measurement. We have extended the first contribution of this work with dealing with any type of static or dynamic environment. This was done using the Voronoi diagram. The Generalized Voronoi Diagram (GVD), also named skeleton, is a powerful environment representation, since, among other reasons, it defines a set of paths at maximal distance from the obstacles. In this work, a real time skeleton based visual servoing approach is proposed for a safe autonomous navigation of mobile robots. The control is based on an approximation of the local GVD using the Delta Medial Axis, a fast and robust skeletonization algorithm. The latter produces a filtered skeleton of the free space surrounding the robot using a pruning parameter that takes into account the robot size. This approach can cope with measurement noises at the perception and control with the wheel slip. This is why we have designed a visual servoing approach on a prediction of a GVD linearization. A complete analysis was performed to show the stability of the proposed control laws. Simulations and experimental tests validate the proposed approach.

Dans le cadre du programme ExoMars, l’ESA va déployer un rover sur Mars dont la mission sera de réaliser des prélèvements d’échantillons par forage souterrain et les analyser à l’aide des instruments scientifiques embarqués. Pour atteindre en toute sécurité les différents points d’intérêt où seront effectués ces prélèvements, le rover devra être capable de parcourir plus de 70 mètres par sol (jour martien) tout en respectant les limitations des communications interplanétaires. Les performances des algorithmes de navigation autonome embarqués impacteront directement la réussite scientifique de cette mission. Le premier objectif de cette thèse est d’améliorer les performances de l’architecture de planification de chemin local itératif proposée par le CNES. Tout d’abord, l’utilisation d’un planificateur incrémental de chemin local ”Fringe Retrieving A∗” permettant de réduire la charge de calcul est proposée. Il est complété par l’introduction de tas binaires dans les structures de gestion de la liste de priorité du planificateur de chemin.Ensuite, les manœuvres de rotation sur place pendant l’exécution des trajectoires sont réduites à l’aide d’un planificateur de chemins non-holonomes. Ce planificateur utilise un ensemble de chemins pré-calculés en tenant compte des capacités de braquage du rover. Le second axe de recherche concerne la planification de chemin global d’un rover d’exploration planétaire. Dans un premier temps, la contrainte de mémoire embarquée est détendue et une étude statistique évalue la pertinence d’un planificateur de chemin de type D∗ lite. Dans un deuxième temps, une nouvelle représentation multi-résolution de la carte de navigation est proposée pour stocker de plus grandes zones explorées par le rover sans augmenter l’utilisation de la mémoire embarquée. Cette représentation est utilisée par la suite par un planificateur de chemin global qui réduit automatiquement la charge de calcul en adaptant le sens de recherche en fonction de la forme et de la distribution des obstacles dans l’espace de navigation. / ESA’s ExoMars mission will deploy a 300kg class rover on Mars, which will serveas a mobile platform for the onboard scientific instruments to reach safely desired locations where subsurface drilling and scientific measurements are scheduled. Due to the limited inter-planetary communication constraints, full autonomous on board navigation capabilities are crucial as the rover has to drive over 70 meters per sol(Martian day) to reach designated scientific sites. The core of the navigation softwareto be deployed on the ExoMars rover uses as baseline the autonomous navigation architecture developed by CNES during the last 20 years. Such algorithms are designed to meet the mission-specific constraints imposed by the available spatial technology such as energy consumption, memory, computation power and time costs.The first objective of this thesis is to improve the performance of the successive localpath planning architecture proposed by CNES. First, the use of an increment allocal path planner, Fringe Retrieving A∗, is proposed to reduce the path planning computation load. This is complemented by the introduction of binary heaps in the management structures of the path planner. In-place-turn maneuvers during trajectory execution are further reduced by using a state lattice path planner which encodes the steering capabilities of the rover.The second research direction concerns global path planning capabilities for roboticplanetary exploration. First the onboard memory constraints are relaxed and a studyevaluating the use of a global D∗ lite path planner is performed. Second, a novel multi-resolution representation of the navigation map which covers larger areas atno memory cost increase is proposed. It is further used by a global path planner which automatically reduces the computational load by selecting its search direction based on obstacle shapes and distribution in the navigation space.

Autonomous vehicle navigation is a complex and challenging task. Land and aerial vehicles often use highly accurate GPS sensors to localize themselves in their environments. These sensors are ineffective in underwater environments due to signal attenuation. Autonomous underwater vehicles utilize one or more of the following approaches for successful localization and navigation: inertial/dead-reckoning, acoustic signals, and geophysical data. This thesis examines autonomous localization in a simulated environment for an OpenROV Underwater Drone using a Kalman Filter. This filter performs state estimation for a dead reckoning system exhibiting an additive error in location measurements. We evaluate the accuracy of this Kalman Filter by analyzing the effect each parameter has on accuracy, then choosing the best combination of parameter values to assess the overall accuracy of the Kalman Filter. We find that the two parameters with the greatest effects on the system are the constant acceleration and the measurement uncertainty of the system. We find the filter employing the best combination of parameters can greatly reduce measurement error and improve accuracy under typical operating conditions.

Lors de dette dernière décennie, l'évolution des technologies a permis le développement de drones de taille et de poids réduit aptes à évoluer dans des environnements intérieurs ou urbains. Pour exécuter les missions qui leur sont attribuées, les drones doivent posséder un système de navigation robuste, comprenant, notamment, une fonctionnalité temps réel d'ego-localisation précise dans un repère absolu. Nous proposons de résoudre cette problématique par la mise en correspondance des dernières images acquises avec des images géoréférencées de type Google Streetview.Dans l'hypothèse où il serait possible pour une image requête de retrouver l'image géo-référencée représentant la même scène, nous avons tout d'abord étudié une solution permettant d'affiner la localisation grâce à l'estimation de la pose relative entre ces deux images. Pour retrouver l'image de la base correspondant à une image requête, nous avons ensuite étudié et proposé une méthode hybride exploitant à la fois les informations visuelles et odométriques mettant en oeuvre une chaîne de Markov à états cachés. Les performances obtenues, dépendant de la qualité de la mesure de similarité visuelle, nous avons enfin proposé une solution originale basée sur l'apprentissage supervisé de distances permettant de mesurer les similarités entre les images requête et les images géoréférencées proches de la position supposée. / In this last decade, technology evolution has enabled the development of small and light UAV able to evolve in indoor and urban environments. In order to execute missions assigned to them, UAV must have a robust navigation system, including a precise egolocalization functionality within an absolute reference. We propose to solve this problem by mapping the latest images acquired with geo-referenced images, i.e. Google Streetview images.In a first step, assuming that it is possible for a given query image to retrieve the geo-referenced image depicting the same scene, we study a solution, based on relative pose estimation between images, to refine the location. Then, to retrieve geo-referenced images corresponding to acquired images, we studied and proposed an hybrid method exploiting both visual and odometric information by defining an appropriate Hidden Markov Model (HMM), where states are geographical locations. The quality of achieved performances depending of visual similarities, we finally proposed an original solution based on a supervised metric learning solution. The solution measures similarities between the query images and geo-referenced images close to the putative position, thanks to distances learnt during a preliminary step.

Det här examensarbetet är utfört i samarbete med Realisator Robotics, vilka förtillfället utvecklar en robot, FUMO, som ska hjälpa till vid brandbekämpning. Målet med examensarbetet är att implementera autonom navigering från en punkt till en annan samt SLAM (Simultaneous Localisation and Mapping, simultan lokaliseringoch kartläggning) funktionalitet. Dessa funktioners färmåga att hantera rök ska även testas. Efter en inledande litteraturstudie på olika sätt att lösa en robots perception i rök så blev det bestämt att använda en så kallad ”multi-echo LIDAR” som huvudsensor. Alla implementationer är gjorda i robotoperativsystemet ROS och öppenkällkod har använts för vissa funktioner. De första testerna av systemet gjordes i en simulerad miljö. I den så approximerades röken utav Gaussiskt brus. Det blev dock senare fastställt att detta inte lyckas representera alla effekter utav riktig rök. De delar dock vissa beteenden. De slutgiltiga testerna utfördes i en testanläggning för rökdykare, där algoritmerna testades i olika nivåer av rök. Dessa tester visade att multi-echo LIDAR:n klarade av att se igenom lätt till mediumtjock rök, det vill säga rök som kan ses igenom upp till ett par meter med blotta ögat. SLAMalgoritmen kunde i dessa fall generera användbara kartor. När det kontinuerligt lades till ny rök till testområdet så blev kartorna fragmenterade och oläsliga. Den autonoma navigeringen testades inte i rök på grund av säkerhetsrisker. Däremot så testades lokaliseringen som den bygger på genom att manuellt köra roboten genom röken. Resultaten från detta tyder på att det är möjligt att använda den autonoma navigeringen under rökfyllda förhållanden. / This thesis is carried out together with Realisator Robotics who is currently developinga fire-fighting assistant robot, FUMO. The aim of the thesis is to implementautonomous path planning and SLAM (Simultaneous Localisation and Mapping) functionality on the existing FUMO prototype as well as to test how robust these are to smoke. After an initial literature study on different ways of robot perception in smokeit was decided to use a multi-echo LIDAR as the main sensor for these tasks. All implementations were done in ROS (Robot Operating System) and open sourcecode was used for some functions. Testing of the system was first performed in asimulated environment. In this environment smoke was approximated using Gaussiannoise. However it was later concluded that this did not accurately portrayall effects of real smoke. It does however share some similarities. The final tests were performed at a testing facility for smoke divers where the algorithms were tested in different levels of smoke. The tests showed that the multi-echo LIDARmanaged to see through light to medium smoke, in other words smoke which you could see through with your bare eyes to up to a few meters. In those conditions the SLAM algorithm was able to create usable maps. When new smoke was continuously added to the already smoke filled environment the maps became fragmented and unreadable. The autonomous path planning was not tested in smoke due to safety concerns. However the localisation which the path planning is based onwas tested when driving the robot manually through the smoke. The result fromthis hints at a possibility of successfully using the path planning in these conditions.