计算机系统应用  2020, Vol. 29 Issue (8): 211-216   PDF    
基于二段多项式的窄空间平行泊车路径规划方法
熊莹1,2, 毛雪松3     
1. 武汉科技大学 计算机科学与技术学院, 武汉 430065;
2. 武汉科技大学 智能信息处理与实时工业系统湖北省重点实验室, 武汉 430065;
3. 武汉科技大学 信息科学与工程学院/人工智能学院, 武汉 430081
摘要:针对窄空间平行泊车路径规划问题, 提出一种基于二段五阶多项式的方法分别计算车辆前进路线与倒车路线, 其中前进路线用于调整车辆位姿, 实现倒车入库路径曲率最优. 根据常规停车位大小与家庭轿车的尺寸建立仿真环境, 结合车辆运动模型, 搜索自由空间内无碰撞路径. 仿真结果表明, 二段五阶多项式法可以实现在有限空间范围内的智能泊车, 且在由两段路径连接得到的路径上方向盘转向角连续变化.
关键词: 无人驾驶    自主泊车    约束空间    多项式    路径规划    
Path Planning by Two-Piece Polynomial Equation in Narrow Space for Parallel Parking
XIONG Ying1,2, MAO Xue-Song3     
1. School of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan 430065, China;
2. Hubei Province Key Laboratory of Intelligent Information, Processing and Real-time Industrial System, Wuhan University of Science and Technology, Wuhan 430065, China;
3. School of Information Science and Engineering/School of Artificial Intelligence, Wuhan University of Science and Technology, Wuhan 430081, China
Abstract: To solve the problem of path planning for parallel parking in narrow spaces, a two-piece five order polynomial equation based method was proposed for calculating approaching path and reverse path respectively, among which the approaching path was applied for adjusting the vehicle pose so that a curvature optimal path for reversing car into parking lot is available. Simulation was performed by considering the general size of parking lot and family car, as well as the kinematic model of vehicle motion, to find a collision free path in free space. The result shows that the two-piece five order polynomial equation-based method can realize intelligent parking in narrow spaces, and the steering angle of wheel changes continuously on the linked path.
Key words: unmanned driving     self-parking     constrained space     polynomial equation     path planning    

相比于垂直泊车, 平行泊车对驾驶员难度更大, 特别当车位长与车身长比值较小的情况下, 很难完成连续转向的泊车任务. 泊车的路径规划包括正向驶入和倒车入库, 其中正向驶入的方法要求车位较长. 当车位较短时, 通常使用倒车入库的方法. 当车身长接近车位长时, 为减少泊车过程中的档位切换, 在倒车入库前需确定最佳倒车起点位置与方向角(统称为位姿). 本文基于倒车入库常用的二段泊车法, 即在前进过程中预先调整车辆的方向角, 再倒车进入泊车位的方法, 提出使用二段五阶多项式, 分别表示前进路段和倒车路段, 实现在有限空间范围内的自动泊车.

自动泊车路径规划常用的方法包括几何路径法、基于地图的搜索法以及基于模糊控制的方法等. 其中几何路径法包括使用圆弧与直线连接生成路径法[1,2]、B样条曲线法[3,4]、五阶多项式法[5-7]等. 这些方法没有考虑前行过程中调整车辆方向角, 而是假定倒车的起始位姿与车位横向方向平行, 因此需要更大的横向空间. 在车位长度较短的情况下, 不预先调整方位角有可能找不到连续泊车路径. 圆弧与直线连接的方法产生的路径存在曲率不连续, 泊车过程中需要多次停车调整方向盘转向角, 轮胎磨损大的问题. 使用B样条曲线产生的路径, 虽然能够满足曲率连续的要求, 但由于方程的约束条件以及待求参数量很多, 求解过程复杂且运算量大.

建立于地图搜索的方法与车辆行驶路径规划方法类似, 包括常用的A*、D*、RRT[8-11]等, 这些方法将地图分割为小的栅格, 通过建立启发函数在栅格中搜索到一条长度最优的无碰撞路径, 然后选择使用曲线对该路径平滑得到曲率连续路径. 首先, 栅格的大小对算法的计算效率影响很大; 其次, 路径搜索中没有考虑车辆运动学特征, 即使经过平滑, 在空间狭窄的情况下, 车辆也不一定能够跟踪所得到的路径. 基于控制的方法则根据驾驶员的驾驶经验, 整理出一套控制规则, 控制泊车过程中的转向角变化. 这种方法在泊车过程中需要多次改变车辆的行驶速度和转向角、多次切换行驶方向, 对车的前后所需要的空间较大.

本文根据驾驶员泊车经验, 将泊车过程分解为前进调整方位角和倒车入库两个过程, 对这两个过程分别使用五阶多项式规划最优路径, 相比于前述文献中的方法, 本文实现在更短的空间内泊车, 且实现方向盘的连续转向.

1 仿真场景与车辆模型

考虑纵列驻车停车场位于车辆右侧, 停车位长5.5 m, 宽2 m, 相邻停车位之间间隔20 cm, 符合通常停车位的标准, 如图1所示. 在车辆长度较大, 即泊车位相对较小的情况下, 为了避免车辆多次切换档位, 通常按图1所示, 在倒车入库前调整自身的位置和方向角(统称为位姿). 在前进调整位姿与倒车入库过程中, 车辆不得触碰相邻车位, 且不能触碰自身停车位的路沿边界. 倒车入库后要求车身与车位长边平行, 如果方向盘转向角不为零, 可以在泊车完成后增加一个调整方向盘的步骤.

图 1 平行泊车仿真场景

泊车过程中, 车辆的速度很低, 因此可以不考虑侧滑等因素, 车辆的运动采用自行车模型[12].

$\left[ {\begin{array}{*{20}{c}} {\dot x} \\ {\dot y} \\ {\dot \theta } \\ {\dot \delta } \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {\cos \theta } \\ {\sin \theta } \\ {{{\tan \delta } / l}} \\ 0 \end{array}} \right]v + \left[ {\begin{array}{*{20}{c}} 0 \\ 0 \\ 0 \\ 1 \end{array}} \right]w$ (1)

这里(x, y)表示车辆后轴中心位置处的坐标, θ为方向角, 定义为车头方向与x轴正方向之间的夹角, δ表示方向盘的转向角, l表示前后轮之间的轴距, v $\dot \delta $ 分别表示车的径向速度和方向盘的转动角速率, w表示方向盘的转向速率. 前3个方程表示车辆的运动状态更新, 最后一个方程表示对方向盘转向角的控制, 该式本身为冗余项, 需要根据搜索得出的无碰撞路径, 使用专门的转向角控制算法来控制车辆行驶过程中的转向角, 例如Pure Pursuit [13]、Stanely [14]等算法. 规划无碰撞路径算法中, 考虑一定的安全裕度同时为简化运动学计算, 用矩形来定义汽车的外观.

算法仿真中使用的车辆特征参数如表1所示.

表 1 车辆特征参数

表1中, 轴距表示前后轴之间的垂直距离, 前悬为车头中心到前轴中心的距离, 后悬表示车尾中心到后轴中心的距离. 泊车完成后, 车位前后方自由空间长度总和为50 cm.

2 二段多项式泊车路径规划方法 2.1 5阶多项式连接相邻路点

有很多文献使用5阶多项式作为连接汽车起点(x0, y0)与终点(xf, yf) 之间的路径规划的方法, 所得到的路径满足起点和终点的约束条件, 且二阶连续, 车辆控制算法对路径的跟踪精度高, 但是起点与终点路径并不总是能够通过一条多项式曲线连接. 如图1所示, 车辆行驶路径包括前进路径与后退路径, 虽然整条路径是连续的, 但不满足二阶连续, 因此不能使用单个多项式来表示从起点到终点的路径. 对车辆的行驶路径分段, 保证每段路径二阶连续, 且相邻路径之间满足一阶连续的条件, 则称每段路径的端点为一个路点. 图1的路径中包含3个路点, 分别称为起点、中间点和终点. 考虑车辆的方向角和转向角, 分别定义3个点的位姿为(x0, y0, θ0, δ0)、(xi, yi, θi, δi)和(xf, yf, θf, δf).

从路径上看, 车辆的方向角θ即为路径对x的导数dy/dx, 转向角δ与路径之间满足关系:

$\tan \delta = \kappa l$ (2)

其中, l为车的轴距, κ为路径的曲率, 定义为:

$\kappa = \dfrac{{\left| {y''} \right|}}{{{{\left( {1 + {{y'}^2}} \right)}^{{3 / 2}}}}}$ (3)

在一阶导数已知的情况下, 它是一个仅与二阶导数有关的量, 因此根据曲线点的参数将车辆位姿修改为 $\left( {x,y,y',y''} \right)$ .

由于Stanely方法控制车辆方向盘转向角需要计算前轮与路径之间的最小距离, 因此规划前进路径时, 以前轮中心所能到达的位置为前进路径的终点. 倒车时, 为减小控制误差, 使用基于参数的方法控制方向盘转向角, 从后轮中心所在位置处为起点计算第二条多项式路径. 将这两个点均称为泊车路径的中间路点, 分别记为 $\left( {{x_{i1}},{y_{i1}},{{y'}_{i1}},{{y''}_{i1}}} \right)$ $\left( {{x_{i2}},{y_{i2}},{{y'}_{i3}},{{y''}_{i3}}} \right)$ . 二段多项式法生成的前进路径、倒车路径以及各路点的表示如图2所示.

图 2 前进与倒车路径以及路点标识

2.2 多项式系数的求解

设连接路点的起点与终点多项式表示为:

$y = \left[ {\begin{array}{*{20}{c}} {{a_0}}&{{a_1}}& \cdots &{{a_r}} \end{array}} \right]{\left[ {\begin{array}{*{20}{c}} 1&x& \cdots &{{x^r}} \end{array}} \right]^{\rm T}}$ (4)

将空间内无碰撞路径搜索问题转化为多项式系数的求解问题.

取泊车路径的起始位置坐标为(x0, y0), 位于待泊车位左后方, 起始位置处的方向角和转向角均为0, 因此:

$ \left( {{x_0},{y_0}} \right){\text{、}}y'{|_{x = {x_0}}} = 0{\text{、}}y''{|_{x = {x_0}}} = 0 $ (5)

终点坐标为(xf, yf), 满足:

$ \left( {{x_f},{y_f}} \right){\text{、}}y'{|_{x = {x_f}}} = 0{\text{、}}y''{|_{x = {x_0}}} < C $ (6)

其中, C为车转向角限定的常数.

泊车路径包括前进与倒车两段路径, 每段路径均由一条多项式曲线连接两个路点得到. 式(5)确定前进路段的起点, 式(6)确定倒车路段的终点. 根据图2, 在中间点已知的情况下, 即可根据式(4)计算连接起点和终点的两段多项式.

将每段曲线两个路点的位姿给出的6个限定条件代入式(4), 得出在r = 5的情况下, 可以找到连接路点起点和终点的唯一曲线. 令:

$y = \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {a} {\left[ {\begin{array}{*{20}{c}} 1&x&{{x^2}}&{{x^3}}&{{x^4}}&{{x^5}} \end{array}} \right]^{\rm T}}$ (7)
$y' = \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {a} {\left[ {\begin{array}{*{20}{c}} 0&1&{2x}&{3{x^2}}&{4{x^3}}&{5{x^4}} \end{array}} \right]^{\rm T}}$ (8)
$y'' = \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {a} {\left[ {\begin{array}{*{20}{c}} 0&0&2&{6x}&{12{x^2}}&{20{x^3}} \end{array}} \right]^{\rm T}}$ (9)

这里 $\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {a} = \left[ {\begin{array}{*{20}{c}} {{a_0}}&{{a_1}}&{{a_2}}&{{a_3}}&{{a_4}}&{{a_5}} \end{array}} \right]$ 为曲线方程的系数矢量. 因此, 为了使车能够实际跟踪多项式表示的路径, 多项式的最低阶数为5. 如果在泊车路径上存在障碍物, 可以为多项式增加高阶a6位来修正路径, 修正路径与高阶项的关系如图3所示.

图 3 高阶系数修正的泊车路径

将6个限定条件分别代入式(7)~式(9), 求出曲线方程的系数为:

$\left[ {\begin{array}{*{20}{c}} {{a_0}}&{{a_1}}&{{a_2}}&{{a_3}}&{{a_4}}&{{a_5}} \end{array}} \right] = {B^{ - 1}}Y$

这里,

$B = \left[ {\begin{array}{*{20}{c}} 1&{{x_{l0}}}&{x_{l0}^2}&{x_{l0}^3}&{x_{l0}^4}&{x_{l0}^5} \\ 0&1&{2{x_{l0}}}&{3x_{l0}^2}&{4x_{l0}^3}&{5x_{l0}^4} \\ 0&0&2&{6{x_{l0}}}&{12x_{l0}^2}&{20x_{l0}^3} \\ 1&{{x_{lf}}}&{x_{lf}^2}&{x_{lf}^3}&{x_{lf}^4}&{x_{lf}^5} \\ 0&1&{2{x_{lf}}}&{3x_{lf}^2}&{4x_{lf}^3}&{5x_{lf}^4} \\ 0&0&2&{6{x_{lf}}}&{12x_{lf}^2}&{20x_{lf}^3} \end{array}} \right]$ (10)
$Y = {\left[ {\begin{array}{*{20}{c}} {{y_{l0}}}&{y'{|_{{x_{l0}}}}}&{y''{|_{{x_{l0}}}}}&{{y_{lf}}}&{y'{|_{{x_{lf}}}}}&{y''{|_{{x_{lf}}}}} \end{array}} \right]^{\rm T}}$ (11)

式(10)和式(11)中的下标l0lf分别表示路点的起点和终点. 对于平行泊车, 两个路点上车的方向角之差不会很大, 因此B矩阵不会出现奇异解.

2.3 中间点的搜索

图2中间点(xi1, yi1)和(xi2, yi2)的搜索以及在中间点位置处的最佳方向角和转向角的计算是泊车路径规划的关键. 可以根据驾驶经验, 确定点(xi1, yi1)存在的区域范围以及方向角范围. 为了使前进与后退过程中方向盘的连续转向, 可取点(xi1, yi1) 处的转向角δ为0, 即 $y''{|_{x = {x_{i1}}}} = 0$ .

使用搜索算法找到点(xi1, yi1)以及方向角后, 根据车体的位姿求出点(xi2, yi2)的位姿为:

$\left( {\begin{array}{*{20}{c}} {{x_{i1}} - l\cos \theta }&{{y_{i1}} - l\sin \theta }&{\tan \theta }&0 \end{array}} \right)$ (12)

作为倒车路段的起点.

2.4 边界条件的数学模型

要求在前进过程中车的v1v2边、v2v3边不能与相邻车位的a0b0边相接触, 倒车过程中v1v2边、v2v3边不能与a2b2边、a2d2边接触, 另外v1v2边、v1v0边不能与c1d1边接触. 转化为数学模型, 即要求前进路段:

${v_2}\left( x \right) < {c_0}\left( x \right),{v_2}\left( y \right) > {b_0}\left( y \right)$ (13)

其中, v2 (x)、v2 (y)分别表示顶点v2x坐标和y坐标.

倒车路段要求:

$\left\{ \begin{array}{l} {v_2}\left( x \right) > {a_2}\left( x \right) \cap {v_2}\left( y \right) > {a_2}\left( y \right) \\ {v_1}\left( y \right) > {d_1}\left( y \right) \\ {v_2}\left( y \right) > {d_1}\left( y \right) \\ \end{array} \right.$ (14)
2.5 目标函数的定义

按照两个路段的曲率最优原则定义目标函数为:

$T = \alpha \int {{\kappa _1}dx + \left( {1 - \alpha } \right)\int {{\kappa _2}dx} } $ (15)

其中, κ1κ2分别为前进路段和倒车路段曲线各点的曲率. α为对目标函数贡献的权重系数.

3 仿真结果

取待泊车位的4个顶点坐标为(3, 0)、(8.5, 0)、(8.5, 2)、(3, 2), 车的起始坐标位置为(2.5, 3.5), 方向角和转向角均为0. 泊车位置为(3.9, 1.05), 方向角为0, 转向角设为方向盘最大转向范围内的一个数, 这里取34º. 在x从9米到14米、y从4米到6米、θ从0到π/4的范围内搜索最优泊车路径, 得到的泊车路径如图4所示. 由于通常期望目标函数中倒车的曲率贡献值大一些, 因此仿真中定义权重因子α = 0.1. 从泊车过程的行驶轨迹看, 二段多项式法可以正确实现平行泊车, 且泊车过程中转向角连续变化. 前进过程中适当调整车的方向角, 可以使倒车过程更容易完成.

图 4 最优二段多项式泊车路径以及泊车行驶轨迹

泊车时, 期望将车尽可能停向车位内侧, 因此取终点位置处的y值分别为1.01 m、1.02 m、1.03 m、1.05 m等几种情况, 在xi1从9 m到14 m、yi1从4 m到6 m、θ从0到π/4的范围内搜索存在安全路径的中间点. 某一中间点处, 可能有多个θ值对应安全路径, 在这些方向中选择一个θ值, 使路径的曲率最小. 存在安全路径的中间点区域如图5所示. 从图可以看出, 车辆终点位置越靠近外侧, 中间点存在区域就越大. 当xi1值较小时, 安全路径的中间点θ值较大, 这与驾驶经验吻合.

yf = 1.05 m, 对应于图5(d)各点处泊车路径的曲率如图6所示, 可见对应于每一个xi1, 存在一个最佳yi1和方向角. 同样对应于每一个yi1值, 存在一个最优xi1值, 使得曲率最低. 另外, 对于固定xi1yi1, 观察θ对另一变量也具有下凸性, 因此, 在搜索区域范围内式(15)定义的T函数具有下凸性, 可使用常规优化算法在搜索空间内找到最优解. 例如选取前轮中间点位姿xi1 = 18.0 m, yi1= 10 m和θ = π/4, 利用最速下降法搜索, 设置收敛精度为2 cm, 程序运行于Intel(R) Core(TM) i5-4460 CPU@3.2GHz, 内存8 GB, 得到最优解的时间约xi1 = 14.6 m, yi1= 7.3 m和θ = 0.79, 所用时间为0.73 s.

图 5 泊车终点位置的纵向坐标对中间点存在区域的影响, 箭头指向该位置处的最佳方向角

图 6 对应于图5(d)各点的安全路径曲率

前向路径上, 使用Stanely算法控制转向角. 当参考路径为多项式时, 低速情况下Stanely具有良好的跟踪性能. 倒车路径上, 根据计算得到路径的位置、一阶和二阶导数, 计算出在每一点位置处的方向盘转向角, 将其保存为倒车控制文件(Speed Profile). 仿真中, 设置仿真时间步长参数为0.025 s, 倒车速度为0.5 m/s, 对路径的跟踪误差不到0.2 cm, 因此通过分段得到的路径可以运用于车辆的平行泊车中.

本文通过二段曲线泊车法实现车位长度5.5 m情况下的连续泊车, 车位长与车身长的比值约为1.2, 与相关文献中已实现的车位长与车身长的比值对比, 结果如表2所示.

表 2 车位长/车身长的比较

4 结束语

本文提出了一种基于二段五阶多项式的方法完成平行泊车, 给出存在安全泊车路径的中间点存在范围, 设计代价函数并验证其下凸性. 基于通常平行车位的尺寸以及B型家用轿车尺寸, 执行泊车仿真. 仿真结果表明, 通过调整中间点方位角的方法, 可以在狭窄的空间范围完成平行泊车任务. 相比于过去假定倒车起点位置处车辆的方向与车位平行的方法, 本文所提的方法更加符合驾驶员的驾驶习惯, 实现更窄空间的平行泊车, 可以为智能驾驶车辆泊车系统的开发提供通用的方案.

参考文献
[1]
Wang DB, Liang HW, Mei T, et al. Research on self-parking path planning algorithms. Proceedings of 2011 IEEE International Conference on Vehicular Electronics and Safety. Beijing, China. 2011. 258–162.
[2]
黄江, 魏德奎, 秦良艳, 等. 自动泊车系统路径规划与跟踪控制方法研究. 汽车技术, 2019(8): 39-45.
[3]
李红, 王文军, 李克强. 基于B样条理论的平行泊车路径规划. 中国公路学报, 2016, 29(9): 143-151. DOI:10.3969/j.issn.1001-7372.2016.09.019
[4]
Elbanhawi M, Simic M, Jazar R. Randomized bidirectional B-spline parameterization motion planning. IEEE Transac-tions on Intelligent Transportation Systems, 2016, 17(2): 406-419. DOI:10.1109/TITS.2015.2477355
[5]
林蓁蓁, 李庆, 梁艳菊, 等. 一种基于路径规划的自动平行泊车算法. 计算机应用研究, 2012, 29(5): 1713-1715. DOI:10.3969/j.issn.1001-3695.2012.05.029
[6]
Zhang SW, Simkani M, Zadeh MH. Automatic vehicle parallel parking design using fifth degree polynomial path planning. Proceedings of 2011 IEEE Vehicular Technology Conference. San Francisco, CA, USA. 2011.1–4.
[7]
Demirli K, Khoshnejad M. Autonomous parallel parking of a car-like mobile robot by a neuro-fuzzy sensor-based controller. Fuzzy Sets and Systems, 2009, 160(19): 2876-2891. DOI:10.1016/j.fss.2009.01.019
[8]
Cheng LP, Liu CX, Yan B. Improved hierarchical A-star algorithm for optimal parking path planning of the large parking lot. Proceedings of 2014 IEEE International Conference on Information and Automation. Hailar, China. 2014. 695–698.
[9]
Guruji AK, Agarwal H, Parsediya DK. Time-efficient A* algorithm for robot path planning. Procedia Technology, 2016, 23: 144-149. DOI:10.1016/j.protcy.2016.03.010
[10]
Ajanovic Z, Lacevic B, Shyrokau B, et al. Search-based optimal motion planning for automated driving. Proceedings of 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Madrid, Spain. 2018.4523–4530.
[11]
Wang YB, Jha DK, Akemi Y. A two-stage RRT path planner for automated parking. Proceedings of the 2017 13th IEEE Conference on Automation Science and Engineering. Xi’an, China. 2017. 496–502.
[12]
Pfrommer J, Warrington J, Schildbach G, et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems. IEEE Transactions on Intelligent Transportation Systems, 2014, 5(4): 1567-1578. DOI:10.1109/TITS.2014.2303986
[13]
Samuel M, Hussein M, Mohamad MB. A review of some pure pursuit based path tracking techniques for control of autonomous vehicle. International Journal of Computer Applications, 2016, 135(1): 35-38. DOI:10.5120/ijca2016908314
[14]
Thrun S, Montemerlo M, Dahlkamp H, et al. Stanley: The robot that won the DARPA Grand Challenge. Journal of Field Robotics, 2006, 23(9): 661-692. DOI:10.1002/rob.20147
[15]
Zhao YN, Collins EG Jr. Robust automatic parallel parking in tight spaces via fuzzy logic. Robotics and Autonomous Systems, 2005, 51(23): 111-127. DOI:10.1016/j.robot.2005.01.002