Simulation is an important tool for prediction and assessment of the behavior of complex systems and situations. The importance of simulation has increased tremendously during the last few decades, mainly because the rapid pace of development in the field of electronics has turned the computer from a costly and obscure piece of equipment to a cheap ubiquitous tool which is now an integral part of our daily lives. While such technological improvements make it easier to analyze well-understood deterministic systems, increase in speed and storage capacity alone are not enough when simulating situations where human beings and their behavior are an integral part of the system being studied. The problem with simulation of intelligent entities is that intelligence is still not well understood and it seems that the field of Artificial Intelligence (AI) has a long way to go before we get computers to think like humans. Behavior-based agent modeling has been proposed in mid-80's as one of the alternatives to the classical AI approach. While used mainly for the control of specialized robotic vehicles with very specific sensory capabilities and limited intelligence, we believe that a behavior-based approach to modeling generic autonomous agents in complex environments can provide promising results. To this end, we are investigating a behavior-based model for controlling groups of collaborating and competing agents in a geographic terrain. In this thesis, we are focusing on scenarios of military nature, where agents can move within the environment and adversaries can eliminate each other through use of weapons. Different aspects of agent behavior like navigation to a goal or staying in group formation, are implemented by distinct behavior modules and the final observed behavior for each agent is an emergent property of the combination of simple behaviors and their interaction with the environment. Our experiments show that while such an approach is quite efficient in terms of computational power, it has some major drawbacks. One of the problems is that reactive behavior-based navigation algorithms are not well suited for environments with complex mobility constraints where they tend to perform much worse than proper path planning. This problem represents an important research question, especially when it is considered that most of the modern military conflicts and operations occur in urban environments. One of the contributions of this thesis is a novel approach to reactive navigation where goals and terrain information are fused based on the idea of transforming a terrain with obstacles into a virtual obstacle-free terrain. Experimental results show that our approach can successfully combine the low run-time computational complexity of reactive methods with the high success rates of classical path planning. Another interesting research problem is how to deal with the unpredictable nature of emergent behavior. It is not uncommon to have situations where an outcome diverges significantly from the intended behavior of the agents due to highly complex nonlinear interactions with other agents or the environment itself. Chances of devising a formal way to predict and avoid such abnormalities are slim at best, mostly because such complex systems tend to be be chaotic in nature. Instead, we focus on detection of deviations through tracking group behavior which is a key component of the total situation awareness capability required by modern technology-oriented and network-centric warfare. We have designed a simple and efficient clustering algorithm for tracking of groups of agent suitable for both spatial and behavioral domain. We also show how to detect certain events of interest based on a temporal analysis of the evolution of discovered clusters.

The role of the unmanned aerial vehicle (UAV) has significantly expanded in the military sector during the last decades mainly due to their cost effectiveness and their ability to eliminate the human life risk. Current UAV technology supports a variety of missions and extensive research and development is being performed to further expand its capabilities. One particular field of interest is the area of the low cost expendable UAV since its small price tag makes it an attractive solution for target suppression. A swarm of these low cost UAVs can be utilized as guided munitions or kamikaze UAVs to attack multiple targets simultaneously. The focus of this thesis is the development of a cooperative online path planning algorithm that coordinates the trajectories of these UAVs to achieve a simultaneous arrival to their dynamic targets. A nonlinear autopilot design based on the dynamic inversion technique is also presented which stabilizes the dynamics of the UAV in its entire operating envelope. A nonlinear high fidelity six degrees of freedom model of a fixed wing aircraft was developed as well that acted as the main test platform to verify the performance of the presented algorithms.

Robot path planning is a critical feature of autonomous systems. Rapidly-exploring Random Trees (RRT) is a path planning technique that randomly samples the robot configuration space to find a path between the start and end point. This thesis studies and compares the performance of four important RRT algorithms, namely, the original RRT, the optimal RRT (also termed RRT*), RRT*-Smart, and Informed RRT* for six different environments. The performance measures include the final path length (which is also the shortest path length found by each algorithm), time to find the first path, run time (of 1000 iterations) for each algorithm, total number of sampling nodes, and success rate (out of 100 runs). It is found that both RRT*-Smart and Informed RRT* algorithm result in shorter path lengths than the original RRT and RRT*. Typically, RRT*-Smart can find a suboptimal path in less number of iterations while the Informed RRT* is able to find the shortest path with increased number of iterations. On the other hand, the original RRT and RRT* are better suited for real-time applications as the Informed RRT* and RRT*-Smart have longer run time due to the additional steps in their processes.

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.

No description available.

No description available.

No description available.

No description available.

For the past couple of years researchers around theworld have tried to develop fully autonomous vehicles. One of theproblems that they have to solve is how to navigate in a dynamicworld with ever-changing variables. This project was initiated tolook into one scenario of the path planning problem; overtakinga human driven vehicle. Model Predictive Control (MPC) hashistorically been used in systems with slower dynamics but withadvancements in computation it can now be used in systems withfaster dynamics. In this project autonomous vehicles controlledby MPC were simulated in Python based on the kinematic bicyclemodel. Constraints were posed on the overtaking vehicle suchthat the two vehicles would not collide. Results show that anovertake, that keeps a proper distance to the other vehicle andfollows common traffic laws, is possible in certain scenarios. / Under de senaste åren har forskare världen över försökt utveckla fullt autonoma fordon. Ett av problemen som behöver lösas är hur man navigerar i en dynamisk värld med ständigt förändrande variabler. Detta projekt startades för att titta närmare på en aspekt av att planera en rutt; att köra om ett mänskligt styrt fordon. Model Predictive Control (MPC) har historiskt sett blivit använt i system med långsammare dynamik, men med framsteg inom datorers beräkningskraft kan det nu användas i system med snabbare dynamik. I detta projekt simulerades självkörande fordon, styrda av MPC, i Python. Fordonsmodellen som används var kinematic bicycle model. Begränsningar sattes på det omkörande fordonet så att de två fordonen inte kolliderar. Resultaten visar att en omkörning, som håller avstånd till det andra fordonet samt följer trafikregler, är möjligt i vissa scenarion. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

Background. Geometry-Independent Path Planning (GIPP) can be done by generating a navigation mesh and computing paths on that mesh in real-time for parallel and dynamic path planning. However, many of the existing algorithms are not suitable for the Graphics card, therefore a new path planning algorithm is created. Hardware Accelerated Line Of Sight (HALOS) performs parallel path planning on grid maps in real-time using the GPU.   Objectives. This thesis aims to implement an automatic navigation mesh generation algorithm using the GPU rendering pipeline and a GPU-bound path planning algorithm for a grid-based map. The proposed method should generate accurate paths and run in real-time. To gather results, the methods are measured in run-time on different types of hardware and scenarios. Methods. Multiple experiments are conducted. A navigation mesh is generated in real-time using the rendering pipeline of the GPU. In addition, a novel path planning algorithm generates paths in real-time using the GPU by utilizing line of sight on the navigation mesh. GIPP is a multi-source, single-destination algorithm. The path planning is done parallel and dynamically to navigate around moving obstacles. Results. The experiments show that GIPP can generate a dynamic navigation mesh in real-time. However, the coverage of GIPP is poor, and some resolutions of GIPP result in agents being unable to reach the goal node. The performance effect of dynamic worlds on path planning is not noticeable compared to static worlds. Conclusions. The proposed method can perform real-time navigation mesh generation and path planning. Different resolutions of GINT show inconsistencies in the length of the path generated. This method, GIPP, is well suited for complex, dynamic, single-floor meshes that more traditional navigation mesh generators are not guaranteed to handle in real-time. The main performance bottleneck for GIPP is the number of layers created during path planning. / Bakgrund. Geometrioberoende vägplanering (GIPP) kan utföras genom att generera ett navigationsnät och beräkna vägar på detta nät i realtid för parallell och dynamisk vägplanering. Många vägplaneringsalgoritmer kan inte köras i realtid på grafikkortet. Därför har Hardware Accelerated Line Of Sight (HALOS) skapats, vilket utför parallell vägplanering i realtid med hjälp av GPU:n. Mål. Denna avhandling syftar till att implementera en automatisk algoritm för generering av navigationsnät med hjälp av GPU:ns renderingspipeline och implementera en GPU-bunden vägplaneringsalgoritm för en rutbaserad karta. Den föreslagna metoden genererar vägar och körs i realtid. För att samla in resultat mäts metoderna i körtid på olika typer av hårdvara och scenarier. \newline\textbf{Metoder.} Flertalet experiment utförst på GIPP. Ett navigationsnät genereras i realtid med hjälp av GPU:ns renderingspipeline och en ny vägplaneringsalgoritm genererar vägar i realtid med hjälp av sikten längs navigationsnätet. Denna algoritm har flera källor med en destination (MSSD) för att hantera ett stort antal agenter. Vägplaneringen görs parallellt och dynamiskt för att navigera runt rörliga hinder. Resultat. Experimenten visar att GIPP kan generera ett navigationsnät i realtid. GIPP har dock dålig precision när det gäller att generera effektiva vägar mot målet.  Vissa upplösningar leder till att agenter inte når slutmålet. Dynamiska världar har omärkbar påverkan på prestandan i jämförelse med statiska världar när det gäller vägplanering. Slutsatser. Den föreslagna metoden kan utföra navigationsnätsgenerering och vägplanering i realtid. Olika upplösningar av navigationsnätet visar att vägplanering har olikeheter i avstånd. Denna metod, GIPP, lämpar sig väl för komplexa, dynamiska, enplansvärldar. GIPPs flaskhals i prestandan är mängden lager som skapas under vägplaneringen.