Dissertation > Industrial Technology > Automation technology,computer technology > Automation technology and equipment > Robotics > Robot

Improvement of Ant Colony Algorithmand Its Application in Robot Path Planning

Author GuoYu
Tutor LiShiYong
School Harbin Institute of Technology
Course Control Science and Engineering
Keywords ant colony algorithm route construction rule path planning vision
Type Master's thesis
Year 2008
Downloads 316
Quotes 2
Download Dissertation

Ant Colony Algorithm(ACA) is a metaheuristic approach for solvingcombinatorial optimization problems. It was first proposed byDorigo in 1991. Fromthen on, it has been successfully used to solve a series of combinatorial problems,such as: Traveling Salesman Problem, Quadratic Assignment Problem, VehicleRouting Problem, Graph Coloring Problem and so on. Because of the greatperformanceofACA,researchersshowgreatinterestintheresearchandapplicationsonACAnowadays.Based on the basic principle of the first ant algorithm, ant system(AS), thisarticle lays a strong emphasis on advantages and disadvantages of many kinds ofbasic ant colony algorithm (Ant Colony System, Max-Min Ant System, Ant ColonyOptimization). In this paper, a Genetic Mechanism Ant Colony Optimization(GMACO) is proposed, through blending Ant Colony System and GeneticsAlgorithm as well as broadeningthe paths choice rules inACS.Thisarticleanalyzesits feasibility and superiority, and applies it to solve some typical TSP. The resultsshowthatGMACOispreferableinconvergencespeedandavoidingfallingintolocaloptimalresultthanGeneticsAlgorithmAntAlgorithm(GAAA).The paper applies GMACO to solve the robot path planning problem, and thestrategies of ant’s vision from present position to aim position, pheromone updatingrules, paths choice are put forward according to the situation. These improvedstrategies much agree with the real ants’behavior in nature. It uses path length andturn number as performance index. The paper carries on the algorithm simulationusingtheMATLAB languageandcomparesitwithGAAA.Theresultshowsthatthealgorithm can find better paths at higher convergence speed, and the success rate offinding the optimal paths is higher, the performance is better, so it solves pathplanningwell.An improved ant colony algorithm based on several route construction rules isproposedtoplananoptimal collision-freepathformobilerobot incomplicatedstaticenvironment. Furthermore, the strategies of backspace from traps, goal attraction,adjustingparametersadaptivelyandpathoptimizationare appliedto pathplanningof mobile robot.The strategyof backspace from traps and punishment function enablesant jump out of traps successfully, and makes the ant don’t choose this path in nextsearch, so it avoids path-locked situation as well as improves the efficiency ofplanningoptimal path. The simulation results show that the best path can be rapidlyfound.

Related Dissertations
More Dissertations