A common method to design trajectories is by cubic splines to interpolate a set of via-points for a robot. The trajectories are optimized with respect to an objective function including the total time with a set of kinematic constraints. The execution time for this problem is longer then the sampling time of an embedded computer and restricts the use of this method in on-line applications. To modify this procedure to be usable on-line a point-to-point motion planner is developed using the output from the optimization programming at each iteration. This point-to-point motion planner runs on a separate process and contains a virtual vehicle to restrict the end-effector speed in its operational space. This results in an adaptive motion planner capable of handling kinematic actuator constraints and end-effector speed constraints in the operational space. The thesis ends with results from simple simulations demonstrating the effects. / En vanlig metod för attutforma banor är genom kubiska splines för att interpolera en uppsättning avvia-punkter för en robot. Banorna är optimerade med avseende på en målfunktionav den totala tiden med en uppsättning av kinematiska begränsningar.Exekveringstiden för detta problem är ofta längre än samplingstiden för eninbyggd dator och begränsar användningen av denna metod i applikationeron-line. För att metoden skall kunna användas on-line skapas enpunkt-till-punkt planerare med hjälp av utdata från den iterativa lösaren avoptimeringsproblemet vid varje iteration. Punkt-till-punkt banorna planeras ochkörs på en separat process och innehåller en virtual vehicle för att begränsaend-effectorns fart i den operativa rymden. Detta resulterar i en adaptiv rörelseplaneraresom hanterar kinematiska manövrerings begränsningar och fart begränsningar avend-effectorn i den operativa rymden. Arbetet avslutas med resultat från enklasimuleringar som visar effekterna.

This thesis work presents a model predictive control (MPC) based trajectory planner forhigh speed lane change and low speed parking scenarios of autonomous four wheel steering(4WS) vehicle. A four wheel steering vehicle has better low speed maneuverabilityand high speed stability compared with normal front wheel steering(FWS) vehicles. TheMPC optimal trajectory planner is formulated in a curvilinear coordinate frame (Frenetframe) minimizing the lateral deviation, heading error and velocity error in a kinematicdouble track model of a four wheel steering vehicle. Using the proposed trajectory planner,simulations show that a four wheel steering vehicle is able to track different type ofpath with lower lateral deviations, less heading error and shorter longitudinal distance. / I detta avhandlingsarbete presenteras en modellbaserad prediktiv kontroll (MPC) -baseradbanplaneringsplan f¨or h¨oghastighetsbanan och l°aghastighetsparametrar f¨or autonomtfyrhjulsdrift (4WS). Ett fyrhjulsdrivna fordon har b¨attre man¨ovrerbarhet med l°ag hastighetoch h¨oghastighetsstabilitet j¨amf¨ort med vanliga fr¨amre hjulstyrningar (FWS). MPC-optimalbanplanerare ¨ar formulerad i en kr¨okt koordinatram (Frenet-ram) som minimerar sidof¨orl¨angningen,kursfel och hastighetsfel i en kinematisk dubbelsp°armodell av ett fyrhjulsstyrda fordon.Med hj¨alp av den f¨oreslagna banaplaneraren visar simuleringar att ett fyrhjulsstyrfordonkan sp°ara olika typer av banor med l¨agre sidof¨orl¨angningar, mindre kursfel ochkortare l¨angsg°aende avst°and.

The usage of Unmanned Aerial Vehicles (UAVs) to navigate autonomously in a dynamic environment is becoming more common. It is important that a UAV can generate collision-free trajectories and also be able to modify them to adapt to environment changes over the entire duration of navigation. The objective of this thesis is to present an optimized motion planning framework for UAV in dynamic environments. The proposed framework consists of two modules, which are optimized motion planner and dynamic scene generator. The optimized motion planner utilizes an asymptotically optimal sampling-based motion planning algorithm, RRTX, and extends RRTX with an optimizer based on Covariant Hamiltonian Optimization for Motion Planning (CHOMP) algorithm to optimize trajectories. A dynamic environment has obstacles that unpredictably appear, disappear or move. The optimized motion planner reacts to environment changes and finds collision-free trajectories during the navigation. Dynamic scene generator contains an obstacle information messenger and UAV simulator. This module is to simulate UAV, obstacles, and planned trajectories in a Unity scene. UAV simulator utilizes Flightmare, which is a flexible modular quadrotor simulator that contains a rendering engine built on Unity and a physics engine for dynamics simulation. The built framework is evaluated in simulations and the results show that the framework enables a UAV to navigate autonomously without colliding with any obstacles in dynamic environments. / Användningen av obemannade luftfarkoster för att navigera autonomt i dynamiska miljöer blir allt vanligare. Det är viktigt att en obemannade luftfarkost kan generera kollisionsfria banor och ändra dem för förändringar i miljöer under hela navigering. Detta examensarbete undersöker optimerad banplanering ramverket för obemannade luftfarkoster i dynamiska miljöer. Ramverket består av två delar: en optimerad banplanerare, och en dynamiska scen modul. Den optimerad banplaneraren använder en asymptotiskt optimala samplingsbaserade banplaneringsalgoritm, RRTX, och förlänger RRTX med en optimala lösning baserad på Covariant Hamiltonian Optimization for Motion Planning (CHOMP) algoritm för att optimera banor. En dynamiska miljö har hinder som oförutsägbart dyker upp, försvinner eller rör sig. Den optimerad banplaneraren reagerar på förändringar i miljöer och hittar kollisionsfria banor under navigeringen. Den dynamiska scen modulen består av en informationsbudbärare för hinder och en simulator för obemannade luftfarkoster. Denna modul ska simulera obemannade luftfarkoster, hinder och banor i en Unity scen. Den simulatorn för obemannade luftfarkoster använder Flightmare, som är en flexibel modulär simulator för quadrotorer. Flightmare består av en återgivningsmotor byggd på Unity och en fysikmotor för dynamiska simuleringar. Ramverket har testats i simuleringar. Resultat från simuleringar bekräftar att det ramverket gör att en obemannade luftfarkost kan navigera autonomt utan att kollidera med några hinder i dynamiska miljöer.

Unmanned flying vehicles (UAVs) are tools that can be used in a variety of scenarios. The most common areas of application are outdoors, where there are not many obstacles to take into consideration when planning a route. In indoor scenarios, the requirements on the path planning system of the UAV becomes stricter, as these scenarios tend to contain more obstacles compared to flying at higher altitude outdoors. Considering a drone with multiple objectives (waypoints to visit), two problems initially come to mind, namely path planning and combinatorial optimization. To finish the objectives in the most effective way, the optimal path between the waypoints needs to be calculated, as well as the order in which the waypoints need to be visited. Another challenge is the fact that the UAV runs on limited battery capacity, and thus might not be able to finish the objectives before running out of battery. Therefore, the combinatorial optimization needs to include visits to a recharging station. The objective of this thesis is to combine and modify methods for path planning and combinatorial optimization in a way that a route can be calculated within a limited time budget, to allow the computation to be executed “on the fly”. The method used for path planning is ANYA, and the two methods used for the combinatorial optimization are ant colony optimization (ACO) as well as the Lin-Kernighan-Helsgaun (LKH) method. The nearest neighbor method (NN) will be used as a baseline for comparison. We propose an algorithm to include the battery constraint in the optimization. To evaluate the algorithms, we measure the computational time, to know if the method works in real-time, and also the estimated time for the UAV to finish the route, which will determine the energy efficiency of the route. We find that the ACO’s solutions improve over time, but require a long computational time, which makes it not suitable for small time budgets. LKH produces better routes than the NN method, and does so within the chosen time budget, as long as the number of waypoints is limited. The algorithm to optimize the trips to the recharging station works better than the previous use of LKH for this specific problem. / Obemannade flygande fordon är verktyg som är användbara inom en mängd områden. Vanligaste miljön för användning av dessa verktyg är i utomhusmiljöer där inte många fysiska hinder existerar. I inomhusscenarion blir kraven på vägplanering större, då dessa miljöer ofta innehåller fler hinder än vid flygning på högre altituder utomhus. Givet ett scenario med en drönare med flera målpunkter att besöka, finns två stora utmaningar, nämligen vägplanering och ruttplanering. För att besöka alla målpunkter behöver vi en metod för att identifiera närmsta, kollisionsfria vägen mellan målpunkterna, men också en metod för att hitta den optimala ordningen att besöka punkterna i. En annan utmaning som uppstår på grund av drönarens begränsade batteritid är att det inte finns någon garanti på att den hinner besöka alla målpunkter innan batteriet tar slut. Därför måste ruttplaneringen innefatta besök till en laddningsstation. Målet med detta examensarbete är att kombinera och modifiera metoder för väg och ruttplanering på ett sätt så en effektiv rutt mellan alla målpunkter kan identifieras, utan att drönaren får slut på batteri, samt med kravet att metoden ska kunna hitta en lösning inom begränsad tid. Metoden som används för vägplanering är ANYA, och de två metoderna som används för ruttplanering är myrkolonioptimering och Lin-Kernighan-Helsgaun-metoden. Närmsta-granne-metoden kommer användas som en baseline för jämförelsen mellan metoderna. Vi föreslår en algoritm som inkluderar batteribegränsningen i ruttplaneringen. För att utvärdera algoritmerna mäter vi beräkningstiden, för att ta reda på om metoden fungerar i realtid. Vi mäter även den uppskattade tiden det tar för drönaren att slutföra rutten, vilket kommer beskriva hur energieffektiv rutten är. Vi finner att myrkolonioptimering ger en bättre och bättre lösning över tid, men kräver en lång beräkningstid, vilket gör den opassande för korta tidsbegränsningar. LKH producerar bättre rutter än närmsta-granne-metoden, och gör det inom den givna tidsramen, så länge antal målpunkter är begränsade. Algoritmen för att optimera besöken till laddstationen fungerar bättre än tidigare appliceringar av LKH på samma problem.

Model Based Systems Engineering (MBSE) approach aims at implementing various processes of Systems Engineering (SE) through diagrams that provide different perspectives of the same underlying system. This approach provides a basis that helps develop a complex system in a systematic manner. Thus, this thesis aims at deriving a system model through this approach for the purpose of autonomous driving, specifically focusing on developing the subsystem responsible for generating a feasible trajectory for a miniature vehicle, called AutoCar, to enable it to move towards a goal. The report provides a background on MBSE and System Modeling Language (SysML) which is used for modelling the system. With this background, an MBSE framework for AutoCar is derived and the overall system design is explained. This report further explains the concepts involved in autonomous trajectory planning followed by an introduction to Robot Operating System (ROS) and its application for trajectory planning of the system. The report concludes with a detailed analysis on the benefits of using this approach for developing a system. It also identifies the shortcomings of applying MBSE to system development. The report closes with a mention on how the given project can be further carried forward to be able to realize it on a physical system. / Modellbaserade systemteknikens (MBSE) inriktning syftar till att implementera de olika processerna i systemteknik (SE) genom diagram som ger olika perspektiv på samma underliggande system. Detta tillvägagångssätt ger en grund som hjälper till att utveckla ett komplext system på ett systematiskt sätt. Sålunda syftar denna avhandling att härleda en systemmodell genom detta tillvägagångssätt för autonom körning, med särskild inriktning på att utveckla delsystemet som är ansvarigt för att generera en genomförbar ban för en miniatyrbil, som kallas AutoCar, för att göra det möjligt att nå målet. Rapporten ger en bakgrund till MBSE and Systemmodelleringsspråk (SysML) som används för modellering av systemet. Med denna bakgrund, MBSE ramverket för AutoCar är härledt och den övergripande systemdesignen förklaras. I denna rapport förklaras vidare begreppen autonom banplanering följd av en introduktion till Robot Operating System (ROS) och dess tillämpning för systemplanering av systemet. Rapporten avslutas med en detaljerad analys av fördelarna med att använda detta tillvägagångssätt för att utveckla ett system. Det identifierar också bristerna för att tillämpa MBSE på systemutveckling. Rapporten stänger med en omtale om hur det givna projektet kan vidarebefordras för att kunna realisera det på ett fysiskt system.

Exploration is a fundamental problem in robotics that requires robots to navigate through unknown environments to autonomously gather information about their surroundings while executing collision-free paths. In this project, we propose a method for producing smooth paths during the exploration process in indoor environments using UAVs to improve battery efficiency and enhance the quality of pose estimation. The developed framework is built by merging two approaches that represent the state of the art in the field of autonomous exploration with UAVs. The overall exploration logic is given by GLocal, a paper that introduces a hybrid, i.e. both sampling-based and frontier-based, framework that is able to cope with the issue of odometry drift when exploring indoor environments due to the absence of absolute localization, e.g. through GNSS. The second approach is FUEL, which introduces a frontier-based exploration methodology which computes the ’drones path as an optimized non-uniform B-Spline. The framework described in this thesis borrows the optimized B-Spline trajectory generation from FUEL and implements it in GLocal. To do this, the original cost function defined by GLocal for each exploration viewpoint was modified and the resulting samples were used to select the initial control points of the B-Spline. Furthermore, we extended the underlying state machine governing the entire algorithm and we revisited the original re-planning logic. The presented system is evaluated in various simulated environments, showcasing the advantages and disadvantages of this method. These evaluations demonstrate its improved state estimation performance and absolute observed volume, albeit at the expense of longer traveled trajectories in big and complex environments. / Utforskning är ett grundläggande problem inom robotteknik som kräver att robotar navigerar genom okända miljöer för att autonomt samla in information om sin omgivning samtidigt som de utför kollisionsfria banor. I det här projektet föreslår vi en metod för att producera jämna banor under utforskningsprocessen i inomhusmiljöer med hjälp av UAV:er för att förbättra batterieffektiviteten och förbättra kvaliteten på posestimeringen. Det utvecklade ramverket bygger på en sammanslagning av två metoder som representerar den senaste tekniken inom autonom utforskning med UAV:er. Den övergripande utforskningslogiken ges av GLocal, en artikel som introducerar en hybrid, i.e. både samplingsbaserad och gränsbaserad, ram som kan hantera problemet med odometridrift vid utforskning av inomhusmiljöer på grund av frånvaron av absolut lokalisering, e.g. genom GNSS. Den andra metoden är FUEL, som introducerar en gränsbaserad utforskningsmetod som beräknar drönarens bana som en optimerad icke-uniform B-Spline. Ramverket som beskrivs i denna avhandling lånar den optimerade B-Spline-banegenereringen från FUEL och implementerar den i GLocal. För att göra detta modifierades den ursprungliga kostnadsfunktionen som definierades av GLocal för varje utforskningspunkt och de resulterande samplen användes för att välja de initiala kontrollpunkterna för B-Spline. Dessutom utökade vi den underliggande tillståndsmaskinen som styr hela algoritmen och vi reviderade den ursprungliga logiken för omplanering. Det presenterade systemet utvärderas i olika simulerade miljöer, vilket visar fördelarna och nackdelarna med denna metod. Dessa utvärderingar visar på förbättrad prestanda för tillståndsuppskattning och absolut observerad volym, om än på bekostnad av längre färdvägar i stora och komplexa miljöer.

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.

Terrain referenced navigation is a method of navigation that uses measurements of altitude above ground to infer the position of the vehicle, mainly aerial or underwater. This method provides an alternative to the commonly used satellite-based navigation. Satellite-based navigation methods rely on positional information being sent from an external source, which can be jammed or tampered with, a problem terrain referenced navigation does not have. Both satellite-based and terrain based navigation methods often work in conjunction with inertial navigation systems, which are accurate for short periods of time but suffer from large errors due to accumulation of errors when used for longer missions. In this thesis, several state-of-the-art methods of terrain referenced navigation are studied and evaluated, with the main focus being the different estimation methods employed. Five of the studied estimators were implemented and tested on simulated flight data from a generic aerial vehicle, resulting in improved navigation accuracy compared to using inertial navigation on its own. For the terrain referenced navigation to work well, the ground needs to be relatively unique in order to contain useful information, thus making the estimation more uncertain when flying over flat regions. To deal with this, path planning was used to alter the flight path to increase the expected information gain. Using a grid based planning algorithm together with the original route yielded a modified path with more potential information. When following this new path, the terrain referenced navigation systems are shown to estimate the position more accurately compared to the original path. The study shows that terrain referenced navigation is a viable alternative to satellite based navigation. It also indicates that modifying the path to increase the expected information gain can result in better robustness and precision. / Terrängbaserad navigering är en navigeringsmetod där mätningar av höjd över mark används för att fastställa fordonets position, huvudsakligen från luften eller under vattnet. Denna metod är ett alternativ till den allmänt använda satellitbaserade navigeringen. Satellitbaserad navigering är beroende av att positionsinformation skickas från en extern källa, som kan störas eller manipuleras, vilket är ett problem som terrängbaserad navigering inte har. Både satellitbaserade och terrängbaserade navigeringsmetoder används ofta tillsammans med tröghetsnavigeringssystem, som är noggranna under kortare tid, men som lider av stora fel på grund av ackumulering av fel när de används under längre uppdrag. I denna rapport studeras och utvärderas flera moderna metoder för terrängbaserad navigering, med huvudfokus på de olika skattningsmetoder som används. Fem av de studerade skattningsmetoderna implementerades och testades på simulerade flygdata från ett generiskt flygfarkost, vilket resulterade i förbättrad navigeringsnoggrannhet jämfört med att använda tröghetsnavigering på egen hand. För att den terrängbaserade navigeringen ska fungera bra måste marken vara relativt unik för att innehålla användbar information, vilket gör uppskattningen mer osäker när man flyger över plana områden. För att hantera detta användes banplanering för att välja en flygbana som ger maximalt informations innehåll. Genom att använda en rutnätsbaserad planeringsalgoritm tillsammans med den ursprungliga rutten erhölls en modifierad bana med mer potentiell information. Genom att följa denna nya bana uppskattas positionen bättre av de terrängbaserade navigationssystemen jämfört med den ursprungliga banan. Studien visar att terrängbaserad navigering är ett gångbart alternativ till satellitbaserad navigering. Den visar också att en ändring av banan för att öka den förväntade informationsvinsten kan leda till bättre robusthet och precision.

Robotics is an interdisciplinary field that integrates computer science, electrical engineering, mechanical engineering, control engineering and other related fields. As the quick development of these fields, people have been building more complex robots with more advanced control strategies in order to solve more challenging tasks. In addition, it is always a target for researchers to achieve autonomous operation of robots so that the manpower can be saved and the robot can work in harsh environment like on Mars. In this project, I focus on the trajectory planning problem of a unicycle model running in 2D environment. I choose Path Integral Policy Improvement (PI2) control algorithm in this project as the main study object. And Model Predictive Control (MPC) is chosen as a reference in order to be compared with PI2 to evaluate the performance of PI2. In order to simulate the tasks that the robot needs to handle in practice, I use obstacles to represent the complex environment and I use Signal Temporal Logic (STL) to represent the complex tasks. Furthermore, I also incorporate the deep dynamics model in the project so that the the method put forward in this project is able to handle complex robot models and complex working environments. To evaluate the performances of PI2 and MPC, five criteria are put forward in this project. Finally, based on the evaluation results, possible improvement and future research are proposed. / Robotics är ett tvärvetenskapligt område som integrerar datavetenskap, elektroteknik, maskinteknik, styrteknik och andra relaterade områden. Som den snabba utvecklingen av dessa fält har människor byggt mer komplexa robotar med mer avancerade kontrollstrategier för att lösa mer utmanande uppgifter. Dessutom är det alltid ett mål för forskare att uppnå autonom drift av robotar så att arbetskraften kan sparas och roboten kan arbeta i tuffa miljöer som på Mars. I det här projektet fokuserar jag på banplaneringsproblemet för en enhjulingsmodell som körs i 2D-miljö. Jag väljer Path Integral Policy Improvement (PI2) kontrollalgoritm i detta projekt som huvudstudieobjekt. Och Model Predictive Control (MPC) väljs som referens för att kunna jämföras med PI2 för att utvärdera prestandan för PI2. För att simulera de uppgifter som roboten behöver hantera i praktiken använder jag hinder för att representera den komplexa miljön och jag använder Signal Temporal Logic (STL) för att representera de komplexa uppgifterna. Dessutom införlivar jag också den djupa dynamikmodellen i projektet så att metoden som läggs fram i detta projekt kan hantera komplexa robotmodeller och komplexa arbetsmiljöer. För att utvärdera prestanda för PI2 och MPC presenteras fem kriterier i detta projekt. Slutligen, baserat på utvärderingsresultaten, föreslås möjliga förbättringar och framtida forskning.