J Shanghai Jiaotong Univ Sci ›› 2023, Vol. 28 ›› Issue (1): 86-99.doi: 10.1007/s12204-023-2572-4

Previous Articles     Next Articles

Ant Colony Algorithm Path Planning Based on Grid Feature Point Extraction

基于栅格图特征点提取下的蚁群算法路径规划

LI Erchao∗ (李二超), QI Kuankuan (齐款款)   

  1. (College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China)
  2. (兰州理工大学 电气工程与信息工程学院,兰州730050)
  • Received:2021-12-30 Online:2023-01-28 Published:2023-02-10

Abstract: Aimed at the problems of a traditional ant colony algorithm, such as the path search direction and field of view, an inability to find the shortest path, a propensity toward deadlock and an unsmooth path, an ant colony algorithm for use in a new environment is proposed. First, the feature points of an obstacle are extracted to preprocess the grid map environment, which can avoid entering a trap and solve the deadlock problem. Second, these feature points are used as pathfinding access nodes to reduce the node access, with more moving directions to be selected, and the locations of the feature points to be selected determine the range of the pathfinding field of view. Then, based on the feature points, an unequal distribution of pheromones and a two-way parallel path search are used to improve the construction efficiency of the solution, an improved heuristic function is used to enhance the guiding role of the path search, and the pheromone volatilization coefficient is dynamically adjusted to avoid a premature convergence of the algorithm. Third, a Bezier curve is used to smooth the shortest path obtained. Finally, using grid maps with a different complexity and different scales, a simulation comparing the results of the proposed algorithm with those of traditional and other improved ant colony algorithms verifies its feasibility and superiority.

Key words: ant colony algorithm, mobile robot, path planning, feature points, Bezier curve, grid map

摘要: 针对传统蚁群算法路径搜索方向和视野范围、无法找到最短路径、容易发生死锁和路径不平滑等问题,提出一种新环境下的蚁群算法。首先,提取障碍物特征点对栅格地图环境进行预处理,能够避免进入陷阱,从而解决死锁问题;其次,以这些特征点为寻路访问节点,减少节点的访问,待选移动的方向更多,待选特征点的位置决定寻路视野范围;然后,以特征点为基础,采用信息素不平等分布和双向并行路径搜索,提高解的构造效率,采用改进启发函数,增强路径搜索的引导作用,动态调整信息素挥发系数避免算法陷入早熟;接着,采用贝塞尔曲线平滑路径,得到的路径平滑且最短;最后,在不同复杂程度和不同尺度的栅格地图中,与传统蚁群算法和其他改进蚁群算法进行仿真对比,验证了本文算法的可行性和优越性。

关键词: 蚁群算法,移动机器人,路径规划,特征点,贝塞尔曲线,栅格地图

CLC Number: