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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-321467 |
| Date | January 2022 |
| Creators | Johansson, Ola |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2022:711 |
Page generated in 0.0031 seconds