一种基于A*算法的路径平滑设计及仿真
摘 要
路径规划是自主式水下航行器（Autonomous Underwater vehicle，AUV）的重要研究领域之一。AUV在水下航行需要一条安全且平滑的路径，传统的A*算法要在栅格化的地图下进行，无法满足平滑的要求，因此提出一种两步路径规划方法，运用A*算法作预处理，通过添加约束点，利用支持向量机的非线性分类功能，在已有路径点的基础上产生一条平滑路径。实验表明这种方法能够有效地平滑路径，并在MOOS（Mission Oriented Operating Suite）平台下进行了AUV仿真实验。【关键词】路径规划 A*算法 支持向量机 MOOS平台
自主式水下航行器（Autonomous Underwater vehicle，AUV）作为一种新型的无人操作的海洋机器人，AUV在执行如海底考察、船体检测等各种水下任务中，一个关键的问题就是如何使AUV在工作中合理而安全地航行。路径规划算法有传统的人工势场法，静态网路中的A*算法等。人工势场法易陷入局部极值点的问题，而A*算法不存在局部极值问题，但A*算法需要在栅格化的地图上进行，往往无法生成平滑的路径，受到运用SVM进行路径规划的启发，本文利用A*算法作预处理，结合SVM进行路径平滑。最后通过实验验证了该方法的平滑效果，并在Linux系统下MOOS平台进行了AUV仿真实验。
1 结合A*和SVM
1.1 A*算法
A*算法一种启发式搜索算法，其估价函数式可表述为： （1）
式中，表示由起点经由当前节点n点到目标点的估计距离函数，表示从起点到n点的实际距离函数，表示从n点到目标点的估计距离。为了得到最优路径，必须使小于或等于n点到目标点的实际距离，这里的又称为启发函数，本文中启发函数采用当前节点到目标点的欧氏距离，即：
（2）
A*算法需要设置两个链表，open表和closed表，起点和需要遍历的点将放入open表中，而障碍物和已经遍历过的点加入closed表中，采用估价函数值最小的点作为扩展节点，并将此点记为其扩展节点的父节点，直至扩展至目标点，再通过反向寻找父节点直至最初的父节点（起点），这些点连接起来形成最后路径。
1.2 SVM算法
（1）SVM作为经典的线性二分类器，通过最大间隔（Maximum Margin）的思想来确定最优分界超平面。在二维情况下，最优分界超平面是一条分界线，假定训练样本，…，，，，其线性分类决策函数可表述为：
（3）
式中，表示拉格朗日乘子，s代表一系列支持向量，这些支持向量满足或。
（2）在实际情况中，存在线性不可分的情况，这个时候SVM通过选取合适的核函数，将训练数据映射到高维特征空间，转换为在高维空间求解超平面的问题，由于高斯函数的平滑特性，且在一般情况下都能取得比较好的分类效果，本文实验中选取径向基函数（Radial Basis Function，RBF）作为SVM的核函数。其表达式为：
（4）
σ代表高斯函数的宽度，此时SVM决策函数为：
（4）
1.3 结合算法
最近，由大阪大学的Jun Miura提出了一种新的路径规划方法，即用SVM进行路径规划，但是单纯的SVM路径规划并不能够保证路径正好通过起点和终点。SVM产生的分界线离两侧支持向量的距离为最大分隔距离的二分之一，利用这个特性，首先利用A*算法计算出一条待平滑路径，将此路径两侧的障碍物分别标记为+1或-1，并在A*路径的两侧选择一定的角度θs和步长ds，选取约束点，并依据之前路径将障碍物分成的正负两类，将两侧约束点标记为+1或-1，再运用SVM进行平滑。
1.4 MOOS平台
MOOS （Mission Oriented Operating Suite）是由美国麻省理工学院Paul Newman等研发的一套用于水下自主式航行器的开源系统，它能够实现AUV航行期间各进程之间的通信，基于MOOS系统可以进行第三方的开发和拓展，提供了AUV从任务规划到底层控制的仿真界面，本文将采用仿真的方式，设置AUV的参数，来实现AUV对平滑路径的航行仿真。
2 实验
本文的实验都在Linux系统下进行，实验首先将大尺度地图通过阈值化后形成二值地图，将二值地图转化为二值文件读入程序中。为使得AUV在航行过程中能够安全的绕过障碍物，实验对不可通行区域进行了适当的膨胀处理。
2.1 路径平滑实验
实验中采用点状障碍物，在栅格化的20×20的区域中，将AUV视为质点，设定起点S和终点E，取θs=π/3，ds=0.05，求解约束点，SVM核函数参数σ=1.5。图1显示了A*算法产生的预处理路径和经由SVM处理后的路径。由图可以看出，该方法实现了路径的平滑。
2.2 与其他平滑方法的比较
在对路径规划中，有很多对路径点进行平滑的操作方法，例如三次样条函数，贝塞尔曲线，B样条曲线等，这里在以上实验的数据环境下做对比实验，对B样条曲线，SVM各自的平滑效果进行比较。代表三次B样条函数的平滑路径，代表SVM的平滑路径。实验中B样条曲线采用非均匀B样条基，其中用来衡量平滑程度的Vs值的计算是将两条路径分别划分成等间隔的相同等份的线段，通过计算各段斜率的平均值来衡量平滑程度，可以看出Vs越小，平滑程度就越好。根据表1的数据表明SVM的Vs值最小，平滑效果最好，而且在路径长度上也最短，能够有效的降低AUV能源损耗。由图2的路径比较可以直观的看出，SVM在全局平滑程度上要优于其他两种平滑方法。
2.3 MOOS平台仿真实验
本文利用以上实验获得的平滑路径进行了仿真实验，设置AUV的底层参数，将路径点进行坐标转换，左侧栏中会显示当前MOOS系统AUV的实时信息，实验效果如图3，图中显示了AUV的模拟航行路径，经过平滑后的路径，有效的减少AUV的转弯次数，从而降低平滑前有可能不符合AUV的自身转弯半径造成路径跟踪失败的可能性。
3 结语
本文在基于栅格地图A*算法的基础上，采用了添加约束点的方式，将两种方法结合，优化核函数参数，设定SVM迭代次数及惩罚因子，利用SVM进行路径平滑，符合AUV自身的转弯半径，减少了AUV在航行中的转弯损耗，同时弥补了单纯的SVM路径规划在准确通过起止位置方面的缺陷，在最后的仿真实验中，体现了该方法的实用性，同时在与样条函数的平滑效果比较中，也显示了这一方法的优越性。
参考文献
[1]Stuart Russell，Peter Norvig.Artificial Intelligence A Modern Approach[M].Pearson Education，2010，95-101.
[2]J.Miura，Support Vector Path Planning[C].Proceedings of the 2006 IEEE/RSJ.International Conference on Intelligent Robots and Systems，2006，Beijing，China.
[3]张雅妮，高金源.一种基于改进A*算法的三维航迹规划方法[J].飞行力学，2008，（01）：48-51.
[4]崔建明，刘建明，廖周宇.基于SVM算法的文本分类技术研究[J].计算机仿真，2013，（02）：299-302.
[5]宋小杉，蒋晓瑜，罗建华等.基于类间距的径向基函数-支持向量机核参数评价方法分析[J].兵工学报，2012，33（2），203-208.
[6]赵前进，胡敏，檀结庆.基于局部梯度特征的自适应多结点样条图像插值[J].计算机研究与发展，2006，（09）：1537-1542.
[7]陈成，何玉庆，卜春光等.基于四阶贝塞尔曲线的无人车可行轨迹规划[J].自动化学报，2015，（03）：486-496.
[8]周明华，汪国昭.基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合[J].计算机研究与发展，2005，（01）：134-143.
作者单位
中国海洋大学信息科学与工程学院 山东省青岛市 266100
