Convex Approximation Based Avoidance Theory and Path Planning MPC for Driver-less Vehicles
-
摘要: 提出了一种改进的无人驾驶车辆路径规划方法, 并搭建了相应的软件在环实时仿真系统, 对方法在结构化道路下的复杂动态交通工况进行性能验证.首先, 引入基于凸近似的避障原理, 对障碍物参考点的选取进行优化, 扩大了路径规划的可行域范围.采用改进后的方法, 并结合模型预测控制(Model predictive control, MPC)原理和曲线坐标系统, 综合考虑自车及障碍车的外形、道路几何约束及自车的机械结构约束、路径最短、侧向加速度、道路对中、逐次变道、车距安全度、左变道优先和前轮转角变化率等权重的影响, 实现了车辆在复杂动态交通工况下的路径规划.最后, 以长城H7运动多用途车作为无人驾驶实验及仿真平台, 搭建基于dSPACE多核架构的Carsim + Simulink软件在环实时仿真系统, 对算法进行验证.结果表明, 所提出的方法不仅可获得合理、平滑的行驶路径, 顺利避开运动障碍车的干扰, 而且具有良好的实时性.Abstract: An improved path planning algorithm for the driver-less vehicle is proposed in this paper, and a soft-ware in loop system is set up to evaluate its performance under complex dynamic traffic scenarios. First, a convex approximation based avoidance theory is introduced, and a method to optimize the obstacle's reference point is proposed for enlarging approachable region. Based on the proposed algorithm, the theory of MPC (Model predictive control) and the curvilinear coordination system, and nine key weighting factors are considered thoroughly to achieve an optimal path, including the dimensions of ego and obstacle vehicles, path geometric constraints and ego vehicle's mechanical constraints, shortest path, lateral acceleration, path alignment, lane changing successively, vehicle to vehicle safety distance, left lane changing priority and the rate of front wheel angle change. Finally, the GWM H7 SUV is used as the driver-less prototype vehicle, and a Carsim + Simulink based soft-ware in loop system is set up, via using the dSPACE multi-cores platform, in order to test the proposed algorithm. The simulation test results demonstrate that not only a reasonable and smooth path is achieved to avoid the disturbances from the moving vehicles, but also an expected real-time performance is obtained.
-
Key words:
- Driver-less vehicles /
- path planning /
- convex approximation /
- obstacle avoidance theory /
- model predictive control (MPC)
-
1. 引言
随着计算能力的提高和计算理论的创新,机器学习在过去30年中取得了长足的发展,正受到越来越多人的关注,并在生物、医药、能源、交通、环境等诸多领域中获得了成功的应用.与此同时,机器学习也面临越来越多的问题,传统机器学习理论框架的不足被逐渐发现和确认,新的机器学习理论框架不断被提出[1].
中科院自动化所王飞跃研究员于2004年提出了平行系统的思想,试图用一种适合复杂系统的计算理论与方法解决社会经济系统中的重要问题.其主要观点是利用大型计算模拟、预测并诱发引导复杂系统现象,通过整合人工社会,计算实验和平行系统等方法,形成新的计算研究体系[2-5].
在过去的10多年中,平行系统这一研究体系在实践中取得了大量的成果,并不断丰富和完善起来[6-9]. 近年来,我们尝试将平行系统的思想扩展并引入到机器学习领域建立一种新型理论框架以更好地解决数据取舍、行动选择等传统机器学习理论不能很好解决的问题.
以下我们将首先回顾常见的一些机器学习理论,并比较它们在数据获取---行动选择这一核心问题上的处理方式. 接着,我们将提出"平行学习"这一新型机器学习理论框架,并着重分析其独特之处. 最后我们总结全文.
2. 一些现有机器学习的理论框架
着眼于数据获取和行动选择之间的关系,我们可以建立如下数学模型来描述常见的一些机器学习理论框架:
假设我们获取到一系列数据并构成集合$X=\left\{ {x_i } \right\}$,$i=1,{\cdots},I$. 若研究对象为复杂系统,则这些数据通常为观测到的系统状态或输出. 针对这些数据,我们可以采取一系列行动$a_k $并构成集合$A=\left\{ {a_k ({X}')}\right\}$,$k=1,{\cdots},J$,${X}'\subseteq X$表示数据集$X$的一个子集. 每一个行动可以导致一个回报$R(a_j )$,且数据的获取和采取行动可以在时间上分离. 我们的目标是,通过机器学习,最大化长期回报
\begin{equation}\label{eq1} \mathop {\max }\limits_{a_j ,1\le j\le J}\sum\limits_{k=1}^J {R(a_k )}\end{equation}
(1) 如果我们关心的是每一个行动导致的损失$L(a_k )$,则目标函数可变为最小化长期损失
\begin{equation}\label{eq2} \mathop {\min }\limits_{a_k ,1\le k\le J}\sum\limits_{k=1}^J {L(a_k )}\end{equation}
(2) 对于常见的有监督学习(Supervised learning)[10-11]而言,上述这一模型可以进一步简化为: 当所有数据已知且已经被正确分类后,我们采取一个行动: 建立一个函数映射(通常是分类函数)来最小化分类误差.一般而言,我们预设数据服从独立同分布假设(Independent and identically distributed,i.i.d.),则目标函数可进一步写为
\begin{equation}\label{eq3} \mathop {\min }\limits_a L(a(X))=\mathop {\min}\limits_a \sum\limits_{i=1}^I {L(x_i ,a)}\end{equation}
(3) 相对于有监督学习,在线机器学习(Online machine learning)[12-14]强调了数据是逐渐获取的,且每新获得一个数据,系统可基于所有已经获取的数据采取一个行动.对于在线机器学习的特例序贯学习(Sequential learning),我们每次仅仅获取一个数据$x_i $,依据映射函数$f(\cdot)$产生一个预测行动$f(x_i )$,接着我们再获取$x_i$真正的标记数据$y(x_i )$,并计算由此产生的损失$L\left[{f(x_i),y(x_i )} \right]$. 最终我们的目标函数为选取合适的映射$f(\cdot )$,最小化长期后悔值(Regret value)
\begin{equation}\label{eq4} \mathop {\min }\limits_f L(a(X))=\mathop {\min}\limits_f \sum\limits_{i=1}^I {L\left[{y(x_i ),f(x_i )} \right]}\end{equation}
(4) 这里我们有多个行动,并随着所获数据的增多,不断优化采取的行动.
与在线学习类似,强化学习(Reinforcement learning)[15-16]依然假设数据逐渐获取,但机器学习系统不再被动地接受数据,而转为主动寻求.系统在$t$时刻每获得一个数据$x_i^{(t)} $ (在强化学习中$x_i$为系统状态),可采取一系列行动$a_i^{(t)} $. 为简化符号,下文中系统状态和行动记为$x_t $和$a_t $.强化学习允许我们在$t$时刻的行动$a_t $影响到我们在$\left( {t+1}\right)$时刻的获取的数据$x_{t+1} $,也即存在如下的$T(\cdot ,\cdot):X× A\to X$表示特定的状态转移函数
\begin{equation}\label{eq5} T(x_t ,a(x_t ),x_{t+1} )=\Pr \left( {x_{t+1} \vert x_t,a(x_t )} \right)\end{equation}
(5) 我们的目标函数为
\begin{eqnarray}\label{eq6} &\mathop {\max }\limits_a \sum\limits_{t=1}^\infty{T(x_t ,a(x_t ),x_{t+1} )}[{R_a (x_t ,a(x_t))}+\nonumber\\&~~{\gamma \cdot V(x_{t+1} )}]\end{eqnarray}
(6) 其中$R_a (x_t ,a(x_t ))$为$t$时刻系统处于状态$x_t$、施加行动$a(x_t )$所获得的即时回报,$V(x_{t+1})$为系统处于状态$x_{t+1} $的长期平均回报,$\gamma $为折扣因子.
因此,强化学习属于主动学习(Active learning)[17]的一种,我们可以选取特定的行动来兼顾优化目标函数和探索输入数据集合$X$.这相对于在线机器学习是非常重要的改进.
然而,经典的强化学习将数据获取和对应行动局限在马尔科夫决策过程(Markov decision processes)的框架中,限制了其能力的发挥.目前研究者提出了不少强化学习的变体,如深度强化学习(Deep reinforcement learning),但基本沿用了马尔科夫决策过程这一框架.这一做法虽然保证了一定范围内学习的有效性,却不能很好地应用到非马尔科夫决策过程.
强化学习不需要传统意义上的有标签数据,实际上其学习的过程就是不断更新数据标签的过程.但是它的学习效率并不高,需要跟环境进行大量交互从而获得反馈用以更新模型.当面临复杂系统大数据处理时,过高的系统状态维数常常使得可行解的探索变得十分困难[18-20].
3. 平行学习的理论框架
为了进一步拓展学习能力,特别是为了解决强化学习所面临的难题,我们提出如下图 1所示的平行学习的基本框架.其大致可以分为数据处理和行动学习两个互相耦合关联的阶段.
图 1 平行学习的理论框架图(虚线上方为通过软件定义的人工系统进行大数据预处理,虚线下方表示基于计算实验的预测学习和集成学习,以及平行控制和指示学习. 细线箭头代表数据生成或数据学习,粗线箭头代表行动和数据之间的交互.)Fig. 1 The theoretical framework of parallel learning (The part above the dash line focuses on big data preprocessing using software defined artificial systems; the part beneath the dash line focuses on predictive learning and ensemble learning based computational experiments,as well as parallel control and prescriptive learning. The thin arrows represent either data generation or data learning; the thick arrows present interactions between data and actions.)在数据处理阶段,平行学习首先从原始数据中选取特定的"小数据",输入到软件定义的人工系统中,并由人工系统产生大量新的数据.然后这些人工数据和特定的原始小数据一起构成解决问题所需要学习的"大数据"集合,用于更新机器学习模型[18].
在行动学习阶段,平行学习沿用强化学习的思路,使用状态迁移来刻画系统的动态变化,从人工合成大数据中学习,并将学习到的知识存储在系统状态转移函数中.但特别之处在于,平行学习利用计算实验方法进行预测学习(Predictive learning). 通过学习提取,我们可以得到应用于某些具体场景或任务的"小知识",并用于平行控制和平行决策.这里的"小"是针对所需解决具体问题的特定智能化的知识,而不是指知识体量上的小.
而平行控制和平行决策将引导系统进行特定的数据采集,获得新的原始数据,并再次进行新的平行学习,使系统在数据和行动之间构成一个闭环.不仅如此,我们还引入指示学习(Prescriptive learning)的思想,从另一个角度来重新结合数据和行动.
4. 平行学习的三大特色方法
在上述新型理论框架的基础上,我们展开说明平行学习采用的特色方法.
4.1 通过软件定义的人工系统进行大数据预处理
杂乱无序的数据难以学习. 基于平行理论,我们可以构建人工场景来模拟和表示复杂系统的特定场景,并将选取的特定"小数据"在平行系统中演化和迭代,以受控的形式产生更多因果关系明确、数据格式规整、便于探索利用的大数据,再把大数据浓缩成小知识、小智慧和小定律[2-9, 18].这一点也符合美国物理学家费曼(Richard Feynman)所说的名言"不是我创造的,我就不能理解" (What I cannot create,I do not understand)[21].
以业界当前研究的新热点"平行视觉" (Parallel vision)为例[22-25]. 我们根据实际采集的少量图像数据,提取特定要素,然后在模拟环境条件中加入新的变化(如改变摄像机朝向、光照和天气条件等)以得到更加多样化的虚拟数据.对虚拟实验产生的结果进行计算评估,我们可以校正视觉模型,并重新设计新计算实验,产生新的虚拟数据. 这一迭代将反复执行直到收敛.测试表明,结合虚拟数据和真实数据可以有效提高模型性能.
需要指出的是,平行学习中将用于产生虚拟数据的人工系统和分析数据的机器学习系统进行了一定程度的切分,允许直接在数据处理阶段进行采样.这为数据产生和数据分析添加了更多的灵活性,和传统机器学习主要由行动来驱动数据采集是不同的.
由于我们采用的是软件定义的人工系统,我们可以借助虚实互动的平行执行来在线优化人工系统模型,更好地实现对复杂系统的智能理解和数据采样.所有数据学习的结果都能用来对人工系统模型进行校正和升级. 因此,我们并非割裂数据产生和数据分析这两部分,而是将其看成一个整体的两面.
4.2 包含预测学习和集成学习的数据学习
在平行学习中,我们强调使用预测学习和集成学习来拓展经典学习方法.
1) 我们允许多个智能体(Agent) $O^n$,$n=1,{\cdots},N$共同学习,每个智能体可以独立地获取到一系列观测数据并构成集合$X^n=\left\{{x_i^n } \right\}$,$i=1,{\cdots},I^n$.每个智能体还可以独立地采取一系列行动并构成集合$A^n=\left\{ {a_k^n({X}'^n)} \right\}$,$k=1,{\cdots},J^n$,${X}'^n\subseteq X^n$表示数据集$X^n$的一个子集.
2) 每个智能体获取的数据和采取行动的次数和时间均独立. 首先,我们允许一个行动可以产生多个新的数据,而强化学习一次只能产生一个新的数据. 其次,强化学习要求获取数据和完成行动必须依次间隔执行,而平行学习允许获取数据和完成行动有着完全不同的频次和发生顺序.
3) 我们以平行世界的角度来看待系统状态的演化过程.将新获得的数据映射到平行空间中,我们可以通过大量长期的仿真迭代来预测和分析预期行动的结果,并最终将最优动作返回现实空间[2-8, 18].
基于上述三点扩展,我们可以放松数据和行动之间的耦合,极大地扩展现有的强化学习方法[26-27]. 其实,上述三点扩展已经在AlphaGo这一划时代的人工智能产品中得以体现[28].参见图 2所示,AlphaGo对于当前局面,使用蒙特卡洛树(Monte Carlo tree)方法,进行数盘20$\sim$30步的模拟测试下来探求局部最优的下法,这可以看作是使用智能体进行中长期仿真迭代来预测和分析预期行动的结果.同时,其数据的产生和行动的产生相对独立,不需时间对齐.AlphaGo利用输入的数万盘高手对局数据进行自我对战. 在和李世乭比赛之前,自我对战了3000多万盘. 这就是典型的实际小数据到虚拟大数据的过程.
LeCun在最近几年的演讲中反复以"蛋糕"比喻整个机器学习领域.而强化学习是蛋糕上的一粒樱桃,监督学习是蛋糕外面的一层糖霜,无监督学习(Unsupervised learning)[29-30]则是蛋糕胚.然而目前,糖霜和蛋糕胚之间还存在巨大的空白区域. 为此,LeCun在2016年认为预测学习可以来填补这一空白[31].
预测学习起源于认知心理学对于儿童学习方式的解释[32].其后被用来解释智能体如何从与环境的交互中学习特定知识[33-34].深入比较不难发现,预测学习和我们在过去10多年中所一直倡导的基于计算实验的平行系统方法[2-9]本质是一样的.简而言之,平行系统和预测学习的核心就是用机器给真实环境建模,仿真预测可能的未来,并通过观察和演示来理解世界如何运行的能力.其中仿真是无监督或半监督(Semi-supervised learning)[35-36]的,而初始状态和最终结果是有监督的.我们称这种学习方式为平行预测+指示学习(Parallel predictive+Prescriptive learning),可以糅合无监督、半监督和有监督三种学习方式,填补各自之间的空白.
4) 类比于多智能体系统[37-38],平行学习还允许分散学习和集成学习两种机制.
分散学习机制要求每个智能体可以独立根据自身获取的数据来进行行动,每一个行动可以导致一个回报$R(a_k^n )$.我们的目标是最大化所有智能体的总体长期回报
\begin{equation}\label{eq7} \mathop {\max }\limits_{a_k^m ,1\le k\le J,1\le m\le N}\sum\limits_{m=1}^N {\sum\limits_{k=1}^J {R^m(a_k^m )} }\end{equation}
(7) 该学习机制适合于分散控制等问题,其中每个智能体获得的数据和执行的行动都是时空局部、甚至可以时间异步的.例如,我们在分布式平行交通控制系统中设定不同路口的控制器进行迭代和学习,协同式产生和发现最优的交通信号灯控制策略[7-8].
集成学习机制则要求设置一个所谓代理智能体(Surrogate agent).每个智能体可以独立地根据自身获取的数据来进行行动,每一个行动可以导致一个回报$R^m(a_k^m )$.我们的目标是选取所有这些智能体可能获得的回报中最大的那个动作,并让代理智能体执行该动作.
\begin{equation}\label{eq8} \mathop {\arg \max }\limits_{a_k^m ,1\le k\le J,1\le m\le N} \sum\limits_{m=1}^N {R^m(a_k^m )}\end{equation}
(8) 该学习机制类似于现有的集成学习(Ensemble learning)[39],可适合于静态数据的集中分类等问题. 而我们的研究表明,更为广义的集成学习技术也可以应用于动态系统的建模和控制之中[40].其中每个智能体都致力于在学习中对复杂系统进行建模并执行特定的行动来达到某一优化目标.各智能体执行的行动是时间同步,但所获取的数据可以是时空局部的.特别地,我们可以设定策略使得每个Agent根据自身偏好来探索输入数据集的不同部分,并建立适合特定输入数据子集的行动策略[40].这一想法亦被我们用在所谓平行动态规划(Parallel dynamic programming)之中,以克服现有近似动态规划算法对于解空间探索不足的困难[41].
4.3 基于默顿定律实现数据---行动引导的指示学习
一般而言,复杂系统可以大致分为牛顿系统和默顿系统两种.无论我们怎么对牛顿系统进行分析,都不会影响系统运行的结果.例如天气预报明天下雨,那么天气是下雨下雪还是刮风,跟我们的分析调控无关. 而在默顿系统中,存在双向影响通路,我们对系统的调控会影响系统运行的结果. 例如,著名分析师对于股市的评论会影响股市的波动. 因此,我们可以设定预期的系统状态,通过对于系统的描述、预测、引导来使得系统达到控制者所期望的状态.美国社会学家默顿将这一长期行动称为预言的自我实现定律(Self-fulfilling prophecy)[42]. 该定律也被后人称为默顿定律.
默顿定律希望通过改变行动的模式,即实际系统与人工系统的平行互动,促使实际系统运行到既定目标. 然而与牛顿系统不同,默顿系统中的"行动建模"与"目标建模"相互独立,且"行动建模"受到有限先验知识,系统高度随机性等多方面因素的影响,难以实现[43]. 如果用上面的学习框架来描述,就是难以确知我们每一次探索所获得的即时回报$R_a (x,a(x))$,而且即时回报$R_a (x,a(x))$和长期回报$V(x)$之间的关系亦不明确.
幸运的是,近10年来研究者先后提出了对抗学习(Adversarial learning)[44-46]、对偶学习(Dual learning)[47]等全新的学习原则,为解决上述问题提出了新的思路.
对抗学习通过构造相互竞争的生成器和辨别器来提高学习的效率[44-46].在图像学习中,前者试图产生假的图像,后者试图鉴别出真正的图像.本质上,这依然是费曼所称"不是我创造的,我就不能理解"概念的体现,即通过构建验证过的概念来理解事物.但对抗学习最大的优点是系统的回报/损失函数不必显式给出,而是通过生成器和辨别器的对抗来自动学习和挖掘来产生.这是默顿定律所期待的,在系统和行动的互动之中,达成知识的"泛化"(Generalization).
对偶学习[47]的思路则更加偏重迭代演进.假设学习过程中有两个智能体分别从事原任务(从集合$X$到集合$Y$的学习任务)和对偶任务(从集合$Y$到集合$X$的学习任务).假如我们首先把集合$X$用第一个智能体的模型$F$映射成集合$Y$的子集$Y'$,再利用第二个智能体的模型$G$把集合$Y'$映射成集合$X$的子集$X'$.比较集合$X$和$X'$,我们常常可以获得非常有用的反馈信号来改进映射模型$F$和$G$.以机器翻译为例,上面的这个过程可以无限循环下去. 可以证明,只要机器翻译模型 $F$ 和 $G$ 的解码部分都使用的是随机算法,这一学习过程是收敛的,最终会学到两个稳定有效的模型$F$和$G$.
综合对抗学习和对偶学习,我们可以提出如下更一般的指示学习.指示学习关注如何设置引导,使得我们获得预期的学习目的或者学习效果[48].具体到大数据环境中的数据获取--数据学习这一矛盾关系中,指示学习可以被建模为反复循环的两阶段学习--探索过程.
假设我们不断地获取数据并构成集合$X=\left\{ {x_i } \right\}$,$i=1,{\cdots},I$. 针对这些数据,我们可以采取一系列行动并构成集合$A=\left\{ {a_k (X)} \right\}$,$k=1,{\cdots},J$.
在第一阶段,我们学习特定行动原则,最大化阶段性回报$V(X,a_k (X))$
\begin{equation}\label{eq9} \mathop {\max }\limits_{a_k ,1\le k\le J} V(X,a_k (X))\end{equation}
(9) 在第二阶段,我们在此基础上通过数据生成算法产生新的数据集合${X}'=\left\{ {{x}'_i} \right\}$,$i=1,{\cdots},I$,并衡量阶段性损失$L\left[{{X}',a_k({X}'))} \right]$. 损失函数$L\left[\cdot\right]$为已学会的行动原则在新数据集合${X}'$上的损失,该函数指示了我们下一步学习的方向. 对于对抗学习而言,$L\left[\cdot\right]$可以直接设为误分类比率. 对于对偶学习而言,$L\left[\cdot\right]$为迭代产生的映射误差. 对于平行系统控制而言,$L\left[\cdot\right]$通常可以设为当前系统状态和理想系统状态之间的差值[7-9].
当上述两个阶段过程完成后,我们进入新的循环,直到我们覆盖所有的数据集或系统状态,又或者我们已经到达理想的系统状态.
目前,强化学习已经为我们在第一阶段的数据学习提供了相当强的理论工具和方法.但我们对于第二阶段的数据探索尚有很多未知的领域值得深入研究.原始的对抗学习中,数据产生的方式是无模型无监督学习,但其效果有待改进[44]. 而对偶学习中,数据产生的方式是有模型无监督学习,理论证明清晰但限制较多[47]. 最近的研究表明,类似于我们在上文中提及的平行仿真和预测学习这种半监督、具有限定条件和指示性目标的演化式学习(例如利用信息熵的InfoGAN[49])可能更加适合特定问题的解决.这即是我们在上文中提到的平行预测+指示学习(Parallel predictive +Prescriptive learning)的思想的体现: 既有方向性指示,亦不过多限制中间探索过程.我们期待这一思想能带来更多新的机器学习方法.
5. 总结
在本文中,我们提出平行学习的基本思想和理论框架,并阐述了平行学习的三大特色方法:1) 通过软件定义的人工系统进行大数据预处理,2) 包含预测学习、集成学习的数据学习,和3) 基于默顿定律实现数据--行动引导的指示学习.
概括而言,平行学习理论框架强调:使用预测学习解决如何随时间发展对数据进行探索;使用集成学习解决如何在空间分布上对数据进行探索;使用指示学习解决如何探索数据生成的方向.目前我们的研究显示,扩展现有的强化学习模型能够较好地和这三者结合.但我们不排除今后有更好的模型来和我们提出的平行学习理论框架结合发展.
需要指出的是,我们主要强调从理论框架层面改进和扩展已有机器学习方法,并初步开展了相应模型和算法的研究.例如我们将平行学习方法应用到了虚拟场景生成和无人驾驶车辆智能测试[50-51],以及社会计算和情报处理[52-54].但很多细节之处尚需完备的理论证明. 期待本文抛砖引玉,引起业内专家学者兴趣,共同对机器学习理论做出更加深入的革新.
-
表 1 长城H7车辆参数值
Table 1 Vehicle parameters of the GWM H7
参数 数值 单位 参数 数值 单位 $k_f$ $-$111187 N/rad $I_z$ 3522.1 ${\rm {kg\cdot m}}^{2}$ $k_r$ $-$90773 N/rad $M_v$ 2211 kg $a$ 1.25 m $v_r$ 6 m/s $b$ 1.59 m 表 2 MPC控制系统参数
Table 2 Parameters of MPC system
参数 数值 参数 数值 $k_1$ 0.3 $k_6$ 0.2 $k_2$ 8 $k_7$ 0.7 $k_3$ 3 $N$ 3 $k_4$ 2.5 $N_{\mu}$ 1 $k_5$ 15 符号 说明 单位 $a/b$ 前/后轴距离质心的距离 m ${\pmb d_{\ast}}$ 自车外观几何形状向量 m $D_{0}$ 自车停车时自车和障碍车之间的距离 m $I_{z}$ 车辆绕$z$轴的转动惯量 kg$\cdot$s$^2$ $k_{f/r}$ 前/后轮的侧倾刚度 N/rad $l$ 车的轴距 m $M$ 障碍车的数量 $M_{v}$ 车辆质量 kg $N/N_{u}$ 预测/控制步长 $o_{L}$ 车辆质心点$p_{0}$投影到中间车道的最短距离 m $OXY/o_{V}x_{V}y_{V}/o_{L}x_{L}y_{L}$ 大地/车辆/道路坐标系 ${\pmb p}$ 可行域中的点 m ${\pmb p_{0}}$ 自车质心位置 m ${\pmb q_{\ast}}$ 障碍车参考点 $r$ 自车凸多边形外形端点数 $R$ 车辆转弯半径 m $s_{*}$ 障碍车凸多边形外形端点数 $S_{L}$ 车辆质心偏移中间道路的位移量 m $S_{L_ {\rm max/min}}$ 左/右道路边缘的极限位置偏移量 m $t$ 采样时间 s $v_{f/r}$ 自车前/后轴速度 m/s $v_{l}$ 障碍车速 m/s $v_{la/lg}$ 质心的侧/纵向速度 m/s $\dot{v_{la}}$ 质心的侧向加速度 m/s$^{2}$ $v_{rel}$ 自车和障碍车之间的相对速度 m/s ${\pmb w_{\ast}}$ 障碍车(物)外观几何形状向量 m $W_{c}$ 车宽 m $W_{L}$ 实时测得的车道宽 m $x/y$ 自车质心在大地坐标系下的横/纵坐标 m $\dot{x}/\dot{y}$ 质心沿大地坐标系$X/Y$轴的速度 m/s $\delta_{f}$ 前轮转角 rad $\mu_{*}$ 缩放系数 ${\pmb w}$ 障碍车(物)内部点 m $\varphi/\dot{\varphi}/\ddot{\varphi}$ 航向角/横摆角速度/角加速度 rad/rad/s/rad/s$^2$ $\gamma$ 实际车距与安全车距的比值 -
[1] How google's self-driving car works [Online], available: http://news.discovery.com/autos/how-google-self-driving-car-works-111018.html, January 1, 2013 [2] DARPA grand challenge [Online], available: http://en.wikipedia.org/wiki/DARPA Grand Challenge. January 1, 2013 [3] 姜岩, 龚建伟, 熊光明, 陈慧岩.基于运动微分约束的无人车辆纵横向协同规划算法的研究.自动化学报, 2013, 39(12): 2012-2020 doi: 10.3724/SP.J.1004.2013.02012Jiang Yan, Gong Jian-Wei, Xiong Guang-Ming, Chen Hui-Yan. Research on diferential constraints-based planning algorithm for autonomous-driving vehicles. Acta Automatica Sinica, 2013, 39(12): 2012-2020 doi: 10.3724/SP.J.1004.2013.02012 [4] Khatib O. Real-time obstacle avoidance for manipulator and mobile robot. The International Journal Robotics Research, 1986, 5(1): 90-98 doi: 10.1177/027836498600500106 [5] Mcfetridge L, Ibrahim M Y. A new methodology of mobile robot navigation: The agoraphilic algorithm. Robotics and Computer-Integrated Manufacturing, 2009, 25(3): 545-551 doi: 10.1016/j.rcim.2008.01.008 [6] Zhang Q S, Chen D D, Chen T. An Obstacle Avoidance Method of Soccer Robot Based on Evolutionary Artificial Potential Field. Energy Procedia Part C, 2012, 16: 1792-1798 doi: 10.1016/j.egypro.2012.01.276 [7] 杜广龙, 张平.基于人工势场的机器人遥操作安全预警域动态生成方法.机器人, 2012, 34(1): 44-49 http://d.old.wanfangdata.com.cn/Periodical/jqr201201007Du Guang-Long, Zhang Ping.A method for generating dynamic security warning region in robotic teleoperation based on artificial potential field. Robot, 2012, 34 (1): 44-49 http://d.old.wanfangdata.com.cn/Periodical/jqr201201007 [8] Howden W E. The sofa problem. The Computer Journal, 1968, 11(3): 299-301 doi: 10.1093/comjnl/11.3.299 [9] Guernane R, Achour N. Generating optimized paths for motion planning. Robotics and Autonomous Systems, 2011, 59(10): 789-800 doi: 10.1016/j.robot.2011.06.001 [10] 张纯刚, 席裕庚.全局环境未知时基于滚动窗口的机器人路径规划.中国科学(E辑), 2001, 31(1): 51-58 http://d.old.wanfangdata.com.cn/Periodical/zgkx-ce200101008Zhang Chun-Gang, XI Yu-Geng. Robust window-based robot path planning when the global environment is unknown. Chinese Science (E), 2001, 31(1): 51-58 http://d.old.wanfangdata.com.cn/Periodical/zgkx-ce200101008 [11] 刘春明, 李兆斌, 黄振华, 等.基于LSPI和滚动窗口的移动机器人反应式导航方法.中南大学学报(自然科学版), 2013(03): 970-977 http://d.old.wanfangdata.com.cn/Periodical/zngydxxb201303016Liu Chun-Ming, Li Zhao-Bin, Huang Zhen-Hua, et al. A reactive navigation method of mobile robots based on LSPI and rolling windows. Journal of Central South University (Science and Technology), 2013(03): 970-977 http://d.old.wanfangdata.com.cn/Periodical/zngydxxb201303016 [12] Chou C, Lian F, Wang C. Characterizing indoor environment for robot navigation using velocity space approach with region analysis and look-ahead verification. IEEE Transactions on Instrumentation and Measurement, 2011, 60(2): 442-451 doi: 10.1109/TIM.2010.2058531 [13] Bemporad A, Rocchi C. Decentralized linear time-varying model predictive control of a formation of unmanned aerial vehicles. In: Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC) Orlando, FL, USA: IEEE, 2011. 7488-7493 [14] Bemporad A, Pascucci C, Rocchi C. Hierarchical and hybrid model predictive control of quadcopter air vehicles. In: Proceedings of the 3rd IFAC Conference on Analysis and Design of Hybrid Systems, Zaragoza, Spain: Elsevier, 2009. [15] Zhi J Z, Schmerling E, Pavone M. A convex optimization approach to smooth trajectories for motion planning with car-like robots. In: Procedings of IEEE 54th Annual Conference on Decision and Control (CDC), Osaka, Japan: IEEE, 2015. [16] Quinlan S, Khatib O. Elastic bands: Connecting path planning and control. in Proc. IEEE Conference on Robotics and Automation, Atlanta, GA, May 1993(2): 80-807 [17] Janson L, Schmerling E, Clark A, Pavone M. Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. International Journal of Robotics Research, 2015, 34(7): 883-921 doi: 10.1177/0278364915577958 [18] Tian Y G, Dolan J M, Lee J W. Runtime-bounded tunable motion planning for autonomous driving. In: Proceedings of the 2016 IEEE Intelligent Vehicles Symposium (Ⅳ), Gothenburg, Sweden: IEEE, 2016. 1301-1306 [19] Tian Y G, Atwood J, Chi Y D, Dolan J M, Lee J W. Tunable and stable real-time trajectory planning for urban autonomous driving. In: Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2015. 250-256 [20] Ryu J H, Ogay D, Bulavintsev S, Kim H, Park J S. Development and experiences of an autonomous vehicle for high-speed navigation and obstacle avoidance. Frontiers of Intelligent Autonomous Systems. Springer, 2013: 105-116 [21] T Berglund, A Brodnik, H Jonsson, M Staffanson, I Soderkvist. Planning smooth and obstacle-avoiding b-spline paths for autonomous mining vehicles. IEEE Transactions on Automation Science and Engineering, 2010, 7(1): 167-172 doi: 10.1109/TASE.2009.2015886 [22] Perez J, Lattarulo R, Nashashibi F. Dynamic trajectory generation using continuous-curvature algorithms for door to door assistance vehicles. Intelligent Vehicles Symposium Proceedings, IEEE, 2014: 510-515 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0214340693 [23] Petrov P, Nashashibi F. Modeling And Nonlinear Adaptive Control for Autonomous Vehicle Overtaking. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(4): 1643-1656 doi: 10.1109/TITS.2014.2303995 [24] Brezak M, Petrovic I. Real-time Approximation of Clothoids With Bounded Error for Path Planning Applications. IEEE Transactions on Robotics, 2014, 3(2): 507-515 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4a6528809b11cf384afa45538b6d5a21 [25] Funke J, Theodosis P, Hindiyeh R, Stanek G, Kritatakirana K, Gerdes C, Langer D, Hernandez M, Muller-Bessler B, Huhnke B. Up to the limits: Autonomous audi TTS. In: Rroceedings of the Intelligent Vehicles Symposium, June 2012: 541-547 [26] Junsoo Kim, Kichun Jo, Wontaek Lim, Minchul Lee, Myoungho Sunwoo. Curvilinear-Coordinate-Based Object and Situation Assessment for Highly Automated Vehicles. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3): 1559-1575 doi: 10.1109/TITS.2014.2369737 [27] Chu K, Lee M, Sunwoo M. Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(4): 1599-1615 doi: 10.1109/TITS.2012.2198214 [28] Kim J H, Kum D S. Threat Prediction Algorithm based on Local Path Candidates and Surrounding Vehicle Trajectory Predictions for Automated Driving Vehicles. In: Proceedings of the 2015 IEEE Intelligent Vehicles Symposium (Ⅳ), COEX, Seoul, Korea: IEEE, 2015. 1220-1225 [29] Barfoot T D, Clark C M. Motion Planning for Formations of Mobile Robots. Robotics and Autonomous Systems, 2004, 45: 65-78 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=cd879d19070c8114dcc0b35a6f7de20a [30] Wang H, Kearney J, Atkinson K. Robust and Efficient Computation of The Closest Point on A Spline Curve. In: Procedings of 5th International Conference Curves Surfaces, 2002: 397-406 [31] 席裕庚.预测控制(第二版).北京:国防工业出版社, 2013.Xi Yu-Geng. Predictive Control (Second Edition). Beijing: National Defense Industry Press, 2013. [32] 郭烈, 葛平淑, 张明恒, 李琳辉, 赵一兵.汽车安全辅助驾驶技术.北京:北京大学出版社, 2014.Guo Lie, Ge Pin-Shu, Zhang Ming-Heng, Li Lin-Hui, Zhao Yi-Bing. Automobile Driving Assisted Driving Technology. Beijing: Peking University Press, 2014. [33] 刘明明, 崔春风, 童小娇, 戴彧虹.混合整数非线性规划的算法软件及最新进展, 中国科学:数学, 2016, 46(1): 1-20 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgkx-ca201601001Liu Ming-Ming, Cui Chun-Feng, Tong Xiao-Jiao, Dai Yu-Hong. Algorithm Software for Mixed Integer Nonlinear Programming and Recent Progress, Scientia Sinica (Mathematica) 2016, 46(1): 1-20 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=zgkx-ca201601001 [34] 陈宝林.最优化理论与算法.北京, 清华大学出版社, 2005.Chen Bao-Lin. Optimization Theory and Algorithm. Beijing, Tsinghua University Press, 2005. [35] Powell M J D. The convergence of variable metric methods for nonlinearly constrained optimization calculations. Nonlinear Programming 3, (O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.), Academic Press, 1978. [36] Constrained Optimization, Sequential Quadratic Programming (SQP), Optimization Toolbox User's Guide. Mathworks Inc, 2016. [37] Andersen H, Zhuang J C, You H E, Pendleton S, Marcelo H A. Geometric path tracking algorithm for autonomous driving in pedestrian environment. In: Proceedings of the 2016 IEEE International Conference on Advanced Intelligent Mechatronics (AIM), Bahff, Canada: IEEE, 2016. 1669-1674 -