1、第 卷 第 期太原科技大学学报.年 月 .文章编号:()收稿日期:基金项目:山西省重点研发计划()作者简介:吴波()男硕士研究生主要研究方向为多智能体协调同步等通信作者:王健安教授:基于布谷鸟鸽群融合算法的多智能体避障研究吴 波王健安(太原科技大学 电子信息工程学院太原)摘 要:针对多智能体系统在避障过程中易出现避障路径冗长、时效性较差的问题提出一种布谷鸟鸽群融合避障算法 首先利用自适应调整步长策略调整布谷鸟 飞行步长大小进行长、短交替搜索获得鸟巢位置更新点得到次优避障路径其次在次优路径的基础上引入鸽群优化算法()的地图罗盘算子与地表算子进行二次避障路径规划演示再次更新位置点进而获得最优避障路
2、径 最后利用 仿真通过效率函数分析对比布谷鸟人工势场算法在、个随机分布的障碍物环境中融合算法你避障时间缩短了约 、关键词:多智能体系统避障路径规划布谷鸟算法鸽群优化算法中图分类号:文献标识码:./.多智能体在协调彼此到达目的地途中受周围客观环境约束的影响不可避免会受到一些障碍物的阻挡比如静、动态障碍物规则、不规则障碍物等等 如何有效合理的避开这些障碍物且保持一定的队形完成所需执行的任务是多智能体系统避障研究的热点问题之一为此国内外科研团队提出了许多相应的解决方法传统相关的多智能体避障方法主要有:人工势场法()、遗传算法、模糊逻辑控制法等人工势场法因具有计算简单、实用性好、便于完成底层控制等优点
3、在多智能体避障路径规划中广受青睐温素芳等为解决多智能体避障易陷入局部最优情况重新定义了障碍物分布区间并优化了 引、斥力的计算模型 等针对智能体时有目标点到达失败现象实时约束了智能体与障碍物、智能体与目标点之间的距离、角度、速度等参数以优化引、斥力势场函数模型最终得以顺利到达指定位置 等提出了将传统遗传算法与多智能体系统相结合的避障控制方法利用遗传算法通用性好、收敛速度快等特性迭代得到最优染色体调节智能体的运动参数至最佳状态归一化其超过最小安全距离的斥力从而实现有效避障郑延斌等利用设置模糊控制器来解决跟随智能体与领航智能体的追踪控制问题通过调节人工势场法的增益系数以达到成功避障目的 但这些方法仅
4、仅限于特定简单的障碍物环境中在随机性复杂障碍物环境中往往效果不佳针对复杂环境中多智能体系统避障路径规划过程中出现的避障路径长、时效性差等问题提出布谷鸟鸽群融合算法 首先利用改进布谷鸟算法进行全局粗搜索获得次优避障路径其次再引入鸽群优化算法进行细搜索获得最优避障路径最后利用效率函数分析验证此方法的时效性与适应性 改进布谷鸟搜索算法 算法基本模型布谷鸟搜索算法主要通过 飞行机制与偏好行走机制不断寻找候选鸟巢位置其后利用贪婪策略更新当前位置最终使获得位置逼近最优解 其中 飞行机制是一种长、短步长交替的飞行方式如图 所示:9图 飞行轨迹 飞行机制更新鸟巢空间解如式()所示:()()式中:为 代第 个鸟
5、巢位置 则为 代第 个鸟巢位置 为飞行步长调节参数 为鸟巢数目即初始化空间解个数()为莱维飞行模式获取的随机路径且()(当鸽群迭代次数达到最大值即满足终止条件时地表算子同样也结束进程 布谷鸟鸽群融合算法 融合算法的衔接布谷鸟鸽群融合算法是在改进布谷鸟搜索算法基础上引入鸽群优化算法 首先利用改进布谷鸟算法中的莱维飞行随机行走模式更新鸟巢位置第 卷第 期 吴 波等:基于布谷鸟鸽群融合算法的多智能体避障研究为 得到次优位置在此基础上再利用鸽群优化算法中的地图罗盘算子模式更新位置为 最后利用地标算子模式更新位置为 得到最优位置 鸟巢位置更新如图 所示图 鸟巢位置更新图.第一阶段采用改进布谷鸟搜索算法莱
6、维行走模式获得次优解避免了多智能体避障陷入局部最优提高了全局搜索能力第二阶段针对第一阶段算法的收敛速度慢、鲁棒性及组合优化能力较差等问题采用鸽群优化算法地图罗盘算子与地标算子获得最终解 融合算法的设计步骤布谷鸟鸽群融合算法的实现步骤如下:初始化布谷鸟搜索算法的基本参数:为鸟巢数目为迭代次数上限为发现概率为步长控制量随机初始化 个鸟巢的起始位置()其中 为维数计算每个鸟巢的适应度函数值并获得最优适应度函数初始值利用改进布谷鸟搜索算法中莱维飞行随机行走机制式()更新当前鸟巢位置 求出此时全部鸟巢的适应度函数值采用贪婪策略对比初始鸟巢适应度函数值择优保留 更新本代鸟巢最优适应度函数值并且对比上一代最
7、优值从而获取一组最优鸟巢位置路径分布图此时进入下一次迭代 判断是否达到最大迭代次数是则转否则继续下一步得到布谷鸟搜索算法第一阶段全局最优位置即次优解(次优避障路径)初始化鸽群优化算法的基本参数:鸽子数目为 初始位置为布谷鸟搜索算法第一阶段结束后得到的次优解位置初始速度为 解空间维数为 地图罗盘因子 最大迭代因子为 依据鸽群优化算法地图罗盘算子机制式()更新当前鸽群各位置求出最新鸽群各位置适应度函数值对比初始适应度函数值获得地图罗盘算子阶段最优鸽群位置依据鸽群优化算法地标算子机制式()更新鸽群各位置与上一代鸽群位置对比进行贪婪选择 更新本代鸽群各最优适应度函数值并且对比上一代最优值从而获取一组最
8、优位置路径分布图此时进入下一次迭代 若达到最大迭代次数转 否则继续 得到布谷鸟鸽群融合算法的第二阶段全局最优位置即最终解即最优避障路径布谷鸟鸽群融合算法避障路径流程图如图 所示:/:/图 组合算法避障路径流程图 仿真分析利用 仿真对比文献方法验证本章方法在复杂障碍物环境中的时效性与合理性为了进一步保证该方法的普适性分别选取障碍物数量为、三个环境复杂度不同的实验场景进行仿真分析 对比 种方法各自进行 次避障路径规划试验 此次选取五个智能体组成“”字型编队队形为了便于观察以及安全起见智能体的移动速度为 /队形夹角为 避障过 太原科技大学学报 年程中依旧采用经典的领航跟随法控制多智能体队形 五个智能
9、体的初始坐标为()()()()()领航智能体需要到达的终点坐标为()()()()()实验一:模拟随机性位置障碍物数目为 的环境分布情况领航智能体的起始坐标为()所到达终点坐标为()本文方法和文献方法分别做了 次实验较优的避障路径如图 所示BCZZYYMFBEFSSPCPUSPCPUSPCPUSPCPUMFBEFSSPCPUSPCPUSPCPUSPCPU图 多智能体避障试验 实验二:模拟随机性位置障碍物数目为 的环境分布情况领航智能体的起始坐标为()所到达终点坐标为()本文方法和文献方法分别做了 次实验较优的避障路径如图 所示BCZZYYMFBEFSSPCPUSPCPUSPCPUSPCPUMFB
10、EFSSPCPUSPCPUSPCPUSPCPU图 多智能体避障试验 实验三:模拟随机性位置障碍物数目为 的环境分布情况领航智能体的起始坐标为()所到达终点坐标为()本文方法和文献方法分别做了 次实验较优的避障路径如图 所示BCZZYYMFBEFSSPCPUSPCPUSPCPUSPCPUMFBEFSSPCPUSPCPUSPCPUSPCPU图 多智能体避障试验 第 卷第 期 吴 波等:基于布谷鸟鸽群融合算法的多智能体避障研究 从图()、()、()可以看出在、个随机性障碍分布环境中 本文避障方法能够适应复杂度不同的障碍物环境避障路径较短、时效性较高且与其他障碍物及智能体无擦边碰撞等情况发生 由图()
11、、()、()可知文献布谷鸟人工势场法利用布谷鸟搜索算法改进人工势场法中引、斥力系数在障碍物数目较多环境复杂度较高的场景中整个避障过程路径冗余不平滑避障中期路径些微震荡且队形稳定性较差智能体与智能体之间以及智能体与障碍物之间易发生摩擦碰撞等情况 三种不同障碍物数目环境中的 次避障时间实验数据整理如表 所示表 次避障时间表 障碍物数目方法 次避障路径时间平均时间/本文 本文 本文 由表 可知多智能体系统在障碍物数目为 的环境分布中运动本文方法 次平均避障时间 比文献的 缩短了 在障碍物数目为 的环境分布中运动本文方法 次平均避障时间 比文献的 缩短了 在障碍物数目为 的环境分布中运动本文方法 次平
12、均避障时间 比文献的 缩短了 由此可见本文方法相比较于文献布谷鸟人工势场法避障路径平滑无冗余且具有较高的时效性利用效率函数对各个目标点进行的 次、次避障样本时间方差评价结果如图 所示 不难看出本文方法相对与文献方法样本时间方差值较小即适应性较好由此表明在随机性复杂障碍物分布环境中本文方法具有较好的环境适应性与时效性能够较好的保持一定编队队形完成整个避障过程 结束语本文提出一种改进布谷鸟搜索算法和鸽群优图 两种方法避障时间样本方差对比 化算法相融合的避障路径算法:首先利用改进布谷鸟搜索算法中长、短交替的行走模式不断更新鸟巢位置避免多智能体避障陷入局部最优获得次优避障路径然后在其基础上引入鸽群优化
13、算法中的地图罗盘算子与地表算子机制再次更新鸟巢位置不断扩大搜索范围、快速求得全局最优解进而获得最终避障路径整个避障过程用领航跟随法保持编队队形 最后通过 实验仿真结果表明所提出的方法能够有效的解决障碍物复杂环境下的多智能体避障问题且具有较高的时效性与适应性参考文献:.():.():.太原科技大学学报 年 .():.张攀刘新杰张威等.飞机牵引机器人路径跟踪模糊控制.计算机工程与应用():.温素芳郭光耀.基于改进人工势场法的移动机器人路径规划.计算机工程与设计():.:.()():.:.张晓凤王秀英.布谷鸟搜索算法综述.计算机工程与应用():.:.郑延斌席鹏雪王林林等.基于人工势场法的多智能体编队避障方法.计算机应用():.吴慧超罗元周前能等.时效优先的轮式机器人编队避障策略.信息与控制():.():.().().:第 卷第 期 吴 波等:基于布谷鸟鸽群融合算法的多智能体避障研究