Improved Ant Colony Algorithm And Its Application

The Path Planning for mobile robots is one of the core contents of the field of robotics research with complex, restrictive and nonlinear characteristics. However, traditional methods of path planning all have their own drawbacks respectively. Especially, when the obstacle number increases or the terrain obstacle tend to complex, the complexity of path planning algorithm will increase greatly. The ant colony algorithm(ACA) is a new bionics optimization algorithm developed in the past decade; it shows excellent performance and great potential for development when solving many complex problems. Inspiration by ant colony algorithm, this thesis mainly studies global path planning for mobile robots and vehicle routing and scheduling problems based on improved ACA in static environment. What I have done is described as follows:1. The fundamental principles and work flow is analyzed and the resolution of the ant algorithm are also concluded by using the application of the ant algorithm and the improved ant algorithm for the resolution of the travel problem and the comparison and analysis of the algorithm.2. Establish an environment modeling to provide an abstract space of physical space, on which ACO(Ant Colony Optimization) can search for path.3. Firstly, to increase the convergence speed and avoid the local optimum, alpha(pheromone heuristic factor), beta(expected heuristic factor) values modified adaptively is introduced to reach a balanced or approximate balance in the process of ant colony search path. This method expands the search space; Secondly, to introduce the "preference power" to the distance heuristic factor "ij(t) Combined with vehicle transportation scheduling problems, and which will improve the efficiency and practicality of the algorithm in the vehicle scheduling; Finally, to avoid the ant colony algorithm falling into concave obstacles and deadlock, a update rule of general pheromone is introduce to the improved method and to increase the research efficiency; By adopting the above strategy, which makes the algorithm jump from the local optimum, thus in a relatively short time to find the global optimal solution, and it improve the whole performance of the basic ant colony algorithm.4. The improved ant colony algorithm is applied to the path planning for mobile robot firstly, Using Matlab-tool for numerical value analysis and experiment, therefore, the results of simulation experiments demonstrate that using this algorithm can be quickly mapped out the optimal path, and the ants could get rid of concave obstacle efficiently and safely. Then the optimized operators are introduced to remove redundant nodes in the path and make it become a practical path; Secondly, this paper applies the improved ant colony algorithm to the vehicle routing and scheduling problems, and to the vehicle routing and scheduling problems, and which is simulated based on the Matlab-tool, through the simulation of different sizes VRSP, it can see that the improved ant colony algorithm is viable and efficient, and the results are effective; Finally, to make a comprehensive summary and outlook based on the work of this paper.