基于改进蚁群算法的移动机器人路径规划方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114964261A(43)申请公布日2022.08.30(21)申请号202210563301.X(22)申请日2022.05.20(71)申请人江南大学地址214122江苏省无锡市滨湖区蠡湖大道1800号(72)发明人冯飞周德强梁彪盛卫锋左文娟赵文博(74)专利代理机构哈尔滨市阳光惠远知识产权代理有限公司23211专利代理师吕永芳(51)Int.Cl.G01C21/20(2006.01)G01C21/34(2006.01)权利要求书3页说明书8页附图3页(54)发明名称基于改进蚁群算法的移动机器人路径规划方法(57)摘要本发明公开了基于改进蚁群算法的移动机器人路径规划方法，属于移动机器人控制领域。本发明首先通过K‑medoids算法对地图障碍物聚类分析，差异化初始信息素浓度，提升了前期收敛速度；然后对蚁群算法进行改进，通过引进自适应启发函数，根据待访问节点位置的不同对启发因子适当放大，以加快向目标点搜索的速度；设定双向搜索机制，将寻找目标点问题转化为两只蚂蚁相遇问题，提高了算法效率，从而提高了路径规划的速度。仿真数据说明本发明相比于现有的路径规划方案，机器人的最短路径长度缩短了5％，过程拐弯次数减少30％，收敛代数减少46.2％，因此本发明可更快速寻找到机器人的最短路径，且路径质量更优。CN114964261ACN114964261A权利要求书1/3页1.一种基于改进蚁群算法的移动机器人路径规划方法，其特征在于，所述方法包括：步骤1：将移动机器人的工作环境视作二维平面坐标系，利用栅格法将所述工作环境构建为静态栅格地图；步骤2：利用聚类算法对所述静态栅格地图做预处理，地图被划分为若干个聚类分区，定义疏通值和拥堵值来量化区域环境复杂度，使信息素浓度差异化；步骤3：初始化各项参数，包括：种群数量M、信息素权重α、启发函数权重β、信息素挥发系数ρ，初始化禁忌表Tabu，并设置最大迭代次数K；步骤4：在所述移动机器人工作环境的起始点S和终点E分别放置M只蚂蚁，从第m＝1对蚂蚁开始，检查该对蚂蚁的行走路径是否存在交集，若不存在，则根据节点转移概率公式转移到下一节点，并将先前节点加入到各自的禁忌表中；若存在，则跳转到步骤5；步骤5：根据该对蚂蚁的行走路径得到一个路径解，并计算路径长度；判断M对蚂蚁寻路是否已全部完成，若m＝M，则找出当前迭代的最优解和最差解；否则m＝m+1，转到步骤4，下一对蚂蚁重新开始寻路；步骤6：每次迭代结束时，更新节点信息素浓度，迭代次数k＝k+1；当k＝K时，所有迭代完成，输出全局最优路径解和对应的最短路径长度，作为所述移动机器人的最优路径。2.根据权利要求1所述的方法，其特征在于，所述步骤4中的节点转移概率公式为：其中，表示节点转移概率；τab(t)为节点a和b间的信息素浓度；ηab(t)为节点a到节点b的启发函数；α、β分别表征信息素浓度和启发函数的权重；τas(t)为节点a到s间的信息素浓度，ηas(t)为节点b到s间的启发函数，allow表示蚂蚁下一步允许访问的节点集合。3.根据权利要求2所述的方法，其特征在于，所述启发函数ηab(t)为：其中，Hab为节点a到节点b的曼哈顿距离，HbE为节点b到终点E的曼哈顿距离，ax、ay为节点a的横纵坐标，bx和by为节点b的横纵坐标。4.根据权利要求3所述的方法，其特征在于，所述步骤4中节点转移策略还包括标记回退的策略，所述标记回退的策略为：蚂蚁走到B节点时，下一步允许访问的节点集合为空，陷入死锁，此时将B节点标记为障碍物，并回退到A节点，避免后续蚂蚁再次进入陷阱，节约寻路资源。2CN114964261A权利要求书2/3页5.根据权利要求4所述的方法，其特征在于，所述更新节点信息素浓度的方法包括：引入奖惩策略和引入拐点评价函数；所述引入奖惩策略为：当每次迭代结束时，只保留找到目标点的路径解，对超过伪全局最优解的路径节点信息素予以提高，对当前所有路径解中的最差解予以降低信息素浓度，所述节点信息素浓度公式为：其中，Q为信息素初始值，iter_best为此次迭代中的最优解，iter_worst为此次迭代中最差解，best为伪全局最优解；t代表第t时刻，即第t代蚂蚁，ρ是信息素挥发系数；所述拐点评价函数，根据每次转弯角度的不同定义相应的扩展路径长度，公式如下：其中，θ为转弯角度，f(θ)代表扩展路径长度。6.根据权利要求1所述的方法，其特征在于，所述步骤2利用K‑medoids算法对地图障碍物聚类分析，依据各聚类中心点划定地图分区，并以疏通值和拥堵值指标表示区域环境复杂度；确定簇中心点的相异度总和公式如下：其中，TCih代表中心点Oi被非中心点Oh替代后的总代价，Cjih代表中心点Oi被非中心点Oh替代后非中