Application of the ACO algorithm for UAV path planning

• Autorzy: Konatowski Stanisław , Pawłowski Paweł

Identyfikatory

DOI

10.15199/48.2019.07.24

Warianty tytułu

PL

Zastosowanie algorytmu ACO do wyznaczania trasy BSP

• Języki publikacji: EN

Abstrakty

EN

The ACO (Ant Colony Optimization) algorithm is a bio-inspired metaheuristic used to optimize problems or functions described by graphs, sequences of events, or queues of tasks. It is used, among a variety of other purposes, when routing Internet network packets, determining the shortest routes between designated points (traveling salesman's problem), for the time and cost optimization of production, or setting public transport stops. In the article, the ACO algorithm was used to autonomously construct the optimal route for an unmanned aerial vehicle (UAV). The algorithm establishes the spatial orientation of the UAV, indicating the direction of its transition for each intermediate waypoint. The results of the simulations show the trajectory of the UAV depending on the selected weighting factors, determining the priority of avoiding detected hazards or choosing the shortest path. The quality of each variant is evaluated numerically by the calculated fitness function, the value of which is the sum of the costs of the transition to each intermediate route point. The effect of the algorithm is a set of executable trajectory variants, of which the one with the best fitness value is selected.

PL

Algorytm ACO (ang. Ant Colony Optimization) jest bio-inspirowaną metaheurystyką, wykorzystywaną do optymalizacji problemów lub funkcji opisywanych za pomocą grafów, sekwencji zdarzeń, czy też kolejki zadań. Znajduje on zastosowanie m.in. przy trasowaniu pakietów sieci internetowych, wyznaczaniu najkrótszych tras między wyznaczonymi punktami (problem komiwojażera), optymalizacji czasu i kosztu produkcji, czy też ustalaniu przystanków transportu publicznego. W artykule, algorytm ACO został wykorzystany do autonomicznego wyznaczenia optymalnej trasy dla bezpilotowego statku powietrznego (BSP). Algorytm ustala orientację przestrzenną BSP, determinującą kierunek jego przemieszczenia dla każdego pośredniego punktu docelowego. Wyniki przeprowadzonych symulacji przedstawiają trajektorię BSP w zależności od dobranych współczynników wagowych, określających priorytet ominięcia wykrytych zagrożeń lub wybrania najkrótszej drogi. Jakość każdego wariantu jest określana liczbowo poprzez ustaloną funkcję dopasowania, której wartość stanowi suma kosztów przejścia do każdego pośredniego punktu trasy. Efektem działania algorytmu jest zbiór wykonywalnych wariantów trajektorii, z których wybrany zostaje ten o najlepszej wartości dopasowania.

Słowa kluczowe

EN

path planning; UAV; ACO algorithm

PL

planowanie trasy; BSP; algorytm mrówkowy

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2019
• Tom: R. 95, nr 7
• Strony: 115--119
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Konatowski Stanisław

• Wojskowa Akademia Techniczna, Instytut Radioelektroniki, ul. Gen. Witolda Urbanowicza 2, 00-908 Warszawa

autor

Pawłowski Paweł

• Wojskowa Akademia Techniczna, Instytut Radioelektroniki, ul. Gen. Witolda Urbanowicza 2, 00-908 Warszawa

Bibliografia

• [1] M. Dorigo, V. Maniezzo, A. Colorni, Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics – Part B. Vol. 26, No 1, pp. 29-41, 1996.
• [2] M. Dorigo, Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy, 1992.
• [3] D. Merkle, M. Middendorf, H. Schmeck, Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4, 2002.
• [4] D. Martens, M. De Backer, R. Haesen, J. Vanthienen, B. Baesens, Classification with Ant Colony Optimization. IEEE Transactions on Evolutionary Computation, Vol. 11, No.5, 2007.
• [5] W. Chen, J. Zhang, An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Carious QoS Requirements. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 39, No 1, 2009.
• [6] H. B. Tolabi, M. H. Ali, M. Rizwan, Simultaneous Reconfiguration, Optimal Placement of DSTATCOM, and Photovoltaic Array in a Distribution System Based on Fuzzy- ACO Approach. IEEE Transactions on Sustainable Energy, Vol. 6, Issue: 1 , January 2015.
• [7] S. Konatowski, P. Pawłowski, Ant Colony Optimization for UAV path planning. 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), Lviv-Slavske, Ukraina, 2018.
• [8] Krzyzanowski, A., Flight mechanics, MUT (2009).
• [9] J. S. Dai: Euler–Rodrigues formula variations, quaternion conjugation and intrinsic connections. Elsevier, October 2015.
• [10] T P. Kaniewski, T. Kraszewski, Drone-based system for localization of people inside buildings. 14th International Conference on Advanced Trends in Radioelecrtronics Telecommunications and Computer Engineering 2018, Lviv- Slavske, Ukraine, pp. 46-51, 2018.
• [11] J. Matuszewski, Identification of radar signals using discriminant vectors. XVII International Conference on Microwaves, Radar and Wireless Communications (MIKON), Wroclaw, Poland, MAY 19-21, 2008, Vols 1 and 2, pp. 433-436.
• [12] J. Matuszewski, A. Dikta, Emitter location errors in electronic recognition system. Proc. of SPIE Digital Library, XI Conference on Reconnaissance and Electronic Warfare Systems, Vol. 10418, No. 4/2017, pp. C1-C8, 2018.
• [13] T. Pietkiewicz, B. Wajszczyk, Fusion of identification information from ELINT-ESM sensors. Proc. SPIE 10715, 2017 Radioelectronic Systems Conference, 107150F.
• [14] M. Łabowski, P. Kaniewski, Motion Compensation for Unmanned Aerial Vehicle’s Synthetic Aperture Radar. Signal Processing Symposium SPS 2015, Debe, Poland, pp.184-188.
• [15] N. Sakthipriya, T. Kalaipriyan, Variants of Ant Colony Optimization – A state of an Art. Indian Journal of Science and Technology, Vol 8(31), November 2015.
• [16] R. Róziecki, Bifurkacyjna analiza dynamiki lotu samolotu supermanewrowego z wektorowaniem ciągu. PhD thesis, Politechnika Wrocławska, Wrocław, 2006.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).