Currently, various path planning algorithms are being used in the logistics industry. Path planning includes global and local path planning. Global path planning uses the given information to avoid collisions with fixed obstacles, and reaches the desired destination with minimal cost. On the other hand, local path planning avoids obstacles by modifying the route in real time [1]. In general, local path planning has a disadvantage of falling into the local minimum; therefore, it is necessary to study an algorithm that has been integrated with the global route planning. However, the fused path planning algorithm requires a lot of computation for various collision situations, such as the frontal or side collision situation shown in Figure 1, where two robots collide at an intersection point; collision may also be with another robot in the process of avoiding a fixed obstacle [2]. When selecting the initial driving route, conventional path planning algorithms only consider the minimum cost. Therefore, while driving, unnecessary costs may be incurred when avoiding obstacles [3–5].

To solve this problem, potential collisions as well as costs should be considered when selecting an initial driving path. In this study, the whole path is composed of a grid-map, and the initial movement path of the individual robots is selected by the D* Lite algorithm. Additionally, it is possible to re-select the path movement strategy after collision detection at the grid point. We propose a collision detection algorithm that can reduce the amount of computation in the central server with minimal detection.

2.1 Path Re-planning between Two Robots

Selecting the initial path of the robot using only the classic D* Lite algorithm can cause some problems in resetting the path to avoid obstacles. First, the D* Lite algorithm recognizes other robots moving along the paths as obstacles and creates a bypassing pass, while other robots approaching from the other side also create a bypassing pass. This situation incurs unnecessary driving costs for two robots that do not share an intersection.

In Figure 2, Robot 1 recognizes Robot 2 as an obstacle and resets the path to avoid the obstacle. Additionally, Robot 2 recognizes Robot 1 as an obstacle and selects a new path. Therefore, the travelling path is increased by at least two steps from the initial path for both robots.

2.2 Collision on the Same Path

When two robots are recognized as obstacles as shown in the aforementioned case, the generation of additional movement paths presents a problem. However, as shown in Figure 3, a repetitive path reset occurs as the robots move on the initial path with the intersection. Whenever the robots move past one grid point, nearby robots are recognized as obstacles, causing unnecessary path resets.

2.3 Side Collision Situation

It is known that the D* Lite algorithm can detect and avoid dynamically moving obstacles. However, the dynamic obstacle can be avoided only when it is on the driving path of the robot; however, a collision may occur if a robot is approaching from the side Figure 4).

3.1 Basic Structure of the Proposed Algorithm

The aim of the general collision avoidance algorithm is to recognize a moving robot on the movement path as an obstacle and avoid it correctly. However, general collision avoidance algorithms do not respond effectively to the situations mentioned in Section 2.

Therefore, a collision prediction system is needed to effectively respond to these situations, and reduce the amount of computation needed to reset the driving path.

The proposed algorithm receives real-time information from the robot and then predicts the collision points through a minimum area search (Figure 5). The range of the minimum area search is determined by the designer and can be set from 5 to 10 grid points. If a collision point exists in the path of the robots, the collision situation is determined, i.e., collision along the same path (frontal collision) or collision from the side (side collision). The collision situation determination algorithm of the proposed algorithm is functionally divided into an emergency collision prediction situation, and a general collision prediction situation, and determines whether it is a frontal or side collision, respectively. When the type of collision is determined by the path planning algorithm operated in the main server, the paths are reset for each situation and transmitted to the robots.

3.2 Setting Priorities among Robots

When the paths of the robots share an intersection where collision is predicted, computation and consumption costs may be reduced if the path of one of the robots is not reset. As shown in the situation in Figure 2, the time loss can be reduced if the two robots do not attempt to reset the path simultaneously, and only one of them resets the path to avoid the other robot. Therefore, in the proposed algorithm, it is necessary to decide which of the robots needs to reset their path before collision.

In the proposed algorithm, the robots re-planning the route are determined based on priority (which can be assigned by a human operator based on the moving distance, work time, and job importance). However, for the effective operation of all robots, the maximum number of path resets must be limited. When the number of times for resetting a path is greater than or equal to a value determined by the human operator, the priority is set to 0 as the highest priority. For example, if the human operator sets the number of times to 5, the robot has the highest priority if it has modified the path 5 times to avoid other robots on the path from the starting point to the target point. The proposed algorithm determines the priority using these conditions and solves the problems caused by all bypassing robots when the collision situation between them is predicted.

3.3 Minimum Area Search

While moving in the grid map environment, the robot scans the QR code on the floor and transmits information, such as current heading direction, the scanned QR code, and the next moving direction, to the management server. The management server stores the received information in a separate memory space and uses it to predict the collision situation. The collision situation prediction method compares the next path of the highest priority robot with the next path of other robots. Because the proposed algorithm searches the grid points in only four directions from the current position of the robot, it can reduce the amount of computation needed to search for collisions as shown in Figure 6.

The method for predicting the frontal and side collision situations is designed using information about the current position of the robots transmitted to the server and the surrounding grid points. In the collision prediction situations, the locations of the lattice points in the four directions are identified in advance, and the management server conducts calculations to determine robots having the same values.

Emergency collision occurs when the next coordinate of the high priority robot is the same as the current coordinate of another robot, as shown in Figure 7. In the case of a frontal collision under an emergency collision prediction situation, the low priority robot resets the route, avoiding the high-priority robot. In the side collision prediction situation, the robot having the current grid point of the robot matching the next grid point is avoided by moving one step, regardless of the priority.

3.4 Safety Zone Verification

The safety zone verification procedure verifies the safety of a region where a low priority robot can avoid a high priority robot when the collision situation is predicted by searching for the minimum area. Figure 8 shows a front collision situation by two robots. If Robot 1 is a low-priority robot, the safety area verification procedure first checks the safety in all possible directions.

The safe area has priority over the area where the robot can move immediately. In a frontal collision situation, the safety zone first checks the left or right side, because the robots move directly to obstacles. If there are obstacles on both the left and right sides of the robot, the robot moves backwards and checks the left and right sides again.

3.5 Safety Zone Verification according to the Situation

The safety zone verification procedure depends on the collision prediction situation. Figure 9 shows the safe areas that can be selected depending on the situation. In Figure 9, Sol1 and Sol2 are candidates for the safety zone, respectively. When robots have a frontal collision, the safety zone is identified based on the robot with the lowest priority. In the side collision, the robot with the lower priority waits as the higher priority robot checks the safety zone. Moreover, in the side collision, positions are searched two steps forward, as well as on the left and right positions of the current robot. If there are no obstacles when checking two steps forward, the robot with the highest priority moves to the corresponding location immediately.

3.6 Resetting the Driving Path

When the robot moves to a safe area, it deviates from the initial path. Therefore, the robot requests a path reset from the management server based on the current location. The robot then continues movement using the newly set path. Figure 10 shows the process of resetting the path of a low-priority robot, and movement when a collision situation is predicted. Unlike the D* Lite algorithm, the proposed algorithm resets the path after evading movement to the safe area when the robot resets the path.

For the high priority robot to move quickly without loss of movement, the low priority robot waits while the high priority robot moves. The proposed algorithm resets the path when an obstacle exists in the path of the high priority robot, as shown in Figure 11.

In this simulation, the grid map is generated within a 10 × 10 range, and a collision prediction situation is created. The collision prediction situation includes a frontal collision, a side collision, and collision in a safe area when evading.

Figures 12–14 show detailed flow charts of each collision situation. The maximum number of robot collisions in one intersection is four. When two robots collide, frontal and side collision situations may occur. The processing algorithm in this case is shown in Figure 12. In the case of a frontal collision situation, the robot with the highest priority waits, and the non-priority robot checks the right and left sides for avoidance. The non-priority robot checks the right side and moves there when safety is confirmed. If there is an obstacle on the right side, the robot is configured to check the left side and moves there when safety is confirmed. If there are obstacles on both the right and left sides, the robot goes back and resets the path. The collision situation with three robots is determined by the complex and side collision situations based on the position of the priority robot. Complex collision considers both the frontal and side collisions, whereas the side collision considers only the left and right side collisions.

In the three collisions, the collision robots wait first, and in the case of a complex collision, the frontal collision is processed first, followed by the side collision. Figure 13 shows the avoidance flowchart in the event of a collision with three robots. Basically, it is the same as the method used for the two robot collisions; however, after resolving all collisions, the verification process is required once more. The path is then reset when it is determined that all the robots are safe from the collision situation.

The collision situation of four robots is a complex collision situation for all the robots. This collision situation is also resolved beginning with the frontal collision. Figure 14 shows the avoidance algorithm in the case of a collision of four robots. The robot with the highest priority avoids the frontal collision situation first, and then resolves the frontal and side collision situations in order of priority.

4.1 Simulation on Frontal Collision Avoidance

In the case of a frontal collision, the low priority robot is evacuated to a safe area after collision is detected. Additionally, in the simulation of the side collision situation, the lower priority robot waits as the higher priority robot moves to the safe area. If there is an obstacle when the robot moves to the safe area, it is detected and another safe area is identified. The robot then moves to the safe area and is tested for resetting (Figure 15).

In the results of the frontal collision avoidance simulation, the lower priority robot confirmed the safe area, then moved for avoidance. It was confirmed that the robot received the reset path from the management server and operated correctly. Further, it was confirmed that the high priority robot moved efficiently according to the set path.

4.2 Simulation on Side Collision Avoidance

The results from the side collision avoidance simulation, confirm that the higher priority robot moves after verifying the safe area while the robot with the lower priority waits. Additionally, it is confirmed that the low priority robot moves safely after the high priority robot safely passes the collision prediction point (Figure 16).

To compare the performance of the D* Lite algorithm and the proposed algorithm, simulation was conducted by dividing the distance from the starting point to the target point into 4 steps, 6 steps, and 8 steps. For the convenience of the simulation, the robot with the lower ID number was used as the high-priority robot. As shown in Table 1, it is confirmed that all the high-priority robots have a 2-step difference in the moving distance. However, the low priority robot that should be avoided is similar to that of the D* Lite algorithm.

At different distances, the difference from the D* Lite algorithm is the same. In the case of a frontal collision, it can be seen that the distance and time of movement of a higher priority robot is saved regardless of the distance.

5.1 Results of Side Collision Avoidance

The criteria for the distance traveled in the side collision simulation are similar to those of the frontal collision simulation. In the side collision test results, the D* Lite algorithm recognized only obstacles in the path; therefore, it is disadvantageous because it could not identify dynamic obstacles as obstacles. Consequently, collision occurred regardless of the distance (Table 2).

On the other hand, the proposed algorithm avoids collisions because it checks the position of each robot, and predicts the collision situation. In the case of a frontal collision, there was only a situation where the lower priority robot waited without a separate avoidance situation; thus, the moving distance was the same as the given distance. With regards to time, because there is a waiting time unlike the moving distance, it was observed that the lower priority robot delayed more.

From the results of the side collision simulation, it can be observed that the proposed algorithm is superior to the D* Lite algorithm in terms of the stability of the collision.

In this study, we proposed a method to safely reset the optimal route of a moving robot, after avoiding collision on encountering a collision situation at an intersection. The proposed algorithm involved searching the safety area to effectively avoid collision while the robot moved from the starting point to the target point and ensuring an appropriate response in various collision situations.

To compare the performance between the D* Lite algorithm and the proposed algorithm, simulation was conducted by dividing the distance from the starting point to the target point into 4 steps, 6 steps, and 8 steps. From the simulation results, the superior performance of the proposed algorithm to that of the existing D* Lite algorithm was demonstrated.

Table 1. CharacteristicsComparison of distance results for the front collision simulation.

Table 2. Comparison of travel time results for frontal collision simulation.