【免费】基于改进遗传算法的AGV动态路径规划及其实现_刘二辉1

需积分: 0 118 浏览量 2022-08-04 17:19:44 上传评论收藏 1.72MB PDF 举报

资源详情

资源评论

资源推荐

基于改进遗传算法的 AGV 动态路径规划及其实现



刘二辉

姚锡凡

蓝宏宇

金鸿

（1. 华南理工大学机械与汽车工程学院，广东广州 510640； 2. 华南农业大学工程学院，广东

广州 510642）

摘要：提供一种改进遗传算法的 AGV 动态路径规划算法,其中，针对传统变异算子缺少启发式

规则导致变异产生优质解的概率较低和算法早熟的缺陷，基于相连的路径片段组成的三角形建立使

路径缩短的启发式变异规则提出路径微调算法；为了提高路径的光滑程度便于 AGV 行驶，提出路径

光滑处理算法；为了增加改进遗传算法的局部寻优能力，对每一代的最优解进行模拟退火操作；并

且基于 Matlab GUI 开发工具开发出 AGV 动态路径规划仿真平台，以证明所改进遗传算法求解 AGV

动态路径规划问题的有效性。

关键词：启发式规则；路径微调算法；路径光滑处理算法；动态路径规划

中图分类号：TH16；TP24 文献标识码：A

AGV Dynamic Path Planning Based on Improved Genetic Algorithm and

its Implementation

LIU Erhui, YAO Xifan, LAN Hongyu, JIN Hong

(1. School of Mechanical and Automobile Engineering, South China University of Technology,

Guangdong Guangzhou 510640, China; 2. College of Engineering, South China Agricultural

University,Guangzhou 510642, China)

Abstract: An improved genetic algorithm (IGA) for AGV dynamic path planning is proposed,

in which fine-tuning path algorithm is proposed based on the heuristic rule to shorten path

by the set up of a triangle consisting of connected path segments to aim at the drawbacks

such as low probability of producing high quality solutions and premature resulted from

the lack of heuristic rules in traditional mutation operators, path smoothing algorithm

is proposed to improve the smoothness of the path and facilitate the running of AGV, and

simulated annealing operation is performed for the optimal solution in each generation to

enhance the IGA exploitation performance. An AGV dynamic path planning platform developed

by MATLAB GUI tools so as to verify the proposed IGA for solving AGV dynamic path planning

problems.

Key Words: heuristic rules ; path fine-tuning algorithm; path smoothing algorithm ; dynamic

path planning

0 引言

AGV 作为智能物料运输的主要工具已经在现代生产系统中广泛使用，AGV 的采用带来诸如生

产率提高、节约劳动成本、提高能源利用率和增强安全性等优点

[1, 2]

。路径规划是 AGV 领域的关键

性问题，主要目标是为 AGV 在包含障碍物的空间中规划出一条从起点到目标点的路径，并且保证

收稿日期： 2017-06-16；修订日期：2017-08-17。Received 16 Jun. 2017,accepted 17 Agu. 2017.

基金项目：国家自然科学基金资助项目(51675186，51175187); 广东省科技计划项目(2017A030223002)；广州市南沙

区科技计划项目 (2015CX005) 。 Foundation items: Project supported by the National Natural Science

Foundation ,China(No.51175187); the Science & Technology Program of Guangdong Province,China(No.2017A030223002);

and the Science & Technology Program of Nansha,Guangzhou,China (No.2015CX005).

网络出版时间：2017-10-30 09:25:42

网络出版地址：http://kns.cnki.net/kcms/detail/11.5946.TP.20171030.0925.004.html

AGV 在运动过程中不与障碍物碰撞且以尽可能快的速度到达目标点完成指定任务
[3]
。AGV 的工作空
间的环境地图可以是静态的也可以是动态的，静态环境的路径规划问题对算法性能要求比动态规划
低，对于动态环境的路径规划问题，由于 AGV 工作空间中的障碍物实时运动，AGV 要规划出可靠
地路径必须实时获取环境信息，并对规划好的路径进行快速修改
[4]
，因此本文着重研究 AGV 动态路
径规划算法设计问题。 
AGV 路径规划问题可以建模成约束优化问题，已经有很多学者研究 AGV 路径规划算法的设计
问题，路径规划算法分为传统算法和智能算法，传统算法主要有 A*算法
[5]
、D*算法
[6]
、人工势场算
法
[7]
、单元分解法、RRT
*[8]
等，路径规划是 NP-Hard 型问题，随着环境地图的复杂性和动态性增加，
传统求解算法有求解代价高、容易陷入局部极值和求解效率低等缺陷，为了克服这些缺陷有很多学
者广泛研究各种智能优化算法在 AGV 路径规划领域的应用
[9]
。智能求解算法主要有遗传算法
（Genetic Alcorithm，GA）
[10]
、花授粉算法（Flower Pollination Algorithm，FPA）
[11]
、灰狼优化算法
（Grey Wolf Optimization，GWO）
[12]
、帝国主义竞争算法（Imperialist Competitive Algorithm，ICA）
[13]
、教-学优化算法（Teaching-Learning-Based Optimization，TLBO）
[14]
、粒子群算法（Particle Swarm 
Optimization，PSO）
[15]
等。与传统求解算法相比智能算法求解路径规划问题有更好的鲁棒性
[16]
，GA
有很好的鲁棒性已经广泛应用于诸多组合优化领域，如云制造服务组合优化
[17]
、旅行商问题、AGV
与加工作业的集成调度问题
[18]
等。 
已经有很多学者开展智能算法求解 AGV 动态路径规划问题的研究，文
[19]
基于细菌进化算法
（Bacterial Evolutionary Algorithm，BEA）和人工势场算法（Artificial Potential Field，APF）提出细
菌势场算法（Bacterial Potential Field，BPF），用于求解移动机器人静态和动态路径规划问题，该算
法利用 BEA 优化引力和斥力系数，有效避免了传统 APF 算法容易陷入局部极值的缺点，仿真实验
证明 BPF 算法求解移动机器人静态和动态路径规划问题的有效性，缺点是环境地图以及障碍物运动
形式简单。传统的 GA 求解优化问题时，变异算子是按一定的概率随机生成一个新的基因替换原来
的基因，会导致生成更好解的可能性较低，文
[20]
提出新的变异算子，具体做法是在要变异的基因邻
域确定自由空间中的候选点集，然后从候选点集中随机选择点替换原来的基因进行变异，有助于提
高变异生成优质解的可能性。基于改进变异算子提出改进 GA 并求解移动机器人动态路径规划问题，
证明改进策略的有效性，但变异点选择没有启发信息，导致变异效率低。文
[21]
基于爬山算法提出新
的变异算子，有效避免传统 GA 求解路径规划问题容易陷入局部极值的缺陷；改进可视图算法对环
境地图进行建模，有效提高了规划出的路径的安全性；为了提高 GA 的寻优效率，遗传操作之后采