=Paper=
{{Paper
|id=Vol-2236/paper-10-010
|storemode=property
|title=
The Use of Frame-Based Microprograms for Planning the Behavior of an Intelligent Unmanned Aerial Vehicle in an Uncertain Environment
|pdfUrl=https://ceur-ws.org/Vol-2236/paper-10-010.pdf
|volume=Vol-2236
|authors=Mikhail V. Khachumov,Vladimir B. Melekhin,Alexander S. Pankratov,Anton A. Andreychuk
}}
==
The Use of Frame-Based Microprograms for Planning the Behavior of an Intelligent Unmanned Aerial Vehicle in an Uncertain Environment
==
https://ceur-ws.org/Vol-2236/paper-10-010.pdf
79
UDC 004.82
The Use of Frame-Based Microprograms for Planning the
Behavior of an Intelligent Unmanned Aerial Vehicle in an
Uncertain Environment
Mikhail V. Khachumov*† , Vladimir B. Melekhin‡ ,
Alexander S. Pankratov† , Anton A. Andreychuk*†
*
Federal Research Centre “Computer Science and Control” of RAS
44/2 Vavilova st., Moscow,119333, Russian Federation
†
Department of Information Technologies
Peoples’ Friendship University of Russia
6 Miklukho-Maklaya st., Moscow, 117198, Russian Federation
‡
Department of applied mathematics and information technologies
Dagestan State Institute of National Economy
5 D.Ataeva st., Makhachkala, 367008, Russian Federation
Email: khachumov_mv@rudn.university, pashka1602@mail.ru, pankratov_as@rudn.university,
andreychuk@mail.com
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 efficiently 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.
Key words and phrases: UAV, frame-based microprogram, planning, predicate, be-
haviour, 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
80 ITTMM-WSS—2018
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 effective intelligent solver for an unmanned
aerial vehicle that can function purposefully in an uncertain environment is the develop-
ment 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 effective 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
first-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 possi-
bility 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
effective 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 effectiveness of inference when planning a UAV behavior.
The main problem of using production models of knowledge representation and processing
Khachumov Mikhail V. et al. 81
is the requirement for existence of a preliminary procedure for eliminating differences
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 proce-
dural 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 efficiently 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.
82 ITTMM-WSS—2018
2. Relevant references for transition to typical elements of procedural knowledge, that
contain operations allowing to achieve necessary conditions in a non-determined
environment.
3. A formalized description of the result obtained by executing corresponding opera-
tions.
The 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:
1 2 34 51 2
𝑄* ≪ 𝑃1* ↑ 𝑏1 (𝑦𝑖 (𝑋𝑖 )) ↓ 𝑃2* ↑↓ 𝑏2 (𝑦𝑖 (𝑋𝑖 )) ↑↓ 𝑄*1 (𝑦𝑖 (𝑋𝑖 )) ↑
(1)
3 45
↓ 𝑄*2 (𝑦𝑖 (𝑋𝑖 )) ↑↓=⇒ the goal is reached ≫,
where 𝑄* is the FMP identifier;
𝑃1* is the operator that checks the condition "There are no obstacles between UAV
location and object 𝑦𝑖 (𝑋𝑖 ) location";
𝑏1 (𝑋𝑖 ) is the operator "Fly to the object 𝑦𝑖 (𝑋𝑖 )";
𝑃2* is the operator that checks the condition "The object 𝑦𝑖 (𝑋𝑖 ) is located in the
visibility zone";
𝑏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 effective 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
Khachumov Mikhail V. et al. 83
in the logical form will take the following structure:
1 23 4
𝐹 (𝑋𝑖* ) = 𝑃1 (ℎ, 𝑦𝑖 (𝑋𝑖* )) ↑ 𝑃2 (𝑙, 𝑦𝑖 (𝑋𝑖* )) ↑↓ 𝑏2 (𝑦𝑖 (𝑋𝑖* )) ↑
1 42 3 3
↓ 𝐹1 (𝑦𝑖 (𝑋𝑖* )) ↑↓ 𝑃3 (𝑁, 𝑦𝑖 (𝑋𝑖* ))(𝐹2 (𝑦𝑖 (𝑋𝑖* ))) ↑ 𝑏1 (𝑦𝑖 (𝑋𝑖* )) ↑
4 41
↓ 𝑃4 (𝑙, 𝑦𝑖 (𝑋𝑖* )) ↑↓ 𝑏3 (𝑦𝑖 (𝑋𝑖* )) −→ the goal is reached
5 6 76 7
↓ 𝑃4 (𝑁, 𝑦(𝑋𝑗 )) ↑ 𝐹2 (𝑦𝑗 (𝑋𝑗 )) ↑↓ 𝑏1 (𝑦𝑗 (𝑋𝑗 )) ↑,
where 𝑋𝑖* are features that an arbitrary object should have for efficient 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 difference ℎ𝑖 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 difference ℎ";
𝑃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
84 ITTMM-WSS—2018
can include various microprograms of behavior (FMPs) that are necessary for its effective
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.
Figure 1. UAV trajectory motion
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 effect 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.
Khachumov Mikhail V. et al. 85
Acknowledgments
This research was supported by the Russian Science Foundation (Project No. 17-71-
10163).
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 sys-
tems 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 satisfiability-
problems 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 Pro-
cessing 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).
86 ITTMM-WSS—2018
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.