A Method for Formalizing Knowledge About Planning UAV Flight Routes in Conditions of Uncertainty Aleksandr Tymochko 1, Natalia Korolyuk 2, Аnastasia Korolyuk 3 and Elena Korshets 4 1,2 Ivan Kozhedub Kharkiv National University of the Air Force, Sumska street, 77/79, Kharkiv, 61023, Ukraine 3 Vasil Karazin Kharkiv National University, 4 Svobody Sq., Kharkiv, 61022, Ukraine 4 Ivan ChernyakhovskyNational Defense University, Povitroflotskyi Avenue, 28, Kyiv 03049, Ukraine Abstract It is advisable to use heuristic methods for the task of planning the flight routes of unmanned aerial vehicles (UAVs) at the planning stage of monitoring and reconnaissance. With their help they look for solutions within some subspace of possible acceptable solutions. They are the best in terms of taking into account the practice, experience, intuition, knowledge of the decision maker. The values of individual predicted factors should be represented using the mathematical apparatus of fuzzy sets. A method of formalizing knowledge about UAV flight route planning has been developed. It is based on interval fuzzy sets. In conditions of uncertainty, they allow to formalize the factors that take into account the conditions of monitoring, search, detection and destruction of objects, the impact of the external environment on the range of UAVs. This effect is manifested in the form of linguistic and interval-estimated parameters for each option, which allow to take into account the uncertainty. The developed method allows to form the area of definition of linguistic variables. These variables are used to describe the conditions for monitoring, reconnaissance and the impact of the environment on the range of UAVs. Such variables are also used to form from the set of the most important objects of monitoring, exploration of the most significant ground objects on the basis of an assessment of the degree of non-dominance of elements. The proposed approach provides a formalization of UAV flight route options for each possible scenario of the location of objects, the impact of the external environment. The result of formalization is fuzzy production rules, where fuzzy linguistic utterances are used as the antecedent and consequent. Keywords 1 Unmanned aerial vehicle, production rules, fuzzy linguistic statements 1. Introduction enemy. Among the available technical means capable of quickly and efficiently collecting the necessary information, one can single out The most important task of the Armed Forces unmanned aerial vehicles (UAVs). When (AF) of Ukraine in the defense nature of military monitoring the area, UAVs fly over the area of doctrine is the constant monitoring of the enemy. interest and collect the necessary data. Monitoring should ensure a timely and organized Thus, UAVs can be used to monitor forests, transition of troops from peacetime to martial law. fields, borders, for environmental and The main role is played by monitoring and meteorological monitoring, search and rescue intelligence. Their tasks are to provide the missions, for military purposes, etc. The presence leadership and headquarters in a timely manner of large potential capabilities of UAVs does not with complete and reliable information about the ISIT 2021: II International Scientific and Practical Conference «Intellectual Systems and Information Technologies», September 13–19, 2021, Odesa, Ukraine EMAIL: timochko.alex@gmail.com (A. 1); natali-kor@ukr.net (A. 2); nastyshakorolyk@gmail.com (A. 3) korshets_l@ukr.net (A. 4) ORCID: 0000-0002-4154-7876 (A. 1); 000-0002-2865-5899 (A. 2); 0000-0003-1860-6599 (A. 3); 0000-0002-7225-0848 (A. 4) ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) guarantee the achievement of the specified Global trends in research in the field of control efficiency of reconnaissance and monitoring. Its theory are concentrated in two areas – artificial increase can be achieved by intelligently intelligence and machine learning, robotics and predicting the behavior of UAVs. This takes into decision theory. Artificial intelligence account the influence of environmental factors, technologies are actively used in the military the behavioral nature of the objects of monitoring, sphere. Work is being actively carried out to knowledge and experience of UAV operators. increase the autonomy of the functioning of The experience of practical application of combat systems. UAVs [1-3] in performing field monitoring tasks The article [4] considers the principles of in real combat conditions revealed the difficulty construction of the distributed external and in making an informed decision on the selection onboard components of the control system of a and construction of rational flight routes. group of reconnaissance and strike unmanned Managing UAVs for monitoring, searching, aerial vehicles. detecting, and destroying objects is a complex, In [5] the models of collective control of poorly formalized task. It is resolved under the manned and unmanned aerial vehicles are condition of opposition of the opposite party presented. Methodical support of training of (conflict) and requires the use of methods in the aircraft control operators and engineers of air field of artificial intelligence. First of all, it navigation systems is offered. concerns decision support systems, methods of In the article [6] the analysis of an estimation presentation and formalization of knowledge, of efficiency and criteria of reliability of group models of fuzzy sets. flights of UAVs is carried out. The algorithm of At present, the combination of stochastic and search of the central repeater of group of UAV for non-stochastic uncertainty factors influencing this ensuring transfer of a control signal in group is process is insufficiently taken into account when developed. selecting appropriate options for the UAV flight The article [7] discusses the advantages and route. Factors of non-stochastic uncertainty have disadvantages of centralized and decentralized the nature of behavioral uncertainty. Therefore, it architecture of UAV group management, presents is necessary to adapt pre-designed decision- tables of the dependence of the level of onboard making models to change many possible automation and the number of UAVs in the group. situations. The article [8] developed a method of planning Tasks of this class require increasing the level the flight path of UAVs to search for a dynamic of automation of their solution. The reason for this object in the forest-steppe area, taking into is the dynamism, ephemerality and high degree of account possible options for its movement. uncertainty of the air and ground conditions, time The article [9] is devoted to the development constraints. But the task of automating the of a meta-model of a multi-agent system for planning of UAV flight routes is complicated by searching and influencing a ground object by a the need to take into account the experience of group of unmanned aerial vehicles under a decision makers (DM). This requires formalizing centralized control variant. The base of rules of one's own knowledge and experience in ATS. To logical inference for agents according to the work with knowledge, including its formalization, solved tasks and a role of the agent in group which it is necessary to improve mathematical support is based on use of production model is developed. and software (MSS). Trends in the development The work [10] is devoted to the development of MSS show the need for the introduction of of a method of UAV route planning when modern information technology (IT), including performing missions to search for a stationary intelligent IT. They are aimed at creating and object. The method allows to take into account the using the knowledge bases (KB) of the UAV distribution of probabilities of importance of the control system (CS) [13-16, 22]. area of the task. The knowledge base is a set of rules, facts, In [11] a method of substantiation of the derivation mechanisms and software that describe optimal route of air reconnaissance was a subject area and are designed to represent the developed. The paper proposes indicators and accumulated knowledge in it [17]. The most criteria for the effectiveness of the search for a difficult stage of creating a database is the dynamic object. formalization of knowledge in a given subject In [12] the issue of efficiency of decentralized area. control of UAV group and operator load when interacting with decentralized scheduler is 𝐴̃ = {(𝑥, 𝑢, 𝜇𝐴̃ (𝑥, 𝑢))|∀𝑥 ∈ 𝑋, ∀𝑢 ∈ 𝐽𝑥𝑢 (1) considered. ⊆ [0,1]}. In [13, 14] the factors of influence of the ̃ The discrete 𝐴 can be represented as external environment are considered, which, in turn, make changes in the initial result of UAV 𝜇𝐴̃ (𝑥) flight planning. These factors are taken into 𝐴̃ = {∑ }= account with a high degree of subjectivity of the 𝑥 𝑥∈𝑋 (2) person planning the flight route. In [14, 15] mathematical models are considered, which aim 𝑁 𝑀 to increase the efficiency of monitoring. To = {∑ [∑ 𝑓𝑥𝑖 (𝑢𝑖𝑘 )/𝑢𝑖𝑘 ]⁄𝑥𝑖 }, determine the optimal flight route, it is necessary 𝑘=1 𝑖=1 to calculate the probability of performing where ∑∑ is the union of x and u. reconnaissance tasks. However, the experience of using UAVs in local conflicts shows the need to If 𝑓𝑥 (𝑢) = 1, ∀𝑢 ∈ [𝐽𝑥𝑢 , 𝐽𝑥𝑢̅ ] ⊆ [0,1], then the _ take into account the factors that affect the membership function of the second type 𝜇𝐴̃ (𝑥, 𝑢) effectiveness of monitoring and reconnaissance is expressed by the lower membership function of operations with UAVs. It is necessary to take into the first type 𝐽𝑥𝑢 ≡ 𝜇𝐴̃ (𝑥) and, accordingly, the account the threats and limitations of natural and technical nature [16, 17], which significantly upper membership function of the first type 𝐽𝑥𝑢̅ ≡ affect the final result of the flight task. 𝜇̅ 𝐴̃ (𝑥). Then IFST2 can be represented as The result of the literature analysis indicates 𝐴̃ = the relevance and prospects of research in the (𝑥, 𝑢, 1)|∀𝑥 ∈ 𝑋, ∀𝑢 ∈ [𝜇 𝐴̃ (𝑥), 𝜇̅𝐴̃ (𝑥)] direction of developing intelligent UAV control (3) { } systems. search, detection and destruction of ⊆ [0,1] objects. The article proposes the use of triangular fuzzy Thus, a change in approaches to planning numbers (TFN) and trapezoidal fuzzy intervals UAV flight routes will make it possible to better (TFI). The expediency of their use is due to the solve the problems of observation, search, simplicity of operations on them and visual detection and destruction of objects. graphical interpretation. The purpose of the study is to develop a In the general case, the fuzzy interval is called method of formalizing knowledge about the IFST2 A  with convex upper and lower planning of UAV flight routes on the basis of membership functions, limiting the area of interval fuzzy sets in the monitoring, search, uncertainty of this IFST2. The fuzzy number of detection and destruction of objects in conditions of uncertainty. IFST2 is called IFST2 A  with convex and unimodal upper and lower membership functions, 2. Problem analysis (Main part) which limit the area of uncertainty of this IFST2. Features of the representation of TFN or TFI in terms of IFST2 are as follows: To formalize the knowledge of UAV flight – the left and right boundaries of fuzzy route planning, it is advisable to use interval fuzzy quantities in terms of IFST2 are not points but sets of type 2 (IFST2). For IFST2, the values of uncertainty intervals; the membership functions of the second order are – the extreme values of the uncertainty constant. That is, the membership function is intervals, in turn, are the boundaries of the two unified (homogeneous) in contrast to the general FST1. They are defined by the upper membership fuzzy sets of type 2 (FST2). function 𝜇̅ 𝐴̃ and the lower membership function Іnterval fuzzy sets of type 2 allow you to use 𝜇𝐴̃ . These functions limit the occupied area of all the tools of interval calculations and are ¯ expressed by the degree of truth of the uncertainty (FOU) TFNIFST2 or TFIIFST2 above uncertainty. It reflects the vagueness and and below, respectively; inaccuracy of the element belonging to a given – the upper 𝜇̅𝐴̃ and lower 𝜇𝐴̃ membership ¯ set. IFST2 (𝐴̃) are characterized by the functions determine the normal convex FST1 on a membership function of the second type (order) non-empty carrier. Moreover, in the case of TFN 𝜇𝐴̃ (𝑥, 𝑢), where 𝑥 ∈ 𝑋 and 𝑢 ∈ 𝐽𝑥𝑢 ⊆ [0,1], 0 ≤ IFST2 it will be unimodal normal convex FST1. 𝜇𝐴̃ (𝑥, 𝑢) ≤ 1,which is expressed Thus, it is proposed to formally present the FOU TFNIFST2 𝐴̃𝛥 in the form of a tuple with SISO – a structure that implements one input and parameters [18-22] one output; MISO – a structure that implements 𝐹𝑂𝑈(𝐴̃𝛥 ) = 〈𝛼𝜇̅ , 𝛼𝜇 , 𝑎𝜇̅ , 𝑎𝜇 , 𝛽𝜇̅ , 𝛽𝜇 〉, (4) many inputs and one output; MIMO is a structure ¯ ¯ ¯ that implements many inputs and many outputs. where 𝛼𝜇̅ – left fuzzy coefficient 𝜇̅ 𝐴̃ ∆; When formalizing knowledge about the 𝛼𝜇 – left fuzzy coefficient 𝜇𝐴̃ ; process of planning the route of the UAV flight in ∆ a  – center (modal value) 𝜇̅𝐴̃ ∆; the form of a fuzzy production rule that describes a predetermined version of the UAV routes, we а𝜇 – center (modal value) 𝜇𝐴̃ will use the rules with MISO-structure. ∆ 𝛽𝜇̅ – right fuzzy coefficient 𝜇̅ 𝐴̃ ∆; These conditions are factors that take into 𝛽𝜇 – right fuzzy coefficient 𝜇𝐴̃ . account the conditions of monitoring, the impact ∆ of the external environment, and the conclusions In this case, the triangular upper membership – recommendations on the appropriate route of the function 𝜇̅ 𝐴̃ ∆; 𝐹𝑂𝑈(𝐴̃𝛥 ) generates a normal UAV flight in specific conditions. unimodal convex FST1 on a nonempty carrier – When developing a method of formalizing an open interval [𝑎𝜇̅ − 𝛼𝜇̅ , 𝑎𝜇̅ + 𝛽𝜇̅ ], and the knowledge about the planning of UAV flight triangular function 𝜇𝐴̃ 𝐹𝑂𝑈(𝐴̃𝛥 ) generates a routes on the basis of interval fuzzy sets, the ∆ following limitations and assumptions are taken normal unimodal convex FST1 on a nonempty into account: carrier – open interval [𝑎𝜇 − 𝛼𝜇 , 𝑎𝜇 + 𝛽𝜇 ]. - issues related to the assessment of the ¯ ¯ ¯ ¯ adequacy and informativeness of the parameters It is also proposed to formally represent FOU used to describe the projected situation are TFI IFST2 in the form of a tuple with the considered resolved and are not considered in this following parameters: study; 𝐹𝑂𝑈(𝐴̃𝛱 ) = - construction of membership functions for (5) = 〈𝛼𝜇̅ , 𝛼𝜇 , 𝑎𝜇̅ , 𝑎𝜇 , 𝑏𝜇̅ , 𝑏𝜇 , 𝛽𝜇̅ , 𝛽𝜇 〉, conditions and conclusions of fuzzy production where 𝛼𝜇̅ – left fuzzy coefficient 𝜇̅ 𝐴̃п ; rules begins with the use of the simplest forms of 𝛼𝜇 – left fuzzy coefficient 𝜇𝐴̃п ; membership functions – piecewise linear functions. Subsequently, their nature can be 𝑎𝜇̅ – lower modal value 𝜇̅ 𝐴̃п ; clarified and taken into account during the 𝑎𝜇 – lower modal value 𝜇𝐴̃п ; adjustment of the rules (for example, at the stage 𝑏𝜇̅ – upper modal value 𝜇̅ 𝐴̃п ; of learning a fuzzy logical system); 𝑏𝜇 – upper modal value 𝜇𝐴̃п ; - issues of ensuring the completeness and 𝛽𝜇̅ – right fuzzy coefficient 𝜇̅𝐴̃п ; consistency of a set of fuzzy production rules in this study are not considered. 𝛽𝜇 – right fuzzy coefficient 𝜇𝐴̃п . The method of formalizing knowledge about In this case, the trapezoidal upper membership the process of planning a reconnaissance flight of function 𝜇̅ 𝐴̃п 𝐹𝑂𝑈(𝐴̃𝛱 ) generates a normal a UAV based on IFST2 includes the following convex FST1 on a nonempty carrier – an open main stages: interval [𝑎𝜇̅ − 𝛼𝜇̅ , 𝑏𝜇̅ + 𝛽𝜇̅ ], and the trapezoidal - presentation of factors that take into account lower function 𝜇𝐴̃п 𝐹𝑂𝑈(𝐴̃𝛱 ) generates a normal the conditions of monitoring, exploration, environmental impact in the form of linguistic unimodal convex FST1 on a non-empty carrier – variables for each projected option; open interval. - formation of the area of definition of In this case, the set of fuzzy production rules linguistic variables used to describe the conditions will be called the base of rules (BR). It is intended of monitoring, exploration and environmental for the formal presentation of empirical impact; knowledge or expert knowledge (DM) on a - formation for each linguistic variable of the subject area based on IFST2 [22]. In the general term set, as elements of which use the names of case, there are the following BP: fuzzy variables that describe the linguistic • by type of fuzzy production rules [17] meanings of the conditions of monitoring, the (depending on the formal representation of the impact of the external environment; derivation of the rule): fuzzy statements; clear - description of UAV flight route options; statements; functions; - formation of many of the most important • by the structure of fuzzy production rules: objects of monitoring, intelligence based on the assessment of the degree of non-dominance of the information preparation and direct planning of elements; UAV routes is up to 66% of the total time for - presentation of options for the location of making a decision [10, 19, 22]. ground objects, the impact of the external The mathematical expectation of the total time environment, the appropriate variant of the UAV for making a decision is 𝑀∗ [𝑇̅𝑡 ]=211,59 s; the flight route in the form of fuzzy production rules, time spent on entering the initial data – where as an antecedent, a follower use fuzzy 𝑀∗ [𝑇̅𝑒 ]=67 s (up to 31% from 𝑀∗ [𝑇̅𝑡 ]) the waiting linguistic statements. time for the result of solving the problem – Thus, it is investigated that for the task of UAV 𝑀∗ [𝑇̅𝑟 ]=73,63 s (up to 35% from 𝑀∗ [𝑇̅𝑡 ]). flight route planning at the planning and Efficiency of decision-making by a decision- reconnaissance planning stage it is expedient to maker at the stage of planning UAV flight routes use heuristic methods. They are looking for may turn out to be unacceptably low (P=0.47 ... solutions within some subspace of possible 0.9). To increase the efficiency of decision- acceptable solutions. They are the best in terms of making, it is necessary to reduce the time for taking into account the practice, experience, preparation and the direct solution of the problem. intuition, knowledge of ATS. The values of In the proposed approach to planning the individual predicted factors should be represented routes of the UAV reconnaissance flight, the using the mathematical apparatus of fuzzy sets. A mathematical expectation of the total time for method for formalizing knowledge about UAV making a decision was 𝑀∗ [𝑇̅𝑡 ]=103,59 s, the time flight route planning based on interval fuzzy sets spent by the decision-maker for entering the initial in conditions of uncertainty has been developed. data was – 𝑀∗ [𝑇̅𝑒 ]=13,74 s (up to 13% With its help it is possible to formalize the factors from 𝑀∗ [𝑇̅𝑡 ]), the waiting time for the decision that take into account the conditions of result was – 𝑀∗ [𝑇̅𝑟 ]=33,71 s (up to 32% from monitoring, search, detection and destruction of 𝑀∗ [𝑇̅𝑡 ]). objects, the impact of the external environment on The proposed approach to planning UAV the range of UAVs. flight routes under conditions of uncertainty They are presented in the form of linguistic makes it possible to reduce the total decision- and interval-estimated parameters for each option. making time by up to 2 times. This approach allows: - take into account uncertainty; - to form the area of definition of linguistic 4. References variables that are used to describe the conditions of monitoring, reconnaissance and the impact of [1] Official site of DefenseUkrain. Robotic the external environment on the range of UAVs; platforms for the Armed Forces of Ukraine: - to form from a set of the most important included in DOZ-2021 and prepared for the objects of monitoring, reconnaissance of the most parade. URL: https://defence-ua.com/ significant ground objects on the basis of an [2] Official site of Ukrainian Military Pages. estimation of a degree of non-dominance of Vision of the Air Force 2035, approved by elements; the Military Council of the Air Force on - to formalize the flight options of the UAV for 15.05.2020. URL: https: //drive.google.com / each possible variant of the location of objects, the file/ d/ 1N3tahxAhqpNUIoz-xbgVDKG- influence of the external environment in the form 1YJmsK. of fuzzy production rules, where fuzzy linguistic [3] On the new version of the Military Doctrine statements are used as an antecedent, a of Ukraine: Decree of the President of consequent. Ukraine of September 2, 2015. URL: http:// zakon.rada.gov.ua /go/555/2015. [4] V.N. Evdokimenkov, M.N. Krasilshchikov, G.G. Sebryakov, 3. Conclusions Distributedintelligentcontrolsystemforagrou pofunmannedaerialvehicles: The calculation of the mathematical architectureandsoftware. IzvestiyaYuFU. expectation of the time to perform individual Technicalsciences (2016). №1. pp. 174-180. operations in the construction of UAV flight [5] V.P. Kharchenko, T.F. Shmelyova, E.A. routes at the planning stage is carried out. Znakovskaya, Methodology of situational In the traditional approach, the time for collective control of manned and unmanned aerial vehicles in a single airspace: scientific [14] V.V. Kaminsky, The fight against air materials. In 3 volumes. Volume 2. terrorism should begin with the ground. Integrated corporate models for collective Science and technology of the Air Force of management of manned and UAVs in a the Armed Forces of Ukraine. (2014), № 1 single airspace in conditions of risk and (14). pp. 16-23. uncertainty (2017). P.120. [15] A. Alimpiev, P.Berdnik, N.Korolyuk, [6] M. L. Cummings, Operator interaction with O.Korshets, Selecting model of unmanned centralized versus decentralized UAV aerial vehicle oaccept it for military purposes architectures. Handbook of Unmanned with regard to expert data. Eastern- Aerial Vehicles,2015. P. 977992. uropeanJournalofEnterpriseTechnologiesIS [7] O. Tymochko, A. Trystan, A. Berezhnyi., O. SN 1729-3774. (2017), №1/ 9 (85).рр 53-60. Sotnikov, [16] O.Yu.Permyakov, N.O. Korolyuk VehicleswhileMonitoringBehaviorofDynam Information - telecommunication icObjectsin a Forest-SteppeArea. technologies and modern armed struggle. InternationalJournalofEmergingTrendsinEn Scientific and technical conference of young gineeringResearch. (2020),volume.8, No scholars "Actual problems of information 7.pp.3208-3215. technology". Kyiv: NUOU. (2018). рр 5-6. [8] O.G. Matyushchenko, V.S. Kadubenko, S.P. [17] S.A. Olizarenko, E.V. Brezhnev, A.V. Sedash, D.O. SizonЄ Multi-agent model of Perepelitsa, Fuzzy sets of type 2. Information group use of unmanned aerial vehicles when processing systems. (2010), Vip. 8 (89). рр. performing special missions. 131–140. PolishJournalOfScience. (2021),. volume1, [18] S.A.Olizarenko, A.V.Perepelitsa, No 35. pp 13-19. V.A.Kapranov, Interval fuzzy sets of type 2. [9] P. Yao, Z. Xie, P. Ren, Optimal UAV Terminology, representation, operations RoutePlanningforCoverageSearchofStationa Information processing systems. (2011), Vip. ryTargetinRiver. IEEE 2 (92). рр. 39 - 45. TransactionsonControlSystemsTechnology. [19] N.O. Korolyuk, Substantiation of the modern (2019), № 27 (2), pp. 822829.doi: approach to automation of aviation decision- 10.1109/TCST.2017.2781655. making processes. Collection of scientific [10] O. Tymochko, A. Trystan, O. Chernavina, works. (2019), №1 (59). рр. 32-39. A.Berezhnyi, The method of planning the [20] T.Saatya, Structuresindecision making: On flight route of unmanned aerial vehicles the subjective geometry of hierarchies and while monitoring the behavior of dynamic networks [on line]. European Journal of objects in the forest-steppe area. Information Operational Research, vol. 199, is. 3, 2009, Processing Systems. (2020), № 3(162). pp. рр. 867–872. 95 - 110. [21] N.O. Korolyuk, R.V. Korolev, O.A. [11] M. L.Cummings, J. P.How, A. Whitten Korshets, The procedure of formalization of O.Toupet, The Impact of Human– data used in the description of the process of Automation Collaboration in Decentralized air traffic control. Collection of scientific Multiple Unmanned Vehicle Control. works of KhNUPS. (2017), № 4 (53). Proceedingsofthe IEEE. (2012),№ 100(3). рр.103-106. pp. 660 - 671. [22] N.O. Korolyuk, V.V. Sinyavsky, D.O. [12] V.V. Kaminsky, V.V. Tyurin, O.A. Haustov, Improving the software of Korshchets, N.O. Korolyuk, Analysis of the automation systems for recognizing the type use of unmanned aerial vehicles in modern of air object. Weapons and military armed conflicts and anti-terrorist operation in equipment. (2017), № 1 (49). рр.122-125. eastern Ukraine. Science and defense. (2017), № 3 (4). pp.4-8. [13] G.S. Stepanov, M.A. Kaminsky, M.A. Pavlenko, Views on problematic issues of the use of the Air Force in air defense. Science and technology of the Air Force of the Armed Forces of Ukraine. (2018), №1 (30). pp. 18- 23.