# AGVs Route Planning Based on Region-Segmentation Dynamic Programming in Smart Road Network Systems

Authors: Zheng Zhang; Juan Chen; Qing Guo
Journal: Scientific Programming
 (2021)

---

## Abstract

In this paper, a route-planning approach is proposed based on the region-segmentation Dynamic Programming (DP) algorithm for Automated Guided Vehicles (AGVs) in large Smart Road Network Systems (SRNSs) to deal with the problem of low route computation efficiency of the classical DP algorithm. We introduced an improved Markov Decision Process (MDP) to describe SRNSs, in which the SRNSs are divided into several regions according to the AGVs’ start nodes and their goal nodes to improve the route-planning efficiency. Moreover, the route with the minimum number of turns is selected to reduce the system running time and energy cost in the following way: first, all the equidistant shortest routes are acquired from the AGVs’ start nodes to their goal nodes using the improved DP algorithm; then, the routes are screened by calculating the angular deviation between all feasible routes and AGVs’ initial directions, and the route with the fewest number of turns is taken as the shortest-time route. The simulation results verified that the proposed method can effectively solve the route-planning problem of AGVs in current SRNSs.


---

## Body

## 1. Introduction

Smart Road Network Systems (SRNSs) are important parts of the Smart World. Automated Storage and Retrieval Systems (AS/RSs) and Container Terminal Systems are typical Industry 4.0 application scenarios. Automated Guided Vehicles (AGVs) are the main tools, which enable automatic access to goods transportation without human labor. With the development of Smart City and Internet of Things technology, the route-planning algorithms of AGVs in SRNSs are commonly used not only in logistics industries and smart factories but also in intelligent transportation systems [1], energy transmission systems [2], and even network planning [3]. With the wide application of AGVs route planning, the goal of route planning is not only to find the route with the shortest distance from AGVs’ start nodes to their goal nodes but also to minimize the system operating time and reduce energy cost. Moreover, the speed of the route-planning algorithm is also important. Therefore, AGVs route-planning problem in SRNSs has been widely studied.The AGVs route planning in SRNSs belongs to the single-source shortest routing problem, and it has similarities with trajectory optimization. They both can be solved using graph search algorithms [4, 5], sampling-based methods [6], and intelligent algorithms [7]. Dijkstra’s algorithm is a classical route search algorithm, which has a simple structure and is robust and easy to implement, and it can meet requirements in practical scenarios. However, Dijkstra’s algorithm belongs to Breadth-First Search (BFS), and thus it is not suitable for applying in scenarios with high real-time requirements [8–10]. In addition, when there are multiple equidistant shortest routes between the start node and the goal node, Dijkstra’s algorithm can find only one of them. Even though there is improved Dijkstra’s algorithm [11] that can obtain all equidistant shortest routes through iterations, the time complexity of Dijkstra’s algorithm is On2, where n indicates the number of nodes in SRNSs. Therefore, it is not suitable for route planning in large SRNSs. AGVs interact with SRNSs all the time and an AGV has state st at each time t. An AGV takes action a on state st, and then it transforms to a new state st+1 by taking reward rt+1, and a sequence (i.e., st-1, at-1, rt, st, at, rt+1...) is built by repeating the operation. The process of computing the shortest routes for AGVs is called the sequence decision process, and Markov Decision Process (MDP) is a typically formulaic method for it. SRNSs described in this paper consist of several regularly arranged nodes, and the workflow can be described using MDP. However, we cannot completely copy the classical MDP to model the environment of the characteristics of different SRNSs.Dynamic Programming (DP) algorithm is a branch of operations research, which was proposed by Bellman et al. [12] in the 1950s. DP algorithm is a method for solving optimization problems of the multistep decision process. DP can transform multistage problems into a series of single-stage problems [13], and it is suitable for solving optimization problems in large-scale environments. DP algorithm is the basic of Reinforcement Learning (RL) [14], and RL is an unsupervised algorithm based on the principles of reward and punishment. However, it is suitable for solving model-free problems, an AGV does not know which state has the bigger reward, and it needs to find the optimal policy to the goal state through trial and error [15]. Moreover, the classical DP algorithm iterates the sample set by randomly selecting starting point until the value function approaches the optimal policy. With the expansion of the scales of route-planning environments, the training time can become larger, and the computation amount of the DP algorithm will increase exponentially with the increasing number of nodes [16].With the development of new communication technologies (e.g., 5G) and the increase of nodes’ number in SRNSs, the real-time requirements for AGVs route-planning algorithm are becoming higher, and the classical DP algorithm is not suitable for the current development of Smart World. We propose a route-planning approach based on the region-segmentation DP algorithm for AGVs in SRNSs to address the low-efficiency problem of the classical DP algorithm. Because the classical MDP fails to accurately model the current SRNSs, we propose an improved MDP model for SRNSs. Since the number of samples is one of the important factors that affect the efficiency of the algorithm, a region-segmentation-based DP algorithm is proposed. Firstly, SRNSs are divided into several regions according to AGVs’ start nodes and their goal nodes, and the objective is to reduce the number of training samples. Then, each node is assigned a value, and the DP algorithm is used to compute the value function of each region, and the objective is to find all equidistant shortest routes from the AGVs’ start nodes to their goal nodes. Because AGVs can take more time and energy to turn, we introduce the following steps to determine routes with the least turns: (a) screening routes by calculating the angle deviation between all candidate routes and an AGV’s initial direction and (b) choosing a route among remaining routes with the fewest number of turns and considering it the optimal route for the AGV. Moreover, we design different route-planning strategies according to whether an AGV is loaded or not, which improves the flexibility and efficiency of SRNSs, and the more nodes in the SRNSs, the more efficient our approach.


## 2. Related Works

The AGVs route-planning problem can be solved using Dijkstra’s algorithm [17], A∗ algorithm [18], D∗ algorithm [19], Probabilistic Roadmap (PRM) [20], Rapid Random Tree (RRT) [21], Artificial Potential Field (APF) [22], neural network [23], genetic algorithm [24], and ant colony algorithm [25]. Dijkstra’s algorithm is a classical shortest route search algorithm, and it is simple and stable for performance. Guo et al. [11] improved Dijkstra’s algorithm and found the shortest routes with the least distance and time consumption for AGVs in AS/RSs. Li et al. [26] assumed that all obstacles were convex and found the shortest routes for AGVs without collision. However, the above achievements were all obtained in small-scale environments without considering the case of large-scale SRNSs (i.e., a large number of nodes and large size of the space). With the rapid development of SRNSs, the calculation amount of AGVs route planning will increase exponentially. But classical Dijkstra’s algorithm does not consider the scenarios with a large number of nodes, and the system may be locked due to too much computation.Yuan et al. [27] proposed Approximate Dynamic Programming (ADP), and they applied it to crane scheduling to reduce the operation time of the AS/RSs. Novoa et al. [28] focused on Vehicle Routing Problem (VRP) from the perspective of ADP, and they proved that a DP-based algorithm could be applied to vehicle routing planning. Cimen et al. [29] proposed a vehicle routing optimization algorithm by combining ADP and MDP. Bahlawan et al. [30] introduced a method of system operation management and energy optimization based on the DP algorithm to minimize the energy cost of factories. Horiguchi et al. [31] focused on the routing problem of network packets, and they redefined the energy function by combining the DP algorithm and neural network. They proposed a method to find the optimal balance between queues’ length and the routes’ distance. Although many achievements have proved that the DP algorithm can be used to solve optimization problems in various situations, the classical DP algorithm needs to iterate the values of each node in the whole space many times until a stable and optimal policy is obtained. To reduce the computing time of DP, Ulmer et al. [32] proposed an offline value function prediction method, which introduced MDP into state space and combined action space with reward information. Desai et al. [33] proposed a preprocessing method of a random dynamic network according to vehicles’ starting time and location. But they failed to fundamentally solve the problem of longer DP algorithm iteration time.


## 3. Rasterizing the SRNS as the Model

There are a large number of nodes arranged according to the regular form of rows and columns in SRNSs and nodes and the lines between nodes (i.e., the driving paths of AGVs) are typically presented as a regular rectangle. Therefore, SRNSs can be rasterized, and the grids’ locations can be stored with spatial coordinates. Figures1(a)–1(c) are m × n SRNSs constructed using grid methods [34], where m and n represent the numbers of rows and columns of the SRNSs, respectively. We establish the Cartesian coordinate system of the SRNSs: the upper-left corner is selected as the origin (x = 0, y = 0), the lower-right corner defines the workspace size (x = n − 1, y = m − 1), and each node corresponds to a coordinate (a, b) (a ≤ n − 1, b ≤ m − 1). Grey grids represent obstacle nodes, white grids indicate the nodes that are available for AGVs, and numbers in grids indicate the number of nodes (i.e., the number of nodes starting from (x = 0, y = 0) and marked as 1, 2, 3, …, n). Red, green, and blue solid squares represent the start nodes of AGVs, and solid circles of the corresponding color represent their goal nodes. The distance between every two adjacent nodes is equal and the SRNS is bidirectional (i.e., AGVs can travel bidirectionally), and each node can only be occupied by one AGV. The size of every obstacle is the same in SRNSs and the number of grids AGVs passed represents the travel distance for AGVs.Figure 1
Rasterize large SRNSs as a model. (a) Horizontal row SRNSs; (b) vertical column SRNSs; (c) fish-bone SRNSs.
(a)(b)(c)Figures1(a) and 1(b) are commonly used SRNSs (e.g., AS/RSs), in which the shelves are arranged according to the rules of row and column, and there is a channel on both sides of each row (or column) of shelf for AGVs access. Figure 1(c) shows recently presented SRNSs due to the rapid development of the Smart World. In these fish-bone SRNSs, shelves are arranged on both sides of the main diagonal of the SRNSs, since it is inconvenient for AGV access and the signal may be blocked, and it can lead to system deadlock of SRNSs; this environment model has no practical application.


### 3.1. General Markov Decision Process Framework

Markov Decision Process (MDP) is a quintuple (i.e.,S,A,P,R,γ), where S is the finite states set, A is the actions set, and P is the state transition probability matrix. Given the current state s and the next state s′, the state transition probability (i.e., Pss′=PSt+1=s′|St=s) represents the transition probability from state s to state s′. R is the rewards set; γ is the discount factor, which denotes that the influence of the goal state on each state is gradually weakened with the increase of distance between a node and the goal node, γ∈0,1. There are two kinds of rewards of R set: (1) immediate reward Rt, which denotes the expectation of rewards from state s to state s′, that is, Rt=ERt+1|St=s, and (2) accumulated reward Gt, which denotes the weighted sum of each immediate reward from the start state to the goal state.(1)Gt=Rt+1+γRt+2+…=∑k=0∞γkRt+k+1.


### 3.2. The Markov Decision Process in SRNSs

State value functionVs represents the expectation of accumulated reward under state s:(2)Vs=EGt|St=s.Bellman equation [12] is the core of all MDP-based algorithms. AGVs can obtain the best route from start nodes to goal nodes according to Bellman equation. The derivation process of the Bellman equation is as follows:(3)Vs=EGt|St=s=ERt+1+γRt+2+γ2Rt+3…|St=s=ERt+1+γRt+2+γRt+3…|St=s=ERt+1+γGt+1|St=s=ERt+1+γVSt+1|St=s.In equation (3), the value of state s consists of (i) the expectation of immediate reward and (ii) the expectation of the state’s value for the next moment. State-policy transition probability Ps,s′π=∑a∈Aπa|sPs,s′a represents the probability of an AGV transforming from state s to state s′.


#### 3.2.1. Smart Road Network System-Reward Matrix (SRNS-RM)

AGVs can obtain different immediate rewards at different nodes, and the reward/penalty obtained by AGVs is defined as follows: (1) if AGVs enter grey solid grids (i.e., obstacle nodes), they will get penalty: −r, where r is a positive integer; (2) if AGVs enter white grids, they will get penalty: −ε, where ε is a positive integer and ε≪r; (3) if AGVs reach the goal node, they can obtain reward +r2. Given an m × n SRNS, where m indicates the number of rows, that is, the number of nodes in a column, and n indicates the number of columns, that is, the number of nodes in a row, the SRNS-RM is(4)SRNS−RM=r11=−εr12=−εr13=−r…r1n=−εr21=−εr22=−rr23−r…r2n=−εr31=−εr32=−εr33=−r…r3n=−ε……………rm1=−εrm2=−εrm3=−ε…rmn=+r2.In equation (4), the dimension of SRNS-RM is m × n, which is the same as the SRNS. The elements (i.e., rij) in SRNS-RM (i=1,2…m; j=1,2…n) indicate the rewards of an AGV reaching nodes in row i and column j. Consider that there are four obstacle nodes in the SRNS, that is, SRNS-RM13 = −r, SRNS-RM22 = −r, SRNS-RM23 = −r, and SRNS-RM33 = −r.


#### 3.2.2. Smart Road Network System-Transition Probability Matrix (SRNS-TPM)

The adjacencies of nodes in SRNSs are as follows: (1) there are no upper adjacent nodes for the nodes on the upper edge but only left, lower, and right adjacent nodes; (2) there are no left adjacent nodes for the node on the left edge but only top, right, and bottom adjacent nodes; (3) there are no lower adjacent nodes for the node on the lower edge but only upper, left, and right adjacent nodes; (4) there are no right adjacent nodes for the node on the right edge but only top, left, and bottom adjacent nodes; (5) there are four adjacent nodes except for the nodes on edges. In principle, the probabilities are the same for an AGV entering any adjacent node in anm × n SRNS, that is, Pij=PSt+1=j|St=i=δ, where 0≤δ≤1. The SRNS-TPM is(5)SRNS−TPM=P11P12P13…P1nP21P22P23…P2nP31P32P33…P3n……………Pm1Pm2Pm3…Pmn.In equation (5), Pij indicates each element of SRNS-TPM, where i indicates AGV’s current state (i.e., St), and j indicates its next state (i.e., St+1). The dimension of SRNS-TPM is m × n, which is the same as the SRNS and P11=P12=⋯=Pmn=δ; that is, the probability of AGV entering each adjacent node is the same.


#### 3.2.3. Criteria of the Optimal Policy Selection

The objective of the classical MDP is to find the optimal policy that can reach the goal to maximize the accumulated rewardGt (see equation (2)). However, AGVs route planning in SRNSs is a multiobjective combinatorial optimization problem. On the one hand, the total routes’ length should be minimized; on the other hand, total routes’ length should be minimized, and AGVs’ traveling time should be the least. Therefore, the criteria for choosing the optimal policy need to be modified.When an AGV enters a node, it uploads coordinates of the current node to the server through 5G, Bluetooth, or other wireless technologies, so that the server can know the location of the AGV in SRNSs. We ignore the size of nodes in SRNSs, and consider that the distance between every two adjacent nodes isLn; the longitudinal length of the AGV is Lc; and the traveling speed of the AGV is fixed as v. When the head of the AGV enters a node, the node is occupied, and the node is released when the tail of the AGV leaves. As shown in Figure 2, the time for the AGV to pass through every two adjacent nodes is tc=Ln+Lc/v.Figure 2
Time of AGVs passing through every two adjacent nodes.In many SRNSs (e.g., AS/RSs), an AGV can only travel in four directions, north, east, south, and west, and can only turn at nodes. It requires deceleration, stopping, autobiography, and acceleration, and the total time for turning istu. The route length from the start node to the goal node is shown in equation (6). Given that the starting time of an AGV is 0 s, the total time for the AGV traveling to the goal node is shown in equation (7).(6)L=nc−1×Ln,(7)T=nc−1×tc+nu×tu.In equations (6) and (7), nc denotes the total number of nodes in the route and nu denotes the number of turns in the route.Given that the computing time of the server ists, the criteria of the optimal policy selection in SRNSs are as follows:(8)mintπs,(9)minLπ=nc−1×Ln,(10)minπT=nc−1×tc+nu×tu,(11)s.t.ts>0nc>1andLn>00≤nu≤nptu>0np=1,2,...,n.Equation (8) indicates that we should reduce route computing time of the server; equation (9) indicates that we should shorten routes’ distance of AGVs; equation (10) indicates that we should minimize the total travel time of AGVs. In equation (11), np denotes the number of nodes in an AGV’s route. Due to the fewer turns in AGVs’ routes, with less energy cost of the SRNSs, reducing the number of turns in AGVs routes can reduce the energy cost.


### 3.3. AGVs Route-Planning Approach in SRNSs

The flowchart of AGVs route-planning approach proposed in this paper is shown in Figure3, which consists of four parts: (1) route-planning region segmentation; (2) computing all shortest routes by training value functions of the regions; (3) obtaining the feasible routes according to AGVs’ status; and (4) selecting collision-free routes with the shortest length and the least travel time.Figure 3
Flowchart of the AGVs route-planning approach proposed in this paper.


#### 3.3.1. Route-Planning Region Segmentation

The most effective way to speed up training is to reduce the number of samples. We here proposed a region-segmentation-based DP algorithm, in which the SRNSs are divided into regions according to AGVs’ start nodes and their goal nodes. The objective is to accelerate the convergence of the DP algorithm by excluding irrelevant nodes. Given the coordinates of an AGV’s start nodeXs,Ys and the goal node Xg,Yg, the left boundary of an SRNS Xl and the right boundary Xr, the upper left coordinates of the AGV’s route-planning region XAGViul,YAGViul, the upper-right coordinates XAGViur,YAGViur, the coordinates of the lower-left corner XAGVidl,YAGVidl, the coordinates of the lower right corner XAGVidr,YAGVidr, the length of the region along the x-direction Lrow, and the length along the y-direction Lcol, the AGVs’ route-planning region is defined as follows:(i)
IfXg−Xl<Xr−Xg, that is, an AGV’s goal node is closer to the left boundary of the SRNS, then(12)XAGViul,YAGViul=Xl,minYs,Yg,(13)XAGViur,YAGViur=maxXs,Xg,minYs,Yg,(14)XAGVidl,YAGVidl=Xl,maxYs,Yg,(15)XAGVidr,YAGVidr=maxXs,Xg,maxYs,Yg,(16)Lrow=maxXs,Xg−Xl,(17)Lcol=Yg−Ys.(ii)
IfXg−Xl>Xr−Xg, that is, an AGV’s goal node is closer to the right boundary, then(18)XAGViul,YAGViul=minXs,Xg,minYs,Yg,(19)XAGViur,YAGViur=minXs,Xg,maxYs,Yg,(20)XAGVidl,YAGVidl=Xr,minYs,Yg,(21)XAGVidr,YAGVidr=Xr,maxYs,Yg,(22)Lrow=Xr−maxXs,Xg,(23)Lcol=Yg−Ys.The conventional region-segmentation methods only focus on locations of AGVs’ start nodes and their goal nodes, but we take the relationship between them and the left (and right) boundaries of SRNSs into consideration. Our approach can reduce the number of samples without losing the accuracy of route planning. As shown in Figure4, given that the start node of an AGV is node 43 (x = 3, y = 5) and the goal node is node 20 (x = 4, y = 2), the blue line indicates the feasible route from the start node to the goal node; the yellow shaded area represents the route-planning region obtained using the conventional region-segmentation methods, which does not include the feasible route, and the area in the red box indicates the region in our approach, which contains the feasible route.Figure 4
Conventional and improved region segmentation.


#### 3.3.2. Training Value Function of the Route-Planning Region

There are two kinds of commonly used DP algorithms: policy iteration-based DP algorithm and value iteration-based DP algorithm. The time of computing route using the DP algorithm based on policy iteration and value iteration in anm×n SRNS (see Figure 1(a)) is shown in Figure 5, where the blue line denotes the training time of the DP algorithm based on policy iteration, and the red line denotes that of the DP algorithm based on value iteration.Figure 5
Curve of convergences between the DP algorithms based on policy iteration and value iteration.As can be seen from Figure5, the training time of the DP algorithm based on value iteration is smaller than that of the DP algorithm based on policy iteration. In this scenario, the average time for route computing is improved by nearly 97.39%, and when the scales of SRNSs become larger, the difference of computing time between them becomes bigger. We employ the value iteration-based DP algorithm because it can adjust the policy while training rather than after the value function converges, which greatly reduces the number of iterations and significantly improves the efficiency of the algorithm.The calculation of the optimal value function (i.e.,V∗s) is a recursive process (refer to equation (3)). We need to evaluate the rewards of all adjacent states based on the current state, and the state with the largest reward is taken as the next state of the AGV. The method of computing the relationship between the current node and all adjacent nodes is(24)VT+1s=∑s+1pst+1|st,atratst+1+γ×VTst+1,wherepst+1|st,at indicates the probability of taking action at to transfer to an adjacent state st+1 based on the current state st; ratst+1 is the reward of taking action at to transfer to state st+1; γ is the discount factor, where γ∈0,1; VTst+1 is the value of each state adjacent to state st.Without considering obstacle nodes in SRNSs, the probability is the same for an AGV traveling to surrounding nodes; that is,pst+1|st,at=1/4 and γ=1. Equation (24) can be rewritten as(25)VT+1=14×−1+1×VuT+−1+1×VdT+−1+1×VlT+−1+1×VrT.In equation (25), VuT,VdT,VlT, and VrT denote the state values of upper, lower, left, and right adjacent nodes of AGV’s current nodes, respectively.


#### 3.3.3. Route-Planning Strategies Based on Status of AGVs

There are multiple obstacles on AGVs’ routes, and the route-planning methods of AGVs in different status can be different. Taking AS/RSs as an example [35], as shown in Figure 6, the height of the bottom shelf from the ground is 75 cm, and the height of each no-load AGV is 50 cm. If an AGV needs to load, the tray on the AGV will be lifted to hold the bottom to lift the shelf. Because the height from the bottom shelf to the ground is greater than the height of a no-load AGV, a no-load AGV can pass under the shelve, whereas a loaded AGV (i.e., an AGV that is carrying a shelve) can not. So the loaded AGVs should avoid collision with not only other AGVs but also shelves placed above the nodes.Figure 6
Height of bottom shelf and no-load AGV in AS/RSs.If AGVs are loaded, the route-planning method is as follows: (1) storing locations of obstacle nodes into a listobstacle_list = [ ] while initializing the environment; (2) repeating equation (25) to compute the value function of the route-planning regions and obtaining all feasible routes from AGVs’ start nodes to their goal nodes; (3) comparing nodes in all feasible routes with nodes in obstacle_list = [ ] and deleting the routes that contain obstacle nodes; and (4) calculating the length of each collision-free route and storing routes with the minimum length. If AGVs are no-load ones, it is not necessary to establish obstacle_list = [ ] while initializing the environment, and we need not compare feasible routes to obstacle_list = [ ] but only to calculate the length of all feasible routes.


#### 3.3.4. Obtaining Collision-Free Routes with the Shortest Length and the Least Travel Time

SRNSs are shaped like chessboards, and AGVs can travel in four directions: north, east, south, and west. Therefore, there may be more than one shortest-distance route from AGVs’ start nodes to their goal nodes. In some large SRNSs (e.g., AS/RSs), AGVs can only turn at nodes, and the time of the process becomes longer with the increase of AGVs’ turning angles. The fewer angles, the smaller the time cost and the higher the system efficiency. We can find routes with the shortest travel time for AGVs through the following steps:Step 1.
Comparing the angles of each feasible route with AGVs’ initial directions to determine their departure routes:(26)θinit=minθ1start−θAGVstart,θ2start−θAGVstart,θ3start−θAGVstart,θ4start−θAGVstart.
In equation (26), θinit indicates the departure angle of AGVs from start nodes. We take the southward as 0° and start nodes as the origin; θ1start indicates the angle of route 1, θ2start indicates the angle of route 2, θ3start indicates the angle of route 3, and θ4start indicates the angle of route 4; θAGVstart indicates the angle of AGVs at start nodes.Step 2.
Computing the routes with the shortest travel time, that is, the routes with the fewest turns: traversing each node of feasible routes obtained in Step 1, deleting routes that contain nodes inobstacle_list = [ ], and then judging whether a node is a turn or not in remaining routes. The method of determining whether a node is a turn or not is as follows: considering the X and Y coordinates of upstream and downstream nodes, if a node satisfies equation (27), it is a turn:(27)Xi+1−Xi≠Xi−Xi−1orYi+1−Yi≠Yi−Yi−1.
In equation (27), i denotes the number of the current node, Xi is the X-coordinate of the current node, and Yi is the Y-coordinate; i+1 denotes the number of the downstream node, Xi+1 is the X-coordinate, and Yi+1 is the Y-coordinate; i−1 denotes the number of the upstream node, Xi−1 is the X-coordinate, and Yi−1 is the Y-coordinate.


## 3.1. General Markov Decision Process Framework

Markov Decision Process (MDP) is a quintuple (i.e.,S,A,P,R,γ), where S is the finite states set, A is the actions set, and P is the state transition probability matrix. Given the current state s and the next state s′, the state transition probability (i.e., Pss′=PSt+1=s′|St=s) represents the transition probability from state s to state s′. R is the rewards set; γ is the discount factor, which denotes that the influence of the goal state on each state is gradually weakened with the increase of distance between a node and the goal node, γ∈0,1. There are two kinds of rewards of R set: (1) immediate reward Rt, which denotes the expectation of rewards from state s to state s′, that is, Rt=ERt+1|St=s, and (2) accumulated reward Gt, which denotes the weighted sum of each immediate reward from the start state to the goal state.(1)Gt=Rt+1+γRt+2+…=∑k=0∞γkRt+k+1.


## 3.2. The Markov Decision Process in SRNSs

State value functionVs represents the expectation of accumulated reward under state s:(2)Vs=EGt|St=s.Bellman equation [12] is the core of all MDP-based algorithms. AGVs can obtain the best route from start nodes to goal nodes according to Bellman equation. The derivation process of the Bellman equation is as follows:(3)Vs=EGt|St=s=ERt+1+γRt+2+γ2Rt+3…|St=s=ERt+1+γRt+2+γRt+3…|St=s=ERt+1+γGt+1|St=s=ERt+1+γVSt+1|St=s.In equation (3), the value of state s consists of (i) the expectation of immediate reward and (ii) the expectation of the state’s value for the next moment. State-policy transition probability Ps,s′π=∑a∈Aπa|sPs,s′a represents the probability of an AGV transforming from state s to state s′.


### 3.2.1. Smart Road Network System-Reward Matrix (SRNS-RM)

AGVs can obtain different immediate rewards at different nodes, and the reward/penalty obtained by AGVs is defined as follows: (1) if AGVs enter grey solid grids (i.e., obstacle nodes), they will get penalty: −r, where r is a positive integer; (2) if AGVs enter white grids, they will get penalty: −ε, where ε is a positive integer and ε≪r; (3) if AGVs reach the goal node, they can obtain reward +r2. Given an m × n SRNS, where m indicates the number of rows, that is, the number of nodes in a column, and n indicates the number of columns, that is, the number of nodes in a row, the SRNS-RM is(4)SRNS−RM=r11=−εr12=−εr13=−r…r1n=−εr21=−εr22=−rr23−r…r2n=−εr31=−εr32=−εr33=−r…r3n=−ε……………rm1=−εrm2=−εrm3=−ε…rmn=+r2.In equation (4), the dimension of SRNS-RM is m × n, which is the same as the SRNS. The elements (i.e., rij) in SRNS-RM (i=1,2…m; j=1,2…n) indicate the rewards of an AGV reaching nodes in row i and column j. Consider that there are four obstacle nodes in the SRNS, that is, SRNS-RM13 = −r, SRNS-RM22 = −r, SRNS-RM23 = −r, and SRNS-RM33 = −r.


### 3.2.2. Smart Road Network System-Transition Probability Matrix (SRNS-TPM)

The adjacencies of nodes in SRNSs are as follows: (1) there are no upper adjacent nodes for the nodes on the upper edge but only left, lower, and right adjacent nodes; (2) there are no left adjacent nodes for the node on the left edge but only top, right, and bottom adjacent nodes; (3) there are no lower adjacent nodes for the node on the lower edge but only upper, left, and right adjacent nodes; (4) there are no right adjacent nodes for the node on the right edge but only top, left, and bottom adjacent nodes; (5) there are four adjacent nodes except for the nodes on edges. In principle, the probabilities are the same for an AGV entering any adjacent node in anm × n SRNS, that is, Pij=PSt+1=j|St=i=δ, where 0≤δ≤1. The SRNS-TPM is(5)SRNS−TPM=P11P12P13…P1nP21P22P23…P2nP31P32P33…P3n……………Pm1Pm2Pm3…Pmn.In equation (5), Pij indicates each element of SRNS-TPM, where i indicates AGV’s current state (i.e., St), and j indicates its next state (i.e., St+1). The dimension of SRNS-TPM is m × n, which is the same as the SRNS and P11=P12=⋯=Pmn=δ; that is, the probability of AGV entering each adjacent node is the same.


### 3.2.3. Criteria of the Optimal Policy Selection

The objective of the classical MDP is to find the optimal policy that can reach the goal to maximize the accumulated rewardGt (see equation (2)). However, AGVs route planning in SRNSs is a multiobjective combinatorial optimization problem. On the one hand, the total routes’ length should be minimized; on the other hand, total routes’ length should be minimized, and AGVs’ traveling time should be the least. Therefore, the criteria for choosing the optimal policy need to be modified.When an AGV enters a node, it uploads coordinates of the current node to the server through 5G, Bluetooth, or other wireless technologies, so that the server can know the location of the AGV in SRNSs. We ignore the size of nodes in SRNSs, and consider that the distance between every two adjacent nodes isLn; the longitudinal length of the AGV is Lc; and the traveling speed of the AGV is fixed as v. When the head of the AGV enters a node, the node is occupied, and the node is released when the tail of the AGV leaves. As shown in Figure 2, the time for the AGV to pass through every two adjacent nodes is tc=Ln+Lc/v.Figure 2
Time of AGVs passing through every two adjacent nodes.In many SRNSs (e.g., AS/RSs), an AGV can only travel in four directions, north, east, south, and west, and can only turn at nodes. It requires deceleration, stopping, autobiography, and acceleration, and the total time for turning istu. The route length from the start node to the goal node is shown in equation (6). Given that the starting time of an AGV is 0 s, the total time for the AGV traveling to the goal node is shown in equation (7).(6)L=nc−1×Ln,(7)T=nc−1×tc+nu×tu.In equations (6) and (7), nc denotes the total number of nodes in the route and nu denotes the number of turns in the route.Given that the computing time of the server ists, the criteria of the optimal policy selection in SRNSs are as follows:(8)mintπs,(9)minLπ=nc−1×Ln,(10)minπT=nc−1×tc+nu×tu,(11)s.t.ts>0nc>1andLn>00≤nu≤nptu>0np=1,2,...,n.Equation (8) indicates that we should reduce route computing time of the server; equation (9) indicates that we should shorten routes’ distance of AGVs; equation (10) indicates that we should minimize the total travel time of AGVs. In equation (11), np denotes the number of nodes in an AGV’s route. Due to the fewer turns in AGVs’ routes, with less energy cost of the SRNSs, reducing the number of turns in AGVs routes can reduce the energy cost.


## 3.2.1. Smart Road Network System-Reward Matrix (SRNS-RM)

AGVs can obtain different immediate rewards at different nodes, and the reward/penalty obtained by AGVs is defined as follows: (1) if AGVs enter grey solid grids (i.e., obstacle nodes), they will get penalty: −r, where r is a positive integer; (2) if AGVs enter white grids, they will get penalty: −ε, where ε is a positive integer and ε≪r; (3) if AGVs reach the goal node, they can obtain reward +r2. Given an m × n SRNS, where m indicates the number of rows, that is, the number of nodes in a column, and n indicates the number of columns, that is, the number of nodes in a row, the SRNS-RM is(4)SRNS−RM=r11=−εr12=−εr13=−r…r1n=−εr21=−εr22=−rr23−r…r2n=−εr31=−εr32=−εr33=−r…r3n=−ε……………rm1=−εrm2=−εrm3=−ε…rmn=+r2.In equation (4), the dimension of SRNS-RM is m × n, which is the same as the SRNS. The elements (i.e., rij) in SRNS-RM (i=1,2…m; j=1,2…n) indicate the rewards of an AGV reaching nodes in row i and column j. Consider that there are four obstacle nodes in the SRNS, that is, SRNS-RM13 = −r, SRNS-RM22 = −r, SRNS-RM23 = −r, and SRNS-RM33 = −r.


## 3.2.2. Smart Road Network System-Transition Probability Matrix (SRNS-TPM)

The adjacencies of nodes in SRNSs are as follows: (1) there are no upper adjacent nodes for the nodes on the upper edge but only left, lower, and right adjacent nodes; (2) there are no left adjacent nodes for the node on the left edge but only top, right, and bottom adjacent nodes; (3) there are no lower adjacent nodes for the node on the lower edge but only upper, left, and right adjacent nodes; (4) there are no right adjacent nodes for the node on the right edge but only top, left, and bottom adjacent nodes; (5) there are four adjacent nodes except for the nodes on edges. In principle, the probabilities are the same for an AGV entering any adjacent node in anm × n SRNS, that is, Pij=PSt+1=j|St=i=δ, where 0≤δ≤1. The SRNS-TPM is(5)SRNS−TPM=P11P12P13…P1nP21P22P23…P2nP31P32P33…P3n……………Pm1Pm2Pm3…Pmn.In equation (5), Pij indicates each element of SRNS-TPM, where i indicates AGV’s current state (i.e., St), and j indicates its next state (i.e., St+1). The dimension of SRNS-TPM is m × n, which is the same as the SRNS and P11=P12=⋯=Pmn=δ; that is, the probability of AGV entering each adjacent node is the same.


## 3.2.3. Criteria of the Optimal Policy Selection

The objective of the classical MDP is to find the optimal policy that can reach the goal to maximize the accumulated rewardGt (see equation (2)). However, AGVs route planning in SRNSs is a multiobjective combinatorial optimization problem. On the one hand, the total routes’ length should be minimized; on the other hand, total routes’ length should be minimized, and AGVs’ traveling time should be the least. Therefore, the criteria for choosing the optimal policy need to be modified.When an AGV enters a node, it uploads coordinates of the current node to the server through 5G, Bluetooth, or other wireless technologies, so that the server can know the location of the AGV in SRNSs. We ignore the size of nodes in SRNSs, and consider that the distance between every two adjacent nodes isLn; the longitudinal length of the AGV is Lc; and the traveling speed of the AGV is fixed as v. When the head of the AGV enters a node, the node is occupied, and the node is released when the tail of the AGV leaves. As shown in Figure 2, the time for the AGV to pass through every two adjacent nodes is tc=Ln+Lc/v.Figure 2
Time of AGVs passing through every two adjacent nodes.In many SRNSs (e.g., AS/RSs), an AGV can only travel in four directions, north, east, south, and west, and can only turn at nodes. It requires deceleration, stopping, autobiography, and acceleration, and the total time for turning istu. The route length from the start node to the goal node is shown in equation (6). Given that the starting time of an AGV is 0 s, the total time for the AGV traveling to the goal node is shown in equation (7).(6)L=nc−1×Ln,(7)T=nc−1×tc+nu×tu.In equations (6) and (7), nc denotes the total number of nodes in the route and nu denotes the number of turns in the route.Given that the computing time of the server ists, the criteria of the optimal policy selection in SRNSs are as follows:(8)mintπs,(9)minLπ=nc−1×Ln,(10)minπT=nc−1×tc+nu×tu,(11)s.t.ts>0nc>1andLn>00≤nu≤nptu>0np=1,2,...,n.Equation (8) indicates that we should reduce route computing time of the server; equation (9) indicates that we should shorten routes’ distance of AGVs; equation (10) indicates that we should minimize the total travel time of AGVs. In equation (11), np denotes the number of nodes in an AGV’s route. Due to the fewer turns in AGVs’ routes, with less energy cost of the SRNSs, reducing the number of turns in AGVs routes can reduce the energy cost.


## 3.3. AGVs Route-Planning Approach in SRNSs

The flowchart of AGVs route-planning approach proposed in this paper is shown in Figure3, which consists of four parts: (1) route-planning region segmentation; (2) computing all shortest routes by training value functions of the regions; (3) obtaining the feasible routes according to AGVs’ status; and (4) selecting collision-free routes with the shortest length and the least travel time.Figure 3
Flowchart of the AGVs route-planning approach proposed in this paper.


### 3.3.1. Route-Planning Region Segmentation

The most effective way to speed up training is to reduce the number of samples. We here proposed a region-segmentation-based DP algorithm, in which the SRNSs are divided into regions according to AGVs’ start nodes and their goal nodes. The objective is to accelerate the convergence of the DP algorithm by excluding irrelevant nodes. Given the coordinates of an AGV’s start nodeXs,Ys and the goal node Xg,Yg, the left boundary of an SRNS Xl and the right boundary Xr, the upper left coordinates of the AGV’s route-planning region XAGViul,YAGViul, the upper-right coordinates XAGViur,YAGViur, the coordinates of the lower-left corner XAGVidl,YAGVidl, the coordinates of the lower right corner XAGVidr,YAGVidr, the length of the region along the x-direction Lrow, and the length along the y-direction Lcol, the AGVs’ route-planning region is defined as follows:(i)
IfXg−Xl<Xr−Xg, that is, an AGV’s goal node is closer to the left boundary of the SRNS, then(12)XAGViul,YAGViul=Xl,minYs,Yg,(13)XAGViur,YAGViur=maxXs,Xg,minYs,Yg,(14)XAGVidl,YAGVidl=Xl,maxYs,Yg,(15)XAGVidr,YAGVidr=maxXs,Xg,maxYs,Yg,(16)Lrow=maxXs,Xg−Xl,(17)Lcol=Yg−Ys.(ii)
IfXg−Xl>Xr−Xg, that is, an AGV’s goal node is closer to the right boundary, then(18)XAGViul,YAGViul=minXs,Xg,minYs,Yg,(19)XAGViur,YAGViur=minXs,Xg,maxYs,Yg,(20)XAGVidl,YAGVidl=Xr,minYs,Yg,(21)XAGVidr,YAGVidr=Xr,maxYs,Yg,(22)Lrow=Xr−maxXs,Xg,(23)Lcol=Yg−Ys.The conventional region-segmentation methods only focus on locations of AGVs’ start nodes and their goal nodes, but we take the relationship between them and the left (and right) boundaries of SRNSs into consideration. Our approach can reduce the number of samples without losing the accuracy of route planning. As shown in Figure4, given that the start node of an AGV is node 43 (x = 3, y = 5) and the goal node is node 20 (x = 4, y = 2), the blue line indicates the feasible route from the start node to the goal node; the yellow shaded area represents the route-planning region obtained using the conventional region-segmentation methods, which does not include the feasible route, and the area in the red box indicates the region in our approach, which contains the feasible route.Figure 4
Conventional and improved region segmentation.


### 3.3.2. Training Value Function of the Route-Planning Region

There are two kinds of commonly used DP algorithms: policy iteration-based DP algorithm and value iteration-based DP algorithm. The time of computing route using the DP algorithm based on policy iteration and value iteration in anm×n SRNS (see Figure 1(a)) is shown in Figure 5, where the blue line denotes the training time of the DP algorithm based on policy iteration, and the red line denotes that of the DP algorithm based on value iteration.Figure 5
Curve of convergences between the DP algorithms based on policy iteration and value iteration.As can be seen from Figure5, the training time of the DP algorithm based on value iteration is smaller than that of the DP algorithm based on policy iteration. In this scenario, the average time for route computing is improved by nearly 97.39%, and when the scales of SRNSs become larger, the difference of computing time between them becomes bigger. We employ the value iteration-based DP algorithm because it can adjust the policy while training rather than after the value function converges, which greatly reduces the number of iterations and significantly improves the efficiency of the algorithm.The calculation of the optimal value function (i.e.,V∗s) is a recursive process (refer to equation (3)). We need to evaluate the rewards of all adjacent states based on the current state, and the state with the largest reward is taken as the next state of the AGV. The method of computing the relationship between the current node and all adjacent nodes is(24)VT+1s=∑s+1pst+1|st,atratst+1+γ×VTst+1,wherepst+1|st,at indicates the probability of taking action at to transfer to an adjacent state st+1 based on the current state st; ratst+1 is the reward of taking action at to transfer to state st+1; γ is the discount factor, where γ∈0,1; VTst+1 is the value of each state adjacent to state st.Without considering obstacle nodes in SRNSs, the probability is the same for an AGV traveling to surrounding nodes; that is,pst+1|st,at=1/4 and γ=1. Equation (24) can be rewritten as(25)VT+1=14×−1+1×VuT+−1+1×VdT+−1+1×VlT+−1+1×VrT.In equation (25), VuT,VdT,VlT, and VrT denote the state values of upper, lower, left, and right adjacent nodes of AGV’s current nodes, respectively.


### 3.3.3. Route-Planning Strategies Based on Status of AGVs

There are multiple obstacles on AGVs’ routes, and the route-planning methods of AGVs in different status can be different. Taking AS/RSs as an example [35], as shown in Figure 6, the height of the bottom shelf from the ground is 75 cm, and the height of each no-load AGV is 50 cm. If an AGV needs to load, the tray on the AGV will be lifted to hold the bottom to lift the shelf. Because the height from the bottom shelf to the ground is greater than the height of a no-load AGV, a no-load AGV can pass under the shelve, whereas a loaded AGV (i.e., an AGV that is carrying a shelve) can not. So the loaded AGVs should avoid collision with not only other AGVs but also shelves placed above the nodes.Figure 6
Height of bottom shelf and no-load AGV in AS/RSs.If AGVs are loaded, the route-planning method is as follows: (1) storing locations of obstacle nodes into a listobstacle_list = [ ] while initializing the environment; (2) repeating equation (25) to compute the value function of the route-planning regions and obtaining all feasible routes from AGVs’ start nodes to their goal nodes; (3) comparing nodes in all feasible routes with nodes in obstacle_list = [ ] and deleting the routes that contain obstacle nodes; and (4) calculating the length of each collision-free route and storing routes with the minimum length. If AGVs are no-load ones, it is not necessary to establish obstacle_list = [ ] while initializing the environment, and we need not compare feasible routes to obstacle_list = [ ] but only to calculate the length of all feasible routes.


### 3.3.4. Obtaining Collision-Free Routes with the Shortest Length and the Least Travel Time

SRNSs are shaped like chessboards, and AGVs can travel in four directions: north, east, south, and west. Therefore, there may be more than one shortest-distance route from AGVs’ start nodes to their goal nodes. In some large SRNSs (e.g., AS/RSs), AGVs can only turn at nodes, and the time of the process becomes longer with the increase of AGVs’ turning angles. The fewer angles, the smaller the time cost and the higher the system efficiency. We can find routes with the shortest travel time for AGVs through the following steps:Step 1.
Comparing the angles of each feasible route with AGVs’ initial directions to determine their departure routes:(26)θinit=minθ1start−θAGVstart,θ2start−θAGVstart,θ3start−θAGVstart,θ4start−θAGVstart.
In equation (26), θinit indicates the departure angle of AGVs from start nodes. We take the southward as 0° and start nodes as the origin; θ1start indicates the angle of route 1, θ2start indicates the angle of route 2, θ3start indicates the angle of route 3, and θ4start indicates the angle of route 4; θAGVstart indicates the angle of AGVs at start nodes.Step 2.
Computing the routes with the shortest travel time, that is, the routes with the fewest turns: traversing each node of feasible routes obtained in Step 1, deleting routes that contain nodes inobstacle_list = [ ], and then judging whether a node is a turn or not in remaining routes. The method of determining whether a node is a turn or not is as follows: considering the X and Y coordinates of upstream and downstream nodes, if a node satisfies equation (27), it is a turn:(27)Xi+1−Xi≠Xi−Xi−1orYi+1−Yi≠Yi−Yi−1.
In equation (27), i denotes the number of the current node, Xi is the X-coordinate of the current node, and Yi is the Y-coordinate; i+1 denotes the number of the downstream node, Xi+1 is the X-coordinate, and Yi+1 is the Y-coordinate; i−1 denotes the number of the upstream node, Xi−1 is the X-coordinate, and Yi−1 is the Y-coordinate.


## 3.3.1. Route-Planning Region Segmentation

The most effective way to speed up training is to reduce the number of samples. We here proposed a region-segmentation-based DP algorithm, in which the SRNSs are divided into regions according to AGVs’ start nodes and their goal nodes. The objective is to accelerate the convergence of the DP algorithm by excluding irrelevant nodes. Given the coordinates of an AGV’s start nodeXs,Ys and the goal node Xg,Yg, the left boundary of an SRNS Xl and the right boundary Xr, the upper left coordinates of the AGV’s route-planning region XAGViul,YAGViul, the upper-right coordinates XAGViur,YAGViur, the coordinates of the lower-left corner XAGVidl,YAGVidl, the coordinates of the lower right corner XAGVidr,YAGVidr, the length of the region along the x-direction Lrow, and the length along the y-direction Lcol, the AGVs’ route-planning region is defined as follows:(i)
IfXg−Xl<Xr−Xg, that is, an AGV’s goal node is closer to the left boundary of the SRNS, then(12)XAGViul,YAGViul=Xl,minYs,Yg,(13)XAGViur,YAGViur=maxXs,Xg,minYs,Yg,(14)XAGVidl,YAGVidl=Xl,maxYs,Yg,(15)XAGVidr,YAGVidr=maxXs,Xg,maxYs,Yg,(16)Lrow=maxXs,Xg−Xl,(17)Lcol=Yg−Ys.(ii)
IfXg−Xl>Xr−Xg, that is, an AGV’s goal node is closer to the right boundary, then(18)XAGViul,YAGViul=minXs,Xg,minYs,Yg,(19)XAGViur,YAGViur=minXs,Xg,maxYs,Yg,(20)XAGVidl,YAGVidl=Xr,minYs,Yg,(21)XAGVidr,YAGVidr=Xr,maxYs,Yg,(22)Lrow=Xr−maxXs,Xg,(23)Lcol=Yg−Ys.The conventional region-segmentation methods only focus on locations of AGVs’ start nodes and their goal nodes, but we take the relationship between them and the left (and right) boundaries of SRNSs into consideration. Our approach can reduce the number of samples without losing the accuracy of route planning. As shown in Figure4, given that the start node of an AGV is node 43 (x = 3, y = 5) and the goal node is node 20 (x = 4, y = 2), the blue line indicates the feasible route from the start node to the goal node; the yellow shaded area represents the route-planning region obtained using the conventional region-segmentation methods, which does not include the feasible route, and the area in the red box indicates the region in our approach, which contains the feasible route.Figure 4
Conventional and improved region segmentation.


## 3.3.2. Training Value Function of the Route-Planning Region

There are two kinds of commonly used DP algorithms: policy iteration-based DP algorithm and value iteration-based DP algorithm. The time of computing route using the DP algorithm based on policy iteration and value iteration in anm×n SRNS (see Figure 1(a)) is shown in Figure 5, where the blue line denotes the training time of the DP algorithm based on policy iteration, and the red line denotes that of the DP algorithm based on value iteration.Figure 5
Curve of convergences between the DP algorithms based on policy iteration and value iteration.As can be seen from Figure5, the training time of the DP algorithm based on value iteration is smaller than that of the DP algorithm based on policy iteration. In this scenario, the average time for route computing is improved by nearly 97.39%, and when the scales of SRNSs become larger, the difference of computing time between them becomes bigger. We employ the value iteration-based DP algorithm because it can adjust the policy while training rather than after the value function converges, which greatly reduces the number of iterations and significantly improves the efficiency of the algorithm.The calculation of the optimal value function (i.e.,V∗s) is a recursive process (refer to equation (3)). We need to evaluate the rewards of all adjacent states based on the current state, and the state with the largest reward is taken as the next state of the AGV. The method of computing the relationship between the current node and all adjacent nodes is(24)VT+1s=∑s+1pst+1|st,atratst+1+γ×VTst+1,wherepst+1|st,at indicates the probability of taking action at to transfer to an adjacent state st+1 based on the current state st; ratst+1 is the reward of taking action at to transfer to state st+1; γ is the discount factor, where γ∈0,1; VTst+1 is the value of each state adjacent to state st.Without considering obstacle nodes in SRNSs, the probability is the same for an AGV traveling to surrounding nodes; that is,pst+1|st,at=1/4 and γ=1. Equation (24) can be rewritten as(25)VT+1=14×−1+1×VuT+−1+1×VdT+−1+1×VlT+−1+1×VrT.In equation (25), VuT,VdT,VlT, and VrT denote the state values of upper, lower, left, and right adjacent nodes of AGV’s current nodes, respectively.


## 3.3.3. Route-Planning Strategies Based on Status of AGVs

There are multiple obstacles on AGVs’ routes, and the route-planning methods of AGVs in different status can be different. Taking AS/RSs as an example [35], as shown in Figure 6, the height of the bottom shelf from the ground is 75 cm, and the height of each no-load AGV is 50 cm. If an AGV needs to load, the tray on the AGV will be lifted to hold the bottom to lift the shelf. Because the height from the bottom shelf to the ground is greater than the height of a no-load AGV, a no-load AGV can pass under the shelve, whereas a loaded AGV (i.e., an AGV that is carrying a shelve) can not. So the loaded AGVs should avoid collision with not only other AGVs but also shelves placed above the nodes.Figure 6
Height of bottom shelf and no-load AGV in AS/RSs.If AGVs are loaded, the route-planning method is as follows: (1) storing locations of obstacle nodes into a listobstacle_list = [ ] while initializing the environment; (2) repeating equation (25) to compute the value function of the route-planning regions and obtaining all feasible routes from AGVs’ start nodes to their goal nodes; (3) comparing nodes in all feasible routes with nodes in obstacle_list = [ ] and deleting the routes that contain obstacle nodes; and (4) calculating the length of each collision-free route and storing routes with the minimum length. If AGVs are no-load ones, it is not necessary to establish obstacle_list = [ ] while initializing the environment, and we need not compare feasible routes to obstacle_list = [ ] but only to calculate the length of all feasible routes.


## 3.3.4. Obtaining Collision-Free Routes with the Shortest Length and the Least Travel Time

SRNSs are shaped like chessboards, and AGVs can travel in four directions: north, east, south, and west. Therefore, there may be more than one shortest-distance route from AGVs’ start nodes to their goal nodes. In some large SRNSs (e.g., AS/RSs), AGVs can only turn at nodes, and the time of the process becomes longer with the increase of AGVs’ turning angles. The fewer angles, the smaller the time cost and the higher the system efficiency. We can find routes with the shortest travel time for AGVs through the following steps:Step 1.
Comparing the angles of each feasible route with AGVs’ initial directions to determine their departure routes:(26)θinit=minθ1start−θAGVstart,θ2start−θAGVstart,θ3start−θAGVstart,θ4start−θAGVstart.
In equation (26), θinit indicates the departure angle of AGVs from start nodes. We take the southward as 0° and start nodes as the origin; θ1start indicates the angle of route 1, θ2start indicates the angle of route 2, θ3start indicates the angle of route 3, and θ4start indicates the angle of route 4; θAGVstart indicates the angle of AGVs at start nodes.Step 2.
Computing the routes with the shortest travel time, that is, the routes with the fewest turns: traversing each node of feasible routes obtained in Step 1, deleting routes that contain nodes inobstacle_list = [ ], and then judging whether a node is a turn or not in remaining routes. The method of determining whether a node is a turn or not is as follows: considering the X and Y coordinates of upstream and downstream nodes, if a node satisfies equation (27), it is a turn:(27)Xi+1−Xi≠Xi−Xi−1orYi+1−Yi≠Yi−Yi−1.
In equation (27), i denotes the number of the current node, Xi is the X-coordinate of the current node, and Yi is the Y-coordinate; i+1 denotes the number of the downstream node, Xi+1 is the X-coordinate, and Yi+1 is the Y-coordinate; i−1 denotes the number of the upstream node, Xi−1 is the X-coordinate, and Yi−1 is the Y-coordinate.


## 4. Simulation Case Studies

Simulation OS isWindows 10, Intel Xeon W-2145 CPU @ 3.70 GHz x64-based processor; programming software is Python 3.7.3; rasterized AS/RSs environment parameters are 25×34 Horizontal Row, with 850 nodes in total, Lc = 2.5 m (note: the proposed algorithm is suitable for not only AS/RSs but also all SRNSs); v = 0.5 m/s, and the times for AGVs traveling between two adjacent nodes (i.e., tc) and turning at nodes (i.e., tu) are both 5 s.Case 1.
Route planning for an AGV in AS/RSs from a designated start node to a designated goal node. The numbers of obstacle nodes of Figure7 are as follows: obstacle_list = [35, 36, 37, 38, 39, 40, 41, 42, 43, 44, …, 805, 806, 807, 808, 809, 810, 811, 812, 813, 814]. The start node of an AGV is node 56 (x = 22, y = 1), and the goal node is node 639 (x = 27, y = 18). The process of route planning is as follows.Figure 7
AGV’s route-planning region (from node 56(x = 22, y = 1) to node 639 (x = 27, y = 18)).


### 4.1. Determining the Route-Planning Region for the AGV

Based on the start node and the goal node of every AGV and the AS/RS’s boundary, we use equations (12)–(17) (or equations (18)–(23)) to obtain the region-segmentation result, as shown in the blue shaded part in Figure 7.


### 4.2. Modeling the AS/RS Using the Improved MDP

According to the definition in equations (16) and (17) (or equations (22) and (23)), we can obtain the following: Lrow=12, Lcol=18, r=10, and ε=1, and the probability of AGV traveling towards the node adjacent to the current node (i.e., state transition) p=1/4. Based on equations (4) and (5), SRNS-RM and SRNS-TPM are as follows:(28)PBS−RM=r1,1=−1r1,2=−10r1,3=−10⋯r1,12=−1r2,1=−1r2,2=−10r2,3=−10⋯r2,12=−1r3,1=−1r3,2=−1r3,3=−1⋯r3,12=−1⋯⋯⋯⋯⋯r18,1=−1r18,2=−1r18,3=−1⋯r18,12=+100,PBS−TPM=P1,1=14P1,2=14P1,3=14⋯P1,12=14P2,1=14P2,2=14P2,2=14P2,3=14P2,12=14P3,1=14P3,2=14P3,2=14P3,3=14P3,12=14⋯⋯⋯⋯⋯P18,1=14P18,2=14P18,2=14P18,3=14P18,12=14.


### 4.3. Obtaining All the Equidistant Shortest Routes

By using the value iteration-based DP algorithm (see equation (25)), we can obtain all the feasible routes from AGV’s start node to its goal node, as shown in Figures 8(a)–8(f).Figure 8
All feasible routes from AGV’s start node to its goal node.
(a)(b)(c)(d)(e)(f)


### 4.4. Selecting a Route with the Least Travel Time

The route of an AGV in SRNS can be presented asS(T), where S indicates the set of nodes’ numbers in AGV’s route, and T indicates the set of time when the AGV passes the nodes. We can choose routes with the least AGV turning angle using (22) and obtain a route with the least turning nodes using equation (23), as shown in Figure 9. The comparison of route computing time between the algorithm proposed in this paper and the classical DP algorithm is shown in Figure 10, where the blue line represents the classical DP algorithm and the red the algorithm proposed in this paper.Figure 9
AGV’s route that has the shortest distance and the least travel time.Figure 10
Comparison of route computing time between the classical DP algorithm and our algorithm.As shown in Figure10, the route computing time of the classical DP algorithm is 0.8756 s, the time of the algorithm proposed in this paper is 0.1233 s, and it reduces the route computing time (i.e., tc) by nearly 85.92%. Then, we compare the route computing time of the classical DP algorithm and our algorithm in SRNSs of different sizes (see Figure 11).Figure 11
Comparison of route computing time between the classical DP algorithm and our algorithm.As shown in Figure11, the algorithm proposed in this paper greatly reduces route computing time of AGVs and significantly improves route-planning algorithm’s efficiency, and the larger the SRNSs, the more obvious the advantages of the proposed algorithm.Case 2.
Route planning for loaded AGVs and a no-load AGV in AS/RSs. Consider the start node of an AGV to be node 23(x = 23, y = 0) and the goal node to be node 435 (x = 27, y = 12). If the AGV is loaded, it should avoid shelves located on nodes while traveling, and we need to build obstacle_list = [ ]. Then, we compute route-planning regions using equations (8)–(13) (or equations (14)–(19)) and repeatedly employ equation (21) to obtain all the feasible routes for the AGV from the start node to the goal node. Finally, we obtain the route with the shortest travel time according to equations (22) and (23), as indicated by the red line in Figure 12. If the AGV is a no-load one, it does not need to avoid shelves while traveling. We omit the process of building obstacle_list = [ ] and directly use the region-segmentation DP algorithm to obtain the route with the shortest length and travel time, as the blue line shows in Figure 12.
As shown in Figure12, although the start node and the goal node of loaded and no-load AGV are the same, the number of turns in routes, the length of the route, and the traveling time of the AGV are different, and the comparison results are as follows.
As shown in Table1, (i) when the AGV is loaded, the number of turns is 2, the length of the route is 70m, and AGV’s travel time is 150 s; (ii) when the AGV is a no-load one, the number of turns is 1, the length of the route is 40m, and AGV’s travel time is 85s. In this scenario, the algorithm proposed in this paper improves the routes computing time (i.e., tc) by nearly 43.33%.Figure 12
Route-planning results according to AGV’s status (loaded or no-load).Table 1
All feasible routes from AGV’s start node to its goal node.
Number of turnsLength of the route (m)AGV’s travel time (s)Loaded AGV270150No-load AGV14085


## 4.1. Determining the Route-Planning Region for the AGV

Based on the start node and the goal node of every AGV and the AS/RS’s boundary, we use equations (12)–(17) (or equations (18)–(23)) to obtain the region-segmentation result, as shown in the blue shaded part in Figure 7.


## 4.2. Modeling the AS/RS Using the Improved MDP

According to the definition in equations (16) and (17) (or equations (22) and (23)), we can obtain the following: Lrow=12, Lcol=18, r=10, and ε=1, and the probability of AGV traveling towards the node adjacent to the current node (i.e., state transition) p=1/4. Based on equations (4) and (5), SRNS-RM and SRNS-TPM are as follows:(28)PBS−RM=r1,1=−1r1,2=−10r1,3=−10⋯r1,12=−1r2,1=−1r2,2=−10r2,3=−10⋯r2,12=−1r3,1=−1r3,2=−1r3,3=−1⋯r3,12=−1⋯⋯⋯⋯⋯r18,1=−1r18,2=−1r18,3=−1⋯r18,12=+100,PBS−TPM=P1,1=14P1,2=14P1,3=14⋯P1,12=14P2,1=14P2,2=14P2,2=14P2,3=14P2,12=14P3,1=14P3,2=14P3,2=14P3,3=14P3,12=14⋯⋯⋯⋯⋯P18,1=14P18,2=14P18,2=14P18,3=14P18,12=14.


## 4.3. Obtaining All the Equidistant Shortest Routes

By using the value iteration-based DP algorithm (see equation (25)), we can obtain all the feasible routes from AGV’s start node to its goal node, as shown in Figures 8(a)–8(f).Figure 8
All feasible routes from AGV’s start node to its goal node.
(a)(b)(c)(d)(e)(f)


## 4.4. Selecting a Route with the Least Travel Time

The route of an AGV in SRNS can be presented asS(T), where S indicates the set of nodes’ numbers in AGV’s route, and T indicates the set of time when the AGV passes the nodes. We can choose routes with the least AGV turning angle using (22) and obtain a route with the least turning nodes using equation (23), as shown in Figure 9. The comparison of route computing time between the algorithm proposed in this paper and the classical DP algorithm is shown in Figure 10, where the blue line represents the classical DP algorithm and the red the algorithm proposed in this paper.Figure 9
AGV’s route that has the shortest distance and the least travel time.Figure 10
Comparison of route computing time between the classical DP algorithm and our algorithm.As shown in Figure10, the route computing time of the classical DP algorithm is 0.8756 s, the time of the algorithm proposed in this paper is 0.1233 s, and it reduces the route computing time (i.e., tc) by nearly 85.92%. Then, we compare the route computing time of the classical DP algorithm and our algorithm in SRNSs of different sizes (see Figure 11).Figure 11
Comparison of route computing time between the classical DP algorithm and our algorithm.As shown in Figure11, the algorithm proposed in this paper greatly reduces route computing time of AGVs and significantly improves route-planning algorithm’s efficiency, and the larger the SRNSs, the more obvious the advantages of the proposed algorithm.Case 2.
Route planning for loaded AGVs and a no-load AGV in AS/RSs. Consider the start node of an AGV to be node 23(x = 23, y = 0) and the goal node to be node 435 (x = 27, y = 12). If the AGV is loaded, it should avoid shelves located on nodes while traveling, and we need to build obstacle_list = [ ]. Then, we compute route-planning regions using equations (8)–(13) (or equations (14)–(19)) and repeatedly employ equation (21) to obtain all the feasible routes for the AGV from the start node to the goal node. Finally, we obtain the route with the shortest travel time according to equations (22) and (23), as indicated by the red line in Figure 12. If the AGV is a no-load one, it does not need to avoid shelves while traveling. We omit the process of building obstacle_list = [ ] and directly use the region-segmentation DP algorithm to obtain the route with the shortest length and travel time, as the blue line shows in Figure 12.
As shown in Figure12, although the start node and the goal node of loaded and no-load AGV are the same, the number of turns in routes, the length of the route, and the traveling time of the AGV are different, and the comparison results are as follows.
As shown in Table1, (i) when the AGV is loaded, the number of turns is 2, the length of the route is 70m, and AGV’s travel time is 150 s; (ii) when the AGV is a no-load one, the number of turns is 1, the length of the route is 40m, and AGV’s travel time is 85s. In this scenario, the algorithm proposed in this paper improves the routes computing time (i.e., tc) by nearly 43.33%.Figure 12
Route-planning results according to AGV’s status (loaded or no-load).Table 1
All feasible routes from AGV’s start node to its goal node.
Number of turnsLength of the route (m)AGV’s travel time (s)Loaded AGV270150No-load AGV14085


## 5. Conclusions

This paper proposes an AGVs route-planning approach in large SRNSs based on a region-segmentation Dynamic Programming algorithm. First, we use the improved MDP to model the large SRNSs. Then, the large SRNSs are divided into several route-planning regions according to AGVs’ start nodes and their goal nodes, the objective is to narrow the range of searching routes and reduce the number of samples, and this step significantly improved the route-planning speed. Since more travel time and energy cost can be caused by AGVs’ turns, we compute the absolute value of angle deviation between each feasible route to AGVs’ initial directions to choose the candidate routes, and then the route with the least turns is selected as the optimal one. Compared with the conventional Dynamic Programming algorithm, the algorithm proposed in this paper greatly improves the efficiency of route planning in large SRNSs.



---

*Source: 9589476-2021-10-22.xml*