Path Planning based Quadtree Representation for Mobile Robot Using Hybrid-Simulated Annealing and Ant Colony Optimization Algorithm

摘要

In this paper, a new path planning approach combining framed-quadtree representation with hybrid-simulated annealing (SA) and ant colony optimization (ACO) algorithm called SAACO is presented to improve the efficiency of path planning. The utilization of framed-quadtree representation is for improving the decomposed efficiency of the environment and maintaining the representation capability of maps. Simulated annealing and ant colony optimization were applied for robot path planning problem respectively and there have been plenty of accomplishments in recent year. Lots forms of SA depend on random starting points and how to efficiently offer better initial estimates of solution sets automatically is still a research hot point. We use ACO to supply a good initial solution for SA runs. According to the theoretical analysis and results obtained from simulation experiment, the presented SAACO algorithm can solve successfully the mobile robot path planning problem, which leads robot to seek the specific destination in the free-collision path and increases the speed of the robot navigation. Some excellent properties of this method have also been proved that is robustness, self-adaptation.