Functional-voxel Modeling of Navigation Algorithm ORCA Mikhail Loktev[0000-0002-0465-1201], Alexey Tolok[0000-0002-7257-9029], and Vladimir Romakin1[0000-0002-9678-0130] Laboratory of Computer Graphics, V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya street, Moscow, 117997, Russia Abstract. The article considers an example of modeling the ORCA algorithm using the functional-voxel method. An analytical description of the permissible collision zone using the set-theoretic apparatus of Rvachev functions (R-func- tions) is proposed. Based on graphical image models, an approach to constructing the area of permissible robot speeds on the plane and in space has been devel- oped. Keywords: Functional-voxel Modeling, ORCA, Multi-agent Systems. 1 Introduction The principles that solve navigation problems in multi-agent systems are comparable to the interaction of social public groups. They can also be divided into centralized and decentralized [2]. With a centralized approach, the actions of agents are often consid- ered from the point of view of fulfilling a joint goal by joint efforts. The action strategy of such agents is described through global system states and joint actions of agents [3]. In this case, the agents are gathered in groups, often choosing a leader, and solve the problem by joint team interaction. However, there are situations in which a decentral- ized agent action planning system is required [3], including decentralized navigation systems. In such systems, each agent has its own goal (for example, delivery service agents). The algorithm for solving this problem involves taking into account the situa- tion throughout the scene and makes an independent decision regarding the behavior of other agents. And this happens with every single agent. In such an algorithm, optimi- zation of the solution is necessarily applied, taking into account the set goal and the many restrictions that arise in its path. One of the representatives of the algorithms of this class is the ORCA algorithm. It is based on the construction of linear half-spaces with respect to each agent, forming at the intersection an area of possible solutions for applying the optimization principles of linear mathematical programming. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). * Supported by V.A. Trapeznikov Institute of Control Science of Russian. 2 M. Loktev, A. Tolok, V. Romakin The article discusses the approach to the construction of the ORCA algorithm by means of functional voxel modeling based on the analytical principles of the R-func- tional construction of a complex geometry domain [1]. At this stage, new challenges are opened for the effective implementation of such a model at the software and technical level. 2 Related Work The ORCA algorithm was first introduced in 2011 [4], as the principle of decentral- ized navigation for large groups of agents, which provides a sufficient condition for avoiding collisions between agents with individual goals. Moreover, each agent takes at least half of the “responsibility” for avoiding a collision with another agent [2]. This principle is based on an earlier work [8] devoted to the formation of the collision region — the velocity obstacle (VO). A velocity obstacle is a region formed by velocity vec- tors and leading to a collision of agents over a certain period of time. Subsequent scientific studies of other groups of authors used the ORCA algorithm to solve various applied problems. For example, the use of various navigation algo- rithms for mutual local evasion of virtual agents in video games is considered in [9]. Simulation of automobile traffic at the intersection based on the ORCA algorithm is considered in [10]. A number of modifications to the ORCA algorithm have also been developed. For example, a new accident-free approach to navigation of nonholonomic robots based on ORCA and taking into account the kinematics of the studied robots was presented in [11]. Also noteworthy is the work [12] which presents a unified collision- avoidance algorithm for the navigation of arbitrary agents, from pedestrians to various types of robots, including vehicles. 3 Urgency of the problem The presented works are based on a significant number of complex geometric calcula- tions at each stage of the operation of the ORCA algorithm. Moreover, for a large group of agents, it is required to carry out a mutual calculation of the possible velocity cor- rections for each pair of robots, followed by the calculation of their new speed on the basis of linear programming. Moreover, for a large group of agents, it is necessary to carry out a mutual calculation of possible speeds for each pair of robots, followed by calculating their new speed based on linear programming. Simplification of mathemat- ical operations is traditionally considered an advantage of functional-voxel modeling, when part of the calculations is replaced by the formation of a graphic image with all the necessary local information it. Similar studies have been successfully carried out on the implementation of problems of local optimization of the path to the goal with ob- stacle avoidance [6] and in the development of functional-voxel modeling of mathe- matical programming problems [7]. Based on the proposed approach, various formula- tions of the path finding problem have already been implemented [6, 13-14]. The functional-voxel representation of the collision region can be calculated in ad- vance, and during the operation of the algorithm only simple calculations will be Functional-voxel modeling of navigation algorithm ORCA 3 applied to the obtained local geometric characteristics of the model, which greatly sim- plifies the computational process. Such a model can be used as a graphic template for modeling the relations of two robots defined in space. 4 Analytical presentation of Velocity Obstacle - 𝑽𝑶𝑻𝑩|𝑨 Consider a specific example of the mutual arrangement of robots A and B with their effective radii 𝑅𝐴 and 𝑅𝐵 equal to unity, where 𝑃𝐵 (−2,3)and 𝑃𝐴 (2, −3) (Fig. 1). Bind the position of the robots to the speed coordinate system. To do this, transfer the origin to the point 𝑃𝐴 , then 𝑃𝐵 (-4,6) will change its coordinates. The initial speeds of both robots are determined by the vectors 𝑣𝐴 (𝑣𝐴𝑥 = 1.5, 𝑣𝐴𝑦 =1.0) and 𝑣𝐵 (𝑣𝐵𝑥 = 3.0, 𝑣𝐵𝑦 =-1.5), and the difference of these vectors, which determines the vector of ap- proach of the robots, is determined by the vector 𝑣(𝐴−𝐵)(𝑣(𝐴−𝐵)𝑥 =-1.5, 𝑣(𝐴−𝐵)𝑦 =2.5) as shown in Figure 2. Fig. 1. The starting position of the robots The difference in the coordinates of the centers of the agents will give a new point(𝑃𝐴 − 𝑃𝐵 ), which in this case will coincide with the position of agent B. At this point, construct a new circle with a common radius of two robots (𝑅𝐴 + 𝑅𝐵 ). Lines 𝑃𝑟1 (𝑥, 𝑦) and 𝑃𝑟2 (𝑥, 𝑦) define half-spaces for lines tangent to a circle with radius (𝑅𝐴 + 𝑅𝐵 ) originating from the origin. To describe their location, it suffices to calculate 2 +𝑦 2 )−(𝑅 +𝑅 )2 √(𝑥𝐵 𝑦 𝐵 𝐴 𝐵 the angles 𝛼 = 𝑎𝑟𝑐𝑡𝑔 ( 𝐵) and 𝛽 = arccos ( ). 𝑥𝐵 2 +𝑦 2 √𝑥𝐵 𝐵 4 M. Loktev, A. Tolok, V. Romakin Fig. 2. Description of the scene with two agents A and B with given velocity vectors The equations of the lines 𝑃𝑟1 (𝑥, 𝑦) and 𝑃𝑟2 (𝑥, 𝑦) take the form: 𝑃𝑟1 (𝑥, 𝑦) = 𝑦 − 𝑡𝑔(𝛼 + 𝛽 )𝑥, (1) 𝑃𝑟2 (𝑥, 𝑦) = 𝑡𝑔(𝛼 − 𝛽 )𝑥 − 𝑦. (2) The area formed between them determines the zone of a possible collision when the velocity difference vector 𝑣(𝐴−𝐵) gets into it. However, the dynamics of the current process should be taken into account. For this, it is worth introducing the parameter of the time interval of the interaction of robots 𝜏, which allows us to clarify the position of the critical zone taking into account the distance between two robots. The introduc- tion of such a parameter makes it possible to clarify the collision avoidance zone. We introduce the value 𝜏 =2.0, as the interval of the known (spare) time for which it is required to determine the region of possible collisions. The position of the new circle defining the beginning of the danger zone is set by the center point (𝑃𝐴 − 𝑃𝐵 )/𝜏 and radius (𝑅𝐴 + 𝑅𝐵 )/𝜏 (Fig. 3). The resulting circle will de- termine the border of the zone of collision with robot B closest to robot A over a time interval 𝜏. To construct an algorithm for determining the membership of the end point of the τ velocity difference vector 𝑣(𝐴−𝐵) in the region of the obtained collision region 𝑉𝑂𝐴|𝐵 , it is necessary to divide this zone into two sections. The first section controls the entry τ of the vector 𝑣(𝐴−𝐵) into the 𝑉𝑂𝐴|𝐵 zone, bounded by the straight lines: 𝑃𝑟1 , 𝑃𝑟2 , 𝑃𝑟3 and 𝑃𝑟4 , where 𝑃𝑟3 and 𝑃𝑟4 - perpendiculars dropped to the lines 𝑃𝑟1 and (𝑅 +𝑅 ) 𝑃𝑟2 from the center of the circle with radius 𝐴 𝜏 𝐵 (Fig. 3.). The equations of such lines are described as follows: 𝑦 𝜋 𝑥 𝑃𝑟3 (𝑥, 𝑦) = (𝑦 − 𝜏𝐵) − tg ( 2 + 𝛼 − 𝛽) (𝑥 − 𝜏𝐵), (3) Functional-voxel modeling of navigation algorithm ORCA 5 𝑦 𝜋 𝑥 𝑃𝑟4 (𝑥, 𝑦) = (𝑦 − 𝐵) − tg ( + 𝛼 + 𝛽) (𝑥 − 𝐵). (4) 𝜏 2 𝜏 τ Fig. 3. Formation of collision region 𝑉𝑂𝐴|𝐵 At the initial stage of the algorithm (condition 1), we calculate the values of 𝑃𝑟1 (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) and 𝑃𝑟2 (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) using equations (1) and (2). If both values are positive, then the point with coordinates (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) is located be- tween the lines 𝑃𝑟1 and 𝑃𝑟2 , and therefore is for further study. Otherwise, this point τ does not fall into zone 𝑉𝑂𝐴|𝐵 and the robot А can move relative to robot В at the same speed and in the same direction. If point (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) is between these lines, you should clarify its position by checking for a positive sign the values of any of the expressions (condition 2): 𝑃𝑟3 (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) ≥ 0 or 𝑃𝑟4 (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) ≥ 0. The fulfillment of the second condition is sufficient to begin to determine the direction of the normal 𝑛⃗ to the nearest boundary of the required region 𝑂𝑅𝐶𝐴𝐴|𝐵 for calculating speed correction vector of τ robot А to ensure its exit from zone 𝑉𝑂𝐴|𝐵 . Denote such a correction vector 𝑤 ⃗⃗ . The direction 𝑤 ⃗⃗ coincides with the direction 𝑛⃗, and its length is determined by the distance τ to the nearest boundary of zone 𝑉𝑂𝐴|𝐵 . In this case, the definition of the nearest bound- ary is considered by the distance to the lines 𝑃𝑟1 and 𝑃𝑟2 : 𝑣(𝐴−𝐵)𝑥 +𝑡𝑔(𝛼+𝛽)𝑣(𝐴−𝐵)𝑦 𝑑𝑥1 = 2 , (5) (𝑡𝑔(𝛼+𝛽)) +1 𝑣(𝐴−𝐵)𝑥+𝑡𝑔(𝛼+𝛽)𝑣(𝐴−𝐵)𝑦 𝑑𝑦1 = 𝑡𝑔(𝛼 + 𝛽 ) (𝑡𝑔(𝛼+𝛽))2 +1 − 𝑣(𝐴−𝐵)𝑦 , (6) 𝑑1 = √𝑑𝑥12 + 𝑑𝑦12 , (7) 𝑣(𝐴−𝐵)𝑥+𝑡𝑔(𝛼−𝛽)𝑣(𝐴−𝐵)𝑦 𝑑𝑥2 = 2 , (8) (𝑡𝑔(𝛼−𝛽)) +1 6 M. Loktev, A. Tolok, V. Romakin 𝑣(𝐴−𝐵)𝑥+𝑡𝑔(𝛼−𝛽)𝑣(𝐴−𝐵)𝑦 𝑑𝑦2 = 𝑡𝑔(𝛼 − 𝛽 ) (𝑡𝑔(𝛼−𝛽))2 +1 − 𝑣(𝐴−𝐵)𝑦 , (9) 𝑑2 = √𝑑𝑥22 + 𝑑𝑦22 , (10) 𝑑 (𝑑𝑥, 𝑑𝑦) = min(𝑑1 (𝑑𝑥1 , 𝑑𝑦1 ), 𝑑2 (𝑑𝑥2 , 𝑑𝑦2 )). (11) Region 𝑂𝑅𝐶𝐴𝐴|𝐵 here is determined by the equation of a line parallel to the selected boundary (for example, 𝑃𝑟1 (𝑥, 𝑦)) transferred to a point with coordinates (𝑣𝐴𝑥 + 𝑑𝑥, 𝑣𝐴𝑦 + 𝑑𝑦): 𝑂𝑅𝐶𝐴𝐴|𝐵 (𝑥, 𝑦) = (𝑦 − (𝑣𝐴𝑦 + 𝑑𝑦)) − 𝑡𝑔(𝛼 + 𝛽)(𝑥 − (𝑣𝐴𝑥 + 𝑑𝑥)). (12) In the event that after the fulfillment of the first condition the second is not fulfilled, we should continue to consider other conditions that allow us to clarify the relation of point τ (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) to region 𝑉𝑂𝐴|𝐵 . Equation 𝐶𝑖𝑟𝑐𝑙𝑒𝜏 (𝑥, 𝑦) is an equation of a circle with a radius (𝑅𝐴 + 𝑅𝐵 )/𝜏 a center at point (𝑃𝐴 − 𝑃𝐵 )/𝜏, which means it is described by the expression: 𝐶𝑖𝑟𝑐𝑙𝑒𝜏 (𝑥, 𝑦) = (𝑅𝐴 /𝜏 + 𝑅𝐵 /𝜏)2 − (𝑥 + 𝑥𝐵 /𝜏)2 − (𝑦 − 𝑦𝐵 /𝜏)2 . (13) τ A part of this circle that is not included in the region 𝑉𝑂𝐴|𝐵 continues to describe its boundary. Therefore, the expression 𝐶𝑖𝑟𝑐𝑙𝑒𝜏 (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) ≥ 0 provides the third τ condition for belonging to the region 𝑉𝑂𝐴|𝐵 as confirmation of the belonging of the point (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) to the region of the circle 𝐶𝑖𝑟𝑐𝑙𝑒𝜏 (𝑥, 𝑦). Under the third condition, the closest point on the boundary for point (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) is a point on a circle with radius (𝑅𝐴 + 𝑅𝐵 )/𝜏. To determine the direction to such a point as the direction of the normal, it suffices to express a straight line orthogonal to a straight line passing through points (𝑣(𝐴−𝐵)𝑥 , 𝑣(𝐴−𝐵)𝑦 ) and (𝑥𝐵 /𝜏, 𝑦𝐵 /𝜏) and transfer to the point of vector 𝑣𝐴 shifted by coordinates 𝑦 ( 𝐵 −(𝑣(𝐴−𝐵)𝑦 ) (𝑅𝐴+𝑅𝐵 ) (𝑤𝑐𝑜𝑠𝛾, 𝑤𝑠𝑖𝑛𝛾), where 𝛾 = 𝑎𝑟𝑐𝑡𝑔 𝑥𝜏𝐵 , 𝑤= − ( −(𝑣(𝐴−𝐵)𝑥 ) 𝜏 𝜏 2 √(𝑥𝐵 − (𝑣(𝐴−𝐵)𝑥 ) + (𝑦𝐵 − (𝑣(𝐴−𝐵)𝑦 )2 . As a result, we have: 𝜏 𝜏 𝜋 𝑂𝑅𝐶𝐴𝐴|𝐵 = 𝑡𝑔 ( + 𝛾) (𝑥 − (𝑣𝐴𝑥 + 𝑤𝑐𝑜𝑠𝛾) − (𝑦 − (𝑣𝐴𝑦 + 𝑤𝑠𝑖𝑛𝛾). (14) 2 As can be seen from the reasoning, the presented algorithm allows us to describe the situation of mutual coordination of speed for the robot with respect to one of the on- coming robots. The full picture is determined by the intersection of all regions of the ORCA, built for each of the robots, affecting the adjustment of the final direction and speed. The obtained region of possible solutions requires the use of optimization tools to obtain the only true velocity vector 𝑣𝐴 . Any optimization statement has an objective function, which is expressed by the main direction to the goal. Such a statement is com- pletely solvable by linear mathematical programming [7]. Functional-voxel modeling of navigation algorithm ORCA 7 To verify the implementation of the calculation of the region on a specific example, τ the region 𝑉𝑂𝐴|𝐵 was simulated in the functional-voxel modeling system RANOK. For this, the R-functional apparatus of set-theoretic operations on functions [15] was ap- plied to the description of regions, which made it possible to distinguish regions with a positive sign of values: 𝑉𝑂𝐴|𝐵 = 𝑃𝑟1 ∧ 𝑃𝑟2 ∧ (𝑃𝑟3 ∨ 𝑃𝑟4 ) ∨ 𝐶𝑖𝑟𝑐𝑙𝑒𝜏 . (15) τ Figure 4 demonstrates the union in the space of velocities of region 𝑉𝑂𝐴|𝐵 and region 𝑂𝑅𝐶𝐴𝐴|𝐵 visually demonstrating the result of calculations for the task. Fig. 4. Construction of a graphic M-image based on equation (15) and formation of a half-plane τ 𝑂𝑅𝐶𝐴𝐴|𝐵 Figure 5 presents graphical image models (M-images) describing the local equation at the points of the collision region. M-images are one of the key tools for graphical anal- ysis of the functional-voxel modeling method [16]. Each of these images characterizes the normal component built in 4-dimensional space. To describe such a local equation, it is necessary to represent the normal vector at each point in the space in the 4th di- mension. τ To obtain the angle of inclination of region 𝑂𝑅𝐶𝐴𝐴|𝐵 it is sufficient to consider the component of the two-dimensional normal vector on the X axis at the point of applica- tion of the velocity difference vector, i.e. 𝑐𝑜𝑠𝛼 2 renormalized by the formula: 𝑐𝑜𝑠𝛼 4 𝑥 + 𝑐𝑜𝑠𝛽 4 𝑦 + 𝑐𝑜𝑠𝛾 4 𝑧 = 𝑐𝑜𝑠𝛿 4 , (16) 𝑐𝑜𝑠𝛼 4 𝑐𝑜𝑠𝛼 2 = = 𝑐𝑜𝑠𝛼 𝑂𝑅𝐶𝐴 . (17) √𝑐𝑜𝑠𝛼 4 2 +𝑐𝑜𝑠𝛽 4 2 8 M. Loktev, A. Tolok, V. Romakin 𝑐𝑜𝑠𝛼 4 𝑐𝑜𝑠𝛽 4 𝑐𝑜𝑠𝛾 4 𝑐𝑜𝑠𝛿 4 Fig. 5. M-images describing the local equation at the points of the collision region 5 Modeling collision region in three-dimensional space To simulate such a case in three-dimensional space, it is necessary to describe the col- lision region in the form of a figure of rotation around a certain axis, for example, ОХ, the generators of which are two straight lines 𝑃𝑟1 and 𝑃𝑟2 , combined with the region of the sphere completing this figure: 𝑃𝑟1 = 𝑡𝑔𝛽𝑥 ′ − √𝑦′2 + 𝑧′2 , (18) 𝜋 𝑃𝑟2 = 𝑡𝑔 ( 2 + 𝛽) (𝑥 ′ − |𝑃𝐴 − 𝑃𝐵 |) − √𝑦′2 + 𝑧′2 . (19) To determine the parameters of the spatial transfer of the figure to the required position, as shown in Figure 6, it is enough to determine the parameters of the spherical coordi- nates of the position point of the robot: 2 |𝑃𝐴 − 𝑃𝐵 | = √𝑥(𝑃 2 2 𝐴−𝑃𝐵 ) + 𝑦(𝑃 𝐴−𝑃𝐵 ) + 𝑧(𝑃 𝐴−𝑃𝐵 ) . (20) The rotation angles 𝜃 and 𝜑 are calculated as follows: 𝑦(𝑃 −𝑃 ) 𝐴 𝐵 𝑎𝑟𝑐𝑡𝑔 (𝑥 ) → 𝑥(𝑃𝐴−𝑃𝐵) > 0 (𝑃𝐴−𝑃𝐵 ) 𝑦(𝑃 −𝑃 ) 𝐴 𝐵 𝜃 = 𝜋 + 𝑎𝑟𝑐𝑡𝑔 (𝑥(𝑃 −𝑃 ) ) → 𝑥(𝑃𝐴−𝑃𝐵) < 0 , (21) 𝐴 𝐵 𝜋 → 𝑥(𝑃𝐴−𝑃𝐵) = 0, 𝑦(𝑃𝐴−𝑃𝐵) ≥ 0 2 3𝜋 {2 → 𝑥(𝑃𝐴−𝑃𝐵) = 0, 𝑦(𝑃𝐴−𝑃𝐵) < 0 Functional-voxel modeling of navigation algorithm ORCA 9 𝑧(𝑃 −𝑃 ) 𝜑 = 𝑎𝑟𝑐𝑐𝑜𝑠 ( |𝑃 𝐴−𝑃 𝐵| ). (22) 𝐴 𝐵 The matrix for recalculating the coordinates of the position of the region will take the form: [𝑥′ 𝑦′ 𝑧′] = [𝑥 𝑦 𝑧]𝑅𝑧 𝑅𝑦 , (23) 𝑐𝑜𝑠𝜃 𝑠𝑖𝑛𝜃 0 𝑠𝑖𝑛𝜑 0 𝑐𝑜𝑠𝜑 𝑅𝑧 = [−𝑠𝑖𝑛𝜃 𝑐𝑜𝑠𝜃 0] , 𝑅𝑦 = [ 0 1 0 ]. (24) 0 0 1 −𝑐𝑜𝑠𝜑 0 𝑠𝑖𝑛𝜑 Fig. 6. Calculation of the displacement of collision region 𝑉𝑂𝐴|𝐵 in a 3D environment τ If in a 2D environment the region of possible velocities 𝑂𝑅𝐶𝐴𝐴|𝐵 is half-plane, then in 3D such a region will be a half-space. Figure 7 shows a cross section of one of the components of the three-dimensional vector w, which determines the slope of the posi- τ tion of the half-space 𝑂𝑅𝐶𝐴𝐴|𝐵 in the 3D environment. τ Fig. 7. Construction of the region of permissible speeds 𝑂𝑅𝐶𝐴𝐴|𝐵 in a 3D environment 10 M. Loktev, A. Tolok, V. Romakin 6 Conclusion The conducted studies proved the possibility of modeling the analytical tools of multi- agent motion algorithms using the functional-voxel method. The resulting functional- voxel model acts as a template that carries complete information about the local geo- metric characteristics at each point in space. This information allows one to easily de- termine the necessary direction of the region of admissible velocities 𝑶𝑹𝑪𝑨𝛕𝑨|𝑩 . Using the presented approaches to the formation of the motion environment in multi-agent systems will allow us to abandon a number of numerical calculations in comparison with the classical description of the algorithm, and most importantly, it allows us to consider such problems without reference to the dimension of space (Fig. 7). References 1. Timofeev, A.V., Yusupov, R.M.: Principy postroeniya integrirovannyh sistem mul'tia- gentnoj navigacii i intellektual'nogo upravleniya mekhatronnymi robotami [Principles of building integrated systems of multi-agent navigation and intelligent control of mechatronic robots]. Information Technologies & Knowledge, 5(3), 237-244 (2011) (in Russian) 2. Dergachev, S.A.: Eksperimental'noe issledovanie reaktivnogo algoritma navigacii dlya grupp agentov – ORCA [Experimental study of reactive navigation algorithm for groups of agents – ORCA]. 17th Russian Conference on Artificial Intelligence, Ulyanovsk, Russian Federation. P.102 (2019) 3. Yakovlev, K.S., Baskin, E.S, Andreychuk, A.A.: Metod avtomaticheskogo planirovaniya sovokupnosti traektorij dlya navigacii bespilotnyh transportnyh sredstv [Dynamics con- straint-aware planning of multiple paths for unmanned vehicle]. Journal Large-Scale Sys- tems Control 58, 306-342 (2015) (in Russian) 4. Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D.: Reciprocal n-body collision avoid- ance. In Robotics research (pp. 3-19). Springer, Berlin, Heidelberg. (2011) 5. Tolok, A. V. Funkcional'no-voksel'nyj metod v komp'yuternom modelirovanii [Functional voxel method in computer modeling]. Moscow, 112 p. (2016) 6. Vassilyev, S. N., Loktev, M. A., Tolok, A. V., Tolok, N. B., Ul'yanov, S. A.: Route planning in 3D environment with a multivariant model. Trudy SPIIRAN, 45, 5-25 (2016) 7. Tolok, A. V., Tolok, N. B.: Mathematical programming problems solving by functional voxel method. Automation and Remote Control, 79(9), 1703-1712. (2018) 8. P. Fiorini, Z. Shiller.Motion planning in dynamic environments using Velocity Obstacles. Int. Journal of Robotics Research 17(7), 760-772 (1998) 9. Lake, A. T., Snape, J., Guy, S. J., Vembar, D., Lake, A., Lin, M. C., Manocha, D.: Reciprocal collision avoidance and navigation for video games (2012) 10. Schaefer, M.: Planning and coordination in driving simulation. Acta Polytechnica CTU Pro- ceedings, 2(2), 40-44 (2015) 11. Mao, R., Gao, H., Guo, L: A Novel Collision-Free Navigation Approach for Multiple Non- holonomic Robots Based on ORCA and Linear MPC. Mathematical Problems in Engineer- ing (2020) 12. Wolinski, D., Lin, M. C.: Generalized WarpDriver: Unified Collision Avoidance for Multi- Robot Systems in Arbitrarily Complex Environments. In Robotics: Science and Systems. (2018) Functional-voxel modeling of navigation algorithm ORCA 11 13. Loktev M. A. Osobennosti primeneniya funkcional'no-voksel'nogo modelirovaniya v zadachah poiska puti s prepyatstviyami [Features of application of functional voxel model- ing in problems of finding a path with obstacles]. Informacionnye tekhnologii v proektiro- vanii i proizvodstve [Information technologies in design and production] I. 1, 45-49 (2016) (in Russian) 14. Grigor’ev, S. N., Tolok, A. V., Tolok, N. B.: Local search gradient algorithm based on func- tional voxel modeling. Programming and Computer Software, 43(5), 300-306 (2017) 15. Rvachev V. L. Teoriya R-funkcij i nekotorye ee prilozheniya [Theory of R-functions and some of its applications]. Kiev, 552 p.(1982) 16. Tolok A. V. Graficheskie obrazy-modeli v informacionnyh tekhnologiyah [Graphic images- models in information technologies]. Prikladnaya informatika [Applied informatics] I. 4, 31- 40 (2009) (in Russian).