Computational Model of Soft Safety Domains and Rough Motion Corridors within Configuration Spaces Volodymyr Sherstjuk1[0000-0002-9096-2582], Maryna Zharikova2[0000-0001-6144-480X], and Ruslan Levkivskiy3[0000-0001-9280-8098] 1Kherson National Technical University, Kherson, Ukraine vgsherstyuk@gmail.com 2Kherson National Technical University, Kherson, Ukraine marina.jarikova@gmail.com 3Kherson State Maritime Academy, Kherson, Ukraine levka.ru55555@gmail.com Abstract. 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 pro- posed spherical topology allows the use of various heuristics to overcome over- sampling and wide distribution of the random points specific to the rapidly ex- ploring 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 colli- sion 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. Keywords: Computational model, Reactive path planning, Collision avoid- ance, Safety domain, Spherical soft topology, Rough motion corridor 1 Introduction 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 involve- ment is undesirable. Certainly, in the fields where they have not been being used, researchers are already working closely on this issue. Furthermore, groups of un- manned vehicles operating simultaneously in several environments have begun to be applied. A smart fishery task is a good example of such operation involving a multi- tude of aerial, surface, and underwater vehicles, where unmanned aerial vehicles per- Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). IntelITSIS-2020 form search missions looking for fishing flocks, unmanned underwater vehicles per- form 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 vehi- cles (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 environ- ments, there is a range of essential constraints imposed on their movement. Some of them are related to static and dynamic obstacles, vehicle dynamics restrictions (veloc- ity, 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 con- ditions 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 con- sidered 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 re- planning 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 [1]. The problem addressed in this paper relates to the real-time re-planning of the joint motion of heterogeneous teams of UVs. 2 Related Works Usually, researchers consider path planning at two main levels: global planning and local planning [2]. The global planning allows determining the path from a certain starting point to the given target point taking into account specific criteria such as the shortest path or minimal travel time. Global planning methods use initial information that is known a priori including the location of various static obstacles. However, unexpected obstacles can often violate pre-determined paths requiring adequate reac- tion to avoid collisions. Thus, there is a need for re-planning, which allows flexibly changing the vehicle’s path corresponding to dynamics of the environment, safety conditions, and the appearance of various circumstances that have not been taken into account during the initial planning due to uncertainty [3]. This task is in the focus of our paper. For now, researchers proposed some approaches and a multitude of path- planning algorithms related to unmanned vehicle’s path planning. Thus, there is a heuristic-based approach and corresponding algorithms such as the Dijkstra, A*, D*. It is known that such algorithms have high computational complexity, so they can not be used for the real-time re-planning [4]. 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 con- structed 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, over- sampling, 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 configura- tion 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 correspond- ent 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 Proposed Methodology 3.1 Collision Avoidance Scenario 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. Fig. 1. Static obstacle avoiding scenario 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 be- ing at the distance d 2 from the obstacle V1 . Thus, a straightforward fragment of the 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 d min from the obstacle V1 . 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 re- turn 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 mov- ing object A2 considered as an “intruder” that violates the pre-planned path P . Cer- tainly, 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 re- solved 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 ) = υ A ( t ) − υ A ( t )  ⊥ B ( A1 , A2 ) , where υ R ( t ) is a projection of relative velocity be- 1 2 tween A1 and A2 on the bearing B ( A1 , A2 ) from A1 to A2 at the time t as well as υ A ( t ) and υ A ( t ) are velocity vectors of A1 and A2 at the time t respectively. 1 2 Fig. 2. Dynamic obstacle avoiding scenario 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 calcula- tion of the relative velocities’ vectors can be time-consuming, therefore, the relative bearings are often evaluated before that as shown in Fig. 3. Fig. 3. Evaluation of relative bearings 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 BA A ( t j − 2 ) ≠ BA A ( t j −1 ) ≠ BA A ( t j ) during at 1 2 1 2 1 2 least three successive time moments t j − 2 , t j −1 , t j , there is no potential collision. And A A (t j −2 ) vice versa, if B= 1 2 A A ( t j −1 ) B= 1 2 BA A ( t j ) , there is a potential collision, therefore, it 1 2 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 drop- ping 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. Fig. 4. Collision cone estimation 3.2 Safety Domains 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 prob- lem is combinatorial and, accordingly, computationally hard. Instead of this, the defi- nition of the safety domain [10] breaks down the circumjacent area into safe and dan- gerous 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 under- standing 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 unpredicta- bility 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 three- dimensional spaces, we consider them spherical. Fig. 5. Definition of safety domains 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 do- mains to take any geometric shape. However, it is quite difficult to do this using exist- ing approaches. We can define safety conditions by a system of concentrically nested spheres, radi- uses 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 colli- sion, 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 re- stricted 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 pa- rameters, 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 Topology of Configuration Space Let Y be a set of a certain nature and T be a set of time points. Assume that a strict order