Research On Improved Ant Colony Algorithms And Applications For Path Planning Problems

Path planning problems have become one of hot research areas in the field ofcombinatorial optimization and operations research. The researches in this area haveimportant significance on theory and practice. Ant colony optimization (ACO) is anovel nature-inspired metaheuristic algorithm based on real ants foraging behavior.The ACO belongs to the class of swarm intelligence algorithm, which obtainedencouraging results for solving of NP-hard combinatorial optimization problems.Because of the advantages of the ACO on solving discrete problems and beingsensitive to path, more and more attentions are paid to solve path planning problemsusing the ACO.In this paper improved ant colony algorithms (ACAs) are proposed to solve thefour path planning problems: traveling salesman problem, multiple agent formationcontrol problem, capacitated vehicle routing problem and agent path planningproblem. The main achievements and contents are listed below.1. An improved ACA is proposed for traveling salesman problems, in which anapproach of local and global dynamic pheromone updating is presented. Byusing the approach of local and global dynamic phenomenon updating, thedistribution of pheromone can be adjusted according to the current route status.The approach of2-opt is only used for some current optimal routes, which canspeed up the convergence of the optimal solution. Simulation resultsdemonstrate the proposed algorithm is efficient.2. Multi-agent formation control problems are researched. A new kind of problemnamed minimum formation distance problem in multi-agents systems is solved.An improved ACA is proposed to solve this kind of problem. In the process ofsearching, the reciprocal of the distance between agent’s current position andtarget position is chosen as the heuristic information. An exchange search approach is used to expand the scope of the search and speed up theconvergence of the optimal solution. Simulation results demonstrate theproposed algorithm is efficient.3. An improved ACA is proposed for capacitated vehicle routing problems. A newinitialization of vehicle’s position with an optimal and random selection is usedto increase the possibility of obtaining the optimal path. In the process ofsearching, the saving path among customers is chosen as the heuristicinformation to make the vehicles be more sensitive to the optimal path. Theapproach of local and global dynamic phenomenon updating is used to adjustthe distribution of phenomenon according to vehicles’ routes. Except themethod of2-opt, insertion and exchange search methods are also used to expandthe scope of the search for the clients on different vehicles’ routes. Thesimulation results demonstrate the proposed algorithm works well andefficiently.4. An ACA using endpoint approximation is proposed for agent path planningproblem under a unknown and static environment. In this algorithm the modelof agent ’s workspace is established with grid method and fold-back iterating isused to search the aims. The most pheromone in a moving direction range and agoal guiding function are chosen as the heuristic information during thesearching process. Meanwhile, two kinds of pheromone are used to guide ants.Furthermore, according to the features of the pheromone strewing in the gridsand ants visiting grids, an endpoint approximation method is proposed to makethe starting point and the end point gradually move towards each other in theiterative process, shortening the distance between the starting point and the endpoint and accelerating the speed of convergence. The simulation resultsdemonstrate that the proposed algorithm has much high efficiency.