特征点提取下的AGV栅格法建模与分析

doi:10.3778/j.issn.1002-8331.2009-0483

摘要/Abstract

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

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

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

赵江, 孟晨阳, 王晓博, 郝崇清, 李冉, 刘慧贤, 王昭雷. 特征点提取下的AGV栅格法建模与分析[J]. 计算机工程与应用, 2022, 58(8): 156-167.

ZHAO Jiang, MENG Chenyang, WANG Xiaobo, HAO Chongqing, LI Ran, LIU Huixian, WANG Zhaolei. Modeling and Analysis of AGV Grid Method Based on Feature Points Extraction[J]. Computer Engineering and Applications, 2022, 58(8): 156-167.

参考文献

[1] LV M，GAO T，ZHANG N.Research of AGV scheduling and path planning of automatic transport system[J].International Journal of Control and Automation，2016，9（4）：1-10.
[2] 杜隆胤.基于混沌遗传的智能吸尘器避障研究[J].计算机测量与控制，2013，21（3）：762-765.
DU L Y.Research on obstacle avoidance of intelligent vacuum cleaner based on chaos genetic algorithm[J].Computer Measurement and Control，2013，21（3）：762-765.
[3] 郜园园，阮晓钢，宋洪军，等.一种基于混合学习策略的移动机器人路径规划方法[J].控制与决策，2012，27（12）：1822-1827.
HAO Y Y，RUAN X G，SONG H J，et al.A path planning method for mobile robot based on hybrid learning strategy[J].Control and Decision Making，2012，27（12）：1822-1827.
[4] HAN J，SEO Y.Mobile robot path planning with surrounding point set and path improvement[J].Applied Soft Computing，2017，57：35-47.
[5] 郑晓霞，赵青杉.基于ACO的彩色图像边缘检测[J].现代计算机，2016（35）：58-61.
ZHENG X X，ZHAO Q S.Color image edge detection based on ant colony optimization algorithm[J].Modern Computer，2016（35）：58-61.
[6] 张松灿，普杰信，司彦娜，等.基于种群相似度的自适应改进蚁群算法及应用[J].计算机工程与应用，2021，57（8）：70-77.
ZHANG S C，PU J X，SI Y N，et al.Adaptive improved ant colony algorithm based on population similarity and its application[J].Computer Engineering and Applications，2021，57（8）：70-77.
[7] NING J，ZHANG Q，ZHANG C，et al.A best-path-updating information-guided ant colony optimization algorithm[J].Information Sciences，2018，433/434：142-162.
[8] FU B，CHEN L，ZHOU Y，et al.An improved A* algorithm for the industrial robot path planning with high success rate and short length[J].Robotics & Autonomous Systems，2018，106：26-37.
[9] HU Hongyu，ZHANG Chi，SHENG Yuhuan，et al.An improved artificial potential field model considering vehicle velocity for autonomous driving[J].IFAC-PapersOnLine，2018，51（31）：863-867.
[10] MOHAJER B，KIANI K，SAMIEI E，et al.A new online random papers optimization algorithm for mobile robot path planning in dynamic environments[J].Mathematical Problems in Engineering，2013：491346.
[11] ZHENG H，YUN L，HAO W，et al.Ground-based experiment of capturing space debris based on artificial potential field[J].Acta Astronautica，2018，152：235-241.
[12] LEE J.Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J].International Journal of Control Automation & Systems，2017，15（5）：1-16.
[13] ZHANG W，GONG X，HAN G，et al.An improved ant colony algorithm for path planning in one scenic area with many spots[J].IEEE Access，2017，5：13260-13269.
[14] LEE J，KIM D W.An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph[J].Information Sciences，2016，332：1-18.
[15] SAIDI-MEHRABAD M，DEHNAVI-ARANI S，EVAZABADIAN F，et al.An Ant Colony Algorithm（ACA） for solving the new integrated model of job shop scheduling and conflict-free routing of AGVs[J].Computers & Industrial Engineering，2015，86：2-13.
[16] YU X，CHEN W N，GU T，et al.ACO-A*：ant colony optimization plus A* for 3D traveling in environments with dense obstacles[J].IEEE Transactions on Evolutionary Computation，2018，23（4）：617-631.
[17] SONG R，LIU Y，BUCKNALL R.Smoothed A* algorithm for practical unmanned surface vehicle path planning[J].Applied Ocean Research，2019，83：9-20.
[18] SUDHAKARA P，GANAPATHY V，PRIYADHARSHINI B，et al.Obstacle avoidance and navigation planning of a wheeled mobile robot using amended artificial potential field method[J].Procedia Computer Science，2018，133：998-1004.
[19] OROZCO-ROSAS U，MONTIEL O，SEPúLVEDA R.Mobile robot path planning using membrane evolutionary artificial potential field[J].Applied Soft Computing Journal，2019，77：236-251.
[20] ZHOU Z，WANG J，ZHU Z，et al.Tangent navigated robot path planning strategy using particle swarm optimized artificial potential field[J].Optik-International Journal for Light and Electron Optics，2018，158：639-651.
[21] 卜新苹，苏虎，邹伟.基于非均匀环境建模与三阶Bezier曲线的平滑路径规划[J].自动化学报，2017，43（5）：710-724.
BU X P，SU H，ZOU W.Smooth path planning based on non-uniform modeling and cubic Bezier curves[J].Acta Automatica Sinica，2017，43（5）：710-724.
[22] HAN J.An efficient approach to 3D path planning[J].Information Sciences，2019，478：318-330.