<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Bi-Soft Open Sphere Topology Model of Configuration Space for Reactive Joint Motion Planning of Unmanned Vehicles</article-title>
      </title-group>
      <contrib-group>
        <aff id="aff0">
          <label>0</label>
          <institution>Kherson State Maritime Academy</institution>
          ,
          <addr-line>Ushakova Str., 20, Kherson, 73000</addr-line>
          ,
          <country country="UA">Ukraine</country>
        </aff>
      </contrib-group>
      <abstract>
        <p>This work presents a model of configuration space for the reactive joint motion planning of unmanned vehicles' ensemble. This model is based on a dynamic bi-soft topology, which allows describing the safety conditions of the joint motion of a multitude of vehicles. The approximation space of the topology is constructed in the system of nested open spheres based on an angular coordinate system. The spheres are discretized onto sector-like cells. The proposed bi-soft topology is based on a two-level breakdown of the configuration space. On the first level, the configuration space is broken down onto “free to move” and obstacle subspaces taking into account uncertainties of observations. On the second level, the obtained soft subspaces are broken down onto safety zones with blurred boundaries. The offered topological model can be used in a hybrid motion planner combining potential field and random sampling methods. The use of the proposed bi-soft topology allows reducing the computational complexity of the motion planning task using partitioning of the configuration space and path search heuristics based on the calculation of the cell volume.</p>
      </abstract>
      <kwd-group>
        <kwd>soft set</kwd>
        <kwd>soft topology</kwd>
        <kwd>open sphere</kwd>
        <kwd>unmanned vehicles</kwd>
        <kwd>reactive path planning</kwd>
        <kwd>collision avoidance</kwd>
        <kwd>safety zones</kwd>
      </kwd-group>
    </article-meta>
  </front>
  <body>
    <sec id="sec-1">
      <title>-</title>
      <p>The great progress of the latest years in the development of unmanned vehicles (UV)
has led to their use in large teams to address a sufficient number of important
realtime tasks. UVs belonging to the large teams can be characterized by different sizes,
functionalities, roles, motion parameters, and ever environments. For example, forest
fire-fighting [1] has recently become an important domain to use the large teams of
UVs where unmanned aerial vehicles of various types can provide fire detection,
localization, and monitoring missions, while a variety of unmanned ground vehicles
(e.g. bulldozers, excavators, tanks, etc.) can be simultaneously involved in fire
extinguishing missions. Another example is a smart fishery task, where unmanned aerial
vehicles can be involved in searching for fishing flocks, unmanned underwater
vehicles can identify fish in flocks, direct and accompany them, as well as unmanned
boats can carry fishing gear.</p>
      <p>The authors are concerned with the teams of UVs of various types providing
different roles and functions while executing their missions jointly and simultaneously to
achieve the common objective. Such a team is often called a heterogeneous ensemble
due to differences in vehicles’ features and their roles in the team [2]. Unlike the
widely used concepts of swarms, which bring together a significant number of
homogeneous UVs performing the same role, the concept of the ensemble has a crisp
structure represented by its spatial and functional configurations taking into account
different roles of involved UVs. Regarding the given role, each UV executes a certain
scenario of the mission together with other members of the ensemble complementing
each other.</p>
      <p>However, the missions usually involve a certain number of UVs in the joint
simultaneous movement within a confined space, which is open to any other moving
objects (manned or unmanned), which may disturb not only the movement of the certain
UVs but also the execution of the ensemble mission at all. For example, in the smart
fishery mission, the invasion of third-party moving objects (MOs) into the area of
mission can require changes in the trajectories of some UVs, which is not an easy task
because of the limitations of safe motion, communication distance, fishing gear cover,
etc. Furthermore, the change of the trajectories of some members of the fishery
ensemble due to safety reasons entails the changes of the trajectories of other members
of the ensemble due to requirements on keeping the spatial configuration.</p>
      <p>The presented considerations pose the problem of dynamic control of the joint
motion of the ensemble members. Thus, using the “sense and avoid” techniques [3], UVs
must move to the given target avoiding obstacles and collisions but keeping the
predetermined spatial configuration. The more complicated the structure and joint
mission of the ensemble, the more difficult the motion control of UVs.</p>
      <p>The problem addressed in this paper relates to the coordinated joint motion of
heterogeneous UV ensembles. Further, we will consider any obstacles as static objects
and any vehicles as moving objects (MO) irrespective of the environment.
2</p>
    </sec>
    <sec id="sec-2">
      <title>Literature analysis</title>
      <p>The problem of dynamic control of the joint motion of UVs is the subject of sufficient
interest of many researchers investigated and reflected in numerous publications. In
general, features of the joint ensemble motion differ from the other known formation
structures such as swarms, flocks, leader-follower structures, and virtual structures [4]
where the entire formation is always considered as a single virtual body [5].</p>
      <p>Let us consider joint UV motion within a space C . Executing a given scenario,
each UV Ai moves along a pre-planned path Pi represented as a sequence of
waypoints (WP) or as a sequence of pairs “timepoint-waypoint” (TP-WP), which define
desired spatial locations at the given time moments described by TPs. Thus, the path
Pi can be almost always represented as a time-arranged sequence
Pi  TPi1,WPi1  ,...TPij ,WPij ,...TPin ,WPin  , TPi1  TPij  TPin , which can be
conveniently used to control the Ai motion.</p>
      <p>In the literature, the most of the suitable approaches to build the path are inspired
from global path planning methods, the systematic review of which is presented in
[6]: the roadmap approach based on the visibility graph algorithm or Voronoi diagram
algorithm, cell decomposition approach, potential field approach, and random
sampling approach including probabilistic roadmap method (PRM) and Rapidly
Exploring Random Trees (RRT). The last two methods are used most often.</p>
      <p>Recent motion planning developments focused on environments that change over
time or are not quite known are more tangible to the problem of the joint UV motion.
When UV moves, it is exposed to a significant number of both dynamic (e.g., wind)
and situational (MOs that disrupting its trajectory) perturbations. When such a
perturbation is observed, UV must react and maneuver to avoid the collision. At the same
time, it should be worried about keeping both the given spatial configuration (i.e.,
hold its relative position during the mission execution) and the safe distance from
other MOs including the members of the ensemble and various obstacles. Therefore,
the initial path Pi can be changed by the displacement of certain WPs forcing other
ensemble members to adjust their motion trajectories.</p>
      <p>Thus, we need to update the motion paths to adapt them to dynamic changes in the
environments. It can be reduced to the dynamic path planning task [7], which can be
solved by re-planning some fragments of the path or adjusting its parameters (in our
case – locations of WPs). It allows us to obtain a new path ahead of time.</p>
      <p>Taking into account the restricted computing capabilities of UVs’ on-board
computers as well as a lack of time to avoid collisions and obstacles, we should use quick
enough methods to re-plan the path Pi . If UV needs to be capable of planning the
path of its motion in time to react to dynamic environments as well as situational
perturbations, we should provide reactive (real-time) planning immediately during the
motion [7]. Thus, the real-time motion planning algorithm could not be iterative.</p>
      <p>The potential field method considers obstacles as repulsive fields while targets as
attractive fields, so the UV motion is guided to the attractive points avoiding the
repulsive points. However, due to the use of iterative optimization techniques this
method is so computationally intensive that it is not suitable for reactive collision
avoidance in general [7].</p>
      <p>Random sampling has emerged as a powerful tool for path planning in
highdimensional configuration spaces, its algorithms are both efficient and simple to
implement. However, multi-query planning algorithms (PRM, DRM) have important
issues such as a straightforward uniform sampling distribution and the implicit
representation of space that need a pre-computation [8]. In contrast to multi-query
planning, there is no pre-computation in the single-query algorithms like RRT, which can
construct small roadmaps on the fly. However, this algorithm is prone to
oversampling while the sampling distribution should be defined explicitly. Unfortunately,
random sampling algorithms are not complete in the sense that they cannot consider
such a situation when no existing paths are found [6]. Due to the use of lookup tables
saving motion primitives, such algorithms are infeasible for resource-limited UVs [9].</p>
      <p>To overcome the above-mentioned disadvantages, it is advisable to develop a
hybrid method combining RRT and potential field complementing each other. To level
the sampling issues, we should develop a model of the configuration space that can
reduce the computational complexity by abandoning iterative calculations. A key
aspect to combine the RRT and potential field methods is to build an approximate
topological model endowed with metric properties to avoid intensive calculations.
Well-known geometric approaches based on relative spatial estimates (so-called
"point of collision") such as “cones”, “safety domains”, “closest points to approach”,
etc. [9-12] can be used to do this.</p>
      <p>This work aims to develop the approximate model of the configuration space in the
context of the control of the joint motion of unmanned vehicles within confined areas.
This model is needed for subsequent implementation of a hybrid reactive
pathplanning method combined with both RRT and potential field methods. To overcome
the computational complexity issue, we must develop a topological model using soft
discretization. The developed model allows analyzing big data streams coming from
remote sensors and representing them in a user-friendly style.
3</p>
    </sec>
    <sec id="sec-3">
      <title>Formal problem statement</title>
      <p>Let configuration be a set of k parameters that determine the location of the UV in
the space of the joint motion (and, possibly, its motion parameters) uniquely. Each
UV can be described by a moving point in a k -dimensional space C called the
configuration space. A configuration q is a single point within C . A certain
configuration q is free if the UV located at q does not collide with any obstacles or MOs.</p>
      <p>A “free to move” subspace F is a subset of all free configurations in C , while an
obstacle subspace B is a complement of F to C : B = C \ F [6].</p>
      <p>Planning is always performed within the configuration space C .</p>
      <p>The motion planning problem concerning the UV Ai can be defined as finding a
path Pi from a start configuration qs to a target configuration qt such that Pi lies
entirely within the free subspace F . A path Pi is defined by a continuous sequence
of configurations [7]. A path planning algorithm is complete if it finds a path
whenever one exists and reports none exists otherwise [6].</p>
      <p>Reactive motion planning at a time t can be defined as changing the path Pi from
a current configuration q t  to the target configuration qt whenever a change of the
configuration space C takes any fragments of the path Pi beyond the free subspace
F (i.e., a fragment of Pi collides with the obstacle subspace B ).</p>
      <p>An example is shown in Fig. 1, where UV Ai moving to the target configuration
qt along the path Pi with velocity v meets an obstacle U at current configuration
q t  . The collision conditions can be described by a collision cone constructed by
dropping tangents r1, r2 from q t  to B representing the safety zone around U .
If the velocity vector v lies within the collision cone, Ai violates B . Decomposition
of v in terms of the tangents r1, r2 gives us v  ar1  br2 . If a  0 and b  0 , then the
obstacle U is critical to Ai . Thus, Pi must be replanned by adding a new waypoint,
which should be the nearest aiming point determined on B by tangents r1, r2 .
4</p>
    </sec>
    <sec id="sec-4">
      <title>Building a basic spatial model</title>
      <p>Consider a three-dimensional linear uniform space C . Let Y be a set of certain
elements, and T be a set of time points t strictly ordered by T having the initial count
t0 . Let us introduce a norm
y  min  y t  within C , where y Y , t T , and a</p>
      <p>c t0,T 
corresponding metric С  y1, y2   y1  y2 such as:
1. С  y1, y2   y1  y2  0  y1  y2 ;
2. С  y1, y2   y1  y2  y2  y1 С  y2, y1 ;
3. С  y1, y2  С  y1  a, y2  a ;
4. С  y1, y2    С  y1, y2  .</p>
      <p>Define the basis e1,e2,e3 within C so that the metric С remains uniform. Therefore,
the decomposition of a vector v 1e1  2e2  3e3 gives the coordinates v1, 2, 3  of
a certain point of the space C describing the position of MO. Currently, we have built
a basic continuous spatial model based on the Cartesian coordinate system that needs
to be sampled to provide sufficient performance.</p>
      <p>Using the metric С , we impose a metric grid of coordinate lines of size
  1   2  3 onto space C with an origin 1  2 3  0 , so that the coordinate
lines form a set D of isometric cubic cells d of size    . Thus, we obtain a space
discretized by the grid D  dxyz , in which the cells dxyz are the smallest homogeneous
spatial objects, whose coordinates x, y, z correspond to e1,e2,e3 .</p>
      <p>Although the basic model we obtained is consistent with the information received
from the sensors observing the navigation situation, including the rectangular cell
coordinate system, however, to represent the safe motion conditions adequately, this
model must be adequately transformed.
5</p>
    </sec>
    <sec id="sec-5">
      <title>Building an open sphere topology</title>
      <p>Let us choose the position of the UV as an observer and endow it with the properties
of origin. Let us construct a sphere V  C with an infinite radius around this position
and define the angular coordinate system, as it is shown in Fig. 2.
Accordingly, the coordinates of UV can be defined as Crd  A  1, 2, r  , where 1
is latitude,  2 is longitude, and r is a distance from the origin to the UV position.</p>
      <p>Let's create a metric  B within the angular coordinate system with the properties
similar to using an isometric bijection Obviously,
 С  : С   B .
 : 1, 2 , 3   Crd 1, 2 , r  , so we can transform the coordinates of the
observation space C to the angular coordinates in the constructed sphere V .</p>
      <p>At the next stage, we construct a discrete sphere model using metric  B and
mapping  , and place an angular grid of coordinate lines with equal angles and equal
discrete of the radius   1, 2,r on the sphere V with the origin point
Crd 0,0,0 , so that the coordinate lines form a set W of cells w (Fig. 3).
Thus, we have got a sampled sphere W  wijk , whose cells wijk are the smallest
sectors of the sphere V with the angular coordinates i, j, k . The cells wijk are
homogeneous objects concerning their interior.</p>
      <p>Obviously, the sampling of a sphere V by a set of cells W constitutes a
topological space TVW  V , Def W  if the cells of each pair  wl , wm  are internally
homogeneous and disjoint, that is l, m wl  wm   , and their union completely covers the
sphere V , so that V  wl W wl . The resulting topology Def W  is nonlinear since the
further from the center of the sphere, the larger the volume of each subsequent cell.
6</p>
    </sec>
    <sec id="sec-6">
      <title>Building the first level of soft open sphere topology</title>
      <p>Let Y  yiik0 be a set of k  1 possible states of the cell wijk W . For example, the
state y0 corresponds to an “empty” cell containing no objects, the state y1
corresponds to a cell containing a certain obstacle, the state y2 corresponds to a cell that is
a target for the UV motion, the state y3 corresponds to a cell containing UV from its
ensemble, and the state y4 corresponds to a cell containing MO considered as
“intruder” because it does not belong to the ensemble.</p>
      <p>Thus, a subset of states y1, y2, y3, y4 Y attributes the appropriate cells to the
category of “occupied”, as well as y0 Y attributes the cell to the category of “free to
move”. Correspondingly, the set of cells having the state y0 constitutes the sampling
of “free to move” subspace F of configuration space C , while the set of cells having
the state y1, y2, y3, y4 constitutes the sampling of the obstacle subspace B of
configuration space C .</p>
      <p>Furthermore, the set of cells having the state y2 corresponds to an attractive
manifold in terms of potential fields while the set of cells having the state y1, y3, y4
corresponds to a repulsive manifold respectively. Since the state of a cell depends on time,
each above-mentioned is dynamic, consequently, the partitioning of configuration
space C onto F and B subspaces is also dynamic.</p>
      <p>Assume that the set W is a universe and the set Y is a set of parameters. A pair
 ,Y  constitutes a soft set of cells if  is a certain mapping Y into the set of all
subsets of the set W ,  : yi  2W [14]. In other words, the soft set is a parameterized
family of subsets of the set of cells W . A certain set , yi  , yi Y from such family
can be regarded as the set of yi -approximated elements of the soft set [15], or, in
other words, as an yi -element of the soft set denoted by i .</p>
      <p>Thus, the universe W can be partitioned by the soft set  ,Y  that is the union of
all k of its yi -elements, where   i ik1 , which constitute a multitude of pairs
i   , yi  : yi  Y ,  , yi   2W  . The soft set is often associated with the set of
equivalence classes induced by a certain indiscernibility relation that depends on time
[16]. We can define such relation of yi -indiscernibility dynamically given on the set
of cells W by yi Y  Wyi t    wm, wn  W W
yi  wm,t   yi  wn,t  .</p>
      <p>Therefore, each yi -element of the soft set i provides the partitioning of the set of
cells W into equivalence classes given by the yi -indivisibility relation Wyi t  at the
moment t . In other words, the parameterized family of subsets of the set W , which
constitutes the yi -element of the set i , can be considered as a factor-set W / Wyi t 
consisting of all equivalence classes of W induced by relation Wyi t  . Thus, the pair
aprW  W ,Wyi t  defines the dynamic approximation space [17].</p>
      <p>Let  be an empty set, W be the universe, and elements W / Wyi t  are
elementary sets so that the finite union of one or more of elementary sets is a compound set.
If the family of all compound sets is Def aprW  , then the dynamic approximation
space uniquely defines the dynamic topological space TWWi t   W , Def aprW  .
y</p>
      <p>It is known that Def aprW  is a topology on W if its subsets satisfy the following
conditions for any A, B W [18]:
1.   Def aprW , A  Def  aprW ;
2. A, B  Def (aprW )  A  B  Def (aprW ) ;
3. A, B  Def aprW   A  B  Def aprW  .</p>
      <p>Consequently, Def aprW  is the family of open sets and TWWi t   W , Def aprW  is
y
the dynamic topological space. The mapping t  in the given interpretation is also
dynamic and uniquely assigns each cell of the universe W to a certain yi -element of
the soft set t,Y  at the time moment t . If the results of the observation are
uncertain, we can interpret them by “degrees of confidence” that the cells are “free to
move” or contain obstacles at the moment of consideration. For this purpose, the
function t  can be represented as a fuzzy set, so that t  : yi  0,1 , where the
degree of confidence has a range of values in the interval 0,1 . Accordingly, we need
to soften the relation Wyi t  using a tolerance relation  Wyi t  instead of the
equivalence one. Thus, we have got a dynamic fuzzy soft set of cells  t,Y instead of the
soft set [19]. Specifying a certain threshold  0,1 , we will be able to cut off from
the consideration all those cells wW , for which the degree of confidence at the
moment t is lower than a given threshold  , i.e.   yi ,t  wW :  , yi w   [20].
Each yi -element  t, yi  of the corresponding fuzzy soft set consists of only those
cells wW , for which the degree of confidence that their state is yi Y , is greater
than the threshold  at the moment t . As a result, we obtain the approximation space
aprW  W , Wyi t  and the dynamic fuzzy soft topology T S t  that describe
configuration space C at the moment t .
7</p>
    </sec>
    <sec id="sec-7">
      <title>Safety zones assessment</title>
      <p>Safety domains usually defined around obstacles and moving objects significantly
affect the solution of the reactive motion planning problem.</p>
      <p>Let   0,...m be a set of distance limits such that
 B  A, B  Crd  A  Crd  B  i for each pair  А, В of moving objects.</p>
      <p>Let þ = ю0, ю1, ю2 be a set of time limits and T be a metric given on T as
ti  t j T  þ with the following properties ti ,t j ,tk  T :
1. T ti ,t j   0  ti  t j ;
2. T ti ,t j   T t j ,ti  ;
3. T ti ,tk „ T ti ,t j  T t j ,tk  .</p>
      <p>In the case of the stationary obstacle, the assessment of the safety motion based on
the collision cone is illustrated in Fig. 1 (Section 3). In the case of two moving
objects, the assessment becomes more complex and usually is based on evaluation of the
closest approach point (Fig. 4) concerning the time TCPA and distance DCPA [9]. It is
possible to evaluate the potential collision based on time TCPA and distance DCPA to
the closest approach point using both metrics  B and T , for example, if
 B  DCPA, A1    m and T TCPA, D1 / V1   ю1 , there is a threat of collision.
It should be noted that such interactions are not always symmetric. In general, it
depends on the vehicle safety domains, which usually are calculated based on its course
and velocity, as well as several environmental factors such as weather [13]. Thus, in
Fig. 4 vehicle A1 interacts with the vehicle A2 dangerously while the vehicle A2
interacts with the vehicle A1 not dangerously due to the difference in the size of their
determined safety domains.</p>
      <p>To take into account spatial zones with different danger levels related to the safety
domain of the vehicle, we can define a set of safety assessments   0,...k ,...n and
assessment function   A, B  i that returns safety assessment i for a vehicle A to
the moving object B using both metrics  B and T , as well as respective courses and
velocities of A and B .</p>
      <p>Based on the set of safety assessments  , we can restrict a discretized sphere W
by representing it as a system of m  1 nested spheres Wn ,...W0 having a common
center at the origin and corresponding radiuses from m to 0 . Using such a system of
nested spheres, we will be able to take into account certain spatial zones, which are
determined by the safety conditions of the UV joint motion. For example, based on
the UV motion parameters with respect to the conditions of collision avoidance, there
can be defined forbidden hA , dangerous hB , restricted hC , and free to move
(unlimited) hD zones bounded by corresponding spheres with boundary lines B3, B2 , B1 that
meet the assessment levels 3,2 ,1,0 respectively (Fig. 5) [21].</p>
    </sec>
    <sec id="sec-8">
      <title>Building a second level of soft open sphere topology</title>
      <p>At the first level, we have parameterized the yi -subset family of the set of cells W ,
which constitutes the soft set of cells t,Y  (or possibly fuzzy soft one  t,Y )
related to the partitioning the cells into equivalence classes by their category.
At the second level, it is necessary to break down each yi -subset of the set W into
safety zones according to the constructed system of spheres having radiuses 0,...n to
take into account the distribution of cells between the corresponding safety zones of
the nested spheres Wn,...W0 . Since the safety assessments for interacting vehicles can
differ due to the differences in the size of their safety domains, there is no possibility
to break down the entire set of cells W into safety zones. Thus, we need to partition
each yi -subset of W onto each  j  separately.</p>
      <p>Let t,Y  be a soft set on W such that  t   i t 
k
i1
, which consists of
the union of all k of its yi -elements i t     t  , yi  : yi  Y ,   t  , yi   2W  .
i t be an  j -indiscernibility relation given on the yi -element i t  of the
</p>
      <p>Let  j
soft set t,Y  , such that  j im0 ji t   wm, wn  Wj Wj wm  i t , wn  i t  .
Thus, we can construct an  j -approximation of each yi -element of the set t,Y  .
Therefore, each  j -element of the soft set i t,Y  provides the partitioning of the
yi -element of the set t,Y  into correspondent equivalence classes given by the

 j -indivisibility relation  j</p>
      <p>i t at the moment t . In other words, we parameterize first
the family of subsets of the set W , which constitutes the yi -elements of the set
i t  , then we parameterize the family of subsets of each set i t,Y  , which
constitutes the  j -elements of the set i t  . Just like the pair aprW  W ,Wyi t  defines
the dynamic approximation space at the first level, the pair apri t   i t , j 
i t
defines the dynamic approximation space at the second level.</p>
      <p>Thus, we obtain a two-leveled soft set of cells t,Y ,  also named as a bi-soft

set. The correspondent dynamic bi-soft topology T t   aprW , Def apri t  is the
partition of yi -elements of the soft set of cells t,Y  into approximated subsets of
cells  ji t  , which are  j -elements of the yi -elements of the set t,Y ,  .
Clear
ly, T t   W ,Wyi t , Def  i t , j</p>
      <p>i t  .</p>
      <p>Each element  ji forms a soft topology T ji t  . Thus, each  j -element is
represented by the soft set of cells t,Y  contained in the corresponding sphere Vj . The
sphere is broken down in turn into yi -elements of the set t, ,Y  , each of which
contains the cells belonging to a certain category yi Y . The dynamic bi-soft
topology that defines configuration space C can be represented as TS  mj0 ik0T jiS  . In
the case of the fuzzy soft set of cells  t,Y be a carrier set for the second level of
topology, we have got the dynamic fuzzy bi-soft set of cells  t,Y ,  and the
corresponding topology.
9</p>
    </sec>
    <sec id="sec-9">
      <title>Implementation of the model</title>
      <p>The proposed model has been implemented in the reactive path planning module
within UV onboard control system prototype based on embedded microcontroller
STM32F429 (180 MHz Cortex M4, 2Mb Flash/256Kb RAM internal, QSPI Flash
N25Q512). Information about the navigational situation comes from onboard sensors
while information about team members and their targets is received from the radio
communication channel.</p>
      <p>Using the proposed model, a reactive planner transforms coordinates of all
observed objects into the angular coordinate system within the configuration space. Then
it creates an open sphere for each observed vehicle and discretizes it separately. Using
the safety domains constructed for each observed vehicle, the planner creates the open
sphere bi-soft topology. Since the environment can change, each observed event
updates the partitioning of the configuration space to distinguish “free to move”
subspace, in which the planner search for the next fragments of the path if a potential
collision has been detected or the spatial configuration of the UV ensemble has violated.</p>
      <p>The planner superposes open sphere topologies for each vehicle and eliminates all
insignificant subsets of the cell. The set of target cells having the state equal to y2 is
considered as attractive manifold while the set of “occupied” cells having the state
equal to y1 , y3 , or y4 is considered as repulsive manifold (Fig. 6).</p>
      <p>Then the search for a path fragment to the next waypoint is provided using the
potential fields-based algorithm, which builds a path choosing the cells of the
constructed bi-soft topology that have the highest degree of safety motion.
Finally, the path fragments will be transformed back to the cartesian coordinate
system. The search algorithm is driven by the heuristic based on the fact that the greater
the volume of the cells the farther the cell from the center of the sphere. It allows
reducing the computational complexity essentially.</p>
      <p>The efficiency of the proposed model has been examined compared to using the
ordinary cartesian spatial model during the computer simulation based on the UV
onboard control system and GIS-based model of the real terrain having the square 4
km2. During the simulation, the number of vehicles has been varied from 10 to 100.
The total time of the path search has been evaluated, the results are shown in Fig. 7.
The results of the experiment show that the proposed bi-soft topological model
provides acceptable performance in terms of the path search time, its efficiency is about
45 percent higher than the efficiency of the ordinary model.
10</p>
    </sec>
    <sec id="sec-10">
      <title>Conclusions</title>
      <p>The problem of modeling of configuration space for the reactive joint motion
planning of unmanned vehicles’ ensemble is addressed in the paper.</p>
      <p>The proposed model is based on a novel dynamic bi-soft topology, which allows
describing the safety conditions of the joint motion of a multitude of vehicles. The
two-leveled approximation space of this topology is constructed within the system of
nested open spheres based on an angular coordinate system. The spheres are sampled
into sector-like cells. The first level of the soft topology breaks down the
configuration space onto “free to move” and obstacle subspaces represented by soft sets of cells
taking into account uncertainties of observations. The second level of the soft
topology breaks down the determined soft subspaces into safety zones also represented as
soft sets. As a result, the bi-soft (fuzzy) set of cells is defined and corresponding
dynamic (fuzzy) bi-soft topology is constructed.</p>
      <p>
        The proposed topological model can be used in a hybrid motion planner
combining potential field and RRT methods. The use of the proposed bi-soft topology allows
reducing the computational complexity of the motion planning task using
sophisticated partitioning of the configuration space as well as path search heuristics based on
the calculation of the cell volume. The computer simulation has shown that the
proposed model provides enough performance, its efficiency is about 45 percent higher
than the efficiency of the ordinary cartesian model.
6. Gonzalez-Banos, H., Hsu, D., Latombe, J.C.: Motion planning: Recent developments. In:
Autonomous Mobile Robots: Sensing, Control, Decision-Making and Applications. CRC
Press (2006). DOI: 10.1201/9781315221229-13
7. Short, A., Pan, Z., Larkin, N., van Duin, S.: Recent progress on sampling based dynamic
motion planning algorithms. In: Proc. of 2016 IEEE International Conference on
Advanced Intelligent Mechatronics (AIM), pp. 1305–1311, USA (2016). DOI:
10.1109/AIM.2016.7576950
8. González, D., Pérez, J., Milanés, V., Nashashibi, F.: A Review of Motion Planning
Techniques for Automated Vehicles. IEEE Transactions on Intelligent Transportation Systems
17(
        <xref ref-type="bibr" rid="ref4">4</xref>
        ):1135–1145 (2016). DOI: 10.1109/TITS.2015.2498841
9. Mujumdar, A., Padhi, R.: Reactive Collision Avoidance Using Nonlinear Geometric and
Differential Geometric Guidance. Journal of Guidance, Control, and Dynamics 34(
        <xref ref-type="bibr" rid="ref1">1</xref>
        ):303–
310 (2011). DOI: 10.2514/1.50923
10. Chakravarthy, A., Ghose, D.: Obstacle avoidance in a dynamic environment: a collision
cone approach. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems
and Humans 28(
        <xref ref-type="bibr" rid="ref5">5</xref>
        ):562–574 (1998). DOI: 10.1109/3468.709600
11. Pietrzykowski, Z., Uriasz, J.: The Ship Domain – A Criterion of Navigational Safety
Assessment in an Open Sea Area. Journal of Navigation 62:93–108 (2009). DOI:
10.1017/S0373463308005018
12. Song, L., Chen, Z., Dong, Z., Xiang, Z., Mao, Y., Su, Y., Hu, K. Collision avoidance
planning for unmanned surface vehicle based on eccentric expansion. International Journal of
Advanced Robotic Systems. 16(
        <xref ref-type="bibr" rid="ref3">3</xref>
        ):1–9 (2019). DOI: 10.1177/1729881419851945
13. Zhang, M.: Formation flight and collision avoidance for multiple UAVs based on modified
tentacle algorithm in unstructured environments. PLoS ONE 12(8): e0182006 (2017).
      </p>
      <p>DOI: 10.1371/journal.pone.0182006
14. Molodtsov, D.: Soft Set Theory – first results. Computers and Mathematics with
Applications 37:19–31 (1999). DOI: 10.1016/S0898-1221(99)00056-5
15. Maji, P. K., Roy, A. R., Iswas, R. B.: An application of soft sets in a decision-making
problem. Computers and Mathematics with Applications 44(8-9):1077–1083 (2002). DOI:
10.1016/S0898-1221(02)00216-X
16. Allam, A.A., Bakeir, M.Y., Abo-Tabl, E.A.: Some Methods for Generating Topologies by</p>
      <p>
        Relations. Bull. Malays. Math. Sci. Soc. Series (
        <xref ref-type="bibr" rid="ref2">2</xref>
        ) 311(
        <xref ref-type="bibr" rid="ref1">1</xref>
        ), 35–45 (2008).
17. Feng, F., Li, Y., Leoreanu-Fotea, V.: Application of level soft sets in decision making
based on interval-valued fuzzy soft sets. Computers and Mathematics with Applications
60:1756–1767 (2010). DOI: 10.1016/j.camwa.2010.07.006
18. Varol, B.P., Aygun, H.: Fuzzy soft topology. Hacettepe Journal of Mathematics and
Statistics 41(
        <xref ref-type="bibr" rid="ref3">3</xref>
        ):407–419 (2012).
19. Wang, L., Qin, K.: Incomplete Fuzzy Soft Sets and Their Application to Decision-Making.
      </p>
      <p>
        Symmetry 11:535 (2019). DOI: 10.3390/sym11040535
20. Mahanta, J., Das, P.K.: Fuzzy soft topological spaces. Journal of Intelligent &amp; Fuzzy
Systems 32(
        <xref ref-type="bibr" rid="ref1">1</xref>
        ):443–450 (2017). DOI: 10.3233/JIFS-152165
21. Zharikova, M., Sherstjuk, V.: Case-based Approach to Intelligent Safety Domains
Assessment for Joint Motion of Vehicles Ensembles. In: Proc. of the 4th International
Conference on Methods and Systems of Navigation and Motion Control, p. 245–250, Kyiv
(2016). DOI: 10.1109/MSNMC.2016.7783153
      </p>
    </sec>
  </body>
  <back>
    <ref-list>
      <ref id="ref1">
        <mixed-citation>
          1.
          <string-name>
            <surname>Sherstjuk</surname>
            ,
            <given-names>V.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Zharikova</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Sokol</surname>
            ,
            <given-names>I.</given-names>
          </string-name>
          :
          <article-title>Forest Fire-Fighting Monitoring System Based on UAV team and Remote Sensing</article-title>
          .
          <source>In: Proc. of 2018 IEEE 38th International Conference on Electronics and Nanotechnology</source>
          , pp.
          <fpage>663</fpage>
          -
          <lpage>668</lpage>
          ,
          <string-name>
            <surname>Kyiv</surname>
          </string-name>
          (
          <year>2018</year>
          ). DOI:
          <volume>10</volume>
          .1109/ELNANO.
          <year>2018</year>
          .8477527
        </mixed-citation>
      </ref>
      <ref id="ref2">
        <mixed-citation>
          2.
          <string-name>
            <surname>Sherstjuk</surname>
          </string-name>
          , V.:
          <article-title>Scenario-Case Coordinated Control of Heterogeneous Ensembles of Unmanned Aerial Vehicles</article-title>
          .
          <source>In: Proc. of 2015 IEEE 3rd Int. Conf. on Actual Problems of Unmanned Aerial Vehicles Developments (APUAVD</source>
          <year>2015</year>
          ), pp.
          <fpage>275</fpage>
          -
          <lpage>279</lpage>
          ,
          <string-name>
            <surname>Kyiv</surname>
          </string-name>
          (
          <year>2015</year>
          ). DOI:
          <volume>10</volume>
          .1109/APUAVD.
          <year>2015</year>
          .7346620
        </mixed-citation>
      </ref>
      <ref id="ref3">
        <mixed-citation>
          3.
          <string-name>
            <surname>Skowron</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Chmielowiec</surname>
            ,
            <given-names>W.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Glowacka</surname>
            ,
            <given-names>K.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Krupa</surname>
            ,
            <given-names>M.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Srebro</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          :
          <article-title>Sense and avoid for small unmanned aircraft systems: Research on methods and best practices</article-title>
          .
          <source>Proceedings of the Institution of Mechanical Engineers. Part G: Journal of Aerospace Engineering</source>
          <volume>233</volume>
          (
          <issue>16</issue>
          ):
          <fpage>6044</fpage>
          -
          <lpage>6062</lpage>
          (
          <year>2019</year>
          ).
          <source>DOI: 10.1177/0954410019867802</source>
        </mixed-citation>
      </ref>
      <ref id="ref4">
        <mixed-citation>
          4.
          <string-name>
            <surname>Abbasi</surname>
            ,
            <given-names>Y.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Moosavian</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Novinzadeh</surname>
            ,
            <given-names>A.</given-names>
          </string-name>
          :
          <article-title>Formation control of aerial robots using virtual structure and new fuzzy-based self-tuning synchronization</article-title>
          .
          <source>Transactions of the Institute of Measurement and Control</source>
          <volume>39</volume>
          (
          <issue>12</issue>
          ):
          <fpage>1</fpage>
          -
          <lpage>14</lpage>
          (
          <year>2017</year>
          ).
          <source>DOI: 10.1177/0142331216649021</source>
        </mixed-citation>
      </ref>
      <ref id="ref5">
        <mixed-citation>
          5.
          <string-name>
            <surname>Kang</surname>
            ,
            <given-names>S.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Choi</surname>
            ,
            <given-names>H.</given-names>
          </string-name>
          ,
          <string-name>
            <surname>Kim</surname>
            ,
            <given-names>Y.</given-names>
          </string-name>
          :
          <article-title>Formation flight and collision avoidance for multiple UAVs Using concept of elastic weighting factor</article-title>
          .
          <source>International Journal of Aeronautical and Space Sciences</source>
          <volume>14</volume>
          :
          <fpage>75</fpage>
          -
          <lpage>84</lpage>
          (
          <year>2013</year>
          ). DOI:
          <volume>10</volume>
          .5139/IJASS.
          <year>2013</year>
          .
          <volume>14</volume>
          .1.
          <fpage>75</fpage>
        </mixed-citation>
      </ref>
    </ref-list>
  </back>
</article>