ON ONE APPROACH TO SOLVING THE TRAVELING SALESMAN PROBLEM FOR AUTONOMOUS UNMANNED AERIAL VEHICLE PLANNING OF TARGET FLIGHT PATHS

Objective. Develop a principle of constructing tools and procedures for optimal routing of targets by an autonomous uncrewed aerial vehicle, which have an acceptable complexity for implementation on an onboard computer.

Methods. The rules for optimizing the terrain map with the located targets, creating a penalty matrix that considers the disturbing factors of the  unstable air environment in the planning process, and building a reference  tree for finding the minimum route for the accepted cost of flying around the targets.

Results. A principle is proposed to develop effective procedures for planning minimum cost-effective routes to fly around targets in an unstable air  environment. The basis for behavior planning is the optimization of the formal description of a given terrain map, which leads to a significant reduction in the number of alternatives compared in the process of searching  for a minimum route to fly around targets. This, in turn, makes it  possible to implement planning procedures on the onboard computer system of an autonomous uncrewed aerial vehicle. A statement is proved to justify the existence of a minimum route for the accepted cost of overflying targets  in the formal description of the terrain map obtained as a result of  converting its original representation based on the developed optimization rules.

Conclusion. The considered approach effectively solves various types of issues reduced to the traveling salesman problem, including planning the  minimum route of flying around targets by an autonomous uncrewed aerial vehicle in an unstable air environment under uncertainty conditions.  

1. Abrosimov V.K. Kollektivy intellektual'nyh letatel'nyh apparatov [Teams of intelligent aircrafts]. Moscow, Nauka Publ., 2017, 304 p. (In Russ)

2. Rondan U. B., Timoti U. M. Malye bespilotnye letatel'nye apparaty. Teoriya i praktika [Small unmanned aerial vehicles. Theory and practice]. Moscow, Tekhnosfera Publ., 2016, 312 p. (In Russ)

3. Semenov S.S., Pedan A.V., Volovikov V.S., Klimov I.S. Analiz trudoemkosti razlichnyh algoritmicheskih podhodov dlya resheniya zadachi kommivoyazhera [Analysis of the complexity of various algorithmic approaches for solving the traveling salesman problem]. Sistemy upravleniya, svyazi i bezopasnosti [Control systems, communications and security], 2017, no 1, pp. 116 – 131. (In Russ)

4. 4 La Valle S.M. Planning Algorithms. Cambridge, Cambridge University Press, 2006, 844 p.

5. Kostik Yu.L. Zadacha kommivoyazhera: priblizhennye algoritmy po metodu vetvej i granic s garantirovannoj tochnost'yu [Traveling Salesman Problem: Approximate Algorithms Using the Branch and Bound Method with Guaranteed Accuracy]. Prikladnaya diskretnaya matematika [Applied Discrete Mathematicы], 2019, no 45, pp. 104 – 112. (In Russ)

6. Mamonov N.V. Issledovanie vliyaniya assimetrii na slozhnost' resheniya zadachi kommivoyazhera metodom vetvej i granic [Investigation of the influence of asymmetry on the complexity of solving the traveling salesman problem by the branch and bound method]. Sovremennye informacionnye tekhnologii i IT obrazovanie [Modern information technologies and IT education], 2019., no 1(15), pp. 99 – 106. (In Russ)

7. Kolesnikov A.V., Kirikov I.A., Listopad S.V., Rumovskaya S.B., Domanickij A.A. Reshenie slozhnyh zadach kommivoyazhera metodami funkcional'nyh gibridnyh intellektual'nyh system [Solving Complex Traveling Salesman Problems by Methods of Functional Hybrid Intelligent Systems]. Pod red. A.V. Kolesnikova. Moscow, IPI RAN Publ, 2011, 295 p. (In Russ)

8. Gerpov A.V., Shatalov D.A., Mitasov R.A. Prakticheskaya pol'za ispol'zovaniya geneticheskih algoritmov na primere resheniya zadachi kommivoyazhera [The practical benefits of using genetic algorithms on the example of solving the traveling salesman problem]. Trudy Rostovskogo universiteta putej soobshcheniya [Proceedings of the Rostov University of Railways], 1917, no 4, pp. 93 – 97. (In Russ)

9. Kurejchik V.V., Kurejchik V.M. Geneticheskij algoritm opredeleniya puti kommivoyazhera [Genetic Algorithm for Determining the Traveling Salesman's Path]. Izvestiya RAN. Teoriya i sistemy upravlenii [Journal of computer and systems sciences international], 2006, no 1, pp. 94 –100.

10. Dorigo M., Stützle T. Ant colony optimization: overview and recent advances. Handbook of metaheuristics. Berlin, Springer - Cham, 2019, pp. 311 – 351.

11. Kubil V.N., Mohov V.A. Mnogokolonial'nyj murav'inyj algoritm s modifikaciyami dlya resheniya mnogokriterial'nyh zadach marshrutizacii transporta [Multicolonial ant algorithm with modifications for solving multicriteria transport routing problems]. Izvestiya vysshih uchebnyh zavedenij. Elektromekhanika [Izvestiya vysshikh uchebnykh zavod. Electromechanics], no 1(61), 2018, pp. 94 – 109. (In Russ)

12. Ligo Tan', Fomichyov A.V. Planirovanie prostranstvennogo marshruta bespilotnyh letatel'nyh apparatov s ispol'zovaniem metodov chastichnogo celochislennogo linejnogo programmirovaniya [Planning the spatial route of unmanned aerial vehicles using partial integer linear programming methods]. Vestnik MGTU im N.E. Baumana. Ser. Priborostroenie [Vestnik MGTU named after N.E. Bauman. Ser. Instrument making], 2016, no 2, pp. 53 – 66. (In Russ)

13. Lebedev G.N., Efimov A.V. Primenenie dinamicheskogo programmirovaniya dlya marshrutizacii obleta mobil'nyh ob"ektov v kontroliruemom regione [Application of dynamic programming for routing flying around mobile objects in the controlled region]. Vestnik Samarskogo gosudarstvennogo aerokosmicheskogo universiteta [Bulletin of the Samara State Aerospace University], 2011, no 6, pp. 234 – 241. (In Russ)

14. Hachaj M.Yu., Ogorodnikov Yu.Yu. Effektivnaya approksimaciya zadachi ob optimal'noj marshrutizacii v metricheskih prostranstvah fiksirovannoj razmernosti [Effective approximation of the problem of optimal routing in metric spaces of fixed dimension]. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniya [Doklady Russian Academy of Sciences. Mathematics, informatics, control processes], 2020, no 1(493), pp. 74 – 80. (In Russ)

15. Kaluder H., Brezak M., Petrovic I. A visibility graph based method for path planning in dynamic environments. MIPRO, 2011, Proceedings of the 34 th International Convention, Opatija, Croatia, 2011, pp. 717–721.

16. Kelly A. Mobile Robotics: Mathematics, Models, and Methods. Cambridge, Cambridge University Press, 2013. 808 p.

17. Melekhin V.B., Hachumov M.V. Planirovanie avtonomnym bespilotnym letatel'nym apparatom effektivnyh marshrutov obleta celej [Planning for an autonomous unmanned aerial vehicle of effective routes to fly over targets]. Aviakosmicheskoe priborostroenie [ Aviation and Space Instrument Engineering], 2020, no 4, pp.. 3 – 14. (In Russ)

18. Chernyj M. A., Korablin V. I. Vozdushnaya navigaciya [Air navigation]. Moscow, Transport Publ., 1991, 432 p. (In Russ)

19. Melekhin V.B., Hachumov V.M. Upravlenie effektivnoj realizaciej tekhnologicheskih processov mekhanicheskoj obrabotki detalej v mashinostroenii[Management of the effective implementation of technological processes of mechanical processing of parts in mechanical engineering]. Problemy upravleniya [Problems of Management], 2020, no 1, pp. 71 – 82.

20. Kurejchik V.M., Lagunova Yu.A. Zadachi o kommivoyazhere. Obzor i metody resheniya [Traveling Salesman Problems. Review and methods of solution]. Palmarium Academic Publishing, 2019. 60 c. (In Russ)