A Research on Ant Colony Algorithm for Path Planning Problem
|School||Harbin Engineering University|
|Course||Computer Software and Theory|
|Keywords||path planning ant colony algorithm particle swarm optimizationalgorithm fusion algorithm grid method|
Path planning is the important branch of intelligent transportation,communication networks, robotics and other artificial intelligence research. It isalways a focue topic for researchers all over the world. Exploring and achieving anaccurate and efficient path planning method has become a hot research topic. As anintelligent optimization algorithm developed in the recent years, the ant colonyalgorithm(ACA) has demonstrated excellent performance and development potentialin solving many complex problems should be concerned. In this thesis, it mainlydiscussed path planning problem and achieve based on ACA.Firstly, based on the basic principles of ant colony algorithm, this thesisintroduced three ant colony algorithm models: ant-density system, ant-quantity systemand ant-cycle system. Then against the ant-cycle system used for this thesis, algorithmdescription and implementation of the basic ant colony algorithm have been given indetail. Meanwhile, analyzed and compared the ant colony system, max-min antsystem, ant colony optimization algorithm and some typical ant colony algorithms.Contents mentioned above provided a theoretical basis for follow-up research works.Secondly, grid method was introduced to establish the environment model forpath planning problems. After giving the description and definition of the pathplanning problem, considered the basic ant colony algorithm exists slow convergence,easy to fall into local optimum value and other defects, this thesis proposed theimproved ant colony algorithm based on target heuristic strategy, parameter adaptiveadjustment strategy, wolves allocation strategy and genetic crossover and mutationstrategy. Meanwhile, a large number of simulation experiments on the path planningwhich contains grid figure obstacles environment and TSP two types problems werefinished. The experimental results showed that the improved ant colony algorithm inboth of the convergence and accuracy were superior to the traditional ant colonyalgorithm.Finally, on the basis of the ant colony algorithm, combined with particle swarmoptimization algorithm, this thesis proposed one fusion algorithm (PSO-ACO) which based on ant colony algorithm and particle swarm optimization algorithm. In order toimprove the performance of the fusion algorithm, the thesis proposed the improvedant colony algorithm based on multipath selection strategy, dynamic pheromone localupdating strategy and adjustment factor for pheromone global updating strategy. Theexperimental results on the complex grid figure obstacles environment and largerscale TSP problems showed the proposed algorithm PSO-ACO not only showed goodadaptability in large scale problems, but also showed good efficiency in the accuracyand speed.