Research on Automatic Path Planning Method of Warehouse Inspection Robot

ABSTRACT

The patrol robot is an important guarantee for the safety of the enterprise’s warehouse. However, due to the large number of patrol target points, the automatic path planning of the patrol robot is difficult and inefficient. In order to solve this problem, the hybrid particle swarm optimization (HPSO) algorithm is combined with A-star algorithm, and a path optimization method for inspection robot based on HPSO-A-star model is proposed. First, the grid model of the map is established, A-star algorithm calculates the path between two inspection points, and then HPSO algorithm realizes the nonlinear planning of the path according to the length of different paths, so as to find an optimal inspection route. The comparative experimental analysis results show that the path planned by HPSO algorithm is 5.71% shorter than that planned by PSO algorithm; the smaller the map grid size is, the shorter the calculated optimal path length is, but it will consume more computing resources. Finally, the HPSO-A-star algorithm is compared with the PSO-A-star algorithm; the experimental results show that the path of the HPSO-A-star algorithm is shortened by 29.79%, and the HPSO-A-star algorithm can better realize the path planning of the patrol robot.

Introduction

Enterprise warehouse safety inspection is an important guarantee for enterprise safety production. With the development of robot technology, artificial intelligence technology and big data technology (Shamilyan et al. 2022), enterprise warehouse inspection is gradually replaced by inspection robots (Li et al. 2011). Automatic path planning for robot inspection is the key technology of robot automatic navigation (Bogaerts et al. 2018). Its purpose is to find an action path with shorter distance and higher efficiency as far as possible under the premise of meeting all inspection points, so as to reduce the resource consumption of inspection (Liu et al. 2021).

For the problem of path optimization of inspection robot, many researchers have proposed new solutions. Zhang, X.et al. studied the heuristic search algorithm and Dijkstra algorithm based on graph theory, and realized the path planning of inspection robots in the substation environment (Zhang et al. 2019). Liao, YF. et al. put forward a guideway fire inspection robot, which uses computer vision platform to track and improve the accuracy of warehouse fire source identification (Liao et al. 2020). Wang, XH. et al. proposed a hybrid path planning algorithm combining A-star algorithm and time-elastic band algorithm, effectively solving the path planning problem that is prone to local optimal solutions in complex environments (Xiaohui Wang, Ma, and Li 2023). It can be seen that due to the large number of inspection target points in the warehouse, automatic path planning of inspection robots is characterized by heavy computation and multiple objectives, and it has become a new research direction to find a more efficient robot path optimization algorithm (Xuewu Wang et al. 2021).

Sohouli, AN. et al. used HPSO optimized genetic algorithm (HPSO-GA) to estimate abnormal parameters in exploration geophysics; the experimental results show that this method can estimate up to 25% of the noise (Sohouli, Molhem, and Zare-Dehnavi 2022). Li, F. et al. used HPSO optimized simulated annealing (HPSO-SA) algorithm to optimize the parameters of a seedling picking mechanism; the research results showed that the method improved the success rate of seedling picking up to 84.46% (Li et al. 2022). Nath, P. et al. used HPSO algorithm to solve the routing problem of Very Large Scale Integration (VLSI) technology; the research results show that this method has generated a safer and more consistent solution (Nath et al. 2022). Sheela, MS. et al. established a COVID-19 diagnostic model using HPSO optimized support vector machine (SVM); the experimental results show that the sensitivity of this method for COVID-19 diagnosis is 0.956, and the accuracy is 95.78% (Sheela and Arun 2022). Zhao, L. et al. used HPSO algorithm to solve the optimization problem of radio power allocation; the experimental results show that the model has good robustness, fast convergence speed and good optimization effect (Zhao and Zhou 2022). Ali, ES. et al. used HPSO optimization Sine Cosine Optimization (SCO) algorithm to solve the problem of renewable energy planning in unbalanced distribution systems; the experimental results show that this method can reduce the power loss to 89% and the imbalance index to 34% (Ali et al. 2022).

Through literature survey, it is found that HPSO algorithm has a wide range of applications in solving nonlinear optimization problems, which are providing a new solution to the problem of weak path planning ability of traditional inspection robots.

In order to meet the performance requirements of path planning for home cleaning robots on path smoothness and response speed, Liu, LS. et al. proposed an algorithm based on optimized A-star; the research results show that this method reduces the path planning time by 60% and the time by 65.2% (Liu, Wang, and Xu 2022). Guo, B. et al. proposed an improved A-star algorithm, and the research results show that this algorithm can shorten the traversal path to 40 steps, while the traditional A-star algorithm requires 54 steps (Guo et al. 2022). In order to solve the problem of multiple search nodes, Liu, HX. et al. proposed an ASL-DWA (A-star Leading Dynamic Window Approach); the research results show that this method has obvious advantages compared with the traditional algorithm (Liu and Zhang 2022). For complex multi-ship encounter scenarios, He, ZB. et al. proposed a dynamic collision avoidance path planning algorithm based on a-star algorithm and ship navigation rules; the research results show that this method can generate more reasonable obstacle avoidance paths (He et al. 2022). To ensure that overtaking is smooth, fast and safe, Malayjerdi, E.et al. proposed sigmoid A-star algorithm; the experimental results show that the sigmoid A-star algorithm leads to a smoother and more relevant motion when compared to other two standard methods (Malayjerdi et al. 2022).

Through literature survey, it is found that A-star algorithm can effectively solve the robot path planning problem. The HPSO algorithm is a random search algorithm based on group cooperation (), therefore, this paper combines the HPSO algorithm with A-star algorithm and proposes a path planning method, which for patrol robots based on HPSO-A-star algorithm to solve the problem of weak path planning ability of traditional patrol robots. First, the grid model of the map is established, and the A-star algorithm is used to calculate the path between two inspection points to avoid obstacles at the same time. Then, according to the length of different paths, HPSO algorithm is used to realize the nonlinear path planning, so as to find the shortest inspection route.

The structure of the rest of the article is as follows. In section 2, the HPSO-A-star model is established. In section 3, the HPSO-A-star algorithm is experiment and analysis based on the X enterprise warehouse model. In section 4, the conclusion and discussion is reached.

Model Establishment

HPSO

The HPSO algorithm abstracts the solution of the optimization problem into particles without mass and volume (Cao et al. 2020), and each particle represents three eigenvalues: position, velocity and fitness function value. In each iteration, a specified number of particles are put into the mixing pool according to the hybridization probability. The particles in the pool hybridize with each other to produce the same number of sub-particles, which replace the parent particles (Bilandi, Verma, and Dhir 2020), as shown in Figure 1.

Figure 1. Principle of hybrid particle swarm.

The update of sub-position $c(x)$ and sub-speed $c(v)$ is shown in Equation (1)(1) $c(x)=P\cdot p_1(x)+(1-P)\cdot p_2(x)$(1) and Equation (2)(2) $\begin{array}{rl}& c(v)=\frac{p_1(v)+p_2(v)}{\left|p_1(v)+p_2(v)\right|}\left|p_1(v)\right|\\ & or,c(v)=\frac{p_1(v)+p_2(v)}{\left|p_1(v)+p_2(v)\right|}\left|p_2(v)\right|\end{array}$(2) .

(1) $c(x)=P\cdot p_1(x)+(1-P)\cdot p_2(x)$(1)

(2) $\begin{array}{rl}& c(v)=\frac{p_1(v)+p_2(v)}{\left|p_1(v)+p_2(v)\right|}\left|p_1(v)\right|\\ & or,c(v)=\frac{p_1(v)+p_2(v)}{\left|p_1(v)+p_2(v)\right|}\left|p_2(v)\right|\end{array}$(2)

Where, $P$ represents the hybridization probability, which is 0.75, $p_1(x)$ represents the position of the first parent particle, $p_2(x)$ represents the position of the second parent particle, $p_1(v)$ represents the speed of the first parent particle, and $p_2(v)$ represents the speed of the second parent particle. When two particles trapped in different local optima are hybridized, they can often escape from the local optima. Therefore, the introduction of hybrid algorithm can enhance the global optimization ability of the population.

A-Star Algorithm

A-star algorithm adds a heuristic search strategy, which is generally superior to Dijkstra algorithm in search time (Lawande et al. 2022). A-star uses a function $f(n)$to represent the total cost of a node, the calculation formula is shown in Equation (3)(3) $f(n)=g(n)+h(n)$(3) .

(3) $f(n)=g(n)+h(n)$(3)

Where $g(n)$represents the moving cost from the initial node to the node $n$, and $h(n)$is the heuristic cost from the node $n$ to the target node. The calculation process is shown in Figure 2.

Figure 2. A-star algorithm calculation process.

Establishment of Path Planning Model for Inspection Robot

The problem required to be solved in this paper is that the patrol robot starts from the initial patrol point, goes through all the patrol points without repetition, and then gets a shortest path. The intelligent patrol robot wants to visit $m$ patrol points in the warehouse, and each patrol point only patrols once to find a shortest patrol path. The mathematical model is as follows: If the path length is represented by$d$, then the cost between $i$and$j$of the two patrol points is:

(4) $d_{ij}=f(n_{ij})$(4)

Where $n_{ij}$ means from $i$patrol point to $j$patrol point, the total cost of patrol path is:

(5) $D=\sum _{i=1,j=1}^{i=m,j=m}{d}_{ij}$(5)

Equation (5)(5) $D=\sum _{i=1,j=1}^{i=m,j=m}{d}_{ij}$(5) is the fitness function to be optimized for the algorithm designed in this paper, where $d_{ij}$ is calculated by A-star algorithm and $D$is obtained by HPSO optimization. Therefore, a path optimization model of patrol robot based on HPSO-A-star algorithm can be established. The calculation method is shown in Figure 3, and the specific steps are as follows:

Step 1: Initialize a certain number of particle, and set the speed $v_{p_m}$and position $x_{p_m}$of each particle;

Step 2: Set the starting point of the intelligent inspection robot as the initial position of the A-star algorithm;

Step 3: $f(n_{ij})$is calculated according to the position $x_{p_m}$of each particle, and $D_{ij}$is calculated according to HPSO;

Step 4: Judge whether $D$is optimal. If it is optimal, stop the calculation. If it is not optimal, proceed to the next step;

Step 5: Update particle speed $v_{p_m}$and position $x_{p_m}$;

Step 6: When the particles can no longer produce particles with better performance in the evolution, the algorithm will terminate, return to the particle position with the global optimal performance, and calculate the optimal $D_{best}$. When the termination condition of the algorithm is not met, it will return to Step 2.

Figure 3. HPSO-A-star hybrid algorithm solution flow chart.

To simplify the calculation model, in E.q (3), the cost function is shown in Equation (6)(6) $g_{ij}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}$(6) and Equation (7)(7) $h_{ij}=|x_i-x_j|+|y_i-y_j|$(7) .

(6) $g_{ij}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2}$(6)

(7) $h_{ij}=|x_i-x_j|+|y_i-y_j|$(7)

Experiment and Analysis

Establishment of Map Model

In this experiment, 30 inspection points are selected for the warehouse of X enterprise. Since the A-STAR path optimization algorithm relies on the map grid model, A grid map as shown in Figure 4 is established, in which the size of each grid is $1m\times 1m$. Figure 5 is a simplified map of obstacles in the warehouse of Enterprise X, which defines that the path direction of the patrol robot at each location has only 8 directions, as shown in Figure 6.

Figure 4. Barrier-free grid map model of 30 patrol points.

Figure 5. Grid map model of coordinate obstacles of 30 inspection points.

Figure 6. Restriction of freedom of motion of inspection robot.

HPSO Experimental Analysis

In the barrier-free map model, the patrol robot can realize the straight path between two targets, so HPSO can directly realize the path optimization of the patrol robot. In order to compare the performance of HPSO path optimization model in the accessibility map model, HPSO and PSO are compared. The shortest distance and average distance obtained by each iteration are shown in Figures 7, Figures 8, 9 and Figure 10. The number of particle swarm is 500, and the number of iterations is 2000.

Figure 7. PSO iteration results.

Figure 8. PSO path planning.

Figure 9. HPSO iteration results.

Figure 10. HPSO path planning.

It can be seen from Figure 7 that the PSO model can realize the path optimization problem. When the iteration is about 600 times, the algorithm converges. At this time, the optimal path is shown in Figure 8, and the shortest distance is 156.76 m. As can be seen in Figure 9, HPSO converges after 28 iterations. At this time, the optimal path is shown in Figure 10, and the shortest distance is 147.82 m. Through comparative analysis, the result of PSO model calculation is a local optimal solution, not a global optimal solution, and the convergence speed of HPSO is faster than that of PSO, and the optimal path is shortened by 5.71%. The experimental results show that HPSO has more performance in solving the problem of path optimization for patrol robots.

A-Star Model Experiment Analysis

In the obstacle map model, the patrol robot cannot achieve the straight path between two targets, so HPSO cannot meet the requirements, while A-star algorithm can achieve obstacle avoidance and path optimization of the patrol robot. Set No. 1 patrol point as the starting position and No. 12 patrol point as the ending position. The path optimization results of A-star model are shown in Figure 11.

Figure 11. A-star algorithm optimization path from No.1 patrol point to No.12 patrol point.

According to the analysis in Table 1, the optimal path length from patrol point 1 to patrol point 12 is 12.6 m, and the number of search grids of A-star algorithm in Figure 11 is 68. To verify the relationship between the optimal path length and the grid size of the map model, change the map grid size to $0.5m\times 0.5m$, set No.1 patrol point as the starting position, and No. 12 patrol point as the ending position. The path optimization results of the A-star model are shown in Figure 12. Compared with Figures 11 and 12, the optimal path is similar. It is calculated that the optimal path length in Figure 12 is 12.30 m, and the number of search grids of A-star algorithm in Figure 13 is 165. The experimental results show that the smaller the map grid size is, the better the calculated optimal path length is, but it will consume more computing resources.

Figure 12. A-star algorithm optimization path from No. 1 patrol point to No. 12 patrol point (grid size reduced).

Table 1. Cost table of A-star algorithm optimization path from No. 1 patrol point to No. 12 patrol point/m.

Point	1	A	B	C	D	E	F	G	H	I	J	12
$g(n)$	0	1.4	2.4	3.4	3.8	5.2	7.2	8.6	9.6	10.6	11.6	12.6
$h(n)$	15	13	12	11	10	8	6	4	3	2	1	0
$f(n)$	15	14.4	14.4	14.4	13.8	13.2	12.6	12.6	12.6	12.6	12.6	12.6
Sum	12.6

Experimental Analysis of HPSO-A-star Model

In order to verify the performance of the HPSO-A-star model, the HPSO-A-star model is compared with the PSO-A-star model, and the obstacle map shown in Figure 5 is input into the HPSO-A-star model and the PSO-A-star model. The change process of the cost function in the training process of the HPSO-A-star model is shown in Figure 13. It can be seen that each path has achieved path optimization, in which 1->12 and 27 ->30 steps are the longest, reaching 12 steps. Combined with the obstacle map analysis shown in Figure 5, the reason is that the A-star algorithm has a better obstacle avoidance effect because of the obstacle crossing.

Figure 13. Cloud chart of cost function change in HPSO-A-star training process.

The path of PSO-A-star model optimization results is shown in Figure 14, and the path of HPSO-A-star model optimization results is shown in Figure 15. Through comparative analysis, it can be seen that PSO-A-star model can also achieve path optimization, but the optimal solution obtained is not global optimal, and the path of optimization results is turbulent. The optimal solution obtained by HPSO-A-star model is orderly, as can be seen from the Figures 14 and 15, the optimal solution of HPSO-A-star model is better than that of PSO-A-star model.

Figure 14. Path diagram of PSO-A-star optimization results.

Figure 15. Path Diagram of HPSO-A-star optimization results.

The total path length of HPSO-A-star model is 151.53 m, and that of PSO-A-star model is 215.82 m. The path of HPSO-A-star model is 29.79% shorter than that of PSO-A-star model. In terms of path length, the optimal solution of HPSO-A-star model is better than that of PSO-A-star model.

Conclusion and Discussion

In the production and operation of enterprise warehouse management, robot inspection plays an important role in ensuring production safety. In order to solve the problems of path overlap and automatic obstacle avoidance during robot inspection, a path optimization method combining HPSO algorithm and A-star algorithm was proposed. A path planning model of inspection robot based on HPSO-A-star algorithm is established to improve inspection efficiency in obstacle maps.

Combined with the map model of X enterprise warehouse, the experimental analysis in the barrier-free map shows that the path length of HPSO planning is 5.71% shorter than that of PSO planning. Through the experimental analysis in the obstacle map, the A-star algorithm can realize the obstacle avoidance and path planning of the patrol robot in the warehouse of X enterprise. Through the comparison experiment between the HPSO-A-star model and the PSO-A-star model, the results show that the path of the HPSO-A-star model is 29.79% shorter than that of the PSO-A-star R model, and the HPSO-A-star model can achieve the optimal path planning of the patrol robot.

PSO algorithm is a random optimization algorithm based on population, which can solve the optimal value of the moderate function with high efficiency. Therefore, in principle, the PSO-A-star model can also realize the optimal path planning of inspection robots, but the experimental results show that the HPSO-A-star model has a better path planning, indicating that the PSO-A-star model has not found the optimal path. The root cause of this phenomenon is that PSO algorithm falls into local optimality in the solution domain. It is precisely because of the introduction of hybridization mechanism so that when HPSO algorithm falls into local optimality in the solution domain, some hybrid particles can jump out of this local optimality, and the global optimality of fitness function in the solution domain can be obtained through further iterative calculation.

The research results of this paper also have some limitations. In order to facilitate the development of the experiment, the map in the research process is a simplified two-dimensional simulation map, while the actual warehouse map is more complex, even a three-dimensional space map. Therefore, the application adaptability of HPSO-A-star model in more complex maps needs to be further studied, and it is also an important direction of future research work. On the other hand, the research results of this paper are based on numerical simulation, and the actual application effect needs to be combined with inspection robots to further carry out field experiments, which is another important direction of future research.

The introduction of hybridization mechanism is an important method to solve the problem that PSO algorithm is easy to fall into local optimal. The further research of this method has important significance to improve the performance of PSO algorithm. The research results of this paper can not only solve the optimal planning problem of robot inspection path, but also have certain theoretical reference value in the fields of logistics distribution, product transportation and urban road planning, especially for the automatic obstacle avoidance research of inspection robots.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

Due to the nature of this research, participants of this study did not agree for their data to be shared publicly, so supporting data is not available.