5.1. Collision region partition

At any time instant, $r_i$ ’s collision region $CR_i(t)$ is partitioned into $l$ equal sectors, that is, $l_i=\{(x,y)| 0\leq x\leq L\cos\!(\theta ), 0\leq y\leq L\sin\!(\theta ), (i-1)\pi/l\leq \theta \leq i\pi/l\}$ , $i=1,2,\ldots, l$ . Consequently, an appropriate value of $l$ should be selected. Considering that many real-world mobile robots are equipped with three groups of sensors in the front, such as [Reference Shen, Wang, Jiang, Ji, Wang and Huang34, Reference Liu, Yao, Zhang and Zhang35], in this paper, the collision region is equally partitioned into three sectors: the left region (LR), the front region (FR), and the right region (RR). The robots in LR are left intruders, those in FR are front intruders, and in RR are right intruders. For example, Fig. 3 shows the three sectors of $r_i$ , where each sector has a central angle of $\pi/3$ . $r_{i1}$ and $r_{i2}$ are in LR, $r_{i3}$ is in FR, and $r_{i4}$ and $r_{i5}$ are in RR. They are the intruders of $r_i$ at the current instant.

Figure 3.

Partition the collision region into three sectors and screen the most dangerous intruder in each sector.

5.2. VO-based intruder selection

To avoid the explosion of the number of fuzzy rules with the number of intruders, in this subsection, a VO-based method is proposed to select a proper intruder in each sector such that the generated rules with a finite number, independent of the number of robots.

The main idea of VO is to select a velocity of a robot outside the VO, which is the set of velocity that may cause collisions with other robots or obstacles. As shown in Fig. 4, suppose robot $r_i$ currently is at ${\textbf{p}}_i$ . It detects an intruder $r_{i1}$ in its collision region $CR_i$ , whose position and velocity are ${\textbf{p}}_{i1}$ and ${\textbf{v}}_{i1}$ , respectively. So $r_i$ should select a velocity ${\textbf{v}}_i$ to avoid collision with $r_{i1}$ . At the current time instant, $r_i$ ’s collision region with respect to $r_{i1}$ can be described as $C_{i|i1}=\{{\textbf{p}}(i) \in \mathbb{R}^2 | \|{\textbf{p}}(i)-{\textbf{p}}_{i1}\|_2\lt 2\rho \}$ , that is, the region within the dashed circle in Fig. 4. The relative velocity of $r_i$ with respect to $r_{i1}$ can be described as ${\textbf{v}}_{i|i1}={\textbf{v}}_i-{\textbf{v}}_{i1}$ . The relative motion can be defined as $\lambda ({\textbf{p}}_i,{\textbf{v}}_{i|i1}) = \{{\textbf{p}}_i + t{\textbf{v}}_{i|i1} |t \gt 0\}$ , that is, the blue ray in Fig. 4. Clearly, $r_i$ and $r_{i1}$ will collide in the future if $\lambda ({\textbf{p}}_i,{\textbf{v}}_{i|i1})\cap C_{i|i1}\neq \emptyset$ . Hence, the VO of $r_i$ related to $r_{i1}$ is defined as $VO_{i|i1}=\{{\textbf{v}}_i|\lambda ({\textbf{p}}_i,{\textbf{v}}_{i|i1})\cap C_{i|i1}\neq \emptyset \}$ , that is, the gray cone in Fig. 4.

Figure 4.

Illustration of VO. $VO_{i|i1}$ is the velocity obstacle of $r_i$ . Each velocity in $VO_{i|i1}$ will cause a collision with $r_{i1}$ in some time instant of the future.

Based on VO, a method is proposed to select the most dangerous intruder in each section according to the collision risk, which is defined as the potential collision time. Furthermore, the collision time criterion is defined to evaluate the collision risk.

In detail, the computation of potential collision time is as follows. Consider the relative motion of $r_i$ with respect to $r_j$ . As shown in Fig. 5, for the relative motion, $r_j$ is with zero velocity, and $r_i$ has a relative velocity ${\textbf{v}}_i(t)-{\textbf{v}}_j(t)$ . Clearly, the minimum distance is reached at the time when the relative motion reaches position $A$ . The distance from ${\textbf{p}}_i$ to $A$ is

(2) \begin{equation} d({\textbf{p}}_i,A)=\frac{({\textbf{p}}_j(t)-{\textbf{p}}_i(t))^T({\textbf{v}}_i(t)-{\textbf{v}}_j(t))}{\|{\textbf{v}}_i(t)-{\textbf{v}}_j(t)\|_2} \end{equation}

Figure 5.

The relative motion of $r_i$ with respect to $r_j$ .

Hence, the estimated time from ${\textbf{p}}_i$ to $A$ is $\dfrac{d({\textbf{p}}_i,A)}{\|{\textbf{v}}_i(t)-{\textbf{v}}_j(t)\|_2}$ , that is,

(3) \begin{equation} \Delta T_i(j) = \frac{({\textbf{p}}_j(t)-{\textbf{p}}_i(t))^T({\textbf{v}}_i(t)-{\textbf{v}}_j(t))}{\|{\textbf{v}}_i(t)-{\textbf{v}}_j(t)\|_2^2}. \end{equation}

Based on the procedure of VO, if ${\textbf{v}}_i\in VO_{i|j}$ , $d_i(j)\lt 2\rho$ , and vice versa. In this case, a collision between $r_i$ and $r_j$ happens when the relative motion arrives at position $B$ , as shown in Fig. 5. Hence, $\Delta T_i^c(j)$ can be computed as follows:

(4) \begin{eqnarray} \Delta T_i^c(j) &=& \Delta T_i(j) - t(B,A)\nonumber \\[5pt] &=&\Delta T_i(j) - \frac{\sqrt{4\rho ^2-d_i^2(j)}}{\|{\textbf{v}}_i(t)-{\textbf{v}}_j(t)\|_2}. \end{eqnarray}

Clearly, the smaller $\Delta T_i^c(j)$ is, the more dangerous $r_j$ is, and the higher priority it has for collision avoidance. According to the estimated collision time, the most dangerous intruder is selected in each sector, that is, the intruder with the smallest $\Delta T_i^c(j)$ in each sector. For example, as shown in Fig. 3, the selected intruder in LR is $r_{i2}$ as it has smaller collision time than $r_{i1}$ .

6.1. Introduction of fuzzy rules

This subsection first gives a brief introduction of fuzzy rules, and the details can be found in ref. [Reference Ding, Zhou and Zhou36]. Let $U$ be the domain of discourse and $u\in U$ . A fuzzy set $\phi$ in $U$ is characterized by a real-value function $\mu _{\phi }\;:\; U \to [0,1]$ , which assigns each element in $U$ with a real number in the interval $[0, 1]$ .

A single fuzzy IF-THEN rule (or simply fuzzy rule) is defined on linguistic variables with the form:

\begin{equation*} {\textbf{IF }} x \text { is } A \text { (premise}) {\textbf{ THEN }} y \text { is } B \text { (consequence}) \end{equation*}

where $x$ and $y$ are two fuzzy $/$ linguistic variables. A and B are two fuzzy sets. A more general type of fuzzy rules in practice can be described as:

\begin{equation*} {\textbf {IF }} x_1 \text { is } A_1 \wedge \cdots \wedge x_p \text { is } A_p {\textbf { THEN }} y_1 \text { is } B_1 \wedge \cdots \wedge y_q \text { is } B_q, \end{equation*}

where $p\geq 1$ and $q\geq 1$ are integers.

6.2. Fuzzy rule generation

On one hand, according to the selection of intruders, the input of a fuzzy rule is the collision time $\Delta T^c$ of the selected intruders. On the other hand, since the kinematic model of each robot considered in this paper is unicycle kinematics, the output variables of fuzzy rules are set as the speed ratio $\alpha$ and the orientation change $\Delta \theta$ . The new speed is $v'_{\!\!c} = \alpha v_c$ , which adjusts the current speed $v_c$ according to a proper ratio $\alpha$ . Note that, to guarantee mutual exclusion during distributed decision making and avoid collisions, each robot is expected to turn right with a proper direction, so $\Delta \theta \in [0,\pi/2]$ , and the new orientation is $\theta _i-\Delta \theta$ , where $\theta _i$ is the current orientation of $r_i$ . Then, the selected velocity is ${\textbf{v}}'_{\!\!i}=(v'_{\!\!c}\cos\!(\theta _i-\Delta \theta ), v'_{\!\!c}\sin\!(\theta _i-\Delta \theta ))$ . Note that the outputs of fuzzy rules are determined by the robot kinematics described in (1), rather than robot dynamics, such as inertia.

In the sequel, the generation of fuzzy rules is described, that is, fuzzification, data sampling, and rule determination.

6.2.1. Fuzzification

The main task of fuzzification is to translate crisp variables into the corresponding linguistic ones. Hence, for each crisp variable $x$ , the set of fuzzy terms and their corresponding membership functions should be determined. Users can select any membership function as long as it can map the crisp data into desired degree of memberships. In this paper, the triangular membership function is applied for each fuzzy set as (1) it has been proven to have good quality results and computational efficiency in many practical applications (including robot motion control) [Reference Kreinovich, Kosheleva and Shahbazova37, Reference Ping and Yu38] and (2) it shows good performance in our simulation experiments.

First, consider the fuzzification process of the input variable $\Delta T^c$ . Usually, a robot needs a time duration, say response time, to perform collision avoidance, including collision prediction and decision execution. Based on the configurations of a robot and its history motion records, the minimal and maximal response time of the robots can be determined, denoted as $t_1$ and $t_2$ , respectively. If $\Delta T^c$ is less than $t_1$ , then the situation is very emergent, and the robot needs to perform some special actions, for example, stop immediately, to avoid collisions. Otherwise, if $\Delta T^c$ is small, meaning that the remaining time to take collision avoidance actions is short, then this situation is dangerous, and the robot needs to do its best to avoid collisions; while if $\Delta T^c$ is large, meaning that the robot has enough time to avoid collisions, then the current motion is safe. Hence, three fuzzy sets, that is, $E$ (emergent), $D$ (dangerous), and $S$ (safe), are defined to describe $\Delta T^c$ . Their membership functions are shown in Fig. 6(a). Moreover, the formal definitions of all membership functions are given in the appendix.

Figure 6.

Membership functions for all variables. (a) Membership function of $\Delta T^c$ ; (b) membership function of $\alpha$ ; (c) membership function of $\Delta \theta$ .

Second, consider the fuzzification of the output variables. (1) The speed variable is partitioned into four fuzzy sets: $MA$ (maintain), $DS$ (decelerate slightly), $DL$ (decelerate largely), and $SU$ (stop urgently). Since the level of speed deceleration is related to the current speed, the ratio of the new speed ( $v'_{\!\!c}$ ) to the current speed ( $v_c$ ), denoted as $\alpha$ , is the inputs of the three membership functions. Note that $0\leq \alpha \leq 1$ . The graphical representation of these membership functions is given in Fig. 6(b), where $\alpha _0$ is the threshold of a maintaining action and can be determined by an expert or based on users’ requirements. (2) For the change of orientation, five fuzzy sets are applied to describe its values: $VS$ (very small), $SM$ (small), $M$ (medium), $L$ (large), and $VL$ (very large). Their membership functions are shown in Fig. 6(c). Note that one can define more fuzzy sets for speed and orientation change if needed.

6.2.2. Building of fuzzy rules

As described before, to avoid an exponential increase in the number of fuzzy rules, a robot selects at most one intruder in each sector to perform collision avoidance. Hence, the premise of a rule contains at most three fuzzy propositions, each of which has four possible forms, including the empty situation. So there are $4^3-1=63$ possible premises. The consequence of a rule contains at most two independent fuzzy propositions, and they have four and five possible forms, respectively. Hence, the number of candidate rules is 63^*(4 + 5) = 567. However, proper rules should be selected from the candidates. For each premise, the next step is to determine the consequences related to the two output linguistic variables, respectively. The rule selection is based on supporting degrees described in ref. [Reference Ding, Zhou, Pu and Zhou39]. For each premise, the supporting degrees of all candidate rules are computed, and only the rule with the maximal one is selected. Note that rules whose supporting degrees are zero are also filtered.

Based on the partition of the collision region and intruder selection, there are three kinds of scenarios during the generation of fuzzy rules. The first one is that there is only one sector existing a selected intruder, as shown in Fig. 7. For each one shown in Fig. 7, the sampling data are generated from multiple simulation runs by setting different status of the intruder. For each run, the ORCA algorithm is performed to generate the cooperative motion data between $r_i$ and the intruder. For example, suppose at time instant $t$ , the robot $r_i$ , with the state $({\textbf{p}}_i(t),{\textbf{v}}_i(t))$ , detects an intruder $r_{i1}$ , whose state is $({\textbf{p}}_{i1}(t),{\textbf{v}}_{i1}(t))$ , in LR, and the ORCA method generates a new velocity ${\textbf{v}}_{i,\text{ORCA}}(t)$ for $r_i$ . Let $\theta _{{\textbf{v}}_i}(t)$ and $\theta _{{\textbf{v}}_{i,\text{ORCA}}}(t)$ denote the orientation angle of ${\textbf{v}}_i(t)$ and ${\textbf{v}}_{i,\text{ORCA}}(t)$ in the inertial frame $XOY$ . When $\theta _{{\textbf{v}}_{i,\text{ORCA}}}(t) \leq \theta _{{\textbf{v}}_i}(t)$ and $\|{\textbf{v}}_{i,\text{ORCA}}(t)\|_2 \leq \|{\textbf{v}}_i(t)\|_2$ , a sample $(L_{\Delta T^c}, \Delta T_i(i1), \alpha _i(t), \Delta \theta _i(t))$ is collected, where $\Delta T_i(i1)$ is computed based on (4), while $\alpha _i(t)$ and $\Delta \theta _i(t)$ are computed based on the following equations.

(5) \begin{align} \alpha _i(t) = \frac{\|{\textbf{v}}_{i,\text{ORCA}}(t)\|_2}{\|{\textbf{v}}_i(t)\|_2}, \end{align}

(6) \begin{align} \Delta \theta _i(t) = \theta _{{\textbf{v}}_i}(t) - \theta _{{\textbf{v}}_{i,\text{ORCA}}}(t) \end{align}

Figure 7.

Scenarios that there is only one thread in a sector.

In this way, a total of 1664 valid records are generated from the first kind of scenarios. With all the records, six rules are generated, whose details are given in the appendix and the website https://fuzzyvo.github.io/. Note that the original rules are in the form with single-input–single-output, such as “IF $L_{\Delta T^c}$ is $D$ , THEN $v_c$ is $DS$ ”. However, the rules with the same premise can be combined, for example, for the rules “IF $L_{\Delta T^c}$ is $D$ , THEN $v_c$ is $DS$ ” and “IF $L_{\Delta T^c}$ is $D$ , THEN $v_c$ is $L$ ”, they can be combined as one “IF $L_{\Delta T^c}$ is $D$ , THEN $v_c$ is $DS$ and $\Delta \theta$ is $L$ ”.

The second kind of scenarios is that there exist two sectors such that either of them contains an intruder, as shown in Fig. 8(a)–(c). Similarly, 29,347 samples are collected in this kind of scenarios, and 12 fuzzy rules are generated, which are given in the appendix. The third one is that each sector contains a selected intruder, as shown in Fig. 8(d). To generate proper rules for this kind of scenarios, a total of 5299 records are collected to train rules.

Figure 8.

Scenarios with multiple intruders.

When the collision time related to the intruder in a sector is emergent, the robot should stop urgently. Hence, three emergent rules are also introduced, which are also given in the appendix. Finally, a rule base containing 29 fuzzy rules is built. All generated fuzzy rules are listed in the appendix.

6.3. Velocity generation via fuzzy inference

When the rule base is built, the velocities can be generated directly via fuzzy inference. In this paper, the Mamdani (min) inference mechanism is applied, whose output is a fuzzy set [Reference Figueiredo, Gomide, Rocha and Yager40]. The mechanism can be described as follows. Given an input $x^0=(x_1^0,\ldots,x_p^0)$ and the activated fuzzy rule “ $rule_1\;:\; \textbf{IF } x_1 \text{ is } A_1 \wedge \cdots \wedge x_p \text{ is } A_p \textbf{ THEN } y \text{ is } B$ ,” the inferential fuzzy set for the consequence is computed based on (7).

(7) \begin{eqnarray} inf(x^0, rule_1) &=&{A_1(x_1^0)} \wedge \ldots \wedge{A_p(x_p^0)} \nonumber \\[5pt] B(y, x^0, rule_1) &=& inf(rule_1) \wedge B(y) \end{eqnarray}

where ${A_1(x_1^0)} \wedge \ldots \wedge{A_p(x_p^0)}=\min \{{A_1(x_1^0)},\ldots,{A_p(x_p^0)}\}$ . For the activation of multiple rules, the final inferential fuzzy set is determined based on (8).

(8) \begin{eqnarray} B(y,x^0)&=&B(y,x^0,rule_{i1})\vee \ldots \vee B(y,x^0, rule_{ij})\nonumber \\[5pt] &=&\max \{B(y,x^0, rule_{i1}), \ldots, B(y,x^0, rule_{ij})\} \end{eqnarray}

Since $B(y,x^0)$ is a fuzzy set, defuzzification is required to generate a crisp value of the velocity for the robot. One of the common defuzzification methods is the center of gravity, which determines a crisp value based on the center of gravity of the generated fuzzy set [Reference Jiang and Li41]. The computation of the center of gravity is given in (9).

(9) \begin{equation} y^*=\frac{\int yB(y,x^0)dy}{\int B(y,x^0)dy} \end{equation}

Based on the above procedure, given the current states of a robot and its intruders, the collision times related to different intruders are first computed and the most dangerous intruder in each sector is selected. Then, a new velocity is generated via the following fuzzy inference process: (1) decide all possible premises, that is, all combinations of the fuzzy sets of the selected intruders’ collision time; (2) for each premise, activate the corresponding rule and return a fuzzy set based on (7); (3) compute the final fuzzy set based on (8); and (4) compute the speed ratio $\alpha ^*$ and the orientation change $\Delta \theta ^*$ based on (9). Hence, the new velocity can be described as

(10) \begin{align}{\textbf{v}}_i^g=[\alpha ^*v_c\cos\!(\theta -\Delta \theta ^*),\alpha ^*v_c\sin\!(\theta -\Delta \theta ^*)]^T \end{align}

Using the above three steps, a candidate velocity can be generated for each robot for collision avoidance.

6.4. Velocity fine-tuning

Since fuzzy inference is a learning-based method depending on the quality of the sampling data, the generated velocity may still result in a collision. Hence, fine-tuning is required to get a collision-free velocity.

In case the generated velocity for $r_i$ is still in the VO region of some selected intruders, the velocity should be adjusted such that it is out of the VO region. Indeed, any VO-based method can be applied, such as ORCA, to compute the current velocity. However, considering the computation cost, a heuristic fine-tuning method is proposed. As shown in Fig. 9, ${\textbf{v}}_i^g$ is the velocity obtained by fuzzy inference, BL and BR are the boundaries of the VO region. There are two situations based on the robot’s current position. The first one is shown in Fig. 9(a), where the current position ${\textbf{p}}_i$ is out of the VO $VO_{i|i1}$ . In this case, the solution is to decrease the generated speed $\|{\textbf{v}}_i^g\|_2$ to the boundary of VO (i.e., point $a$ in Fig. 9(a)) without changing the orientation of the velocity. The second one is shown in Fig. 9(b), where the current position ${\textbf{p}}_i$ is in the VO $VO_{i|i1}$ . In this case, the main idea is to increase the speed and $/$ or change the orientation of ${\textbf{v}}_i^g$ . However, since the built fuzzy rules prefer to decrease the speed to avoid collisions, the generated speed may be too small to guarantee collision avoidance by only changing the orientation. Hence, for this situation, the speed will be increased to the boundary (i.e., point $a$ in Fig. 9(b)).

Figure 9.

Illustration of velocity refinement. ${\textbf{v}}_i^g$ is obtained from fuzzy inference, ${\textbf{v}}_i^f$ is refined velocity. (a) ${\textbf{p}}_i$ is out of $VO_{i|i1}$ . (b) ${\textbf{p}}_i$ is in $VO_{i|i1}$ .

8.1. Multiple robots moving in the same environment

To evaluate the effectiveness of Fuzzy-VO, the first simulation experiment is conducted with 4 AscTec Firefly UAVs, denoted as $r_1$ − $r_4$ . Their initial positions are $(0, 20)$ , $(0, 0)$ , $(20, 0)$ , and $(20,20)$ , respectively. They need to move to $(20, 0)$ , $(20, 20)$ , $(0, 20)$ , and $(0, 0)$ , respectively.

Figure 11 shows some snapshots of the motion of the four UAVs at different time instants. As shown in Fig. 11(a), from the start time to the time instant $k = 342$ (i.e., $t=3.42$ s), each UAV detects that there are no intruders within its sensing range, so they move directly to their targets. When the time instant is $k = 428$ , $r_3$ arrives at $(14.135, 5.923)$ with a speed of $v_3 = 2$ units/s and an orientation $\theta _1 = 135.121^\circ$ . At this time, it detects that there are two intruders in its sensing range, namely, $r_2$ and $r_4$ , whose positions are $(6.218, 6.331)$ and $(13.808, 13.748)$ , respectively. With intruder selection, $r_3$ finds that $r_2$ is in its RR, while $r_4$ is in its LR. Thus, $r_3$ activates rules $15-18$ to generate the motion command. The motion command generated by Fuzzy-VO for $r_3$ at this time is: $\alpha = 0.285$ , $\Delta \theta = 43.423^\circ$ . Hence, as shown in Fig. 11(b) and (c), $r_3$ changes its motion to right from $k = 428$ to $k = 449$ . Similarly, during the motion from $k=449$ to $k=474$ , $r_2$ , $r_1$ , and $r_4$ detect intruders in their sensing ranges sequentially, so they turn a little bit to right to avoid collisions, as shown in Fig. 11(d). At $k = 474$ ( $t=4.74$ s), $r_4$ is at $(12.787, 12.756)$ and detects $r_1$ , $r_2$ , and $r_3$ , whose positions are $(7.141, 12.635)$ , $(7.201, 7.049)$ , and $(13.546, 6.924)$ , respectively, are in its sensing range, so there are three intruders need to address for $r_4$ . Clearly, $r_1$ is in RR, $r_2$ is in FR, and $r_3$ is in LR. Since there is one intruder in each sector, rules $19-26$ are activated. The generated command is: $\alpha = 0.267$ , $\Delta \theta = 82.5^\circ$ . Hence, $r_4$ should turn greatly to right and slow down its speed, as shown by the paths in Fig. 11(e). At $t = 5.87$ s, $r_2$ detects $r_3$ is in its FR, so rules 3 and 4 are activated to generate command ( $\Delta \theta = 23.279^\circ$ ) for $r_2$ , which brings $r_2$ to turn right. After $t = 5.87$ s, $r_4$ does not detect any intruder in its sensing range, so $r_4$ only needs to move towards the target position. Such motion of them can be found in Fig. 11(f). When $k=667$ , that is, $t = 6.67$ s, the orientation of the four UAVs are −41.618 $^\circ$ , 48.85 $^\circ$ , 140.068 $^\circ$ , and −129.561 $^\circ$ , respectively. For $r_3$ and $r_4$ , the initial orientation is 135 $^\circ$ and −135 $^\circ$ , respectively. Based on the motion shown in Fig. 11(f) and (g), from $t = 6.67$ s to $t = 7.50$ s, each robot turns a little bit to right first to avoid collisions with other robots. When there are no intrudes in its sensing range, each robot turns to left to move directly to its target.

Figure 11.

Detailed simulation process of collision avoidance for four UAVs.

As time elapses, the system reaches Fig. 11(g) at $t = 7.50$ s. From now on, even through there are others UAVs within their sensing ranges, the four UAVs detect that there are no collisions in the future, and all potential collisions are resolved. Hence, each UAV moves directly to its target again. As shown in Fig. 11(h), all robots reach their targets at $t = 14.74$ s. From their traversed trajectories, an observation is that in order to pass the intersection without any collision, each robot moves to its right side to avoid collisions. From their traversed trajectories, it is can be seen that in order to pass the intersection without any collision, each robot moves to its right side to avoid collisions. As in the ground traffic system, such motion of these robots is similar to the motion within a roundabout [Reference Zhou, Hu, Liu, Lin and Ding16].

Furthermore, more simulations are also conducted with 3, 4, 6, and 8 UAVs, respectively. All videos of simulations can be found at https://fuzzyvo.github.io/. It can be seen that Fuzzy-VO can serve as an effective and universal collision avoidance method, for multirobot systems with different numbers of robots, by leveraging the advantages of fuzzy rules and VOs.

8.2. Comparison of Fuzzy-VO with other fuzzy rule-based methods

Since our method improves fuzzy rule-based methods, which can deal with uncertainties and linguistic variables, we compare Fuzzy-VO with the pure fuzzy rule method on the number of rules and the smoothness of the generated paths. In addition, more experiments are also conducted to compare the performance of the proposed intruder selection method with other selection methods.

8.2.1. Comparison with pure fuzzy rule method

Let us first consider the number of rules. For the pure fuzzy control method, at any time instant, a robot evaluates the risks related to all other robots and then determines its motion. Hence, the rules are generated directly based on the number of robots in a system. Indeed, in this method, the number of rules increases exponentially with the number of robots in the system. Suppose the risk related to each robot is described by two fuzzy sets: dangerous and safe, and the orientation is described by three fuzzy sets: left, front, and right. If there are $M$ robots in a system, the possible rules are $6^{M-1}$ . For example, as shown in Fig. 12(a), when there are three, four, and five robots, respectively, the required numbers of rules is 36, 261, and 1296, respectively. However, in Fuzzy-VO, by intruder selection, the number of rules is fixed and does not change when the number of robots is larger than 3. As shown in Fig. 12(a), when there are two robots in the system, there is one obstacle to be processed, so only six rules required for both Fuzzy-VO and pure fuzzy rule control. There are 18 rules when the system contains three robots. When $M\geq 4$ , the number of rules in Fuzzy-VO is always 26 (without considering the emergent situation described before), which is independent of the number of robots. The result indicates that Fuzzy-VO decreases the number of fuzzy rules significantly by selecting a proper and fixed number of intruders.

Figure 12.

The number of rules and the generated paths of Fuzzy-VO and pure fuzzy rule method. The dotted lines indicate the paths of the dynamic obstacles.

Let us further compare the paths generated by the two methods. Consider the situation that there are three dynamic obstacles ( $r_1 - r_3$ ) and a Test Robot. The Test Robot is placed to $(20, 0)$ with an initial speed is 2 units/s, and its target position is $(20, 40)$ . The three obstacles’ initial positions are $(15, 40)$ , $(18, 40)$ , and $(25, 40)$ , respectively; their missions are that $r_1 - r_3$ need to move directly to $(25, 0)$ , $(21, 0)$ , and $(15, 0)$ , respectively, with a fixed speed 2 units/s. Figure 12(b) shows the paths that the robots traversed. The solid lines represent the paths of the Test Robot. From the paths, an observation is that the path generated by Fuzzy-VO is smoother. Indeed, in pure fuzzy rule method, due to the excessive considering of the larger number of fuzzy rules, some unnecessary rules are activated to generate motion sometimes, which make the generated path oscillating. The result validates that the path of a robot may be oscillating when there are a large number of rules. Since it generates a proper number of rules, Fuzzy-VO can produce smoother paths.

8.2.2. Performance comparison of different selection methods

The common metrics to assess collision risks in a dynamic environment include: distance to collision (DTC), time to collision (TTC), and time to react (TTR) [Reference Katrakazas, Quddus, Chen and Deka43]. As mentioned before, this paper focuses on TTC, that is, potential collision time in Fuzzy-VO, to select the most dangerous intruder in each sector. In some scenarios, a robot can only determine the nearest obstacle considered in each region using its onboard sensor information directly, such as that of ultrasonic sensors and laser sensors. Thus, the collision risk in evaluated based on DTC, such as [Reference Wen, Zhou and Wang21]. For a deeper exploration of Fuzzy-VO, the performance comparison between the two methods is studied. The systems are initialized with 3, 4, 5, 6, 8, and 10 robots, respectively, using Monte Carlo simulation. For each system, 10,000 experiments are performed. In each experiment, the initial and target positions for each robot are randomly assigned. Then, Fuzzy-VO and the DTC-based method (the configurations of fuzzy sets, membership functions, and fuzzy rules are the same as [Reference Wen, Zhou and Wang21]) are run independently. The comparison metrics are as follows.

1. 1. Success rate. It is defined as the ratio of the number of experiments in which each robot arrives at its target position successfully while maintaining a safe distance with other robots at any time instant.

2. 2. Minimum separation. It is defined as the minimum distance between any two robots during their motion in each collision-free experiments.

3. 3. Trajectory length. It is defined as the path length of a robot. Due to different initial and target positions, the trajectory length is normalized by the distance between each pair of initial and target positions. Hence, trajectory length can be computed as follows.

   (11) \begin{eqnarray} L_{tr}(i) = \frac{\sum _{k} \|{\textbf{p}}_i(k+1)-{\textbf{p}}_i(k)\|_2 }{\|{\textbf{p}}_i^o-{\textbf{p}}_i^f\|_2} \end{eqnarray}

4. 4. Motion time. It is defined as the discrete steps performed from the initial position to the target position of a robot.

For each system, the mean of each metric and the comparison results are shown in Fig. 13. As shown in Fig. 13(a), with the increase of robots, DTC-based selection cannot be applied anymore since most of the experiments are in collisions, while Fuzzy-VO is still with a low collision rate. In addition, from the average statistics aspect, compared to the DTC-based selection, the average success rate of Fuzzy-VOs can be increased by 306.5%. Note that the reasons for the happening of collisions in Fuzzy-VO are that: (1) since the initial and target positions are generated randomly, they may be in collisions when they are spawned; (2) currently, there are only two fuzzy sets associated to the collision time in Fuzzy-VO, so a robot in some situations may not be able to respond to collisions timely; it can be addressed by refining the collision time with more fuzzy sets; however, the more fuzzy sets, the more fuzzy rules; further study on how to balance the number of fuzzy sets and motion performance is one of future directions. Figure 13(b) shows that Fuzzy-VO can deal with collisions more precisely since it generates lower minimum separation in the context of collision avoidance. Figure 13(c) and (d) show that Fuzzy-VO can generate lower trajectory length and shorter motion time to complete the motion tasks.

Figure 13.

Comparison of motion performance between Fuzzy-VO and DTC-based method.

Additionally, the variances of minimum separation, trajectory length, and steps are shown as in Table II. It can be found that in all experiments, Fuzzy-VO can generate a smaller variance than fuzzy rules with DTC. Hence, it can be concluded that the proposed intruder selection method can assess the collision risk accurately and guarantee a higher success rate.

Table II.

Comparison of the variances of minimum separation, trajectory length, and steps.

8.3. Comparison of Fuzzy-VO with ORCA

At last, the comparison between Fuzzy-VO and ORCA [Reference van den Berg, Guy, Lin and Manocha14] is carried out. It aims to investigate the real-time decision efficiency of Fuzzy-VO. The experiments on six systems are conducted with different robots, that is, 3, 4, 5, 6, 8, and 10 robots, respectively. For each system, running Fuzzy-VO and ORCA 10,000 times, respectively. Figure 14(a) shows different methods’ average success rates under the control of the two methods. It can be observed that even though the success rate decreases as the number of robots vary from 3 to 10, Fuzzy-VO can remain a high success rate. Note that in Fuzzy-VO, it is a trade-off between the number of selected intruders and the collision avoidance performance. If the number of selected intruders is too large, the computation cost will increase, and the smoothness of generated trajectory will decrease. If the selected intruders are too few, the generated velocities may cause collisions. Hence, sometimes, users need to determine an appropriate number of collision regions.

Figure 14.

Comparison of avoidance performance between Fuzzy-VO and ORCA.

To further compare the real-time performance, the average one-step decision time (average time consumed for generating one candidate velocity) of the two methods is calculated. The results are shown in Fig. 14(b). From the results, it can be found that Fuzzy-VO has a shorter average decision time at each time step. With the increase of the number of robots, Fuzzy-VO can filter more nonurgent robots and has a less average one-step decision time for each robot. But the decision time of ORCA method increases with the number of robots in a system, as ORCA makes decision by resolving an optimization problem considering all other robots. The average one-step decision time of Fuzzy-VO is reduced by 740.9%, compared with the ORCA. This comparison results also further validate that Fuzzy-VO can improve the real-time decision efficiency without losing much success rate.