系统解决方案 蘑 鲻旗麓誊 无人机实时蚁群算法路径规划 尚梦雨 （广州市第四十七中学，广州５１００００） 摘 要：介绍基于蚁群算法的无人机实时路径规划．保证无人机在航迹作业时有较高的实时性来对作业环境及时 做出响应。针对传统蚁群算法的早熟问题，本文采用信息素全局及局部信息素衰减法。实验结果表明，改进的蚁群算法 具有快速的计算能力，能在短时间内对更改的路径进行响应，验证了算法的有效性。 关键词：无人机；实时路径规划；蚁群算法 中图分类号：ＴＰ２４２ 文献标识码：Ａ Ｏ引言 随着科技发展和社会进步，现代无人机运用的领 域和范围越来越广．执行的任务也更加复杂和多样 化。好的航迹可降低任务风险或成本，航迹优化的价 值也随之变高。航迹规划作为无人机自主飞行控制研 究的重要内容之一，一直都是人们研究的热点，随之 兴起的算法也是层出不穷。由于航迹规划算法兴起， 大量的航迹规划研究性成果涌现，按照规划决策方法 分类可将航迹规划算法分为最优式和启发式算法。其 中，最优式算法包括数学规划和穷举法等［１，２ ３；启发式 算法则有神经网络、遗传算法和蚁群算法等Ｉ３ 。启发 式算法因快速而又高效的计算能力更加得到广大研 究者青睐。 蚁群算法最早由Ｄｏｒｉｇｏ等哺 作为一种多条件约 束优化的方法，很好地解决了一些复杂的组合优化问 题。目前已经有很多种基于蚁群算法或其改进算法应 用于各种不同的离散优化问题，这些研究已经涵盖了 路径规划。本文针对基本蚁群算法在收敛后期易陷入 局部最优的缺点，以信息素更新等方面作为改进点， 提高了算法的计算速度和全局优化能力。进而提高了 无人机的航迹规划效果与实时重规划能力。 １改进蚁群算法 １．１蚁群优化算法 蚁群优化算法在航迹规划中有较多运用。其基本 原理是蚂蚁从出发点沿地形寻找食物，找到食物后原 路折返，并在走过的路径上留下信息素，与此同时信 息素需要按照一定的比例随时间变化衰减。 １．１．１状态转移策略 初始迭代时，设ｆ （０）＝ （ｈ为常数）。蚂蚁设为ｍ 收稿日期：２０１６．１１．２３ ６１ ＷＷＷ．ａｕｔｏ—ａｐｐｌｙ．ｃｏｍ 自动化应用 （１，２，…，ｋ，…， ，其中，７ｉｊ（ｆ）表示迭代次数ｔ时ｉ点到 点间航迹所包含的信息素量。在蚁群移动过程中，蚂 蚁通过各条路径上的信息素总量来确定下一节点转 移方向， Ｏ）表示第ｔ次的迭代时蚂蚁ｋ从点ｉ转移到 点 的概率，其计算公式为： ＿［ 上 一 ， ∈ ｆ０ １ １ ０）＝ ［ （ｆ） （ｆ）］ （１） ０ ｏｔｈｅｒｓ 式中，ａｌｌｏｗｅｄｋ＝Ｎｒ；ｎｔａｂｔｔｋ为蚁群算法中蚂蚁的可 行动点，ｔｂａｕ 为禁止清单，记录蚂蚁ｋ代所走过的节 点及蚂蚁不能走的节点，并不断做动态调整。ｔａｂｕ 表 示尚未经过的节点，Ｍ表示当前航迹节点周遭相邻节 点集。此外，式（１）中的 代表信息素浓度， 代表启发 因子，Ｏｌ与 的取值对算法的收敛起着重要作用。 １．１．２启发因子设计 启发因子的作用是指引蚂蚁往目标的方向移动。 起到方向指引性的作用。其计算公式为： ｒ／ｉｊ＝１ （２） 式中 ｄ表示节点ｉ到节点 的距离。由式（２）可 知，离目标节点越近，导引因子越大；反之越小。此外， 无人机在整个飞行过程中受到诸多因素的影响，例如 飞机燃油损耗程度会大大限制无人机飞行航程，即无 人机存在最大航程参数。记最大路径长度为 一，每一 航程段距离厶应满足： ２２ ｆ。≤，Ｊ （３） ｌ １．１．３信息素更新策略 由于传统蚁群算法有早熟问题，本文通过信息素 更新来促进蚁群全局性搜索，主要有局部和全局信息 素更新方法［１０］。 为了保证蚁群算法局部最优，当每只巡线蚂蚁结 束搜索后。在所走过的每条道路上的信息素都要进行 系统解决方案 蒸发。当信息素蒸发时，后续蚂蚁选择前面蚂蚁所走 道路的概率会变小。局部信息素更新公式为： ＂／＇ｉｊ（￡＋１）＝（１一 ７－ （ｔ）＋Ｏ（１／Ｎ￣Ｌ Ｊ （４） 式中，０为预先设定好的局部蒸发系数（０＜ ＜１）…Ｌ。 为随机选择各毗邻点之间的一段距离。 当本轮所有蚂蚁走过的所有道路信息素更新后， 全局信息素更新会使当前迭代巾最优路径上的信息素 蒸发量减少。 此在下轮迭代时，残存信息素会让蚂蚁 更加精确地找到更好的路径。全局信息素更新公式为： ｄ，（ｆ＋１）＝（１－ｐ）ｒ（ｔ）＋ｐＡｒ （５） 式中，ｐ（０ ＜１）为全局信息素衰减参数。算法为了 １．３无人机航迹重规划 一般在无人机巡线作业过程中，州户会根据需要 来设定无人机飞行作业目标点，然后系统根据目标点 生成最优航迹，并控制无人机根据规划的路径进行作 业。当无人机位置脱离航线或者目标点变更后，系统 会根据改变的无人机动态及静态信息利用蚁群算法 重新生成路径， 一般无人机系统主要包括静态无人机路径规划 和动态无人机航迹规划策略。当无人机工作环境及作 业要求需要更改航迹点时．无人机系统会以 机当前 ＧＰＳ坐标为起点，根据改动的动态无人机信息对无人 机当前飞行航迹进行刷新．重新生成路径指令来遍历 目标。 当尤人机作业路径发生改变后，系统会迅速做｝｝｛ 响应，根据无人机系统新生成的航迹来控制无人机飞 保证全局信息素更新策略的有效性，将△ 赋值为全 局最优路径的倒数： Ａｔ＝１／ＬＩ （６） １．２基于蚁群算法的航迹规划 大多数情况下，无人机执行任务时飞行的航迹都 是从起点 发到各个航路点完成任务冉返回起点的 过程 本文的航迹规划也是以此为前提，闪此可将此路 径规划转化为ＴＳＰ（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ）问题， 行．系统会将控制指令信号转化为ＰＷＭ信号，达到对 无人机姿态控制的目的 “ 。蚁群重规划系统控制原 理如图２所示 ：｛ ⅢＩ… Ｉ在执行蚁群算法时．只需将求解ＴＳＰ问题时的城市坐 标改为航路点坐标即可Ｆ１２１。蚁群优化算法流程（如图１ 所示）： ｔ 二＿。＿＿ Ｅ＾ 、 ＾ 鬯蒜篙 照 甫＿ 一 ｛｜ １ ｉ （１）初始化，将蚂蚁随机分布到城市中，并将蚂蚁 所在的城市添加到各自的禁忌列表中。 ｒ＿二叶．＿Ｉ ！．】丝 （２）设定结束条件，不满足结束条件，执行步骤 （３）、步骤（４）循环。 图２蚁群重规划系统控制原理 （３）对蚂蚁 （１＜ ＜Ｍ），进行如下指示： ｉｆ ｆ本次循环结束时能到达下一个城市ｉ） 抵达下一个城市 ： ｅｌｓｅ记录本次循环路径。 ２仿真实例 ２．１基于蚁群算法的无人机航迹规划 假设蚁群相关信息 ＝２，／３＝３，ｐ＝０．１，盯 ＝０．０１， ＝ ０．１， ＝３０，Ｋ＝１００，其中Ｍ为蚂蚁数， 为循环次数， 并设起点为（０，１０，４），终点为（２０，８，５），可仿真得到最 优巡线路径如图３所示、 （４）更新路径上的信息素。 （５）输出结果 、 （６）程序结束。 ２０ 毒 Ｉ— 图３无人机航迹规划 根据起点、终点及地图信息的解算，总算法时长 ３２５ｍｓ。从算法 成路径中可以看Ｈ｛，该算法可有效规 自动化应用 ２０１６ １２期 ６２ ｊ， 忏．：７ —，ｒＪ哆Ｉ 鹈裁辫曦巍棼麓 避当前路径上的障碍，确保无人机安全飞行，还可使 ［３］Ｙａｎｇ Ｙｕ．Ｒｅｓｅａｒｃｈ ｏｎ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ Ｍｏｂｉｌｅ Ｒｏｂｏｔ Ｂａｓｅｄ ｏｎ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｄｙｎａｍｉｃ 无人机作业时有效地监测地面信息 ２．２基于蚁群算法的无人机航迹重规划 假设无人机作业航迹规划侦测点分别为ｆ３０，４０，２０）， Ｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＩＥＥＥ，２００８：４９７—４９９ ［４］ＴＡＮＧ Ｌ，ＦＡＮＧ Ｔ Ｊ．Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆｕｎｉｖｅｒｓｉｔｙ ｏｆｓｃｉｅｎｃｅ ａｎｄｔｅｃｈｎｏｌｏｇｙｏｆｃｈｉｎａ，２００９，３９（９）：７７－７９ ［５］白俊强，柳长安．基于蚁群算法的无人机航路规划【Ｊ］． （４５，５０，６０），（５５，６０，４０），（２３，４０，１０），（２９，５４，５５），（１８，４０，３４）， （２２，６０，２３），（２４，４２，７７），（２５，６２，５２），（２５，３８，２３），并设蚁 群算法参数 ：２， ＝３，Ｐ：Ｏ．１，ｑ０＝０．０１，０＝０．１，Ｍ＝ ３０，Ｋ＝１００，得到无人机遍历目标点的路径如图４ 所示，其算法运行时间为４５０ｍｓ．最短路径长为 ２１８．３５１。需要对无人机航迹进行更改时输入新坐 标点，生成路径最短为２０９．４９３．新航迹生成用时 ４０４ｍｓ 飞行力学，２００５，２３（２）：３５．３８ 【６】Ｏｓｃａｒ Ｃａｓｔｉｌｌｏ，Ｌｅｏｎａｒｄｏ Ｔｒｕｊｉｌｌｏ，Ｐａｔｒｉｃｉａ Ｍｅｌｉｎ．Ｍｕｌｔｉｐｌｅ ｏｂｊｅｃｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｐａｔｈ－ｐｌａｎｎｉｎｇ ｏｐｔｉｍｉｚａ —ｔｉｏｎ ｉｎ ａｕｔｏｎｏｍｏｕｓ ｍｏｂｉｌｅ ｒｏｂｏｔｓ［Ｊ］．Ｓｏｆｔ ｃｏｍｐｕｔ，２００７， １ １：２５９—２７９ 【７］Ｎ．Ｓａｒｉｆ￡ＡｎＯｖｅｒｖｉｅｗｏｆＡｕｔｏｎｏｍｏｕｓＭｏｂｉｌｅＲｏｂｏｔＰａｔｈ Ｐｌａｎｎｉｎｇ Ａｌｇｏｒｉｔｈｍ［Ｃ］．ＩＥＥＥ ４ｔｈ Ｓｔｕｄｅｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ（Ｓｃｏｒｅｄ ２００６）．２００６，１ ８３—１ ８８ ［８］Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ，ＣｏｌｏｍｉＡ．Ａｎｔｓｙｓｔｅｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ａ ｃｏｌｏｎｙ ｏｆ ｃｏｏｐｅｒａｔｉｎｇ ａｇｅｎｔ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ，ａｎｄ Ｃｙｂｅｎｅｒｔｉｃｓ，１９９６，２６（１）：２９－４１ ［９］王绪芝．基于蚁群算法的无人机航迹规划及其动态仿 真【Ｄ】．南京：南京航空航天大学，２０１２ 图４无人机航迹规划与重规划 ［１ ０］Ｒｕｅｙ—ＭａｗＣｈｅｒｔＨｅｕｒｉｓｔｉｃｓＢａｓｅｄＡｎｌＣｏｌｏｎ５Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｒｆ Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ［Ｊ】．ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｄｕｓｔｒｉａｌ Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２０ １ １：１ ０３９－１ ０４３ ３结语 蚁群算法实验结果显示．改进蚁群算法具有高效 的迭代能力和快速的计算速度，可以针对目标及时做 出相应，并随着无人机当前位置或目标点的更改迅速 改变无人机的飞行航迹，能很好地满足无人机实时航 ［１１］Ｗｅｎｚｈｉ—ｑｉａｎｇ，Ｃａｉｚｉ－ｘｉｎｇ．Ｇｌｏｂａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｐｐｒｏａｃｈ ｂａｓｅｄ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｍ．［ｈＪ］．ｃｅｎｔ． Ｓｏｕｔｈ ｎｉｖ．ｔｅｃｈｎｏｌ，２００６，１３（６）：７０７－７１２ ［１２］ｗｌｕ Ｂｉｎ，Ｓｈｉ Ｚｈｏｎｇ－ｚｈｉ，ＡｎＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍＢａｓｅｄ Ｐａ￣ｉｔｉｏｎ Ａｌｇｏｒｉｔｍ ｈｏｒｆ ＴＳＰ，Ｃｈｉｎｅｓｅ［Ｊ］．Ｊ．Ｃｏｍｐｕｔｅｒｓ， ２００１，２４（１２）：１３２８—１３３３ 迹规划准确性和实时性的要求。 参考文献 ［１］左洪浩．蚁群优化算法及其应用研究［Ｄ］．合肥：中国科 学技术大学合肥智能机械研究所．２００６ ［１３］Ｓ Ｓ Ｇｅ，Ｙ Ｊ Ｃｕｉ．Ｄｙｎａｍｉｃ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ ｏｒｆ ｍｏｂｉｌｅ ｒｏｂｏｔｓ ｕｓｉｎｇ ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄ ｍｅｔｈｏｄ［Ｊ］．Ａｕｔｏｎｏｍｏｕｓ Ｒｏｂｏｔｓ，２００２，１ ３：２０７－２２２ ［２】ＷＡＮＧ Ｗ Ｐ，ＬＩＵ Ｊ．Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｕｎｍａｎｎｅｄ Ａｉｒ Ｖｅｈｉｃｌｅ Ｒｏｕｔｅ Ｐｌａｎｎｉｎｇ Ｍｅｔｈｏｄｓ［Ｊ］．Ｆｌｉｇｈｔ Ｄｙｎａｍｉｃｓ， ２０１０，２８（２）：６—１０ ［１４】韩攀．基于改进蚁群算法的无人机航迹规划［Ｄ］．南 京：南京航空航天大学，２０１３ （上接第６页Ｊ 服缺陷，提高电气控制系统的工作效率，才能保证 对电气自动化的监控力度。 参考文献 ［１】刘超．电气自动化控制系统之设计思路探析［Ｊ］．神州， ２０１３（０６１ ［Ｊ］．科学之友，２０１ １（１１） ［３］王庆海．ＰＬＣ控制系统接地抗干扰技术［Ｊ】．电子技术 与软件工程，２０１５（１６） 【４】廉志先，郑德祥．电气自动化控制设备可靠性测试分析 ［Ｊ］．科技经济导刊，２０１６（０４） 【５］姜爱林，裴志富．电气自动化控制技术的探讨［Ｊ］．科技 ［２］彭里．电气自动化在我国煤矿的发展现状及未来展望 ６３ ＷＷＶ￣．ａｕｔｏ ａｐｐｌｙ．ｃｏｍ 自动化应用 创新与应用．２０１６（１７）
