Path planning of mobile robot based on improved ant colony algorithm for logistics

1.   Introduction

In the process of rapid development of modern logistics industry, intelligent sorting is one of the key links to ensure that the logistics process can make timely classification of massive material demand ^[1,2]. The path planning of logistics sorting robot is the current hot research direction, which has a wide range of application prospects in the fields of warehousing and logistics, industrial production, sorting and distribution.

Path planning of mobile robot is an important topic in the field of robot research. Its goal is to find a collision free optimal or suboptimal path from the starting point to the end point in the environmental model. In terms of path length, path smoothness, running time and security, path planning constantly pursues more optimized models and algorithms ^[3].

According to the prior knowledge of robot environment, path planning can be divided into global planning and local planning. Global path planning is to calculate the best path from the starting point to the end point according to the previously known environmental information. This kind of algorithm is suitable for the situation that all environmental information is known. Global path planning algorithm mainly includes ant colony algorithm, genetic algorithm, fast random search tree algorithm and so on ^[4]. Local path planning has less prior knowledge of the environment, only the current range of environmental information. Local search algorithms include artificial potential field algorithm, artificial neural network algorithm, fuzzy algorithm and so on ^[5].

Rath introduce the feedback idea of control theory to realize the dynamic adaptive adjustment of the parameters of ant colony algorithm, so as to optimize the parameters of the algorithm. On the premise of low time complexity, the obstacle free operation path is planned ^[6]. Gul propose a bi-directional smoothing algorithm based on variable step size, which enables the random tree to adjust the step size to avoid obstacles when new nodes encounter obstacles. Then, greedy thinking is used to deal with the remaining path spikes. This method not only retains the advantages of small randomness, but also greatly improves the efficiency of path search ^[7]. By introducing elitist strategy and designing a new smoothing method, Hasan solve the problem of unnecessary inflection point in ant colony algorithm ^[8]. By expanding the search neighborhood and increasing the possibility of search direction in the grid environment, Dewangan reduce the length of the search path of the improved algorithm and effectively solve the problem of path redundancy ^[9]. By introducing the maximum minimum ant colony system to limit the updated pheromone concentration, Kawasaki solve the problem that the pheromone difference of ant colony algorithm is too large and fall into precocity, and narrow the scope of finding the optimal path ^[10]. Ghathwan design the search model of dynamic search inducer, and accelerate the convergence speed of ant colony algorithm at the initial stage of search, so as to optimize the quality of the solution ^[11].

Aiming at the needs of mobile robot path planning in logistics sorting work, this paper improves ant colony algorithm and designs a new adaptive variable step size path planning method. The advantage of this method is that the multi-step search strategy improves the field of vision and the smoothness of the path. At the same time, through the design of updating pheromone function, it solves the problem that ant colony algorithm is easy to enter the local optimum in the iterative process, which makes unnecessary spikes appear in the path.

2.   The proposed method

2.1.   Ant colony algorithm

In the research process of mobile robot path planning, the first step is to choose a reasonable and effective state space description method, so as to establish an accurate, reliable, easy to code and update environment map. The commonly used methods are grid method, geometry method and topology method. This paper uses simple, reliable, descriptive and strong grid method for environment modeling. In the $n \times n$ grid environment of, the relationship between the grid number and the coordinates is as follows:

Here, $x$, $y$ represents the current coordinates of the robot. $W$ represents the total width of the grid, and $\bmod ()$ represents modular operation. n is the side length of square grid environment.

Ant colony algorithm is a bionic heuristic algorithm. In the natural environment, ants can instinctively find the optimal or suboptimal path from a certain location to the food source. Therefore, ant colony algorithm had been put forward and widely used in a variety of optimization problems ^[12,13].

The main steps of ant colony algorithm are as follows: At time t, the probability transfer formula of the k^th ant from node i to node j is as follows:

Here, ${\rho _{ij}}(t)$represents the pheromone concentration of the mobile robot moving from point i to point j. ${\eta _{ij}}(t)$ represents the heuristic coefficient of the mobile robot moving from point i to point j. ${\eta _{ij}} = \frac{1}{{{d_{ij}}}}$. ${d_{ij}}$ represents the distance between grid i and grid j.

After completing a cycle, ants will leave pheromones on the path they pass, and the original pheromones of the path will continue to volatilize and decrease. The updating formula of pheromone is as follows:

Here, $Q$ represents pheromone strength. ${L_k}$ is the length of the ant k-th cycle path.

Classical ant colony algorithm has the advantages of strong robustness, parallelism and easy to combine with other algorithms, but in the case of improper search or high area and complexity of environment map, its convergence speed is slow, running time is long, easy to fall into local optimum! Ants are easy to fall into a path node and lead to "path deadlock".

2.2.   Multi step search strategy

The classic ant colony algorithm uses a single step to search, as shown in Figure 1(a), that is, the algorithm step is fixed to 1, and the robot can only take the grid of adjacent positions as the next step's destination. This leads to slow convergence speed and redundant path peak, and may make the path unable to achieve the optimal or suboptimal. Multi step moving strategy, that is, each moving is not limited to one grid length, as shown in Figure 1(b), that is, the schematic diagram of step field of view range of 2. Considering that the larger the step size of mobile robot, the wider the field of vision and the shorter the length, the possibility of generating redundant path nodes is smaller and the path is smoother. Therefore, when choosing the next foothold, the priority from far to near is generally adopted.

2.3.   Pheromone update strategy

For the disadvantage that traditional ant colony algorithm is easy to fall into local optimum, the pheromone addition mechanism is introduced firstly. When each ant goes through a cycle, the traditional ant colony algorithm can find the optimal solution. Additional compensation design is given to pheromone. In this way, the pheromone corresponding to the optimal solution is enhanced when the information is transmitted between ants through pheromone. The pheromone enhancement of the optimal solution has a greater impact on the ants passing behind. In this way, ant colony algorithm can avoid falling into local optimum in the iterative process. The formula of pheromone addition is as follows:

Here, ${\rho _{ij}}(t)$ is pheromone at t moment, and ${\rho _{ij}}(t + 1)$ is pheromone at (t+1) moment, ${\rho '_{ij}}(t)$ is compensation items.

Here, $\Delta {\rho '_{ij}}$ indicates that the pheromone of ants on the path increases. $L'$ shows the path length corresponding to the optimal solution found at the end of this cycle. $solutio{n_{obt}}$ represents the set of optimal solutions.

Aiming at the problem that traditional ant colony algorithm is easy to fall into the U-shaped path, which makes the algorithm unable to continue to implement, the pheromone decreasing mechanism is introduced. The so-called pheromone decreasing mechanism allows an ant to step back when it is trapped in a path. Update the tabu list information and weaken the pheromone around it. As time goes on, the attraction of this path becomes less and less, so as to avoid the algorithm falling into deadlock. This processing improves the global search ability and environmental adaptability of ant colony algorithm. At the same time, this processing can avoid the stagnation of the algorithm and enhance the anti-jamming ability of the algorithm. The decreasing formula of pheromone is as follows:

Here, $\lambda$ represents the penalty coefficient. Size of $\lambda$ is directly proportional to the number of times the ant has fallen into a U-shaped deadlock before. t represents the current time node.

2.4.   Path optimization strategy

In this paper, we use the peak smoothing method based on the center point, that is, adding new nodes to replace the old nodes in the unprocessed path peak. The selection and addition of new nodes have a direct impact on the improvement of path smoothness and the efficiency of the overall path planning. Considering that the turning angle of robot is limited in the actual situation, increasing the original turning angle has stronger practicability and environmental adaptability.

If the value of the actual turning angle $\alpha$is less than the expected value of the angle$\beta$, take the midpoint $({x_{new1}}, {y_{new1}})$ and $({x_{new2}}, {y_{new2}})$ between the feasible regions of the two line segments, and then judge whether the new turning angle meets the expected value of the angle respectively. If not, repeat the above steps until the angle size meets the condition. And then judge whether other inflection points in the path meet the conditions, and repeat until the smooth operation is completed.

2.5.   Algorithm flow design

The first step is to initialize the parameters of ant colony algorithm and set the static grid environment to initialize the tabu list.

In the second step, m ants are randomly distributed to each node and the starting point is added to the tabu list.

In the third step, according to the multi step selection strategy, the candidate grid set is determined and the next moving grid is selected, and then the current grid is added to the tabu list.

The fourth step is to judge whether the ant is in a U-shaped deadlock state when searching the path. If so, step back and execute pheromone decrement mechanism according to formula (8). If not, proceed to the next step.

In the fifth step, Eq (7) implements the pheromone addition mechanism to update the pheromone.

The sixth step is to judge whether the end condition of the algorithm is met. If so, the next step will be executed, otherwise the iteration will continue.

The seventh step is to keep the shortest path as the optimal path and output the result.

The pseudo code design of the above process is as follows:

3.   Experimental results and analysis

3.1.   Experimental condition

In the experiment, the configuration of the computer is Intel 8-core CPU, and the main frequency is 3.8G Hz. The memory is DDR4, 16 GB. The software environment used in the experiment is Matlab 2014.

In order to verify the effectiveness of the improved ant colony algorithm proposed in this paper for mobile robot in logistics path planning, the next experimental study is carried out. In the experiment, the map in the logistics warehouse was set to be 16 * 16 grids, and the actual side length of each grid was 1 meter. In this experiment, the starting point of the mobile robot is at the grid with coordinates of (1, 16), and the ending point is at the grid with coordinates of (14, 1).

In the experiment, the configuration of ant colony algorithm is: the total number of ants is 30, the maximum number of iterations is set to 300, and the heuristic factor $\alpha = 1.0$, and $\beta = 5.0$. Evaporation coefficient $\lambda = 0.5$, pheromone factor $Q = 100$, and enalty coefficient $\kappa = 0.3$.

According to the traditional ant colony algorithm, the path of the robot in the warehouse map is shown in Figure 2.

In Figure 2, the green dot represents the starting position of the logistics robot, the pink dot represents the ending position of the logistics robot, and the red thick line represents the path planned by the traditional ant colony algorithm. The white grid represents the area where the robot can walk, the black sand grid represents the shelf area where the items are placed, and the robot cannot walk. As can be seen from Figure 2, affected by the one-step field of vision, the robots turn right angles, thus forming a path composed of multiple broken lines. Such a path not only has a long absolute distance, but also has a great impact on robot steering and tire wear.

In order to further form a comparison with traditional ant colony algorithm, we use the simultaneous interpreting method of this paper and ^[14] to execute the path planning again. The result is shown in Figure 3.

In Figure 3, the blue thick solid line is the path planned by the improved ant colony algorithm for the logistics robot. This path contains seven key points such as ABCDEFG. Compared with the path planned by the traditional ant colony algorithm in Figure 2, we can see that in this path, the logistics robot starts to walk two diagonal grids at point a and reaches point B. The section from point C to point D is also a diagonal of two grids. From point E to point F, the planning path selects the diagonal of the larger area. From point F to point G, we take the diagonal of two grids. In this way, the length of the path is significantly reduced. At the same time, the turning angle of the robot becomes smaller at the inflection point, which reduces the mechanical wear of the robot tire and other parts. The reason why this effect can be formed is that the improved ant colony algorithm in this paper has played a role in expanding the field of vision and improving the pheromone update strategy.

In Figure 3, the green thick solid line is the result of path planning obtained by the method of reference ^[14]. It can be seen from the comparison that the effect of the method in ^[14] is better than that of the traditional ant colony algorithm, but there are still right angle turns in some areas. From the effect of path planning, the method proposed in this paper is slightly better than that in ^[14].

Some results of three algorithms are further compared, as shown in Table 1.

In Table 1, the average path length planned by this method is 28.14, which is significantly shorter than 30.88 planned by traditional ant colony algorithm. At the same time, the optimal path length planned by this method is 24.53, which is shorter than 27.02 planned by traditional ant colony algorithm.

It can be seen from the data in Table 1 that the average path and optimal path planned by the improved ant colony algorithm for the logistics robot in this paper are greatly reduced. However, the increase of the number of iterations and the time consumption is not obvious, which proves the advantages of the improved ant colony algorithm.

In order to investigate the robustness of the proposed method, the map scene is replaced, and the path planning results of the three methods are compared again, as shown in Figure 4.

As shown in Figure 4, the map is extended to 18 * 18 grid areas. Red implementation still represents the traditional ant colony algorithm, blue real line represents the ant colony algorithm improved in this paper, and green real line represents the method of literature ^[14]. From the results of Figure 4, it can be seen that the path length and the included rectangular bending of the traditional ant colony algorithm are long. The results of the method in literature ^[14] are much better, but in the planning of large areas, the effect is still weaker than the method proposed in this paper.

Further comparison of other results of this experiment is shown in Table 2.

The comparison of the convergence curves between the method in this paper and the method in reference ^[14] is shown in Figure 5.

4.   Conclusions

The application of robots in the logistics industry greatly improves the operation efficiency, which is of great significance for warehousing, sorting and distribution. In order to improve the mobile efficiency of logistics robot, based on the traditional ant colony algorithm, this paper proposes an improved ant colony algorithm for path planning of logistics robot. In this improved algorithm, the multi-step search strategy is used to replace the single step search strategy, the extra pheromone update mechanism is introduced to prevent the robot from falling into the U-shaped path, and the path smoothing strategy is configured to reduce the wear caused by the large bending rotation of the robot. On the 16 * 16 grid logistics storage site, the path planning results of this method and the traditional ant colony algorithm are compared under the predetermined starting point and key constraints. Experimental results show that: in the case of little increase in algorithm time and iteration times, the improved method can shorten the optimal path by 9.21% compared with the traditional ant colony algorithm. The research results of this paper propose a new method for mobile robot path planning, which improves the efficiency of path planning, and can better serve the storage logistics, goods sorting and other tasks, and has good practicability for the logistics industry.

Acknowledgments

This study was supported by Doctor. Scientific and Research Start-up Project of Harbin University of Commerce (NO.2019DS031) and also by The National Nature Science Foundation of China project (No 71772016 Research on operation mechanism and decision optimization of cross border Logistics Alliance based on cloud platform technology), and Beijing Social Science Foundation Project "Research on Dynamic Collaborative Path of Beijing-Tianjin-Hebei Logistics System under Industrial Transfer" (17GLB020).

Conflict of interest

The authors declare there is no conflict of interest.