Research on Path Optimization Method for Warehouse Inspection Robot

ABSTRACT

With the increasing popularity of intelligence, many enterprises’ warehouse inspection work is completed through robots. However, due to the multiple target points of warehouse inspection, the low efficiency of planning intelligent robot inspection paths is a problem that needs to be solved. In order to solve the above problems, this paper proposes an HPSO-ACO algorithm based on hybrid particle swarm optimization (HPSO) to optimize the parameters of the ant colony optimization (ACO) algorithm, and establishes a path optimization model for intelligent inspection robots in warehouse management. Compared with HPSO algorithm and ACO algorithm, the experimental results show that the proposed method has faster convergence speed, fewer iterations, and shorter optimal path under the same conditions, which provides a theoretical reference for path optimization for inspection robot.

Introduction

With the rapid development of the logistics industry, the demand for standardized warehouse management is increasing. With the increasing popularity of intelligence (Xu 2008), many enterprises use warehouse inspection robots for daily patrol work, comprehensively utilizing the internet of things and artificial intelligence technology to achieve control of inspection machines (Kalinov et al. 2021). The path planning of inspection is a key issue in robot automatic navigation (Wang et al. 2019), the purpose is to select the shortest and most efficient course of action for the robot under multi-objective conditions (Zhu et al. 2021). However, due to the lack of efficient path planning algorithms as technical support, traditional inspection robots have weak computing power and high resource consumption problems in path automatic planning (Sik et al. 2014). Multi-objective path planning of inspection robots is essentially a traveling salesman problem (Bao et al. 2023), so using heuristic algorithms to solve this problem has become an important research direction (Majumder, Majumder, and Bhaumik 2021).

In view of the above problems, Duguleana, M. et al. combined Q-learning with neural network algorithm, collision-free trajectory planning of mobile robot in uncertain workspace is realized (Duguleana and Mogan 2016). Xiong, N.Z. et al. proposed a time taboo ACO algorithm, which improved the slow convergence and poor global search ability of ACO path planning in a dynamic environment (Xiong et al. 2021). Huang, M.D. et al. proposed a robot path planning method combining angle factor and visibility; the experimental results show that it is superior to genetic algorithm and traditional ant colony algorithm in global path planning (Wang, Wang, and Jiang 2015). Porta, G.M. et al. proposed a new scheme based on simple ACO. The experimental results show that the method effectively improves the speed of path planning (Garcia et al. 2009). Xuan，R.Z. et al. proposed a robot path planning method using ant colony algorithm to optimize A * algorithm, the experimental results show that the search path of this method is better than A * algorithm (Xuan et al. 2018).

Through literature survey, it has been found that optimization algorithms have wide applications in robot path planning and can provide robots with optimal planning routes. A comparison of several common optimization algorithms is shown in Table 1. Tabu search optimization (TSO) and simulated annealing (SA) algorithms are single body optimization algorithm (Gu et al. 2023; Wang, Wu, and Glover 2017), which have smaller search space in the solution domain and lower solving efficiency. ACO is an algorithm structure (Zou et al. 2013), while HPSO is a random search algorithm based on group collaboration (Kadavy et al. 2018). The characteristics of both HPSO and ACO are swarm body optimization algorithms, which can receive inferior solutions in the form of a single unit, that is, jump out of local optima; therefore, they are more widely used in solving path planning problems for inspection robots.

Table 1. Comparison of several common optimization algorithms.

Algorithms	single body/swarm body	Solution method	Inferior solution acceptance method
HPSO	Swarm body	Update global optimal solution with group optimal solution	Accept inferior solutions through hybridization
ACO	Swarm body	Using the solution with thicker pheromones and smaller spacing as the optimal solution	Accept inferior solutions with probability
TSO	Single body	Selecting optimal solutions to generate neighborhoods	There is a chance of obtaining suboptimal or inferior solutions
SA	Single body	Better solutions must be accepted	Accept inferior solutions with probability
HPSO-ACO	Swarm body	Receive the optimal solution based on pheromones and city spacing	Accept inferior solutions through hybridization

Ming, L. Y. et al. proposed a fusion model based on adaptive ACO and HPSO, and realized the path planning of intelligent robot in a disturbed environment (Ming et al. 2019). Wei, P.C. et al. proposed a grid scheduling optimization algorithm based on HPSO algorithm and ACO algorithm, which effectively improved the efficiency of task scheduling (Wei and Shi 2010). Kuo, R.J. et al. proposed a new HPSO combining ACO and HPSO, which effectively solved the job shop scheduling problem (Kuo and Cheng 2013). Wu, C. Z. et al. introduced an improved ACO to replace the road factor, effectively reducing the average urban road congestion rate of 9.73%~13.63% (Wu, Zhou, and Xiao 2020).

Existing literature focuses more on solving practical problems, but in the process of robot path automatic planning, the issue of computing power and resource consumption is particularly important, but it has received little attention. Meanwhile, through a literature survey, it is found that the combination of HPSO algorithm and ACO algorithm can improve the overall performance of the algorithm. Therefore, this paper proposes a path planning method for patrol robots based on HPSO to optimize ACO, to solve the problem of weak path planning ability of traditional inspection robot. In this method, HPSO is used to optimize the parameters of the ACO. At the same time, we improve the pheromone updating method, to improve the convergence iteration speed and local search ability of the ant colony algorithm.

This article has made the following contributions: combining HPSO and ACO to establish an HPSO-ACO algorithm, which improves the optimization ability of HPSO algorithm and ACO algorithm. Based on the HPSO-ACO algorithm, a path optimization model for intelligent warehouse inspection robots was established, achieving path optimization of inspection robots under multi-objective conditions.

The structure of the rest of the article is as follows. In chapter 2, the relevant models are established and the improved ACO based on HPSO is introduced. In chapter 3, the comparative simulation analysis of the above models and algorithms is presented, and finally puts forward a conclusion and discussion.

Model Establishment

ACO

The principle structure of the ACO is shown in Figure 1. The path is continuously optimized according to the smell trace until the optimal path is found (Sun 2023).

Figure 1. The principle structure of the ACO.

$P_{ij}^k(t)$ means the probability that the ant $k$ chooses to move to the $j$ patrol point when it is currently at the $i$ patrol point, the formula is as follows:

(1) $P_{ij}^k(t)=\left\{\begin{array}{cc}\frac{{\tau }_{ij}^{\alpha }(t){\eta }_{ij}^{\beta }(t)}{\sum {\tau }_{ij}^{\alpha }(t){\eta }_{ij}^{\beta }}& ,\mathrm{j}\in allow{d}_k\\ 0& ,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.$(1)

where ${\tau }_{\mathrm{i}\mathrm{j}}^{\hspace{0.17em}}\left(\mathrm{t}\right)$ represents the pheromone concentration at the patrol point $j$ and on the route of the patrol point $i$ at $t$ time, ${\eta }_{ij}(t)$ is a heuristic factor, ${\eta }_{ij}(t)=\text{1}/\text{{{d\_{ij}}}}$ is taken here, $d_{ij}$ is the distance between the patrol point $i$ and the patrol point $j$, and $allowe{d}_k$ is the set of the next patrol point that the $k$ ant can select, $\alpha$ indicates the degree of importance attached to the path, and $\beta$ indicates the degree of importance attached to heuristic information.

HPSO

Particle Swarm Optimization (PSO) is a kind of swarm intelligence algorithm, which abstracts the solution of the optimization problem into particles without mass and volume, and each particle exhibits three eigenvalues: position, velocity, and fitness function value. Let the number of particles be $N$, in the D-dimensional search space, the position of particle $i$ is $X_i=[x_{i,1},x_{i,2},\cdots ,x_{i,d}]$ and the speed is $V_i=[v_{i,1},v_{i,2},\cdots ,v_{i,d}]$, which is controlled by the best position of the particle itself and the global best position, and is continuously updated until the optimal solution is found (Liang et al. 2019). The way of updating the position and velocity of particles as in

(2) $\begin{array}{rl}& v_{i,j}(t+1)=v{w}_{i,j}(t)+c_1{r}_1[p_{i,j}-x_{i,j}(t)]+c_2{r}_2[p_{g,j}-x_{i,j}(t)]\\ & x_{i,j}(t+1)=x_{i,j}(t)+v_{i,j}(t+1),j=1,2,\cdots ,d\end{array}$(2)

where $w$ is the inertia weight, $t$ is the current iteration number, $c_1$ and $c_2$ are the learning factors, $r_1$ and $r_2$ are the random numbers from 0 to 1. In the process of optimization, the conventional particle swarm optimization algorithm may converge to local optimal solution, which leads to a large calculation error. Drawing on the concept of hybridization in genetic algorithm, in each iteration, according to the probability of hybridization, a specified number of particles are put into the mixing pool, and the particles in the pool are hybridized with each other to generate the same number of child particles, which replace the parent particles (Bilandi, Verma, and Dhir 2020), as shown in Figure 2.

Figure 2. The principle structure of the HPSO.

The sub-position $child(x)$ and sub-velocity $child(v)$ updates as in

(3) $\begin{array}{rl}& child(x)=p\cdot paren{t}_1(x)+(1-p)\cdot paren{t}_2(x)\\ & or,child(x)=(1-p)\cdot paren{t}_1(x)+p\cdot paren{t}_2(x)\end{array}$(3)

(4) $\begin{array}{rl}& child(v)=\frac{paren{t}_1(v)+paren{t}_2(v)}{\left|paren{t}_1(v)+paren{t}_2(v)\right|}\left|paren{t}_1(v)\right|\\ & or,child(v)=\frac{paren{t}_1(v)+paren{t}_2(v)}{\left|paren{t}_1(v)+paren{t}_2(v)\right|}\left|paren{t}_2(v)\right|\end{array}$(4)

When two particles trapped in different local optima perform hybridization operations, they can often escape from the local optima. Therefore, the introduction of hybridization algorithm can enhance the global optimization ability of the population.

HPSO-ACO

ACO works out the optimal path according to the change of pheromone concentration. As it belongs to the classical probability algorithm, the initial parameters of the algorithm are randomly given according to people’s experience, which leads to poor stability of the algorithm. On the contrary, unlike ACO, HPSO has the ability to quickly jump out of local optima and can quickly and effectively optimize the parameters of ACO. Therefore, this paper uses HPSO to optimize the parameters $\alpha ,\beta ,\rho$ of ACO to solve the intelligent inspection path optimization problem.

The process of HPSO-ACO is shown in Figure 3, and the specific steps are as follows:

Figure 3. Solution flow chart of HPSO-ACO.

Step 1: initialize a certain number of particles$p_0,p_1,\dots ,p_m$;

Step 2: Feedback the parameter value corresponding to each particle back to the ant colony algorithm. One particle corresponds to a group of parameters$\alpha ,\beta ,\rho$. Use these parameters to call the ACO once, and then update the pheromone in the environment;

Step 3: Judge the particle position according to the solution results of the ACO, and update the $p_{best}$ and $G_{best}$;

Step 4: Update particle speed and position;

Step 5: When the particles can no longer produce particles with better performance in the evolution, the algorithm will terminate and return to the particle position with the global optimal performance. When the termination conditions of the algorithm are not met, the algorithm will return to Step 2.

Establishment of Path Planning Model for Intelligent Inspection Robot

The intelligent patrol robot wants to visit each patrol point in the warehouse, and each patrol point only patrols once, and finally returns to the initial patrol point to find a shortest patrol path. The mathematical model is as follows: If the path to visit $m$ patrol points is represented by $L$,$L=\left(L_1,L_2,\dots ,L_m\right)$, $L_{\mathrm{m}}=\left({\mathrm{x}}_{\mathrm{m}},{\mathrm{y}}_{\mathrm{m}}\right)$, then the distance between the two patrol points $i$ and $j$ is:

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

The total distance of patrol path is:

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

Eq. (6) is the model to be optimized for the algorithm designed in this paper. The selection of the pheromone updating method has a very important impact on the solution quality of ACO (Zhai et al. 2015). The following is the formula for updating the pheromone of traditional ACO:

(7) ${\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\mathrm{\Delta }{\tau }_{\mathrm{i}\mathrm{j}}(\mathrm{t})$(7)

(8) $\mathrm{\Delta }{\tau }_{ij}(t)=\sum {\tau }_{ij}^k(t)$(8)

In Eq. (7) and Eq. (8), $\rho$ represents the degree of pheromone volatilization, the value range of pheromone is $\left[0,1\right]$, $\mathrm{\Delta }{\tau }_{ij}^k(t)$ represents the amount of pheromone released by ant $k$ in the path interval at this stage of $t$ time, and $\mathrm{\Delta }{\tau }_{ij}(t)$ represents the increase in pheromone concentration. In this paper, the model shown in Eq. (9) is used as the update model of the pheromone volatilization mode.

(9) $\mathrm{\Delta }{\tau }_{ij}^k(t)=\left\{\begin{array}{cc}\frac{Q}{G_k}& \mathrm{a}\mathrm{n}\mathrm{t}\mathrm{k}\mathrm{p}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h}[\mathrm{i},\mathrm{j}]\\ 0& ,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.$(9)

$G_k$ represents the total distance by ants during inspection, and $Q$ refers to the pheromone content. In view of the problem that traditional ACO disable accumulates enough pheromones in a short time, pheromones are updated continuously throughout the algorithm solution process. When parameters change, the pheromones are not reinitialized. This method can retain and accumulate enough environmental information in a short time, greatly reduce the number of ACO iterations, and reduce the time consumption. When there is no optimal solution, the pheromone updating formula is as shown in Eq. (7) and Eq. (8). When a better solution appears, the concentration of pheromones left by elite ants will be enhanced, and pheromones will be updated according to the following formula:

(10) ${\tau }_{ij}(t+1)=\left(1-\rho \right){\tau }_{ij}(t)+\mathrm{\Delta }{\tau }_{\mathrm{i}\mathrm{j}}(\mathrm{t})+\mathrm{\Delta }{\tau }_{\mathrm{i}\mathrm{j}}(\mathrm{t}{)}^{\mathrm{\prime }}$(10)

In Eq. (10), ${\tau }_{ij}(t)$is obtained from Eq. (9). $\mathrm{\Delta }{\tau }_{ij}(t{)}^{\mathrm{\prime }}$ is the pheromone concentration left by ants on the optimal path $[i,j]$ during the path iteration solution process, and includes:

(11) $\mathrm{\Delta }{\tau }_{\mathrm{i}\mathrm{j}}(\mathrm{t})=\left\{\begin{array}{cc}\frac{\mathrm{Q}}{{\mathrm{G}}_{\mathrm{k}}}& ,[i,j]\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\\ 0& ,\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\end{array}\right.$(11)

Therefore, step 2 can be changed into: return the parameter value corresponding to each initial particle to the ACO. One particle corresponds to one group of parameters$\alpha ,\beta ,\rho$, uses this group of parameters to operate the ACO. When the parameters change, the pheromone will not be reinitialized

Experiment and Analysis

Case Analysis

In order to verify the performance of HPSO-ACO inspection algorithm, this experiment uses the example of X enterprise warehouse with 30 inspection points to carry out path, using HPSO algorithm, ACO algorithm, and HPSO-ACO algorithm, respectively, to verify that the algorithm proposed in this paper is superior to the other two algorithms. At the same time, in order to achieve point-to-point movement of the inspection robot on a flat map, it is assumed that the robot can freely move according to instructions on the flat map without constraints. The coordinates of 30 inspection points in X enterprise warehouse are shown in Figure 4.

Figure 4. Coordinates of 30 patrol points.

Simulation Analysis of ACO

Through multiple experiments, the number of ants was set to 50, the number of iterations was set to 200, the pheromone importance factor was set to 1, the heuristic function importance factor was set to 5, and the pheromone volatilization factor was set to 0.1. The shortest distance and average distance obtained from each iteration are shown in Figure 5, where the average distance is the average of the distances calculated for each feasible solution. The ACO plans the path as shown in Figure 6.

Figure 5. ACO iteration results.

Figure 6. ACO path planning.

It can be seen from Figure 5 that the ACO performs well in solving the problem of path optimization this time, and the convergence speed of the algorithm is relatively fast. It converges in 55 iterations, and the shortest distance is 1659.62 m, time consumption 7.145 s. The ACO uses a positive feedback mechanism and has a certain global optimization ability, so the mature ACO can quickly and effectively obtain the optimal solution.

Simulation Analysis of HPSO

Through multiple experiments, the number of particles was set to 500, the number of iterations was set to 2000, and the inertia weight was set to 0.75. The iterative results in the optimization process of the HPSO algorithm are shown in Figure 7, and the path planning of the HPSO algorithm is shown in Figure 8.

Figure 7. HPSO iteration results.

Figure 8. HPSO path planning.

From Figure 7, it can be seen that the performance of the HPSO algorithm is average. Due to the fast convergence speed in the initial stage and the slow convergence speed in the later stage, the overall convergence time is relatively long. It took 939 iterations to converge, taking 23.548 s, and the shortest distance is 1743.45 m.

Hybrid Particle Swarm Optimization Ant Colony

The parameter settings of ACO and HPSO are consistent with the previous text. The iterative results after HPSO optimized ACO are shown in Figure 9, and the path planning after HPSO optimized ACO is shown in Figure 10.

Figure 9. HPSO-ACO process iteration results.

Figure 10. HPSO-ACO path planning.

From Figure 9, it can be seen that the HPSO-ACO converges faster after 42 iterations, taking 6.424 s, and the shortest distance is 1622.87 m.

Experimental Results and Analysis

The performance comparison of the three experimental results is shown in Table 2. HPSO converges after 939 iterations, which is greater than the 55 iterations of ACO algorithm. However, the number of iterations of HPSO-ACO is significantly better than the 939 iterations of HPSO algorithm and the 55 iterations of ACO, indicating that HPSO-ACO saves more computational resources.

Table 2. Comparison of Experimental results of three models.

Model	Number of iterations	Calculation time	Shortest path length
ACO	55	7.145 s	1659.62 m
HPSO	939	23.542 s	1743.45 m
HPSO-ACO	42	6.424 s	1622.87 m

The calculation time of HPSO-ACO is shorter than that of ACO algorithm and HPSO algorithm, indicating that HPSO-ACO has faster calculation speed than ACO algorithm and HPSO algorithm.

The optimal path length calculated by HPSO-ACO is 120.58 m shorter than the optimal path length of HPSO, and 36.75 m shorter than the optimal path length of ACO. It can be explained that the calculation results of the HPSO-ACO algorithm are closer to the global optimal solution, and the optimization effect is better.

Through analysis, it can be seen that the HPSO-ACO reduces the path by 2.21% compared to the ACO and reduces the path by 6.91% compared to the HPSO. In summary, the HPSO-ACO algorithm performs better than the HPSO and ACO algorithms.

Conclusion and Discussion

With the increasing demand for automation in enterprise warehouse management, many inspection tasks are completed through robots. However, due to the multiple target points of warehouse inspection, there are problems such as weak computational power and resource consumption in path automatic planning. A path optimization method based on HPSO and ACO is proposed to achieve automatic path planning for inspection robots. Based on the map model of X enterprise warehouse, experimental analysis shows that HPSO-ACO, compared with ACO and HPSO algorithms, saves more computational resources and has faster calculation speed in optimizing the closed-curve inspection path. The automatically planned inspection robot path is more optimal. This method not only improves the inspection efficiency of robots but also reduces inspection costs.

The ACO algorithm has the characteristic of positive feedback, which can easily lead to the algorithm falling into local optima, and parameter selection is more dependent on experience and trial and error. Improper initial parameters can weaken the algorithm’s optimization ability. The initial convergence speed of the HPSO algorithm is relatively slow, but its internal hybridization mechanism does not rely on problem information, which can promote the algorithm to jump out of local optima well. The HPSO-ACO algorithm can rely on the hybrid mechanism of HPSO, making it easier for the ACO algorithm to jump out of local optima, accelerating the overall solving speed of the algorithm, and improving its optimization ability.

The research results of this article also have some limitations. In order to facilitate the experiment, the map has been simplified, and in actual warehouse environments, various obstacles will inevitably appear. In map environments with obstacles, to achieve robot path planning and automatic obstacle avoidance, it is necessary to combine it with other new algorithms, and the adaptability of the HPSO-ACO model needs further research. On the other hand, this project uses a two-dimensional map. If the actual warehouse map is a three-dimensional spatial map, further experiments are needed to demonstrate the performance of the HPSO-ACO model.

The HPSO-ACO algorithm can effectively improve its global optimization ability on the existing basis, which has certain guiding significance for solving the traveling salesman problem. At the same time, the research results of this study also have certain promotion value in urban road planning, commodity distribution, and unmanned aerial vehicle automatic navigation.

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 are not available.