基于微分邻域和粗糙集的动态障碍路况下智能车的控制

江 怡

(中国民用航空飞行学院 计算机学院，四川 广汉 618307)

0 引言

智能自主移动设备在障碍路况中的避障控制与路径选择是智能系统的重要组成部分，已有大量的专家、学者对智能自主移动设备的避障控制算法进行了研究，其关键在于根据设备、障碍物的位置信息及障碍物的形状大小来选择合适的局部路径以达到安全行驶的目的。目前已取得了许多突破性的进展，但是这些避障控制算法大多是基于模糊控制[1-3]、神经网络控制[4-5]等。模糊控制是基于人的经验来提取相应的控制规则，再根据这些规则建立相应的隶属函数和推理控制方法，但通常情况下隶属函数的建立相对困难，且存在一定的误差，不能确保控制的准确性。而神经网络方法在控制工程中需要输入大量的经验值，其控制效果表现一般。

智能车在障碍路况中的避障控制与路径选择是自动驾驶技术重要的组成部分，基于邻域系统[1]的动态决策与控制模型是处理和实现智能驾驶技术的一种有效途径，其主要思想源于智能生物随时随地的动态决策和行为方式。智能生物可以根据当前时刻的周围环境特点圈定一定的范围作为其安全活动范围，安全范围之外的一切事物都视为与之无关、静止的，一旦外界事物侵犯了圈定的范围，生物会做出相应的决策和行为来确保自身的安全。我们可以将此思想用于整个决策过程，使无限、复杂的决策环境转变为一个有限、局部的简单环境，即将宏观上复杂的动态决策过程分解为一系列微观上简单的静态决策过程。其要点在于一旦确定了局部的环境邻域，该邻域外的一切事物都可以看作是与之无关的和静止的，从而可视为对邻域内所做的决策没有影响的事物。该方法由两步完成：首先根据当前状态，在其邻域系统中按照某种方法找出满意的可行邻域，并将其看作静止不变的；其次在满意的可行邻域内按照某种满意优化控制算法给出控制量并实施控制动作[6]。而一个过程或事件的整体动态决策过程可看成无数个局部环境邻域内行为的顺序叠加结果。图1给出了行驶在实际道路中汽车的邻域示意图。

图1 实际道路中汽车的邻域示意

在道路上行驶的汽车会遇到各式各样的障碍物，而障碍物可分为静态障碍物和动态障碍物，后者主要是指相对于此汽车行驶的其他车辆。按照上述思想，对于静态障碍物，文献[7]给出了基于粗糙集和邻域系统的控制方法，对于动态障碍物，结合当前时刻智能车安装的各种传感器收集到的信息的变化趋势，对下一短暂时刻信息的改变情况作出相应的预测，再结合微分邻域固有的避障性，通过折线法建立相应的微分邻域，对此微分邻域所代表的区域进行分类、筛选，再取覆盖粗糙集模型下的下近似将不规则的邻域化为规则的。由此得到的可行邻域中控制规则的选取方法与文献[7]中静态障碍物中的一致，最后进行决策。为了验证方法的有效性，利用Matlab进行了仿真实验，其中，用于仿真的道路边界是由正弦函数按法线法[8]构造的等距曲线而生成的，而障碍物采用随机函数给出。仿真结果表明梯形微分邻域与经验驾驶者的驾驶范围相近。

1 基本概念

定义2.4.1(邻域[9])设X是一个论域，x为X内一个对象，称X的某个特定子集(可以不包含x)为x的邻域，记作N(x)。

定义2.4.2(邻域系统[8,9])设X是一个论域，x为X内一个对象，由x的所有邻域所构成的集族称为对象x的一个邻域系统，记做NS(x)。而论域X中所有对象邻域系统的并集称为论域X的邻域系统，记作NS(X)。

按照上述定义，有：NS(x)={A|A⊆X且A是对象x的邻域}。

(1)

定义2.4.4(微分邻域[9])设Ψ(t)为系统在t时刻邻域的边界，当t有增量时Δt，邻域的边界Ψ(t)也有相应的改变量ΔΨ(t)，以Ψ(t)+ΔΨ(t)为边界的邻域称为原邻域Φ(t)的微分邻域，记作Ω(t)。

由微分邻域的定义知，系统的微分邻域为满足一组条件的区域，即Ω(t)={(x1(t),…,xn(t))|(x1(t),…,xn(t))满足条件S}，其中S可取为式子(2)。

(2)

对于智能自主移动装置而言，例如机器人、无人驾驶飞机、智能车等，显然其实用邻域位于三位立体空间之中，下面将研究在三维空间中的邻域及其相关的数学模型。

对于某系统中的被控对象，其上的传感器在t时刻检测到一组足够密的数据(x1(t),y1(t),z1(t)),(x2(t),y2(t),z2(t)),…,(xn(t),yn(t),zn(t))，由这n个点可以确定系统在t时刻的一个邻域Φ(t)={(ω1(t),…,ωn(t))|(ω1(t),…,ωn(t))满足条件S}，其中S可取为：

(3)

ωi=(xi(t),yi(t),zi(t))，i=1,2,…,n。

Ω(t)={(ϖ1(t),…,ϖn(t))|(ϖ1(t),…,ϖn(t))满足条件S}，其中S为：

(4)

图2 微分邻域的几何意义

如图2所示，ACBEF代表的区域为被控对象t时刻的邻域，经过Δt时刻，其边界曲线ACB段变化为ADB所代表的边界曲线，则被控对象t时刻的微分邻域为ADBEF表示的区域。

2 微分邻域创建的一般模型

汽车在道路上行驶时，不仅会遇到静止的障碍物，还会遇到运动着的障碍物，例如相对行驶的汽车、行人、突然蹿出的小狗等。考虑到方法的类同性，下面主要针对同路行驶的车辆为障碍的情形进行研究。

为了更直观地反映智能车在道路上的位向信息，设在世界坐标系的基础上以智能车前轴为x轴，纵向方向为y轴，前轴中点为原点建立一个相对直角坐标系(参照图3)。

图3 微分领域示意图

利用集合B可以得到t时刻的一个微分邻域。此微分邻域是由集合B中的n个点共同决定的，可以利用Lagrange插值、分段插值、牛顿插值等数值方法近似的得到微分邻域边界函数的表达式。为了简单有效，本文采用Lagrange插值法[10-12]和分段线性插值法[13-15]进行处理。

对于t时刻的n个观测量(X1(t),Y1(t)),(X2(t),Y2(t)),…,(Xn(t),Yn(t))，其微分邻域Ω(t)= {(x(t),y(t))|(x(t),y(t))满足条件S}，其中S由式(5)、(6)、(7)决定。

y(t)≤Pn(x)

(6)

(8)

其中(xA,yA)、(xB,yB)分别表示智能车左前轮、右前轮在相对坐标系中的坐标。

式(5)、(6)、(7)的几何意义如图3所示。其中，矩形ABCD为智能车的外形轮廓，ABFE代表的区域为当前时刻智能车的可行邻域，AE由式(5)确定，曲线EF由式(6)确定，BF由式(7)确定，则ABFE区域中的点满足式(8)。

a) Lagrange插值法

(9)

b) 分段线性插值法

第二，数据组织、存储和管理功能。该功能主要用于提高存储空间利用率和方便存取效果，同时提供多种存取方法，如索引查找、Hash查找、顺序查找等。

Lagrange插值法的数学思想清晰明了，其数学表达式是对称的，易于记忆，且结构紧凑，与各节点的顺序无关。但是当增加或者减少一个节点时，其表达式整体上都要发生改变，需要重新计算，大大增加了计算量；另一方面，多项式的次数会随着节点数的增加而增加，增加了计算量且容易出现Runge现象，不利于有效的逼近被插函数。

而分段线性插值法是用折线将t时刻的n个观测量两两相连，得到微分邻域的边界函数。分段线性插值法的计算简洁方便，且增加或者减少一个节点时，只影响某局部范围的表示式，很大程度上减少了计算量。基于算法的简便性和实用性，本文采用分段线性插值法来近似微分邻域边界函数的表达式。

3 梯形微分邻域的求解模型

由上述模型得到的微分邻域一般为一个不规则的区域。在实际问题中，不规则的邻域用于控制时对于控制规则的建立通常比较困难，不利于控制模型的建立，为了算法的简便性，我们需要将不规则的微分邻域化为规则的，其思想和做法如下。

a)分类

对于集合A={(x1(t),y1(t)),(x2(t),y2(t)),…,(xn(t),yn(t))}，考虑点的增量得到的集合为B={(X1(t),Y1(t)),(X2(t),Y2(t)),…,(Xn(t),Yn(t))}，根据B中元素的坐标分量的增量对集合B进行分类，将分量的增量相等或相差某一个常数且满足相邻条件所对应的点归到一类，组成一个新的集合C={B1,B2,…,Bm}。对∀Bj∈C，Bj由下述数学模型确定：

Bj={(Xj1(t),Yj1(t)),(Xj2(t),Yj2(t)),…,(Xjt(t),Yjt(t))}

对∀Bj∈C，Bj为B的一个子集，即Bj⊆B，j=1,2,…,m，且Bj确定了t时刻的一个微分邻域Ωj(t)，Ωj(t)={(x(t),y(t))|(x(t),y(t))满足条件Sj}，其中Sj由式(5)、(7)、(9)确定，设(5)确定的直线为lj，(7)确定的直线为rj。

b)确定最优邻域

利用如下优化模型从Ωj(t)选择一个作为t时刻的微分邻域：

max{min{|Yj1|，…，|Yjt|}}

(12)

其中d为被控对象的宽度，ε为某个大于零的常数。

c)对求解结果进行判断

若b)中优化模型的解存在，则转到e)；若为空集，即Ωj(t)的宽度都小于被控对象的宽度，则进行下一步。

d)减少分类个数

通过减少B的分类个数来达到目标，具体做法如下：

令D={B1∪B2,B2∪B3,…,Bm-1∪Bm}，即将相邻的两类归为一类，将原来m类变为m-1类。再由式(11)得到此优化模型的解。若解为空集，则继续减少B的分类个数，令E={B1∪B2∪B3,B2∪B3∪B4,…,Bm-2∪Bm-1∪Bm}，即将D中相邻的两类归为一类，再由式(11)得到此优化模型的解。若解为空集，继续上述步骤，直到得到此优化模型的解Ωp(t)，则Ωp(t)为t时刻的微分邻域。

e)化不规则为规则

设Ωp(t)由点集{(Xp1(t),Yp1(t)),(Xp2(t),Yp2(t)),…(Xpr(t),Ypr(t))}确定。Ωp(t)的形状一般情况下是不规则的，Ωp(t)={(x(t),y(t))|(x(t),y(t))满足条件Sp}，其中Sp由式(5)(7)(9)确定。将不规则的Ωp(t)化为规则的梯形微分邻域，以L1、L2作为梯形的两边，h作为梯形的高，得到一个梯形邻域T(t)，即T(t)={ (x,y)| (x,y)满足条件S}，其中S可取为：

(13)

其中(xA,yA)、(xB,yB)分别表示智能车左前轮、右前轮在相对坐标系中的坐标。

通过改变h得到一系列的梯形邻域T(t)，然后取覆盖粗糙集模型意义下的下近似作为t时刻的梯形微分邻域。

4 基于动态障碍物的梯形微分邻域求解的仿真

对于动态障碍物的梯形微分邻域求解的仿真实现，本文利用正弦函数作为道路的边界曲线函数来进行仿真，具体的方法参照文献[7]，且令道路的宽度为7 m，再采用文献[7]中的智能车的仿真模型，得到如图4所示的仿真结果图。

图4 t时刻汽车的位置

图5 t时刻传感器采集到的点

在图4中，编号为1的矩形代表的智能车为被控对象，编号为2、3的矩形代表的智能车为动态障碍物。同时，智能车1、2、3的速度分别为v1、v2、v3，对于智能车1而言，智能车3的速度比智能车1快，智能车2的速度比智能车1慢，即满足v3>v1>v2。若车载传感器在当前时刻t采集到一组点集为：

A={(0.5,1.8),(0.75,1.93),(0.79,1.84),(0.81,1.66),(1.3,1.7),(1.32,1.6),(1.34,1.5),(1.36,1.4),(1.25,1.34),(1.25,1.16),(1.35,1.08)(1.17,1.02)}。

点集A如图5中小实心黑点所示，利用上文中式(5)、(7)、(9)得到时刻t的可行邻域，如图6所示。

图6 时刻t的可行邻域

图7 t+t时刻障碍点预测的变化位置

图8 t时刻的微分邻域

图9 t时刻的微分邻域

将得到的新的n个点利用上文式(5)、(7)、(9)，我们可以得到时刻t的微分可行邻域，如图8中虚线部分所示，更直观的如图9所示。

图10 筛选出的微分邻域

图11 筛选出的微分邻域

对于图9得到的t时刻的微分邻域，再利用上文中的梯形微分邻域的求解模型对此微分邻域进行筛选，得到如图10所示的微分邻域。筛选出的t时刻的微分邻域更直观的如图11所示。

再利用梯形微分邻域的求解模型对此微分邻域进行规则化，得到如图12所示的梯形微分邻域。

图12 t时刻的梯形微分邻域

5 结语

本文利用微分邻域固有的避障作用和覆盖粗糙集模型的特点来处理动态障碍路况下智能车的控制，其方法为利用分段线性插值法得到微分邻域边界曲线的表达式，再基于邻域的区域分类和覆盖粗糙集模型的下近似得到梯形可行邻域，达到了预测的效果，实现了保守且安全的控制，使智能车在行车过程中在保障安全的前提下能以较高的效率行驶。