A laser-based multi-robot collision avoidance approach in unknown environments

Abstract

As a fundamental problem, collision avoidance for multiple robots still need further investigation, especially for many robots aggregating in a tight space. In this article, a laser-based collision avoidance approach is proposed in complex multi-robot environments. The laser data is analyzed and processed in terms of distance thresholding, safe passageway analysis, obstacles repulsion, goal position attraction, and inter-robot safety. Specifically, the safe passageway analysis is used to remove unsafe directions effectively, and inter-robot safety processing reduces the possibility of being selected for the directions affected by the neighboring robots. On this basis, an optimized decision is made to guarantee that the robots achieve collision-free motions even in crowded environments. The validity of the proposed approach is verified by simulations.

Keywords

Laser-based collision avoidance inter-robot safety multiple robots unknown environments

Introduction

The multi-robot system is attracting more and more attentions with advantages that are beyond the scope of a single-robot system.¹ It possesses the characteristics of parallelism, robustness, and flexibility with a wide variety of applications such as autonomous warehouse,^2,3 military, aerospace, and search and rescue. Existing researches focus on the problems including tasks and resource distribution, sensing, conflict resolution, formation, coordinated planning, and so on. As a fundamental problem, motion-level conflict resolution requires that the robots avoid collisions not only with static obstacles but also with other robots. If a robot regards its neighboring robots as static obstacles, the conflict among the robots is inevitable in some cases. It becomes worse in crowded multi-robot environments.

Commonly used sensors for environmental perception include infrared sensor, ultrasonic sensor,⁴ visual sensor,⁵ laser range finder,⁶ and so on. Infrared sensor is often used to identify closer obstacles for emergency due to its short detection range. Ultrasonic sensor is more popular in robot applications; however, it is susceptible to interference from reflection and noise, which leads to a poor accuracy. Visual sensor can provide the robot with more abundant environmental information—especially binocular vision can directly solve the depth information of the objects in the scene. However, it is susceptible to environmental illumination variation. Also, the distance errors to obstacles are a little larger. In recent years, laser sensor has been widely used with its tolerance to illumination variation.^6
–8 More importantly, it can directly measure the distances with high accuracy and fast scanning speed.

On the basis of environment information provided by on-board sensors, many researchers devote themselves to collision avoidance methods. Ayoade et al. proposed a real-time laser-based gap finding obstacle avoidance approach, and this approach computes a trajectory toward a gap that is wide enough and is closest to the path preplanned by the global planner.⁷ Yuan et al. presented a collision-free motion method for a mobile robot based on subregion evaluation in local sensing environment, and the optimal subregion will be used for decision with better adaptability to the environment.⁸ Zhou and Li proposed an adaptive artificial potential field method for planning.⁹ The sizes of the robot and the obstacles are considered into the potential field function, and the weight of this function can be changed to adapt to the environment. Hernández et al. provided a strategy based on distance clustering analysis for robot navigation, where the objects are detected by using the density-based spatial clustering of applications with noise method.¹⁰

The above methods can handle the static obstacles effectively; however, in multi-robot environments, they do not always work well due to the interference from other moving robots. To solve this problem, some researches have been conducted. Kato et al. applied traffic rules to coordinate the robots for safety movements.¹¹ Many common rules such as keep right, safety space ahead, and no-passing have been constructed. Sometimes, it is hard for a robot to determine a rule suitable for current situation due to the limitation of the robot’s cognition capability. Liu et al.¹² and Yan and Zhang¹³ combined rules with priority to achieve a conflict resolution among the robots. In practice, the application of priority has its limitation. For example, a robot needs to know the corresponding priority of its each neighboring robot by communication, which may complicate the decision-making. Zhang et al. conducted the collision avoidance with moving obstacles by employing the degree of risk and fuzzy function method.¹⁴ Liu et al. adopted the behavior-based approach to multi-robot formation navigation.¹⁵ Four primitive behaviors are presented: move_to_goal, keep_formation, avoid_static_obst-acle, and avoid_robot behaviors, and the parameters to synthesize these behaviors are determined by the particle swarm optimization algorithm. It shall be noted that the avoid_robot behavior requires the robot to turn right with a fixed value π/4 for collision avoidance among the robots, which is usually applied to small-scale multi-robot system. Zhang et al.¹⁶ proposed an obstacle forbidden zone-based motion planning approach for multiple robots in unknown environments. The recurrence least square algorithm with restricted scale is used to anticipate the motions of other robots that have higher priorities for the dynamic predictive obstacle forbidden zone, which is beneficial to collision avoidance among robots. In addition, a collision avoidance algorithm based on Bluetooth received signal strength indication is proposed for multi-robot systems in an indoor environment.¹⁷ Nevertheless, the Bluetooth signal is attenuated during propagation with a poor measurement accuracy. Based on existing outcomes, collision avoidance among multiple robots deserves further discussion, especially for crowded environments.

In this article, a laser-based collision avoidance approach for multiple robots is proposed for a complex multi-robot environment. Firstly, the safe passageway analysis is designed to remove unsafe directions effectively. Secondly, inter-robot safety processing is presented to reduce the possibility of being selected for the directions affected by the neighboring robots. This approach can improve the collision avoidance ability, especially for many robots aggregating in a small space.

The rest of this article is organized as follows. The “Laser-based collision avoidance” section describes the laser-based collision avoidance approach in detail. The “Simulations” section presents the simulation results. Finally, the article is concluded.

Laser-based collision avoidance

In this article, the original data are provided by a laser sensor. We label the maximum detection distance of the laser sensor as d _L, and the detection angle range is within (−π, π]. l_i (i = 1,2,…, N) are labeled as the data obtained from the laser sensor, where N is the number of laser data. A two-tuple T_i = (l_i , θ_i ) is defined, where θ_i = −π + i × 2π/N refers to the direction corresponding to the distance l_i . It is noted that θ_i = 0 corresponds to the current direction of the robot. Let all T_i constitute a set W = {T_i |i = 1,2,…, N}. Then, the data set W is analyzed and processed in sequence from the following five aspects: distance thresholding, safe passageway analysis, obstacles repulsion, goal position attraction, and inter-robot safety processing. Finally, an optimal motion direction θ* can be determined to adapt to the current environment, which can guide the robot to move toward the goal position without collisions with obstacles and other robots.

The block diagram of multi-robot collision avoidance approach is shown in Figure 1, where W_t , W_s , W_d , W_g , and W_f are the results of data sets after distance thresholding, safe passageway analysis, obstacles repulsion, goal position attraction, and inter-robot safety processing are exerted, respectively. In addition, a variable d_i is used to reflect the values of these data sets. Initially, its value is equal to l_i and updated by the corresponding processing.

Figure 1.

The block diagram of a multi-robot collision avoidance approach.

Distance thresholding

Generally speaking, laser sensor has a larger detection range than that required for safety motion of the robot. Herein a maximum distance threshold d _max (d _max < d _L) is introduced to process the data being greater than d _max in the data set W as d _max. Meanwhile, the robot is not allowed to have too close distances with its neighboring obstacles. This minimum distance threshold is described as d_safe with a value of k(r + v _max), where r is the radius of the robot, v _max is the maximum velocity of the robot, and k (k > 1) is a given coefficient. If a data d_i in W is less than d_safe , it means that the movement of the robot in the direction corresponding to this data may be dangerous. For safety consideration, the data being less than d_safe in W is regarded as an invalid one, and d_i is clear to 0. The data set W_t is then acquired after the maximum and minimum distance thresholds are applied to the data set W. Figure 2 illustrates a result of distance thresholding for a piece of data set W.

Figure 2.

Distance thresholding.

Safe passageway analysis

The robot is a physical entity and it should choose a direction that is safe enough for its whole body. For a direction θ_i , we divide the surrounding environment of the robot into three zones: I, II, and III (see Figure 3), which correspond to the intervals (θ_i − π/2, θ_i − θ_safe ), [θ_i − θ_safe , θ_i + θ_safe ], and (θ_i + θ_safe , θ_i + π/2), respectively, where θ_safe = arcsin(r_safe /d_safe ) and r_safe is a safety radius. It shall be noted that as a candidate direction, θ_i is restricted to the interval [−π/2, π/2] in order to prevent possible oscillations during obstacle avoidance.

Figure 3.

An illustration of the robot’s environment.

From the safety perspective, there are different requirements for different intervals. A qualified candidate θ_i should satisfy different requirements from these three intervals. For a direction θ_k in the zone II, its corresponding d_k in W_t should follow the condition d_k ≠ 0, whereas the direction θ_k within the zones I and III also needs to meet the condition d_ok ≥ r_safe /sin|θ_k − θ_i |, where the data d_ok refers to the original data in the data set W. The former is used to provide enough front space for the safety of the robot, and the latter is for collision avoidance of the left and right sides of the robot with obstacles. We set the data d_i to an invalid datum 0 when its corresponding direction θ_i is unqualified. Therefore, we have W_s after the safe passageway analysis is applied to W_t . The detailed process is given in algorithm 1. Figure 4 demonstrates the processing for the data set W_t in Figure 2.

Figure 4.

The processing with safe passageway analysis for the data set W_t in Figure 2.

Algorithm 1.

Safe passageway analysis.

Input: The data set W_t .

Output: The data set W_s .

1. for i=1 to N

2. if θ_i ∈[-π/2, π/2] then

3. temp=0;

4. for k=1 to N

5. if θ_k ∈(θ_i +θ_safe , θ_i +π/2) and d_ok<r_safe /sin|θ_k -θ_i| then temp++;

6. if θ_k ∈[θ_i -θ_safe , θ_i +θ_safe ] and d_k (in W_t )=0 then temp++;

7. if θ_k ∈(θ_i -π/2, θ_i -θ_safe ) and d_ok<r_safe /sin|θ_k -θ_i| then temp++;

8. end for

9. if temp≠0 then d_i (in W_t )=0;

10. end if

11. else d_i (in W_t )=0;

12. end if

13. end for

14. W_s ←W_t ;

15. return;

Osbtacles repulsion

For any nonzero data in W_s , there are different levels of threat from environment obstacles. Clearly, the smaller the distance from the robot to an obstacle is, the bigger the danger caused by the obstacle is, and vice versa. In this section, an obstacle repulsion function F_o (d_i ) is introduced to drive the robot to keep away from obstacles. From the safety perspective, when the distance between the robot and the obstacle is very small, a much larger repulsion shall be exerted. Specifically, F_o (d_i ) = 1/d_i . Then d_i is updated by F_o (d_i ). It is seen that the influences from obstacles drop sharply at the initial stage, and then the trend becomes flat. Figure 5 describes the result for the data set W_s with obstacles repulsion processing, which is expressed by W_d .

Figure 5.

The obstacles repulsion processing.

Algorithm 2.

Inter-robot safety processing.

Input: The data set W_g , the total number of its neighboring robots Z;

Output: The data set W_f .

1. for i=1 to N

2. if d_i (in W_g )≠0

3. if Z≠0

4. for j=1 to Z

5. θ_sj , θ_ej ←cal_θ(R_j );

6. Ψ _θ =[min(θ_sj , θ_ej ), max(θ_sj , θ_ej )];

7. D_j =dis(R_j );

8. calculate M_ij according to (2) and (3);

9. end for

10. M_i ← ${max}_{j = 1}^{Z} M_{i j}$ ;

11. else M_i ←1;

12. end if

13. d_i (in W_g )←d_i (in W_g )×M_i ;

14. end if

15. end for

16. W_f ←W_g ;

17. return;

Goal position attraction

The robot will eventually reach its goal position. An expectation is that the robot moves toward the goal position directly; however, it is often broken due to the disturbance from obstacles. We label the direction of the goal position relative to the robot as θ_g . A goal position attraction function F_g (i) is defined and there are two rules to follow. The first one is that F_g (i) reaches the maximum value when θ_i = θ_g. The second is that the closer θ_i is near to θ_g , the bigger the value of F_g (i) is, and vice versa. Specifically, F_g (i) is designed as

F_{g} (i) = e^{- \frac{{(\frac{90}{N} (i - \frac{(θ_{g} + π) \times N}{2 π}))}^{2}}{700}}

By applying d_i /F_g (i) to the data set W_d with all nonzero values, d_i is updated and we have W_g (see Figure 6).

Figure 6.

Goal position attraction processing.

Inter-robot safety

The robot moves in an environment with multiple robots; the threat from other robots in some cases may be even greater than that from static obstacles. Consider a scenario shown in Figure 7 with three robots, where θ_c is the current direction of the robot, and θ_cj and θ_ck are the moving directions of its nearby robots. Take a neighboring robot R_j as an example. Based on the line from the robot to R_j and the moving direction of R_j , we have the angles θ_sj and θ_ej , where θ_ej is parallel to θ_cj . For a direction θ_i , it shall be affected noticeably by the robot R_j if θ_i is within the interval Ψ _θ = [min(θ_sj , θ_ej ), max(θ_sj , θ_ej )]. The influence factor M_ij is expressed as follows

M_{i j} = {\begin{matrix} max (F_{i r} (i, j), 0.1 e^{- \frac{D_{j}}{d_{max}}}) & θ_{i} \in Ψ_{θ} \\ 0.1 e^{- \frac{D_{j}}{d_{max}}} & others \end{matrix}

F_{i r} (i, j) = e^{- \frac{D_{j}}{d_{max}}} e^{- \frac{{(\frac{90}{N} (i - \frac{(θ_{o j} + π) \times N}{2 π}))}^{2}}{300}}

Figure 7.

A three-robot scenario.

where F_ir (i, j) is the inter-robot influence function, as shown in Figure 8, D_j is the distance between the robot and its neighboring robot R_j , and θ_oj is the direction of the line from the robot to the next estimated position of robot R_j .

Figure 8.

The inter-robot influence function F_ir (i, j).

The influences from all nearby robots are then combined together. For the index i (i=1,2,…, N), the influence M_i is achieved by maximizing all influences from neighboring robots. Then we update d_i by applying d_iM_i to the nonzero data in W_g and obtain the data set W_f .

The detailed process is given in algorithm 2, where Z is the total number of its neighboring robots, cal_θ(R_j ) is used to calculate θ_sj and θ_ej , and dis(R_j ) provides the distance D_j . Figure 9 gives an illustration. The presence of other robots shall affect the data values of corresponding directions, which can reduce the possibility of these directions to be selected.

Figure 9.

Inter-robot safety processing.

Decision-making

It is noted that the data in the data set W_f are acquired with full considerations of environment, itself, and other robots. Each direction θ_i corresponding to a positive d_i is safe and it is considered as a candidate of the optimal direction. In this article, θ* is chosen as follows:

θ^{*} = θ_{{arg min}_{i = 1}^{N} d_{i}_{}} s.t. d_{i} > 0, θ_{i} \in [- \frac{π}{2}, \frac{π}{2}]

As can be observed in Figure 10, the direction corresponding to the minimum value of the valid data in W_f is selected as the optimal direction θ*, which will be sent to the motor unit for execution.

Figure 10.

Decision-making.

Simulations

Simulations are conducted to testify the proposed approach in our developed multi-robot platform with the functions of robots setting, obstacles setting, sensors perception, dynamic motion process demonstration, and so on. The robot is round with a radius r of 0.5 m. v _max = 0.2m/s, d _L = 6 m, and N = 90. The parameters in the proposed approach are as follows: d _max = 4, k = 1.5.

In simulation 1, four robots R ₁–R ₄ are required to arrive at their destinations while avoiding the collisions. The trajectories of the robots are demonstrated in Figure 11, where S ₁–S ₄ and G ₁–G ₄ are their initial positions and goal positions, respectively. It can be seen that each robot fulfills its task smoothly.

Figure 11.

The trajectories of the robots in simulation 1.

Simulation 2 is used to testify the anti-disturbance ability. The task requires four robots R ₁–R ₄ exchange their positions in pair. The results are shown in Figure 12. The robots move from the initial positions S ₁–S ₄ to respective goal positions G ₁–G ₄. When they arrive at the positions illustrated in Figure 12(a), a new obstacle obs ₃ is added, as shown in Figure 12(b). These robots rapidly respond to this sudden environment change, and finally they reach respective destinations safely.

Figure 12.

The results of simulation 2: (a) before a new obstacle obs ₃ is added and (b) after a new obstacle obs ₃ is added.

Simulation 3 considers a 20-robot scenario where R_q (q = 1,…, 10) is demanded to exchange their positions with R_q (q = 11,…, 20), respectively. The snapshots of simulation 3 are depicted in Figure 13. One can see that each robot successfully moves round the obstacles and other robots it encountered during the motion toward its destination, which demonstrates the performance of the proposed approach.

Figure 13.

The results of simulation 3 with a 20-robot scenario.

Simulation 4 assumes that the robots work in a warehouse-like environment with three sorting tables and some cargo shelves, where 12 robots are required to go to cargo shelves and 5 robots are ready to return sorting tables. The simulation result is illustrated in Figure 14(a) and (b), where the starting position and ending position for the robot R_q (q = 1,2,…, 17) are S_q and G_q , respectively. One can see that each cargo robot achieves collision-free motion.

Figure 14.

The results of simulation 4.

To further verify the proposed approach with inter-robot safety, we conduct the comparison with the method where inter-robot safety is not considered and the approach in Zhang et al.¹⁶ All robots are located in a circle whose radius is 16.5 m, and the initial position and goal position of each robot are symmetric with respect to the center of the circle. When the number of robots is even, they distributed evenly, which is equivalent to the case with positions exchange in pair. For the robotic systems whose number N_js is odd, they follow the simulation conditions as that of the even case with N_js + 1.

Figure 15 demonstrates the comparison of the proposed approach with the method without inter-robot safety and the approach in Zhang et al.¹⁶ Figures 16 to 18 illustrate the motion snapshots of robots adopting these three approaches with 12 robots, respectively.

Figure 15.

The comparison of three approaches.

Figure 16.

The snapshots of the simulation where 12 robots exchange their positions in pair with the proposed approach.

Figure 17.

The snapshots of the simulation where 12 robots exchange their positions in pair without the consideration of inter-robot safety.

Figure 18.

The snapshots of the simulation where 12 robots exchange their positions in pair with the approach in Zhang et al.¹⁶

One can see that our approach and the approach in Zhang et al.¹⁶ are superior to the method without inter-robot safety. This is mainly because that the former two approaches consider the mobility influence from the neighboring robots. From Figures 16 to 18, the approaches without inter-robot safety and in Zhang et al.¹⁶ lead to a denser aggregation of robots. Clearly, this aggregation shall increase the difficulty for these robots to break away from the congestion, which results in a lengthy task execution time. For the proposed approach, the dense aggregation of robots is suppressed. The comparison reveals the superiority of the proposed approach with a shorter execution time.

Conclusion

This article proposes an approach to avoid collisions in complex multi-robot environments. The proposed approach considers the influences from itself, the static obstacles, and other neighboring robots. By inter-robot safety processing, the possibility of being selected for the directions that are affected by the neighboring robots is reduced. Finally, an optimized criterion is given to obtain a collision-free decision. The simulation results show that the proposed approach can achieve collision avoidance even in crowded multi-robot environments. In the future, we will conduct the experimental verification with more theoretical analysis.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under grants 61633017 and 61633020, the National High Technology Research and Development Program of China (863 Program) under grant 2015AA042201, the Beijing Natural Science Foundation under grant 4161002, and the Key Research and Development Program of Shandong Province under grant 2017CXGC0925.

References

Tiwari

Honoré

Jeong

. Resource-constrained decentralized active sensing for multi-robot systems using distributed Gaussian processes. In: 16th International Conference on Control, Automation, and Systems (ICCAS), Gyeongju, South Korea, 16–19 October 2016, pp. 13–18. IEEE.

Zheng

Negenborn

Lodewijks

. Fast ADMM for distributed model predictive control of cooperative waterborne AGVs. IEEE Trans Control Syst Technol 2017; 25(4): 1406–1413.

Digani

Sabattini

Secchi

. A probabilistic Eulerian traffic model for the coordination of multiple AGVs in automatic warehouses. IEEE Robot Autom Lett 2016; 1(1): 26–32.

Saad

Bleakley

Dobson

. Robust high-accuracy ultrasonic range measurement system. IEEE Trans Instrum Meas 2011; 60(10): 3334–3341.

Hamzah

Rosly

Hamid

. An obstacle detection and avoidance of a mobile robot with stereo vision camera. In: 2011 International Conference on Electronic Devices, Systems and Applications (ICEDSA), Kuala Lumpur, Malaysia, 25–27 April 2011, pp. 104–108. IEEE.

Liu

Dong

. Collision-free navigation for mobile robots by grouping obstacles. In: 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), Zhuhai, China, 6–9 December 2015, pp. 1686–1691. IEEE.

Ayoade

Sweatt

Steele

. Laser-based gap finding approach to mobile robot navigation. In: 2016 IEEE International Conference on Advanced Intelligent Mechatronics (AIM), Banff, AB, Canada, 12–15 July 2016, pp. 858–863. IEEE.

Yuan

Cao

Liu

. A motion control method for mobile robot based on sub-regions evaluation in local sensing environment. J Huazhong Uni Sci Technol (Natural Science Edition) 2013; 41(Sup. I): 38–41 (in Chinese).

Zhou

. Adaptive artificial potential field approach for obstacle avoidance path planning. In: 2014 Seventh International Symposium on Computational Intelligence and Design (ISCID), Hangzhou, China, 13–14 December 2014, pp. 429–432. IEEE.

10.

Hernández

Hoang

. Laser-based obstacle avoidance strategy for autonomous robot navigation using DBSCAN for versatile distance. In: 2014 7th International Conference on Human System Interactions (HSI), Costa da Caparica, Portugal, 16–18 June 2014, pp. 112–117. IEEE.

11.

Kato

Nishiyama

Takeno

. Coordinating mobile robots by applying traffic rules. In: Proceedings of the 1992 lEEE/RSJ International Conference on Intelligent Robots and Systems, Raleigh, NC, USA, 7–10 July 1992, pp. 1535–1541. IEEE.

12.

Liu

Tian

Lin

. A multi-level conflict resolution method for large-scale robot system. In: The Sixth World Congress on Intelligent Control and Automation, Dalian, China, 21–23 June 2006, pp. 9006–9011. IEEE.

13.

Yan

Zhang

. Collision avoidance planning in multi-robot based on improved artificial potential field and rules. In: IEEE International Conference on Robotics and Biomimetics (ROBIO), Bangkok, Thailand, 22–25 February 2009, pp. 1026–1031. IEEE.

14.

Zhang

Lan

Qiao

. Multiple obstacles collision avoidance and behavior modelling for a mobile robot. In: 2012 Proceedings of International Conference on Modelling, Identification & Control (ICMIC), Wuhan, Hubei, China, 24–26 June 2012, pp. 951–956. IEEE.

15.

Liu

Zhang

. PSO-based parameters optimization of multi-robot formation navigation in unknown environment. In: 2012 10th World Congress on Intelligent Control and Automation (WCICA), Beijing, China, 6–8 July 2012, pp. 3571–3576. IEEE.

16.

Zhang

Cao

Zhou

. Obstacle forbidden zone based multi-robot motion planning in unknown environments. In: IEEE International Conference on Networking, Sensing and Control, Sanya, China, 6–8 April 2008, pp. 380–384. IEEE.

17.

Amrita

Kumaar

AAN

. Bluetooth RSSI based collision avoidance in multirobot environment. In: 2016 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Jaipur, India, 21–24 September 2016, pp. 2168–2174. IEEE.