Research on Robot Path Planning Technology Combining Ant Algorithm and DWA Algorithm

Introduction

Path planning can be divided into global path planning and local path planning [1]. The global path planning of a robot means that the robot can search for a collision-free path from the starting point to the target point according to static map information under offline conditions. In actual situations, robots usually acquire the surrounding environment information based on the perception system on the robot, such as radar, sensors and other devices. In the real environment, robots often need to enter some unknown environments to perform tasks, and may encounter static or dynamic obstacles. In order to enable robots to safely and smoothly reach the target, Some local path planning algorithms are needed to enable robots to avoid obstacles dynamically, safely and reliably when encountering these obstacles, and to avoid obstacles by avoiding dangers like humans. Therefore, it is of great significance to study a general path planning algorithm that conforms to the characteristics of tasks in the real environment for robotics technology and the strategy of strengthening artificial intelligence robots.

Path Planning Research

Path planning refers to finding feasible motion paths that meet the required standards according to the starting point and end point of the environment in a specific environmental space, and finding feasible path solutions that meet the restricted requirements. In addition, for feasible routes, obstacles can be avoided and the target destination can be reached safely and smoothly. As a key issue in the field of unmanned systems research, path planning is also the primary task of navigation in other fields, which itself represents whether the intelligence of unmanned technology meets the requirements and determines the level of unmanned technology. As various industries begin to use different kinds of intelligent unmanned systems, path planning algorithm, as the core technology, needs to be developed [2].

Ant Algorithm Research

Ant colony algorithm is a bionic algorithm that simulates the foraging behavior of ants in nature. It was first proposed in 1991 by Italian scholar M.Dorigo et al. [3]. Inspired by the ant's foraging behavior, he applied his ideas to the traveling salesman problem (TSP) and proposed the ant colony algorithm. This algorithm has the following advantages: strong stability, better optimization ability and easy parallelization. At the same time, it has the following disadvantages: the algorithm convergence is slow, it is easy to precocious, fall into local optimal, and the algorithm may stall in some cases. Although individual ants have very limited abilities and do not have strong visual and auditory perception systems, the ant colony as a whole exhibits very efficient executive ability and strong self- organization characteristics. Through long-term observation and analysis of ant colony behavior, relevant researchers found that the fundamental reason why ant colonies can show certain intelligence is that ants indirectly complete communication between individuals through a chemical substance called pheromone [4]. In the iteration process, the pheromone on the path will change as the ant moves. For a single ant, choosing the next path according to the level of pheromone concentration is generally a positive feedback mechanism. In 1989, Goss and other researchers further studied the foraging behavior of ants through the famous "double bridge experiment" [5], thus discovering the mystery of pheromones.

DWA Algorithm Research

Dynamic window method (DWA) is relatively strong in real- time and has certain advantages in the amount of computation in moving machines Human local path planning is widely used. The DWA method was developed by Dieter Fox and Wolfram Burgard In 1997, et al. proposed that the general obstacle avoidance algorithm did not take into account the kinematic performance of the robot, but DWA considered the kinematic constraints of the robot, and then they successfully applied it to the obstacle avoidance of mobile robots [6]. Compared with other local path planning algorithms, DWA takes the kinematics constraints of the robot into account, and the obtained velocity and other related physical information can be directly handed to the robot's bottom control layer for control, which can be well combined with path optimization and operation feedback. Seder M et al. combined D* algorithm with DWA, regarded dynamic obstacles as moving grids, predicted the collision point between obstacles and mobile robots, and then generated virtual obstacles according to the collision point. Finally, the two algorithms were used to achieve obstacle avoidance in dynamic environment. Literature combined DWA algorithm with reinforcement learning, added new evaluation function terms to expand the DWA evaluation function to address the defect that too few factors were taken into account, and then learned the parameters of DWA adaptively through Q-learning, so that the agent could adapt to different location environments. DWA performs better than other local path planning algorithms due to its low computation and good stability, and is widely used in games, mobile robot navigation and other fields. The biggest advantage of this algorithm is that it takes into account the kinematic constraints of the robot to generate a smooth and round safe collision free path, and its output is the corresponding linear speed and angular speed, which can be used directly as a control instruction [8,7].

Research on Fusion Algorithm

It can be seen from the above literature that the global static path planning algorithm can effectively plan the global optimal path by using the global information, but it cannot avoid the dynamic obstacles. Local dynamic path planning algorithm can plan paths online in real time and avoid dynamic obstacles effectively, but because of the lack of global information, it is easy to fall into the local optimal solution and often cannot reach the target point. For these two Many scholars have combined the two kinds of algorithms and achieved good results in real- time dynamic path planning. In order to plan the global optimal path in dynamic environment, a global dynamic path planning algorithm based on ant colony algorithm and dynamic window method is proposed in this paper. This paper takes the turning point of the global optimal path planned by ant colony algorithm as the subpoint of the dynamic window method, and guides the dynamic window method to carry out real-time dynamic path planning along the global optimal path direction, and finally realizes the robot to effectively avoid dynamic obstacles and plan the global optimal path.

Ant Algorithm

Ant colony algorithm is a heuristic algorithm that simulates ant foraging behavior. It finds the optimal path based on the pheromone trail left by ants when they search for food. Classic ant colony algorithms usually include two processes: pheromone updating and route selection. In the process of pheromone renewal, ants will leave pheromone on the path, and the amount of pheromone is proportional to the quality of the path. During the route selection process, ants will choose the path with higher pheromone concentration for walking.

Introduction to Ant Algorithm

Real ants, in search of a food source, release an ant-specific secretion, often called a pheromone, along their path, which other ants within a certain range can detect and thus influence their future behavior. Ants choose routes with high concentrations of pheromones, and when more ants pass through some routes, they leave higher concentrations of pheromones, which leads to leeches.

The probability of ants choosing this path increases, showing positive feedback of information. Understood as an enhanced learning system, ants can eventually discover the shortest path. At the same time, pheromones are aromatic substances that evaporate, and their strength diminishes over time. Inspired by the fact that the shortest path between Ant nests and food sources can be found during the foraging process of ant colonies, Italian scholar M. Dorigoet al. proposed a new analog evolutionary algorithm called Ant System (AS) in 1991. Here, Figure 1 is used to illustrate the path search principle and mechanism of ant colonies [9].

Suppose there are two paths around the obstacle leading from the ant's Nest to the Food source: Nest-abd-food and Nest-acd- food, with lengths of 4 and 6, respectively. Ants can travel a unit length of distance per unit of time, starting with no pheromones left on any of the roads.

Figure 1: Schematic Diagram of the Ant Algorithm

At t=0, the first group of 20 ants moved from the nest to A, and since there were no pheromones on all roads, they chose either the left (ABD) or the right (ACD) road with equal probability, so 10 ants went left (ABD) and 10 went right (ACD). At the 4th unit time, the ants that walked left (ABD) to the food source will double back, and the ants that walked right (ACD) will reach the middle point of CD. At the fifth unit time, the two groups of ants will meet at point D. At this point, the number of pheromones on BD is the same as on CD, because 10 ants each choose the corresponding path, so five returning ants will choose BD and the other five will choose CD, and the right side (ACD) ants will continue to move towards food. At the eighth unit time, the first five ants will return to the nest, and there will be five ants at the midpoint of AC, five ants at the midpoint of CD, and five ants at point B. At the ninth unit time, the first five ants returned to A and were again faced with the choice of going left or right.

At this point, the number of tracks on AB is 20 and the number on AC is 15, so more ants will choose to go left, thus enhancing the pheromone of the route. As the process continues, the difference in the number of pheromones on the two paths will get bigger and bigger until the vast majority of ants choose the shortest path. This is how ants find the optimal route from the nest to the food source when foraging.

Ant Algorithm Flow

Path planning task, the basic ant colony algorithm in solving the path planning task of surface unmanned vehicle process is as follows:

• Step 1. Initialize the starting position and end point, set parameters such as the total number of iterations of the ant colony algorithm N max, the number of iterations N c, the number of ants m, and the volatilization coefficient of pheromone, etc., and raster the map.

• Step 2. Go through all the ants and start the search process. Take ant k as an example, a tabu table is constructed according to the size of the map to record the positions that ant k has already traveled, and the ant is placed at the starting point to select the next feasible grid point according to the state transition probability formula. The path and path length of the ant are recorded during the ant's movement, until the ant has no next feasible grid point or has reached the end point, and then the search is stopped. Start your search with the next ant k +1.

• Step 3. When all ants complete the search, that is, after the end of a single iteration, the pheromone number value of the path taken by the ants is calculated according to the pheromone calculation formula, and the pheromone update is carried out.

• Step 4. Check whether the number of iterations reaches the upper limit. If the number of iterations does not reach the upper limit, Nc =Nc +1, and go to Step 2.

• Step 5. Output the optimal path saved during the algorithm. The algorithm is complete. The operation flow chart of ant algorithm is shown in Figure 2.

Figure 2: Diagram of the Ant Algorithm

Ant Algorithm Experiment Simulation

The planned path of the ant algorithm simulation experiment is shown in Figure 3.

Figure 3: Ant Algorithm Simulation Diagram

It can be seen from Figure 3 that ants with a shorter path release more pheromone. As time goes on, the accumulated pheromone concentration on the shorter path gradually increases, and the number of ants choosing this path also increases. Finally, the whole ant will concentrate on the best path under the action of positive feedback, and the corresponding solution is the optimal solution to the problem to be optimized.

The Ant Algorithm has Problems

According to the previous simulation, the ant algorithm has the following shortcomings:

• Artificial ants are blind in the initial stage of search. In the initial stage, the pheromone concentration on each path is the same by default, so ants conduct blind random search in the initial stage of the algorithm, resulting in a large number of random paths in the initial stage of the algorithm, which affects the convergence speed of the algorithm.

• The traditional ant colony algorithm adopts eight-direction search, which will limit the Angle of selecting the next path node in the search process of artificial ants to some extent, and finally make the path length obtained by the algorithm exceed the ideal optimal path, and the path Angle is too large, which is not conducive to the actual tracking and movement of unmanned boats, and has higher requirements for the robot motor and other actuator. If the robot completely follows this path, it may cause the failure of the motor and other power equipment; At the same time, in the actual navigation environment, the robot can move at any Angle, that is, the path is a path with any heading Angle.

• In practical application, ant colony algorithm is prone to defects such as low search efficiency, local optimal solution and deadlock. Therefore, the search efficiency and convergence of the algorithm gradually deteriorate, and the probability of ants falling into local extreme value points and deadlock points gradually increases.

DWA Algorithm

The dynamic window method is a local path planning algorithm, which abstracts the obstacles around the robot into a window and finds a feasible path within the window. Common local obstacle avoidance algorithms for mobile robots include artificial potential field method, dynamic window method (DWA), velocity obstacle method, fuzzy control and so on. Among them, dynamic window method is relatively strong in real-time and has certain advantages in computational amount, and is widely used in local path planning of mobile robots [10].

DWA Algorithm Introduction

The idea of DWA algorithm is to collect robot velocity samples through the robot mathematical model, predict and simulate the motion trajectories generated under the sample velocity for a period of time, conduct standard evaluation on these motion trajectories, select a group of optimal trajectories, and the robot moves according to the optimal trajectories. The motion attitude and direction of the robot are determined by the current linear velocity and angular velocity (turning velocity) of the robot.

DWA algorithm mainly includes three steps: velocity sampling, trajectory prediction (calculation), trajectory evaluation. In the velocity vector space Vr, the continuous velocity vector space VR is discretized according to the sampling points of linear velocity and angular velocity, and the discrete sampling points (v,ω) are obtained. For each sampling point, multiple motion trajectories of the robot in the next moment are predicted according to the robot kinematics model, as shown in Figure 4.

Figure 4: DWA Algorithm Schematic Diagram

DWA Algorithm Flow

The algorithm steps of dynamic window method are as follows:

• Step 1. Initialize the start position and end position.

• Step 2. Calculate the feasible velocity space, the dynamic window.

• Step 3. Sample the dynamic window obtained in Step 2 and obtain the set of speed pairs according to the set speed resolution.

• Step 4. For the speed pair set obtained above, traverse the robot trajectory corresponding to the speed pair according to the set simulation cycle time.

• Step 5. After considering the position of the target point, select the current optimal trajectory and the corresponding speed pair based on the evaluation function.

• Step 6. The robot uses the optimal speed pair in Step 5 to move.

• Step 7. Determine whether the robot has reached the target point at this time. If it has reached the target, output the global trajectory and end the algorithm; Otherwise, go to Step 2. The algorithm flow chart is shown in Figure 5 below

Figure 5: Flowchart of DWA Algorithm

DWA Algorithm Emulation

Figure 6: Dwa Algorithm Simulation Diagram

It can be seen from FIG. 6 that after sensing the motion information of dynamic obstacles through sensors, the robot can predict the trajectory of obstacles and determine whether they collide with the robot. For dynamic obstacles that may collide with the robot, the repulsive force of dynamic obstacles on the simulated trajectory can be evaluated through the evaluation function in the DWA cost function. This allows the robot to turn or slowdown in time to avoid dynamic obstacles in the environment.

Here are Problems with DWA Algorithm

The traditional dynamic window method does not consider the size of the mobile robot itself, and its size will affect the planning effect of the dynamic window method in practical application. At the same time, the traditional dynamic window method only considers the local optimal trajectory when guiding mobile robots such as unmanned boats to move, but there may be many areas in the map that lead to robot deadlock, such as U-shaped areas, which may lead to local minimum problem, because the overall shape of the map is not taken into account. The robot moves only according to the optimal trajectory of the current moment; In addition, in the traditional dynamic window method, when the distance between the robot and the target point is small, the Angle evaluation term in the evaluation function may change sharply, and the original evaluation function will prompt the robot to increase its angular velocity to narrow the Angle gap. Its disadvantage is that the robot will shock when approaching the target, and the robot may not reach the target point at all when the situation is not ideal.

Multi-Robot Fusion Algorithm

In order to solve the path planning problem of multiple dynamic obstacles, a path planning algorithm based on ant colony algorithm and dynamic window method is proposed in this paper. The algorithm regards ants as robots and pheromones as state information about the robot's surroundings, and controls the robot's actions by adjusting the pheromone concentration and window size.

Advantages of Fusion Algorithm

In the current research project tasks related to robot path planning, firstly, the optimal path is obtained offline according to the global path planning algorithm based on the known static environment information, that is, the global path planning has been completed before the mobile robot executes the actual task, but the disadvantage is that such planning cannot cope with the dynamic obstacles encountered during the robot operation. The purpose of local path planning is to enable the mobile robot to cope with dynamic obstacles in the process of moving so as to safely avoid obstacles. The disadvantage of such planning is that it does not take into account the global map, but only considers partial incomplete environmental information within a certain range, which may fall into local optimization, resulting in greater blindness and randomness of the generated path. They tend to be poor in length or other aspects.

Fusion Algorithm Flow

• Initialize pheromones: Abstract the environment around the robot into a grid, and initialize each grid to a pheromone value.

• Ant colony algorithm process: Ants will move from the current grid to another surrounding grid with a certain probability, and leave pheromones in the process of moving. The concentration of pheromones depends on the quality of the path. The path the ants choose is influenced by the pheromone concentration and the heuristic function.

• Dynamic window method process: According to the speed and direction of the robot, determine the size of the window around the robot. The grid in the window is regarded as a feasible path and the best path is selected.

• Update the pheromone: Update the pheromone concentration according to the path taken by the robot, so that more pheromones accumulate in areas with higher path quality.

Figure 7: Fusion Algorithm Flow Chart

Fusion Algorithm Simulation

Fusion Experiment Without Obstructions1

In order to verify the effectiveness of the proposed path planning algorithm, an experiment is carried out. The initial target path planning test of the robot was carried out in the environment without additional obstacles, and the test results are shown in Figure 8.

Figure 8: Plan the Path Diagram Globally

Figure 9: Global Planning Path Convergence Diagram

Figure 10: Local Planning Path Obstacle Avoidance Figure 1

As can be seen from FIG. 8 and FIG. 9, when the robot's environment is known and there are no additional dynamic unknown obstacles, the robot runs global path planning, and the path convergence data is shown in FIG. 9.

Fusion Experiment Dynamic Obstacle 2

This experiment is an extended version of experiment 1, the main purpose of which is to verify the collision avoidance effect of fusion algorithm on multi-target dynamic obstacles. Dynamic obstacles are added to the aforementioned robot path environment. The simulation test of robot path planning under multi-target dynamic obstacles environment is shown in Figure 10.

Figure 11: Local Planning Path Obstacle Avoidance Figure 2

Figure 12: Local Planning Route End Point Diagram

Figure 13: Fusion Planning Path Trajectory Diagram

Fusion Experiment Mixed Environment Obstacle 3

This experiment is an extended version of experiment 2, the main purpose of which is to verify the collision avoidance effect of fusion algorithm on multi-target dynamic obstacles and unknown static obstacles. Dynamic and static unknown obstacles are added to the aforementioned robot path environment. The simulation test of robot path planning under multi-target dynamic and static obstacles environment is shown in Figure 14.

Figure 14: Mixed Obstacle Environment Plan

Figure 15: Local Planning Path Obstacle Avoidance Map

Figure 16: Local Planning Terminal Route Planning Diagram

Figure 17: Fusion Algorithm Planning Path Trajectory Diagram

As can be seen from FIG. 14 and 15, when there are unknown dynamic and static obstacles in the environment of the robot, when the robot approaches the dynamic obstacles, the robot takes timely obstacle avoidance measures and makes certain adjustments to its path. When it encounters the tunnel formed by the unknown static obstacles, it also successfully completes the task of safe collision avoidance. This experiment successfully demonstrates the performance of the fusion algorithm.

Fusion Algorithm Innovation Points

In this paper, the global path planning algorithm and local path planning algorithm are integrated, and simulation experiments are carried out in different environments. Simulation experiments verify the feasibility of the algorithm. The algorithm can make good use of the global optimal path and use the improved DW algorithm to avoid collision with unknown dynamic obstacles. Only by combining the above two path planning can the robot safely and efficiently reach the target point on demand.

Conclusion

Path planning algorithm is an important core technology of robot motion research, and reasonable path planning algorithm is of great significance to improve the economy and safety of robot operation. This paper proposes a path planning algorithm based on ant colony algorithm and dynamic window method. In this paper, the proposed fusion algorithm is simulated for path planning under different environments with multiple dynamic obstacles. The test results show that the fusion algorithm can deal with path planning of multiple dynamic obstacles, and the proposed algorithm has a good path planning effect. It has higher robustness and better adaptability. In the future, we can further explore the application of the algorithm proposed in this paper in the field of robots to promote the autonomous action and intelligent development of robots.

Acknowledgements

This research is supported by Sanya University Virtual Faculty Pilot Construction Project (SYJZXN202303)

Author Contributions

The authors have worked together to complete this research. All authors contributed to the study’s conception and design. Sanli Fu and Hengyi Huang performed research, analyzed the data and were involved in writing the manuscript.Hengyi Huang and Sanli Fu collected, analysed, and interpreted the data from differ- entresearch articles to formulate a summary and to create a roadmap for future researchers.

Data Availability

The data presented in this study are available on request from the corresponding author. The datasets used and/or anal- ysed during the current study are available from the corresponding author on reasonable request.

Declarations

The author(s) declared no potential conicts of interest with respect to the research, authorship, and/or publication of this article.

Ethical Approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Consent to Participate

Not applicable. Consent for Publication We, the authors give consent for the publication of identifiable details, which can include photographs or details within the text (“Material”) to be published in the above Journal Therefore, anyone can read the material published in the Journal.

Conflicts of Interest

The authors declare no conflict of interest. Institutional Review Board Statement The study in the paper did not involve humans or animals. scope includes intelligent robots, machine learning, and path planning.

Publisher’s Note Springer Nature remains neutral with regard to juris- dictional claims in published maps and institutional affiliations.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Hengyi Huang, lecturer, teacher at the School of New Energy and Intelligent Connected Vehicles, Sanya University. Received a master's degree from Hubei University in 2014. His research scope includes machine learning and path planning.

Sanli Fu, lecturer, teacher at the School of New Energy and Intelligent Connected Vehicles, Sanya University. Received a master's degree from Hubei University in 2014. Her research scope includes machine learning and path planning.

References

1. Liu, Y., & Bucknall, R. (2015). Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment. Ocean engineering, 97, 126-144.
2. Huang Yan, Li Yan, Yu Jiancheng, et al. Current Situation and Development Trend of AUV Intelligence [J]. Robot, 2019,42(2):215-231. (in Chinese)
3. Colorni, A., Dorigo, M., & Maniezzo, V. (1991, December). Distributed optimization by ant colonies. In Proceedings of the first European conference on artificial life (Vol. 142, pp. 134-142).
4. Mohan, B. C., & Baskaran, R. (2012). A survey: Ant Colony Optimization based recent research and implementation on several engineering domain. Expert Systems with Applications, 39(4), 4618-4627.
5. Deneubourg, J. L., Aron, S., Goss, S., & Pasteels, J. M. (1990). The self-organizing exploratory pattern of the argentine ant. Journal of insect behavior, 3, 159-168.
6. Fox, D., Burgard, W., & Thrun, S. (1997). The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine, 4(1), 23-33.
7. Seder, M., Baotic, M., & Petrovic, I. (2016). Receding horizon control for convergent navigation of a differential drive mobile robot. IEEE transactions on control systems technology, 25(2), 653-660.
8. Chang, L., Shan, L., Jiang, C., & Dai, Y. (2021). Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment. Autonomous robots, 45, 51-76.
9. Dorigo, M. (1991). Positive feedback as a search strategy.Technical report, 91-16.
10. Wang Yongxiong, Tian Yongyong, Li Xuan, Li Lianghua. Adaptive Dynamic Window Method for Crossing Dense Obstacles [J]. Control and Decision,2019,34(05):927-936.