This thesis describes all the necessary parts needed to build a complete system for autonomous indoor mapping in 3D. The robotic platform used is a two-wheeled Segway, operating in a planar environment. This, together with wheel odometers, an Inertial Measurement Unit (IMU), two Microsoft Kinects and a laptop comprise the backbone of the system, which can be divided into three parts: The localization and mapping part, which fundamentally is a SLAM (simultaneous localization and mapping) algorithm implemented using the registration technique Iterative Closest Point (ICP). Along with the map being in 3D, it also designed to handle the mapping of dynamic scenes, something absent from the standard SLAM design. The planning used by the system is twofold. First, the path planning - finding a path from the current position to a destination - and second, the target planning - determining where to go next given the current state of the map and the robot. The third part of the system is the control and collision systems, which while they have not received much focus, are very necessary for a fully autonomous system. Contributions made by this thesis include: The 3D map framework Octomap is extended to handle the mapping of dynamic scenes; A new method for target planning, based on image processing is presented; A calibration procedure for the robot is derived that gives a full six degree of freedom pose for each Kinect. Results show that our calibration procedure produces an accurate pose for each Kinect, which is crucial for a functioning system. The dynamic mapping is shown to outperform the standard occupancy grid in fundamental situations that arise when mapping dynamic scenes. Additionally, the results indicate that the target planning algorithm provides a fast and easy way to plan new target destinations. Finally, the entire system’s autonomous mapping capabilities are evaluated together, producing promising results. However, it also highlights some problems that limit the system’s performance such as the inaccuracy and short range of the Kinects or noise added and reinforced by the multiple subsystems / Detta exjobb beskriver delarna som krävs för att för bygga ett komplett system som autonomt kartlägger inomhusmiljöer i tre dimensioner. Robotplattformen är en Segway, som är kapabel att röra sig i ett plan. Segwayn, tillsammans med en tröghetssensor, två Microsoft Kinects och en bärbar dator utgör grunden till systemet, som kan delas i tre delar: En lokaliserings- och karteringsdel, som i grunden är en SLAM-algoritm (simultan lokalisering och kartläggning)  baserad på registreringsmetoden Iterative Closest Point (ICP). Kartan som byggs upp är i tre dimensioner och ska dessutom hantera kartläggningen av dynamiska miljöer, något som orginalforumleringen av SLAM problemet inte klarar av. En automatisk planeringsdel, som består av två delar. Dels ruttplanering som går ut på att hitta en väg från sin nuvarande position till det valda målet och dels målplanering som innebär att välja ett mål att åka till givet den nuvarande kartan och robotens nuvarande position. Systemets tredje del är regler- och kollisionssystemen. Dessa system har inte varit i fokus i detta arbete, men de är ändå högst nödvändiga för att ett autonomt system skall fungera. Detta examensarbete bidrar med följande: Octomap, ett ramverk för kartläggningen i 3D, har utökats för att hantera kartläggningen av dynamiska miljöer; En ny metod för målplanering, baserad på bildbehandling läggs fram; En kalibreringsprocedur för roboten är framtagen som ger den fullständiga posen i förhållande till roboten för varje Kinect. Resultaten visar att vår kalibreringsprocedur ger en nogrann pose for för varje Kinect, vilket är avgörande för att systemet ska fungera. Metoden för kartläggningen av dynamiska miljöer visas prestera bra i grundläggande situationer som uppstår vid kartläggning av dynamiska miljöer. Vidare visas att målplaneringsalgoritmen ger ett snabbt och enkelt sätt att planera mål att åka till. Slutligen utvärderas hela systemets autonoma kartläggningsförmåga, som ger lovande resultat. Dock lyfter resultat även fram problem som begränsar systemets prestanda, till exempel Kinectens onoggranhet och korta räckvidd samt brus som läggs till och förstärks av de olika subsystemen.

Dinaminiai kelio paieškos algoritmai apjungia euristinės ir plečiamos (angl. incremental) paieškos metodus, sprendžiant eiles panašių paieškos uždavinių tiek žinant visą informaciją apie aplinką, tiek neturint jokios informacijos. Yra trys plečiamą paiešką naudojančių algoritmų klasės. Šiame darbe pateikiama trumpa dinaminių kelio paieškos algoritmų, naudojančių plečiamos paieškos metodus analizė. Pagrindinis darbo tikslas – visų trijų plečiamos paieškos klasių algoritmų, kuriuos naudojant gaunamas optimalus kelio paieškos sprendinys aplinkose, kur perėjimų tarp viršūnių svoriai gali didėti ir mažėti, palyginimas. Algoritmai lyginami trijose skirtingose situacijose: stacionarioje, judėjimo link tikslo (angl. goal – directed) bei judančio taikinio (angl. moving – target). Tyrimo rezultatai parodė, jog A* ir FSA* nepasiekiamų viršūnių kiekiui esant ~16000 yra ~23,6% našesni už GAA* ir trečios plečiamos klasės algoritmus, o pasiekiamumą keičiančių viršūnių kiekiui esant ~8000 – 42,3%. Nepasiekiamų viršūnių kiekiui kintant nuo 1000 iki 16000 trečios plečiamos klasės algoritmai yra vidutiniškai ~58,7% našesni už GAA* ir ~54% našesni už A* ir FSA*. Pasiekiamumą keičiančių viršūnių kiekiui kintant nuo 500 iki 8000 trečios plečiamos klasės algoritmai yra vidutiniškai ~69,3% našesni už GAA* ir ~47,8% našesni už A* ir FSA*. / Dynamic path finding algorithms combine heuristic and incremental search methods to solve a series of similar search tasks in both known and unknown environments. There are three classes of incremental search algorithms. In this document we provide a brief summary of dynamic path finding algorithms, that uses incremental search methods, but its main focus is on comparing main algorithms of all three incremental classes, that are guaranteed to give optimal solution in environment where action costs can increase and decrease over time, and showing their strong and weak sides. The algorithms are compared in three different situations: stationary, goal – directed and moving – target. At the end of the document conclusions are given based on performed work. In this paper, research showed that A* and FSA* are ~23,6% more efficient than GAA* and third incremental class algorithms when the amount of untraversable cells is ~16000 and ~42,3% more efficient when the amount of traversability changing cells is ~8000. When the amount of untraversable cells is between 1000 and 16000, the third incremental class algorithms are ~58,7% more efficient than GAA* and ~54% – than A* and FSA*. When the amount of traversability changing cells is between 500 and 8000, the third incremental class algorithms are ~69,3% more efficient than GAA* and ~47,8% – than A* and FSA*.