ＤＯＩ：１０．１９５５７６．ｅｎｋｉ．１００１—９９４．４．２０１７．０３．００１ 基于改进型蚁群算法的ＡＵＶ路径规划 董凌艳 ．一．徐红丽 （１．中国科学院沈阳自动化研究所机器人学国家重点实验室，沈阳１１００１６；２．中国科学院大学北京１０００４９） ，摘要：在已知障碍物的环境中寻找一条从起点到终点的无碰路径即为路径规划 扩展改进 型蚁群算法应用背景，应用于智能水下机器人（ＡｕＶ）的路径规划。为改善传统蚁群算法在 实际应用中的不足，提出加入再励学习机制的改进型蚁群算法。通过对蚁群信息素更新实 行奖惩制度后，改善蚁群算法搜索求解缓慢，易陷入局部最优解而产生停滞现象，提高算 法的搜索速度及寻优能力，能够明显地提高路径规划的效率。仿真结果验证了改进算法的 有效性。 关键词：路径规划；蚁群算法；再励学习；Ｄ１ｊ ｋｓｔｒａ算法；信息素更新；自治水下机器人 中图分类号：ＴＰ２７３ 文献标志码：Ａ 文章编号：１００１—９９４４（２０１７）０３—０００１—０４ ＡＵＶ Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ＤＯＮＧ Ｌｉｎｇ－ｙａｈ１，２，ＸＵ Ｈｏｎｇ—ｌｉ （１．Ｓｔａｔｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｒｏｂｏｔｉｃｓ，Ｓｈｅｎｙａｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ａｕｔｏｍａｔｉｏｎ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅ，ＳｈｅｎｙａＲｇ １１００１６， Ｃｈｉｎａ；２．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ １０００４９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｐａｔｈ ｐｌａｎｎｉｎｇ ｉｓ ｍｅａｎｔ ｂｙ ｌｏｏｋｉｎｇ ｆｏｒ ａ ｐａｔｈ ｗｉｔｈｏｕｔ ｃｏｌｌｉｓｉｏｎ ｆｒｏｍ ｔｈｅ ｓｔａｒｔ ｐｏｉｎｔ ｔｏ ｔａｒｇｅｔ ｐｏｉｎｔ ｉｎ ａｎ ｅｎｖｉｒｏｎｍｅｎｔ ｗｈｉｃｈ ｔｈｅ ｏｂｓｔａｃｌｅ ｉｓ ｋｎｏｗｎ．Ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｘｔｅｎｄｅｄ ｔＯ ｔｈｅ ａｒｅａ ｏｆ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ａｕｔｏｎｏｍｏｕｓ ｕｎｄｅｒｗａｔｅｒ ｖｅｈｉｃｌｅ．ｎａｍｅｌｙ ＡＵＶ ｆｏｒ ｓｈｏｎ．Ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｄｒａｗｂａｃｋｓ ｏｆ ｔｒａｄｉｔｉｏｎａｌ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｉｎ ｐｒａｃｔｉｃａｌ印ｐｌｉｅａｔｉｏｎ，ａｎ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒｅｉｎｆｏｒｃｅｍｅｎｔ ｌｅａｒｎｉｎｇ ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ａｎｔ ａｌｇｏ— ｒｉｔｈｍ’Ｓ ｓｈｏｒｔｃｏｍｉｎｇｓ ｏｆ ｓｌｏｗ ｉｎ ｓｅａｒｃｈ ａｎｄ ｅａｓｙ ｉｎ ｔｒａｐｐｉｎｇ ｉｎｔｏ ｌｏｃａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ａｒｅ ｉｍｐｒｏｖｅｄ ｗｉｔｈ ｔｈｅ ｕｓａｇｅ ｏｆ ｒｅｗａｒｄ ａｎｄ ｐｕｎｉｓｈｍｅｎｔ ｉｎ ｔｈｅ ｕｐｄａｔｅ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｐｈｅｒｏｍｏｎｅ．Ｉｍｐｒｏｖｅ ｔｈｅ ｓｅａｒｃｈ ｓｐｅｅｄ ａｎｄ ｏｐｔｉｍｉｚａｔｉｏｎ ａｂｉｌｉｔｙ ｆ ｔｏｈｅ ａｌｇｏｒｉｔｈｍ ｅａＲ ｏｂｖｉｏｕｓｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｉｃｉｆｅｎｃｙ ｏｆ ｐａｔｈ ｐｌａｎｎｉｎｇ．Ｓｉｍｕｌ￣ｉｏｎ ｒｅｓｕｌｔｓ ｖｅｒｉｆｙ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ｐａｔｈ ｐｌａｎｎｉｎｇ；ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ；ｒｅｉｎｆｏｒｃｅｍｅｎｔ ｌｅａｒｎｉｎｇ；Ｄｉｊｋｓｔｒａ ｌｇｏａｉｒｔｈｍ；ｐｈｅｒｏｍｏｎｅ ｕｐｄａｔｅ；ａｕｔｏｎｏｍｏｕｓ ｕｎｄｅｒｗａｔｅｒ ｖｅｈｉｃｌｅ（ＡＵＶ） 海洋蕴藏着丰富的矿物资源、生物资源以及能 源，是人类可持续发展的财富，因此对海洋的开发成 为各国的战略重点。常见的水下机器人包括遥控机器 人ＲＯＶ和自治水下机器人ＡＵＶ。ＡＵＶ由于其自主 性而受到广泛应用【ｌ１。导航是实现机器人从起始位 收稿日期：２０１６—１２—０２；修订日期：２０１７—０１—１４ 置到目标位置无碰撞且不丢失的一个过程，包括定 位、路径规划及运动控制３个部分。路径规划是导 航中最重要的一部分。由于机器人在各个领域中都 扮演重要角色．路径规划的研究得到了快速发展［２１。 路径规划是在一定环境下，规划或寻找一条从 基金项目：中国科学院国防创新项目（ＣＸＪＪ一１５Ｍ０３１） 作者简介：董凌艳（１９９２一），女，博士研究生，研究方向为水下对接等。 茸动纪与 蓑２０１７，３２ｐ） ■ 起始状态（包括位置和姿态）到目标状态的无碰安 全路径。路径规划需要解决３个问题：从起点到目 标点的运动；运用一定算法实现避障，且经过必经 点：满足上述要求后，轨迹优化。路径规划根据工作 环境不同可分为２种：基于模型的全局路径规划 （静态路径规划）。作业环境全部已知；基于传感器 的局部路径规划（动态路径规划），作业环境全部未 知或部分未知。常用的路径规划方法有可视图法、 自由空间法、最优控制法、栅格法、拓扑法。 随着发展，遗传算法、模糊集理论和神经网络 等许多人工智能算法也应用到了路径规划领域［３１。 ＡＵＶ在海洋环境中工作区域宽阔，障碍物稀疏。 ＡＵＶ所处环境属于大范围开放的三维空间。三维路 径规划十分复杂，难度较大，且大部分路径规划适 用于二维空间。ＡＵＶ在水下作业大部分时间是在 同一深度航行，所以可以将三维路径规划转化为 二维路径规划。由动力学原理知，ＡＵＶ航艏向以顶 流姿态是最省力和稳定的。因此路径规划时尽量使 ＡＵＶ的姿态满足顶流要求ｆ４１。ＡＵＶ水下携带能源有 限，水的黏性阻力等阻力因素更会增加ＡＵＶ的能 耗，所以选择长度代价小的路径有利于节约ＡＵＶ的 能源。 传统的路径规划方法都存在一定的缺陷，例如 遗传算法在解决大规模问题时编码困难，时空消耗 大。文献［５］指出将遗传算法与分层规划思想结合， 能有效克服遗传算法的不足。遗传模拟退火算法结 合分层路径规划思想。克服遗传模拟退火算法早 熟、局部寻优能力差的缺点嘲。基于栅格模型的改进 蚁群算法采用折返迭代方式．采用惯性原则和最大 信息素搜索策略使蚂蚁对最优路径更加敏感，提高 算法的效率和稳定性【７Ｊ。蚁群算法用于路径规划时， 由于蚁群算法具有一定的随机性，蚁群数量大，所 以算法寻优缓慢，且存在局部最优等问题。再励思 想加入蚁群算法能提高寻优效率，改善算法性能。 １蚁群算法描述 １．１算法基本原理 蚁群算法是２０世纪９Ｏ年代提出的一种新型 进化算法，源于对蚂蚁的研究。蚂蚁在寻找食物时， 在走过的路径上释放一种称为信息素的分泌物，信 息素保留一定的时间，后续蚂蚁能够察觉信息素的 存在，选择信息素浓度较高的路径并且经过时留下 目 自己的信息素。假设有２条路径ＡＢ和ＣＤ，ＡＢ的长 度是ＣＤ的２倍。初始时，这２条路径都没有信息 素．蚂蚁选择路径的概率各为１／２。由于路径长度不 同．在一段时间内经过ＣＤ的蚂蚁数量是ＡＢ的２ 倍，ＣＤ路径上信息素浓度就是ＡＢ段信息素浓度的 ２倍。这样，蚂蚁选择ＣＤ的概率大于选择ＡＢ的概 率，随着时间的推移，选择ＣＤ的概率越来越大，最 终完全选择ＣＤ。蚁群算法具有启发性、较强的鲁棒 性、优良的分布性、易于与其它算法结合网。 １．２算法基本流程 蚁群算法的基本流程为①建立空间模型；②规 划初始路径；③初始化算法参数；④开始搜索；⑤蚂 蚁到达终点；⑥信息素更新；⑦判断算法是否结束， 未结束跳至④，结束了则至⑧；⑧得到最优路径。 １．３建模及初始化路径 步骤采用Ｍａｋｌｉｎｋ构建二维路径规划的空间模 型。Ｍａｋｌｉｎｋ线定义为障碍物之间不与障碍物相交 的顶点之间的连线。以及障碍物顶点和边界的交 线。Ｍａｋｌｉｎｋ线构造二维空间。Ｍａｋｌｉｎｋ图上存在ｌ条 自由链接线，链接线的中点及起点和终点构成初始 路径规划的无向网络图。 Ｄｉｊｋｓｔｒａ算法用于计算单源最短路径，就带权图 中所有节点分成２组，以确定最短路径组和未确定 最短路径组。按最短路径长度递增顺序逐渐将未确 定组中的点加入到已确定组中，直到所有节点都包 含在已确定最短路径组。利用Ｄｉｊｋｓｔｒａ算法得到一 条从起点到终点的次最优路径。路径依次经过链接 线Ｌ （ｉ＝１，２，…，ｄ），其端点为 ｍ， ‘”，链路上其它 点表示为 Ｐｉ（ｈ ）＝只‘。 ＋（ （１）ｐｉ 。 ） ｈ ∈［０，１］（ｉ＝１，２，…，ｄ） （１） 式中：ｈ 为比例参数；ｄ为链路划分节点数。只要给 定一组ｈ参数即可得到新路径，蚁群算法的解表示 为（ｈ－，ｈ２，…，ｈ ）。 １．４蚁群转移规则 蚂蚁寻找下一节点按照一定的转移规则，与信 息素浓度及启发信息有关。蚂蚁在链接线上厶选择 下一链接线厶＋ 上‘，节点的方法为 ｒ ，Ｉ ｌ Ｉ Ｂ Ｉ、 ｊｌａｒｇｍａｘｋ ，【ｌ Ｉ ， ｌ Ｊ，ｑ≥ｑｏ … Ｊ －０ｔｈｅｒｓ 式中：ｉ为链接线上的点；ｑ为［０，１］之间的随机数； ｑ。为［０，１］之间可调参数； ． 为启发值； ｍ为信息 素浓度。．，的计算方法为首先计算 到 的选择概率 Ｐ ，以此为根据，应用轮盘赌法找到下一节点 ，Ｐ 的计算方法为 ｐｉ，ｊ－－ —— — 一 上Ｏ￣ＥＩＴｉ， 叼ｉ． 径的代价值作为再励信号，对较优的人工蚂蚁进行 奖励．对较差或者失败的人工蚂蚁进行惩罚，加 入再励机制后，提高较优路径的信息素浓度．降低 较差路径信息素浓度，使人工蚂蚁更倾向于较优路 （３）（ｊ 径。另一方面，增加了未选择路径和已选择路径信 息素的对比，提高算法的寻优能力。在基本的蚁群 １．５信息素更新 信息素是影响蚁群算法的关键因素，分为局部 算法中，局部信息素更新中为预设值不变．改进 的局部信息素更新基于路径代价加入奖励惩罚制 信息素更新和全局信息素更新。实时信息素更新是 蚂蚁走过每个节点后对该节点的信息素进行更新， 其公式为 ，产（１－ｐ）ｒｌ，ｊ＋Ｐ＇ｒｏ （４） 式中：Ｉ＂ｏ为信息素初始值；Ｐ为［０，１］区间的可调参 数。当所有蚂蚁走过全部节点后，完成依次迭代搜 索，选择其中的最短路径进行全局信息素更新： ＝， （１－ｐ）＇ｒｉ，』＋｜ｐ△ ， Ａ＇７＂ｉ＝． Ｉ／Ｌ （５） 式中：￡‘为最短路径长度嘲。 ２ 改进算法 蚁群算法具有随机性，蚁群数量大，迭代次数 多，所以蚂蚁构造出的路径优劣程度不同。有些蚂 蚁甚至不能成功构造路径。如果蚂蚁在迭代过程中 构造劣质路径或不能成功构造路径可能会使算法 过早收敛或者搜索失败。为了改善蚁群算法的此类 缺陷，将再励学习机制引入到信息素更新机制中． 提高蚁群算法的性能。 ２．１ 再励学习 再励学习把学习看作试探评价的过程，用图１ 描述。学习机输出一个动作作用于环境。环境接收 输出动作状态发生变化，产生奖励或惩罚的再励信 号反馈给学习机，学习机根据环境当时的状态以及 反馈的奖励或惩罚信号选择下一步的动作信号，选 择动作信号的原则是使受到正再励即奖励信号的 概率越来越大［１Ｏｌ。 图１再励学习系统 Ｆｉｇ．１ Ｒｅｉｎｆｏｒｃｅ ｌｅａｒｎｉｎｇ ｓｙｓｔｅｍ ２．２改进信息素更新 在蚁群算法信息素更新过程中以蚂蚁构造路 廖动 与 蓑２０１７，３２（３） 度．即： 下 ，产（１－ｐ）￣＇ｉ，＋ｐＡ￣－ △丁：｛【０ （（ｎＷ （ ））） （（人工蚂蚁构造解失败）人工蚂蚁构造解成功 （ ６） 式中：Ｗ （ｔ）为当前迭代中第ｋ只人工蚂蚁所构造 路径的综合代价值。由此可见，当人工蚂蚁构造路 径越优，其代价值越小，得到奖励，其局部更新中 信息素增量Ａｒ越大．对应路径上信息素保留的越 多，后续迭代中被选择的概率就大。如果人工蚂 蚁构造的路径代价值大或者无穷大，受到惩罚，其 局部信息素更新中信息素增量△ 越小．对应路径 上信息素保留的越少，在后续迭代中被选择的概率 越ｄｘ［ｎ］ ３仿真与分析 仿真实验算法流程如图２所示。 ｌ ＭＡＫｕＮＫ图论法建模 Ｉ Ｄ ｋ ｔ 法生成初始路径 【 初始化参数 １ｒ＇ ＩＩ蚂蚁迭代寻优， 局部信息素更新 寻找最短路径．全局信息素更新 Ｎ 图２算法流程 Ｆｉｇ．２ Ａｌｇｏｒｉｔｈｍ ｆｌｏｗ ｃｈａｒｔ 在有障碍的环境内，应用ＭＡＫＬＩＮＧＫ图理论 构造如图３所示的二维规划空间。 利用Ｄｉｊｋｓｔｒａ算法获得初始最短路径。算法流 程为①初始化２个集合 和ｓ，分别存放未确定和 已确定最短路径集合点，利用带权图初始化原点到 ■ ∞舳∞∞加∞∞∞∞∞０ ！ｖｌ０ ｉ ： ｉ ；ｖ２Ｏ ： ： ： ：ｖ１９ ｖ１６ ４０ ６ｏ ８Ｏ ｌ００ ｌ２０ １０４ １６０ １８０ ２０ｏ （ｋｉｎ） 图３无向网络图 Ｆｉｇ．３ Ｕｎｄｉｒｅｃｔｅｄ ｎｅｔｗｏｒｋ ｄｉａｇｒａｍ 其他节点的最短路径长度Ｄ，其中有连接弧的对应 值是其弧的权值，否则为极大值；②选择原点到点ｉ 的最短路径长度Ｄ［ｉ］，将点从集合 移至集合Ｓ；③ 根据节点ｉ更新数组Ｄ中源点到集合 中的节点ｋ 对应的路径长度值；④重复②③找到原点到所有节 点的最短路径。通过以上算法得到图４。 ｘ／（ｋｍ） 图４初始最短路径 Ｆｉｇ．４ Ｉｎｉｔｉａｌ ｓｈｏｒｔｅｓｔ ｐａｔｈ 初始化最短路径后，得到初始最短路径经过的 链接线。每条链接线上１０等分得到等分点作为采 样点。计算采样点之间的距离ｄ，寻找所有采样点之 间的最短距离ｄ 和最长距离ｄ 。从节点ｉ到节点 的代价计算为： ｃｏｓｔ＝ ： ｄＨＩａｘ—ｄＩＩｌｉｎ ＣＯＳＴ＝∑ｃｏｓｔ （７） 式中：ＣＯＳＴ为已选择路径代价值与待选择节点的 代价和．作为再励学习机制奖惩标准。标准改变将 会影响算法的迭代效果。当代价小于一定值时，给 予奖励，局部更新中信息素衰减后的增量△ 大，当 代价大于一定值时，给予惩罚，局部更新中信息素 衰减后的增量Ａｒ为零。加入再励学习机制的蚁群 算法。最后得到的迭代曲线和基本蚁群算法得到的 迭代曲线的对比如图５所示。 ■ ∞舳∞∞加∞∞∞∞加０ 图５改进蚁群算法和基本蚁群算法迭代曲线 Ｆｉｇ．５ Ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ａｎｄ ｂａｓｉｃ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｉｔｅｒａｔｉｖｅ ｃｕｒｖｅ 由图可见，加入再励机制的改进蚁群算法较基 本蚁群算法寻优更快，迭代曲线更加稳定。 ４ 结语 介绍了传统ＡＵＶ路径规划的方法和特点，以 及基本蚁群算法的原理、流程与不足。将再励机制 引入到蚁群算法中，利用ＭＡＫＬＩＮＫ建立二维规划 空间模型．Ｄｉｊｋｓｔｒａ算法得到初始次优路径。在局部 信息素更新中加入奖惩再励信号。仿真验证了改进 型算法的有效性，改善了蚁群算法搜索求解时陷入 局部最优解而产生停滞现象，提高了算法的搜索速 度及寻优能力．能够明显地提高了路径规划的效率。 参考文献： …１ 李哗，常文田，孙玉山，等．自治水下机器人的研发现状与展望ｌＪ】． 机器人技术与应用，２００７，２０（１）：２５—３１． ［２］张捍东，郑睿，岑豫皖．移动机器人路径规划技术的现状与展望 ．系统仿真学报，２００５，１７（２）：４３９—４４３． ［３】张巧荣．智能水下机器人分层全局路径规划方法研究［Ｄ］．哈尔 滨：哈尔滨工程大学，２００２：１－８３． 【４］彭艳，顾国昌．基于遗传算法的水下机器人大范围路径规划【ＪＪ．应 用科技，２００３，３０（２）：１８—２１． ｆ５】顾国昌，付岩，刘海波．基于遗传模拟退火算法的水下机器人路 径规划【Ｊ】．哈尔滨工程大学学报，２００５，２６（１）：８４—８７． ［６］王沛栋，冯祖洪，黄新．一种改进的机器人路径规划蚁群算法［Ｊ］． 机器人。２００８，３０（６）：５５４—５６０． 【７］覃刚力，杨家本．自适应调整信息素的蚁群算法Ⅲ．信息与控制， ２００２，３１（３）：１９８—２０１． ［８】史峰，王辉，郁磊，等．ＭＡＴＬＡＢ智能算法３Ｏ个案例分析【Ｍ］．北 京：北京航空航天大学出版社，２０１１：２１７—２２７． ［９】张云．一种基于模糊神经网络采用再励学习的ＰＩＤ控制器【Ｄ１．曲 阜：曲阜师范大学，２００３：１－５１． 『１０］陈岩，苏菲，沈林成．概率地图ＵＡＶ航线规划的改进型蚁群算法 【Ｊ］．系统仿真学报，２００９，２１（６）：１６５８—１６６３． ■ Ａｕｔｏｍａｔｉｏｎ＆Ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ ２ｏ１７，３２（３）