范士波 李毅
（上海宽带技术及应用工程研究中心孪生推演与智能决策实验室，上海，200336）
自主式水下机器人（Autonomous Underwater Vehicle，AUV)是多学科技术的集成体，涉及到计算机技术、自动控制、流体力学、人工智能、水声学和网络通信等领域。AUV搭载了多种传感设备和测量装置，具有自主导航和定位能力、任务规划、信息处理和机械手作业等功能。因此，AUV不仅能够完成海洋资源勘探、海底管道检测与维修、海洋生态环境调查研究等任务，还能够胜任一些特殊的军事使命，如援潜救生、扫雷等[1]。其中，路径规划是AUV智能控制的关键技术之一，在一定程度上直接决定着AUV智能水平的高低[2-3]。
AUV在海洋环境航行时，需要获得所处海域的环境信息。通常AUV在小范围的航行都是通过搭载的声纳设备来获得相应的数据和信息。但是，当AUV在大范围海洋环境航行时，借助传感设备的方法已经不能满足航行的需要，而电子海图恰好提供了详细而准确的海洋环境信息，因此，利用预先存储于电子海图的海洋环境信息进行建模并完成路径规划是AUV发展的必然趋势[4]。
根据对环境信息依赖程度的不同，AUV路径规划可分为全局路径规划和局部路径规划。其中，全局路径规划包括环境建模和路径搜索策略两个子问题，主要是根据先验知识（如海图等）规划出一条从始发点到目标点的无避碰路径；
局部路径规划又称动态避碰规划，通过搭载的传感器（如声纳、摄像机等）在线地对机器人作业环境进行探测，利用实时获取的障碍物位置、形状和尺寸等信息，在尽可能短的时间内避开未知障碍物的过程[5-8]。
目前，全局路径环境建模的主要方法有：可视图法（V-Graph）、自由空间法（Free Space Approach）、栅格法（Grids）等[9-10]，路径搜索策略主要有：
A*算法、D*最优算法、遗传算法、蚁群算法、神经网络等[11-13]；
局部路径规划的主要方法包括：人工势场法、遗传算法、模糊逻辑算法、强化学习等人工智能算法[14-16]。
受自然界中蚂蚁觅食行为的启示，本文研究了一种基于海图信息的AUV蚁群路径规划算法，提出利用电子海图信息进行环境建模的方法，同时，针对蚁群规划路径不平滑问题，设计了切割算子和插点算子，最后，在Windows平台下，通过VC++仿真软件，验证了算法的可行性。
由于海底地形地貌的复杂性和水下存在的一些未知障碍物，对AUV的安全构成了潜在的威胁，为了实时感知这些信息，一般在AUV本体上安装了多波束前视声呐传感器，通过接口反馈的探测信息为AUV路径规划提供依据。
本文的海洋环境建模思路是：把某一海域建立成二维的离散空间模型，并以矩阵栅格为组织形式，栅格阵左上角为坐标点，由此可抽象出一个二维坐标系，并约定水平向右为X轴递增方向，竖直向下为Y轴递增方向。用集合表示栅格阵中所有的栅格，则对任意栅格根据上述设定，都有唯一的坐标（x，y）与之相对应；
记为障碍栅格集，表示此区域全部或部分被水面岛礁覆盖，是不可行区域；
记为可行栅格集，表示此区域是自由可行的区域。通过对水面岛礁或障碍物的轮廓按一定的规则进行扩充，并在扩充的轮廓上适当选择一些栅格点称作绕行点。对于两栅格点，若由决定的线段所经过的任意栅格点，都有则称是通透的，记作
图1所示为栅格模型示意图，其中，空白栅格点是自由可行区域，是不可行区域，栅格点是AUV的起始点，是目标点，是绕行点，点和点是通透的，和是不通透的。基于上述通透性检查可以建立相应栅格模型的可视图模型，如图2所示。
图1 栅格模型示意图
图2 可视图示意图
海图中每个地方都有一定的属性，例如，划定一个区域可以判断出该区域是陆地还是海洋。根据AUV实际工作的需要，规定陆地、岛屿、半岛、各类滩涂、碍航物等为AUV不可通过的区域，以及把影响AUV航行安全的部分限制区域作为障碍区域，其他区域为自由区域。
本文将海图信息栅格化，栅格分辨率为18""，然后，取范围18""×18""的正方形区域将其视为一个栅格节点。每个栅格节点与海图的相应区域做相交检测，得到相交区域具有的属性编码。不同的属性都有各自的编码，根据相应的编码对应shapefile电子海图数据字典的相应属性，可以确定该栅格为障碍区域还是自由区域，最后将转换好的栅格文件作为AUV进行全局路径规划的海图信息文件。图3是某海域电子海图，图4为根据要求栅格化的海图信息。
图3 某海域电子海图
图4 某海域海图栅格化
本文主要对AUV在某一特定深度进行路径规划研究，并且不考虑海流等的影响。因此，AUV前视声纳探测模型的相关变量的设置均基于二维空间来考虑。
经研究发现：蚂蚁在觅食过程中能够在所经过的路径上留下一种称为信息素的物质，而且能够感知这种物质的存在及其强度，并以此指引着自己的前进方向，它们倾向于朝着该物质强度高的方向移动。因此，大量蚂蚁集体觅食的行为便表现出一种信息正反馈现象：某一路径越短，该路径上走过的蚂蚁就越多，则留下的信息素强度就越大，后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息交流来选择最短路径并达到搜索食物的目的。蚁群算法就是模拟蚁群这一觅食行为的优化算法。
2.1 符号描述与定义
2.2 状态转移规则
2.3 蚁群信息素更新规则
1）全局信息素更新规则。
全局信息素更新规则如式（2）计算。
2）精英信息素强化更新。
为了引导蚁群在更优路径上寻食，本文对每代最优路径的信息素进行了强化更新，主要分两步完成。
步骤1：找出本次迭代过程中蚁群中路径最优的蚂蚁（若有多只，只算其中的一只），设为按式（3）对信息素进行强化更新。
步骤2：若本代蚁群中路径最优蚂蚁的代价比上代蚁群中路径最优蚂蚁的代价大，则不做本次局部更新，否则设本代蚁群中路径最优蚂蚁为上代为按式（4）进行信息素强化更新。
3）信息素更新后的处理。
信息素更新后，再按式（5）进行处理。
2.4 蚁群全局路径规划的步骤
利用上述算法所得的规划结果是构成路径点的序列，路径点的连线为折线，必须加以平滑来提高AUV的稳定性，故本文开发了两个简单的算子对规划出来的路径进行了平滑。
3.1 切割算子
图5 正向切割示意图
图6 反向切割示意图
3.2 插点算子
图7 插点算子示意图
本文在Windows平台下，设置了1000m×1000m的矩形海域仿真环境。当AUV起点S经度为纬度为终点G经度为纬度为时，采用蚁群算法，初始化种群选用100个个体，终止条件为迭代800代，交叉概率为0.8，变异概率为0.4，假设海流较弱，不考虑海流因素，其规划结果如图8（a）所示；
采用算法，和图8（a）中有相同的起点和终点坐标，以路径最短为启发信息规划出结果，如图8（b）所示。
图8 全局路径规划试验1
图9 全局路径规划试验2
在海流较弱、无需考虑海流因素影响的情况下，对两种全局路径规划方法的结果进行比较，具体见表1。
表1 试验结果比较
当海洋环境中海流较强，需要考虑海流因素影响时，采用蚁群算法的规划结果如图10所示。其中，箭头表示该区域海流流向，箭头分布密度表示海流的大小。
图10 海流较强时的路径规划结果
由试验结果可知，在AUV自身消耗能量一定，AUV尽量沿海流方向航行，尽可能利用海流的能量的情况下，其航行距离最远。
本文以电子海图信息为基础对AUV进行环境建模，解决了对大范围海洋环境建模的问题；
采用蚁群算法作为搜索策略对机器人进行全局路径规划；
在基于栅格法表示的路径规划中，引入通透性的概念，根据实际问题，对信息素不仅进行了全局更新，而且对每代中的最优代价路径进行了强化，从而使蚁群算法很快收敛到最优路径；
针对规划路径不平滑的问题，本文设计了两个算子（切割算子和插点算子）进行解决，同时使路径的长度更短；
最后，在Windows平台下，通过VC++仿真软件验证了本文设计的算法的有效性和实用性。