一种基于蚁群算法的室内AGV路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113848919A(43)申请公布日2021.12.28(21)申请号202111149575.6(22)申请日2021.09.29(71)申请人河北大学地址071002河北省保定市五四东路180号(72)发明人肖金壮余雪乐周振孙可可(74)专利代理机构石家庄国域专利商标事务所有限公司13112代理人胡素梅(51)Int.Cl.G05D1/02(2020.01)权利要求书3页说明书12页附图11页(54)发明名称一种基于蚁群算法的室内AGV路径规划方法(57)摘要本发明提供了一种基于蚁群算法的室内AGV路径规划方法。本发明通过引用距离函数和方向函数作为启发因子改进启发函数，增加算法的启发性，引导蚂蚁向着较优的方向和位置节点搜索，有效减少在AGV移动过程中可能出现的尖锐转弯，提升路径质量。而且，本发明还通过改进状态转移概率和自适应参数调整策略，在不断迭代的过程中，算法的控制参数不断调整和变化。再有，本发明基于差异化‑分级信息素更新改进信息素更新方法。将改进后的蚁群算法应用到AGV室内路径规划中，可以使AGV快速地搜索得到实际环境中一条起始节点到目标节点的无碰撞的较优路径，从而提升运输效率，减少人工运输成本。CN113848919ACN113848919A权利要求书1/3页1.一种基于蚁群算法的室内AGV路径规划方法，其特征是，包括如下步骤：a、构建栅格地图，为AGV设定好起始节点和目标节点；b、初始化蚁群算法各项参数；蚁群算法各项参数包括：蚂蚁数量m，最大迭代次数NC，信息素重要程度因子α，信息素初始浓度τij(0)，启发函数重要因子最大值β_max和最小值β_min，信息素挥发因子ρ，自适应状态转移概率选择参数q0，信息素强度Q，精英蚂蚁个数ε；c、将蚂蚁放在起始节点上；d、按照改进的自适应伪随机概率选择下一节点，改进的自适应伪随机概率转移规则如下面公式所示：其中，q为0‑1之间的随机值，为传统蚁群算法的轮盘赌随机选择模型，的计算公式如下所示：其中，τij(t)为栅格节点(i，j)间的信息素浓度，ηij(t)为启发函数，allowed为AGV下一待选节点的集合；β为启发函数重要程度影响因子；β的计算公式如下：β＝β_max‑(β_max‑β_min)×(N/NC)其中，N是当前迭代次数；启发函数ηij(t)的计算公式如下：其中，(xe，ye)表示目标节点的坐标，(xj，yj)表示下一节点的坐标；Cij为方向因子，ψ为上一节点与当前节点之间的直线和当前节点与下一节点之间的直线组成的夹角；a和b分别为调整方向和距离的影响程度参数，且a+b＝1；q0的计算公式如下：e、判断当前蚂蚁是否到达目标节点，如果是则执行步骤f，否则执行步骤d；2CN113848919A权利要求书2/3页f、判断是否达到最大蚂蚁数；如果是，则执行步骤g；否则蚂蚁数加1，执行步骤c；g、记录本次迭代过程中一级蚂蚁找到的最优路径长度、二级蚂蚁找到的较优路径长度，以及普通蚂蚁找到的最差路径长度，同时计算出整个蚁群中所有存活蚂蚁找到的路径均值，基于改进差异化‑分级蚂蚁更新策略对信息素进行动态调整；所述一级蚂蚁指当前迭代过程中找到最优路径长度的蚂蚁，所述二级蚂蚁指当前迭代过程中找到较优路径长度的蚂蚁，除一级蚂蚁和二级蚂蚁之外的其他蚂蚁均为普通蚂蚁；所述存活蚂蚁指能从起始节点到达目标节点的蚂蚁；基于改进差异化‑分级蚂蚁更新策略对信息素进行动态调整，具体公式如下：τij(t+1)＝(1‑ρ)τij(t)+ρΔτij+Δτij′‑Δτij″其中，Lk为第k只蚂蚁找到的路径长度，Lb为本次迭代的最优路径长度，Lw为本次迭代的最差路径长度，La为本次迭代的平均值路径长度；Lgb为全局最优路径长度，Lgw为全局最差路径长度；h、判断是否达到了最大迭代次数，如果是则执行步骤i；如果否，则使迭代次数加1，然后执行步骤c；i、在最优路径的基础上，利用三次均匀B样条曲线进行路径平滑，输出最终路径。2.根据权利要求1所述的基于蚁群算法的室内AGV路径规划方法，其特征是，步骤i中，利用三次均匀B样条曲线进行路径平滑，具体计算公式如下：Pt为给定n+1个控制点Pt(i＝0,1,2，……，n)的坐标，Fl，n为B样条基函数；Fl，n的表达式如下：t为自变量。3.根据权利要求2所述的基于蚁群算法的室内AGV路径规划方法，其特征是，n＝3，三次B样条曲线的基函数如下所示：3CN113848919A权利要求书3/3页4.根据权利要求1所述的基于蚁群算法的室内AGV路径规划方法，其特征是，步骤b中，信息素重要程度因子α为1，信息素挥发因子ρ为0.1，信息素强度Q为1。5.根据权利要求1所述的基于蚁群算法的室内AGV路径规划方法