# Method of Formation of Quantitative Indicators of Complexity of the Environment by a Group of Autonomous Mobile Robots

Authors: Denis Beloglazov; Vladimir Pereverzev; Victor Soloviev; Viacheslav Pshikhopov; Morozov Roman
Journal: Journal of Robotics
 (2020)

---

## Abstract

This article presents the methods that allow forming quantitative estimations of functional characteristics of a group of autonomous mobile robots (AMRs) and local areas of the environment surrounding it. The evaluation of the environment is based on the analysis of scattering of the cloud of obstacle points and made using the information formed by the computer vision system (CVS), which every robot in the group has. The core element of CSV is 3D lidar. Quantitative data about the complexity of the environment can be used for determining the optimal methods of solving the planning tasks and forming the patterns of group formation. Such data about the complexity of local areas of the environment can also be used for determining them as insurmountable for a single robot or a group of robots. The reason for such a decision can be the violation of safety rules and breaking of the group formation. The assessment of robots’ functional characteristics is performed based on the fuzzy model that consists of separate fuzzy classifiers; each of them allows obtaining a quantitative estimation of one of the parameters. The hierarchic structure of the used fuzzy model makes it significantly easier to synthesize and analyze it.


---

## Body

## 1. Introduction

Robots are widely used in various spheres of human activity, such as the automotive industry, steel and chemical industry, and production of electronics. Further development of robotics is aimed at creating robots that are able to autonomously solve set problems and operate in groups. On the one hand, that makes robots less dependable on the human operator. On the other hand, that allows producing simple robots that operate in big and small mixed groups.To make robots function within the environment, it is necessary to improve the methods of path planning, mapping, environment evaluation, and assessment of functional possibilities of single robots that make a part of the group [1–22]. In [1–6], methods of organizing an exchange and complexation of data that are formed by single members of the robot group when they solve a task of mapping the environment are proposed. A distinctive feature of the proposed methods is the possibility of their use with insufficient amount of sensory information. In [7, 8], methods for estimating the probability of successful completion of the task by robots are proposed, based on mathematical modeling of their interaction with each other and the surrounding space. The practical use of the proposed methods requires a big amount of a priori information about the parameters of robots and the environment. Such information cannot always be obtained in a sufficient amount and does not always have the desired level of precision, which significantly narrows the applicability of this article’s findings.In [9–11], methods of mobile autonomous mobile robot path planning for environments with dynamic obstacles are proposed. A distinctive feature of the methods is the ability to predict the behavior of dynamic obstacles, which is taken into account in the process of forming the trajectories of the movement of robots.In [12], a hybrid method of path planning for a group of mobile robots is considered. Its main idea is the consequent use of two methods—method of artificial potential fields and genetic algorithms (GA), and method of obtaining preliminary robots’ path trajectory with its further optimization. A significant drawback of this method is the need for data on the location of obstacles, which is not always feasible in practice.In [13, 14], methods of mobile robots’ path planning based on classic GA are proposed. The peculiarity of the method described in [13] lies in the way of representing the generated trajectories by variable length chromosomes containing a set of pairs of values—the direction of movement and the length of the segment. The robot surrounding space is represented as the horizontal plane that is divided by sectors. That simplifies the process of genetic search but restricts the applicability of this method for the three-dimensional environment. The methods described in [13, 14], which have similar limitations, differ in the way of coding chromosomes.In [15, 16], a method of mobile robots’ path planning based on improved GA is proposed. Compared to analogs; the proposed algorithm has two significant differences: it uses data on the state of the environment that are limited by the visibility scope and applies a modified mutation operator. The main drawback of the methods described in [15, 16] is the same as of [13, 14] and connected with the representation of the environment.In [17], a method was proposed for the formation of optimal trajectories for moving mobile robots based on a genetic algorithm similar to the methods proposed in [14–16]. Its distinctive feature is the use of a special polynomial to smooth the resulting GA trajectories.In [18], different types of robot chassis’ that are intended for increasing the off-road performance in the complex environment of both natural and artificial kinds are considered. Proposed decisions allow to significantly increase the area of use of mobile robots, but they are designed for the urban environment.In [19], a method of reconfiguration of the structure of the snake-like wheel robot containing some base modules with the possibility to use each of them separately is considered. The main idea of the method is to minimize the time of base modules’ reconfiguration by their more precise maneuvering.In [20], a method of using a hive of robots for ground reconnaissance and mapping is proposed. It features the results of modeled hive landing on the surface of one of the planets of the Solar System, which confirm the efficiency of the method’s algorithms of control and coordination.In [21], a method for planning the path of moving mobile autonomous robots for three-dimensional environments, characterized by the possibility of optimizing the generated trajectories by using the particle swarm algorithm, is presented. The disadvantage of this method is the impossibility of its application in environment with dynamic obstacles.In [22], a method is presented that allows one to obtain optimal robot trajectories based on an improved self-learning algorithm Q-learning. The disadvantages of the method are similar to those described in [13, 14] and are determined by the two-dimensional grid way of representing space. The common feature of most works on robotics, including [1–22], is the insufficient attention to the analysis of the environment in which robots perform the set tasks. Evaluation of robots’ functional characteristics that allows determining the level of their fitness for the achievement of the set objectives is also not being done. In order to solve the above problems, this work presents the methods of formation of qualitative indicators of complexity of the local region of the environment and complex evaluation of robots’ characteristics.


## 2. Materials and Methods

During the experiments with the proposed method, a number of the following assumptions were made: the relative position of the group members is known to each of its members; information on obstacles detected is available to all group members at the same time. In practice, the implementation of these assumptions requires the use of special equipment, such as inertial navigation systems, GPS navigation, odometers, and other devices to solve the problem of determining the location of robots in area, a data transmission system for organizing intragroup information exchange. Currently, the proposed method does not limit the source of data necessary for its correct application, which makes it possible to use any available hardware devices.Under the “complexity of the environment” in this paper, we mean the number and configuration of obstacles in the environment surrounding the group of robots. Using data on the complexity of the environment and the parameters of the robots of the group, it is possible to obtain more optimal trajectories of movement of both individual members of the group and the entire group as a whole, to determine areas of space in which it is undesirable or unacceptable to enter.The method of formation of qualitative indicators of complexity of the local region of the environment is based on the use of a particular model. It allows transforming data that come from the i-th robot’s computer vision system into a numerical assessment of the local complexity of the environmentδloc. Let us consider how this happens. When robots use CVS based on 3D lidars, the obstacles are presented as a set of points, which allows assessing their distribution. Figure 1 illustrates the scanning of the environment by CVS.Figure 1
Illustration of CVS scanning the environment as a 3D lidar:OY1—АМR longitudinal axis; ОY2—АМR transverse axis; P1—obstacle point; dp11 and dp12—lengths of perpendiculars from the obstacle to the axes ОY1 and ОY3; dp1—distance to the point Р1.Using the physical analogy of the moment of rotation of the body around the longitudinal axis of an autonomous mobile robot (AMR)OY1 and the transverse axis ОY3, and considering the body mass to be single, we obtain the concentration J around the axes ОY1 and ОY3 for the point P1:(1)JOYp1=dp112,(2)JOYp3=dp132.Normalized concentrations of all the obstacle points around the axesОY1 and ОY3 can be found by the following formulas:(3)JOYp1=∑i=1mdpi12∑j=1mdj12+∑i=1mdpi12,(4)JOYp3=∑i=1mdpi32∑j=1mdj32+∑i=1mdpi32,where dpi1 and dpi3 are the lengths of perpendiculars from i-th obstacle to the axes ОY1 and ОY3, dj1 and dj3 are the lengths of perpendiculars from j-th lidar ray that did not meet an obstacle to the axes ОY1 and ОY3, m is the number of rays that met obstacles, and n is the number of rays that did not meet an obstacle.Let 3D lidar have the following characteristics:αlid: horizontal scanning angle (rad); βlid: vertical scanning angle (rad); llid: lidar operating range (m); Δlid: lidar rays spacing (rad). Using the above characteristics, lidar is able to scan the space left-to-right and bottom-up. Lengths of perpendiculars dpi1 and dpi3 can be found by the following algorithm: calculate the horizontal angle of the i-th ray (left-to-right) rhiΔ (rhi is the horizontal number of the i-th ray); calculate the vertical angle of the i-th ray (bottom-up) rviΔ (rvi is the vertical number of the i-th ray); calculate the coordinates xiР, yiР, and ziР of the point Рi using the formulas: xiР = dpicos (rhiΔ) × cos (rviΔ), yiР = dpisin (rhiΔ) × cos (rviΔ), ziР = dpicos (rhiΔ) × sin (rviΔ); to take into account the AMR orientation angles (φ, υ, γ), we need to multiply the (xi, yi, zi) coordinate vector by rotation matrix:(5)Mφ,υ,γ=cφcυcφsυsγ−sφcγcφsυcγ+sφsγsφcυsφsυsγ+cφcγsφsυcγ−cφsγ−sυcυsγcυcγ,where s (·) and c (·) are sines and cosines, respectively; the angles to the axes ОY1, ОY2, ОY3 were found through the direction cosines:(6)α=acosx1Pdp1,β=acosy1Pdp1,ρ=acosz1Pdp1.The lengths of perpendiculars from the pointPi to the axes ОY1 and ОY2 were found: dpi1 = dpisin (α) and dpi3 = dpicos (β). Last expressions allow calculating the concentrations of the obstacle points using formulas (1)–(4).To obtain the assessment of degree of the local complexity of the environment, we can use the following expression:(7)δlос=JОY1JОY3.In order to confirm the adequacy of the assessment of the local complexity of the environment, we performed simulation with the following given data: 3D lidar parameters:αlid = π/2, βlid = π/4, llid = 20 m, Δlid = π/30, and the space is scanned left-to-right and bottom-up; moving object parameters: y1 = 0, y2 = 0, y3 = 0, φ = 0, υ = 0, and γ = 0; and obstacle parameters: spheres with a unit radius.Below, the examples of cases with different given number of obstacles in the view of 3D lidar and different given distance from AMR to the obstacles are given.Case 1: there is one obstacle in the AMR’s view at the distance of 15 m. The vertical view projection for this case is given in Figure2; the front view projection is shown in Figure 3.Figure 2
Vertical projection of the 3D lidar’s view for one obstacle in 15 m.Figure 3
Front projection of the 3D lidar’s view for one obstacle in 15 m.In Case 1, we obtained the value of the local complexity of the environment ofδlос = 0.0115, which corresponds to reality, since the obstacle is far from AMR. Case 2: there is an obstacle in the AMR’s view at the distance of 5 m, which is three times closer than that in Case 1. The vertical view projection for this case is presented in Figure 4, and the front view projection is presented in Figure 5. In Case 2, we obtained the value of the local complexity of the environment of δlос = 0.0658. The value of complexity estimation increased because the obstacle is closer to the AMR now. Case 3: there is one obstacle in the AMR’s view at the distance of 1.35 m. Figure 6 illustrates the tridimensional view of the obstacle as seen by the AMR’s 3D lidar.Figure 4
Vertical projection of the 3D lidar’s view for one obstacle in 5 m.Figure 5
Front projection of the 3D lidar’s view for one obstacle in 5 m.Figure 6
Tridimensional view of the obstacle at the distance of 1.35 m by the AMR’s 3D lidar.In Case 3, the value of the local complexity of the environment in the direction of AMR’s movement isδlос = 1, which corresponds to reality, since the obstacle, in fact, blocks the way. Case 4: there are three relatively grouped obstacles in the AMR’s view at the distance of 15 m. The vertical view projection for this case is presented in Figure 7, and the front view projection is presented in Figure 8. In Case 4, we obtained the value of the local complexity of the environment of δlос = 0.0483. The obtained estimation value is bigger than that in Case 1—though the distance to the obstacles is the same, there are now three of them, which form a group. Case 5: there are three relatively grouped obstacles in the AMR’s view at the distance of 5 m.Figure 7
Vertical projection of the 3D lidar’s view for three obstacles in 15 m.Figure 8
Front projection of the 3D lidar’s view for three obstacles in 15 m.The vertical view projection for this case is presented in Figure9, and the front view projection is presented in Figure 10. In Case 5, we obtained the value of the local complexity of the environment of δlос = 0.8153. The value of the environment complexity estimation is now significantly bigger, comparing with the previous case that had the same number of obstacles, but at three times bigger distance from the AMR. Case 6: there are five relatively grouped obstacles in the AMR’s view at the distance of 15 m. The vertical view projection for this case is presented in Figure 11, and the front view projection is presented in Figure 12.Figure 9
Vertical projection of the 3D lidar’s view for three obstacles in 5 m.Figure 10
Front projection of the 3D lidar’s view for three obstacles in 5 m.Figure 11
Vertical projection of the 3D lidar’s view for five obstacles in 15 m.Figure 12
Front projection of the 3D lidar’s view for five obstacles in 15 m.In Case 6, we obtained the value of the local complexity of the environment ofδlос = 0.0531, which is bigger than that in Case 4 with three obstacles placed at the same distance. Case 7: there are five obstacles far from each other in the AMR’s view at the distance of 15 m. The vertical view projection for this case is presented in Figure 13, and the front view projection is presented in Figure 14. In Case 7, we obtained the value of the local complexity of the environment of δlос = 0.1784, which is bigger than that in Case 4 with three obstacles and corresponds to the level of five obstacles in the AMR’s 3D lidar view.Figure 13
Vertical projection of the 3D lidar’s view for five scattered obstacles in 15 m.Figure 14
Front projection of the 3D lidar’s view for five scattered obstacles in 15 m.Successful completion of tasks by a group of robots is determined not only by the complexity of the environment but also by robots’ characteristics. Obtaining a quantitative assessment of characteristics of members of an AMR group is a separate task, which is solved in this work basing on the model shown in Figure15. This model consists of the following elements: model of assessment of the AMR’s dynamics; model of assessment of the AMR’s size; and model of assessment of the AMR’s maneuvering capabilities. Decomposition of the model shown in Figure 15 into its constituent elements significantly reduces the complexity of the synthesis. This is achieved by reducing the number of combinations of input and output variables that the researcher is forced to operate when drawing up the control rules for each of the elements. Instead of one bulky fuzzy model, the result is a few simpler and logically transparent ones.Figure 15
Structure of the model of assessment of the AMR’s characteristics.We are going to present the model of assessment of the robot’s dynamics as a combination of three models М1–М3 as follows: the input of the model receives output variables of fuzzy classifiers regarding the linear and angular characteristics of AMR, and the output variablemr is formed. Linear velocity vr and linear acceleration ar will be considered as the input linguistic variables (LV) of model M1. Angular velocity ωr and angular acceleration εr will be considered as the input linguistic variables of model M2.For the LV “linear velocity,” experts determined the term setT (vr) = {<low>, <medium>, <high>}, which contains three terms—three fuzzy variables (FV). The base set for defying FV LV “linear velocity” has the velocity change range from vrmin to vrmax. To simplify further operations with fuzzy values, let us normalize the range of velocity changes, reducing it to the interval [0, 1]. Figure 16 shows the FV membership function for LV vr. For the LV “linear acceleration,” experts determined the term set T (ar) = {<slow>, <average>, <fast>}, which contains three FVs. Note that the term “linear acceleration” includes both the acceleration and retardation of an AMR. The base set for setting FV LV “linear acceleration” has the acceleration change range from −armin to + armax.Figure 16
FV membership functions for LVvr: “linear velocity”.Again, we simplify further operations with fuzzy values; let us normalize the range of acceleration changes, reducing it to the interval [0, 1]. Figure17 shows the FV membership function for LV ar.Figure 17
FV membership functions for LVar: “linear acceleration”.In the same way, let us define the LVεr (“angular velocity”) and LV ωr (“angular acceleration”), setting the similar term sets T (εr) and T (ωr) with three FVs with the same meaning. Figure 18 shows the FV membership function for LV εr. Figure 19 shows the FV membership function for LV ωr. The base sets for determining FV for LV εr and FV for LV ωr are also normalized, i.e., reduced to the range of values [0, 1]. Rule bases of fuzzy classifiers M1 and M2 contain 9 rules of fuzzy output each. Surfaces of fuzzy output for these models are shown in Figures 20(a) and 20(b). Output variable of the model of assessment of the AMR’s dynamics is the one LV mr (“assessment of the AMR’s dynamics”).Figure 18
FV membership functions for LVεr: “angular velocity”.Figure 19
FV membership functions for LVωr: “angular acceleration”.Figure 20
(a) Fuzzy output surfaces for model М1 and (b) fuzzy output surfaces for model М2.
(a)
(b)This LV has the term setT (mr) = {<low>, <medium>, <high>}. The base set for assessment of the AMR’s dynamics is the interval of relative values from 0 to 1, where 1 is the maximum value of AMR’s mobility. Figure 21 shows the FV membership function for LV mr. Figure 22 shows the surface of fuzzy output of LV mr values, which illustrates the dependency of the degree of decision from the input parameters of the model.Figure 21
FV membership functions for LVmr: “AMR dynamics”.Figure 22
Fuzzy output surface for model M3.Fuzzy model proposed for assessment of the AMR’s size has three inputs and one output, as shown in Figure22. For LV “length,” experts determined the term set T (lr) = {<small>, <medium>, <great>}, which contains three fuzzy variables. The base set for determining FV LV “length” has the change range from lrmin to lrmax, which is reduced to the interval [0, 1]. Figure 23 shows the FV membership function for LV lr. The LVs hr (“height”) and и br (“width”) are defined in the same way. Membership functions of these variables are given in Figures 24(a) and 24(b). The output of the model of assessment of AMRs’ size is defined by LV Sizer with term set T (Sizer) = {<small>, <middle>, <large>}.Figure 23
FV membership functions for LVlr: “length”.Figure 24
(a) FV membership functions for LVhr: “height”; (b) FV membership functions for LV br: “width”.
(a)
(b)Figure25 shows the FV membership function for LV Sizer with base set of estimations from 0 to 1. The expert rule base for determining the values of the variable Sizer contains 27 rules. Fuzzy model of integral estimation of AMR’s maneuvering capabilities has two inputs (“assessment of dynamics” and “assessment of size”) and one output (linguistic variable “maneuvering capabilities”). For LV “maneuvering capabilities,” experts determined the term set T (msr) = {<weak>, <strong>, <excellent>}, which contains three fuzzy variables. The base set for defying FV LV “maneuvering capabilities” has the changing range from msrmin to msrmax, which is reduced to the interval [0, 1].Figure 25
FV membership functions for LVSizer.Figure26 shows the FV membership function for LV msr. The form of membership functions for variable dcom is shown in Figure 27. The rule base for output values of the variable “maneuvering capabilities” contains 9 rules. Figure 28 shows the fuzzy output surface for model M5.Figure 26
Fuzzy output surface for model M5.Figure 27
FV membership functions for LV “control range”.Figure 28
Fuzzy output surface for model M6.


## 3. Results and Discussion

The initial parameters of the fuzzy models used in the work were selected based on the preferences of the researchers and subsequently adjusted according to the results of experiments. The final parameters of fuzzy models, as well as the solution surfaces and modeling results obtained on their basis, are presented below.Experimental studies of the method of formation of quantitative indicators of complexity of the local region of the environment were conducted in several test scenarios. Let us consider each of them. As shown in Figure29, the group consists of three AMRs and five obstacles; positions of which are described in Table 1. The CVS was modeled by lidar with a distance matrix of 16 × 8, a viewing angle of 90° horizontally and 45° vertically, and a range of 20 m. Figure 30 illustrates the lidar scanning of the environment by the respective robots.Figure 29
Initial positions of the obstacles and the group of AMR: (a) 3D view; (b) plan view.
(a)
(b)Table 1
Obstacle coordinates.
No. of obstacles
y
p1
y
p3
y
p2
1
10
0
0
2
15
−4
0
3
15
4
0
4
15
0
4
5
15
0
−4Figure 30
Simulating the work of CVS: (а) 3D view of AMR no. 1; (b) plan view of AMR no. 1; (c) 3D view of AMR no. 2; (d) plan view of AMR no. 2; (e) 3D view of AMR no. 3; (f) plan view of AMR no. 3.
(a)
(b)
(c)
(d)
(e)
(f)The coordinates of the start and end moving points of AMR are given in Table2 and Table 3. Figure 31 presents the results of simulating the movement of a group of robots using fuzzy modes [23–26]. Figures 31(a) to 31(d) show the results of simulating the movement of a group of AMR when reaching the endpoint from different angles.Table 2
Starting point coordinates.
No. of the AMR
y
1
y
3
y
2
1 (center)
0
0
4
2 (left)
0
3.5
−2
3 (right)
0
−3.5
−2Table 3
Endpoint coordinates.
No. of the AMR
y
1
y
3
y
2
1 (center)
20
0
4
2 (left)
20
3.5
−2
3 (right)
20
−3.5
−2Figure 31
Case 1 simulation results. (a–d) Results of simulating the movement of a group of AMR when reaching the endpoint; (e) estimation of the complexity of the environment during movement.
(a)
(b)
(c)
(d)
(e)As we can see from Figure31, the environment looks most complex from the point of view of the AMR no. 1 (solid line), but its low value (less than 0.25) allowed all the robots to pass the group of obstacles as one formation, without collisions. The complexity estimations of AMR no. 2 and AMR no. 3 are somewhat similar because they have symmetrical positions in the group. Case 2: each robot in the group has its own complexity. The initial positions of the obstacles and the AMR group are shown in Figure 32.Figure 32
Initial positions of the obstacles and the group of AMR: (а) 3D view; (b) plan view.
(a)
(b)The coordinates of the start and end moving points of the AMR group are given in Table4 and Table 5. As we can see in Figure 32, the group of AMR needs to pass an obstacle that is presented as a wall of spheres with singular radius and blocks 50% of the movement zone. Case 3 simulation results are shown in Figure 33.Table 4
Starting point coordinates.
No. of the AMR
y
1
y
3
y
2
1 (center)
0
0
0
2 (left)
0
3
0
3 (right)
0
−3
0Table 5
Endpoint coordinates.
No. of the AMR
y
1
y
3
y
2
1 (center)
20
0
0
2 (left)
20
3
0
3 (right)
20
−3
0Figure 33
Simulating the work of CVS: (а) 3D view of AMR no. 1; (b) plan view of AMR no. 1; (c) 3D view of AMR no. 2; (d) plan view of AMR no. 2; (e) 3D view of AMR no. 3; (f) plan view of AMR no. 3.
(a)
(b)
(c)
(d)
(e)
(f)As we can see from Figure33, the different members of the AMR group have significantly different CVS views, which influence the process of motion and the assessment of the complexity of the environment. Figure 34 shows Case 2 stimulation results. In this case, the environment looks the most complex from the point of view of the robot no. 2 (dashed line), which was the reason for not achieving the endpoint on time. AMR no. 1 (solid line) assessed the complexity of the environment as rather complicated, but after left maneuvering indicators JYO1 and JYO2 began to decrease and the estimation changed to noncomplicated. The estimation of environment complexity by the AMR no. 3 (chain-dotted line) initially was the lowest one, and there was no need for motion correction during the simulation.Figure 34
Case 1 simulation results. (a–d) Results of simulating the movement of a group of AMR when reaching the endpoint; (e) estimation of the complexity of the environment during movement.
(a)
(b)
(c)
(d)
(e)


## 4. Conclusions

Conducted studies and experiments showed that the method of formation of estimations of local regions of the environment using the CVS data allows us to get an idea of how loaded they are with various objects, such as obstacles. Such data can be used for determining of optimal planning algorithm that meets the requirements of the current situation in terms of the cost of computing resources and the efficiency of the resulting trajectories [23–26]. If the considered local region has relatively small complexity, the planning task can be successfully solved based on such methods as virtual fields and fuzzy behavioral approach.If the complexity is high, alternative approaches should be used, for example, the method of unstable modes. Data about the complexity of the environment can also be used for defying some of its regions as insurmountable for a single robot or a group of robots. The reasons for this decision may be a violation of security requirements, inability to keep the group formation, or completion of the task on time. The method of formation of a complex assessment of AMRs’ characteristics allows obtaining quantitative estimations of their fitness for achieving the set objectives. These data are necessary for effective target distribution, reconfiguration of the group formation in case of changes in its structure, objective change, etc.



---

*Source: 6874291-2020-04-30.xml*