Abstract: As a common algorithm in mobile robot path planning, grid method has the characteristics of less information and simple structure, but the traditional grid method usually affects the effectiveness of the algorithm because of its excessive grid. In order to solve this problem, this paper proposes an improved grid method for feature points extraction. This method uses the idea of feature extraction to extract the vertices of obstacle grid as feature points, and carries out path planning among these feature points. This method simplifies the planning scope of the algorithm. The new grid method is applied to different kinds of path planning algorithms and compared with the traditional grid method. The results show that this modeling method can solve the local optimization problem of artificial potential field method and make the planned path safer; reduce the number of grid search grid of A* algorithm, make A* algorithm search more purposeful, and improve the efficiency of A* algorithm search; at the same time, the ant colony algorithm does not search path by grid, reducing the calculation times of transition probability and speeding up the algorithm iteration speed.

Key words: feature points extraction, path planning, grid modeling method, A* algorithm, artificial potential field method, ant colony algorithm

摘要： 栅格法作为一种在移动机器人路径规划中的常用算法，其具有信息量少、结构简单的特点，但传统栅格法通常由于其栅格过多而影响算法的有效性。针对这一问题，提出了一种特征点提取的改进栅格法，该方法利用特征提取的思想将障碍物栅格的顶点作为特征点提取出来，在这些特征点间进行路径规划，该方法简化了算法的规划范围。将新的栅格法应用于不同种类的路径规划算法中，并与传统栅格法建模进行比较。结果表明，利用该建模方法解决了人工势场法的局部最优问题，使其规划出的路径更加安全；减少了A*算法搜索栅格的数量，使A*算法搜索更有目的性，进而提高了A*算法搜索的效率；同时使蚁群算法搜索路径时不再逐格进行，减少了转移概率的计算次数，加快了其迭代速度。

关键词: 特征点提取, 路径规划, 栅格法建模, A*算法, 人工势场法, 蚁群算法