Path Planning Studies Based On Ant Colony Algorithm

Path planning has been one of the research hotspots in recent years. Path planning of mobile robots is one of the applications of path planning problems. It refers to that in some specified work environment, the mobile robot schemes out an optimal or sub-optimal path from the starting position to the target position according to some performance index (like time, distance and so on). This thesis lays out the research on path planning under the known static environment. Two improved ant colony algorithms are put forward on the basis of research and analysis of the fundamental principles of ant colony algorithm and present improved ant colony algorithm. The main research work includes:1. An ant colony optimization algorithm based on self-adaption threshold (ACOST) was presented on the issue of local optimum of ant colony (ACO)algorithm. ACOST algorithm dynamically interferes the search process of ACO algorithm through adaptive threshold, which guarantees the search scope in early stage and reduces the probability of the appearance of local optimum. At the same time, it regulates the amount of pheromone left by elitist ants, which increases the convergence speed of the algorithm while guarantees the search scope. It was shown from simulation experiments that ACOST algorithm can scheme out a reasonable path within a short period of time. The average number of iterations of ACOST algorithm decreased by 32.9% and the average length of its planned path reduced by 7.69% compared to ACO.2. A quadratic path planning (QACO) algorithm based on sliding window and ant colony algorithm was put forward on the issue of weak planning ability of ACO algorithm in complex environments. Feedback strategy of ant colony algorithm with feedback strategy (ACOFS) has been improved. Feedback times are reduced through the decrease of pheromone along feedback path. In the first time planning, the improved ant colony algorithm was applied to make a global path planning for the grid environment. In the second time planning, the sliding windows slid along the global path. Local path in sliding windows was planned with ant colony algorithm. Then global path could be optimized by local path until target position was contained in the sliding window. It was shown from simulation experiments that the average planning time of QACO algorithm reduced by 26.21% and the average length of path reduced by 47.82% compared to ACO. And those of QACO algorithm reduced by 52.03% and 42.28% respectively compared to ACOFS.ACOST algorithm discussed in this thesis reduces the probability of the appearance of local optimum in planning process and increases the convergence speed. QACO algorithm improves the planning ability in complex environments and effectively reduces planning time as well as the length of planned path. Both the two algorithms have certain practical application value.