Research on the Collision-Free Path Planning of Multi-AGVs System Based on Improved A* Algorithm ()
1. Introduction
With the development of e-commerce, its scale is increasing rapidly and tends to develop in the direction of “muti-varieties and small batch” because of personalized needs of people. The velocity of logistics, as one of the important aspects of service quality evaluation in the express industry, is immediately influenced by the efficiency of sorting operation [1] [2] . The general sorting mode of “people to goods” can decrease the cost, but it has the disadvantages of lower efficiency and automation. The modern modes such as automated sorting machine and stereoscopic warehouse, which mainly depend on transmission equipment and logistics information technology, have the advantage of higher sorting efficiency, but they also have some shortages such as large area occupied, poor flexibility and robustness, etc. [3] [4] [5] [6] .
Automatic Guided Vehicle (AGV) is a kind of advanced automatic logistics equipment which can meet the requirements of sorting operation and turn the “people to goods” sorting mode into “goods to people” sorting mode. The path planning problem is the core and hot topic of task allocation for multi-AGVs [7] . At present, there are many researches on dynamic and static path planning problems at home and abroad. The local and global path planning methods for mobile robots’ are summarized and induced by Gu Donglei et al. [8] . The two-stage dynamic path planning and scheduling problems in multi-AGVs system are studied by Liu Guodong et al. [9] . Further researches on route optimization problems of single AGV and multi-AGVs are also done by scholars abroad. Vehicle travelling models for AGV systems under various dispatching rules is studied by Pyung Hoikoo et al. [10] . Tatsushi Nishi [11] conducted an experimental study on a local rescheduling procedure for dynamic routing autonomous decentralized AGV systems. Toshiyuki Miyamoto [12] studied local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems. Mohammad Saidi-Mehrabada [13] proposed an ant colony algorithm for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs. Although there are many research results about the problem of searching the shortest path, they do not solve the path planning problem from the perspective of reducing traffic congestion.
The paper is organized as follows. First, based on the dynamic sorting operation mode for multiple AGVs, the sorting environment is described by using grid method. Second, the estimated cost of A* algorithm is improved by adding the penalty value of the paths that AGVs share with each other to alleviate traffic congestion. Then the collision-free path planning is done by combing the improved A* algorithm and collision- free planning. Finally, the sorting efficiency of the improved A* algorithm is compared with that of other algorithms by simulation experiments.
2. The Modeling of Warehouse Environment Using Grid Method
Environment modeling is the basis of collision-free path planning. In this paper, environment model for AGVs’ work space is established using grid method. Grid environment has the characteristics of good visibility and simple model building, so the application of this method is mature. The size and number of grids are determined by the size of AGV and work space. The grids are defined in rectangular coordinate system. The attributes of grids include the following dimensionalities: 1) each grid’s position coordinates information 
which can be fed back to upper computer; 2) each grid’s sequence number which is set from left to right successively can represent AGV’s driving path; 3) the types of grids includes shelf grid (set 1), pigeonhole grid (set 2),
![]()
Figure 1. Warehouse environment modeled using grid method.
replenishment platform grid (set 3), pausing area grid (set 4), charging piles grid (set 5) and the other free grids is set 0. They are represented by grids with different color. The warehouse environment modeled using grid method is shown in Figure 1.
Based on the environment model, the work process of AGVs is given as follows. First AGVs receive tasks to carry shelves to the appointed sorting area from the appointed shelf area and the shelves wait to be sorted. Then shelves which had been sorted out are carried to the original position and AGVs are allocated another task. If there are no other tasks, AGVs will return to the pausing area. The direction of the arrow represents AGV’s driving direction. AGVs can drive in 4 directions: due east, due west, due south and due north.
3. The Improvement of A* Algorithm When Used in Collision-Free Path Planning of Multi-AGVs System
3.1. The Original A* Algorithm
A* algorithm can calculate the shortest path in real time efficiently and is applied widely in the practical engineering. Two factors including actual cost and estimated cost are taken into account for the method to calculate the distance between the current point and the target point [14] . The actual cost means the cost of the path that AGV had taken and the estimated cost means the cost of the path that the AGV will take. The general evaluation function form is given as follows:
(1)
where 
means the actual cost (from the starting point to the current point n calculated according to the actual driving condition, 
means the estimated cost (from the current point n to the target point) including heuristic information. Estimated cost is mainly used to find the search direction, which has great influence on the final search results and efficiency [15] . The closer the estimated cost is to the actual cost, the faster the convergences speed will be. When the estimated cost is less than the actual cost, the convergence speed will be slower but the optimal solution can be ob-
tained, on the contrary the convergence speed will be faster but the optimal solution probably cannot be obtained. So the estimated cost is the emphasis and difficulty of the research.
3.2. The Improvement of A* Algorithm Considering Traffic Congestion
The moving directions for AGV in the storage environment are due east, due west, due south and due north. So usually the Manhattan Distance is used to calculate the estimated cost 
when study the sorting route. The estimated cost according to the current point 
and the target point 
is given as follows:
(2)
But if the Manhattan Distance is used as the estimated cost, the path planning will be restricted to the single AGV in static rather than dynamic environment, and it will cause traffic jam. In order to relieve traffic jam and improve calculation efficiency, at the intersection, the paths of AGVs are planned again and all the feasible paths are detected in which the penalty value of the paths that AGVs share with each other is added. The penalty value depends on the distance from the AGV and it is in inverse proportion to the distance. Eventually the estimated cost function is chosen as follows.
(3)
In this function, a is the number of AGVs whose distance from the target point is 1-4 grids and its weight is
, b is the number of AGVs whose distance from the target point is 4-8 grids and its weight is
, and the number of the other AGVs is c and its weight is
.
, Which means the closer the distance the greater the penalty value. Dynamic path planning is implemented by improving the estimated cost and the traffic jam is relieved. The final estimated cost function is given as follows:
(4)
4. The Collision Resolution Rules
When using A* algorithm to plan the path of each AGV dynamically, collisions will happen when many AGVs work at the same time in practical operation. Two types of collisions in storage environment are given as follows.
4.1. Conflicts Caused by Catching Up
Conflicts caused by catching up are shown in Figure 2. To solve this conflict, the priority of AGVs is not considered, the AGV behind should stop and wait until the AGV ahead passes, and then it continues to move.
4.2. Conflicts in Intersection
There are 4 types’ conflicts in intersection, which are shown in Figure 3. To solve these conflicts in intersection, AGVs with lower priority should stop to wait until the AGV with higher priority passes, and then they can continue to move.
![]()
Figure 2. Conflicts caused by catching up.
5. The Steps of Collision-Free Path Planning of Multi-AGVs Based on Improved A* Algorithm
Based on the analysis above, collision-free path planning of multi-AGVs based on improved A* algorithm and collision resolution rules is carried out, the steps are as follows.
Step 1: Define two tables named OPEN and CLOSE. OPEN means the set of nodes which will be searched definitely but cannot be ensured that they are on the shortest path. CLOSE is the set of nodes which have been searched already and the shortest path can be found from the starting point to the target point in these nodes.
Step 2: Choose nodes 
and ![]()
which are the starting point and the target point respectively and ![]()
means the other points. Then ![]()
is placed in the table OPEN and table CLOSE is initialized to be empty.
Step 3: Choose the node n which makes the value of function f(n) minimum and then it is added into table CLOSE. Then if the point is the target point, the search is ended and the optimum solution is obtained, otherwise the next search is conducted. If table OPEN is empty, it means the path cannot be found and the algorithm is ended
Step 4: Extend searching for grid ![]()
which is adjacent to ![]()
and has no obstacles and calculate the value of![]()
, then repeat step 3.
If there are conflicts between AGVs, it is handled by collision resolution rules. The path of AGVs can be planed again using the method. So the new method can obtain the maximal benefit using the idea of reliving traffic jam on the premise of finding a collision-free path.
6. Simulation Analyses
On c# software platform, the simulation software of multi-AGVs sorting system is developed, as shown in Figure 4. The left is menu bar which can monitor AGV’s motion state and adjust AGV’s speed and accelerated speed. The right is work area modeled by gird method which can simulate the real sorting environment. Sorting efficiency indicators are shown in the top right corner. AGV’s application environment and the number of tasks required can be set automatically according to the need in the system.
In the simulation experiment, the area of warehouse is 800 × 800 which is divided into 1 × 1 grids. The number of AGV is 80 and its size is 0.8 × 0.8. The speed of AGV is 2 m/s. When select the parameters of α, β, γ, we should ensure![]()
, which means the closer the distance the greater the penalty value. Here we the parameters of α, β, γ are set to be 0.6, 0.3 and 0.1 separately. On the platform, the sorting efficiency of multi-AGVs with path planning based on the improved A* algorithm is compared with that of original A* algorithm, as shown in Table 1. In the table, ASP/s stands for the average sorting pieces per second.
![]()
Figure 4. The simulation platform of multi-AGVs sorting system.
![]()
Table 1. Comparison of the sorting efficiency between original A* algorithm and improved A* algorithm.
According to the simulation results, sorting speed of the two methods both decreases with time, but method based on the improved A* algorithm can sort more pieces of express package and the sorting speed decreases more slowly than that of original A* algorithm. That is because traffic congestion and collision avoidance are considered in the improved algorithm. So the method based on the improved A* algorithm not only can meet the sorting system’s requirements for stability, but also can improve the sorting efficiency and relieve traffic jam.
7. Conclusion
On the basis of warehouse environment built by using grid method, the paths of AGV are planned from the perspective of relieving traffic jam and avoiding collisions by using improved A* algorithm and collision resolution rules. Simulation results show that the new method can improve the sorting efficiency of multi-AGVs and relive traffic jam. In future research, more effective algorithms according to different scenarios will be studied.
Acknowledgements
This paper is supported by Funding Project for Beijing Intelligent Logistics System Collaborative Innovation Center; Funding Project for Beijing key laboratory of intelligent logistics system; Science and technology plan general program of Beijing Municipal Education Commission (ID: KM201510037001); Funding Project for Technology Key Project of Municipal Education Commission of Beijing (ID: TSJHG201310037036).