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所示).这里直接销售给顾客与进行热轧的钢产品由于需求目的的不同, 对钢级的要求也不同, 所以在均热炉中均热的温度与时间往往是不同的, 因此一般情况下目的相同的钢锭可以组成批进行均热, 而目的不同的钢锭不组成批, 即批是不可兼容的.此外, 两个不同目的的钢锭集合到达批处理机上加工的到达时间可以看作两类不同的释放时间.基于上述初轧阶段的生产特点, 为了满足两个不同目的的生产需求, 同时也为了提高初轧阶段的生产效率、降低能耗, 如何在批处理机上对工件进行组批, 调度两个工件集合的加工顺序是至关重要的研究问题之一.
下面将给出一个具体的实例来解释我们所研究的一台批处理机上具有两类释放时间的工件集竞争调度问题.在上面描述的钢锭初轧生产过程中, 假设热轧阶段需要$\rm 3$个钢产品, 对应的钢锭工件集合为$J^A=\{J^A_1, J^A_2, J^A_3$}.顾客需要直接购买$\rm 2$个钢产品, 对应的钢锭工件集合为.每个钢锭的加热时间分别为集合$J^A$中工件的共同释放时间为$r^A=0$, 集合$J^B$中工件的共同释放时间为$r^B=2$.批处理机的能力为$b=2$, 不同集合的工件不能组成批加工.所考虑的目标函数为在满足集合$J^B$中工件的最大完工时间$C^B_{\max}$不超过一个给定上界$Q_B=7$的约束下, 最小化集合$J^A$中工件的最大完工时间$C^A_{\max}$.具体的参数介绍见第1节中问题描述.对于上述实例, 我们能获得一个最优调度$\pi$满足$C^B_{\max}=6＜Q_B$的条件下集合$J^A$工件的最大完工时间最小值为$C^A_{\max}=4$ (如图 2所示).最优调度不仅满足了顾客的需求, 同时通过最小化热轧阶段所需工件的最大完工时间, 为热轧阶段提高了生产效率.
近几年来, 两个或多个工件集竞争调度的问题作为调度领域中多目标问题的特殊情况备受学者们的关注, 其中每个工件集有各自的优化目标.不同目标工件集的存在使得问题的求解比所有工件对应一个工件集的情况更加困难.多个工件集竞争的调度问题最初由Baker等[1]以及Agnetis等[2]提出, 前者研究了单机上最小化两个工件集目标函数线性组合形式问题的复杂性, 后者研究了单机上依赖两个工件集不同目标函数的有约束优化形式及帕累托形式问题的复杂性.关于多个工件集竞争的调度问题, 读者可参阅Perez-Gonzalez等[3]以及Agnetis等[4].本文主要研究两个工件集目标函数有约束优化的形式, 即找到一个最优调度最小化一个工件集的目标函数使得另一个工件集的目标函数不超过一个给定上界的问题.下面主要针对两个工件集竞争的有约束优化调度问题进行简单综述.
关于单机批处理机上两个工件集竞争的调度问题, Li等[5]提出了多项式或伪多项式时间的算法来求解无界批处理机上批不可兼容与批可兼容两种情况下各种正则目标函数结合的调度问题, 其中针对批不可兼容问题与分别提出了时间复杂度为$\rm O$$(nn_An_B\log(Q_U-Q_L))$与$(nn_An_BP)$的算法, 这里$IF$表示批不可兼容, 具体参数请见文献[5]. Agnetis等[4]针对无界批处理机上批不可兼容的问题与分别提出了时间复杂度为与$\rm O$$(n_A+n_B^4)$的多项式时间算法. Fan等[6]针对有界批处理机上批不可兼容时问题提出了时间复杂度为$\rm O$的最优算法, 同时证明了上述问题当批可兼容情况下以及批不可兼容情况下问题均为NP—难问题.最近, Wang等[7]研究了有界批处理机上工件具有不同尺寸大小、加工时间相同的两个工件集竞争调度问题, 证明出目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集的最大完工时间不超过给定上界问题, 不存在多项式时间算法具有常数的最坏情况比, 同时提出了一个有效算法获得最优解的下界以及两个启发式算法对问题进行求解.虽然上面的文献考虑了批处理机上两个工件集竞争的调度问题, 但所考虑的问题都是工件具有相同的释放时间. Tang等[8]研究了单机无界批处理机与有界批处理机上工件具有恶化加工时间的两个工件集竞争调度问题, 基于批的兼容性与工件释放时间的差异性, 作者对一些目标函数的结合给出了时间复杂性, 其中当批不可兼容且工件存在不同释放时间时, 针对批无界问题提出了时间复杂度为$(n_An_Bn\log(Q_U^\prime-Q_L^\prime))$的最优求解算法, 同时证明出批有界问题对于批可兼容与不可兼容两种情况均为NP—难问题, 具体参数请见文献[8].
关于单机上具有释放时间的两个工件集竞争调度问题, Yin等[9]证明了问题为强NP—难问题, 并提出了分支定界算法进行求解. Lee等[10]对问题提出了分支定界算法与遗传算法进行求解. Wu等[11]证明了问题为强NP—难问题, 同时提出了分支定界算法、蚁群算法以及遗传算法对问题进行求解. Cheng等[12]对问题提出了分支定界算法以及模拟退火算法进行求解.以上文献虽然考虑了工件带有不同的释放时间, 但都是利用智能算法对问题提出近优算法进行求解, 没有从理论分析的角度对具有不同释放时间的两个工件集竞争调度问题进行研究. Dover等[13]研究了单机上工件具有相同加工时间与不同释放时间的两个工件集竞争调度问题, 对各种正则目标函数的结合给出了时间复杂性.
另一方面, 关于批处理机上的调度问题也有许多学者研究.一台批处理机可以同时加工多个工件, 一批的加工时间为该批中工件加工时间最大者, 同一批的所有工件同时开始加工同时结束, 一旦一批开始加工就不能中断, 也不能再加入其他的工件到该批. Potts等[14]对批处理机上的调度问题进行了综述.根据批处理机的能力, 可以分为无界批处理机与有界批处理机. Brucker等[15]研究了单机批无界与批有界两种情况下工件具有相同释放时间的各种目标函数的时间复杂性. Lee等[16]研究了单机批处理机上工件具有不同释放时间, 目标函数为最小化工件最大完工时间问题的时间复杂性, 对批无界情况提出了多项式时间动态规划算法, 对批有界情况当工件具有两类释放时间时提出了伪多项式时间的动态规划算法进行求解, 对一般情况提出了启发式算法. Liu等[17]同样对于上述目标函数证明了批有界情况下问题为NP—难问题, 并对工件具有有限个释放时间情况提出了伪多项式时间算法, 对一般情况设计了贪婪算法. Liu等[18]针对有界批处理机上工件具有不同释放时间的最小化总完工时间问题提出了一个多项式时间近似策略, 针对无界批处理机上工件具有不同释放时间的最小化总加权完工时间问题提出了一个伪多项式时间近似策略.
综上, 目前还没有存在关于工件具有两类释放时间的两个工件集在批处理机上竞争调度问题的研究, 虽然文献[8]中针对无界批处理机上批不可兼容情况下工件具有恶化加工时间与不同释放时间时, 目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集最大完工时间不超过给定上界问题的一般情况提出了伪多项式时间求解算法, 但本文基于问题的自身特征针对该目标函数在批无界与不可兼容情况下工件具有两类释放时间的特殊情况提出了多项式时间求解算法, 同时针对批无界情况下最小化最大延迟与总完工时间问题分别提出了最优求解方法.此外, 对于批有界情况下工件具有不同释放时间时, 目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集的最大完工时间不超过给定上界问题, 文献[8]针对一般情况证明了问题的$\rm NP$-难性, 而本文进一步证明了当两个工件集具有两类释放时间的特殊情况也均为NP—难问题, 同时分别提出了伪多项式时间的动态规划算法对问题进行求解.这样的研究不仅为实际工业生产提供了理论指导依据, 而且从理论上丰富了多个工件集竞争调度的理论研究基础.
1. 问题描述
设有两个工件集合$J^A$和$J^B$, 其中, $J^B=\{J^B_1, J^B_2, \cdots, J^B_{n_B}\}$.设$n$表示两个集合中所有的工件数, 即$n=n_A+n_B$.两个集合中的工件同时竞争在一台批处理机上不可中断地加工, 批处理机能同时加工$b$个工件作为一批.本文假设只有来自同一集合的工件能组成批加工, 即批不具有兼容性.假设工件$J^X_j$具有加工时间$p^X_j$, 工期$d^X_j, $ 批处理机上一批$B_x$的加工时间定义为$p(B_x)=\max_{J^X_j\in{B_x}}\{p^X_j\}$, 工期为$d(B_x)=\min_{J^X_j\in{B_x}}\{d^X_j\}$.每个集合的工件具有共同的释放时间$r^X$, $X\in\{A, B\}$, 即如果工件$J_j^X\in J^X$, 那么它的释放时间为$r^X$.由于两个集合的工件具有两类不同的释放时间, 为了便于问题的分析, 不妨假设其中较小的释放时间记为0, 较大的释放时间记为$r(r>0)$.此外, 假设所有问题中参数均为非负整数.给定一个加工顺序, 定义工件$J^X_j$的完工时间为$C^X_j$, 延迟为$L^X_j=C^X_j-d^X_j$.本文基于两类释放时间的大小比较, 分别考虑了批处理机能力无界$(b>n)$情况, 即批处理机能同时加工任意多个工件作为一批, 与批处理机能力有界$(b<n)$情况, 即批处理机最多能同时加工$b$个工件作为一批.主要研究的目标函数分别为最小化集合$J^A$中工件的最大完工时间$C_{\max}^A=\max\{C^A_j\}, $最大延迟$L_{\max}^A=\max\{L^A_j\}, $总完工时间$\sum C_j^A$, 使得集合$J^B$中工件的最大完工时间$C_{\max}^B=\max\{C^B_j\}$不超过一个给定的上界$Q_B>0.$利用文献[2]提出的表示法, 所研究问题表示为
;
其中$p-batch$表示批处理机.
2. 批处理机能力无界
本节将考虑批处理机能力无界的情形.针对两个工件集各自释放时间$r^A$与$r^B$的大小关系, 分别研究了最小化工件集$J^A$中工件的最大完工时间、最大延迟以及总完工时间, 使得另一个工件集$J^B$中工件的最大完工时间不超过一个给定上界问题的时间复杂性.
2.1 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$
首先对于求解本节的问题提出如下最优解性质.
性质1. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么在最优调度中工件集$J^A$与$J^B$的工件分别形成一批生产加工.
证明. 由于一批的容量是无限大的, 所以将集合$J^A$与$J^B$的工件分别在各自释放时间之后形成一批生产加工, 将不会增加各自工件的最大完工时间.
下面基于性质1, 同时针对$r^A$与$r^B$的大小比较, 分别对两种不同情况问题给出多项式时间最优求解算法.
1) $r^A=0, r^B=r$
算法1.
步骤1. 如果, 那么当$\max\{p_j^A\}\leq r$时, 在最优调度中从0时刻开始加工集合$J^A$中工件构成的一批, 从$r$时刻开始加工集合$J^B$中工件构成的一批; 当$\max\{p_j^A\}>r$时, 在最优调度中从0时刻开始加工集合$J^A$中工件构成的一批, 从$\max\{p_j^A\}$时刻开始加工集合$J^B$中工件构成的一批.如果$\max\{\max\{p_j^A\}, r\}+\max\{p_j^B\}>Q_B$, 那么转到步骤2.
步骤2. 如果$\max\{p_j^A\}\leq r$, 那么问题没有解.如果$\max\{p_j^A\}>r$, 那么在最优调度中从$r$时刻开始加工集合$J^B$中工件构成的一批, 从$r+\max\{p_j^B\}$时刻开始加工集合$J^A$中工件构成的一批.
2) $r^A=r, r^B=0$
算法2.
步骤1. 如果$r+\max\{p_j^A\}+\max\{p_j^B\}\leq Q_B$, 那么在最优调度中从$r$时刻开始加工集合$J^A$中工件构成的一批, 从$r+\max\{p_j^A\}$时刻开始加工集合$J^B$中工件构成的一批.如果$r+\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 那么转到步骤2.
步骤2. 如果$\max\{p_j^B\}\leq Q_B$, 那么在最优调度中从0时刻开始加工集合$J^B$中工件构成的一批, 从$\max\{\max\{p_j^B\}, r\}$时刻开始加工集合$J^A$中工件构成的一批.如果$\max\{p_j^B\}> Q_B$, 那么问题无解.
定理1. 算法1与2均可在$\rm O$$(n)$时间内分别找到问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$不同释放时间大小的最优调度.
证明. 由性质1可知, 工件集$J^A$与$J^B$中的工件分别在各自的释放时间之后构成一批加工.当$r^A=0<r^B=r$时, 如果问题存在最优解, 那么: a)当集合$J^A$中工件的最大加工时间$\max\{p_j^A\}\leq r$时, 所有集合$J^A$中工件能够从0时刻开始构成一批加工, 完工时间即为$\max\{p_j^A\}$, 此时集合$J^B$中的工件最早可以从$r$时刻开始构成一批加工, 其完工时间为$r+\max\{p_j^B\}$; b)当$\max\{p_j^A\}> r$时, 如果仍从0时刻先加工工件集$J^A$再加工工件集$J^B$, 能够满足工件集$J^B$的最大完工时间, 则能获得问题的最优解; 反之, 如果$\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 则最优解中只能最早从释放时间$r$开始先加工工件集$J^B$, 再接着加工工件集$J^A$.
同理, 当$r^A=r>r^B=0$时, 如果问题存在最优解, 那么此时工件集$J^A$的最早开始加工时间为$r$, 如果先加工工件集$J^A$再加工工件集$J^B$, 满足目标约束条件, 则能获得问题的最优解; 反之, 如果$r+\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 则最优解中只能从0时刻开始先加工工件集$J^B$, 再接着加工工件集$J^A$.
算法1与2中均需求出工件集$J^A$与$J^B$中最大加工时间, 因此时间复杂性均为${\rm O}(n_A)+{\rm O}(n_B)={\rm O}(n)$.
下面给出一个实例来应用算法1.假设工件集合}, 集合$J^B=\{J^B_1, J^B_2\}$.工件的加工时间分别为$p^A_1=1, p^A_2=2, p^A_3=3; p^B_1=1, p^B_2=2.$共同释放时间分别为$r^A=0$, $r^B=r=1$.集合$J^B$工件的最大完工时间上界为$Q_B=4$.
在算法1的步骤1中, 由于, 转到步骤2.又由于$\max\{p_j^A\}=3>r=1$, 所以最优调度$\pi'$为从$r=1$时刻开始加工集合$J^B$中工件构成的一批, 然后再从$r+\max\{p_j^B\}=3$时刻开始加工集合$J^A$中工件构成的一批, 最优调度如图 3所示.
2.2 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|L_{\max}^A:C_{\max}^B\leq Q_B$
针对问题, 给出一个最优解性质.
性质2. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|L_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 集合$J^A$中所有工件按照最短加工时间(Shortest processing time, SPT)规则生产加工.
证明. 类似于性质1的证明, 很容易得出集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 这样既不会增加集合$J^B$中工件的最大完工时间, 也不会增加集合$J^A$中每个工件的完工时间, 进而不会增加集合$J^A$中工件的最大延迟.下面假设存在一个最优调度$\pi$, 其中批$B_x$与$B_y$是关于集合$J^A$中工件的任意两批, 且$x<y$, 工件$J_i^A\in {B_x}$, $J_j^A\in {B_y}$, 同时$p_i^A>p_j^A$.将工件$J_j^A$从批$B_y$中移动到$B_x$中, 经过这样的转移后得到一个新的调度$\pi^\prime$.我们可以看到在$\pi^\prime$中工件$J_j^A$的完工时间减少, 其他工件的完工时间都不会增加.因此得到.
由性质2可知, 如果集合$J^A$中存在两个工件$J_i^A$和$J_j^A$, 并且满足$p_i^A\leq p_j^A$, 同时$d_i^A\geq d_j^A$, 那么我们可以将工件$J_i^A$转移到与工件$J_j^A$同一批中, 而不会增加集合$J^A$中工件的最大延迟.由此, 对于问题, 我们可以假设集合$J^A$中所有工件已经按照$\cdots$$\leq p_{n_A}^A$及的顺序排列.
1) $r^A=0, r^B=r$
针对问题, 由性质2设$X_B$为集合$J^B$所有工件形成的一批.设$S_1$为在$X_B$之前加工生产的集合$J^A$中工件的子集, $S_2$为在$X_B$之后加工生产的集合$J^A$中余下工件的集合, 即问题具有最优调度形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$中任何一个都可以是空集.
对于调度形式$(S_1, X_B, S_2)$, 集合$J^B$的最大完工时间$C_{\max}^B$由集合$S_1$中工件个数$l$及$S_1$中最后一批工件的完工时间$t$所决定, $0\leq l\leq n_A$.因此如果给定集合$S_1$中工件个数$l$, 问题就分解为在零时刻分别调度子集$S_1$与$S_2$中的工件, 分别使得$S_1$中工件对于每个$t$的最大延迟最小化以及$S_2$中工件的最大延迟最小化, 其中$S_1=\{J_1^A, J_2^A, \cdots, J_l^A$}, .因此, 调度形式的最优调度对应的最小化最大延迟值为
$$ \max\{f(l, t), C_{\max}^B+L_{\max}^A(S_2)\} $$ (1) 使得$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$成立, 其中为子集$S_1$中调度$l$个工件当最后一批工件的完工时间为$t$时的最大延迟最小值.
在式(1)中最大延迟最小值$L_{\max}^A(S_2)$, 所对应的最优调度可以利用Brucker等[15]求解问题的动态规划算法在$\rm O$$(n_A^2)$时间内获得.而最大延迟最小值$f(l, t)$, 所对应的最优调度可以通过下面构造的动态规划算法获得.
算法DP1.
初始条件:
对于每个$l=1, \cdots, n_A$对应在不同的最后一批完工时间$t$下, $t=p_l^A, \cdots, \sum_{j=1}^{l}p_j^A$有如下递归关系: , 如果满足$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 其中当前调度中最后一批的工件为对于任意的$h$, $0\leq h< l$.
此时对于每个$l$, 对应在不同的$t$值下, 所有的值以及对应的调度均可在时间内找到.
综上, 针对不同的$l$以及对应不同的$t$值, 在所有得到的$f(l, t)$中, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时最大延迟值最小的所对应的调度即为问题的最优调度.
定理2. 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
证明. 由性质2, 所研究问题的最优解具有调度形式, 并且所有集合$J^A$中的工件按照同时的顺序排列, 因此最优调度只需确定$S_1$中$l$个工件对应不同最大完工时间的最大延迟最小值, 以及$S_2$中$n_A-l$个工件的最大延迟最小值.为了确定$S_2$中工件最大延迟最小值, 我们可利用文献[15]中求解问题的最优算法从零时刻开始调度$S_2$中工件, 其时间复杂度为$\rm O$$(n_A^2)$.由于$S_2$中工件的实际开始加工时间为集合$X_B$的完工时间$C_{\max}^B$, 而$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}$, 受$S_1$中最后一批工件完工时间$t$的影响, 因此, 对于$S_1$中每个给定的工件个数$l$对应不同最大完工时间$t$构造动态规划算法DP1, 得出$S_1$中$l$个工件在不同最大完工时间$t$下对应的最大延迟最小值.进而对不同的$l$对应不同的$t$, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时最大延迟最小的所对应的调度即为问题的最优调度.
对于算法DP1, 由性质2可知, 从零时刻开始第一批工件按照SPT规则以及工期不减的顺序在机器上加工, 对应最大完工时间$t$时的最大延迟最小值为$f(l, t)$, 当前调度中最后一批工件对应的最大延迟为$t-d_{h+1}$.因此, 目标函数值为.为了使得调度形式$(S_1, X_B, S_2)$具有可行性, 需满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$.此外, 算法DP1中还满足$0\leq h< l\leq n_A$, , 所以DP1的时间复杂度为$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$.
综上, 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
2) $r^A=r, r^B=0$
如果问题存在可行调度, 那么有如下三种情况:
a) 如果$\max\{p_j^B\}\leq r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$r$时刻开始利用文献[15]中关于求解问题的动态规划算法可在$\rm O$$(n_A^2)$时间内求得最优解.
b) 如果$r<\max\{p_j^B\}\leq Q_B-r-t$, 其中, 由性质2可知, 问题仍具有最优调度形式, 其中集合$S_1$与$S_2$中工件对应的调度与上面时情况相同.而组合后调度形式的最优调度对应的最小化最大延迟值为
$$ r+\max\{f(l, t), t+\max\{p_j^B\}+L_{\max}^A(S_2)\} $$ (2) 其中, $0< t\leq \sum_{j=1}^{n_A}p_j^A$, $r+t+\max\{p_j^B\}\leq Q_B.$
因此, 该情况能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得问题的最优解.
c) 如果$\max\{p_j^B\}\geq Q_B-r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$\max\{p_j^B\}$时刻开始利用文献[15]中关于求解问题的动态规划算法可在$\rm O$$(n_A^2)$时间内求得最优解.
2.3 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|\sum C_j^A:C_{\max}^B\leq Q_B$
类似于性质2的证明, 对于问题, 给出如下最优解性质.
性质3. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|\sum C_j^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 集合$J^A$中所有工件按照SPT规则生产加工.
1) $r^A=0, r^B=r$
针对问题, 由性质3, 设$X_B$为集合$J^B$中所有工件形成的一批, 同时有$p_1^A\leq p_2^A\leq\cdots\leq p_{n_A}^A$.设$S_1$为在$X_B$之前加工生产的集合$J^A$中工件的子集, $S_2$为在$X_B$之后加工生产的余下集合$J^A$中工件的集合, 即问题具有最优调度形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$中任何一个都可以是空集.
类似于第2.2节, 对于调度形式$(S_1, X_B, S_2)$, 集合$J^B$的最大完工时间$C_{\max}^B$由集合$S_1$中工件个数$l$及$S_1$中最后一批工件的完工时间$t$所决定.因此如果给定集合$S_1$中工件个数$l$, 问题就分解为在零时刻分别调度子集$S_1$与$S_2$中的工件, 分别使得$S_1$中工件对于每个$t$的总完工时间最小化以及$S_2$中工件的总完工时间最小化, 其中$S_1=\{J_1^A, J_2^A, \cdots, J_l^A$}, .因此, 对于问题, 最优调度对应的最小化总完工时间为
$$ f(l, t)+(n_A-l)C_{\max}^B+\sum\limits_{j=l+1}^{n_A}C_j^A(S_2) $$ (3) 满足其中为子集$S_1$中调度$l$个工件当最后一批工件的完工时间为$t$时的最小总完工时间.
在式(3)中, 集合$S_2$中工件最小总完工时间所对应的最优调度可利用文献[15]提出的求解问题的动态规划算法在$\rm O$$(n_A\log{n_A})$时间内获得.而最小总完工时间$f(l, t)$可以通过下面的动态规划求出.
算法DP2.
初始条件:
对于每个$l=1, 2, \cdots, n_A$对应在不同的最后一批完工时间$t$下, $t=p_l^A, \cdots, \sum_{j=1}^{l}p_j^A$有如下递归关系: , 如果满足$\max\{t, r\}+\max\{p_j^B\}\leq Q_B, $其中当前调度中最后一批的工件为$\{J_{h+1}^A, \cdots, J_l^A\}$, 目标函数的增加值为该批的总完工时间$(l-h)t$.
对于每个$l$, 对应在不同的$t$值下, 所有的值以及对应的调度均可在$(n_A^2\sum_{j=1}^{n_A}p_j^A)$时间内找到.
综上, 针对不同的$l$以及对应不同的$t$值, 在所有得到的$f(l, t)$中, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时总完工时间最小的所对应的调度即为问题的最优调度.
定理3. 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
定理3的证明类似于定理2的证明, 这里不再详细赘述.
2) $r^A=r, r^B=0$
如果问题存在可行调度, 那么有如下三种情况:
a) 如果$\max\{p_j^B\}\leq r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$r$时刻开始利用文献[15]中关于求解问题的动态规划算法在$(n_A\log{n_A})$时间内求得最优解.
b) 如果$r<\max\{p_j^B\}\leq Q_B-r-t$, 其中, 由性质3可知, 问题仍具有最优调度形式, 其中集合$S_1$与$S_2$中工件对应的调度与上面时情况相同.而组合后调度形式的最优调度对应的最小化总完工时间值为
$$ \begin{align}f(l, t)\, &+(t+\max\{p_j^B\})(n_A-l)+\nonumber\\&\quad \sum\limits_{j=l+1}^{n_A}C_j^A(S_2)+n_Ar\end{align} $$ (4) 其中, $0< t\leq \sum_{j=1}^{n_A}p_j^A$, $r+t+\max\{p_j^B\}\leq Q_B.$
因此, 该情况能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得问题的最优解.
c) 如果$\max\{p_j^B\}\geq Q_B-r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$\max\{p_j^B\}$时刻开始利用文献[15]中关于求解问题的动态规划算法在$(n_A\log{n_A})$时间内求得最优解.
3. 批处理机能力有界
本节只考虑批处理机能力有界的情形下, 目标函数为最小化集合$J^A$工件的最大完工时间使得集合$J^B$工件的最大完工时间不超过给定上界的复杂性.针对两个工件集各自共同释放时间$r^A$与$r^B$的大小关系, 分别证明了两种情况下问题均为NP—难问题, 同时针对这两种情况分别设计了伪多项式时间算法进行求解.
1) $r^A=0, r^B=r$
定理4. 问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A: C_{\max}^B\leq Q_B$是一般意义NP-难的.
证明. 我们将通过NP-难的划分问题归约来证明问题的NP-难性.划分问题(Partition problem)定义如下:
给定$m$个正整数$a_1, a_2, \cdots, a_m$, 并且满足$\sum_{j=1}^ma_j=2H$, 是否存在一个划分将下标集合分成两个不相交的子集$I_1$和$I\setminus I_1$, 使得$\sum_{j\in I_1}a_j=\sum_{j\in I\setminus I_1}a_j=H$?
给定划分问题的一个实例, 构造问题的判定问题的一个实例如下:
$$ n_B=1, r^B=r=H, p_1^B=H, Q_B=2H; $$ 批处理机一批的能力为$b=2;$
$n_A=2m, r^A=0, p_j^A=p_{j+m}^A=a_j, j=1, 2, \cdots, m;$
集合$J^A$目标的阈值为$Q_A=3H.$
接下来证明对于构造的问题的实例, 当且仅当划分问题有解时, 能够找到一个调度满足$C_{\max}^A\leq Q_A, C_{\max}^B\leq Q_B$.
$\Longrightarrow$如果划分问题有解, 即存在子集$I_1\subset I, $使得$\sum_{j\in I_1}a_j=\sum_{j\in I\setminus I_1}a_j=H$成立.对于上面问题构造的实例, 能够找到一个调度, 满足, 调度如下:工件$J_1^B$在$r^B=H$时刻开始调度, 具有相同加工时间的工件$J_j^A$与$J_{j+m}^A$组成一批加工, 即批$B_j=\{J_j^A, J_{j+m}^A\}$, $j\in {I}$, 其中对应下标的批从0时刻开始加工, 下标的批从$2H$时刻开始加工.容易验证.
$\Longleftarrow$如果对于问题构造的实例存在一个调度满足那么容易证明集合$J^B$唯一的工件$J_1^B$一定在$r^B=H$时刻开始调度.此外, 由于$\sum_{j=1}^{2m}p_j^A/b=2H, $所以调度从0到$3H$时刻之间没有空闲时间, 集合$J^A$工件构成的每一批都是满批, 并且每一批的两个工件一定具有相同的加工时间.记批, $j\in {I}$, 因此在$J_1^B$之前加工的所有批的加工时间和为, 之后加工的所有批的加工时间和为.因此划分问题有解.
下面给出求解问题的两个最优解性质.
性质4. 对于问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r$或者$r$之后连续生产加工, 并且加工批满足满批最大加工时间(Full batch largest processing time, FBLPT)规则.
证明. 由于集合$J^B$中所有工件的释放时间为$r$, 所以集合$J^B$中工件只能在时刻$r$或者$r$之后加工生产.在一个可行调度中, 将工件交换位置使得集合$J^B$中除最后一个工件外其他的工件向右移动到集合$J^B$中最后一个工件前与之连续加工, 再结合文献[15]中提出的求解问题$1|p-batch, b<n|C_{\max}$的调度方法, 得到的调度中集合$J^B$的工件最大完工时间不会增加, 同时集合$J^A$的每个工件的完工时间也不会增加, 进而最大完工时间不会增加.
设$X_B$为集合$J^B$工件按照FBLPT规则连续加工形成的集合.
性质5. 对于问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^A$中所有工件可以按照FBLPT规则产生所有加工批.
证明. 通过工件交换与工件转移, 能够证明性质的结论.
由性质4和5, 设集合$J^A$与$J^B$中的工件分别按照FBLPT规则获得所有加工批, 所需时间为$\rm O$$(n\log n)$, 设批总长度为$T_X$, $X\in\{A, B\}$, 即$T_X=\sum_{i=0}^{[\frac{n_X}{b}]}p_{ib+1}^X$, 其中$[x]$表示不大于$x$的最大整数.下面针对问题提出如下算法进行求解.
算法3.
步骤1. 如果$\max\{T_A, r\}+T_B\leq Q_B$, 那么在最优调度中从0时刻开始按照FBLPT规则连续加工集合$J^A$的工件, 从$\max\{T_A, r\}$时刻开始按照FBLPT规则连续加工集合$J^B$的工件.如果$\max\{T_A, r\}+T_B>Q_B$, 那么转到步骤2.
步骤2. 如果$T_A\leq r$, 那么问题没有解.如果$T_A>r$, 那么问题的最优调度具有形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$分别为在$X_B$前后加工生产的集合$J^A$工件的子集合, $S_1$可能为空集, 而$S_2$一定不是空集.针对这一情况, 设计如下伪多项式时间动态规划算法对问题进行求解.
算法DP3.
由性质5, 我们可以将集合$J^A$中所有工件按照FBLPT规则产生的每一个批看作一个工件.因此, 此时关于集合$J^A$工件的批生产调度问题可以转化为单机生产调度问题, 即批处理机的能力为$b=1$.假设集合$J^A$的所有工件按照加工时间不增的顺序排列如下: .定义$f(s)$为调度$n_A$个集合$J^A$的工件与全部$J^B$工件后集合$J^A$工件最大完工时间的最小值, 其中$s$是$X_B$的开始加工时间, 满足$r\leq s< r+P^A_{\max}$, 其中, $P^A_{\max}=\max\{p^A_j\}$, 因为在集合$S_1$中至多一个工件在$r$之后加工完.对于一个给定的$s$, 为了求出$f(s)$的最小值, 进一步定义为调度部分工件时集合$J^A$工件最大完工时间的最小值, 其中$t$是集合$S_1$中最后一个工件的完工时间, $t\leq s$.
定义初始条件为
$$ F(0,t)=\left\{ \begin{array}{*{35}{l}} s+{{T}_{B}}, & 若\ \ t=0 \\ +\infty , & \text{ }其他 \\ \end{array} \right. $$ 为了获得$F(h, t)$的最优值, 我们列举工件$J_h^A$的可能加工位置, 即工件$J_h^A$可能是集合$S_1$中最后一个加工的工件, 也可能是集合$S_2$中最后一个加工的工件, 于是有下面的递归关系:
$$ F(h,t)=\min \left\{ \begin{array}{*{35}{l}} F\left( h-1,t-p_{h}^{A} \right),若J_{h}^{A}\in {{S}_{1}} \\ F(h-1,t)+p_{h}^{A},若J_{h}^{A}\in {{S}_{2}} \\ \end{array} \right. $$ 因此, 对于$X_B$的每个开始加工时间$s$, $r\leq s<r+P^A_{\max}$, $f(s)$的最小值能够获得, 具有如下形式:
$f(s)=\min\{F(n_A, t): t\leq s\}$
进而, 问题的最优解值为$\min\{f(s): r\leq s < r+P^A_{\max}\}.$
定理5. 算法3可以找到问题的最优调度, 其中算法DP3的时间复杂度为$\rm O$$(n_A(r+P_{\max}^A)^2)$, 这里$P_{\max}^A=\max\{p_j^A\}$.
证明. 在算法3中, 如果问题存在最优解, 那么当时, 很显然利用性质4和5在最优解中从0时刻开始按照FBLPT规则连续加工集合$J^A$中工件, 从$\max\{T_A, r\}$时刻开始按照FBLPT规则连续加工集合$J^B$工件; 当$T_A+T_B> Q_B$时, 具有最优调度形式$(S_1, X_B, S_2)$.由性质5可知, 此时可以将关于集合$J^A$工件的批生产调度看成单机生产调度问题.对于一个给定的$X_B$的开始加工时间$s$, 工件$J_h^A$的完工时间有两种情况: a)当$J_h^A$在集合$S_1$中最后一个加工时, ; b)当$J_h^A$在集合$S_2$中最后一个加工时, .最后对于每个$s$所获得的集合$J^A$全部工件的最大完工时间最小值, 再求$\min\{f(s)\}$即为问题的最优解.又由于, 所以$s$的大小界限为$\rm O$$(r+P_{\max}^A)$.另外$0\leq h\leq n_A$, $t$是集合$S_1$中最后一个工件的完工时间, 满足$t\leq s$.因此, 算法DP3的时间复杂度为$(n_A(r+P_{\max}^A)^2)$.
2) $r^A=r, r^B=0$
定理6. 问题$1|p-batch, r^A=r, r^B=0, b<n|C_{\max}^A: C_{\max}^B\leq Q_B$是一般意义NP—难的.
证明. 类似于定理4的证明, 通过NP—难的划分问题归约来证明该问题的NP—难性.构造问题的判定问题的一个实例如下:
$n_B=2m, r^B=0, p_j^B=p_{j+m}^B=a_j, j=1, 2, \cdots, m, Q_B=3H;$
批处理机一批的能力为$b=2;$
$n_A=1, r^A=r=H, p_1^A=H;$
集合$J^A$目标的阈值为$Q_A=2H$.
在此我们忽略详细的证明过程.
针对问题, 首先设计一个动态规划算法计算出集合$J^B$所有工件最大完工时间的最小值, 然后在所有这些最小值中找到满足集合$J^B$目标函数约束条件下集合$J^A$工件的最小开始加工时间.类似于性质4的证明, 提出如下的最优解性质:
性质6. 对于问题$1|p-batch, r^A=r, r^B=0, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^A$中所有工件在时刻$r$或者$r$之后连续生产加工, 并且加工批满足FBLPT规则.
设$X_A$为集合$J^A$工件按照FBLPT规则连续加工形成的集合, 类似于性质5有下面的最优解性质:
性质7. 对于问题, 如果存在一个最优调度, 那么集合$J^B$中所有工件可以按照FBLPT规则产生所有加工批.
类似于情况$r^A=0, r^B=r$, 设$T_X$, 为集合$J^X$所有工件按照FBLPT规则获得所有加工批的批总长度.在问题中, 假设$r<T_B<Q_B$; 否则, 当$T_B\leq r$或$T_B=Q_B$时, 如果存在一个最优调度, 那么可以将集合$J^B$所有工件从零时刻开始按照FBLPT规则连续加工生产, 集合$J^A$所有工件对应在$r$或$Q_B$时刻按照FBLPT规则连续加工生产; 当$T_B>Q_B$时, 问题没有解.因此, 问题具有调度形式, 其中$S_1$与$S_2$分别为在$X_A$前后加工生产的集合$J^B$工件的子集合, $S_1$可能为空集, 而$S_2$一定不是空集.
根据以上的分析, 首先给出如下动态规划算法求出问题中集合$J^B$所有工件最大完工时间的最小值.
算法DP4.
由性质7, 我们可以将集合$J^B$中所有工件按照FBLPT规则产生的每一个批看作一个工件.因此, 此时关于集合$J^B$工件的批生产调度问题可以转化为单机生产调度问题, 即批处理机的能力为$b=1$.假设集合$J^B$的所有工件按照加工时间不增的顺序排列如下: .定义$f(s)$为调度$n_B$个集合$J^B$工件与全部集合$J^A$工件后集合$J^B$工件最大完工时间的最小值, 其中$s$是$X_A$的开始加工时间, 满足$r\leq s< r+ P^B_{\max}$.对于一个给定的$s$, 为了求出$f(s)$的最小值, 进一步定义为调度部分工件时集合$J^B$工件最大完工时间的最小值, 其中$t$是$S_1$中最后一个工件的完工时间, $t\leq s$.
定义初始条件为
$$ F(0,t)=\left\{ \begin{array}{*{35}{l}} s+{{T}_{A}}, & 若\ \ t=0 \\ +\infty , & \text{ }其他 \\ \end{array} \right. $$ 为了获得$F(k, t)$的最优值, 同样列举工件$J_k^B$的所有可能加工位置, 即工件$J_k^B$可能是集合$S_1$中最后一个加工的工件, 也可能是集合$S_2$中最后一个加工的工件, 于是有下面的递归关系:
$$ F(k,t)=\min \left\{ \begin{array}{*{35}{l}} F\left( k-1,t-p_{k}^{B} \right),若J_{k}^{B}\in {{S}_{1}} \\ F(k-1,t)+p_{k}^{B},若J_{k}^{B}\in {{S}_{2}} \\ \end{array} \right. $$ 因此, 对于$X_A$的每个开始加工时间$s$, $r\leq s<r+P^B_{\max}$, $f(s)$的最小值能够获得, 具有如下形式:
$f(s)=\min\{F(n_B, t): t\leq s\}$
为了求出满足条件下集合$J^A$工件最大完工时间的最小值, 我们在上面得到的所有$f(s)$中找到满足条件$f(s)\leq Q_B$的最小的$s$, 该调度即为问题的最优调度.
定理7. 算法DP4可以在$(n_B(r+P_{\max}^B)^2)$时间内找到问题的最优调度, 其中$P_{\max}^B=\max\{p_j^B\}$.
证明. 算法DP4的最优性证明类似于定理5中最优性的证明.由于$r\leq s< r+P^B_{\max}$, 所以$s$的大小界限为$(r+P_{\max}^B)$.另外$0\leq k\leq n_B$, $t$是集合$S_1$中最后一个工件的最大完工时间, 满足$t\leq s$.因此, 算法DP4的时间复杂度为$\rm O$$(n_B(r+P_{\max}^B)^2)$.
4. 结论
本文研究了带有两类释放时间的两个工件集在一台批处理机上竞争生产加工的有约束优化调度问题.针对两类释放时间的大小, 分别考虑了批无界与批有界情况下一些问题的时间复杂性.当批无界时, 在满足一个工件集最大完工时间不超过一个给定上界的条件下, 分别针对最小化另一个工件集的最大完工时间、最大延迟以及总完工时间问题提出了最优解性质, 设计了多项式或伪多项式时间的最优求解算法.当批有界时, 对于最小化一个工件集的最大完工时间使得另一个工件集最大完工时间不超过一个给定上界问题, 运用复杂性证明出问题为一般意义NP—难问题, 同时给出了伪多项式时间动态规划算法进行求解.批处理机上工件带有两类释放时间的两个工件集竞争调度问题的研究, 不仅为实际工业生产提高了机器生产效率、降低能耗、满足不同顾客需求, 也为多个工件集竞争调度问题的研究奠定了理论基础.未来可以进一步研究此类问题中NP—难问题的启发式算法, 并作出算法的性能分析, 也可以对问题的其他目标函数进行研究.
-
图 3 不同参考点计算的可行域对比
Fig. 3 Feasible area comparison calculated by different reference points
图 4 改进前后两种凸近似避障法的路径规划结果对比
Fig. 4 Path planning comparison results between un-developed and developed convex approximation avoidance methods
图 5 基于曲线坐标系统的车道偏移量计算原理
Fig. 5 Lane off-set calculation theory based on the curvilinear coordination system
图 7 权重函数松弛前后结果对比
Fig. 7 Comparison results of the cost functions before/after relaxation
图 12 基于SILS的H7 Carsim模型与实车实验性能对比
Fig. 12 Performance comparison between the H7 Carsim model and prototype vehicle based on SILS
表 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 
下载: 导出CSV
表 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
下载: 导出CSV
符号 说明 单位 $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$ 实际车距与安全车距的比值
下载: 导出CSV
-
[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 -
下载:
计量
- 文章访问数: 3722
- HTML全文浏览量: 1682
- PDF下载量: 715
- 被引次数: 0
