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

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111982125A(43)申请公布日2020.11.24(21)申请号202010891876.5(22)申请日2020.08.31(71)申请人长春工业大学地址130012吉林省长春市朝阳区延安大街2055号(72)发明人侯阿临杨骐豪姜伟楠吴浪孙弘建季鸿坤杨理柱刘丽伟李秀华梁超杨冬(51)Int.Cl.G01C21/20(2006.01)G05D1/02(2020.01)权利要求书2页说明书5页附图4页(54)发明名称一种基于改进蚁群算法的路径规划方法(57)摘要本发明涉及一种基于改进蚁群算法的路径规划方法。该算法将改进的人工势场(APF)算法和蚁群算法相结合，采用改进APF算法进行初始地图规划，降低了蚁群算法初始规划的盲目性。该算法利用A*算法的评估函数以及路径转折角度来改进启发函数，引入启发信息递增函数，免于局部最优的同时保证收敛速度。改进状态转移规则并自适应地调整状态转移函数的阈值，可以提高算法的运行效率，同时可以增加解的多样性。改进算法的信息素更新机制和路径评价函数，提高了算法的全局最优性，使得到的路径更符合实际需求。CN111982125ACN111982125A权利要求书1/2页1.一种基于改进蚁群算法的路径规划方法，其特征在于，包括以下步骤：Step1：采用栅格法对机器人的工作环境进行建模；Step2：设置起始点S，目标点G，最大迭代次数Ncmax，初始化全局信息素；Step3：使用一种改进的人工势场法简化初始地图，减少蚁群算法探索的地图范围；Step4：将m只蚂蚁置于起始点S，并将它们此时的位置加入禁忌表Tabu；基于传统蚁群算法的基础上引入A*算法的自适应启发函数思想，考虑转折角度，结合其计算蚂蚁可能前往的下一节点j到目标点G的距离LjG，综合构造启发信息函数，同时设计启发函数递增函数自适应调整启发信息；在启发信息函数和全局信息素的作用下，在轮盘赌法算法的基础上进行改进自适应调整选择概率，计算t时刻蚂蚁k在节点i选择下一个节点j的状态转移概率，选择蚂蚁下一个前往的节点j；蚂蚁到达下一节点j后，更新禁忌表Tabu，将节点j加入禁忌表；Step5：判断蚂蚁是否到达目标点G；若是，停止搜索，一次迭代结束；否则，继续按照Step4的方法搜索直到找到目标点；Step6：在一次迭代结束，所有蚂蚁到达目标点G后，综合考虑路径的长度、转折数以及转折角度来改进路径的评价函数评价最优路径,参考最优-最差蚂蚁系统原理，对全局排名前n的最优路径，更新全局信息素，清空禁忌表Tabu；Step7：判断当前迭代次数Nc是否到达最大迭代次数Ncmax：若是，输出最优路径；否则，转到Step3，直到Nc＝Ncmax；算法结束，输出最优路径。2.根据权利要求1所述基于势场法改进的蚁群算法路径规划方法，其特征在于Step3中所使用的人工势场法，算法通过三个节点列表在栅格图上构建出一张新的势场图，势场图生成步骤具体如下：Step3.1首先，将所有节点都加入到open表中，再将目标点从open表中删除，同时设置其具有最大的势场值，加入到temp表；接下来将所有障碍点从open表中删除，设置其势场值为，加入到closed表中；Step3.2之后，从目标节点开始，按公式（为递减值，可设为10）为目标节点在open表中的相邻节点赋予势场值，并将这些相邻节点加入temp表中，从open表中删除，将目标节点从temp表中移除，并加入到closed表；Step3.3然后，从temp表中依次取出节点，按照Step3.1-3.2为节点赋予势场值，迭代i次后，直到temp表为空，所有节点都被赋予了势场值，势场图生成，与的大小可根据实际地图大小进行设定；通过算法获得多个子路径，然后统计路径中的所有节点，将不属于统计节点的节点设置为障碍物，从而简化初始地图。3.根据权利要求1所述基于势场法改进的蚁群算法路径规划方法，其特征在于：所述启发信息函数如下：2CN111982125A权利要求书2/2页其中，dij表示迭代次数为t时当前节点i和可选节点j之间的欧氏距离，djg表示可选节点j与目标节点g之间的欧几里德距离，thita表示前一节点与当前节点i和可选节点j之间的角度，w1，w2和w3代表三个启发因子的权重，表示启发信息函数的递增函数，控制迭代次数为t时启发信息的大小，函数的调整系数决定了递增函数的增长速度。4.根据权利要求1所述基于势场法改进的蚁群算法路径规划方法，其特征在于，所述状态转移函数如下：其中，α和β分别是信息素因子和启发式因子，α越大，蚂蚁k越倾向于选择信息素浓度较大的路径，β越大，蚂蚁越倾向于选择距离目标点近的节点，qo为选择概率，qmax表示最大选择概率的值，qmin表示最小