基于多目标搜索的两群多向机器人路径规划方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106323293A(43)申请公布日2017.01.11(21)申请号201610898092.9(22)申请日2016.10.14(71)申请人淮安信息职业技术学院地址223005江苏省淮安市枚乘路3号(72)发明人程乐宋艳红卞曰瑭徐义晗刘万辉(74)专利代理机构淮安市科翔专利商标事务所32110代理人韩晓斌(51)Int.Cl.G01C21/20(2006.01)权利要求书2页说明书4页附图3页(54)发明名称基于多目标搜索的两群多向机器人路径规划方法(57)摘要本发明公开了一种基于多目标搜索的两群多向机器人路径规划方法，将多目标搜索、轮盘赌合理引入到蚁群算法中，并扩大蚂蚁个体的搜索范围和方向；动态信息素的生成和存储方法，使当前最优路径保持较高的信息素水平，以吸引部分蚂蚁沿最优路径移动，对当前最优路径不断优化；本发明综合考虑了整个种群中随机分流部分蚂蚁完成全局随机搜索，同时也考虑了利用蚁群算法的正反馈策略完成对当前最短路径的不断优化，提高了路径搜索效率和发现最优路径概率。CN106323293ACN106323293A权利要求书1/2页1.基于多目标搜索的两群多向机器人路径规划方法，其特征是该机器人路径规划方法包括如下具体步骤：步骤1：以密度为M×N栅格对工作空间进行建模，生成栅格地图；栅格地图中障碍物区域的单元格被标记为“0”，称为“障碍物单元格”；可行区域单元格被标记为“1”称为“可行单元格”；所有单元格信息素浓度都被初始化为1；步骤2：在栅格地图中标记起点S和终点T，分别以S和T为原点，以16向射线方式，向外探测可行单元格，起点S探测到的可行单元格标记为“起点搜索目标”，终点T探测到的可行单元格标记为“终点搜索目标”；步骤3：在起点和终点各生成一个子群，分别称为起点子群和终点子群；起点子群中第i个蚂蚁个体用符号asi表示，终点子群中第j个蚂蚁个体用atj表示；起点子群个体依次向终点生成的搜索目标和终点单元格T爬行；终点子群个体依次向起点生成的搜索目标和起点单元格S爬行；asi的当前移动轨迹用禁忌表RSi记录，atj的当前移动轨迹用禁忌表RTj记录；禁忌表中同一单元格不允许重复出现；爬行过程中，蚂蚁个体选择搜索域内的可达单元格建立可行域集合；通过启发信息和随机策略选择可行域内的一个单元格作为蚂蚁下一步行进位置；当发现第一条可行路径后，步骤3执行结束；步骤4：当发现第一条可行路径后，可行路径被Rbest记录，Rbest路径上的单元格在栅格地图中被标记，Rbest中所有单元格信息素浓度被动态更新为步骤5：起点子群和终点子群，继续相向搜索；搜索过程中每个蚂蚁个体通过启发信息和轮盘赌算法完成可行域内的下一步行进的单元格选择；步骤6：当发现更优的路径后，Rbest被更新；Rbest路径上的单元格在栅格地图中被重新标记并且信息素被动态赋值为地图中其他单元格格的信息素被动态设置为1；步骤7：重复步骤5和步骤6，最后Rbest中记录了算法计算的最后路径。2.根据权利要求1所述的基于多目标搜索的两群多向机器人路径规划方法，其特征是：所述步骤1中，用M×N的栅格为工作空间建模生成栅格地图，还包括：栅格地图的单元格表示为这里(x,y)表示单元格坐标，其中x＝1,…,M，y＝1,…,N；α是一个二值变量，α＝1表示单元格为可行单元格，α＝0表示单元格为障碍物单元格；θ记录了单元格的信息素浓度值，初始值被设置为θ＝1。3.根据权利要求1所述的基于多目标搜索的两群多向机器人路径规划方法，其特征是：所述步骤3中，将整个蚂蚁种群划分为两个子群，以起点子群为例进行描述，终点子群的搜索过程与此类似，还包括：起点中每个蚂蚁体asi向所有终点生成的搜索目标进行搜索，最后对目标点栅格T进行搜索；搜索过程中，asi每一步移动前先建立搜索域，搜索域由asi所在单元格的周围两层单元格构成，每个asi有16个行进方向；删除搜索域中的障碍单元格和asi当前移动路径RSi所经过的单元格，余下的单元格中asi通过直线方式到达的单元格，构成asi的可行域集合；蚂蚁个体选择下一步单元格的公式为：其中，K表示asi的可行域集合；r0是一个阈值，具体为一个随机数，且r0～U(0,1)，asi每行进一步r0都重新被计算；Min(K)表示可行域集合中距离当前搜索目标直线距离最短的单2CN106323293A权利要求书2/2页元格；Rand(K)表示在可行域集合中以随机方式选择一个单元格；当asi的可行域中，发现被标记为“终点搜索目标”的单元格或发现终点单元格T，则一条可行路径被建立，发现的第一条可行路径由Rbest存储。4.根据权利要求1所述的基于多目标搜索的两群多向机器人路径规划方法，其特征是：在步骤4中