一种基于改进蚁群算法的全局规划路径方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN115560772A(43)申请公布日2023.01.03(21)申请号202211160614.7(22)申请日2022.09.22(71)申请人福建（泉州）哈工大工程技术研究院地址362000福建省泉州市丰泽区软件园9号楼(72)发明人蒋嘉骏李瑞峰霍光磊黄小春吴宇雄(74)专利代理机构泉州市立航专利代理事务所(普通合伙)35236专利代理师林章(51)Int.Cl.G01C21/34(2006.01)权利要求书2页说明书5页附图4页(54)发明名称一种基于改进蚁群算法的全局规划路径方法(57)摘要本发明涉及自主导航技术的全局规划路径方法技术，具体是公开一种基于改进蚁群算法的全局规划路径方法，包括对工作环境地图进行栅格化建模；采用蚁群算法寻找最短路径，首先初始化参数，接着开始进行迭代，搜索路径，添加禁忌表中；当前蚂蚁到达终点时，采用激励惩罚机制对当前蚂蚁所走路径的信息素进行更新；判断当前迭代的蚂蚁是否全部到达终点，若没有返回开始进行迭代，若有则继续进行；每轮迭代结束后采用信息素偏差放大更新当前迭代所有蚂蚁的信息素；判断迭代是否完成，若未完成返回开始进行迭代，若完成继续进行；根据记录的全局最小路径生成路径。该方法能够提高对蚁群算法的收敛速度以及稳定性。CN115560772ACN115560772A权利要求书1/2页1.一种基于改进蚁群算法的全局规划路径方法，其特征在于，全局规划路径方法步骤包括，步骤1、对工作环境地图进行栅格化建模；步骤2、采用蚁群算法寻找最短路径，其包含步骤2.1、初始化参数，初始化参数，迭代次数记为K，蚂蚁数记为m，最大信息素指导参数记为AlphaMax，最小信息素指导参数记为AlphaMin，最大启发函数指导参数记为BetaMax，最小启发函数指导参数记为BetaMin，信息素挥发因子记为ρ，信息素强度系数记为Q，信息素偏差调节因子记为c；步骤2.2、开始进行迭代，搜索路径，将起始点加入禁忌表中，根据轮盘赌算法选择下一节点，将该节点添加至禁忌表中；步骤3、当前蚂蚁到达终点时，采用激励惩罚机制对当前蚂蚁所走路径的信息素进行更新；步骤4、判断当前迭代的蚂蚁是否全部到达终点，若没有返回步骤2.2，若有则继续进行；步骤5、每轮迭代结束后采用信息素偏差放大更新当前迭代所有蚂蚁的信息素；步骤6、判断迭代是否完成，若未完成返回步骤2.2，若完成继续进行；步骤7、根据记录的全局最小路径生成路径。2.如权利要求1所述的一种基于改进蚁群算法的全局规划路径方法，其特征在于，所述步骤1建模方法过程是将环境地图抽象为m×n的栅格环境，每个网格对应一个唯一的网格编号记为i，i与所在栅格坐标的对应关系为其中x表示栅格坐标中x轴坐标值，y表示栅格坐标中y轴坐标值，m表示每一行网格数目，n表示每一列网格数目，mod为求余运算，ceil为向上取整，通过矩阵来生成栅格图，0表示可以通过，1表示有障碍物。3.如权利要求2所述的一种基于改进蚁群算法的全局规划路径方法，其特征在于，所述步骤2.2中轮盘赌算法公式为，其中，为状态转移概率，α为信息素知道因子，β为启发函数知道因子，τij(t)为路径i、j的信息素浓度，ηij(t)为启发函数，在传统蚁群算法中，设蚂蚁总数为m只，设定在t时刻，蚂蚁k从当前i接电移动到下一j节点的可能性由状态转移概率决定，其中，Ljg为节点j到目标节点的距离，Lig为节点i到目标节点的距离，α和β因子在本发明中采用自适应的计算方式计算，计算方法为，2CN115560772A权利要求书2/2页其中Nc为当前迭代数，n是一个常数，当Nc＜n时α和β去最小值，此时有利于增加群算法的全局性，随着迭代，此时的增高α和β不断增大，通过此做法加快算法收敛。4.如权利要求1所述的一种基于改进蚁群算法的全局规划路径方法，其特征在于，所述步骤3中信息素进行更新的更新机制计算公式为，其中，ρ为信息素挥发因子，Q为信息素强度因子，PLm为当前蚂蚁到终点的路径长度，PLbs为当前迭代最短路径长度，PLws为当前迭代最长路径长度，c是常数，k为当前迭代数，K为总迭代次数，这里引入k和K是为了在迭代前期增加解的全局性，防止出现局部极值，在后期加快收敛。5.如权利要求3所述的一种基于改进蚁群算法的全局规划路径方法，其特征在于，所述步骤5中信息素浓度τij(t)计算方式采取信息素浓度偏差放大策略，改进后的信息素更新规则定义公式为，其中，ρ为信息素挥发因子，Q为信息素强度因子，PLm为当前蚂蚁到终点的路径长度，PLbs为当前迭代最短路径长度，PLws为当前迭代最长路径长度，根据上述公式更新每轮迭代的信息素浓度。3CN115560772A说明书1/5页一种基于改进蚁群算法的全局规划路径方法技术领