This work presents a model of soft multi-level safety domains and rough motion corridors within path search configuration spaces during reactive planning of the joint motion of a multitude of unmanned vehicles. The model of the multilevel soft safety domains is based on the spherical topology that allows defining non-spherical safety domains by measuring various radiuses within sectors located in different longitude and latitude. The nonlinearity of the proposed spherical topology allows the use of various heuristics to overcome oversampling and wide distribution of the random points specific to the rapidly exploring random tree-based methods and improve the efficiency of the search for suitable paths within the configuration space. The algorithm of the computation of rough motion corridors based on the soft rough topology is proposed. The motion corridor can be determined through a superposition of multi-level collision cone systems imposed onto the soft topological space. The proposed model allows describing rough motion corridors within configuration space narrowed by soft safety domains of any levels, sizes, and shapes as well as improving the planner performance.
Unmanned vehicles, which were considered as the result of significant technological progress until recently, have now become commonplace. Today, they are used in all possible areas of human activity to solve complex problems, where human involvement is undesirable. Certainly, in the fields where they have not been being used, researchers are already working closely on this issue. Furthermore, groups of unmanned vehicles operating simultaneously in several environments have begun to be applied. A smart fishery task is a good example of such operation involving a multitude of aerial, surface, and underwater vehicles, where unmanned aerial vehicles perform search missions looking for fishing flocks, unmanned underwater vehicles perform different missions aimed at identifying fish in flocks and driving them in fishing gears, as well as unmanned boats can carry fishing gear and hook fish.
To achieve good results of a smart fishery operation, all involved unmanned vehicles (UV) must cooperatively perform their missions synchronizing their movements and actions in time and space. Accordingly, each of UAVs must have its mission plan that prescribes procedures for moving and performing the necessary actions taking into account safety and efficiency considerations. accordingly, each UV gets its planned path represented by a sequence of waypoints (WP) within a four-dimensional space of joint motion where three dimensions are spatial, and one dimension is time. Such waypoints are often connected to specific time points in order to simplify the coordination of joint movement. During path planning, some possibly conflicting criteria must be taken into account such as fuel availability, filling of the hold volume, time, etc.
Since UVs usually operate in respectively large, uncertain, and dynamic environments, there is a range of essential constraints imposed on their movement. Some of them are related to static and dynamic obstacles, vehicle dynamics restrictions (velocity, acceleration, rudder angle), environmental forces (winds, currents, waves), and technical limitations (communication range, length of gear). However, there are also situational disturbances such as moving objects and restrictions caused by regulations (rules at sea, air) within the open (civil) space for operations.
Surely, dynamic environmental impacts most often affect predetermined paths forcing UVs to change their motion trajectories and ever vary the execution of the whole operation. Such changes can occur not only due to the changes in motion conditions but also due to the depletion of some fish schools or the discovery of new fish schools. The correspondent change of the motion trajectories of some vehicles entails the changes in the trajectories of other vehicles mainly due to safety reasons.
Thus, there are two planning problems: the first one is preliminary and can be
considered as global planning problem aimed at planning the paths for each UV within a
global space of joint motion, and the second one is local and aimed to real-time
replanning of the paths of the vehicles during the mission execution including obstacles
avoiding and mitigating posed uncertainty and risk. The authors are concerned with
the large heterogeneous teams of UVs [
Usually, researchers consider path planning at two main levels: global planning and
local planning [
There are several modern approaches proposed in the recent literature [5] including Voronoi diagrams, artificial potential fields, fast marching (FM)-based, evolutionary methods, etc. The sampling-based approaches such as probabilistic roadmaps (PRM) or rapidly exploring random trees (RRT) are applicable in conditions of well-known static environments and static obstacles and, therefore, are mainly used in the field of UVs. Among them, RRT algorithms are more popular since PRM algorithms do not guarantee the shortest paths [6].
RRT algorithms are based on the idea of growing a tree in an obstacle-free region from a start location to a target location [7]. In RRT, feasible trajectories can be constructed by expanding trees growing, which starts from the initial point, going through a set of random points called seeds, and finishes when the target point is achieved. The advantage of the RRT algorithm is that it can be used to plan a path in a complex environment without building a spatial model [8]. At the same time, the RRT-based path-planning method has also some drawbacks such as high randomness, oversampling, slow rate of calculation, etc. Thus, the paths generated by the RRT planner are not optimal due to such drawbacks [9]. Therefore, some improved methods have been also proposed by researchers, but the key issues leading to the poor performance of RRT planners remain unexplored.
To overcome such drawbacks as oversampling and wide distribution of the random points, which reduces the path search performance, we develop a model of configuration spaces based on rough motion corridors narrowed by soft safety domains. We investigate the use of non-trivial spherical topologies to reduce the computational complexity by abandoning iterative calculations. This work aims to develop the method of determination of soft multi-level safety domains and building correspondent motion corridors within configuration space during reactive joint motion planning of a multitude of unmanned vehicles. This method is aimed at RRT-based reactive path-planning. 3 3.1
Suppose C is a three-dimensional space. Assume that a group of vehicles performs a certain operation together within space C . Suppose a path is a pre-planned sequence of pairs (waypoint-timepoint) (WP/TP). Such a path must start at some initial point and lead to some target point; both start and target points should be given within space C . Consider the simplest situation presented in Fig. 1. Here, the active object A1 moves along the pre-planned path P to the given goal g represented in Fig. 1 by a dashed line. We consider A1 as a “host vehicle”. Being at the point x1 , it detects the obstacle V1 at the distance d1 in the forward direction. The vehicle control system must start a collision avoidance maneuver at the point x2 being at the distance d2 from the obstacle V . Thus, a straightforward fragment of the 1 initial path P starting at the point x2 and up to the point x3 should be replaced by a curvilinear fragment represented in Fig. 1 by a dash-dotted line. As a result, the new re-planned path P′ will be obtained by adding the extra waypoint x3 laying at the minimal safe distance dmin from the obstacle V . 1
Furthermore, at the point x3 the host vehicle A1 has two alternatives to achieve the target point g : either it will continue to move along the curvilinear path P′ and return to the original path P at the point x4 , or it will add a new rectilinear fragment from the point x3 immediately to the target point g . Despite the simplicity of the considered situation, the solution is not easy because of the high uncertainty: it is not known what other static or dynamic obstacles the vehicle A1 can detect within the space from x3 to x4 before it gets into the close neighborhood of the point x3 .
Let us consider a more complex situation when the host vehicle A1 detects a moving object A2 considered as an “intruder” that violates the pre-planned path P . Certainly, A2 is a dynamic obstacle to avoid. The situation represented in Fig.2 is quite similar to the previous one represented in Fig. 1, so a potential collision can be resolved in a similar way. However, the object A2 is moving. Both the vehicle A1 and the intruder A2 can equiprobably approach or move away from each other. Moreover, their joint movement cannot affect them. There is the following way to find out if there is a danger of a potential collision: we should calculate a relative velocity of both movement participants concerning the bearing from A1 to A2 defined as υ R (t ) = υ A1 (t ) −υ A2 (t ) ⊥ B ( A1, A2 ) , where υ R (t ) is a projection of relative velocity between A1 and A2 on the bearing B ( A1, A2 ) from A1 to A2 at the time t as well as υ A1 (t ) and υ A2 (t ) are velocity vectors of A1 and A2 at the time t respectively. Thus, if υ R (t ) ≤ 0 , the vehicle A1 and the intruder A2 are moving away from each other, but if υ R (t ) > 0 , they are moving closer to each other. Therefore, a potential collision should be detected, and a correspondent collision avoidance maneuver should be activated. In the condition of the joint motion of many vehicles, the calculation of the relative velocities’ vectors can be time-consuming, therefore, the relative bearings are often evaluated before that as shown in Fig. 3. The relative bearings between vehicle A1 and intruder A2 should be evaluated with some periodicity in time (time moments t1 , ...tn ). If the relative bearing to the object does not remain constant over time, i.e. if BA1A2 (t j−2 ) ≠ BA1A2 (t j−1 ) ≠ BA1A2 (t j ) during at least three successive time moments t j−2 , t j−1, t j , there is no potential collision. And vice versa, if BA1A2 (t j−2 ) =BA1A2 (t j−1 )
=BA1A2 (t j ) , there is a potential collision, therefore, it is a reason to evaluate the distance between A1 and A2 : if it is decreasing in time, the possible collision is detected. The relative velocity vector can be evaluated instead of the distance between A1 and A2 to clarify the possibility of their collision.
The collision conditions can be described by a collision cone constructed by dropping tangents l1,l2 from A1 to a certain sphere Bi representing the safety zone around Ai as it is shown in Fig. 4. If the velocity vector υ1 lies within the collision cone, A1 violates Bi . Decomposition of υ1 in terms of the tangents l1,l2 gives us υ1 =al1 + bl2 . If a > 0 and b > 0 , then the obstacle Ai is critical to A1 . To avoid a collision, it is necessary to perform such a maneuver that the velocity vector υ1 should leave the collision cone. The most common approaches to evaluate safety conditions of the joint motion are based on the definition of the safety domains or the definition of the closest point of approach (CPA) and corresponding linear (distance DCPA ) and temporal (time TCPA ) estimations to CPA. Within the latter approach, safety assessment is based on the subsequent comparison of DCPA and/or TCPA with the given threshold values DZ and TZ . In the case of the joint movement of a significant number of vehicles, this problem is combinatorial and, accordingly, computationally hard. Instead of this, the definition of the safety domain [10] breaks down the circumjacent area into safe and dangerous areas (domains). In this case, the host vehicle must eliminate the ingress of any other objects into its safety domain or avoid violating the safety domains of other vehicles. Thus, any intrusion into the safety domain is qualified as a threat. Although many studies are offering different shapes of safety domains (circle, ellipse, hexagon, etc.) and methods for determining their sizes, the shape and size of the safety domain depend on a range of factors of stochastic nature hampering a clear determination of its margins [11].
The biggest problem is related to the uncertainty of the approaching conditions. Obviously, without knowing the intentions of A2 (Fig. 2), we cannot be sure that its speed and direction will not change during the approach. The accuracy of our understanding of the size, motion speed, and direction of the object A2 is limited in general by the accuracy of the A1 ’s onboard equipment and its susceptibility to interferences; in any case, it is not absolute. Thus, we have inaccuracy, uncertainty, and unpredictability of the situation.
To overcome uncertainty, it is advisable to use multilevel domains, as shown in Fig. 5. Since the safety domains of spherical shape are most often used in threedimensional spaces, we consider them spherical. Given the uncertainty of the intruder’s shape and size as well as the complexity of taking them into account, it is customary to represent the intruder’s shape as inscribed geometrically in a certain sphere having a radius r0 (Fig. 5). Of course, this is a very strong assumption, therefore, it is necessary to provide the opportunity for safety domains to take any geometric shape. However, it is quite difficult to do this using existing approaches.
We can define safety conditions by a system of concentrically nested spheres, radiuses of which uniquely determine margins of the corresponding levels of the safety domain: 1. The radius r0 describes the margins of the forbidden domain ω0 , violation of which leads to an unconditional collision; 2. The radius r1 describes the margins of the critical domain ω1 when a collision can be avoided only by resorting to emergency braking and abrupt evasion; 3. The radius r2 describes the margins of the dangerous domain ω2 . To avoid a collision, there is a need to change the speed or direction urgently; 4. The radius r3 describes the margins of the unsafe domain ω3 . The motion is restricted by an intruder, and there is also a need to change the speed or direction in order to avoid a collision but not so urgent like within dangerous domain; 5. The radius r4 describes the margins of the almost safe domain ω4 . There is no need to change the motion parameters but given the uncertainty, special attention is required to the intruders falling into this domain – they can change its motion parameters, which could lead to danger.
The space ω5 outside the domain ω4 is safe and free to move. Certainly, in each case domains can be broken down into more or fewer levels taking various shapes. This is especially important for marine applications where elongated geometric shapes of vehicles prevail that differ significantly from round and spherical shapes considered above. Therefore, it is advisable to develop a model that describes safety domains of any levels, sizes, and shapes. We use topologies to do this. 3.3
Let Y be a set of a certain nature and T be a set of time points. Assume that a strict order <T is imposed over the time points within T and t0 is an initial time moment.
Suppose C is a three-dimensional Euclidean space discretized by a uniform metric grid D of coordinate lines. Thus, D is a three-dimensional array of isometric cubic cells {dxyz } , where x, y, z are dimensional indexes.
Let D be a non-empty set of cells, let R ≥0 be a set of non-negative real numbers, and let ξ D be a function D × D → R≥0 . If ξ D satisfies the following conditions for each d1, d2 , d3 ∈ D : 1. ξ D ( d1, d1 ) = 0 if and only if d1 = d2 ; 2. ξ D ( d1, d2 ) = ξ D ( d2 , d1 ) ; 3. ξ D ( d1, d2 ) + ξ D ( d2 , d3 ) ≥ ξ D ( d1, d3 ) , ξ D is a suitable distance function (metric), ξ D ( d1, d2 ) =d1 − d2 gives us a distance from the certain cell d1 to the cell d2 within D , and the couple ( D,ξ D ) is a metric space.
Each cell can be considered as a homogeneous volumetric figure. Let us define a reflexive, symmetric, and transitive (equivalence) relation ℜD ⊆ D × D on the set of all cells within D , namely an indiscernibility relation. In terms of safety/danger value ω ∈ Ω and with respect to the ℜD , ℜD (d1, d2 ) means that (∀d1, d2 ∈ D)(∀ω ∈ Ω) ω (d1 ) =ω(d2 ) , so the cells d1 and d2 are ω -indiscernible.
The pair aprD =( D,ℜD ) can be considered an approximation space, so the factor set consisting of all equivalence classes of D with respect to ℜD is denoted by D / ℜD [12]. We can also consider elementary sets such as the empty set ∅ , the universal set D , and the elements of the corresponding factor set D / ℜD , as well as a composite set represented by a finite union of one or more elementary sets. Thus, we can define a family of all composite sets denoted by Def ( aprD ) , as well as the equivalence class denoted by ℜD ( d ) , which contains a certain cell d ∈ D .
The approximation space aprD =( D,ℜD ) uniquely determines the topological space T = ( D, Def ( aprD )) . Obviously, Def ( aprD ) is a topology on D if and only if all its subsets satisfy the following conditions [13]: 1. ∅ ∈ Def (aprD ), D ∈ Def (aprD ) ; 2. A, B ∈ Def (aprD ) ⇒ A ∩ B ∈ Def (aprD ) ; 3. A, B ∈ Def (aprD ) ⇒ A ∪ B ∈ Def (aprD ) .
In this case, Def ( aprD ) is a family of open sets, T = ( D, Def ( aprD )) is the topological space, and d ∈ D are the elements of this topological space.
Each object within D can occupy one cell or a certain plurality of contiguous cells. Therefore, the motion of any objects including vehicles can be represented as the change of its indexes within the space D over time T . The object position within D is described by a triplet of spatial indices ( x, y, z ) , and a function Pos ( Ai ) returns the indices of the cell corresponding to the spatial position of the geometric center of the object Ai in the form of the triplet.
Suppose a cell is a certain kind of voxels – the elements of the space that define the value of a certain type within a uniform spatial lattice. Although in the visualization field the value of the voxel traditionally represents color, in our case the value of the cell will represent a safety/danger degree of the corresponding spatial area. Since the safety/danger degree of the cell can change over time, the voxels can be represented dynamically as doxels (=dynamic voxels), which values depend on time. 3.4
Safety domains are mainly spherical and must be constructed starting at the current location of the intruder. To build a safety domain for the vehicle Ai , we need to define an angular coordinate system that originated in the current position of this vehicle. This allows to represent coordinates by triplets (β1,β 2 ,l ) , where β1 is latitude, β 2 is longitude, and l is a distance from the sphere origin, instead of cartesian coordinates ( x, y, z ) . Certainly, the center of this sphere should be aligned with the center of the sphere of radius r0 circumscribing geometrically the object Ai .
Let us build an infinite sphere V that originated at the cell di ∈ D such that Pos ( Ai ) = di . Let us discretize the sphere V using an angular grid of coordinate lines with equal angles and equal discrete of the radius. Thus, the sphere V is divided into m angular discrete elements both in the meridian and the parallels planes such that ∆β1 =∆β 2 =360 / n (Fig. 6). Its radius is also breaking down into uniform discrete ∆l starting at the origin of the sphere and directed outside. As a result, we obtain a sphere
with the sectoral cells w (Fig. 6) discretized by the cells wijk being the smallest sectors of the sphere V with the angular coordinates i, j, k The cells wijk are homogeneous objects with respect to their interior.
Based on the discretized sphere W , we can define two different metrics. The first one is a linear distance metric ξV with properties similar to ξ D . To define this metric, we should use an isometric bijection χ :ξ D → ξV . Obviously, using bijection χ we can also transform the rectangular coordinates of any objects within the grid D to the angular coordinates within the spherical grid W , and vice versa.
The second metric ξW is based on the volumetric properties of the sectors. Since the volume of each next sector located farther from the center of the sphere is necessarily larger than the volume of the previous sector, this metric ξW is non-linear. The closer to the center of the sphere the sector is the smaller its volume is, and vice versa. This metric ξW allows us to define an indiscernibility relation ℜW ⊆ W ×W (reflexive, symmetric, and transitive) over the set of all sectors within W based on their volume estimations. Using the relation ℜW , we can define the correspondent approximation space aprW =(W ,ℜW ) that determines uniquely the topological space TW = (W , Def ( aprW )) , where Def (aprW ) is a spherical topology on W . Since the metric ξW is nonlinear, the resulting topological space TW is also non-linear. The nonlinearity of the topology TW
allows using the various heuristics to overcome oversampling specific to the RRT method and improve the efficiency of the search for the suitable paths within the configuration space.
Building such a spherical topology makes it possible to build non-spherical safety domains by measuring various radiuses within sectors located in different longitude and latitude. An example of a two-dimensional projection of a non-spherical safety domain is shown in Fig. 7. An important feature of the safety domain is that its shape and dimensions depend on time. Usually, their values are relevant only at the evaluation time. The joint motion process is essentially dynamic, therefore, possible changes of the motion parameters of both the host vehicle and the intruder (and even other vehicles), as well as changes of environmental parameters including weather conditions, can cause changes in the shape and dimensions of the safety domains. Besides, the safety domains are asymmetric, so the fact that the host vehicle A1 violates the critical domain of the intruder vehicle Ai does not entail the converse statement, because the vehicle Ai can safely interact with A1 due to differences in their dimensions and velocities.
Consider safety assessments are dynamic. Let ri (t ) = {r0 (t ),...rl (t )} be a set of domain-dependent margins evaluated for a certain vehicle Ai at the time t based on the above-considered metric ξ D . Suppose a function Pos ( Ai ,t ) returns the position of the vehicle ui at the time t . Thus, for each couple ( Ai , Ak ) of vehicles, we can evaluate a certain distance Pos ( Ai ,t ) − Pos ( Ak ,t ) ξ
→ ri (t ) .
D
Let ϕi (t ) = {ϕ0 (t ),...ϕ q (t )} be a set of time-dependent limits and ξT be a metric defined on T such 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 ) .
Using time-dependent limits, we can determine the margins of the safety domain. For example, the domain-dependent margin r1 (t ) of the critical safety domain ω1 can be evaluated based on the distance needed for emergency braking, while the corresponding time-depending limit ϕ1 (t ) is the time required for emergency braking at the current vehicle speed υ1 (t ) . The margins r2 (t ),...r4 (t ) can be determined in the same way based on the assumptions of the use of certain control actions to avoid a collision. The margin r0 (t ) can be estimated based on the intruder’s dimensions and practically does not depend on time, except the situations where the values of such dimensions can be refined during the observation.
It allows us to build a vague safety domain represented by a system of concentric safety domain levels around each vehicle Ai involved in motion interactions. Such levels can be represented as collision cones based on evaluated domain- and timedependent safety margins as shown by colors in Fig. 8. Since domain levels can take non-spherical shapes, such figures can take shapes differing from the cone. Let r be a partial order that arranges margins r0 (t ),...rm (t ) with respect to a certain scale Ω ={ω1,...ωm} such that r0 (t ) r ... r rm (t ) , The number m of scale elements sets safety levels; for example, m = 4 in Fig. 8. This value should be a compromise between the accuracy of safety estimation and its computational complexity.
The 6-levels scale corresponding to Fig. 8 is shown in Table 1. Clearly, all sectors of topology TW concentrated inside the certain collision cone according to the safety domain ωi take danger grade yi corresponding to Table 1. ly of subsets of the set of sectors W parameterized by the set Y . Each value of the parameter yi ∈Y defines a set of yi -approximated elements of the soft set ( yi elements of the soft set [15]), denoted by ϒi .
Using the soft set ( ϒ,Y ) , we can break down the universe W into the set of yi elements, so that ϒ = ∪{ϒi }ik=1 . Let us define a dynamic yi -indiscernibility relation on the set of cells W as (∀yi ∈Y ) ℜWyi (t ) ={(wm , wn ) ∈W ×W yi ( wm ,t ) =yi ( wn ,t )} . The defined relation ℜWyi (t ) allows considering each yi -element of the soft set ϒi as the corresponding equivalence class at the moment t . Consequently, the parameterized family of subsets of the set W , which constitutes the certain yi -element of the set ϒi , can be considered as a factor-set W / ℜWyi (t ) that consists of all equivalence classes of W induced by the relation ℜWyi (t ) . Thus, a pair aprW =(W ,ℜWyi (t )) defines the dynamic approximation space. Accordingly, we can define a family of all compound sets Def (aprW ) and a dynamic soft topological space TWℜWyi (t ) = (W , Def ( aprW )) that uniquely corresponding to the dynamic approximation space [16].
The y0 -element of the soft set contains all sectors, which have the safety grade y = 0 , and describes the space forbidden to other vehicles at the moment t . The y1 element must be also considered as prohibited for safety reasons. The y4 -element of the soft set, on the contrary, contains all sectors, which have the safety grade y = 1 , and describes the space that is “free to move” at the moment t . Undoubtedly, the y4 element of the soft set relates to the “free to move” subspace of configuration space, while y0 - and y1 -elements relate to the obstacle subspace of configuration space. Since y2 - and y3 -elements constitute an uncertain space, we can further consider configuration space as a rough concept.
Now we need to develop a method for determining a soft corridor to find suitable paths within the configuration space. We will proceed from the fact that the host vehicle is surrounded by some other vehicles that interact during their movement. Thus, safety domains should be defined for all vehicles that interact or can interact with the host vehicle (Fig. 9). The topological space TW , which origin is located in Pos ( A1,t ) , is the basis for building the motion corridor. In Fig. 9, there are three vehicles ( A2 , A3 , and A4 ) around the host vehicle A1 . Thus, we should determine the safety domains for each of A , A3 , 2 and A4 , and build corresponding collision cones as it is shown in different colors in Fig. 9. It should be noted that in Fig. 9, these cones are shown in a simplified manner, without respect to the safety levels. The development of the motion corridor requires multilevel safety domains and corresponding collision cones.
Obviously, collision cones can be represented as sets of sectors within the discretized sphere W having certain grades of danger. Since all collision cones are superimposed on the topology TW , their danger grades should be summed up. Thus, ϑw (t ) = ⊕ mj=1 ( yij (t )) . Suppose each element of the topological space T has an initial danger value function ϑd = 1 . To compute the safety grade of the certain element of the topologic space T , we need to subtract summary danger grade from the initial safety value such that ϑd (t ) = 1 −ϑw (t ) . As a result, we obtain a certain dispersion of safety levels over the configuration space. Choosing the required subspace corresponding to an y4 -element of the soft set, we obtain the required motion corridor as shown in Fig. 9 in yellow color.
This corridor can be represented as a soft rough set based on the assumptions that aprDϑd = ( D, RϑDd ) is a Pawlak approximation space [17]. Thus, its lower approximation can be defined as the soft set ϒD (ϑd ,t ) = {∀ϑd ∈ Ω( RϑDd (d ) ⊆ ϒD (ϑd ,t ) d ∈ D)} while the upper approximation is ϒD (ϑd ,t ) ={∀ϑd ( RϑDd (d ) ∩ ϒD (ϑd ,t ) ≠ ∅ d ∈ D)} , where the indiscernibility relation
RωDi is defined on the set of cells
D as RϑDd ={(dm , dn ) ∈ D × D f (dm ,ϑd ) =f(dn ,ϑd )} . 4
The proposed model has been implemented in the reactive path planning module within UV onboard control system prototype Breeze [18] based on embedded microcontroller STM32F429 (180 MHz Cortex M4, 2Mb Flash/256Kb RAM internal, QSPI Flash N25Q512). It has been implemented using the C++ programming language and SoFTo library. The latter offers a set of operations for building cartesian and spherical topologies, their addition and subtraction, determining their unions, intersections, closures, and interiors. The reactive path planner transforms coordinates of all observed objects into the angular coordinate system within the configuration space and defines the spherical topology. Then it determines the safety domains for each object and constructs the system of collision cones based on the computed grades of danger. Finally, it superimposes all collision cones into the spherical topology to outdraw the motion corridors. Thus, the configuration space is narrowed by soft safety domains, so the planner can use only the motion corridors within configuration space to search for random points. 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. The 6-level scale based soft-rough dynamic topological space has been used during the simulation, as well as the number of vehicles has been varied from 10 to 100. The total time of the path search has been evaluated and the results are shown in Fig. 10. The results of the experiment show that the proposed model provides acceptable performance in terms of the path search time, its efficiency is about 45 percent higher than the efficiency of the ordinary cartesian-based model in situations when the number of jointly moving objects is more than 40. 5
The problem of improving the efficiency of the RRT path planner for the reactive joint motion planning of unmanned vehicles is addressed in the paper. The authors propose the concepts of multi-level soft safety domains and rough motion corridors, which can reduce the configuration space when the planner searches for random points (also known as seeds). The paper presents the model of soft multi-level safety domains and corresponding motion corridors within configuration space during reactive planning of the joint motion of a multitude of unmanned vehicles. The model of the multi-level soft safety domains is based on the spherical topology that allows defining non-spherical safety domains by measuring various radiuses within sectors located in different longitude and latitude. The nonlinearity of the proposed spherical topology allows the use of various heuristics to overcome the oversampling and wide distribution of the random points specific to the RRT method and improve the efficiency of the search for suitable paths within the configuration space. The algorithm of the computation of rough motion corridors based on the soft rough topology is proposed that allow determining motion corridors within the configuration space through a superposition of multi-level collision cone systems imposed onto the soft topological space. The proposed model allows describing rough motion corridors within configuration space narrowed by soft safety domains of any levels, sizes, and shapes. It also provides the performance enough to reactive motion planning. 3. Abbasi, Y., Moosavian, S., Novinzadeh, A.: Formation control of aerial robots using virtual structure and new fuzzy-based self-tuning synchronization. Transactions of the Institute of Measurement and Control 39(12):1–14 (2017). DOI: 10.1177/0142331216649021 4. Kang, S., Choi, H., Kim, Y.: Formation flight and collision avoidance for multiple UAVs using concept of elastic weighting factor. International Journal of Aeronautical and Space Sciences 14:75–84 (2013). DOI: 10.5139/IJASS.2013.14.1.75 5. Patle, B.K., Babu L, G., Pandey, A., Parhi, D.R.K., Jagadeesh, A.: A review: On path planning strategies for navigation of mobile robot. Defence Technology 15(4): 582–606 (2019). DOI: 10.1016/j.dt.2019.04.011. 6. 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, pp. 1305–1311, USA (2016). DOI: 10.1109/AIM.2016.7576950 7. 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(4):1135–1145 (2016). DOI: 10.1109/TITS.2015.2498841 8. Mujumdar, A., Padhi, R.: Reactive Collision Avoidance Using Nonlinear Geometric and Differential Geometric Guidance. Journal of Guidance, Control, and Dynamics 34(1):303– 310 (2011). DOI: 10.2514/1.50923 9. Sunkara, V. R., Chakravarthy, A.: Cooperative Collision Avoidance and Formation Control for Objects with Heterogeneous Shapes. IFAC-PapersOnLine 50(1):10128–10135 (2017). DOI: 10.1016/j.ifacol.2017.08.1793 10. 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 11. 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(3):1–9 (2019). DOI: 10.1177/1729881419851945 12. Zhang, M.: Formation flight and collision avoidance for multiple UAVs based on modified tentacle algorithm in unstructured environments. PLoS ONE 12(8): e0182006 (2017).
DOI: 10.1371/journal.pone.0182006 13. Zhang, H., Perez Fernandez, R., De Baets, B.: Topologies induced by the representation of a betweenness relation as a family of order relations. Topology and its applications 258: 100–114 (2019). DOI: 10.1016/j.topol.2019.02.045 14. Tripathy, B. K., Arun, K. R.: Soft Sets and Its Applications. In: John, S. J. (Ed.), Handbook of Research on Generalized and Hybrid Set Structures and Applications for Soft Computing, pp. 65–85. IGI Global. (2016). DOI: 10.4018/978-1-4666-9798-0.ch005 15. Al Ghour, S., Bin-Saadon, A.: On some generated soft topological spaces and soft homogeneity. Heliyon, 5(7), e02061 (2019). DOI: 10.1016/j.heliyon.2019.e02061 16. Ali, M.I., Mahmood, T., Rehman, M.M.U., Aslam, M.F.: On lattice ordered soft sets. Applied Soft Computing 36:499–505 (2015) DOI: 10.1016/j.asoc.2015.05.052 17. Li, Z., Xie, N., Gao, N.: Rough approximations based on soft binary relations and knowledge bases. Soft Computing 21, 839–852 (2017). DOI: 10.1007/s00500-016-2077-2 18. 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