The Use of Frame-Based Microprograms for Planning the Behavior of an Intelligent Unmanned Aerial Vehicle in an Uncertain Environment

Abstract

In the paper we consider a model for the representation and processing of procedural knowledge of an intelligent unmanned aerial vehicle (UAV) that is based on the logic of condition-dependent predicates. Condition-dependent predicate calculus provides logically valid inferences in an arbitrary subject area by isolating monotone regions. The proposed knowledge model contains a set of frame-based microprograms of behavior (FMP) and overcomes certain disadvantages of known logic models. Procedures for planning purposeful behaviour of an unmanned aerial vehicle in underdetermined environment are proposed.The automatic planning of the purposeful UAV behavior in an underdetermined environment comes down to: substitution of objects for subject variables that implement slots functions in condition-dependent predicates and form the structure of FMP body; planning of purposeful activity through verification of conditions that determine possibility of eficiently performing operations included in the FMP structure and by selection of typical elements of procedural knowledge. In the experimental part of the paper we simulate UAV purposeful behaviour in a perturbed environment.

Keywords

• and phrases
• UAV
• frame-based microprogram
• planning
• predicate
• behaviour
• underdetermined environment
• procedural knowledge

-

Copyright © 2018 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the 1st Workshop (Summer Session) in the framework of the Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Tampere, Finland, 20–23 August, 2018, published at http://ceur-ws.org

1. Introduction

The analysis of state-of-the-art foreign and domestic researches on the planning behavior of robotic systems, including unmanned aerial vehicles (UAVs), identifies separate fields of research and subject area problems. Trajectory motion of a UAV in a perturbed environment is one of the central themes of the modern researches. In the paper [ 1 ] the authors consider an intelligent motion control system of mobile robots based on rules, which is able to respond rapidly to changes in the real dynamic environment. The problem of synthesis of the quadrocopter motion control is discussed in [ 2 ].The authors propose a new approach to the synthesis of control systems of mobile robots based on the principles and methods of synergetic control theory. In papers [ 3, 4 ] the problem of trajectory tracking of an unmanned aerial vehicle is solved by adjusting the fuzzy PID controller. Two-loop control system that uses adaptive neural networks to compensate external disturbances is considered. An overview of modern intelligent control systems of robotic aircrafts with a special focus on autopilots for small unmanned aerial vehicles is performed in [ 5 ]. We remark the presence of a large number of papers in the area of motion planning of robotic systems in an environment with obstacles. In [ 6, 7 ] the authors discuss construction of control and planning systems for autonomous agents (robot systems) in a non-deterministic environment. In [ 8, 9 ] the authors solve 3D-trajectory planning problems for an aircraft in the presence of uncertainty. The authors use a spatial grid as a model of the environment and propose heuristic search algorithms on graph models.

One of the central problems of creating an efective intelligent solver for an unmanned aerial vehicle that can function purposefully in an uncertain environment is the development of a model for representation and processing of knowledge in a general form. The necessity of such a representation of knowledge for an intelligent UAV is determined by the impossibility to form a detailed model of regularities in the environment. Due to that, in an underdetermined environment UAVs have to adapt to the current operating conditions that entails knowledge representation given in a general form. It is required to represent UAV knowledge in such a form that allows specifying them and adapting to the current environmental conditions in the process of purposeful activity, taking into account the nature of objects.

First-order predicate logic is one of the most common approaches associated with the representation and processing of knowledge in multi-purpose intelligent systems [ 10– 12 ]. However, the efective application of this model for the representation and processing of knowledge in the problem of planning purposeful activity of an intelligent UAV in underdetermined environment is limited for the following reasons: 1. To derive solutions a detailed knowledge representation model should be build [ 13 ]; 2. Second-order and higher-order predicates cannot be used in knowledge models, thereby functionality of intelligent problem solvers is significantly reduced [ 14 ]; 3. The laboriousness of the approach for deriving solutions to complex problems of knowledge processing, which is reduced to theorem-proving by the resolution rule [ 15 ]. This follows from the fact that in knowledge models based on the logic of ifrst-order predicates for the formal description of objects, events and regularities, semantic component is not used.

A significant contribution to the solution of the problem of the exponential complexity in deductive inference was made in [ 16 ]. In this paper the authors propose deduction algorithms based on the transformation of semantic networks, which provide the possibility of organizing several types of parallel inference and reducing the complexity of the theorem proof process. Decision-making procedures organized in this way allow building efective solvers of complex problems, but do not remove the rest of the above-mentioned limitations associated with the usage of first-order predicate logic for planning purposeful UAV activities in a non-deterministic environment.

Above mentioned circumstances have led to the transition to a new paradigm based on the special models of knowledge representation and production rules [ 17, 18 ]. But there is a significant limitation in the efectiveness of inference when planning a UAV behavior. The main problem of using production models of knowledge representation and processing is the requirement for existence of a preliminary procedure for eliminating diferences between actual and goal situations, but establishing such a procedure automatically in complex conditions is impracticable.

One of the first attempts to overcome this problem relies on using production models of knowledge representation and processing based on frame-microprograms of behavior (FMP) with the following structure: “input” “body” “output”. The input of the FMP is represented by an active fuzzy semantic network [ 19 ], vertices of such a network are labeled with specific objects in the process of purposeful behavior of an autonomous intelligent system. The input semantic network determines the situation when the intelligent system can successfully cope with the operations included in its body. The output of the FMP is given by a fuzzy semantic network describing the results of FMP operations. The disadvantage of such a model of knowledge representation intended for an intellectual UAV behavior planner (which has significant limitations on computing resources), is its cumbersomeness and the fact that it omit situations when performing all the FMP actions is not mandatory.

In this paper we propose a model for the representation and processing of procedural knowledge of an intelligent UAV for deriving solutions in the form of typical FMPs, which make it possible to overcome disadvantages of known logic models. The developed procedural model of knowledge is based on the logic of condition-dependent predicates [ 19 ], which provide the possibility to construct knowledge in a general form without using cumbersome representation structure. The automatic planning of the purposeful UAV behavior in an underdetermined environment comes down to: 1. Substitution of objects for subject variables that implement slots functions in condition-dependent predicates and form the structure of FMP body. This allows UAV to concretize the general purpose knowledge and use it to plan purposeful activities in the current operating conditions. 2. Planning of purposeful activity through verification of conditions that determine possibility to eficiently perform operations included in the FMP structure and by selection of typical elements of procedural knowledge. As a result, a chain of operations is formed allowing UAV to achieve its goal under specific operating conditions.

2.

Procedural knowledge model of a UAV

The proposed model for the presentation of a UAV procedural knowledge, as it was noted earlier, is based on logic of condition-dependent predicates. In general, the range of admissible values of each object variable ( ) ∈ , = ( ), = 1, in formulas is determined by a set of characteristics that allows to set the acceptable constants (specific objects and events). If we describe each object or event = ( ), = 1, 1 by the features then substitution of objects or events ( ) ∈ for variables ( ) ∈ is permissible if and only if the condition " ⊂ " is met. For example, the expression "To be able to fly (technical systems of Class A (strong wings, traction motor, no defects))" becomes a true statement when constants substituted into it are A class objects, for example, "aircraft KC21" has strong wings, a traction motor and no defects. Thus, in the condition-dependent predicate logic, an arbitrary multiple variable formula [ 1( 1), . . . ( ), . . . ( )] is true if and only if all the constants ( ) substituted for corresponding variables ( ) ∈ meet the conditions "( ⊂ )" [ 15 ]. Thereby, a UAV intelligent solver in the current operating conditions is able to verify an arbitrary statement by assigning objects to subject variables.

Consider the following two formulas: 1 = 1( , ( )) - "To fly to (UAV, object ( ))"; 2 = 2( , ( )) - "To perform an operation (UAV, object ( ))". We combine and extend these formulas with: 1. Conditions that must be met in an uncertain environment for successful performing

UAV’s operations. environment.

tions. 2. Relevant references for transition to typical elements of procedural knowledge, that contain operations allowing to achieve necessary conditions in a non-determined 3. A formalized description of the result obtained by executing corresponding operaThe aforesaid allows us to form a standard FMP "To perform an operation on a given object" given with the structure: "Identifier" "Procedures" "Exit". The identifier provides selection of an FMP by the kind of binary relations between UAVs and environmental objects. That relations can change while executing operations included in FMP procedures. FMP procedures include conditions that must be fulfilled for successful execution of the UAV operations contained in that procedures. The output of the FMP is given by the semantic network, whose edges labeled with relation values that are obtained for objects and UAVs when operations included in its procedures are processed. FMP conditions (that are determined by the values of binary relations) must be met for successful execution of the corresponding operations.

The structure of the described FMP can be represented in a form of a logic scheme [ 19 ] as follows: 3 1

2 45 * ≪ 1* ↑ 1( ( )) ↓ 2* ↑↓ 2( ( )) ↑↓ 1*( ( )) ↑ ↓ 2*( ( )) ↑↓=⇒ the goal is reached ≫, 34 51 2 (1) where * is the FMP identifier; location and object ( ) location";

1* is the operator that checks the condition "There are no obstacles between UAV visibility zone"; 1( ) is the operator "Fly to the object ( )"; 2* is the operator that checks the condition "The object ( ) is located in the 2( ) is the operator "Execute the operation 2 on the object ( )"; 1* is the FMP "To plan and work out the route of convergence with the object ( ) in the presence of obstacles";

2* is the FMP "Ensure fulfillment of the 2* condition".

The numbered arrows indicate the direction of the transition from one operator to another when the conditions

* given before operator are not met.

Thus, to provide an intelligent UAV with the necessary functional capabilities, the model of procedural knowledge can be represented in the form of a set of FMPs. This model allows to significantly reduce the search space of fairly complex tasks by selecting several efective operations at each step of behaviour planning.

3.

The problem of planning UAV purposeful activity

Let us consider the case when the purpose of a UAV mission in an underdetermined environement is set in a procedural form, for example, "Execute an operation on an object ( )", "To fly close to the object ( )", etc., where , are sets of features correspondingly describing objects ( )" and ( ). In this case, FMP output is not used in the decision-making process when planning UAV’s activity.

Let the the intellectual solver of the UAV’s tasks in order to achieve a given goal selects FMP ( *) "Perform an operation on the object ( )". FMP procedures in the logical form will take the following structure: 4 41 ↓ 4(, ( *)) ↑↓ 3( ( *)) −→ the goal is reached 5 ↓ 4(,

6 76 7 ( )) ↑ 2( ( )) ↑↓ 1( ( )) ↑, where * are features that an arbitrary object should have for eficient processing of the operations of a given FMP ( *), * = should have permissible size and weight and be immovable;

1(ℎ, ( *)) is the operator that checks the condition "The object ( *) is located higher than the zone of visibility" in order to establish if there is a diference ℎ between actual and required (for succes execution of the operation 2( ( *))) situations; 2(, ( *)) is the operator that checks the condition "The object ( *) is located further than the zone of visibility (checks the distance )"; 2( ( *)) is the operator "Execute an operation 2 on the object ( *)"; 1( ( *)) is the FMP "To eliminate the diference ℎ "; 3(, ( *)) is the operator that checks the condition "There are obstacles between the UAV and waypoint ( *)";

2( ( *)) is the FMP "To plan avoiding obstacles and work out the route to the object ( *)"; 1( ( *)) is the operator "To get close to the object ( *)"; 4(, ( )) is the operator that checks the condition "The object ( ) is located within the zone of visibility (checks the distance )"; 3( ( *)) is the operator "Execute an operation 3 on the object ( *)"; 4(, ( )) is the operator that checks the condition "There are obstacles between the UAV and waypoint ( )";

2( ( )) is the FMP "To plan avoiding obstacles and work out the route to the object ( )"; 1( ( )) is the operator "To get close to the object ( )".

When a frame-based microprogram of the UAV behavior is selected, the UAV forms (relative to its location) the model of the operating area in the form of a semantic network = (, , 0), where: is a set of vertices marked with objects located in the operating area; a set of edges, that are determined by the binary relations between the UAV and other objects; 0 is the key vertex that correspond to the UAV. Semantic network determines current situation and is constructed relative to key vertex.

The intelligent solver takes descriptions of goal object ( ) and other objects of the operating area (that are associated with the execution of the selected FMP) and checks the condition "All the assosiated objects satisfy the requirements of substitution into the selected frame-based microprogram". If all conditions are met the decision is made that the selected FMP is feasible in the current situation and the UAV starts to implement FMP’s operations. Otherwise, the intellectual solver makes a decision that none of FMPs allow performing the current task. In this case, the UAV starts planning the behavior on the basis of typical elements of the procedural knowledge model in the form of frame-based operations with the following structure: "Conditions that are necessary for execution of the operation ( ( *))" "Operation and description of objects’ features" "Operation result".

FMPs included in the plan of a UAV behaviour are determined by identifiers that are contained in the structure of the initial frame-based microprogram. Each microprogram can include various microprograms of behavior (FMPs) that are necessary for its efective execution the current situation. To solve more complex problems UAV mission, as a rule, is given in a declarative form, for example, in the form of a semantic network * given in the state space.

4.

Experimental research

As an experimental task, we use the problem formalized in a form (1).The problem is to reach an object in the presence of obstacles and perform an operation on the object, for example, to take some pictures. The process of UAV motion in the presence of obstacles and under wind loads is simulated in MATLAB Simulink system. Details related to the selection of the mathematical models of the flight vehicle and wind loads, as well as to the development of an intelligent control system are described in [ 20 ]. The developed simulating system contains a special module of intelligent control, realizing strategies and control rules for prompt response to changes in the external environment. The results of simulating are shown in Figure 1.

Here, UAV start point (brown color), trajectory of UAV motion (red color), impassable obstacles (cyan color) and the goal object (green color) are shown. It can be seen that the control rules enable flight vehicle to successfully cope with the mission. UAV trajectory demonstrates the efect of obstacles and wind loads on the motion. The main criterions for aircraft control quality are: integral evaluation of the deviation from the planned route in the process of motion; visual assessment of the flight trajectory. 5.

Conclusions

The use of condition-dependent predicate calculus allows to represent UAV knowledge in an arbitrary subject area and organize planning various types of purposeful activity in a priori underdetermined environement. The proposed model for the representation and processing of procedural knowledge allows UAV to plan its behaviour automatically with polynomial complexity. For this purpose, a decision output tree is formed, which includes frame-based microprograms of behavior that are necessary to achieve the goal.

Acknowledgments

This research was supported by the Russian Science Foundation (Project No. 17-7110163).

References

1. A. Pandey , D. R. Parhi , Multiple mobile robots navigation and obstacle avoidance using minimum rule based anfis network controller in the cluttered environment , International journal of Advanced Robotics and Automation (1) ( 2016 ) 1 - 11 .

2. G. Veselov , A. Sklyarov , S. Sklyarov , Synergetic approach to the quadrotor helicopter control in an environment with external disturbances , in: Proceedings of 2016 International Siberian Conference on Control and Communications (SIBCON-2016).

3. B. E. Demir , R. Bayir , F. Duran , Real-time trajectory tracking of an unmanned aerial vehicle using a self-tuning fuzzy proportional integral derivative controller , International Journal of Micro Air Vehicles 8 ( 4 ) 252 - 268 .

4. C. Zhang , H. Hu , J. Wang , An adaptive neural network approach to the tracking control of micro-aerial vehicles in constrained space , International Journal of Systems Science 48 ( 1 ) 84 - 94 .

5. F. Santoso , M. Garratt , S. Anavatti , State-of-the-art intelligent flight control systems in unmanned aerial vehicles , IEEE Transactions on Automation Science and Engineering 15 ( 2 ) 613 - 627 .

6. P. Allgeuer , S. Behnke , Hierarchical and state-based architectures for robot behavior planning and control , in: Proceedings of 8th Workshop on Humanoid Soccer Robots.

7. J. A. Xavier , S. R. Selvakumari , Behavior architecture controller for an autonomous robot navigation in an unknown environment to perform a given task , International Journal of Physical Sciences 10 182 - 191 .

8. L. Filippis , F. Guglieri , G. and Quagliotti, Path planning strategies for uavs in 3d environments , Journal of Intelligent and Robotic Systems 65 ( 2012 ) 247 - 264 .

9. M. Kothari , I. Postlethwaite , A probabilistically robust path planning algorithm for uavs using rapidly-exploring random trees , Journal of Intelligent and Robotic Systems 71 ( 2 ) ( 2013 ) 231 - 253 .

10. S. Russell , P. Norvig , Artificial intelligence: a modern approach , Prentice Hall, 2010 .

11. A. Kelly , Robotics: mathematics, models, and methods, Cambridge University Press, 2013 .

12. J. Kober , J. Peters , Learning motor skills: from algorithms to robot experiments , Springer, 2014 .

13. N. J. Nilsson , Principles of artificial intelligence , Springer, 1982 .

14. L. G. F. , Artificial intelligence: structures and strategies for complex problem solving, Addison- Wesley , 2008 .

15. Y. Kilani , M. Bsoul , A. Alsarhan , A. Al-Khasawneh , Survey of the satisfiabilityproblems solving algorithms , Intern. J. Advanced Intelligence Paradigms 5 ( 3 ) ( 2013 ) 233 - 256 .

16. V. Vagin , O. Morosin , M. Fomina , Inductive inference and argumentation methods in modern intelligent decision support systems , Journal of Computer and Systems Sciences International 55 ( 1 ) ( 2016 ) 79 - 95 .

17. G. Osipov, Intelligent dynamic systems, Scientific and Technical Information Processing 37 ( 5 ) ( 2010 ) 259 - 264 .

18. L. Bernshtein , V. Melekhin , Planning of polyphase behavior for self-organizing intelligent systems , Journal of Computer and Systems Sciences International 39 ( 5 ) ( 2000 ) 808 - 811 .

19. L. Bernshtein , V. Melekhin , Decomposition of fuzzy semantic nets for planning integral robot operations , Journal of Computer and Systems Sciences International 31 ( 3 ).

20. M. Khachumov , V. Khachumov , The problem of target capturing by a group of unmanned flight vehicles under wind disturbances , in: 2017 Second Russia and Pacific Conference on Computer Technology and Applications (RPC) , 2017 .