基于改进A*算法的人工智能鱼路径规划研究

袁红春，毛 瑞，杨蒙召

(上海海洋大学信息学院， 上海 201306)

人工智能技术作为一个热门领域，在医疗和农业等各个领域都有着重大影响[1-3]。人工智能中每个实体都具有一定的高级自主行为，如何将物体智能化是该领域的重要研究方向之一。路径规划是构建人工智能鱼不可或缺的环节，是将人工鱼智能化最有力的保证[4-5]。因此，有效的路径优化算法在构建人工智能鱼的过程中具有重要的实际意义。

随着人工智能领域的兴起，如何自主高效地进行路径寻优成为一个重要问题。近年来，各种智能算法的应用都获得了比较理想的结果。宋建辉等[6]利用人工势场法实现移动机器人的路径规划；张航等[7]提出一种基于量子行为粒子群优化算法(QPSO)的飞行器三维路径规划；Luitpold 等[8]提出了一种具有时间约束的协调目标分配和无人机路径规划的算法；朱大奇等[9]针对水下机器人(AUV)的路径规划问题给出了一种基于生物启发模型的三维路径规划和安全避障算法。A*(A-Star)算法由Hart PE等提出[10]，其利用启发函数进行路径搜索的方法获得了广泛的应用[11-13]。

本研究针对鱼类检索路径时的回退现象，将传统A*算法中的OPEN列表进行改进，减少了遍历OPEN列表时的代价；同时，为获取更优的路径，利用碰撞检测算法优化生成路径。

1 A*算法概述

A*算法属于启发式搜索算法，搜索路径由评价函数的返回值作为搜索的成本执行。其估价函数的公式[14]为：

F(ni)=G(ni)+H(ni)

(1)

式中：F(ni)表示当前节点的估价函数，即从初始节点Start开始，达到当前节点后再由当前节点前往终止节点Goal这一段路径的预估；G(ni)表示已花费的代价，其代表从初始节点Start到达当前节点这一段路径所消耗的代价；H(ni)为预估的代价，用于估算从当前节点到达终止节点Goal这一段路径可能消耗的代价。

A*算法的效率与准确度是由函数H(ni)决定的。H(ni)对路径的预估主要来源于其距离与单位距离内所花费的代价δ的乘积。根据距离公式得到H(ni)的预估方式[15]有以下3种：

1)曼哈顿距离预估

曼哈顿距离是坐标系中两点之间坐标系的投影值的总和，其预估公式为：

hM(n)=δ(|xGoal-xn|+|yGoal-yn|+|ZGoal-zn|)

(2)

2)切比雪夫距离预估

切比雪夫距离又称为棋盘距离，其预估公式为：

hc(n)=δmax(|xGoal-xn|,|yGoal-yn|,|zGoal-zn、)

(3)

3)欧几里得距离预估

欧几里得距离指在坐标系的两点直线距离，其预估公式为：

(4)

式中：xn、yn、zn为所求点的三维坐标；xGoal、yGoal、zGoal为目标点的三维坐标；δ为单位距离所花费的代价。

如图1所示，将起始节点Start放入OPEN列表中，寻找OPEN列表中F值最小的节点i作为当前节点并判断是否为终止节点Goal。若不是，则将i移入CLOSE列表并计算节点i的邻域Ni中各节点ni的Flatest值。判断ni是否属于OPEN列表或CLOSE列表：如果ni在OPEN列表中比较Flatest和原F的值，取最小者作为新的F值并重新设置父节点；如果ni属于CLOSE列表则舍弃该节点并选择Ni内其他节点进行判断；如果ni不属于OPEN列表且不属于CLOSE列表，将Flatest设置为F值，并设置i为其父节点，将ni移至OPEN列表中。按此循环不断查找OPEN列表，直到找到终止节点Goal，使用回溯法生成最优路径。

图1 传统A*算法流程图

A*算法中，在每次对OPEN列表的节点选取时，要重新比较所有表内F值的大小，增大了算法的计算量。由于OPEN列表节点选取的不确定性，可能导致在搜索路径时的迂回现象。同时，每次A*算法进行搜索路径时，均为选择相邻节点的局部路径，可能使寻找出的路径并非是其最优路径。

2 改进的A*算法

传统A*算法在OPEN列表处理上不断将当前节点的相邻节点存放至OPEN列表中，这会造成搜索路径的迂回。针对鱼类运动路径的仿真，将OPEN列表的处理方法进行改进。每次在选取一个节点后，将OPEN列表进行清空操作。在寻找当前节点i的相邻节点时，将相邻节点标记为OLD。如果相邻节点为OLD，则略过该点。这样使得每次在OPEN列表进行选择时，选择的节点为当前节点的下一节点，防止路径的回退现象。并且，该做法可限制载入OPEN列表的节点数量，列表内的节点F值逐级递减，减少了算法的计算量，提高算法的执行效率。同时使得CLOSE列表的载入节点在虚拟海洋环境中始终是相关节点，从而确保了鱼类运动行径的平滑性。

在传统的A*算法中，由于邻域阈值的影响，在选取邻域节点过程中有约束，始终无法选取出最优路径。为了减少阈值约束的影响，在搜索路径结束后使用碰撞检测算法对路径的节点进行筛选，以达到优化路径的目的。

碰撞检测是在人工智能领域中使用的一项重要技术，具有快速、准确等特性。目前的碰撞检测主要为基于包围盒的碰撞技术。在这里，采用基于AABB碰撞检测技术进行路径的处理[16-17]。该技术将物体放入三维坐标中，依据其最大值和最小值进行计算。物体的包围盒可表示为：

R={(X,Y,Z)|Sx≤x≤1x,Sy≤y≤1y,Sz≤z≤lz}

(5)

式中:Sx,1x、Sy、1y、Sz、lz分别表示为包围盒在不同坐标轴上最小值、最大值的映射。

AABB碰撞检测算法如图2所示。

图2 AABB碰撞检测算法

该算法的中心思想为检测2个包围盒在不同的坐标轴上的映射是否相交。记物体A的包围盒最小顶点元素和最大顶点元素分别为(Axmin,Aymin,Azmin)和(Axmax,Aymax,Azmax)；物体B的包围盒最小顶点元素和最大顶点元素分别为(Bxmin,Bymin,Bzmin)和(Axmax,Aymax,Azmax)。图2为使用AABB碰撞检测算法检测AB两物体是否碰撞流程图。由图2可知，AABB碰撞检测算法分别对x轴、y轴、z轴进行碰撞检测，最多只需6次对比即可判断AB两物体是否碰撞。

如图3所示，在OPEN列表寻找到具有最小F值得节点i后实行清空OPEN列表操作。同时在寻找当前节点i的相邻节点时，将相邻节点标记为OLD，防止路径的回退现象。同时，针对传统A*算法生成的路径，使用碰撞检测技术进行优化。

图3 改进的A*算法流程图

将生成的路径节点进行1～n的编号，从1和n两个节点出发，遍历所有的节点间构建的路径。对生成的路径进行碰撞检测。如果与障碍物等发生碰撞，则不做处理，否则删除未发生碰撞的路径中节点，建立新路径，从而达到路径优化的目的。

3 试验结果

3.1 试验平台

试验硬件环境的CPU为AMD Ryzen Threadripper 1950X 16-Core Processor 3.40 GHz，具有32.0 GB RAM，GPU为NVIDIA GeForce 1080Ti。基于Windows 10操作系统，仿真软件为Matlab 2017a、3ds Max 2017和Unity3D。

3.2 鱼类仿真建模

在3ds Max中进行鱼类的仿真建模[18-19]，采用弹簧—阻尼模型[20]进行鱼类构建。首先使用3ds Max建立鱼体的几何网格模型，采用建模函数对曲面上的顶点序列进行定义的方法来精确描述控制网点因子；其次采用曲面控制网点位置坐标的方式进行实时绘制，以形成离散的网格模型，并可用其“包装”生物力学模型。构建后发布并导入Unity3D中。

图4为3ds Max生成初步鱼体网格模型图。首先将需要建模鱼的图片导入至3ds Max中，使用曲面建模方法进行构建，从而在Front视图中建立模型。对图片进行描点并转化成可编辑的多边形，通过相应的拖点来制作鱼的外形。然后继续进行横向拖点操作，以便产生新的顶点和表面，通过拉伸表面可以生成胸鳍、腹鳍等更多细节的鱼体形状。鱼眼的制作通过对鱼头的裂顶点、对齐及挤压形成，从而生成如图5(a)所示的人工鱼几何网格模型。最后，在Left和Top视图中切换制作立体部分的结构并在达到基本的构线结构之后，使用“涡轮平滑”修改器进行模型的平滑处理，初步完成如图5(b)所示的几何鱼体模型。

图4 3ds Max生成初步鱼体网格模型流程

图5 人工智能鱼仿真模型

3.3 改进A*算法仿真试验

在Matlab R2017a中进行仿真试验。如图6所示，在Matlab中绘制一幅三维模拟海底图。该海底图中，x、y轴构成面积大小为21 km×21 km的海底，x、y、z轴的单位均为千米(km)，是由一个随机数组组成，代表深海中高度不同的丘陵。

如图7所示，设置人工鱼在三维海底的起始点为(15，0，1)，终点为(10，21，1)。将人工鱼用质点来表示，将由改进A*算法得到的路径节点用空心圆点代替，得到改进的A*算法所寻的路径图。

图6 三维海底图

在模拟的三维海底中，设置人工鱼的不同起始节点和终止节点，进行多组试验。改进A*算法与传统A*算法的结果对比见表1。

图7 试验结果

表1 试验结果

由表1可知，由于对OPEN列表节点选取的改进，改进后的A*算法运行消耗时间比传统的A*算法要小，但因为进行碰撞检测需要消耗时间，所以在运算时间上并没有太大的提升。在最终生成的路径上，平均优化的距离约占原距离的5%，使得人工鱼的路径更加高效。

将改进的A*算法应用在人工鱼的建模当中，借助Unity3D技术，将海洋鱼类与改进的A*算法相结合。首先需要仿真模拟出海底环境的基本场景，模拟出来的仿真场景俯视图如图8所示。地图的大小为500×500,分为海藻密集区域和深海丘陵区域。采用Unity3D自带的Terrian系统搭建丘陵地貌，海底的植物均由3ds Max进行高密度的静态建模，并且使用贴图实现丘陵的各种颜色。为了模拟海底自然光线和实时计算出光照产生的阴影，采用静态的天空盒与一个平行的光源进行光源设置。最后，通过Shader材质实现水下波纹的逼真效果。

图8 场景俯视图

智能鱼的模型导入后，将改进的A*算法寻路模块通过A-star脚本和FishNewMove脚本挂载至智能鱼的模型上，并以第三人称视角展现虚拟海洋环境图。如图9所示，智能鱼从t1时刻开始，在遇到海草等障碍物时，可以沿着改进A*算法规划好的路径游走，从而达到t4时刻避障的效果。

图9 鱼类避障图

4 讨论

4.1 改进A*算法所带来的影响及其优化

传统的A*算法由于在OPEN列表的处理上，不断将当前节点的相邻节点存放至OPEN列表中，造成搜索路径的迂回。本研究在每次选取一个节点后，将OPEN列表进行清空操作。该做法减少了算法的计算量，提高算法的执行效率。同时，传统A*算法由于邻域阈值大小选取的影响，在选取邻域节点过程中具有约束，始终无法选取出最优路径。本研究在A*算法的基础上使用碰撞检测的原理进行路径节点的筛选，有效解决了阈值约束的影响，确保了鱼类运动行径的平滑性。试验结果表明，在运算时间相当的情况下，所寻的路径减少了5%，使得改进后的A*算法相较于传统模型具有全面的提升。

4.2 人工鱼的智能化研究对比

在传统的对人工鱼智能研究上，大多数学者都选择对人工鱼自身或者鱼群进行智能化。人工鱼自身方面，孟宪宇等[21-22]采用模糊神经网络和模糊推理机制分别实现人工鱼的味觉系统和嗅觉感知；尹璐[23]通过使用BP神经网络、自组织竞争型神经网络和SOM神经网络对人工鱼的感知、行为和意图行为进行优化。袁红春等[24-25]通过对行为决策方面的研究实现了人工鱼群行为的改进。相较于传统的鱼类智能研究，本研究重点在于真实环境的交互上，有效解决了鱼类游泳过程中，鱼类游泳路径的随机性。但是本文对鱼群游泳时的行为缺乏研究，下一步将继续研究鱼群游泳时的运动规律，进一步完善鱼类行为的智能化。

5 结论

针对三维虚拟海洋环境中人工智能鱼运动路径仿真低效的问题，提出一种改进的A*算法来进行人工鱼路径寻优。该算法在寻找路径过程中对OPEN列表进行节点清空操作，并利用碰撞检测处理A*算法所得到的路径。试验证明，改进后的算法解决了A*算法的回退现象，并且更加高效，寻找的路径更优。该算法能够有效地为人工智能鱼进行路径规划，为鱼类行为探索提供一种有效参考。

□