Keywords

1 Introduction

Automated guided vehicle (AGV) is playing an increasingly important role in the area of logistics due to its high efficiency for material delivering among workstations [1]. The applications of AGV systems face several issues: AGVs number determining, path planning and constraint exerting [2,3,4]. However, the path planning is most important in ensuring an efficient flow of materials during the storage process.

Several methodologies had been proposed to optimize the AGV path planning distance, such as an improved Dijkstra algorithm was utilized to solve the shortest route [5, 6], a space-time A* algorithm was developed to handle the path planning at the lower 1evel [7, 8], an improved genetic algorithm was investigated to optimize the running path [9, 10], and an improved ant colony algorithm was implemented to avoid local optimization and accelerating convergence speed [11]. Apparently, there existing various constraints in AGV path planning: collision-free constraints [12,13,14], time window constraints [15, 16], and distance constraints [17, 18]. For this reason, Mohammad Saidi-Mehrabad et al. built a mathematical model which was composed of Conflict-Free Routing Problem (CFRP) and Job Shop Scheduling Problem (JSSP) to minimize the total completion time [19], Sun Maomao and Kuang Bing discussed a collision free path planning method based on time window for AGV [20], and Wang Dingxin introduced artificial neural network into Q-learning algorithm to find an optimal path without collision by itself through independent learning [21].

However, the genetic algorithm, ant colony algorithm and neural network algorithm have the problem of slow convergence speed. In addition, the Dijkstra and A* algorithm are easy to fall into local optimal solutions. Therefore, an improved D*lite algorithm for AGV path planning is presented to obtain the total shortest path.

2 Methodology

2.1 Model Assumption

There is an AGV in the logistics warehouse, which is responsible for delivering materials to N locations (N ≥ 1). For the distribution, the following assumptions are considered for describing the details.

  1. 1)

    AGV travels one route with the predefined path and the fixed speed.

  2. 2)

    AGV starts from the same starting point and comes back to the starting point.

  3. 3)

    Only one delivering task for AGV each time.

  4. 4)

    Loading/unloading time is negligible and traveling path is clean and smooth.

  5. 5)

    AGV is always full of power during delivering materials.

  6. 6)

    AGV cannot be interrupted or recalled during delivering materials.

The work diagram can be stated as Fig. 1 shows:

Fig. 1.
figure 1

Work diagram of AGV based on grid map

Full size image

Figure 1 shows that the green grid is the starting area, the red grids are shelves or obstacles, the blue grids are pick-up locations, and Pij is the traveling route between i and j.

2.2 Model Establishment

The modeling process of the improved D*lite algorithm can be divided into three steps: pre-planning, real-time planning and reach the goal, as Fig. 2 shows.

Fig. 2.
figure 2

Schematic diagram of improved D*lite algorithm

Full size image

The improved D*lite algorithm can be utilized to solve the goal-directed navigation problem in unknown terrain. The terrain is modeled as an eight-connected graph. The costs of its edges are initially one. They change to infinity when the AGV discovers that they cannot be traversed. One can implement the AGV-navigation strategy by applying D* Lite to this graph with \(s_{start}\) being the current vertex and \(s_{goal}\) being the goal vertex [22].

  1. (1)

    In the pre-planning stage

Dijkstra algorithm is used to compute the local shortest path from start vertex to the goal vertex. And the topological map based on the grid graph is shown in Fig. 3:

Fig. 3.
figure 3

Topological map based on the grid graph

Full size image

The vertex \(v_1\) can be labeled as P, so \(d(v_1 ) = 0\), and the vertex \(v_j\) (j = 2, 3, …, n) can be labeled as T, so \(d(v_j ) = l_{1j}\).

If \(d(v_{j0} ) = l_{1j}\), its label T will be updated with label P, and other vertices with label T will be recalculated to select the smallest one as a new label T. Repeat the above steps until all target vertices have been labeled as P. Ultimately, the local shortest path can be computed by using Matlab software.

  1. (2)

    In the real-time planning stage

The improved D*lite algorithm is introduced to compute shortest path through backward searching from the goal vertex to the start vertex until the target vertex is found at this stage [23]. Therefore, the objective function is shown in Invariant (1):

$$ g(s) = \left\{ {\begin{array}{*{20}{l}} {0,}&{if\;s = {s_{start}}}\\ {{\mathop{\min} \nolimits_{s \in pred(s)}}(c(s^{\prime},s) + g(s^{\prime}),}&{otherwise}\end{array}} \right. $$
(1)

where S is the finite set of vertices of the graph. \(pred(s) \subseteq S\) denotes the set of predecessors of vertex \(s \in S\). \(0 < c(s^{\prime},s) \le \infty\) denotes the cost of moving from vertex s to vertex \(s^{\prime}\). \(g(s)\) denotes the length of a shortest path from \(s_{start}\) to s.

The rhs-values are one-step previous values based on the g-values and potentially better informed than the g-values. They always satisfy the following relationship as Invariant (2) shows:

$$ rhs(s) = \left\{ {\begin{array}{*{20}{l}}{0,}&{if\;s = {s_{start}}}\\ {{\mathop{\min} \nolimits_{s \in succ(s)}}(c(s^{\prime},s) + g(s^{\prime})),}&{otherwise}\end{array}} \right. $$
(2)

In the Invariant (2), \(succ(s) \subseteq S\) denotes the set of successors of vertex \(s \in S\). A vertex is called locally consistent if its g-value equals its rhs-value, otherwise it is called locally inconsistent. If all vertices are locally consistent, then the g-values of all vertices equal their respective start distances. Instead, it uses the heuristic approaches to focus the search and updates only the g-values that are relevant for computing a shortest path (Invariant 3).

$$ h(s,s_{start} ) = \left\{ {\begin{array}{*{20}l} {0,} \hfill & {if\;s = s_{start} } \hfill \\ {c(s,s^{\prime}) + h(s^{\prime},s_{goal} ),} \hfill & {otherwise} \hfill \\ \end{array} } \right. $$
(3)

The priority of a vertex in the priority queue is always the same as its key, which is a vector with two components (Invariant 4 & 5):

$$ k_1 (s) = \min (g(s),rhs(s)) + h(s_{start} ,s) + k_m $$
(4)
$$ k_2 (s) = \min (g(s),rhs(s)) $$
(5)

In the Invariant (4), km is a variable need to get added up if the AGV moves again and then detects cost changes again. It is usually set to 0 during initialization. Keys are compared according to a lexicographic ordering. The improved D*lite algorithm expands the vertex in the priority queue with the smallest key.

  1. (3)

    Reach the goal

Finally, the variables and parameters are input into the simulation model. After Compute Shortest Path () returns, one can follow a shortest path from \(s_{goal}\) to \(s_{start}\) by moving from the current vertex s to any successor \(s^{\prime}\) that minimizes \(c(s,s^{\prime}) + g(s^{\prime})\) until \(s_{goal}\) is reached. It means that the path planning has been completed.

2.3 Model Solution

The solution process of improved D*lite algorithm is drawn in Fig. 4.

Fig. 4.
figure 4

Solution process of improved D*lite algorithm

Full size image

3 Experiments

3.1 Case Description

A logistics warehouse has a length of 11 m and a width of 8 m. There are seven pick-up locations (N1–N7), but only one AGV can be utilized to handle materials with 15 m/min in the logistics warehouse. S1 is the starting area of AGV, and E1 is the ending location (see Fig. 5).

Fig. 5.
figure 5

Grid numbering graph of warehouse

Full size image

In Fig. 5, each space is a 1 × 1 m2, and the green grid is the starting area of AGV, red grids are shelves or obstacles, blue grids are pickup locations, yellow grid is the ending position, and white areas are free grids without obstacles.

3.2 Pre-planning for AGV Routing

The topological map of AGV routing is generated with grid graph (see Fig. 6). And the local shortest path from start vertex to the goal vertex can be computed by using Dijkstra algorithm (Red line is the shortest path).

Fig. 6.
figure 6

Topological map of AGV routing

Full size image

Figure 6 shows that, the adjacent matrix D is established according to the direct distance among vertices.

$$ D = \left[ {\begin{array}{*{20}c} \infty & 5 & 2 & 3 & \infty & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & 3 & \infty & \infty & \infty \\ \infty & \infty & \infty & 4 & 4 & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & 2 & \infty \\ \infty & \infty & \infty & \infty & \infty & 3 & 3 & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 3 \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 3 \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \end{array} } \right] $$

Next, the weighted adjacent matrix is inserted into Matlab software, and the simulation results are as follows.

$$ path\_all = \;\left[ {\begin{array}{*{20}c} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 1 & 3 & 5 \\ 0 & 0 & 0 & 0 & 1 & 3 & 5 & 6 \\ 0 & 0 & 0 & 0 & 0 & 1 & 4 & 7 \\ 0 & 0 & 0 & 0 & 1 & 4 & 7 & 8 \\ \end{array} } \right] $$

Finally, the local shortest path is: 0-1-1-1-3-5-4-7.

3.3 Real-Time Planning for AGV Routing

In the real-time planning stage, a simulation model is built to compute the total shortest path with Matlab software based on the improved D*lite algorithm. In simulation, S is the finite set of vertices (s = 1, 2, …, 7). After running the simulation, the total shortest path is marked in blue, and its length is 10 m (see Fig. 7).

Fig. 7.
figure 7

The total shortest path of AGV

Full size image

3.4 Experimental Results

The simulation results for two algorithms are drawn in Fig. 8 and Fig. 9.

Fig. 8.
figure 8

Dijkstra algorithm

Full size image
Fig. 9.
figure 9

Improved D*lite algorithm

Full size image

Figure 8 shows that, at 540 iterations, the maximum distance of AGV is 12 m for the Dijkstra algorithm.

Figure 9 shows that, at 270 iterations, the maximum distance of AGV is 10 m for the improved D*lite algorithm.

Table 1. Comparison of Dijkstra and Improved D*lite algorithm
Full size table

From Table 1, it can be seen that the improved D*lite algorithm has achieved several optimizations, such as the convergence speed is 50% faster, the shortest path and duration are reduced by 16.7%.

4 Conclusion

AGV is playing a key role in the area of distribution logistics because of its efficient, accurate and flexible for material handling. However, the traditional AGV path planning algorithm has slow convergence speed and is easy to fall into local optimal solution. Therefore, an improved D*lite algorithm is developed by combining Dijkstra algorithm and D*lite algorithm to solve the problem. In the improved D*lite algorithm, the total shortest path in AGV delivery task can be computed through backward searching. And the experimental results show that the AGV path distance and convergence speed are improved by using the improved D*lite algorithm.

In the following steps, we are going to study the path planning and task scheduling for multiple AGVs with the improved D*lite algorithm.