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-functions) 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 developed.
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 considered 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 decentralized 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 situation 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, optimization 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.
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-functional construction of a complex geometry domain [
At this stage, new challenges are opened for the effective implementation of such a model at the software and technical level. 2
The ORCA algorithm was first introduced in 2011 [4], as the principle of decentralized 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 vectors 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 algorithms 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 collisionavoidance algorithm for the navigation of arbitrary agents, from pedestrians to various types of robots, including vehicles. 3
The presented works are based on a significant number of complex geometric calculations 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 corrections 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 mathematical 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 obstacle avoidance [6] and in the development of functional-voxel modeling of mathematical programming problems [7]. Based on the proposed approach, various formulations of the path finding problem have already been implemented [6, 13-14].
The functional-voxel representation of the collision region can be calculated in advance, 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 simplifies 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 approach of the robots, is determined by the vector ( − )( ( − ) =-1.5, ( − ) =2.5) as shown in Figure 2. 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 the angles = ( )and = arccos ( √( 2+ 2)−( + )2 √ 2 + 2 ). The equations of the lines 1( , ) and 2( , )take the form: 1( , )= − ( + ) , 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 introduction 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 determine 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 1and 2 from the center of the circle with radius ( + ) (Fig. 3.). The equations of such lines are described as follows: 3( , )= ( − )− tg (
+ − )( − ), values are positive, then the point with coordinates ( ( − ) , ( − ) )is located between 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 boundary is considered by the distance to the lines 1 and 2: 1 = ( − ) + ( + ) ( − ) ,
( ( + ))2+1 1 = ( + ) ( − ) + ( + ) ( − ) − ( − ) ,
( ( + ))2+1 1 = √ 12 + 12, 2 = ( − ) + ( − ) ( − ) , ( ( − ))2+1 (5) (6) (7) 2 = ( − ) ( − ) + ( − ) ( − ) − ( − ) , , ( ,
)= min( 1( 1, 1), 2( 2, 2)).
Region
| here is determined by the equation of a line parallel to the selected boundary (for example, 1( , )) transferred to a point with coordinates ( + , + ): | ( , )= ( − ( + ))− ( + )( − ( + )).
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 , ), 2 2 (9) (10) (11) (12) where
= (
√( − ( ( − ) ) + ( − ( ( − ) )2. As a result, we have: ( −( ( − ) ),
( −( ( − ) ) = ( + )
− | = ( + )( − ( + )− ( − ( + ).
(14) 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 oncoming 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 completely 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 applied to the description of regions, which made it possible to distinguish regions with a positive sign of values: | = 1 ∧ 2 ∧ ( 3 ∨ 4)∨ .
(15) 4 +
4 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 + ′2, 2 =
( + )( ′ − | − |)− √ ′2 + ′2.
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 coordinates of the position point of the robot:
| − | = √ (2 − )+ (2 − )+ (2 − ).
The rotation angles and are calculated as follows: = + 2 3 → ( − ) = 0, ( − ) < 0 (18) (19) (20) (21)
The matrix for recalculating the coordinates of the position of the region will take the form: [ ′ ′ ′] = [
] , = [− 0 0 0 1 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 position of the half-space τ| in the 3D environment.
τ| is half-plane, then in τ| in a 3D environment 6
The conducted studies proved the possibility of modeling the analytical tools of multiagent motion algorithms using the functional-voxel method. The resulting functionalvoxel model acts as a template that carries complete information about the local geometric characteristics at each point in space. This information allows one to easily determine 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). 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) sovokupnosti traektorij dlya navigacii bespilotnyh transportnyh sredstv [Dynamics constraint-aware planning of multiple paths for unmanned vehicle]. Journal Large-Scale Systems Control 58, 306-342 (2015) (in Russian) in 3D environment with a multivariant model. Trudy SPIIRAN, 45, 5-25 (2016) collision avoidance and navigation for video games (2012) ceedings, 2(2), 40-44 (2015) 11. Mao, R., Gao, H., Guo, L: A Novel Collision-Free Navigation Approach for Multiple Nonholonomic Robots Based on ORCA and Linear MPC. Mathematical Problems in Engineering (2020) 12. Wolinski, D., Lin, M. C.: Generalized WarpDriver: Unified Collision Avoidance for MultiRobot Systems in Arbitrarily Complex Environments. In Robotics: Science and Systems.