﻿ 基于支持向量机的局部路径规划算法
«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2019, Vol. 40 Issue (2): 323-330  DOI: 10.11990/jheu.201708085 0

### 引用本文

ZHUGE Chengchen, XU Jinsong, TANG Zhenmin. A local path planning method based on support vector machine[J]. Journal of Harbin Engineering University, 2019, 40(2), 323-330. DOI: 10.11990/jheu.201708085.

### 文章历史

1. 南京理工大学 计算机科学与技术学院, 江苏 南京 210094;
2. 悉尼科技大学 大数据中心, 新南威尔士 悉尼 2007

A local path planning method based on support vector machine
ZHUGE Chengchen 1, XU Jinsong 2, TANG Zhenmin 1
1. School of Computer Science and Engineering Nanjing University of Science and Technology, Nanjing 210094, China;
2. School of Electrical and Data Engineering Sydney University of Technology, Sydney 2007, Australia
Abstract: To solve the path-planning problem of unmanned ground vehicles (UGV) in an unstructured road environment, a local path-planning method based on multiple Lidar and support vector machine (SVM) is proposed in this paper. First, a safe path is extracted from the grid map by nonlinear SVM. A path described with a cubic polynomial can be extracted by using RANSAC algorithm on the multi-frame projection data and the path can be used to calculate the road curvature. Then, the control points are selected by considering the state of the UGV and the final path is generated by using Bezier curve fitting. The proposed method can effectively extract the path from the grid map when the performance of the vision-based road detection algorithms is limited by poor lighting and weather. Finally, the validity and correctness of the proposed algorithm is verified on a real vehicle.
Keywords: unstructured road    unmanned ground vehicle    path-planning    support vector machine    RANSAC algorithm    load path    grid map

1 基于SVM的路径提取

SVM[11]是一种二类分类模型，其最优分类超平面能够使得类间隔最大化。如图 1中的栅格地图所示，道路两侧的障碍物可以视作两类目标，以此作为训练样本进行训练得到的SVM分类超平面可以使得两侧障碍物具有最大间隔。分类超平面在二维栅格地图上的投影轨迹不仅平滑而且能够确保远离障碍物，因此可以作为UGV的可行驶路径。

 $K({{\mathit{\boldsymbol{p}}}_{i}}, {{\mathit{\boldsymbol{p}}}_{j}})=\text{exp}(-{{\left\| \text{ }{{\mathit{\boldsymbol{p}}}_{i}}-{{\mathit{\boldsymbol{p}}}_{j}} \right\|}^{2}}/{{\delta }^{2}})$ (1)

 $f\left( {{\mathit{\boldsymbol{p}}}_{j}} \right)=\sum\limits_{i=1}^{n}{{{\alpha }_{i}}{{\gamma }_{i}}K({{\mathit{\boldsymbol{p}}}_{i}}, {{\mathit{\boldsymbol{p}}}_{j}})+b=0~}$ (2)

 $D({{\mathit{\boldsymbol{p}}}_{i}})=\left| \mathit{\boldsymbol{w}}\cdot {{\mathit{\boldsymbol{p}}}_{i}}+b \right|/\left\| \mathit{\boldsymbol{w}} \right\|$ (3)
 $D({\mathit{\boldsymbol{p}}_i}) < {\mathit{w}_{{\rm{car}}}}/2 + {d_{{\rm{safe}}}}$ (4)

2 路径规划算法 2.1 栅格地图预处理与分类

 Download: 图 4 路径规划算法流程 Fig. 4 Flow diagram of the path planning algorithm

1) 对原始栅格使用大小为一个车宽的窗口进行膨胀、腐蚀处理(见图 5(b))。将栅格数据作为二值图像，利用链码跟踪[15]算法提取障碍物的轮廓，每一个闭合轮廓被标记为一个障碍物目标(见图 5(c))。定义pij=(xij, yij)为第i个障碍物的第j个轮廓点坐标，pci=(xci, yci)为第i个障碍物的质心坐标，(pij, γi)为本文所使用的训练样本；

2) 将Nobs个障碍物转换到极坐标系下进行分割，将所有的障碍物分成两类，记分割线左侧的障碍物类别标签记为γi=-1，右侧为γi=+1。接着将所有的训练样本进行训练得到一组wb。如图 5(c)中有4个障碍物，每次分割成两组，因此有5种分割方式。对Nobs+1种分割依次训练之后得到Nobs+1组wb以及对应的超平面。最后，保留其中类间隔最大的一组wb，其所构成的超平面Hmax则为当前所求的安全路径(见图 5(d))。

2.2 基于RANSAC的路径提取

 $f\left( y \right) = a + by + c{y^2} + d{y^3}$ (5)

 $k = \left| {f{{\left( y \right)}^{\prime \prime }}} \right|/{\left( {1 + f{{\left( y \right)}^\prime }^2} \right)^{3/2}}$ (6)
 $\rho = {k^{ - 1}}$ (7)

1) 在t时刻，首先将全局坐标系下的多帧SVM超平面轨迹点转换到局部车体坐标系下，然后合并t时刻求得的SVM超平面轨迹Ht，得到局部坐标系下的点集local_points。接着将local_points中位于车体前方的点qi转换到全局坐标系下，并保存在点集global_points中为下一帧处理做准备。

2) 根据式(5)可知，本文使用RANSAC算法需要在轨迹点集中随机采样4个点来估计道路模型M。而在UGV正常行驶过程中，道路可以认为是在车体坐标系下沿着y轴方向单调递增的，因此将投影点集沿着y轴方向分成4段，对每一段内的点集随机采样一个点。通过对点集进行分段归类，这样使得随机采样点有效分布在整个轨迹线上以提高RANSAC收敛速度。

2.3 更新策略与最终路径生成

1) 更新策略

t时刻，Ruse∩{1-Cfree}≠∅则进行更新。Ruse表示当前使用中的RANSAC轨迹，Cfree表示UGV的自由空间。在UGV行驶过程中，局部地图中出现了新的障碍物，导致沿着Ruse行驶将有碰撞的危险时，先去除local_points中有碰撞的点，然后重新生成t时刻的无碰撞RANSAC轨迹Rt，并更新Ruse=Rt和global_points。

t时刻，Ruse剩下的可行驶长度drest满足drest < de，则重新生成t时刻的无碰撞RANSAC轨迹Rt并更新Ruse=Rt。其中de=v2/(2·amax)，v为当前UGV速度，amax为UGV的最大制动加速度。

2) 最终路径生成

① 将剩余可行驶长度drest进行5等分得到每段长度dseg，接下来需要先确定控制点O1。见图 7，设$\overrightarrow {{O_0}{O_1}}$与当前车辆瞬时行驶方向的夹角为φ1O0为车辆前轴中心，φ1∈[-Δφ, Δφ]，φtt时刻车辆前轮转向角，Δφ是执行周期内车前轮最大转向角。

 $\left\{ \begin{array}{l} {x_{{O_1}}} = {d_{{\rm{seg}}}} \cdot {\rm{sin}}\left( {{\varphi _1} + {\varphi _t}} \right)\\ {y_{{O_1}}} = {d_{{\rm{seg}}}} \cdot {\rm{cos}}\left( {{\varphi _1} + {\varphi _t}} \right) \end{array} \right.$ (8)
 ${\varphi _i} = \mathop {{\rm{argmin}}}\limits_{\varphi \in \left[{-\Delta \varphi, \Delta \varphi } \right]} \left( {{c_1}\cdot\frac{{\left| \varphi \right|}}{{\Delta \varphi }} + {c_2} \cdot \frac{{{\rm{d}}\mathit{x}}}{{{\mathit{d}_{{\rm{max}}}}}}} \right)$ (9)

O1坐标可由式(8)计算得到，其中φ1取值应使得式(9)取到最小值。其中，式(9)前半部分用于控制曲线的曲率，后半部分用于控制曲线尽量靠近安全的区域。其中dx表示控制点OiRuse的水平距离，${\mathit{d}_{{\rm{max}}}} = \mathop {\max }\limits_{{\varphi _i}} \left( {{\rm{d}}\mathit{x}} \right)$

② 根据式(9)来确定后续控制点。确定第i个控制点Oi时，向量$\overrightarrow {{O_{i - 1}}{O_i}} $$\overrightarrow {{O_{i - 2}}{O_{i-1}}} 的夹角|φi|≤Δφ。同样当控制点的选取使得式(9)值最小时，控制点Oi被确定下来。最后根据式(10)得到最终的路径。  B\left( t \right) = \sum\limits_{i = 0}^5 {\frac{{5!}}{{i!\left( {5 - i} \right)!}}{{\left( {1 - t} \right)}^{5 - i}}{t^i}{O_i}, t \in \left[{0, 1} \right]} (10) 3 实验与分析 3.1 生成路径对比 为了验证提出算法的有效性与正确性，利用实验平台“行健号”(见图 8)在非结构化道路上进行了大量测试。  Download: 图 8 实验平台 Fig. 8 Experiment platform 本节将本文提出的算法与文献[7-8]以及文献[10]的算法进行了对比。由于FM2算法和Circle-based算法需要起点和终点，因此将本文算法得到路径的两端作为FM2算法和Circle-based算法所需的起点和终点。 图 9(a)分别为强光、阴暗、雨天、植被覆盖以及岔道几个不同场景的视觉图像。其中部分场景下，图像受到光照、天气以及道路环境干扰，基于视觉的道路检测算法不能稳定工作。图 9(b)是本文算法的道路提取结果，图 9(c)是采用FM2算法得到的路径，图 9(d)是采用Circle-based算法得到的路径，图 9(e)是使用Linear SVM得到的检测结果。从图中可以看到本文算法、FM2算法和Circle-based算法各场景下都能生成有效路径，而Linear SVM无法处理道路曲率较大的情况。因此，在场景一的相关对比实验中没有Linear SVM的结果。  Download: 图 9 不同场景的提取路径对比 Fig. 9 The comparison of the path extracted in different scenes 图 10中的箱形图显示了各个场景下、不同算法生成的轨迹距离栅格地图中障碍物的最大值、平均值以及最小值。从图中可以看到，在安全性方面，本文算法结果整体优于Linear SVM的结果；在第1个和第3个场景下，本文算法是最优的；在第2个场景下，本文算法与最优的FM2算法较为接近，且优于Circle-based算法；在第4个场景下，由于栅格地图较为狭长，各个算法生成的轨迹较为接近，所以各算法结果都比较接近；在场景五中，FM2算法生成的路径会趋向更为安全的区域，而Circle-based算法在扩展过程中，后继圆的圆心是随机采样的，其中半径较大的圆会被优先扩展以保证路径的安全性，因此这2种算法在存在岔道的场景下生成的路径具有较高的安全性，但是路径长度并不是最优的。  Download: 图 10 离开障碍物距离的对比 Fig. 10 The comparison of the distance away from obstacles 图 11是各个场景下、不同算法生成轨迹的变化程度的对比。由于Linear SVM的线性特性生成的轨迹是直线，因此并没有将其加入对比。轨迹变化程度的定义如下：设qi-1、qi和qi+1是轨迹上的连续采样点。\overrightarrow {{q_{i - 1}}{q_i}}$$\overrightarrow {{q_i}{q_{i+1}}}$之间的夹角用来表示点qi处的变化率，以此来计算整条轨迹上采样点的变化程度。图 11中不同形状标记的位置是整条轨迹变化率的平均值，整条轨迹变化的方差决定了图中变化值的上下界。

 Download: 图 11 曲线变化对比 Fig. 11 The comparison of the change of the curve

 Download: 图 13 本文算法生成的最终路径 Fig. 13 The final paths generated by proposed method
3.2 路径曲率分析