Keywords

1 Introduction

With the rapid development of artificial intelligence, Automated Guided Vehicle (AGV) is gradually developing towards miniaturization and intelligence. As a modern tool of logistics handling and production assembly, AGV will replace labor in logistics enterprises, manufacturing enterprises, tobacco enterprises, pharmaceutical enterprises and even more fields. By optimizing the running path of warehouse AGV, we can reduce the errors caused by human negligence, improve the utilization rate of storage space and logistics efficiency, reduce logistics costs, improve the scientific and technological content and competitiveness of enterprises, and promote the intelligent development of logistics industry in China.

In order to promote the research of AGV path optimization in warehouse environment, this paper summarizes the research status of intelligent optimization algorithms in warehouse AGV path planning in recent years, introduces the basic model of warehouse AGV path planning, discusses the genetic algorithm, ant colony algorithm and particle swarm algorithm commonly used in AGV path optimization, summarizes the improvement methods of each algorithm, analyzes the advantages and disadvantages of each algorithm and its applicable scope, and looks forward to the future research of warehouse AGV path planning.

2 Overview of Warehouse Agv Path Planning Model

Path planning refers to finding a feasible and optimal path between task points in the process of movement, and avoiding obstacles in the environment during the process of travel. Path planning includes environment modeling, path searching and path smoothing [1]. The following will be introduced from three aspects: environment modeling, objective function and constraint conditions.

2.1 Environmental Modeling

The process of environmental modeling is to transform the external environment in its original form into an internal mathematical model of appropriate planning through a series of treatments. In order to simplify the problem, the three-dimensional space environment is usually converted to two-dimensional for modeling. Environmental modeling is mainly the representation of obstacles, starting points and target points [2]. The method of environmental modeling determines the choice of path planning method and search algorithm. Different environmental modeling adopts different path planning methods. Commonly used environmental modeling methods include cell method, geometric method and artificial potential field method.

  1. 1)

    Cell Method

    Cell method is a method of dividing space into individual cells with appropriate granularity and assigning corresponding values. It mainly includes grid method and unit tree method, which are mainly different from the size of cells [3].

    The grid method divides the spatial environment by using cells of the same size, and represents the environment with arrays, in which obstacles are represented as 1 and free space as 0 [4]. Each grid point is in obstacle space or free space. Mixed grid points are classified as free space or obstacle space according to the proportion they occupy respectively. Figure 1(a) shows the grid method.

    The unit tree method divides the environment space into units with different sizes to describe the environment. Generally, the environment space is divided into larger units first, and the smaller units are divided in the space that needs to be refined. The working space of the divided unit may be free space, obstacle space and mixed space. Its advantage is better adaptability. Figure 1(b) shows the unit tree method.

Fig. 1.
figure 1

Grid method and unit tree method.

Full size image

Scholars at home and abroad choose two-dimensional or three-dimensional cell method to model the environment according to actual needs. Reference [5, 6] adopted grid method to model environment in three-dimensional space. Reference [7] realized the transformation from 3D to 2D, which vastly reduces the number and size of grids. Reference [8] used the combination of two-dimensional grid method and element decomposition method based on edge base points to model the environment, which not only solves the contradiction between grid resolution and planning speed, but also ensures the effectiveness of the whole region traversal.

Grid method is simple, but it has the problem of solving accuracy. The unit tree method has better self-adaptability, and the loss of calculating the adjacency relationship between units is large, and the calculation algorithm is more complex than the grid method.

  1. 2)

    Geometric Method

Geometric method is to extract the geometric features of the environment and map the environment space to a weighted graph by using its combination characteristics, so that the path planning problem of avoiding obstacles can be transformed into a simple graph search problem [9]. The main methods include visibility graph and Voronoi diagram method.

Visibility graph connects all the vertices of obstacles(set as V0), the starting point S, and the target point G with straight lines, and the connecting lines between the three do not pass through the obstacles, that is, the straight lines are visible. So the graph G(V, e) is constructed by giving weights to the edges in the graph, and then the optimal path is planned by some search method [10]. The viewable method is shown in Fig. 2.

Reference [11] adopted visibility graph method to model the environment, simplifying the three-dimensional motion space into two-dimensional space. Reference [12] put forward an improved visibility graph, which is only applicable to static global path planning with known working environment. Visibility graph is intuitive in concept and simple in implementation, but it lacks flexibility. In other words, once the starting point and the target point are changed, it is necessary to reconstruct the visibility graph, which is too heavy to calculate when the number or shape of obstacles is complex [13].

Fig. 2.
figure 2

Visibility graph.

Full size image

Voronoi diagram method is defined by a series of nodes, that are equidistant to the edges of two or more nearby obstacles. The space is divided into several regions, each of which contains only the edge of an obstacle [14].Voronoi diagram method is shown in Fig. 3.

Fig. 3.
figure 3

Voronoi diagram method.

Full size image

Reference [15] proposed a path planning algorithm based on Voronoi diagram. Reference [16] proposed an algorithm to calculate the generalized Voronoi diagram and its channel width generated in crowded obstacle environment. Reference [17] proposed an incremental construction method based on Voronoi diagram. The path security of Voronoi diagram is high, but the path is not necessarily optimal, and the calculation is large.

  1. 3)

    Artificial Potential Field Method

The artificial potential field method is a spatial planning method expressed by magnetic field characteristics. The basic idea is to abstract the motion of AGV in the environment as the motion of artificial gravitational field, in which the target points attract AGV and obstacles repel AGV, and the corresponding path is obtained according to the stress direction of AGV, so that AGV can effectively avoid obstacles in real time and move to the target points along the collision-free path [18]. The artificial virtual potential field method has high timeliness and smooth generation path, but it lacks macro self-regulation ability in global environment, so it is easy to fall into local optimum [19].

By adding virtual target points and improving potential field function, the problem that artificial potential field method is easy to fall into local optimum can be solved to a certain extent. Reference [20] proposed an improved artificial potential field method based on virtual target points and environmental judgment parameters to realize local path planning of mobile robots. Reference [21] made the artificial potential field algorithm realize robot automatic obstacle avoidance path planning in dynamic environment by improving the repulsive force gravitational function.

In order to improve the performance of artificial potential field method, scholars at home and abroad have proposed optimization algorithms combining artificial potential field method with rolling window method [22], fuzzy control method [23], simulated annealing method [24] and particle swarm optimization algorithm [25, 26], which mainly solves the local minimum problem and enhances the navigation ability in complex environment.

The advantages and disadvantages of cell method, geometric method and artificial potential field method are shown in Table 1.

Table 1. Comparison of advantages and disadvantages of environmental modeling methods
Full size table

2.2 Objective Function

According to different task requirements, AGV path planning can construct different objective functions. The planning model can be single objective or multi-objective, and generally takes travel time, path length and obstacle avoidance as objective functions.

Researchers usually choose single-objective optimization under certain conditions. Reference [27] took minimizing AGVs delay time as the optimization goal under the condition of given task allocation. Reference [28] took the shortest driving path as the optimization objective under the condition of meeting the requirements of obstacle avoidance. The single objective function can be solved accurately and quickly, but it is difficult to meet the actual needs.

Compared with single objective function, multi-objective function is more consistent with complex environment and has practical significance. Reference [29] took minimizing path length and maximizing path smoothness as optimization objectives. Reference [30] took energy consumption, path smoothness, and the shortest task completion time as optimization objectives. Reference [31] took task allocation waiting time and conflict-free path as optimization objectives. Reference [32] took path length, safety and smoothness as optimization objectives. The optimization of multi-objective function is based on reducing the speed of solution, and the solution is not unique and can not achieve the optimization of every sub-objective.

2.3 Constraints

The constraints of AGV path planning include self-constraints and environmental constraints. Generally, self-constraints are AGV endurance, driving speed, driving acceleration [33], waiting time [34], etc. There will be other constraints according to different task requirements. Environmental constraints include path boundaries, dynamic obstacles, terrain constraints [35], etc., and intelligent algorithms are selected to plan AGV paths under environmental constraints.

Satisfying certain constraints is the premise of AGV path planning, and the constraints are often coordinated and competitive with each other. Compared with the constraint conditions of single AGV path planning problem, the biggest feature of multi-AGV path planning is that cluster constraints are also taken into account, which usually include spatial cooperation constraints such as safe driving distance between AGVs and task cooperation constraints.

3 Overview of Algorithms for Solving the Path Planning of Warehouse AGV

Common path planning algorithms include traditional algorithms and intelligent optimization algorithms. Traditional methods mainly include mixed integer linear programming method [36, 37], A* algorithm [38], Dijkstra algorithm [39], artificial potential field method [40], dynamic window algorithm [41], etc., which have limitations in solving path planning problems. For example, A* algorithm can solve the optimal path faster and more effectively, but its efficiency decreases with the increase of search space, and it is mostly used in single AGV path planning. Although Dijkstra algorithm can find the shortest path, it contains a lot of redundant operations in the operation process, which leads to the increase of algorithm memory and the decrease of efficiency. The route planning by artificial potential field method depends on the establishment of potential field,If attractive force and repulsive force are equal and there are many positions, it may fall into the optimal layout, and if obstacles are close to the target point, it may not be possible to find a feasible path. Dynamic window algorithm has good obstacle avoidance ability and smooth path, but it is easy to fall into the local optimal solution and cannot reach the designated target along the global optimal path.

In recent years, intelligent algorithms and bionic algorithms are increasingly applied to path planning, such as genetic algorithm, ant colony algorithm, particle swarm algorithm, neural network algorithm, bee colony algorithm, and reinforcement learning algorithm, etc. Among them, genetic algorithm, ant colony algorithm and particle swarm algorithm are the most widely used. This paper mainly summarizes these three algorithms.

3.1 Genetic Algorithm

Genetic algorithm (GA), which originated from Darwin’s theory of evolution, is a kind of intelligent optimization algorithm proposed by imitating the evolution phenomenon of genetic cross mutation of natural species, and is widely used in medicine, agriculture, industry and other fields [42]. At present, many scholars have used genetic algorithm to study the path planning of single AGV. Guo Erdong [43] solved the path planning problem of single laser navigation AGV by using genetic algorithm. Dang Hongshe [44] used genetic algorithm to solve the problems of complex driving path and application limitations of AGV in factories. Gu Yong [45] put forward a multi-objective point path planning method for the multi-robot coordinated sorting operation process in intelligent warehouse. These studies effectively shorten the path length and travel time, but do not consider the constraint relationship between clusters.

In the practical scene application, the path planning problem of multi-AGV is more involved, and more and more scholars begin to study the path planning problem of multi-AGV. Li Qingxin [46] studied the genetic algorithm of path planning from single AGV to multi-AGV, and analyzed several different types of path planning according to the complexity and quantity of information in the running environment. Li Ming [47] researched and designed an improved genetic algorithm, which was applied to single robot and multi-robot path planning.

There are premature problems in the application of genetic algorithm in path planning. Many scholars optimize it by adding operators and improving fitness function. Chaymaa Lamini [48] put forward an improved crossover operator and a new fitness function considering distance, security and energy, which makes the algorithm converge faster, but increases the search time of path in the crossover process. Milad Nazarahari [49] improved the initial path by using five customized crossover and mutation operators to eliminate possible collisions between paths. Cheng Liang [50] avoids premature algorithm by adding smoothing operator and deleting operator. Yang C [51] proposed the adaptive operator and the supervised operator, which adaptively added or deleted path nodes according to the complexity of map, and obtained the optimal path considering length, smoothness and security, which was safer than other methods. These methods accelerate the convergence speed of the algorithm and reduce the time spent on AGV path planning, but the improved algorithm is mainly suitable for static environment.

Some scholars have introduced the idea of simulated annealing into the population selection operation of the algorithm to plan the optimal path of AGV [52,53,54]. Compared with local algorithm, the combination of genetic algorithm and simulated annealing algorithm can achieve convergence faster, jump out of the poor solution of local path optimization, and improve the efficiency of AGV global path search.

3.2 Ant Colony Algorithm

Ant colony optimization (ACO) was proposed by Italian scholar Dorigo et al. in 1990s. By simulating the behavior of ant colony searching for food, ACO transformed the combinatorial optimization problem into path optimization problem [55]. ACO was originally used to solve TSP problem. After years of development, it has gradually penetrated into other fields, such as graph coloring problem, large-scale integrated circuit design, routing problem in communication network, load balancing problem, vehicle scheduling problem and so on.

Traditional ant colony algorithm is affected by the setting of initial parameter empirical value, and its efficiency is low in the process of path optimization. Because pheromones are not updated in time, path search can not get the global optimal solution only locally. Aiming at the problems of ant colony algorithm in path planning, scholars at home and abroad have made improvements from two aspects: randomness of initial parameters, experience range and pheromone update.

By optimizing the initialization parameters, the convergence speed of the algorithm in path planning can be accelerated, and the global optimal path can be obtained by avoiding falling into the local optimal solution [56]. Chen Yuanyi [57] improved the algorithm by adjusting heuristic factors to avoid the algorithm falling into local minimum. Masoumi Zohreh [58] modified the relevant parts of “ant decision rules”, which is suitable for path search in complex terrain environment. Ali Zain Anwar [59] enhanced the Max-Minimum Ant Colony Optimization (MMACO) algorithm by adding Cauchy mutation (CM) operator, eliminating the limitations of classical ACO and MMACO algorithms. Li Xue [60] has improved the searching ability at the initial time, expanded the searching range and added roulette operators by adaptively changing the volatilization coefficient, thus effectively improving the quality of the solution and the convergence speed of the algorithm.

Many scholars have combined ant colony algorithm with intelligent algorithms such as genetic algorithm [65], particle swarm optimization algorithm [66] and artificial potential field method [67] to improve global and local search ability, speed up path convergence, and realize autonomous navigation, obstacle avoidance and path optimization of AGV.

Many scholars combine ant colony algorithm with other intelligent algorithms to improve the convergence speed of the algorithm. Jiao Deqiang [67] used genetic algorithm and nonlinear optimization to optimize ant colony algorithm, using genetic algorithm to improve global search ability, and using nonlinear optimization algorithm to improve local search ability. Chunyan Jiang [68] combined the heuristic strategy of particle swarm optimization and ant colony algorithm, and adopted different search strategies at different stages of the algorithm, which has fast convergence speed and strong optimization ability and can obtain better optimization results. Wang Yu [69] added the algorithm of local search of artificial potential field to find the optimal path based on ant colony algorithm, and realized the autonomous navigation, obstacle avoidance and path optimization functions of AGV trolley in automatic workshop environment.

3.3 Particle Swarm Optimization

Particle Swarm Optimization(PSO) is an evolutionary computation technique proposed by Dr. Eberhart and Dr. Kennedy in 1995, which originated from the study of bird predation behavior. The algorithm uses swarm intelligence to establish a simplified model, and makes use of the sharing of information by individuals in the swarm to make the movement of the whole swarm evolve from disorder to order in the problem solving space, thus obtaining the optimal solution [69].

PSO algorithm has the characteristics of simple modeling, easy implementation, less parameters, high precision and fast convergence, which has attracted many scholars' attention. However, the traditional PSO algorithm has the problems of slow convergence speed and early-maturing in the later stage when applied to path planning.

In order to solve the problem of late convergence speed, Guangsheng Li [70] proposed to select the most suitable search strategy adaptively at different stages, which improved the searching ability of AGV path. Nianyin Zeng [71] analyzed the path planning problem of switched local evolutionary particle swarm optimization based on non-homogeneous Markov chain and DE, and overcame the contradiction between local search and global search.

To solve the problem of premature convergence, scholars at home and abroad have put forward some solutions. Peram Thanmaya [72] optimized PSO algorithm according to the distance ratio of fitness value. Liang J J [73] used the optimal historical information to update the particle velocity. Shao Peng [74] introduced a sinusoidal function factor with periodic oscillation, which made every particle position get periodic oscillation and expanded the search space. All these three methods effectively avoided premature path. Chen Jialin [75] solved the premature phenomenon in smooth path planning by improving population evolution state strategy, adaptive inertia weight, adaptive learning factor strategy and group jump strategy.

In addition to paying attention to the search path and path optimization ability of the algorithm, scholars also have some research on the obstacle avoidance ability of the algorithm and the smoothness of the path. Ma [76] proposed random disturbance particle swarm optimization algorithm and simulated annealing particle swarm optimization algorithm to study collision-free path planning in dynamic double warehouse environment. P.K [77] used bee colony operator to enhance the ability of improved particle swarm algorithm, and calculates the optimal collision-free trajectory of robot in complex environment. Baoye Song [69] added multi-modal delay information to the speed update model, and proposed a multi-modal delay particle swarm optimization algorithm for global smooth path planning of mobile robots.

At present, in addition to optimizing PSO path planning algorithm by improving parameters, many scholars have studied the application of PSO and ant colony algorithm [78], simulated annealing algorithm [79] and genetic algorithm [80] in path planning. There are some limitations in path optimization of single algorithm, and the final result of hybrid algorithm is better than PSO algorithm alone. The fusion of intelligent algorithms can effectively play the advantages of each algorithm, improve the quality, speed and security of solving the optimal path, and its disadvantage is that the hybrid algorithm takes a long time to calculate.

To sum up, most scholars use genetic algorithm, ant colony algorithm and particle swarm algorithm for AGV path planning. These algorithms have inherent parallelism, high robustness and few parameters. In practical application scenarios, scholars have proposed some improved methods for different algorithms. Specific algorithm analysis and comparison are shown in Table 2.

Table 2. Algorithm analysis and comparison
Full size table

4 Summary

As one of the main equipments in modern warehousing, AGV's path planning technology is the key to realize intelligent warehousing. The research of AGV path planning algorithm can improve the ability of AGV to plan its own path and shorten the time of path search, which has important practical significance in the application of warehousing scenarios. In this paper, the models and environmental modeling methods of warehouse AGV path planning are summarized. It is found that the cell method is difficult to update; artificial potential field method is easy to solve, but easy to fall into local optimum. In this paper, genetic algorithm, ant colony algorithm and particle swarm optimization algorithm, which are widely used in AGV path planning, are summarized. It turned out that genetic algorithm has strong global optimization ability, but slow convergence speed, which is suitable for complex and highly nonlinear path planning problems. Ant Colony Algorithm has strong robustness and global optimization ability, but is easy to fall into local optimization, which is suitable for discrete path planning problems. PSO has the advantages of fast searching speed, few parameters and simple realization, but slow late convergence speed and easy premature convergence, which is suitable for real number path planning problems. The three algorithms can merge each other to form a new algorithm in different degrees. The fused intelligent algorithm can effectively play the advantages of each algorithm and make up for the shortcomings of the algorithm.

The environment of large-scale warehousing is complex and changeable. The warehousing tasks are highly random and dynamic, and the task scale is large. Although there have been fruitful research results on AGV path planning, the warehouse environment requires higher AGV quantity, cooperation ability, response ability, fault tolerance ability, performance and system efficiency. The research on multi-AGV path planning still cannot meet the urgent needs of storage environment, and further research and system development are needed. With the continuous progress of science and technology, multi-AGV cooperation and multi-algorithm integration will become the development direction of intelligent warehouse AGV path planning.