# Path Planning of Mobile Robots in Warehouse Logistics Relying on Computer Multimedia 3D Reconstruction Technology

Authors: Yan Sun
Journal: Advances in Multimedia
 (2021)

---

## Abstract

Because traditional methods are difficult to solve the problems related to the path planning of logistics robots, this study proposes a method of using computer multimedia 3D reconstruction technology to realize the path planning of warehouse logistics robots. Without fully considering the accurate movement path between points, according to the warehouse logistics robot, it is judged whether the starting point is at the exit. The planning problem of the movement path is converted into a TSP problem and a TS-TSP problem. Finally, the analysis of experimental results shows that the method proposed in this study converges faster than traditional algorithms and can quickly obtain the global optimal solution. At the same time, the warehousing logistics robot requires less path planning time and has strong practical application.


---

## Body

## 1. Introduction

In the process of traditional robot path planning research, two-dimensional maps are usually used to describe the robot’s motion environment. However, because two-dimensional maps can only describe relatively high environmental plane information, they cannot provide relatively complete data information. Therefore, it has a great influence on the completion of the robot path planning, and the construction of the three-dimensional environment is very important for the robot path planning [1–3]. With the development of the computer Internet and science and technology across the Soviet Union, the research on mobile robots for warehousing and logistics has gradually become a hotspot in the current intelligent research direction and has been widely used in many areas of people’s daily life and industrial production. In turn, the economic benefits of different industries can be continuously increased. Mobile robots have gradually begun to replace manual sorting and handling in warehousing logistics, but in the process of task scheduling, mobile robots are prone to problems such as task matching error, slow response speed, long distance of planned path, and so on. Therefore, to ensure that mobile robots work efficiently and accurately in automated warehousing and logistics has become an urgent problem to be solved.Therefore, the use of computer multimedia three-dimensional reconstruction technology applied to the path planning of warehouse logistics robots is more important for its movement navigation in the indoor environment. The inventory logistics path planning method proposed in this study converts the researched path planning problem into a classic TSP problem and uses the potential field ant colony method to obtain the approximate optimal global path point access sequence according to the path point access sequence. Path planning and the final experimental analysis results show that the method proposed in this study is reliable and practical.


## 2. Three-Dimensional Path Planning Optimization Algorithm

### 2.1. Path Energy Function

The plan penalty function of a path is defined as the sum of the plan penalty functions of each path point, and the plan penalty function of a point is defined as the sum of the penalty functions defined by the neural network structure for each obstacle [4–7]. Figure 1 shows the neural network as a penalty function from a point to a polyhedral obstacle. The neural network is a forward three-layer network consisting of an input layer, a hidden layer, and an output layer. The three neurons of the input layer are the coordinates x, y, and z for a given path point. The connection weight from the hidden layer to the output layer is 1, and the threshold of the output layer neuron is a negative number minus 0.5 from the number of inequalities.Figure 1
The neural network of the obstacle penalty function.Pxi,yi,zii=1,2,…,N on waypoint definition(1)E1=∑i=1N−1Li2=∑i=1N−1xi+1−xi2+yi+1−yi2+zi+1−zi2.That is,E1 is the square of the length of the entire path.(2)E=E1+Ec.That is, the path energy function is the sum of the square of the path length and the path penalty function.


### 2.2. Path Planning Algorithm

The path planning method comes from the simplifiedD∗ algorithm [8–10], and the planning algorithm flow is shown in Figure 2. First of all, suppose that G = (S, E) represents a grid map, where S represents a series of grids of possible locations of a mobile robot for warehouse logistics, and E represents the boundaries of these locations. The function is the area near the adjs grating, Succs⊆S represents the grating behind the grating, and Preds⊆S represents the grating in front of the grating. vs indicates whether the warehouse logistics mobile robot has reached the grid. When the first grid sstart∈S and target grid sgoal∈S are given, the path planning algorithm can assume the estimated function gs, which records the consumption from the initial state to each other state s, thereby generating the shortest path.(3)gs=0,ifs=sstart,mins′∈Predsgs′+cs′,s,otherwise.Figure 2
An example diagram of the path planning algorithm flow. (a) Initial path planning. (b) The first step of path planning. (c) The second step of path planning. (d) The third step of path planning. (e) The fourth step of path planning. (f) The fifth step of path planning. (g) Path planning completed.
(a)(b)(c)(d)(e)(f)(g)In the formula, function0<cs,s′≤∞ is used to store the consumption from state s to state s′, and c (s, s′) = ∞ means that it is impassable from grid s to grid s'. At the same time, the fast retrieval function hs,sgoal is used to estimate the path consumption to reach the target position and to reduce those unnecessary (not toward the target point) calculations. Obviously, hs,sgoal and c (s, s′) satisfy the triangle inequality.(4)hs,sgoal≤hs′,sgoal+cs,s′.At the beginning, all sumsh (s) are set to 0 and vs is set to false. In other words, information such as whether all grids are passable is unknown to the warehouse logistics mobile robot. When gsstart=0 search starts, s is set to CLOSED, that is, there is no need to reach the barrier again. For all grid s∈adjsstart, calculation functions gs, and value hs,sgoal, if the grid s is not set in CLOSED, then the OPEN sequence is added. The OPEN sequence stores the grid required by the warehouse logistics mobile robot, and according to k (s) function to sort,(5)ks=gs+hs,sgoal,k (s) after arranging the grid with the smallest numerical value at the top of the OPEN sequence and placing the grid in the OPEN sequence, the grid at the top of the sequence is popped up, and the state is set in CLOSED and in OPEN. After the sequence is arranged, the grid with the smallest k (s) value is popped up to continue the exploration. This process continues until s∈adjsstart is marked. If the OPEN sequence is empty, it means that sgoal does not have a suitable sgoal path.


## 2.1. Path Energy Function

The plan penalty function of a path is defined as the sum of the plan penalty functions of each path point, and the plan penalty function of a point is defined as the sum of the penalty functions defined by the neural network structure for each obstacle [4–7]. Figure 1 shows the neural network as a penalty function from a point to a polyhedral obstacle. The neural network is a forward three-layer network consisting of an input layer, a hidden layer, and an output layer. The three neurons of the input layer are the coordinates x, y, and z for a given path point. The connection weight from the hidden layer to the output layer is 1, and the threshold of the output layer neuron is a negative number minus 0.5 from the number of inequalities.Figure 1
The neural network of the obstacle penalty function.Pxi,yi,zii=1,2,…,N on waypoint definition(1)E1=∑i=1N−1Li2=∑i=1N−1xi+1−xi2+yi+1−yi2+zi+1−zi2.That is,E1 is the square of the length of the entire path.(2)E=E1+Ec.That is, the path energy function is the sum of the square of the path length and the path penalty function.


## 2.2. Path Planning Algorithm

The path planning method comes from the simplifiedD∗ algorithm [8–10], and the planning algorithm flow is shown in Figure 2. First of all, suppose that G = (S, E) represents a grid map, where S represents a series of grids of possible locations of a mobile robot for warehouse logistics, and E represents the boundaries of these locations. The function is the area near the adjs grating, Succs⊆S represents the grating behind the grating, and Preds⊆S represents the grating in front of the grating. vs indicates whether the warehouse logistics mobile robot has reached the grid. When the first grid sstart∈S and target grid sgoal∈S are given, the path planning algorithm can assume the estimated function gs, which records the consumption from the initial state to each other state s, thereby generating the shortest path.(3)gs=0,ifs=sstart,mins′∈Predsgs′+cs′,s,otherwise.Figure 2
An example diagram of the path planning algorithm flow. (a) Initial path planning. (b) The first step of path planning. (c) The second step of path planning. (d) The third step of path planning. (e) The fourth step of path planning. (f) The fifth step of path planning. (g) Path planning completed.
(a)(b)(c)(d)(e)(f)(g)In the formula, function0<cs,s′≤∞ is used to store the consumption from state s to state s′, and c (s, s′) = ∞ means that it is impassable from grid s to grid s'. At the same time, the fast retrieval function hs,sgoal is used to estimate the path consumption to reach the target position and to reduce those unnecessary (not toward the target point) calculations. Obviously, hs,sgoal and c (s, s′) satisfy the triangle inequality.(4)hs,sgoal≤hs′,sgoal+cs,s′.At the beginning, all sumsh (s) are set to 0 and vs is set to false. In other words, information such as whether all grids are passable is unknown to the warehouse logistics mobile robot. When gsstart=0 search starts, s is set to CLOSED, that is, there is no need to reach the barrier again. For all grid s∈adjsstart, calculation functions gs, and value hs,sgoal, if the grid s is not set in CLOSED, then the OPEN sequence is added. The OPEN sequence stores the grid required by the warehouse logistics mobile robot, and according to k (s) function to sort,(5)ks=gs+hs,sgoal,k (s) after arranging the grid with the smallest numerical value at the top of the OPEN sequence and placing the grid in the OPEN sequence, the grid at the top of the sequence is popped up, and the state is set in CLOSED and in OPEN. After the sequence is arranged, the grid with the smallest k (s) value is popped up to continue the exploration. This process continues until s∈adjsstart is marked. If the OPEN sequence is empty, it means that sgoal does not have a suitable sgoal path.


## 3. Path Planning Method of Warehousing Logistics Robot

### 3.1. Storage Environment Design Based on Computer Multimedia 3D Reconstruction Technology

Before planning the global path of the warehouse logistics robot, it is necessary to complete the modeling of the warehouse storage environment to improve the warehouse storage status of the warehouse logistics robot. The modeling of the warehouse storage environment in this section selects computer multimedia 3D reconstruction technology. The 3D reconstruction technology of computer multimedia is also called the unit decomposition method [11–13]. It divides the environment in which the warehouse logistics robot is located into area and volume and divides it into several two-dimensional or three-dimensional grids with the same shape. The other components are explained in abstract in units of small grids to construct a warehouse environment that the logistics robot can easily understand.The mapping relationship between the two is changed and used according to the requirements. The detailed mapping relationship is(6)Bianhao=x−1×ceilm/a+y.Part of the simulation environment of the warehouse is shown in Figure3.Figure 3
Partial schematic diagram of simulated storage environment.


### 3.2. Construction of the Mathematical Model of Warehousing Logistics Robot Path Planning

Regardless of the point and the correct path of the point, the path planning problem is divided into two parts according to whether there is an exit at the initial point of the warehouse logistics robot [14, 15]. One of them is that the initial point of warehouse logistics robots is when they are exported. It can be regarded as a typical TSP problem. The other is that if the initial point is not at the exit, the end of the initial point can be regarded as a constant TSP problem, that is, an ST-PSP problem. The mathematical model of a typical TSP problem can be expressed by (2), and the optimal path P=u1,u2,…,uk is calculated.(7)minZPα=∑i=1k=1duαi,uαi+1+duα1,uk.In the formula,duαi,uαi+1 is used to describe the reorganized set of K path point sequences of the Manhattan distance between two points Pα and αi.If the potential field ant colony method is used to solve the typical TSP problem, all waypoints can be regarded as group individuals, and the adaptive function selection equation (2) can be used. For the TSP problem and the ST-PSP problem, the potential field ant colony method can only obtain the best access sequence of the global path points, not the path, and cannot meet the requirements of the mobile wheeled logistics robot volume selection path plan. It is necessary to obtain an accurate global planning path through three-dimensional reconstruction technology.


## 3.1. Storage Environment Design Based on Computer Multimedia 3D Reconstruction Technology

Before planning the global path of the warehouse logistics robot, it is necessary to complete the modeling of the warehouse storage environment to improve the warehouse storage status of the warehouse logistics robot. The modeling of the warehouse storage environment in this section selects computer multimedia 3D reconstruction technology. The 3D reconstruction technology of computer multimedia is also called the unit decomposition method [11–13]. It divides the environment in which the warehouse logistics robot is located into area and volume and divides it into several two-dimensional or three-dimensional grids with the same shape. The other components are explained in abstract in units of small grids to construct a warehouse environment that the logistics robot can easily understand.The mapping relationship between the two is changed and used according to the requirements. The detailed mapping relationship is(6)Bianhao=x−1×ceilm/a+y.Part of the simulation environment of the warehouse is shown in Figure3.Figure 3
Partial schematic diagram of simulated storage environment.


## 3.2. Construction of the Mathematical Model of Warehousing Logistics Robot Path Planning

Regardless of the point and the correct path of the point, the path planning problem is divided into two parts according to whether there is an exit at the initial point of the warehouse logistics robot [14, 15]. One of them is that the initial point of warehouse logistics robots is when they are exported. It can be regarded as a typical TSP problem. The other is that if the initial point is not at the exit, the end of the initial point can be regarded as a constant TSP problem, that is, an ST-PSP problem. The mathematical model of a typical TSP problem can be expressed by (2), and the optimal path P=u1,u2,…,uk is calculated.(7)minZPα=∑i=1k=1duαi,uαi+1+duα1,uk.In the formula,duαi,uαi+1 is used to describe the reorganized set of K path point sequences of the Manhattan distance between two points Pα and αi.If the potential field ant colony method is used to solve the typical TSP problem, all waypoints can be regarded as group individuals, and the adaptive function selection equation (2) can be used. For the TSP problem and the ST-PSP problem, the potential field ant colony method can only obtain the best access sequence of the global path points, not the path, and cannot meet the requirements of the mobile wheeled logistics robot volume selection path plan. It is necessary to obtain an accurate global planning path through three-dimensional reconstruction technology.


## 4. Experimental Analysis and Application

### 4.1. Application Background and Data

The application background is to choose an automated three-dimensional warehouse and build a rasterized warehouse environment as shown in Figure4.Figure 4
Rasterized storage environment.The rasterized storage environment shown in Figure4 is divided into a total of 23 parts in the sorting station on the left side of the warehouse. Through the path formed by the protective cover next door, only one warehouse logistics robot can pass all the paths. In other words, single ticket. The warehouse logistics robot completes a large number of screenings in the warehouse at a speed of 1 m/s.


### 4.2. Potential Field Ant Colony Method Performance Test

The performance of the potential field ant colony method has a great influence on the path planning results of the warehouse logistics robot, which is verified in this section.Figure5 shows how the individual fitness of each generation changes according to the evolutionary algebra when the potential field ant colony method is excellent. The concentration point in Figure 5 is the average fitness value of each generation, and the best fitness value is the relatively scattered points nearby and corresponds.Figure 5
The optimal path length and average path length of each generation.Analyzing Figure5, the potential field ant colony method used in this article has a fast convergence rate, and people in their 30s have basically found the global best solution. In the initial generations, if the difference between the individual and the expected value is large, the optimal value is quickly optimized. In the later generations, as the group approaches the optimal solution, the optimization value, optimization speed becomes slower, which conforms to the actual situation and avoids the generation of local optimal solutions.By analyzing Figure6, we can see the repetition process of the potential field ant colony method. The vertical line in Figure 6 represents the adaptive range of different points in each generation, and the curve represents the average adaptability development trend after repetition. Before repeating 30 times, the fitness between the groups of each generation is very different, and the line segment is long. This difference is repeated 30 times and becomes smaller and stabilized, and the line segment gradually becomes shorter, which means that the optimal fitness area is stable, the diversity is reduced, the convergence speed is improved, and the global optimal solution has a rapid effect.Figure 6
The iterative process of the potential field ant colony method.


## 4.1. Application Background and Data

The application background is to choose an automated three-dimensional warehouse and build a rasterized warehouse environment as shown in Figure4.Figure 4
Rasterized storage environment.The rasterized storage environment shown in Figure4 is divided into a total of 23 parts in the sorting station on the left side of the warehouse. Through the path formed by the protective cover next door, only one warehouse logistics robot can pass all the paths. In other words, single ticket. The warehouse logistics robot completes a large number of screenings in the warehouse at a speed of 1 m/s.


## 4.2. Potential Field Ant Colony Method Performance Test

The performance of the potential field ant colony method has a great influence on the path planning results of the warehouse logistics robot, which is verified in this section.Figure5 shows how the individual fitness of each generation changes according to the evolutionary algebra when the potential field ant colony method is excellent. The concentration point in Figure 5 is the average fitness value of each generation, and the best fitness value is the relatively scattered points nearby and corresponds.Figure 5
The optimal path length and average path length of each generation.Analyzing Figure5, the potential field ant colony method used in this article has a fast convergence rate, and people in their 30s have basically found the global best solution. In the initial generations, if the difference between the individual and the expected value is large, the optimal value is quickly optimized. In the later generations, as the group approaches the optimal solution, the optimization value, optimization speed becomes slower, which conforms to the actual situation and avoids the generation of local optimal solutions.By analyzing Figure6, we can see the repetition process of the potential field ant colony method. The vertical line in Figure 6 represents the adaptive range of different points in each generation, and the curve represents the average adaptability development trend after repetition. Before repeating 30 times, the fitness between the groups of each generation is very different, and the line segment is long. This difference is repeated 30 times and becomes smaller and stabilized, and the line segment gradually becomes shorter, which means that the optimal fitness area is stable, the diversity is reduced, the convergence speed is improved, and the global optimal solution has a rapid effect.Figure 6
The iterative process of the potential field ant colony method.


## 5. Path Planning Result Test

In this section, the experimental analysis is performed in the MATLAB environment. For the actual storage environment shown in Figure3, the method proposed in this study, the method of the D∗ algorithm, and the method of the multistage decision algorithm are compared and tested to verify the effectiveness of this method. Select 20 warehouse logistics robots to jointly perform 300 batch screening tasks, divide the tasks into 50 groups, and perform 6 tasks in each group.Figure7 shows when the warehouse logistics robot is faulty, the hollow pill represents a warehouse logistics robot. The representative robot with a hollow circle takes the black rectangle in the matching station as the initial point and reaches the black rectangle to get the goods.Figure 7
Situation of obstacles encountered by warehousing logistics robots.Figure8 is a block diagram, the white part represents the passable channel, the gray part represents the blockage area, and the darker the gray color, the more serious the blockage. Analyzing Figure 8 shows that during a certain period, the logistics robots concentrated in a part of the area for screening, so congestion occurred.Figure 8
Blockage map.Figure9 shows the path planning results of the method in this study, the method in the D∗ algorithm, and the method in the multistage decision algorithm.Figure 9
Comparison of the path planning results of the three methods. (a) D∗ algorithm and method path planning results. (b) Multistage decision algorithm and method path planning results. (c) Path planning results of the method in this study.
(a)(b)(c)Analyzing Figure9, we can see that the method and literature of the D∗ algorithm are used; the method is to plan the global path although the path is short, but it needs to wait in a traffic jam. This leads to a waste of resources. This method is used to plan the overall path. The selected path does not need to wait for the traffic jam, and the time required is less, which greatly improves the selection efficiency.The following robot 30 is a large amount of goods 300, 400, 500, and 600, and the total length of the planned path and the total selection time are compared with the data of various algorithms. The results are given in Table1.Table 1
Comparison of planning performance of 3 methods.
MethodIndexPicking goods/piece300400500600This articlePath length/m1256182121593815MethodPicking time/s325422586921D∗ algorithmPath length/m1239182221393806MethodPicking time/s3964757291106Multistage decision algorithmPath length/m1250181521453802MethodPicking time/s4156017321095According to the analysis given in Table1, in the planning path, the method in the D∗ algorithm and the method in the multistage decision algorithm are slightly shorter than the method in this article, but regarding the selection time, the time required by the method in this article is significantly lower than the other two methods. This is mainly because the method in this study can avoid obstacles and save a lot of picking time.


## 6. Conclusions

For the problems that arise in the actual path planning of mobile warehousing and logistics mobile robots, this study uses the three-dimensional reconstruction technology of computer multimedia to plan the moving path of warehousing and logistics robots. For raster maps, the memory space can be reduced, and at the same time, the motion collision process can be tested, and the spatial feasibility can be analyzed more quickly. This study uses the potential field ant colony method to solve the movement path of the warehouse logistics robot. According to the three-dimensional reconstruction technology method to obtain the path planning results, experimental analysis shows that the method proposed in this study is very practical.



---

*Source: 4090990-2021-12-08.xml*