第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201805004 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190520.1514.012.html 基于邻域系统的智能车辆最优轨迹规划方法 王星，赵海良，王志刚 （西南交通大学数学学院信息与计算科学系，四川成都610031) 摘要：针对智能车在行驶中的轨迹规划与控制问题。以邻域系统理论为基础，将智能车在复杂道路的动态控 制转化为邻域内的简单静态控制：对邻域内的最优轨迹曲线进行选取，采用曲率的积分定义了曲线的弯阻指 数，并以此为基础给出了邻域内的最优轨迹曲线评判模型和求解算法：以插值方法所建立的满意轨迹曲线为例 进行仿真。结果表明，该方法在选取智能车的行驶轨迹的平稳光滑性上有一定的优越性。 关键词：智能车辆：自动驾驶；轨迹规划；车辆避障：邻域系统；最优轨迹：满意曲线；综合评判 中图分类号：0231.2文献标志码：A文章编号：1673-4785(2019)05-1040-08 中文引用格式：王星，赵海良，王志刚.基于邻域系统的智能车辆最优轨迹规划方法.智能系统学报，2019,14(5)： 1040-1047. 英文引用格式：WANG Xing,ZHAO Hailiang,.WANG Zhigang..Optimal trajectory planning method of intelligent vehicles based on neighborhood systemJ CAAI transactions on intelligent systems,2019,14(5):1040-1047. Optimal trajectory planning method of intelligent vehicles based on neighborhood system WANG Xing,ZHAO Hailiang,WANG Zhigang (Department of Information and Computation Science,School of Mathematics,Southwest Jiaotong University,Chengdu 610031, China) Abstract:This study mainly investigates the trajectory planning and control problems in the driving process of smart vehicles.First,based on the theory of neighborhood system,the dynamic control of intelligent vehicles on complex roads is transformed into a simple static control in the neighborhood,and then the optimal trajectory is selected in the neighborhood.The bending resistance index of the curve is defined by the integral of the curvature,and based on this, the optimal trajectory curve evaluation model and algorithm in the neighborhood is given.Finally,a satisfactory traject- ory curve established by the interpolation method is taken as an example for simulation.The results show that this meth- od has some advantages in selecting the steadiness and smoothness of the driving trajectory of an intelligent vehicle. Keywords:intelligent vehicle;automatic driving;trajectory planning,obstacle avoidance;neighborhood system;optim- al trajectory;satisfaction curve;comprehensive evaluation 智能车辆的研究内容十分多样，例如它的结 Floyd--Warshall算法，支持向量机算法，A*算法4 构设计，控制理论，路径规划。对于智能车的 等均有文献进行应用和改进。而对于智能车的动 路径规划，设计最优的曲线是此问题的核心。智 态路径规划，人工势场算法、神经网络算法、遗 能车的路径规划按照范围可分为宏观与微观 传算法等智能算法也被广泛的应用。上述算法大 2类，按照状态可分为动态规划和静态规划2 多是对宏观的道路网络节点进行路径规划，然而 类。对于智能车的宏观路径规划，Dijkstra算法、 对于微观的道路上的轨迹规划问题，目前国内外 文献较少从最优性这一角度进行考量，还需要进 收稿日期：2018-05-05.网络出版日期：2019-05-21. 基金项目：国家自然科学基金资助项目(61473239,61402382). 行进一步的探索与研究。对于轨迹规划问题，基 通信作者：王星.E-mail:775423112@qq.com. 于Dubins路径的轨迹生成方法是一种可行的
DOI: 10.11992/tis.201805004 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190520.1514.012.html 基于邻域系统的智能车辆最优轨迹规划方法 王星，赵海良，王志刚 （西南交通大学 数学学院 信息与计算科学系，四川 成都 610031） 摘 要：针对智能车在行驶中的轨迹规划与控制问题。以邻域系统理论为基础，将智能车在复杂道路的动态控 制转化为邻域内的简单静态控制；对邻域内的最优轨迹曲线进行选取，采用曲率的积分定义了曲线的弯阻指 数，并以此为基础给出了邻域内的最优轨迹曲线评判模型和求解算法；以插值方法所建立的满意轨迹曲线为例 进行仿真。结果表明，该方法在选取智能车的行驶轨迹的平稳光滑性上有一定的优越性。 关键词：智能车辆；自动驾驶；轨迹规划；车辆避障；邻域系统；最优轨迹；满意曲线；综合评判 中图分类号：O231.2 文献标志码：A 文章编号：1673−4785(2019)05−1040−08 中文引用格式：王星, 赵海良, 王志刚. 基于邻域系统的智能车辆最优轨迹规划方法 [J]. 智能系统学报, 2019, 14(5): 1040–1047. 英文引用格式：WANG Xing, ZHAO Hailiang, WANG Zhigang. Optimal trajectory planning method of intelligent vehicles based on neighborhood system[J]. CAAI transactions on intelligent systems, 2019, 14(5): 1040–1047. Optimal trajectory planning method of intelligent vehicles based on neighborhood system WANG Xing，ZHAO Hailiang，WANG Zhigang (Department of Information and Computation Science, School of Mathematics, Southwest Jiaotong University, Chengdu 610031, China) Abstract: This study mainly investigates the trajectory planning and control problems in the driving process of smart vehicles. First, based on the theory of neighborhood system, the dynamic control of intelligent vehicles on complex roads is transformed into a simple static control in the neighborhood, and then the optimal trajectory is selected in the neighborhood. The bending resistance index of the curve is defined by the integral of the curvature, and based on this, the optimal trajectory curve evaluation model and algorithm in the neighborhood is given. Finally, a satisfactory trajectory curve established by the interpolation method is taken as an example for simulation. The results show that this method has some advantages in selecting the steadiness and smoothness of the driving trajectory of an intelligent vehicle. Keywords: intelligent vehicle; automatic driving; trajectory planning; obstacle avoidance; neighborhood system; optimal trajectory; satisfaction curve; comprehensive evaluation 智能车辆的研究内容十分多样，例如它的结 构设计，控制理论[1-2] ，路径规划。对于智能车的 路径规划，设计最优的曲线是此问题的核心。智 能车的路径规划按照范围可分为宏观与微观 2 类，按照状态可分为动态规划和静态规划 2 类。对于智能车的宏观路径规划，Dijkstra 算法、 Floyd-Warshall 算法，支持向量机算法[3] ，A*算法[4-5] 等均有文献进行应用和改进。而对于智能车的动 态路径规划，人工势场算法[6] 、神经网络算法、遗 传算法等智能算法也被广泛的应用。上述算法大 多是对宏观的道路网络节点进行路径规划，然而 对于微观的道路上的轨迹规划问题，目前国内外 文献较少从最优性这一角度进行考量，还需要进 行进一步的探索与研究。对于轨迹规划问题，基 于 Dubins 路径[7] 的轨迹生成方法是一种可行的 收稿日期：2018−05−05. 网络出版日期：2019−05−21. 基金项目：国家自然科学基金资助项目 (61473239，61402382). 通信作者：王星. E-mail: 775423112@qq.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
第5期 王星，等：基于邻域系统的智能车辆最优轨迹规划方法 ·1041· 方法。此外还有三角函数曲线、圆弧曲线等轨迹 声波传感器、图像传感器等。当智能车辆在道 生成方法。考虑到曲率连续问题，文献[⑦]给出 路上运动时，这些传感器会给出当前道路包括 了基于五次多项式的轨迹规划方法。此外还有文 障碍物的各种信息，用以确定车辆的一个安全 献采用模糊逻辑控制0、粒子群算法、蚁群算法 行走范围，这就是车辆的一个可行邻域，可行邻 等智能算法进行优化与控制。上述文献给出了十 域的定义如下。 分有价值的理论成果，但大多是对首末位置以及 定义1可行邻域 障碍物信息已知情况下的轨迹规划，不少文献采 假设状态论域X的一个有界区域Q(xo,T刀满 用GPS定位方式确定信息，鉴于目前GPS装置的 足：E∈Qx,T),3{x()xo,T∈(xo),使得z∈{x): 精度和性能，可能会和实际路况存在较大误差。 xo,T且{x(t),x0,TQxo,T),则称Q(x,T)是初态 因此，在实际道路中目标点的确定依然是一个难 x的一个可行邻域，其中T称可行区域的保持时 题，而邻域系统理论是一种可行的解决方式。 间，x)为初始状态为x的轨迹集合。 本文主要以邻域系统8：)理论为基础，研究 由初始状态x的所有可行邻域构成的集合称 智能车在邻域系统内的最优轨迹，是微观道路上 的轨迹规划问题。邻域系统是一个数学上的常用 为该状态的可行邻域系统，记为FNS(x)。状态 概念，是对事物及其关联事物体系的抽象描述。 x的一个可行邻域包括了从x出发的一段时间 本文一方面将数学中的邻域系统应用于智能车辆 T内状态轨迹的集合，在一个确定的可行邻域内 具体的控制过程，这里涉及到了设计具体控制规 可能含多条轨迹。 则，实现数学抽象到具体应用的转变；另一方面 要实现智能车等智能轮式机器人的自主移 将具体的智能车控制过程抽象成一般的数学模 动，首先需要模仿智能生物的行为决策过程。智 型，并通过具体的求解算法，进行数学模型的求 能生物在面对复杂的动态环境时，通常先寻找一 解。通过分层决策思想，将动态的车辆运动规划 个短时间不变或保持相对稳定的环境作为其下一 中近乎无限多的信息缩小至车辆的邻域系统内， 步活动的决策范围，然后再进行行为决策。这一 继而缩小至有限个标准可行邻域内，从而将复杂 决策范围即可行邻域，一系列的可行邻域构成邻 道路中的运动简化为车辆在一系列简单的邻域内 域系统。基于邻域系统的动态决策模型⑧就是描 的静态决策过程的叠加。因此只需考虑某一个单 述这样一个基于邻域系统的控制决策过程。其控 邻域内的最优轨迹规划问题，这为问题求解带 制过程由以下几个步骤组成： 来了极大地简化。 1)根据控制过程中观测变量的特点选择合适 对于单一邻域内的最优轨迹规划问题。首先 的邻域系统； 根据乘车者的需求对标准可行邻域内的轨迹曲线 2)通过一些优化方法，在当前状态下确定一 寻求泛函极值。具体做法是应用泛函的思想确立 个满意的可行邻域； 轨迹曲线的弯阻指数与长度指数等指标，其中采 3)在满意的邻域中，根据一些规划方法给予 用曲线曲率的积分定义了曲线的弯阻指数。上述 指标的建立是为了模拟乘车者的感受，以弯阻指 满意的决策，实施新的决策行为； 数为例，若道路曲率越小，则弯阻指数越小，车辆 4)在可行邻域的持续时间内保持相同的行 行驶越顺畅。按照上述指标的要求，本文建立了 为，直到产生下一个决策； 最优轨迹曲线的多目标优化模型，并给出了一种 5)上述过程是一个完整的决策循环。当一个 实用的和可操作的求解方案，构造了一种采用 周期完成后，一个新的循环开始依次执行步骤 Hermite插值法的轨迹曲线，并和其他几类常用的 2)-4)0 轨迹曲线进行了对比，结果表明本文构造的曲线 可以看到，各个邻域的控制过程不断重复叠 是一种比较好的满意轨迹曲线，更接近人工经验 加，从而构成了整个控制过程。模型将复杂的宏 轨迹。 观环境下的动态决策过程分解为一系列简单的邻 1智能车辆的邻域系统 域内的静态决策过程的组合，简化了整个决策过 程，使得面对的是一个有限的、局部的简单环境， 智能车辆会因人们的各类需求而装配有各 而不是无限的、复杂的整个世界。由此可见，车 类传感器，例如距离传感器、红外线传感器、超 辆在道路上的运动轨迹问题被转化为在每一个可
方法。此外还有三角函数曲线、圆弧曲线等轨迹 生成方法。考虑到曲率连续问题，文献 [7] 给出 了基于五次多项式的轨迹规划方法。此外还有文 献采用模糊逻辑控制[8-10] 、粒子群算法、蚁群算法 等智能算法进行优化与控制。上述文献给出了十 分有价值的理论成果，但大多是对首末位置以及 障碍物信息已知情况下的轨迹规划，不少文献采 用 GPS 定位方式确定信息，鉴于目前 GPS 装置的 精度和性能，可能会和实际路况存在较大误差。 因此，在实际道路中目标点的确定依然是一个难 题，而邻域系统理论是一种可行的解决方式。 本文主要以邻域系统[8-12] 理论为基础，研究 智能车在邻域系统内的最优轨迹，是微观道路上 的轨迹规划问题。邻域系统是一个数学上的常用 概念，是对事物及其关联事物体系的抽象描述。 本文一方面将数学中的邻域系统应用于智能车辆 具体的控制过程，这里涉及到了设计具体控制规 则，实现数学抽象到具体应用的转变；另一方面 将具体的智能车控制过程抽象成一般的数学模 型，并通过具体的求解算法，进行数学模型的求 解。通过分层决策思想，将动态的车辆运动规划 中近乎无限多的信息缩小至车辆的邻域系统内， 继而缩小至有限个标准可行邻域内，从而将复杂 道路中的运动简化为车辆在一系列简单的邻域内 的静态决策过程的叠加。因此只需考虑某一个单 一邻域内的最优轨迹规划问题，这为问题求解带 来了极大地简化。 对于单一邻域内的最优轨迹规划问题。首先 根据乘车者的需求对标准可行邻域内的轨迹曲线 寻求泛函极值。具体做法是应用泛函的思想确立 轨迹曲线的弯阻指数与长度指数等指标，其中采 用曲线曲率的积分定义了曲线的弯阻指数。上述 指标的建立是为了模拟乘车者的感受，以弯阻指 数为例，若道路曲率越小，则弯阻指数越小，车辆 行驶越顺畅。按照上述指标的要求，本文建立了 最优轨迹曲线的多目标优化模型，并给出了一种 实用的和可操作的求解方案，构造了一种采用 Hermite 插值法的轨迹曲线，并和其他几类常用的 轨迹曲线进行了对比，结果表明本文构造的曲线 是一种比较好的满意轨迹曲线，更接近人工经验 轨迹。 1 智能车辆的邻域系统 智能车辆会因人们的各类需求而装配有各 类传感器，例如距离传感器、红外线传感器、超 声波传感器、图像传感器等。当智能车辆在道 路上运动时，这些传感器会给出当前道路包括 障碍物的各种信息，用以确定车辆的一个安全 行走范围，这就是车辆的一个可行邻域，可行邻 域的定义如下。 定义 1 可行邻域[8] ∀ ∃ ⊆ 假设状态论域 X 的一个有界区域 Q(x0 , T) 满 足： z∈Q(x0 , T)， {x(t); x0 , T}∈Γ(x0 )，使得 z∈{x(t); x0 , T}且{x(t); x0 , T} Q(x0 , T)，则称 Q(x0 , T) 是初态 x0 的一个可行邻域，其中 T 称可行区域的保持时 间，Γ(x0 ) 为初始状态为 x0 的轨迹集合。 由初始状态 x0 的所有可行邻域构成的集合称 为该状态的可行邻域系统，记为 FNS(x0 )。状态 x0 的一个可行邻域包括了从 x0 出发的一段时间 T 内状态轨迹的集合，在一个确定的可行邻域内 可能含多条轨迹。 要实现智能车等智能轮式机器人的自主移 动，首先需要模仿智能生物的行为决策过程。智 能生物在面对复杂的动态环境时，通常先寻找一 个短时间不变或保持相对稳定的环境作为其下一 步活动的决策范围，然后再进行行为决策。这一 决策范围即可行邻域，一系列的可行邻域构成邻 域系统。基于邻域系统的动态决策模型[8] 就是描 述这样一个基于邻域系统的控制决策过程。其控 制过程由以下几个步骤组成： 1) 根据控制过程中观测变量的特点选择合适 的邻域系统； 2) 通过一些优化方法，在当前状态下确定一 个满意的可行邻域； 3) 在满意的邻域中，根据一些规划方法给予 满意的决策，实施新的决策行为； 4) 在可行邻域的持续时间内保持相同的行 为，直到产生下一个决策； 5) 上述过程是一个完整的决策循环。当一个 周期完成后，一个新的循环开始依次执行步骤 2)～4)。 可以看到，各个邻域的控制过程不断重复叠 加，从而构成了整个控制过程。模型将复杂的宏 观环境下的动态决策过程分解为一系列简单的邻 域内的静态决策过程的组合，简化了整个决策过 程，使得面对的是一个有限的、局部的简单环境， 而不是无限的、复杂的整个世界。由此可见，车 辆在道路上的运动轨迹问题被转化为在每一个可 第 5 期 王星，等：基于邻域系统的智能车辆最优轨迹规划方法 ·1041·
·1042· 智能系统学报 第14卷 行邻域里的运动规划问题的叠加。 就是在一个个局部的标准可行邻域内的轨迹规划 如图1所示，为智能车某一时刻在道路上行 的累积过程。 驶的示意图。其中上下两侧的平行线为仿真道路 的边界，道路内部的虚线所围成的不规则多边形 是传感器能够确立的车辆行驶的一个可行邻域。 注意到可行邻域的形状与数学表达都很难描述， 因此需要建立车辆的标准可行邻域，其中图1内 虚线围成的矩形框就是一个标准可行邻域。鉴于 标准可行邻域没有一个统一的定义，本文的标准 可行邻域含义如下。 图3智能车的动态轨迹规划 Fig.3 Intelligent vehicles dynamic trajectory planning 2最优轨迹曲线的评判指标 2.1基于邻域系统的最优轨迹曲线 在本文的智能车控制系统中，设Q为标准可 行邻域系统，则寻求最优轨迹曲线可以抽象为对 标准可行邻域内的信息寻求泛函极值的过程。 图1智能车标准可行邻域分析图 Fig.1 Standard feasible neighborhood analysis J[x(t】]= F.x(.xd (1) 标准可行邻域：可行邻域中数量有限的特定 式中：方括号为泛函记号；时间1是自变量，满足 邻域。 0≤t≤T,T为控制总时间；x(①；o,T}为过xo的轨 标准可行邻域的提出是为了在计算机仿真的 迹集合；F为被积函数，随不同乘车者的需求而取 过程易于进行模型的建立和数学描述，根据目的 的不同可以建立不同形状、不同大小的标准可行 不同的形式，例如可取轨迹的长度。 邻域。如图2所示，为智能车的标准矩形邻域。 对最优轨迹曲线的选取进一步细分，可根据 要求标准矩形邻域的底边与车体的底边是重合 不同的需求划分如下： 的。智能车的邻域系统控制思想可以将复杂的动 1)用时较短； 态控制转化为简单的静态控制。主要包括2个步 2)行走路径较短； 骤，第一步是将控制范围缩小至一个局部的可行 3)乘客感到舒适。 邻域，第二步是将局部可行邻域内的控制简化至 这是一个多目标优化问题，上述问题的最优 有限个标准的可行邻域内的控制。 解是车辆在标准可行邻域内的最优曲线。 2.2最优轨迹曲线的评判指标 由上述需求，对于轨迹曲线L的轨迹方程= x)。构造规则如下： 1)轨迹曲线的首尾位置是固定的，起始位置 为当前邻域相对坐标系的原点，末位置为当前标 准可行邻域的尾部中点向左平移一个车体长度。 2)轨迹曲线的方程为单值函数，即对于自变 0 量x,其对应的函数值x)是唯一的。 图2标准矩形邻域 3)轨迹曲线是连续的。 Fig.2 Standard rectangular neighborhood 如图4所示，曲线A不满足构造规则2)，不是 如图3所示，给出了智能车在3个不同时刻 本文的轨迹曲线。这也是符合实际驾驶经验的， 的行驶状态，其中每一个矩形框为智能车此时确 车辆在单行道路行驶时，不会出现反向行驶的情 立的标准可行邻域。智能车在道路上的轨迹规划 况。曲线B,C为车辆的轨迹曲线
行邻域里的运动规划问题的叠加。 如图 1 所示，为智能车某一时刻在道路上行 驶的示意图。其中上下两侧的平行线为仿真道路 的边界，道路内部的虚线所围成的不规则多边形 是传感器能够确立的车辆行驶的一个可行邻域。 注意到可行邻域的形状与数学表达都很难描述， 因此需要建立车辆的标准可行邻域，其中图 1 内 虚线围成的矩形框就是一个标准可行邻域。鉴于 标准可行邻域没有一个统一的定义，本文的标准 可行邻域含义如下。 O x y 图 1 智能车标准可行邻域分析图 Fig. 1 Standard feasible neighborhood analysis 标准可行邻域：可行邻域中数量有限的特定 邻域。 标准可行邻域的提出是为了在计算机仿真的 过程易于进行模型的建立和数学描述，根据目的 的不同可以建立不同形状、不同大小的标准可行 邻域。如图 2 所示，为智能车的标准矩形邻域。 要求标准矩形邻域的底边与车体的底边是重合 的。智能车的邻域系统控制思想可以将复杂的动 态控制转化为简单的静态控制。主要包括 2 个步 骤，第一步是将控制范围缩小至一个局部的可行 邻域，第二步是将局部可行邻域内的控制简化至 有限个标准的可行邻域内的控制。 O x y 图 2 标准矩形邻域 Fig. 2 Standard rectangular neighborhood 如图 3 所示，给出了智能车在 3 个不同时刻 的行驶状态，其中每一个矩形框为智能车此时确 立的标准可行邻域。智能车在道路上的轨迹规划 就是在一个个局部的标准可行邻域内的轨迹规划 的累积过程。 O x y 图 3 智能车的动态轨迹规划 Fig. 3 Intelligent vehicles dynamic trajectory planning 2 最优轨迹曲线的评判指标 2.1 基于邻域系统的最优轨迹曲线 在本文的智能车控制系统中，设 Q 为标准可 行邻域系统，则寻求最优轨迹曲线可以抽象为对 标准可行邻域内的信息寻求泛函极值的过程。 J [x (t)] = ∫ T 0 F (t, x (t), x ′ (t))dt (1) 0 ⩽ t ⩽ T {x (t); x0,T} 式中：方括号为泛函记号；时间 t 是自变量，满足 ，T 为控制总时间； 为过 x0 的轨 迹集合；F 为被积函数，随不同乘车者的需求而取 不同的形式，例如可取轨迹的长度。 对最优轨迹曲线的选取进一步细分，可根据 不同的需求划分如下： 1) 用时较短； 2) 行走路径较短； 3) 乘客感到舒适。 这是一个多目标优化问题，上述问题的最优 解是车辆在标准可行邻域内的最优曲线。 2.2 最优轨迹曲线的评判指标 由上述需求，对于轨迹曲线 L 的轨迹方程 y= y(x)。构造规则如下： 1) 轨迹曲线的首尾位置是固定的，起始位置 为当前邻域相对坐标系的原点，末位置为当前标 准可行邻域的尾部中点向左平移一个车体长度。 2) 轨迹曲线的方程为单值函数，即对于自变 量 x，其对应的函数值 f(x) 是唯一的。 3) 轨迹曲线是连续的。 如图 4 所示，曲线 A 不满足构造规则 2)，不是 本文的轨迹曲线。这也是符合实际驾驶经验的， 车辆在单行道路行驶时，不会出现反向行驶的情 况。曲线 B，C 为车辆的轨迹曲线。 ·1042· 智 能 系 统 学 报 第 14 卷
第5期 王星，等：基于邻域系统的智能车辆最优轨迹规划方法 ·1043· 对于轨迹曲线，如何在轨迹曲线族中选取最 对式(4)进行化简，令 优的轨迹曲线是整个轨迹规划理论的关键。考虑 (x1-o) (5) 多目标优化条件，本文给出下述2个指标。 Jinin=1+(x1-xo) 结合定义2，有 八=1-= 1 1-Ja(1+0(1-Jm) (6) 曲线L的距离优度就是对长度指数的标准 化。其中区间[xx]代表智能车轨迹曲线首末位 置所在的区间。因此最短距离为直线距离 图4曲线构造图 d=-0,J为最短距离d的标准化形式。考虑 Fig.4 Curve construction diagram 到无限长的连续曲线可以围住一块有限的面积这 定义2长度指数 一事实，标准化过程就是将长度指数的范围从 J=J[y(x)]= /1+0y(x)2dx (2) d,+o]映射到[0,1]区间上。当长度指数J为最 短距离d时，代入式(6)，”取1；当长度指数为+o 称之为曲线L的长度指数。 时，·取0。因此严的取值越接近1越令人满意。 定义3弯阻指数 定义5顺畅度 K=K[y(x)]= by"( -dx (3) by"( -dx V1+y) V1+y(x)3 称之为曲线L的弯阻指数。 K=1- ly"( (7) 长度指数是衡量首末位置等同的不同轨迹的 + -dx V1+y(x)月 驾驶长度。一般来说，对于一固定首末点的曲 线，轨迹长度越短，可以认为沿此曲线行驶的驾 称之为曲线L的顺畅度。 驶效率越好。 结合定义3对式（⑦）进行化简，则有 车辆行驶的弯阻指数主要取决于行驶轨迹的 (8) 顺畅，不同于轨迹曲率这一局部概念，是一个整 K1k 体性的概念。对于行驶轨迹的平稳，易知曲率越 曲线L的顺畅度是弯阻指数的标准化过程， 小，轨迹越顺畅，乘客越舒适。其次由定义式可 考虑到直线的曲率为0，因此标准化的过程就是 知，弯阻指数取决于轨迹的固有特征，与其他因 将弯阻指数的范围从[0，+∞]映射到[0,1]区间 素无关，是描述轨迹性质的常数。 上。当弯阻指数K为0时，代入式(8)，K取1；当 对于定义3，可给出推论1： 弯阻指数为+时，K取0。因此K的取值越接 推论1对于A、B两条首末位置相同的曲 近1越令人感到顺畅。 线，若A曲线每一点的曲率的绝对值都小于B曲 在实际应用时，可根据不同需求选用指数型 线，则A曲线的弯阻指数小于B曲线。 指标或标准化指标。对于不同驾驶风格的驾驶 由推论1显然可以得出，对于2条定长曲线， 员，可初步划分为驾驶平稳型和追求速度型，他 曲率越小的曲线越令人感到顺畅。 们对于上述2个指标是有着不同偏好的。为了综 2.3评判指标的标准化 合评判不同驾驶员对于最优轨迹曲线的要求，现 为了便于进行指标的评判和比较，本文的指 引入对于最优轨迹曲线的综合评判指标。 标标准化方法如下： 定义6综合评判指标 C=w1·+w2·K (9) 定义4距离优度 称之为曲线L的综合评判指标，其中w1、w2 +dx (X1-xo) 为不同驾驶风格的驾驶员对于J*、K*指标的权 1+1+dx 1+(x1-xo) 重，可由专家评判给出。 =1- (4) 综上可知，在众多轨迹曲线中选取一个最优 曲线，只需比较不同轨迹曲线的综合评判指标的 称之为曲线L的距离优度。 值，数值最大的曲线即为所求
对于轨迹曲线，如何在轨迹曲线族中选取最 优的轨迹曲线是整个轨迹规划理论的关键。考虑 多目标优化条件，本文给出下述 2 个指标。 O x y A B C 图 4 曲线构造图 Fig. 4 Curve construction diagram 定义 2 长度指数 J = J [ y (x) ] = ∫ x1 x0 √ 1+(y ′ (x))2 dx (2) 称之为曲线 L 的长度指数。 定义 3 弯阻指数 K = K [ y (x) ] = ∫ x1 x0 |y ′′ (x)| √ (1+y ′ (x))3 dx (3) 称之为曲线 L 的弯阻指数。 长度指数是衡量首末位置等同的不同轨迹的 驾驶长度。一般来说，对于一固定首末点的曲 线，轨迹长度越短，可以认为沿此曲线行驶的驾 驶效率越好。 车辆行驶的弯阻指数主要取决于行驶轨迹的 顺畅，不同于轨迹曲率这一局部概念，是一个整 体性的概念。对于行驶轨迹的平稳，易知曲率越 小，轨迹越顺畅，乘客越舒适。其次由定义式可 知，弯阻指数取决于轨迹的固有特征，与其他因 素无关，是描述轨迹性质的常数。 对于定义 3，可给出推论 1： 推论 1 对于 A、B 两条首末位置相同的曲 线，若 A 曲线每一点的曲率的绝对值都小于 B 曲 线，则 A 曲线的弯阻指数小于 B 曲线。 由推论 1 显然可以得出，对于 2 条定长曲线， 曲率越小的曲线越令人感到顺畅。 2.3 评判指标的标准化 为了便于进行指标的评判和比较，本文的指 标标准化方法如下： 定义 4 距离优度 J ∗ = 1− ∫ x1 x0 √ 1+(y ′ (x))2 dx 1+ ∫ x1 x0 √ 1+(y ′ (x))2 dx − (x1 − x0) 1+(x1 − x0) 1− (x1 − x0) 1+(x1 − x0) (4) 称之为曲线 L 的距离优度。 对式 (4) 进行化简，令 J ∗ min= (x1 − x0) 1+(x1 − x0) (5) 结合定义 2，有 J ∗ = 1− J 1+J − J ∗ min 1− J ∗ min = 1 (1+J) ( 1− J ∗ min ) (6) [x0, x1] d = x1 − x0 J ∗ min [d,+∞] J ∗ +∞ J ∗ J ∗ 曲线 L 的距离优度就是对长度指数的标准 化。其中区间 代表智能车轨迹曲线首末位 置所在的区间。因此最短距离为直线距离 ， 为最短距离 d 的标准化形式。考虑 到无限长的连续曲线可以围住一块有限的面积这 一事实，标准化过程就是将长度指数的范围从 映射到 [0,1] 区间上。当长度指数 J 为最 短距离 d 时，代入式 (6)， 取 1；当长度指数为 时， 取 0。因此 的取值越接近 1 越令人满意。 定义 5 顺畅度 K ∗ = 1− ∫ x1 x0 |y ′′ (x)| √ (1+y ′ (x))3 dx 1+ ∫ x1 x0 |y ′′ (x)| √ (1+y ′ (x))3 dx (7) 称之为曲线 L 的顺畅度。 结合定义 3 对式 (7) 进行化简，则有 K ∗ = 1− K 1+K = 1 1+K (8) [0,+∞] K ∗ +∞ K ∗ K ∗ 曲线 L 的顺畅度是弯阻指数的标准化过程， 考虑到直线的曲率为 0，因此标准化的过程就是 将弯阻指数的范围从 映射到 [0,1] 区间 上。当弯阻指数 K 为 0 时，代入式 (8)， 取 1；当 弯阻指数为 时， 取 0。因此 的取值越接 近 1 越令人感到顺畅。 在实际应用时，可根据不同需求选用指数型 指标或标准化指标。对于不同驾驶风格的驾驶 员，可初步划分为驾驶平稳型和追求速度型，他 们对于上述 2 个指标是有着不同偏好的。为了综 合评判不同驾驶员对于最优轨迹曲线的要求，现 引入对于最优轨迹曲线的综合评判指标。 定义 6 综合评判指标 C ∗ = w1 · J ∗+w2 ·K ∗ (9) 称之为曲线 L 的综合评判指标，其中 w1、w2 为不同驾驶风格的驾驶员对于 J*、K*指标的权 重，可由专家评判给出。 综上可知，在众多轨迹曲线中选取一个最优 曲线，只需比较不同轨迹曲线的综合评判指标的 值，数值最大的曲线即为所求。 第 5 期 王星，等：基于邻域系统的智能车辆最优轨迹规划方法 ·1043·
·1044· 智能系统学报 第14卷 3最优轨迹曲线模型及其求解方法 设在节点0≤x<2<…<xn≤H-1上，取=3， 对于初始点满足 3.1最优轨迹曲线模型及其满意条件 y(x1)=0, 1=0 首先建立最优轨迹曲线的多目标优化模 y()=2,<<3 (13) 型一最优轨迹曲线模型对于标准可行领域 y(x3)=S,x3=H-1 Q内的轨迹集合T(xo),寻求最优轨迹曲线y(xo), 导数值满足 使得下列目标函数可取得极值 y(x1)=0 minT y(2)=y3 (14) minJy(x) (10) y(x3)=0 minK [y(x)] 式中O(x,y)、O(x,)为已知节点，因此需要确 限制条件为 定节点O2的坐标值和导数值。假设满意轨迹曲 y(xo)cr(xo)cQ 线对称，则节点O2的坐标值为曲线中点，导数值 T≤Tax (11) k是一个和邻域大小相关的量，可设初始值为 式中：T为智能车在标准可行邻域内完成规划的 ko=s/h-I (15) 轨迹所用的总时间；Tmx完成规划的轨迹能够接 受的最长时间；J、K分别为轨迹曲线的长度指数 和弯阻指数。目标函数的最优解y()为最优轨 迹曲线，此模型可简写为OTC模型。 尽管式(10)给出了最优轨迹曲线模型，但该 模型的一般求解是困难的。在实际问题中只需给 出一种实用的、可操作的构造方法即可。因此需 要给出满意曲线的满意条件。寻求满意曲线的过 图5智能车的邻域坐标系 程是一个筛选与尝试的过程，需要建立合理的限 Fig.5 Neighborhood of intelligent vehicles coordinate sys- 定规则，提高筛选与尝试的效率。参考图4的 tem 3条曲线，其中曲线B是一条符合生活经验的满 2)计算轨迹曲线指标。 意曲线，考虑到曲线B的特征，本文的规则如下： 将上述数据代入，函数x)在节点处的插值 规则1：车体轨迹应较为光滑。 多项式为 规则2：车体的末位置应尽可能满足底边中 (16) 点到邻域两边是等距的要求，即在邻域中部运动。 基于上述规则，满意条件如下： 根据多项式计算长度指数和逆舒指数，并选 定义7p水平满意集 择合适的权重，计算式(9)的综合评判指标C:,执 B={y(x)hw·Jy(x]+w2Ky(x≥pl (12) 行3)0 为曲线x)的p-水平满意集。 3)计算导数值。 由式(12)可知，根据目标阈值p,可求出满意 对于导数初值ko,确定搜索区间[ak,Bkl,其 曲线的集合B,若最优曲线的集合为C,易知CsB, 中a<1,B>l,设步长为1，对于每次迭代i,导数值为 因此可通过逐步迭代法来寻找满意曲线。 ki=(a+ti)ko (17) 3.2满意曲线的求解算法 合理调整步长，转2)，使得每次迭代的结果 如图5所示，为智能车的邻域坐标系，其中车 C:>C,直到C:的值达到p,则迭代终止。 体与可行邻域底部的中点距离为S,邻域长为H, 按照上述算法，本文以满意度指数p=0.8,权 车体长为1。假设轨迹曲线二阶光滑，其中初始位 重w1-0.4、1w2-0.6,所计算出的节点O2的坐标值和 置坐标为o(0,0),末位置坐标为(H-1,s),且二者一 一阶导数如下： 阶导数皆为O;Hermite插值法可以将函数值和导 1)节点坐标为 H-I s 2,2 为曲线的中点。 数值完全利用，根据插值节点的个数不同，可求 出不同的轨迹曲线，兼顾满意度和复杂性，本文 2)节点一阶导数为2H- 将插值节点的个数定为3个。则满意轨迹曲线的 3.3满意曲线的理论分析 迭代算法如下： 对于上述操作算法，首先证明最优轨迹曲线 1)确定初始值。 的存在性
3 最优轨迹曲线模型及其求解方法 3.1 最优轨迹曲线模型及其满意条件 y ∗ (x0) 首先建立最优轨迹曲线的多目标优化模 型—最优轨迹曲线模型 对于标准可行领域 Q 内的轨迹集合 Γ(x0 )，寻求最优轨迹曲线 , 使得下列目标函数可取得极值 minT min J [ y (x) ] minK [ y (x) ] (10) 限制条件为 { y (x0) ⊂ Γ(x0) ⊂ Q T ⩽ Tmax (11) Tmax y ∗ (x) 式中：T 为智能车在标准可行邻域内完成规划的 轨迹所用的总时间； 完成规划的轨迹能够接 受的最长时间；J、K 分别为轨迹曲线的长度指数 和弯阻指数。目标函数的最优解 为最优轨 迹曲线，此模型可简写为 OTC 模型。 尽管式 (10) 给出了最优轨迹曲线模型，但该 模型的一般求解是困难的。在实际问题中只需给 出一种实用的、可操作的构造方法即可。因此需 要给出满意曲线的满意条件。寻求满意曲线的过 程是一个筛选与尝试的过程，需要建立合理的限 定规则，提高筛选与尝试的效率。参考图 4 的 3 条曲线，其中曲线 B 是一条符合生活经验的满 意曲线，考虑到曲线 B 的特征，本文的规则如下： 规则 1：车体轨迹应较为光滑。 规则 2：车体的末位置应尽可能满足底边中 点到邻域两边是等距的要求，即在邻域中部运动。 基于上述规则，满意条件如下： 定义 7 p-水平满意集 B = { y (x)|w1 · J ∗ [ y (x) ] +w2 ·K ∗ [ y (x) ] ⩾ p } (12) 为曲线 y(x) 的 p-水平满意集。 C ⊆ B 由式 (12) 可知，根据目标阈值 p，可求出满意 曲线的集合 B，若最优曲线的集合为 C，易知 ， 因此可通过逐步迭代法来寻找满意曲线。 3.2 满意曲线的求解算法 如图 5 所示，为智能车的邻域坐标系，其中车 体与可行邻域底部的中点距离为 s，邻域长为 H， 车体长为 l。假设轨迹曲线二阶光滑，其中初始位 置坐标为 o(0，0)，末位置坐标为 (H-l，s)，且二者一 阶导数皆为 0；Hermite 插值法可以将函数值和导 数值完全利用， 根据插值节点的个数不同，可求 出不同的轨迹曲线，兼顾满意度和复杂性，本文 将插值节点的个数定为 3 个。则满意轨迹曲线的 迭代算法如下： 1) 确定初始值。 设在节点 0 ⩽ x < x2 < ··· < xn ⩽ H −l 上，取 n=3， 对于初始点满足 y (x1)=0, x1=0 y (x2)=y2, x1 < x2 < x3 y (x3) = s, x3=H −l (13) 导数值满足 y ′ (x1)=0 y ′ (x2) = y ′ 2 y ′ (x3)=0 (14) 式中 O1 (x1 , y1 )、O3 (x3 , y3 ) 为已知节点，因此需要确 定节点 O2 的坐标值和导数值。假设满意轨迹曲 线对称，则节点 O2 的坐标值为曲线中点，导数值 k 是一个和邻域大小相关的量，可设初始值为 k0 = s/h−l (15) O x y H s l 图 5 智能车的邻域坐标系 Fig. 5 Neighborhood of intelligent vehicles coordinate system 2) 计算轨迹曲线指标。 将上述数据代入，函数 f(x) 在节点处的插值 多项式为 H2n+1 (x)= ∑n i=1 Hi(x)· yi+ ∑n k=1 hk (x)· yk ′ (16) C ∗ i 根据多项式计算长度指数和逆舒指数，并选 择合适的权重，计算式 (9) 的综合评判指标 ，执 行 3)。 3) 计算导数值。 对于导数初值 k0，确定搜索区间 [αk0 ,βk0 ],其 中 α<1, β>1，设步长为 t，对于每次迭代 i，导数值为 ki = (α+ti) k0 (17) C ∗ i C ∗ i−1 C ∗ i 合理调整步长，转 2)，使得每次迭代的结果 > ，直到 的值达到 p，则迭代终止。 按照上述算法，本文以满意度指数 p=0.8，权 重 w1=0.4、w2=0.6，所计算出的节点 O2 的坐标值和 一阶导数如下： ( H −l 2 , s 2 ) 1) 节点坐标为 ，为曲线的中点。 3s 2(H−l) 2) 节点一阶导数为 。 3.3 满意曲线的理论分析 对于上述操作算法，首先证明最优轨迹曲线 的存在性。 ·1044· 智 能 系 统 学 报 第 14 卷