一种基于改进蚁群算法的叉车路径规划方法及系统.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113985888A(43)申请公布日2022.01.28(21)申请号202111315179.6(22)申请日2021.11.08(71)申请人合肥工业大学地址230000安徽省合肥市包河区屯溪路193号(72)发明人肖本贤刘子骏(74)专利代理机构合肥市浩智运专利代理事务所(普通合伙)34124代理人郑浩(51)Int.Cl.G05D1/02(2020.01)权利要求书3页说明书8页附图2页(54)发明名称一种基于改进蚁群算法的叉车路径规划方法及系统(57)摘要一种基于改进蚁群算法的叉车路径规划方法及系统，属于AGV路径规划技术领域，解决如何采用栅格处理法以及首尾对向搜索策略，提高路径规划的准确度以及传统蚁群算法的搜索精度、效率的问题；利用栅格法模糊处理障碍物边界信息，定义视野范围栅格，障碍栅格，定义栅格部落密度中心，部落密度函数，栅格样本部落密度集，定义疏密度函数来量化描述地图复杂度；采用的新颖的栅格处理方法和算法策略提高了路径规划准确度；采用首尾对向搜索策略，考虑初始点、当前节点、下一节点、目标点和终点的关系来改进设计启发函数，考虑初始点和终点的位置改进信息素挥发系数，与传统蚁群算法相比显著减小了机器人的移动时间，提高了搜索精度和搜索效率。CN113985888ACN113985888A权利要求书1/3页1.一种基于改进蚁群算法的叉车路径规划方法，其特征在于，包括以下步骤：S1、采用栅格法将叉车的工作环境划分为多个单元栅格，模糊处理障碍物边界信息，从而建立叉车在工作环境中的栅格模型；S2、将障碍物占据整个单元栅格的定义为障碍栅格，将障碍物部分占据单元栅格的进行柔性模糊膨化处理，处理后将其视为障碍栅格；S3、将障碍栅格部落密度函数的极大值定义为障碍栅格部落密度中心，将障碍栅格部落密度中心所对应的障碍栅格部落中的样本从障碍栅格位置集合D中删除，重复上述删除操作直到集合D为空集，得到在地图模型中的k个障碍栅格部落密度中心集合A＝{A1，A2，A3...Ak}；S4、根据集合A＝{A1，A2，A3...Ak}设定k个栅格部落P＝{P1,P2,P3,...,Pr,...，Pk}，定义疏密度函数，更新部落密度中心；S5、初始化两组蚁群E、F，设整个蚁群蚂蚁的数量为m对蚂蚁，ρ0为初始信息素挥发系数，信息素浓度H和最大迭代次数Ymax，设定的迭代次数将迭代次数置为0，对两组蚁群进行配对，计算每只蚂蚁选择下一节点的概率；S6、根据启发函数，采用首尾对向搜索策略，达到搜索结束条件时，计算同对中两只蚂蚁的路径长度LE0和LF0，L＝LE0+LF0，为本次可行的首尾对象搜索路径最优解；当所有的m对蚂蚁全部搜索完毕，更新全局路径的信息素；判断当前迭代次数Y是否达到最大迭代次数，是则结束算法并输出最优路径，否则迭代次数Y＝Y+1并返回步骤S5。2.根据权利要求1所述的基于改进蚁群算法的叉车路径规划方法，其特征在于，步骤S3中所述的障碍栅格部落密度函数的公式如下：式中，r为部落密度圆的半径为集合D平均样本距离，若障碍栅格xi与xj间的欧式距离小于部落密度圆半径，则判定样本点xj存在于该样本圆内，记为1，否则记为0。3.根据权利要求2所述的基于改进蚁群算法的叉车路径规划方法，其特征在于，所述的集合D平均样本距离的公式为：其中，d(xi，xj)为每两个栅格样本xi，xj之间的欧式距离，其中i，j＝1，2，3，4，...，N。4.根据权利要求3所述的基于改进蚁群算法的叉车路径规划方法，其特征在于，步骤S4中所述的疏密度函数的公式为：其中，Mr为栅格部落Pr中栅格总数，Nr为栅格部落Pr中样本点数；疏密度函数越小，说明节点在其所属栅格部落的紧密度越小，即障碍栅格密集度小，越稀疏，即该部落连续为0的栅格越多，拐点越少，叉车更易通过。5.根据权利要求4所述的基于改进蚁群算法的叉车路径规划方法，其特征在于，步骤S5中所述的计算每只蚂蚁选择下一节点的概率的公式为：2CN113985888A权利要求书2/3页式中，ηij(t)为启发函数，反映了从节点i运动到节点j的可能性；allow为蚂蚁n未访问的节点，α为信息素浓度因子，α值越高，则信息素浓度作用性越强；β为启发函数权值因子，β值越高，则启发函数作用性越强，蚂蚁n运动到距离短的节点可能性越高，栅格部落疏密度R反映了路径上经过节点复杂度，R值越小，部落越稀疏，蚂蚁n从i节点运动到j节点概率越大。6.根据权利要求5所述的基于改进蚁群算法的叉车路径规划方法，其特征在于，步骤S6中所述的启发函数的公式为：其中，dij是当前节点i到下一节点j的距离，djT是下一节点j到目标节点T的距离，dSi为初始点S到当前节点i的距离，dSG为初始点S到终