# Dynamic Path Planning Analysis of Warehouse Handling Robot

Authors: Yue Zhao
Journal: Journal of Sensors
 (2022)

---

## Abstract

In order to further improve the operational efficiency and the flexibility of automated warehouse, a path planning algorithm for a warehouse handling robot was evaluated. Under the background of determining the operation scene and environment of multihandling robot, a path planning algorithm with time window is proposed for multihandling robot, and a two-stage path planning method is also analyzed. The results show that the route planning using the improved Dijkstra algorithm saves 7.16 meters compared with the traditional algorithm, and the task is completed 3.17 seconds earlier. Comprehensively considering the heat of the various paths to turn to the required time, using the improved Dijkstra algorithm path, handling the robot’s total running distance than the traditional algorithm saves 14.45 meters, the total run time saves 8.45 seconds, and whether in time or in the distance, crane robot handling efficiency compared with the traditional algorithm has an obvious increase, closer to reality.


---

## Body

## 1. Introduction

With the development of warehousing automation technology, handling robot technology is also developing rapidly and has become the focus of attention in the world today [1]. At present, the handling robot has completed the simple work such as palletizing, dispalletizing, and handling, in-depth to more complex logistics operations such as sorting and picking [2].With the acceleration and deepening of the aging process of China’s population, the era of “demographic dividend” with abundant labor resources has gradually faded, and the problem of high labor cost of enterprises has gradually emerged. It has become an inevitable trend to replace manual operation with automatic equipment to improve the level of warehousing automation [3]. Undoubtedly, using the handling robot to replace manual picking operation of goods, for improving the level of automation and saving labor costs, improve the efficiency of the operation plays an important role [4].The development of e-commerce and logistics industry has promoted the integrated application of intelligent handling robots in automated warehouses and promoted the transformation and upgrading of storage operation mode. However, a series of problems about intelligent and efficient task allocation, vehicle scheduling, path planning, and conflict handling restrict the promotion and application of handling robots [5]. Therefore, it is necessary to increase the research on the handling robot, solve the technical difficulties affecting the integrated application of the handling robot, and realize the cooperative planning of multiple handling robots, so as to improve the operating efficiency, reduce labor costs, and maximize profits.


## 2. Literature Review

The handling robot is a new type of mobile robot which is used in storage operation field, by laying magnetic rails, navigation routes, positioning beacons, and other indicating devices in the warehouse, combined with motion control technology, task planning technology, sensor technology, and other technical methods. According to the information of indicating device, accurate positioning and path planning are needed. Smooth handling of mobile shelves and effective connection between shelves and staff are as shown in Figure1 [6].Figure 1
Transfer robot.At present, there are mainly two kinds of robots used in warehouses, one of which is the logistics robot represented by Kiva used by Amazon, which is also used in most logistics warehouses in China [7]. This kind of robot subverted the traditional mode of looking for goods on the shelf through manual attack. Instead of picking goods by itself, the robot can directly carry the whole movable shelf to the picking platform for picking workers to pick goods, thus realizing the picking of goods to people mode [8]. The use of Kiva-like robots in the warehouse reduces the time for workers to walk in the warehouse to pick up goods. This greatly reduces the number of picking workers, greatly saves the labor cost, and improves the working efficiency of the storage system, and the robot delivers the work of picking goods to the picking workers. It also reduces the complexity, easy to operate, and is the main role in the future automated warehouse [9]. However, because the robot needs to move the whole shelf to the picking table at one time, the energy consumption is high and the goods category is less. Moreover, due to the limitation of the loading volume of the shelf, the handling robot cannot carry the goods with large volume and heavy weight, so there are certain restrictions on the types of goods and the promotion scope is narrow. Scheduling and path planning for multiple robots are also difficult and prone to conflict, which requires continuous improvement [10].The other is the robot used by Tmall platform. This kind of robot can not only move to the shelf and use the mechanical arm to pick goods but also transport the picked goods to the packaging platform for direct packaging, without the need for picking workers to pick again [11]. Compared with Kiva, it can directly select goods according to the order information, with a higher degree of automation. However, it requires a robot for picking tasks and a robot for delivery tasks to cooperate to complete the task, which requires a large number of robots and a high cost. In addition, the technology of grasping goods with mechanical arm is not mature, and the grasping of goods with small volume is not very accurate and the efficiency is low, which needs to be improved gradually in the future [12, 13]. Facing the huge market demand, in order to win the time efficiency favored by customers, further improves the operational efficiency and enhances the flexibility of automated warehouse. Many enterprises such as Amazon, Tmall, Jingdong, and other e-commerce enterprises are actively carrying out the research of multi-handling robots, trying to use multihandling robots to carry goods, accelerate the layout of more intelligent automatic storage system, improve the quality of service, and increase the competitiveness of enterprises [14, 15].On the basis of the current research, this paper takes the dynamic path planning problem of multiple porters as the research object. This paper analyzes the research status at home and abroad and the existing problems in path planning of multihandling robots and designs a path planning model and its solving algorithm.


## 3. Research Methods

### 3.1. Path Planning Algorithm for Multiple Handling Robots with Time Windows

The time window algorithm was first proposed by Kim and Tanchoco and is often used for path optimization of multiple handling robots in bidirectional graphs [16]. The time window algorithm was first proposed by Kim and Tanchoco and is often used for path optimization of multiple handling robots in bidirectional graphs [17]. In the process of robot operation, the time occupied by each robot on each road section can be calculated [18]. When the time windows occupied by different robots do not overlap, it indicates that there is no collision [19]. If there is a potential collision, adjust the original time window to avoid collision [20]. The specific algorithm flow chart is shown in Figure 2. Therefore, as long as the start time, speed, start node, target node, and path information matrix of the robot are clear, the sequence of resources occupied by the robot can be prearranged through calculation to avoid conflicts and collisions.Figure 2
Flow chart of time window algorithm.


### 3.2. Multihandling Robot Operation Description

In actual production, the picking mode of the person receiving the goods is that the handling robot moves the shelves of the items needed in the order to the picking table, and the picking workers only need to take out the SKU needed from the shelves at the picking station [21]. The use of the handling robot saves the time of manual walking and improves the operation efficiency. The operation process of the handling robot in the delivery and human picking mode is as follows:
(1)
According to the quantity of each SKU in the order: inventory and other information to select the matching task rack and will need to pick the shelves and picking platform to match (determined by the shelf location picking platform busy degree and other factors), determine the starting point and end point of picking(2)
Assign tasks to moving robots: since a handling robot cannot execute multiple order tasks at the same time, the system needs to query the working status of the handling robot, assign the task to the idle handling robot nearest to the required handling shelf, and plan the optimal walking path from the starting point to the end point. If there is no free robot, wait until there is a free robot(3)
After receiving the task, the state of the handling robot will be changed from idle to working state, drive to the task shelf according to the path planned by the system from the location, and lift the task shelf, and the robot will be changed from empty to load state(4)
The handling robot with the task shelf drives to the target picking station and waits for picking. After the current picking task is completed, check whether there are other picking tasks. If so, move to the designated picking station and wait for picking. Otherwise, enter Step (5)(5)
It requests the system to transport the task shelf back to the target location given by the system and designs the optimal return path for the carrying robot. The state of the carrying robot becomes empty(6)
Determine whether the handling robot needs to be charged. If it needs to be charged, drive to the charging pile for charging, otherwise release the handling robot(7)
Go to Step (2) and repeat until there are no picking tasks [22, 23]


### 3.3. Environment Modeling

Combined with the characteristics of different modeling methods and according to the actual warehouse operation environment, this paper adopts raster graph modeling method to create warehouse operation electronic environment map model [24].The steps of warehouse operation environment modeling for handling robot are as follows:(1)
Determine the number of gridsWith the lower left corner of the warehouse as the origin of coordinates, the rectangular coordinate system is established. The axis of the coordinate system represents the length of the warehouse, and the axis represents the width of the warehouse. Assuming that the length of the warehouse isX, the width is Y, and the side length of the grid is z, the number of grids of the axis x is the rounded value of the length of the warehouse divided by the length of the grid INTX/Z, and the number of grids of the axis y is the rounded value of the width of the warehouse divided by the width of the grid INTY/Z [25].
(2)
EncodingAfter the number of grids is determined, the grid data in the rectangular coordinate system is numbered. The grid’s two-dimensional coordinates start at the origin1,1, and the grid’s one-dimensional coordinates start at 1 and proceed from bottom to top, left, and right. Assuming that the two-dimensional numbering of the grid P is x,y, the corresponding formula of two-dimensional coordinates and one-dimensional coordinates is
(1)Coding=x−1∗INYXZ+y(3)
Barriers to assign a valueThe obstacle grid on the international circle is divided into several grids on the international circle. Grids with impassable obstacles are marked with a 1, and grids with unpassable obstacles are marked with a 0.


### 3.4. Two-Stage Path Planning Method

The core idea of the two-stage path planning method is to generateN alternative paths for the handling robot in offline state and then plan the path of the robot in real time through online information. The algorithm has been widely used in the path planning of mobile robots because of its advantages such as low online computation burden. However, the optimal path generated by this method in the offline state is not the optimal path of the robot, which needs to be further planned online, making the overall efficiency of the system low. This paper optimizes the traditional two-stage path planning method.Firstly, based on the weighted directed graph, Dijkstra algorithm with path heat evaluation index is used to generate global optimal path in the offline phase. Due to the static path planning for the handling robot, the route of each handling robot may be interfered by other robots as the tasks continue to enter the system. Therefore, during the operation of the handling robot, the multihandling robot system needs to track and locate the route of the handling robot running in the system in real time. If there is no path interference, the static optimal solution is the global optimal solution. Once it is found that two or more handling robots have path interference and there is time window conflict, the traffic control strategy will be started. By adjusting the priority of vehicles, possible path conflicts can be prevented and avoided in advance. The structure of offline-online two-stage path planning algorithm is shown in Figure3.Figure 3
Flowchart of two-stage path planning method.


### 3.5. Improved Algorithm Dijkstra

In this paper, the traditional Dijkstra algorithm is improved by adding heat value into the path weight to make the route planning more reasonable. The heat of each path is definedfb=fb12,fb23,⋯,fbmn in the time cycle ∆, the real-time number of handling robots on each path during operation is bg=b12,b23,⋯bmn, and E is the total number of paths. The specific calculation process is as follows:
(1)
The traditional Dijktra algorithm is used to preliminarily plan the path of each carrying robot from the task starting point to the end point(2)
The paths in step (1) are decomposed and the utilization frequency of each road section within the time cycle is counted(3)
When the carrying robot passes through the current path,bg automatically decreases by 1(4)
The influence coefficient function of construction path busyness on path selection by Dijkstra algorithm is shown in(2)Ffb=bg+1hk∑g=1p∑k=1EbghkThen, the path weight value after adding path heat is(3)wjk=1+Ffb.The improved Dijkstra algorithm flow is shown in Figure4.Figure 4
Improved Dijkstra algorithm flow chart.


## 3.1. Path Planning Algorithm for Multiple Handling Robots with Time Windows

The time window algorithm was first proposed by Kim and Tanchoco and is often used for path optimization of multiple handling robots in bidirectional graphs [16]. The time window algorithm was first proposed by Kim and Tanchoco and is often used for path optimization of multiple handling robots in bidirectional graphs [17]. In the process of robot operation, the time occupied by each robot on each road section can be calculated [18]. When the time windows occupied by different robots do not overlap, it indicates that there is no collision [19]. If there is a potential collision, adjust the original time window to avoid collision [20]. The specific algorithm flow chart is shown in Figure 2. Therefore, as long as the start time, speed, start node, target node, and path information matrix of the robot are clear, the sequence of resources occupied by the robot can be prearranged through calculation to avoid conflicts and collisions.Figure 2
Flow chart of time window algorithm.


## 3.2. Multihandling Robot Operation Description

In actual production, the picking mode of the person receiving the goods is that the handling robot moves the shelves of the items needed in the order to the picking table, and the picking workers only need to take out the SKU needed from the shelves at the picking station [21]. The use of the handling robot saves the time of manual walking and improves the operation efficiency. The operation process of the handling robot in the delivery and human picking mode is as follows:
(1)
According to the quantity of each SKU in the order: inventory and other information to select the matching task rack and will need to pick the shelves and picking platform to match (determined by the shelf location picking platform busy degree and other factors), determine the starting point and end point of picking(2)
Assign tasks to moving robots: since a handling robot cannot execute multiple order tasks at the same time, the system needs to query the working status of the handling robot, assign the task to the idle handling robot nearest to the required handling shelf, and plan the optimal walking path from the starting point to the end point. If there is no free robot, wait until there is a free robot(3)
After receiving the task, the state of the handling robot will be changed from idle to working state, drive to the task shelf according to the path planned by the system from the location, and lift the task shelf, and the robot will be changed from empty to load state(4)
The handling robot with the task shelf drives to the target picking station and waits for picking. After the current picking task is completed, check whether there are other picking tasks. If so, move to the designated picking station and wait for picking. Otherwise, enter Step (5)(5)
It requests the system to transport the task shelf back to the target location given by the system and designs the optimal return path for the carrying robot. The state of the carrying robot becomes empty(6)
Determine whether the handling robot needs to be charged. If it needs to be charged, drive to the charging pile for charging, otherwise release the handling robot(7)
Go to Step (2) and repeat until there are no picking tasks [22, 23]


## 3.3. Environment Modeling

Combined with the characteristics of different modeling methods and according to the actual warehouse operation environment, this paper adopts raster graph modeling method to create warehouse operation electronic environment map model [24].The steps of warehouse operation environment modeling for handling robot are as follows:(1)
Determine the number of gridsWith the lower left corner of the warehouse as the origin of coordinates, the rectangular coordinate system is established. The axis of the coordinate system represents the length of the warehouse, and the axis represents the width of the warehouse. Assuming that the length of the warehouse isX, the width is Y, and the side length of the grid is z, the number of grids of the axis x is the rounded value of the length of the warehouse divided by the length of the grid INTX/Z, and the number of grids of the axis y is the rounded value of the width of the warehouse divided by the width of the grid INTY/Z [25].
(2)
EncodingAfter the number of grids is determined, the grid data in the rectangular coordinate system is numbered. The grid’s two-dimensional coordinates start at the origin1,1, and the grid’s one-dimensional coordinates start at 1 and proceed from bottom to top, left, and right. Assuming that the two-dimensional numbering of the grid P is x,y, the corresponding formula of two-dimensional coordinates and one-dimensional coordinates is
(1)Coding=x−1∗INYXZ+y(3)
Barriers to assign a valueThe obstacle grid on the international circle is divided into several grids on the international circle. Grids with impassable obstacles are marked with a 1, and grids with unpassable obstacles are marked with a 0.


## 3.4. Two-Stage Path Planning Method

The core idea of the two-stage path planning method is to generateN alternative paths for the handling robot in offline state and then plan the path of the robot in real time through online information. The algorithm has been widely used in the path planning of mobile robots because of its advantages such as low online computation burden. However, the optimal path generated by this method in the offline state is not the optimal path of the robot, which needs to be further planned online, making the overall efficiency of the system low. This paper optimizes the traditional two-stage path planning method.Firstly, based on the weighted directed graph, Dijkstra algorithm with path heat evaluation index is used to generate global optimal path in the offline phase. Due to the static path planning for the handling robot, the route of each handling robot may be interfered by other robots as the tasks continue to enter the system. Therefore, during the operation of the handling robot, the multihandling robot system needs to track and locate the route of the handling robot running in the system in real time. If there is no path interference, the static optimal solution is the global optimal solution. Once it is found that two or more handling robots have path interference and there is time window conflict, the traffic control strategy will be started. By adjusting the priority of vehicles, possible path conflicts can be prevented and avoided in advance. The structure of offline-online two-stage path planning algorithm is shown in Figure3.Figure 3
Flowchart of two-stage path planning method.


## 3.5. Improved Algorithm Dijkstra

In this paper, the traditional Dijkstra algorithm is improved by adding heat value into the path weight to make the route planning more reasonable. The heat of each path is definedfb=fb12,fb23,⋯,fbmn in the time cycle ∆, the real-time number of handling robots on each path during operation is bg=b12,b23,⋯bmn, and E is the total number of paths. The specific calculation process is as follows:
(1)
The traditional Dijktra algorithm is used to preliminarily plan the path of each carrying robot from the task starting point to the end point(2)
The paths in step (1) are decomposed and the utilization frequency of each road section within the time cycle is counted(3)
When the carrying robot passes through the current path,bg automatically decreases by 1(4)
The influence coefficient function of construction path busyness on path selection by Dijkstra algorithm is shown in(2)Ffb=bg+1hk∑g=1p∑k=1EbghkThen, the path weight value after adding path heat is(3)wjk=1+Ffb.The improved Dijkstra algorithm flow is shown in Figure4.Figure 4
Improved Dijkstra algorithm flow chart.


## 4. Interpretation of Result

### 4.1. Improved Dijkstra Algorithm Validation

In this paper, the proposed improved Dijkstra algorithm is verified by simulation experiments assuming that the moving speed of the robot is 1 m/s and the distance between grids is 5 m. The starting and ending coordinates of priority 1 are10,18,8,1, and the starting and ending coordinates of priority 2 are 21,10,16,1. The results are shown in Table 1.Table 1
Computational results.
AlgorithmDistance (m)Running time (seconds)Traditional Dijkstra algorithm268.96273.96Improved Dijkstra algorithm261.80270.7938It can be seen from Table1 that when the path heat value is added and the traditional algorithm and the improved algorithm are used to plan the path, the distance, and time of the carrying robot are different. Compared with the traditional algorithm, the route planning using the improved Dijkstra algorithm saves 7.16 meters and completes the task 3.17 seconds earlier. On the one hand, the improved algorithm coordinates the load balance of the path to avoid the congestion of the path; on the other hand, it also saves the running time and distance and improves the efficiency of the carrying robot.


### 4.2. Validation of Dynamic Path Planning Algorithm in Offline Phase of Multihandling Robot

On the basis of considering the busy degree of the path and turning time, four tasks were set for the carrying robot, and the total running distance and running time of the carrying robot were compared between the traditional Dijkstra algorithm and the improved Dijkstra algorithm.The starting point and ending point of priority 1 are10,18 and 8,1, respectively. The starting point and ending point of priority 2 are 21,10 and 16,1, respectively. The starting point and ending point of priority 3 are 19,23 and 24,1, respectively. The starting and ending coordinates of priority 4 are 29,8 and 32,1, respectively.The comparison of the total running time and total running distance of the four tasks before and after the algorithm was improved is shown in Figure5. Experimental results show that when the heat of each path is considered comprehensively, the time required for turning is taken into account. Using the path solved by the improved Dijkstra algorithm, the total running distance and total running time of the robot are 14.45 meters and 8.45 seconds less than those of the traditional algorithm. Both in time and in distance, the handling efficiency of the handling robot has been significantly improved compared with the traditional algorithm and is closer to the reality.Figure 5
Comparison of calculation results before and after algorithm improvement.


## 4.1. Improved Dijkstra Algorithm Validation

In this paper, the proposed improved Dijkstra algorithm is verified by simulation experiments assuming that the moving speed of the robot is 1 m/s and the distance between grids is 5 m. The starting and ending coordinates of priority 1 are10,18,8,1, and the starting and ending coordinates of priority 2 are 21,10,16,1. The results are shown in Table 1.Table 1
Computational results.
AlgorithmDistance (m)Running time (seconds)Traditional Dijkstra algorithm268.96273.96Improved Dijkstra algorithm261.80270.7938It can be seen from Table1 that when the path heat value is added and the traditional algorithm and the improved algorithm are used to plan the path, the distance, and time of the carrying robot are different. Compared with the traditional algorithm, the route planning using the improved Dijkstra algorithm saves 7.16 meters and completes the task 3.17 seconds earlier. On the one hand, the improved algorithm coordinates the load balance of the path to avoid the congestion of the path; on the other hand, it also saves the running time and distance and improves the efficiency of the carrying robot.


## 4.2. Validation of Dynamic Path Planning Algorithm in Offline Phase of Multihandling Robot

On the basis of considering the busy degree of the path and turning time, four tasks were set for the carrying robot, and the total running distance and running time of the carrying robot were compared between the traditional Dijkstra algorithm and the improved Dijkstra algorithm.The starting point and ending point of priority 1 are10,18 and 8,1, respectively. The starting point and ending point of priority 2 are 21,10 and 16,1, respectively. The starting point and ending point of priority 3 are 19,23 and 24,1, respectively. The starting and ending coordinates of priority 4 are 29,8 and 32,1, respectively.The comparison of the total running time and total running distance of the four tasks before and after the algorithm was improved is shown in Figure5. Experimental results show that when the heat of each path is considered comprehensively, the time required for turning is taken into account. Using the path solved by the improved Dijkstra algorithm, the total running distance and total running time of the robot are 14.45 meters and 8.45 seconds less than those of the traditional algorithm. Both in time and in distance, the handling efficiency of the handling robot has been significantly improved compared with the traditional algorithm and is closer to the reality.Figure 5
Comparison of calculation results before and after algorithm improvement.


## 5. Conclusion

Intelligent logistics is the development direction of the logistics industry in the future. By solving the key problems existing in intelligent logistics, it is conducive to promoting the transformation and development of the logistics industry and improving the overall level and efficiency of the logistics industry. The development of intelligent logistics technology has promoted the widespread application of handling robots in warehousing operations. How to carry out path planning for multiple handling robots has been widely concerned by the academic community and is summarized as follows:(1)
According to the actual environment of logistics warehouse, the warehouse operation environment map model is established. According to the actual demand of e-commerce enterprises, the path planning mathematical model of multihandling robot with time window is established with the shortest total running time as the objective function(2)
Based on the traditional two-stage path planning, a path planning algorithm for handling robot is designed which combines offline planning and dynamic scheduling. In the offline state, the path heat and turning time are considered, and the improved Dijkstra algorithm is used to plan the global optimal path. In the online state, real-time scheduling is carried out based on the priority of vehicles to avoid conflicts(3)
The traditional Dijkstra algorithm is improved by adding the path heat value to the path weight, taking into account the congestion caused by busy paths and the time required by the transfer robot to turn. The improved algorithm makes the path load balance and saves the running time of the removal robot



---

*Source: 4434971-2022-07-25.xml*