水面无人艇(unmanned surface vehicle，USV) 和空中无人机、路面无人车、海底无人潜艇一样，属于智能机器人的一个分支[1-2]．USV起源应用于军事领域，而今同样广泛应用于诸如油气资源勘探、渔业资源勘探、内陆河流水质水文监测和水面巡航等民事领域．路径规划是USV实现自主导航的关键技术之一．根据对环境感知信息的掌握程度不同，路径规划可以分为环境信息已知的全局路径规划和环境信息完全未知或部分未知的局部路径规划[3]．常见的路径规划算法有人工势场法、粒子群算法、蚁群算法(ACO)、遗传算法(GA)、动态窗格法及快速匹配法等[4-7]．随着人工智能的深入研究和发展，各种新兴的智能算法和仿生算法为解决传统优化问题提供了全新的解决思路和有效可行的方法．细菌觅食优化算法(bacterial foraging optimization algorithm，BFO)作为仿生类群体智能算法的一种[8]，在路径规划领域得到了成功的应用．文献[9]将BFO的固定趋化步长改进为自适应调整的步长，固定迁移概率改进为自适应迁移概率，以获取更好的寻优精度及稳定性．实验表明：改进算法能实现USV在动态障碍物下的自主避碰．文献[10]利用Voronoi图理论生成候选子路径，并采用BFO求解最优路径．文献[11]以Sphere函数作为路径寻优的仿真测试环境，采用BFO算法驱动的搜索主体快速找到目标地点，验证了该方法优越的搜索效率和求解精度．模拟退火算法(simulated annealing algorithm，SAA)[12]是一种高效的启发式全局搜索算法，其通过概率判断跳出局部最优解，从而提高求解质量．文献[13]将遗传算法的“优胜劣汰”思想加入到SAA中，解决了不同环境下的路径规划问题．文献[14]提出一种混合了A*的SA算法求解全局路径规划问题，仿真结果表明：该算法增强了跳出局部最优陷进的能力，提高了算法所得解的质量．这里结合模拟退化算法高效的全局搜索能力，提出一种混合了模拟退火机制的BFO算法(SA-BFO)求解USV路径规划问题．将模拟退火机制引入到BFO算法的迁移操作中，计算更新前后的迁移个体的适值度，接受优化解的同时以一定概率接受恶化解，使BFO算法能更好地从局部极值中跳出，从而收敛至全局最优．基于USV的感知系统，在安全范围内识别如航行的船只、舰艇等可控性型动态障碍物和移动的水面漂浮物(浮木、残渣)等不可控型动态障碍物，根据本文算法拟定安全、高效的局部路径．1 环境建模基于栅格法的环境模型能够简单、高效地模拟USV的环境地图，且地图信息易于编辑，因此对USV在路径规划过程中会遇的静态障碍物和动态障碍物进行网格化处理．在n×n的栅格环境中，栅格序号i和USV坐标(x,y)的关系为x=mod(i-1,n)+0.5;y=n+0.5-ceil(i/n), (1)式中mod和ceil分别为求余运算和向上取整运算．如图1所示，图中：黑色栅格表示静态障碍物；白色栅格表示可行路径；绿色栅格表示动态障碍物，绿色栅格存储了障碍物和其移动路径信息．USV在栅格地图的移动距离可表示为Ddis=1       (xi=xi+1或yi=yi+1); 2     (其他). (2)10.13245/j.hust.220313.F001图1栅格地图中的各类障碍物根据动态障碍物运动特性对其进行分类，USV可能会遇到机动型船只、舰艇等动态障碍物，也可能会遇到诸如悬浮的木头、冰块等移动缓慢的非机动型的动态障碍物．USV可依靠艇上装备的各类传感器采集到一定范围内的各类动态障碍物的位置、速度信息．2 模拟退火-细菌觅食算法设计自然法则倾向于保留觅食能力强的物种，淘汰觅食能力弱的物种．BFO算法就是模拟大肠杆菌在觅食行为过程中所体现出来的生理行为，进行建模迭代产生最优解的一种仿生搜索算法．BFO算法是由趋化、繁殖和迁移三个算子构成[15]．三个算子形成一个三层嵌套循环，最内层是趋化算子，中间层是繁殖算子，最外层是迁移算子．2.1　适值函数USV的路径是由有序的栅格序号组成的，在栅格地图中，每条路径所包含的节点数量是不一定相等的，因此路径长度也是长度不一．其中，一条路径代表一个细菌．适值函数是个体对于其生存环境的适应程度的数学模型，适值度是评价个体质量的标准．在栅格环境中，定义规划路径长度的倒数为适值度．适值函数为K=1/∑i=sedi,i+1，(3)式中：s为路径的起点；e为路径的终点；di,i+1为相邻两点间的欧氏距离．2.2　趋化算子趋化算子是模拟细菌觅食行为的主要操作，该算子是通过细菌的翻转和游动使细菌向营养丰富的地方集中．图2所示为细菌趋化示意，图中：Path 1为进行趋化的细菌；Path X为种群中随机选取的一个细菌；Path 1'为翻转后的细菌；S为趋势起点；G为趋势终点．这里把路径交叉使路径长度缩短的动作视为细菌觅食的行为．10.13245/j.hust.220313.F002图2细菌趋化示意图2.3　复制算子复制算子遵循了自然界优胜劣汰，适者生存的原则．在细菌完成趋化周期之后，复制操作将保留并复制菌群中适值度排名前50%的细菌．该算子通过群体多样性的收缩，加快了算法的收敛速度．2.4　迁移算子迁移算子模拟了细菌随着环境变化导致位置变化的行为．该算子不仅能够增加算法种群多样性，而且能够提升BFO算法全局寻优能力．提出的SA-BFO算法在迁移算子中混合了模拟退火机制．结合SA算法容易跳出局部最优的特点，进一步提升算法在解空间中的全局寻优能力．迁移算子描述如下：a．将复制操作之后的细菌适值度升序排列，并设置初始温度T，温度迭代次数L；b．选择适值度排序前βM (0β1)个细菌进行迁移操作，并计算Knew，M为细菌总数；c．判断Knew与Kglobal的大小，并以Metropolis准则接受新解；d．温度T以一定速率降低，下降速率为 　 T=aT(0a1)；e．判断温度迭代是否完毕，若迭代完成则执 行步骤f，反之执行步骤b~d；f．输出当前解为最优解．3 路径规划仿真SA-BFO优化算法测试于Inter(R) Core(TM) i5-7200 CPU @2.50Hz 2.71 GHz，内存8.00 GiB的64位操作系统．3.1　SA-BFO算法参数设定在实验中，选择传统BFO，ACO，GA作为对比算法．所有的算法均采用相同时间作为终止条件，即0.1Q(s)，其中Q=400为栅格单元的总个数．此外，采用正交实验确定SA-BFO算法的各参数对模型输出影响，进而获得最优参数组合．SA-BFO的主要参数包含种群数量M、趋化次数Nc、复制次数Nre、迁移次数Ned、温度迭代次数L．采用5因素4水平正交表进行正交实验．表1为各参数水平列表，表2为正交数组和其对应的20次独立实验得到的路径长度的平均值αAPL．αAPL及其信噪比ρSNR如表3所示，其中ρSNR=-10lg αAPL2．SA-BFO算法的主要参数敏感性分析结果如表4所示．10.13245/j.hust.220313.T001表1参数及其水平列表参数水平1234M40506070Nc3456Nre1234Ned1234L234510.13245/j.hust.220313.T002表2L16(45)正交表实验次数参数水平αAPLMNcNreNedL11111119.5421222220.0831333319.3541444419.8852123418.9762214319.3572341219.0182432119.4093134219.89103243118.95113312419.49123421318.97134142318.97144231419.30154324119.37164413219.3510.13245/j.hust.220313.T003表3规划路径平均值及其信噪比统计表参数参数水平MNcNreNedLαAPL119.7119.3419.4319.2119.32219.1819.4219.3519.4919.58319.3319.3019.4919.1619.16419.2519.4019.2019.6219.41ρSNR1-25.89-25.73-25.77-25.67-25.722-25.66-25.77-25.73-25.80-25.843-25.73-25.71-25.80-25.65-25.654-25.69-25.76-25.67-25.85-25.7610.13245/j.hust.220313.T004表4SA-BFO各参数的敏感性分析表参数水平MNcNreNedL119.7119.3419.4319.2119.32219.1819.4219.3519.4919.58319.3319.3019.4919.1619.16419.2519.4019.2019.6219.41极差0.530.120.290.460.42排序15423由参数敏感性分析结果可知：各参数对系统输出的影响依次为MNedLNreNc．在栅格规模为 Q=400的环境中，SA-BFO算法的最优参数设置为M=50，Nc=5，Nre=4，Ned=3，L=4．3.2　全局路径规划仿真USV全局路径规划实验采用的栅格地图的规模为20×20，其最优路径长度为18.9．在全局路径规划实验中，统计每个算法独立运算20次的结果．其中：LMin为最短路径；LMax为最长路径；αAPL为平均路径；θPOS为算法搜寻最优解的概率，实验结果如表5所示．图3给出了在相同终止条件下，4种算法收敛至最优路径的收敛曲线．10.13245/j.hust.220313.T005表5全局路径规划数据统计表算法LMinLMaxαAPLθPOS/%GA18.9019.1419.0440ACO18.9019.4919.0640BFO18.9024.9020.0120SA-BFO18.9019.1418.958010.13245/j.hust.220313.F003图3算法的收敛曲线对比图3.3　局部路径规划仿真局部路径规划能够帮助USV实现在环境部分未知或者完全未知的情况下的路径规划任务．USV在航行过程中，与他船或者非机动型动态障碍物可能会遇的情况有对遇、交叉、追越．根据不同的会遇动态障碍物，对以上三种情况进行仿真．实验均假设为在能见度良好、无风浪、船舶互见的环境中进行．当USV与机动型障碍物构成对遇局面时，各船遵循COLREGS规则进行避让动作，即两船应向右转向，从他船的左舷驶过．当USV与机动型障碍物构成追越局面时，USV遵循COLREGS规则进行追越动作，追越行动要早、大、宽、清，应保持两船以较大的横距驶过．当USV与机动型障碍物构成交叉局面时，各船遵循COLREGS规则进行避让．当两艘机动船交叉相遇致有构成碰撞危险时，有他船在本船右舷的船舶应给他船让路，如果当时环境许可，还应避免横越他船的前方．以上3种会遇情况的避障策略，如图4所示．USV与非机动型动态障碍物同样构成以上3种会遇情况．由于USV的强机动型，在面对非机动型动态障碍物时，USV在避障的过程中承担让路责任．三种情况的避障策略，如图5所示．10.13245/j.hust.220313.F004图4机动型动态障碍物避障策略10.13245/j.hust.220313.F005图5非机动型动态障碍物避障策略USV在公共水域中必然会涉及到多船避碰的问题．COLREGS规则虽然只解决了两船会遇的问题，但任何多于两船相遇的问题都被分解成一系列两船相遇的问题．为验证本文方法的可行性，假设在30×30的栅格环境中，存在机动型动态障碍物MDO1，MDO2和非机动型障碍物NMDO1．USV 将从起点依照全局规划路径开始航行，途中将对遇MDO1、追越MDO2和交叉NMDO1，最终复航至全局规划路径的目标终点．USV规划的航行路径如图6中红色轨迹所示；黄色路径为初始规划的全局路径；t1，t2，t3为USV检测到动态障碍物的初始时刻．当船载雷达检测到动态障碍物之后，USV须根据障碍物的位置、速度信息快速地规划出避障路径．SA-BFO算法在规划局部路径时，以时间为终止条件．算法在不同时间内均独立运行20次，统计数据如表6所示，其中：RMin为初始点至复航点的最短路径；RMax为初始点至复航点的最长路径；θPOS为算法搜索最优解的概率；栅格总量Q=30×30．10.13245/j.hust.220313.F006图6USV会遇动态障碍物路径规划图10.13245/j.hust.220313.T006表6全局路径规划数据统计表障碍物0.020×Q0.010×Q0.005×Q0.002×QMDO1RMin4.834.834.834.83RMax4.834.834.835.41θPOS/%10010010095MDO2RMin4.834.834.834.83RMax4.834.834.835.41θPOS/%10010010095NMDO1RMin6.246.246.246.24RMax6.246.246.246.24θPOS/%1001001001003.4　仿真分析上述仿真实验结果表明，提出的SA-BFO 算法具备有效性、可行性．在全局路径规划方面，通过表5的数据可知：所有算法在20×20规模的栅格环境中，都能找到最优路径18.9，但是算法稳定性和准确性均不一样．SA-BFO算法的寻优的最差解最小，平均路径长度最小，说明该算法的稳定性最优．GA和ACO虽然在稳定性方面和所提算法相差无几，但在求解最优路径的概率上，要远落后于SA-BFO，这说明SA-BFO算法的准确性要优于其他．文中传统BFO算法优势在于算法收敛速度快，但是算法的稳定性和准确性均不理想．提出的SA-BFO算法的收敛速度较对比算法更快．在同样的栅格环境中，求解最优值的概率高达80%．局部路径规划方面，根据不同动态障碍物类型，结合COLREGS规则设计了USV避障方法，能够安全、有效地避开各类动态障碍物．在USV的局部路径规划仿真实验中，如表6所列数据，在不同的会遇局面，SA-BFO算法在20，10和5 s内均能做到100%规划出最优的避让路径，在2 s内也可做出高达95%和100%的高效避障动作．综上所述：本研究验证了在相同终止条件下，即使递减运算时间，本文方法依然能够高效、准确地规划出避障路径．仿真结果表明：SA-BFO算法寻优精度高、收敛速度快，能使USV做出迅速、合理的避障动作．在未来工作中，将基于BFO算法对USV的能耗、时间、路径等多目标的优化问题进行深入研究．