Research on Improved A* Algorithm and Ant Colony Algorithm of Patrol Robot

摘要

In order to increase the robot's efficiency while patrolling, a method combining A * algorithm and ant colony algorithm was proposed. A * algorithm was used to build feasible and efficient paths among each two patrol points. To shorten the computing time of A * algorithm, a new heuristic function was designed. The experimental findings confirm that the traversed nodes and the computing time were reduced, especially in the environment with fewer obstacles, by using this method. Then, the generated paths were smoothed by testing the visibility between two nodes and removing redundant nodes, which compensated for the increase in path length caused by the redefined heuristic function. Finally, ant colony algorithm was used to search the shortest patrol sequence among various patrol points, and generate the final patrol path.