=Paper=
{{Paper
|id=Vol-2393/paper_340
|storemode=property
|title=Optimization of Flows and Flexible Redistribution of Autonomous UAV Routes in Multilevel Airspace
|pdfUrl=https://ceur-ws.org/Vol-2393/paper_340.pdf
|volume=Vol-2393
|authors=Tetiana Shmelova,Arnold Sterenharz,Oleksand Burlaka
|dblpUrl=https://dblp.org/rec/conf/icteri/ShmelovaSB19
}}
==Optimization of Flows and Flexible Redistribution of Autonomous UAV Routes in Multilevel Airspace==
Optimization of Flows and Flexible Redistribution of Autonomous UAV Routes in Multilevel Airspace Tetiana Shmelova1[0000-0002-9737-6906], Arnold Sterenharz 2[ 0000-0003-3942-1227 ], Oleksandr Burlaka3[ 0000-0002-8883-6130] 1National Aviation University, Komarova av., 1, 03058, Kiev, Ukraine shmelova@ukr.net 2ECM Space Technologies GmbH (ECM), Germany arnold.sterenharz@ecm-office.de 3National Aviation University, Komarova av., 1, 03058, Kiev, Ukraine wrkttt@gmail.com Abstract. The authors present a problem of the performance of Unmanned Aer- ial Vehicles (UAV)’s flights (group or single flight) for the decision of different target tasks in the city using information air navigation technology and methods of mathematical modeling in Artificial Intelligence (graph theory, Expert Judgment Method, methods of decision making in risk and fuzzy-logic, dynam- ic programming, etc.). The configuration and optimization of group flight routes for UAVs depend on the type of "target task". The algorithm of estima- tion performance of UAVs flights in the smart-town, an illustrative example of the optimization of UAVs flights is presented in the article. Keywords: Unmanned Aerial Vehicle, Remotely Piloted Aircraft System, To- pology, GRID-analyze, Decision Making in Risk, Dynamic Programming, Smart City. 1 Introduction Remotely piloted aircraft systems (RPAS) are a new component of the aviation sys- tem. They are based on cutting-edge developments in aerospace technologies, which may open new applications; improve to the safety and efficiency of aviation [1; 2]. Unmanned Aerial Vehicles (UAV)'s have several advantages, namely low operat- ing cost, simplicity, availability, UAVs may be used in cases where the usage of manned aircraft is impractical, expensive or dangerous [3; 4]. Nowadays using of UAVs is effective for decision lot problems such as in monitoring forest fires; search and rescue operations; for relay communications in those places - where the antenna coverage cannot be set because of difficult terrain; in logistic as the safest, cheap and fast method of movement of goods; for aerial photography; for controlling traffic; for first aid to people under various extreme conditions, etc. [3; 4; 5]. Many of these tasks decision for an urban locality and wherein effectively use single and group flight of 2 UAVs [6; 7]. The Forum "Urban Air Mobility" in November 2018 at Amsterdam discussed the future of drones in cities. Looked at from the perspective of cities and citizens, urban air mobility and the idea of Mobility as a Service (MaaS) provide a fascinating view of a possible future where a daily commute could seamlessly include a bicycle, train, and drone service all as part of an integrated public transportation system [8]. In this sense, the usage of group flights UAVs is more appropriate, for example, for photo/video monitoring; group survey of large areas and patrol areas; delivery of big number cargo and use of an unmanned taxi to move passengers, etc. Noted additional useful properties such as faster coverage of big area fragment of urban and minimal risk in the movement of UAVs in town as in “smart-city”. There- fore, the disadvantages of UAV’s that include the limited capacity due to the small size of UAV can be satisfied with the group flight usage [6]. When planning UAV flights, it is important to comply with regulatory air naviga- tion requirements and effective methods for flight operations [1; 2; 9]. The documents of ICAO are including the requirements and UAV management rules such as UAV certification and operator certification; UAV registration; rules for UAV operations; communication with the UAV; training of personnel for the operation of the UAV; emergency situations with UAV and flight safety; legal issues to ensure the possibility of performing safe, coordinated and effectively integrated flights UAVs [1; 2]. The purposes of the work are: building an Expert system (ES) as Artificial Intelligence (AI) for estimation of the performance of UAVs flights (group and single) for the decision of different target tasks in an urban locality; definition safe and minimal cost ways UAVs movement in town. 2 Flexible redistribution of autonomous Unmanned Aircraft routes in multilevel airspace 2.1 Expert systems for estimation performance of UAVs flights in smart-town The concept of “smart city” is characterized by using the new achievements for the effective organization of life in a town. This is using AI as UAVs and Expert systems; Internet technologies in order to monitor the state of urban infrastructure facilities, their control, and based on the data obtained because of monitoring, optimal alloca- tion of resources and ensuring the safety of citizens. Such objects include bridges and tunnels, roads and railways, communication systems, water supply, and drainage sys- tems, power supply systems, and various large industrial facilities, airports, rail rail- way stations, seaports, etc. [4; 9]. The effectiveness of presenting using UAVs for a modern town as a “smart city” has some problems: the presence of buildings, roads, construction, recreation areas, and natural areas, etc.; availability of specific flight orders - target use of drones [9]; air navigation requirements [1; 2] for flight operations of the manned and unmanned aircraft, etc. The “smart city” is an aggregate of several information and communica- tion technologies, mathematical methods and AI. The usage of UAVs in the smart city concept will help solve such tasks: traffic jams monitoring; search and rescue tasks; 3 photo/video monitoring; the mobile point of Wi-Fi retranslating; the movement of goods; taxing operations; ambulance operations, etc. Using graph theory can determine the effectiveness of different structures (topolo- gies) in UAV’s group formation. To control a group of drones from RPAS suggested choosing and using a Central Drone Repeater (CDR) to connect to the operator on the ground and control the other of the UAVs using the method of server selection in local computer networks [6; 10]. For planning and flight control UAV developed a Distributed Decision Support System (DDSS), which represents a complex system with complex interactions geographically distributed local Remote piloted aircraft (RPA). During the flight UAVs may be controlled by remote piloting station (RPS). At any given time ti k-UAV must piloted by only one j-th RPS, if necessary, at time ti+1 to be transmitted to the control (j + 1)-th RPS (fig. 1). This transfer flight control of the j-th RPS to (j + 1)-th RPS to be safe and effective, which is provided through the local operators UAV. To coordinate interaction and exchange of information be- tween remoted pilots developed a database of local RPS NoSQL [6]. The authors have developed computer programs for DDSS of the unmanned air- craft pilot, “Remote Expert Air Traffic Management System “Decision making (DM) in a common environment FF-ICE (Flight & Flow Information for a Collaborative Environment (FF-ICE)” presented decentralized-distributed UAVs control system using blockchain technology for connection between RPS and RPA (Fig.1). Block- chain technology is ideal as a new infrastructure to secure, share, and verify learning achievements and Collaborative Decision Making (CDM) too. For today, the key to ensuring the safety of flights is the problem of the organization of CDM by all the operational partners based on general information on the flight process and ground handling of the manned and unmanned aircraft [11]. There are many advantages of this approach such as enhanced security, security, big data analysis, and record keep- ing, real-time constant data exchange, etc. Fig. 1. Decentralized-distributed UAVs control system with blockchain connection between RPA For the management of the UAV, a system for managing single or a group of the UAV’s is proposed, depending on the purpose of the UAV (“target task”). Taking into 4 account the limited and dependence of the use of the UAV group on its intended pur- pose were analysed the network topology indicators for the implementation of the group flight. The Algorithm of building an Expert system (ES) for estimation of the performance of UAVs flights (group and single) for the decision of different target tasks in an urban locality: 1. The estimation effectiveness performance the target task of using the next sys- tems: the group of separate UAVs with controls from separate operators; the UAVs group with control from CDR-UAV; single UAV with control single operator. If there is the UAV group with control from CDR need: a. Decomposition of the complex system on subsystems “network topol- ogies - the target tasks”, description of the characteristics of subsys- tems, and estimation of effectiveness of network topologies for per- formance the specific target task. b. The effectiveness of network topologies for performance the target task and definition of criteria estimation (definition the corresponding weight coefficients of the efficiency of the topology). c. Estimation of network topologies of the UAV group for the specific target task using Expert Judgment Method (EJM) (definition of system preferences and coordination of experts’ opinions too). 2. Estimation of urban locality using GRID analyses of sector UAV flight, fuzzy- logic or EJM for estimation of risk/safety of UAV flight. 3. Aggregation of subsystems to the new system (additive or multiplicative aggre- gation depend on the type of "target task"). 4. Graphical presentation of results for Expert System (group UAV, single UAV or group of single UAVs), for example, estimation of effectiveness of network topol- ogies for performance the target task “monitoring" by UAVs group” (Fig.2). Fig. 2. Control system of UAV’s group from RPAS using CDR-drone To evaluation, the safety of UAVs flights in town, need to obtain quantitative val- ues of risks of flights in different segments of the territory of the town using methods 5 for evaluating risk/safety (EJM or Fuzzy logic) [13] and according to air navigation requirements [1; 2]. The air navigation rules for classification obstructions in town such as “Restricted” and “Dangerous” areas, but they have nothing in common with ICAO’s official defi- nitions, this is an estimation of risks movement ways of UAVs in smart-city. The "Restricted areas" in our case are such areas, where the risk of harming people is high, the “Dangerous areas” - the risk of harming people is very high. Initial data for esti- mation risk: a). Buildings. These are objects where people live and work (offices, factories, markets) and public places. Potential risk after these area penetrations: for UAVs - very high; for people - moderate to high. b). Columns and wired communication. These objects are columns with its wires, masts, pipes antennas, which may endanger life and health of people nearby in case of breakdown. Potential risk after area penetration: for UAVs - moderate; for people - low to moderate. c). Trees and natural obstructions: These objects are trees, hills, mountains etc. Potential risk after area penetration: for UAVs - high to very high; for people - very low. d). Dangerous areas are classified on the basis of an application to the object of “Restricted area”. “Dangerous areas” themselves are not hazardous, but permanent residence increases the risk directly proportional to the residence time. Potential risk at the moment of penetration: for UAVs - very low; for people - very low. e). The potential risk when UAVs is staying in any period of time is a very com- plex task and depends on many factors, such as time, enclosing object, the previous trajectory of flight, maneuverability of UAVs, aerodynamic aspects, environmental conditions, etc. f). Track area. It is a part of the planned flight path after UAV flight in which 99.99% UAV is or will be located according to “Flight plan” data: for UAVs - high to very high; for people - high to very high. g). Track conflict area: It is unplanned part of space around “Track area”: for UAVs - high to very high; for people - high to very high. The results of values of risk/safety estimation of UAV flights in the city presented in Table 1. For example, risk of UAV flight in a restricted area equal to ten conven- tional units (multiplication the hazard/safety flight weight by the expected damage). Table 1. Results of areas estimation in risk using EJM. Obstruction Name and code Code Value of Risk Track Track area TA 50 Track Track Conflict area TCA 25 Track- Flight Flight UAV FA 1 Restricted area Building B-RA 10 Restricted area Columns and wired communication C-RA 9 Restricted area Trees and natural obstructions N-RA 8 Restricted area Horizontal buffering area HBA 7 Restricted area Vertical buffering area VBA 5 6 Fuzzy logic methods have been applied to assess risk levels and is based on the logical rules "IF (condition) - TO (conclusion)" [13]. In this case, the corresponding probabilities of events and the size of possible outcomes are considered as Fuzzy sets Pj and Lij, membership functions ( Pj ), ( Lij ) . Risk R is determined as: R ( Pj ) ( Lij ) The qualitative risk level indicator includes next characteristics of risk, namely: 1. “Very low risk” corresponds to the flight of UAV. 2. “Low risk” corresponds to restricted areas such as columns and wired com- munication; 3. “Average risk” corresponds to restricted areas such as a building; 4. “High risk” corresponds to dangerous areas; 5. “Very high risk” corresponds to the tracks area by busy of UAV. The degree of belonging of a certain value determined as the ratio of the number of responses in which the value of the linguistic variable occurs in a certain interval, to the maximum value of this number in all intervals. Experts were interviewed by the Delphi method in two rounds. There are 35 ex- perts attend the survey. The results of the survey are listed in Table 4. Units of inter- vals – 1 for 0 - 0,1; 2 for 0,1- 0,2, 3 for 0,2- 0,3,etc. Table 2. The results of the survey are listed Interval, units Value 1 2 3 4 5 6 7 8 9 10 18 16 5 1 0 0 0 0 0 0 2 0 8 20 11 1 0 0 0 0 0 3 0 0 0 7 17 12 4 0 0 0 4 0 0 0 0 0 0 2 23 15 0 5 0 0 0 0 0 0 0 7 9 24 kj 18 24 25 19 18 12 6 30 24 24 To process the data, using a matrix of prompts, which is a string with the elements defined by the formula: 5 k j bij , j 1, 10 . i 1 The matrix of prompts in our case has the form: М 18 24 25 19 18 12 6 30 24 24 Choose from the matrix of prompts the maximum element and convert the ele- ments of table 2 according to the formula: kmax max k j max 18; 24; 25;19;18;12; 6; 30; 24; 24 30 j 7 bij k max cij kj , The results of calculations are included in the Table 3, based on which the func- tions of membership will be built. Table 3. The results of calculations based on which the functions of membership will be built Interval, units Value 1 2 3 4 5 6 7 8 9 10 1 30,0 20,0 6,0 1,6 0,0 0,0 0,0 0,0 0,0 0,0 2 0,0 10,0 24,0 17,4 1,7 0,0 0,0 0,0 0,0 0,0 3 0,0 0,0 0,0 11,1 28,3 30,0 20,0 0,0 0,0 0,0 4 0,0 0,0 0,0 0,0 0,0 0,0 10,0 23,0 18,8 0,0 5 0,0 0,0 0,0 0,0 0,0 0,0 0,0 7,0 11,3 30,0 The maximum elements in each line are finding as: ci max max cij , i 1,2 ,..., m , j 1,2 ,..., n j c1max = 25,0, c2max = 21,0; c3max = 25,0; c4max = 21,4; c5max = 25,0. The value of the membership function is determined by the formula: ńij ci max The results of calculations are shown in the Table 4. Table 4. The results of experts’ opinion Interval, units Value 1 2 3 4 5 6 7 8 9 10 1,00 0,67 0,20 0,05 0,00 0,00 0,00 0,00 0,00 0,00 FA 0,00 0,42 1,00 0,72 0,07 0,00 0,00 0,00 0,00 0,00 TCA 0,00 0,00 0,00 0,37 0,94 1,00 0,67 0,00 0,00 0,00 TA 0,00 0,00 0,00 0,00 0,00 0,00 0,43 1,00 0,82 0,00 RA Dangerous 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,23 0,38 1,00 area The membership functions for estimation of risk were obtained based on experi- mental data. Assume that the minimum risk level is zero units and the maximum is 100 units respectively. The fuzzy-logic functions of estimation in risk moving UAVs in flight, track conflict area, track area, restricted area, and dangerous area in Fig.3 (after the first round of the poll). 8 Fig. 3 Fuzzy-logic function of estimation risk From the resulting diagrams, determined the quantitative indicators that corre- spond to the values of the linguistic variable "risk level"(after the second round of the poll): “Very low risk” corresponds to the quantitative significance of the level of risk in 10. “Low risk” corresponds to the quantitative significance of the level of risk in 35; “Average risk” corresponds to the quantitative significance of the level of risk in 60; “High risk” corresponds to the quantitative significance of the level of risk in 80; “Very high risk” corresponds to the quantitative significance of the level of risk in 100. 2.2 Definition minimal cost and safety of UAVs movement ways in town The mathematical methods such as the Dynamic Programming (DP), EJM, and fuzzy logic for estimation risks and minimal cost of ways of moving. For a definition, minimal cost and safety of UAVs movement ways in smart-city of town may use mathematical methods and modern air navigation rules. Estimation of an area in a fragment of the territory in fig.4a. Algorithm of definition minimal cost and safety of UAVs movement ways in town next: 1) Grid-analysis - cells are superimposing on a fragment of terrain (Fig.4b). 2) Risk assessment of Grid cells depending on the type of area (“Restricted” or “Dangerous”). 3) Finding the minimum cost path W1 for a UAV1 using the DP method for plan- ning a flight in a level L1: Wi (yi ) yi 1 ( RA; BA; TA; TCA; FA) min yi ( RA; BA; TA; TCA; FA) a b Fig. 4 Fragment of the territory for estimation minimal cost and safety of UAVs movement 9 Assessing the path W1 (level L1) of the UAV1 as “Dangerous”; 4) Finding the minimum cost path W2 for a UAV2 using the DP method for plan- ning a flight in a level L1, if necessary, the transition to the level L2, etc. For example, estimation and finding the minimum cost path W1 for a UAV1 on Fig.5, and the minimum cost path W1 for a UAV1 on Fig.6 (W1=39). Fig. 5 Risk assessment of Grid cells Fig. 6 The minimum cost path W1 for a UAV1. The transfer of a UAV flight from level L1 to level L2 is shown in Figure 7 when loading the first level. Fig. 6 Creating of root with flight levels Flow optimization and flexible redistribution of autonomous UAV routes in multi- level airspace is performed in accordance with air navigation rules. The documents of 10 ICAO include main recommendations for using UAVs, i.e. the operation of the UAV should minimize the threat of harm to life or health of people, damage of property, danger to other aircraft [1; 2; 11]. 3 What is next? Further research should be directed to the solution of practical problems of actions UAV’s operator in case of emergencies, software creation. The organization of CDM by all aviation operators using collaborative DM models (CDMM) based on general information on the flight process and ground handling of the UAVs. Models of flight emergencies (FE) development and of DM in Risk and uncertainty by UAV’s in FE will allow predicting the operator’s actions with the aid of the Informational-analytic and Diagnostics complex for research UAV operator’s behavior in extreme situation. For example, the synthesis of models for DM in an emergency if is solving logistic problem UAV flight in bad weather condition (emergency - "loss connection"). (in Figure 7). In the process of analysis and synthesis of DM models of AI in emergency tend to simplify models (stochastic, the neural network, fuzzy, the Markov network, GERT-models, reflexion models to deterministic models). Fig. 7 Solving Logistic task using UAVs flights (1 - takeoff and climb, 2 - echelon, 3 - cargo discharge, 4 - echelon reverse, 5 - descent and landing) In order to simulate DM under conditions of an emergency, next steps: an analysis of an emergency; intelligent data processing; analysis and identification of the situa- tion using stochastic models; decomposition of the situation as a complex situation into subclasses and the formation of adapted deterministic models of AI actions are made. The models for decision and predicting of EF using CDMM – technology pre- sented in Table 2. In cases of big and difficult data methods can be integrated into traditional and next-generation hybrid DM systems by processing unsupervised situation data in the deep landscape models, potentially at high data rates and in near real time, producing a structured representation of input data with clusters that correspond to common situation types [16]. Deterministic action model targeted to specific situation type. Another benefit of these models is a potential ability of such systems to learn to iden- tify relationships between different types of situations. 11 Table 2. The models for decision in FE using CDMM-technology Models Describing of modelling FE Expert assessment of the complexity of the flight stages (takeoff and climb, echelon, cargo discharge, echelon reverse, descent and landing) Neural Network Model to determine potential alter- native of the flight completion. Determination of weight coefficients of neural network (probabilities for the model – DM in risk) and effectiveness of flight completion: {YG ;YGаеr;YGlf; W}. Fuzzy logic to determine quantitative estimates of potential loss - functions of estimation risk R / outcomes U for next models of DM in Risk and Uncertainty-{gr} DM in Risk. Stochastic models types’ tree, GERT’s network (Graphical Evaluation and Review Tech- nique) for DM and FE developing. The optimal solution is found by the criterion of an expected value with the principle of risk - Adopt DM in certainty using Network Planning method and DM in Risk for each branch. Determined mod- els for an operators / AI with deterministic proce- dure - ti; ;Тcr;Тmid;Тmin;Тmax Optimal decision for action in EF (operator / AI model). The authors have developed a computer program for finding optimal solutions [17]. 4 Conclusion It was presented a problem of the performance of UAV’s flight plans for group flights or single flights for the decision of different target tasks in the city (monitor- ing, data acquisition, transportations, urban survey, etc.) using information technolo- gy, graph theory, and mathematical methods. The configuration and optimization of group flight routes for UAVs depend on the "target task" and results of estimation (cost/safety) territory for UAVs flights. The algorithms of building an ES for estima- tion of the performance of UAVs flights (group and single) in an urban locality and definition ways of minimal cost/safety of UAVs movement in town were presented. Further research should be directed to the solution of practical problems of actions UAV’s operator / AI models in case of emergencies and software creation according 12 to the target task. Next planned to use new methods for DM (Big Data, Blockchain technology, AI models, next-generation hybrid DM systems; Data mining, etc.). References 1. International Civil Aviation Organization (ICAO): Manual on remotely piloted aircraft sys- tems, Doc. 10019/AN 507. 1-ed. Canada, Montreal, (2015). 2. ICAO: Unmanned Aircraft Systems (UAS), Circ. 328-AN/190. Canada, Montreal, (2011). 3. Austin, R., UAS: design, development and deployment, John Wiley & Sons Ltd. USA, (2010). 4. Gulevich, S, Veselov, Y., Pryadkin, S., Tirnov, S.: Analysis of factors affecting the safety of the flight of UAVs. Causes of accidents drones and methods of preventing them. In Journal «Science and education», 2(12), pp.75–94, Russian, (2012). 5. Sładkowski, A., Wojciech, K.: Cases on Modern Computer Systems in Aviation. Chapter 3 Using Unmanned Aerial Vehicles to Solve Some Civil Problems. International Publisher of Progressive Information Science and Technology Research, pp.52-127, USA, Pennsylvania. (2019). 6. Shmelova, T., Bondarev, D.: Graph Theory Applying for Quantitative Estimation of UAV’s Group Flight. In Actual Problems of Unmanned Aerial Vehicles Developments (APPUAVD). IEEE 3d International Conference on Proceedings, pp. 328–331. Kyev, (2015). 7. Shmelova, Т., Sikirda,Yu., Kovaliov, Yu.: Decision Making by Remotely Piloted Aircraft System’s Operator / In APPUAVD. IEEE 4d International Conference in Proceeding. pp. 92- 99, Kyev, (2017). 8. LNCS Homepage, https://dronelife.com/2018/11/28/urban-air-mobility-the-first-uic2-forum- at-amsterdam-drone-week-shows-europes-commitment-to-smart-cities/, last accessed 2019/05/09. 9. Vyrelkin A., Kucheryavy, A.: The usage of unmanned aircraft solve the tasks of "a smart city" St. Petersburg, Russian (2016) 10. Olifer, V. Olifer, N.:Computer networks: principles, technologies, protocols. St. Petersburg. Russian (2006). 11. ICAO: Manual on Collaborative Decision-Making (CDM). 2nd ed. Doc. 9971. Canada, Mon- treal, (2014). 12. Kirichek, R., Makolkina M., Sene, J., Takhtuev, V.:Estimation quality parameters of transfer- ring image and voice data over ZigBee in transparent mode. In International Conference on Distributed Computer and Communication Networks pp. 260–267. Russian (2016). 13. Salem, M., Shmelova, T.: Intelligent Expert Decision Support Systems: Methodologies, Applications and Challenges, International Publisher of Progressive Information Science and Technology Research, pp.215-242, USA, Pennsylvania (2018). 14. Shmelova T., Bondarev D.: Unmanned Aerial Vehicles in Civilian Logistics and Supply Chain Management. Chapter 8 Automated System of Controlling Unmanned Aerial Vehicles Group Flight. International Publisher of Progressive Information Science and Technology Research, pp. 208-242. USA, Pennsylvania. (2019). 15. Shmelova, Т., Sikirda,Yu.: Applications of Decision Support Systems in Socio-Technical Systems. International Publisher of Progressive Information Science and Technology Research, pp.182-214USA, Pennsylvania. IRMA (2019). 16. Dolgikh S. Spontaneous Concept Learning with Deep Autoencoder In International Journal of Computational Intelligence Systems, Volume 12, Issue 1, November 2018, pp. 1 – 12, Canada. 17. Shmelova T., Yakunina I., Moiseenko V., Grinchuk M.: Computer program "Network analysis of a special case in flight". Certificate of registration of copyright for the product N55587 (2014)