The problem of avoiding a collision between moving agents constantly arises in multi-agent systems with decentralized control. The various algorithms for solving this problem are accompanied by computational complexity and increasing computational power requirements as the number of agents in question increases. There are difficulties in adapting these algorithms to practical applications on mobile platforms. It is necessary to develop simpler computational schemes and to apply appropriate models. The most computationally expensive step in the classical collision avoidance algorithm ORCA is to calculate the mutual half-planes of possible collision for each pair of robots and use linear programming to calculate the new velocity from them. The application of the functional-voxel method will simplify the necessary calculations by storing in graphical images the local geometric characteristics of the searched domain. Moreover, the application of such models will make it possible to perform most of the necessary calculations in advance, which will accelerate the work of the algorithm. This paper proposes the construction of a functional-voxel model of a required geometric domain by interpolating the contour of the domain using Bézier curves. The local geometric modelling by means of local zeroing function is used as a tool for functional-voxel curve The obtained functional-voxel model represents a static case of possible mutual positioning of two agents. A four-dimensional graphical model is proposed to solve the dynamic case. This model performs the distribution of the static case modelling results in the space-time
modelling. characteristics.
Existing algorithms of robot motion in multi-agent systems are usually based on the geometric representation of the point-positions of agents and their velocity vectors [1]. In papers devoted to such algorithms [2-3], as a rule, only the general logic of behavior of each agent under threat of collision is described, and all geometrical aspects of such approaches are not presented.
The classical ORCA algorithm for determining the collision avoidance vector constructs a collision velocity region. The geometry of this region is formed by two tangents to a circle. The process of calculating this region is the most computationally intensive of all necessary calculations. This makes it difficult to use the algorithm on mobile platforms.
The considered software implementations of such algorithms do not follow the basic principles of the classical algorithm outlined in the theoretical part. They use simplified vector schemes, which reduces the accuracy of the search for the optimal solution.
2021 Copyright for this paper by its authors.
The need arises to find accurate but simplified calculation schemes for the application of this algorithm in simulation systems, as calculations need to be carried out at each point in time in relation to each pair of robots under consideration. For example, approaches that allow the required parameters to be pre-calculated for the static problem, and then distribute the calculation results in space-time characteristics to solve the dynamic case.
Simplification of mathematical operations is a traditional advantage of functional-voxel modelling [4], due to the fact that part of calculations replaced by the generation of a graphic image containing all necessary local information about object geometry. The application of this method allows a significant part of calculations to be carried out in advance, before the robot movement process begins. The robot can perform calculations by referring to the required image of the functional-voxel model and obtaining the requested characteristic.
To construct a functional-voxel model requires the formulation of an analytical function describing the collision zone. For this purpose, it is necessary to obtain the R-functional modeling law [5] of the contour of its boundary on a given rectangular region. Based on the position of the half-planes organizing this contour, the inner region must contain a characteristic slope from the central ridge to the boundary of the collision zone. An example of such an image is shown in Figure 1.
a) b) Figure 2: Schematic representation and resulting R-functional model of domain
By interpolating the robot collision velocity area with some curve, the properties of functional-voxel curve modelling can be applied. This requires the contour of the area to be defined, so an analytical representation of the curve describing this contour is needed
The task of constructing the required contour can be reduced to interpolating the contour of a curve that passes through the given points. Parametrically defined curves are a universal design tool for constructing smooth contours. There are various approaches to construct a parametrically defined curve from predetermined points [7, 8]. It seemed easy enough to choose the most suitable approach and proceed to functional-voxel modelling. But the following problems arose in the process of solving this question. Let us consider a classical representative of parametric curves – the Bezier curve.
A smooth Bézier curve can be functional-voxel modelled in various ways. In particular, it can be modelled by applying the De Casteljo algorithm using the apparatus of R-functions [9]. However, the application of this approach cannot generate the required monotonic smooth surface. Moreover, creating complex curves with variable curvature is only possible with the discontinuity of the surface caused by the necessity of matching convex regions (Figure 3). of the model in which, instead of two segments, linear Bezier curves are used, i.e., they are also localized by minimal segments.
The resulting two-dimensional graphical images characterize the static situation of the relative position of the two robots relative to each other in x and y coordinates in the plane. In this case, the motion vectors of the robots lie on the same line. In practice, however, it is necessary to dynamically analyze the distance between the robots. Also, the motion vectors of the robots can be angled at different angles. Thus, it is necessary to consider the distance between the robots d and the angle of deviation of the motion vector of the approaching robot from the motion vector of the current robot.
Initially it was supposed to perform necessary transformations of the obtained geometrical model via operations of spatial transformations [10] (parallel transfer, rotation and scaling). However, by using the functional-voxel model, it is possible to obtain the full variety of possible robot arrangements in a single model.
Reducing the distance between the robots leads to a change in the geometry of the resulting area. A gradual divergence of the tangent lines is observed (Figure 10).
As a result, the mutual location of the two robots is defined by four variables - x and y coordinates, contained in a two-dimensional graphical image, the distance between the robots d and the angle of inclination . Thus, the dynamics of motion of the two robots will be displayed in a four-dimensional model, a visual representation of which is shown in Figure 14.
The obtained 4-dimensional functional-voxel model displays the dynamics of collision velocity zone representation for basic situations of relative position of two robots and allows to eliminate from the procedure of ORCA region determination the main part of calculations, involved for determination of deviation of velocity direction of the considered robot. This approach will justify its application in various multicriteria calculations in mathematical modeling problems represented geometrically.
[1] A. V. Timofeev, R. M. Yusupov, Principles of Integrated Multi-Agent Navigation and Intelligent Control Systems for Mechatronic Robots, Information Technologies & Knowledge 3 (2011) 327. in Russian. [2] Jur van den Berg, Stephen J Guy, Ming C Lin, Dinesh Manocha, Reciprocal n-Body Collision
Avoidance, Robotics Research (2011) 3-19. doi: 10.1007/978-3-642-19457-3_1. [3] D. Alejo, J. A. Cobano, G. Heredia and A.Ollero, Optimal Reciprocal Collision Avoidance with Mobile and Static Obstacles for Multi-UAV Systems, International Conference on Unmanned Aircraft Systems (2014) 1259-1266. doi: 10.1109/ICUAS.2014.6842383 [4] A. V. Tolok, Functional voxel method in computer modeling, Moscow, Fizmatlit, 2016. in
Russian. [5] V. L. Rvachev, Theory of R-functions and Some Applications, Kiev, Naukova Dumka, 1982. in
Russian; [6] A. V. Tolok, P. M. Harlanova, L. N. Sizova, M. A. Loktev, A. A. Sycheva, Modeling of control algorithms for groups of mobile robots by means of the functional-voxel method, Stankoinstrument 4 (2020) 76-81. in Russian. [7] E. V. Konopatsky, Geometric modeling of multifactor processes based on point calculus, Ph.D. thesis, Nizhny Novgorod State University Of Architecture And Civil Engineering (NNGASU), Nizhny Novgorod, 2020. In Russian. [8] V. V. Borisenko, Construction of an Optimal Bezier Spline, Fundamental and Applied
Mathematics 3 (2016) 57 –72. in Russian. [9] A. V. Tolok, A. A. Sycheva, N. B. Tolok, Construction of the Functional Voxel Model for a Spline Curve, in: Proceedings of the 30th International Conference on Computer Graphics and Machine Vision, GraphiCon 2020, CEUR Workshop Proceeding, St.Petersburg, 2020. URL: http://ceurws.org/Vol-2744/paper52.pdf. [10] E. V, Lotorevich, Geometric transformations of the functional voxel model space, Master`s thesis, Nizhny Novgorod State University Of Architecture And Civil Engineering (NNGASU), Nizhny Novgorod, 2016. In Russian.