无人机-智能车队协同路径实时规划研究

谢博宇，李茂青，岳丽丽，陈启香

1.兰州交通大学 自动化与电气工程学院，兰州 730070

2.宝鸡文理学院 电子电气工程学院，陕西 宝鸡 721000

1 引言

随着经济、科技的不断发展和进步，智能交通系统的发展为路径规划问题中道路交通信息的获取提供了新的思路和方法。路径规划问题是根据出行需求，在车辆导航系统中根据OD点信息，系统规划出一条最佳的路径。

路径规划问题首先要获得道路信息，然后根据道路信息使用不同的算法得到出行时间最少的路径。在得到每条道路的行驶时间后，选择一种合适的算法来搜寻出一条最优路径。在当前的研究算法中，常用的有Dijkstra算法、A*算法、蚁群算法等。文献[1-2]建立新的模型，如曹慧等[1]建立了随机时变路网环境下稳健路径模型。文献[3-5]改进了算法，如Zhang 等[3]首先采用动态邻接节点关系矩阵和动态邻接节点权重矩阵改进Dijkstra 算法。另外，Kammoun 等[6]提出了基于蚁群行为的自适应车辆导航系统，提出一种基于多智能体的体系结构，通过改进的蚁群算法规划出一条最佳的路径。

在最新的成果当中，开始提出在车联网环境下的路径规划问题。通过路旁检测设备获取到的信息更准确、更实时，将这种方式称之为路测工作模式。王庞伟等[7]提出基于车路协同系统的区域实时路径规划，根据在交叉口前排队车辆的数目，按照排队车辆消散时间来计算时间。但是该方法只考虑信号灯处于红灯状态时的情况。而没有考虑多次排队情况，以及车辆左转和右转情况。吴黎兵等[8]提出了一种车联网环境下的城市车辆协同选路方法，根据车辆到达路口时道路的状态来分别计算每条路上的权值，以此来计算出一条最佳的路径。该方法只给出车辆直行时的计算公式，而且没有考虑不同车道的交叉口延时时间。尽管目前国家提倡智能交通系统的建设和使用，未来也会大规模建设。但是由于目前大部分城市还没有普及智能交通系统或者由于设备故障或者设备之间通信信号中断等情况而导致接收不到道路信息。

在无人车避障绕行的路径规划研究中，为解决无人车环境感知有限的问题，使无人机-无人车协同工作来解决，它是通过无人机的大范围环境感知能力为无人车提供导航信息[9-10]。席阿行等[11]利用SURF 算法建立了UGV 可执行的地图，提出优化的A*算法优化了所有的拐点，实验证明可以有效地避开障碍物，找到一条全局路径规划。胡秋霞等[12]以无人机与无人车协同为背景，提出一种改进的人工势场法，解决了局部极小点问题。杜仕刚等[13]针对无人机拍摄遮挡问题，使用图像拼接技术构建全局地图，使用车辆传感器感知环境构建局部地图，最后采用A*算法计算出路径。在文献[11-15]以及现有无人机与无人车协同路径规划算法中，多数研究是理论基础研究，它们能够在空旷地上避开障碍物，自行规划出一条从起点到目标点的最优路径。而现有文献很少应用在道路交通中，即根据城市中的可供行驶道路选择一条使驾驶员能够最快到达目的地的道路。

王云鹏等[14]在专利中提出一种基于无人机感知的无人驾驶车辆路径规划方法，主要是通过无人机获取路网模型，根据无人飞行器的GPS信息，来进行匹配运算，得到无人车的位置。应用C 空间算法和Dijstra 算法相结合，该专利提出一种在电子地图中选择一条权值为道路长度和车辆占道比相结合最小的一条路径的思路，它没有考虑整体时间用时情况，也没说明如何实施。同时根据全局规划选出一条最短路后，使用人工势场法避开道路上其他车辆。

由此提出无人机-智能车队协同系统，该系统有两种计算路径的模式，即路测模式和机测模式。它们分别利用路旁检测设备或无人机检测的信息进行路径规划。在两方面进行了改进：一是在路测模式当中，根据从智能交通系统中获得到的排队长度和信号灯的显示，改进文献[9-10]为考虑车辆到达路口时多种信号灯显示情况、在不同车道行驶以及多次排队情况，计算出一条行驶时间最短的路径；二是提出机测模式，由无人机拍摄视频，经过图像处理得到在交叉口前的车辆排队长度，并改进文献[16]根据道路长度和车辆占道比来选择路径的思路，同时考虑车辆在不同车道上行驶以及多次排队情况计算出一条行驶时间最短的路径。

2 无人机-智能车队协同系统

无人机-智能车队协同系统是基于车辆导航系统所改进的，该系统将车辆导航系统和无人机相结合。如图1所示为系统的总体示意图。系统分为4个子系统，即智能车队、路旁设备、交通指挥中心以及无人机子系统。

如图2 所示为系统内部结构框图。在无人机-智能车队协同系统中，车辆有两种计算路径模式。路测模式是由路旁设备采集信息，并经过交通指挥中心处理最终发给车辆。在该模式中，车辆根据在交叉口前的排队长队以及进入道路时的交通灯显示来计算时间。机测模式是车辆和无人机协同工作。由无人机拍摄视频，并将视频传递给车辆，由车辆经过图像处理得到信息。同时由车辆控制无人机，包括飞行路线、飞行姿态、无人机上的摄像装置。在此模式中，目前只根据排队长度来计算时间。

图2 系统内部结构框图

如图3所示为车辆从接收信息、传递信息到规划最优路径的系统工作流程图。

车辆进入某路段时，默认模式是路测模式。系统会判断是否能通过路旁设备接收到至汽车位置相邻2 个交叉口及路段上的信息，当接收不到时，提示“路测模式无法工作”。系统会进入机测模式，此时车辆和无人机协同工作。车辆派遣无人机去道路上拍摄视频并传回车辆对视频做处理得到需要的信息。在该算法中，考虑到无人机飞行时间、图像采集及道路背景识别的时间，无人机会比车辆提前飞行至目的地进行拍摄。无人机可以拍摄出方圆800 m范围，包含4个交叉口的范围，即车辆每走两个交叉路口会计算接下来所走道路的时间，规划一次路径。当车辆拍摄完一个路口的视频后，会继续往前拍摄视频，来保证数据的实时性要求。

图3 系统工作流程

由于无人机飞行时间一般在20～30 min，针对发生长时间工作电量不足的现象，设置两架无人机，一台主用一台备用，同时在车上设置充电装置，无人机可随时充电。如果无人机由于信号遮挡或者通信距离过长导致无人机丢失信号。通过在备用无人机上架设信号中继设备，在丢失信号附近区域飞行，通过信号中继设备实现无人机与车辆之间信号实时传输。对于特殊情况，如无人机拍摄完成准备返航时突发事故等导致该区域交通状态突发变化，无人机需要重新采集数据进行路径规划，然后返航。

2.1 智能车队

在智能车队中，车车之间要有车车协同控制，同时要保持队列行驶。在车队中只有领航者才可以接收到无人机发来的视频，其余跟随者由领航者传输数据。在机测模式中，无人机将拍摄的视频通过无线通信模块传输到图像处理模块进行图像处理，并将处理后的数据再次通过通信模块传输到路径规划模块进行路径规划。车辆会根据接收到的无人机信息通过无人机控制模块控制无人机飞行，包括飞行路线、飞行姿态、无人机上的摄像装置。

2.2 路旁设备和交通指挥中心

路旁设备一般固定安装在道路旁，用于采集交通信息。一般有环型感应线圈检测器、超声波检测器、红外线检测器、微波雷达检测器、视频图像车辆检测器这几种。由于所研究内容，需要得到在交叉口前的排队长度信息，对比几种检测器，使用视频图像车辆检测器进行检测。

交通指挥中心用于接收路旁设备采集到的信息，并将信息处理成需要的数据。将处理后的视频通过无线传输发送到车辆上用于路径规划。

2.3 无人机系统

无人机系统是由若干个相互联系、作用、依存的组成部分结合而成的且具有完成指定任务的有机整体。在无人机系统中共有4 个分系统，即飞行器平台分系统、测控与信息传输分系统、无人机定位信息分系统以及图像采集分系统。在该系统中，图像采集模块用于对道路视频进行拍摄，并通过机载信息传输模块将视频传输至智能车队中的领航者。同时，车辆会根据无人机飞行状态通过地面信息传输模块将控制命令传输给无人机。

3 基于无人机-智能车队协同系统的路径规划方法

如图4 所示，为城市道路示意图，研究对象为最常见的6车道路段，包含直行、左转、右转道。

图4 城市道路示意图

交叉口选用四相位信号设计方案，即每个进口方向都设置左转专用车道，同时右转路口为自由右转。如图5所示为交叉口的相位放行示意图。

图5 四相位放行示意图

在此设计方案中，把一个信号周期分为3 个阶段，即绿灯直行、绿灯左转和红灯，忽略黄灯时间。周期为C=tSL+tLL +tH，其中绿灯直行所占时间为tSL，绿灯左转所占时间为tLL，红灯所占时间为tH。右转为自由右转，所占时间为tRL =C。为方便阅读，将主要变量列出，如表1所示。

表1 变量含义列表

基于所提出的路径规划方法，需要经过获取信息、计算路阻权值、规划最优路径3个步骤。获取信息方式前文已介绍，现介绍后两个步骤。

3.1 道路权值的计算

3.1.1 交叉口前运动状态分析

车辆从不同车道由静止到通过交叉口，所需时间有不同的计算结果。

车辆在交叉口行驶的最大速度为vi。根据某省道路交通管理条例实施办法中第三十条关于车辆通过交叉路口时的规定：在有交通信号或交通标志控制的交叉路口，机动车时速不准超过30 km/h。故假设车辆在交叉口行驶速度为30 km/h（8.33 m/s），为计算方便，将此值设为8 m/s，即vi=8 m/s。

车辆在交叉口前从启动到通过交叉口，运动过程是先从零做匀加速运动，加速到vi，即8 m/s。然后以8 m/s的速度做匀速运动。但是在右转道，若使用变速运动计算，在计算权值时计算过程过于繁杂，故将变速运动近似为匀速运动。假设路口距离为30 m，右转时通过一半路口，即15 m。则车辆通过一个交叉口时间约为3 s，故匀速度约为15/3=5 m/s。

由于右转路口为自由右转，在计算时为符合实际道路情形，需要考虑礼让行人的情形，将行人所造成的阻碍通过时间设为tp。如图6所示，为车辆右转时等待行人情景。假设车辆以东西方向行驶，车辆等待行人分为两种情形，情形一信号灯处于绿灯直行和左转这段时间内，车辆需要等待时间tp1；情形二信号灯处于红灯状态，车辆右转需要等待时间tp2后才可以继续行驶。有研究指出驾驶员主观合理等待时间约为16 s[15]。

图6 车辆右转时等待行人情景

3.1.2 计算关键值

（1）计算sS、sL、sR，这三个变量分别是直行、左转、右转时可通过最远排队车辆到交叉口的距离，这个值用于划分车辆的排队次数。

①sS和sL

由3.1.1 小节知车辆在直行和左转道时，先做加速运动后做匀速运动，故sS、sL计算过程为这两部分的距离之和。由vi=v0+at=8 可知匀加速运动时间为t加=距离为匀速运动时间为则直行时可通过最远排队车辆到交叉口的距离sS为：

左转时可通过最远排队车辆到交叉口的距离sL为：

②sR

由图6 所示的车辆右转时等待行人情景可知，车辆需要等待两个行人时间，可将一个周期分为4 个时间段。即等待tp1、车辆行驶、等待tp2、车辆行驶。sR的值因此情况复杂，为省略篇幅，在此不详细介绍，具体见后文。

（2）计算车辆在交叉口前从停止到通过交叉口的时间，即交叉口延误时间。同理按照不同车道划分，依据3.1.1节来计算。直行和左转时间为：

右转时间为：

3.1.3 权值计算

将权值设为车辆从进入道路到分别从直行道、左转道、右转道离开的通过时间，即ts,tl,tr。

由前文介绍，系统有机测和路测两种计算模式。当全部使用路旁设备得到信息时，能够得到车辆抵达路口时的信号显示时刻t0和在交叉口前的排队长度d。当使用无人机获取信息时，目前仅能够得到排队长度d。t0值计算公式如下。

计算车辆抵达路口时的信号显示时刻t0：

其中是车辆进入道路时的信号显示时刻，为前一段路所行驶的时间。由于t0的值在一个周期之内，故需和周期C取余。

当仅使用无人机获取信息时，在公式中假设t0=0。

根据在交叉口前一个进口的直行、左转、右转三车道，把在交叉口前的排队长度分别记为dS、dL、dR。

计算从进入一条道路到离开交叉口的时间分为以下两个步骤。

步骤1得到所需要的数据。包括车辆抵达路口时的信号显示时刻t0和在交叉口前的排队长度d。

步骤2计算ts、tl、tr。首先根据t0值进行划分，判断此时车辆处于的时刻。接下来根据车辆到达交叉口的时间来划分区间，选择计算公式。

1）从直行道离开的通过时间ts

（1）0 ≤t0＜tSG

① 0 ≤dS ＜sS

注1由于公式冗长，为方便排版，将公式中C的倍数，比如mC写为Cm,(m+1)C写为Cm+1，全文公式同理。

②n⋅sS≤dS ＜(n+1)⋅sS(n=1,2,3,…)

2）从左转道离开的通过时间tl

3）从右转道离开的通过时间tr

由于车辆需要等待两个行人时间，故将一个周期分为4 个时间段。在每个时间段内dR的取值范围均不同，即车辆排队次数的计算公式不同。由于篇幅限制，将每个时间段的计算顺序给出。

经过上述步骤即可得到道路权值。

3.2 道路模型

由于车辆在交叉口行驶时，需要考虑直行、左转、右转三种情形，一般研究提出的路网模型反映不出车辆左转、右转的情形。同时，还要能够表示出交叉口的转向限制、单向交通、掉头等情况。故使用对偶图法来建立路网的数据模型，其实质是将基于节点的图转化为基于边的图。如图7（a）所示为一简单的十字路口，图7（b）是该道路的节点-路段表示，图7（c）是该道路的路段-链表示。

图7 路网模型

3.3 最优路径选取

根据计算出来的权值，经过计算即可得到最优路径。根据3.1 节所述的方法得到权值后，使用迪杰斯特拉（Dijkstra）算法即可规划出一条最优的路径。

4 仿真分析

4.1 仿真场景设置

如图8所示，用一个简单路网来阐述算法的实现过程。

此路网是由9 个交叉口，6 条主干路构成的12 条双向6车道。把每个交叉口从①～⑨进行标号，设一对起屹点，记为OD。算例设置如下：

（1）每条道路的长度如图8中标记所示。假设交叉口长度相等，为li=40 m。

图8 算例路网

（2）交叉口信号配时。表2为所选区域每个交叉口的信号配时，每个交叉口均为四显示。

表2 信号交叉口信号配时 s

（3）车辆加速度a。表3所示为不同类型轿车动力参数，表中分别为最高车速、从0 加速到100 km/h 的时间以及加速度。

表3 不同类型轿车动力参数

由表3可知车辆加速度在2～4 m/s2之间，为均衡不同车辆的类型，取加速度a=3 m/s2。

（4）道路最高速度。表4 为《城市道路工程设计规范（2016年修订版）》中规定的各级道路的设计速度，由此确定道路的速度。

表4 各级道路的设计速度

示例道路均为主干路，故由表4可得道路设计速度为60 km/h、50 km/h、40 km/h，为方便计算，选取道路速度v=50 km/h。

4.2 不同场景下的应用

首先将举例城市道路转换为道路数据模型。其次假设工作模式为路测模式，即信息完全由路旁设备获得，根据不同场景下的路况进行仿真。假设由路旁设备得到某时刻的交叉口信号显示已知，根据该例起屹点行驶方向设置。在南北方向，路口①68 s，②34 s，③76 s，⑤ 45 s，⑥67 s，⑧32 s，⑨24 s；东西方向，路口④40 s，⑤ 39 s，⑥ 12 s，⑦ 52 s，⑧ 47 s，⑨ 64 s。

然后通过设置不同的排队长度来实现不同场景下的仿真。

（1）道路状况良好，不存在拥堵情况

在交叉口前均设置很少的排队车辆，来实现仿真。具体数据为，在每条道路前的直行车道排队长度分别为：10、35、20、17、18、17、25、34、15、19、14、26、24、23、27、23、15、34、15、35、18、21、35、16、10、0 m；左转车道排队长度分别为：28、20、13、16、25、13、24、22、45、22、23、22、10、12、14、14、28、20、23、18、12、12、13、14、0、0 m；右转车道排队长度分别为：10、25、10、10、13、10、24、34、12、32、24、58、56、34、30、23、42、10、45、50、29、50、76、87、0、0 m。仿真结果见表5。

表5 不存在拥堵情况下的路线结果

由图8所知，在表5中，序号1、2、6三条路线行驶过程当中会经历3 个直行路口、1 个左转路口、1 个右转路口；序号2、3、4 三条路线行驶过程当中会经历1 个直行路口、2个左转路口、2个右转路口。由表5可以得出，车辆在行驶过程中，遇到左转路口少的情况下，行驶时间会变短。当左转路口一样多的情况下，可以很好地找出最短的一条路径。

（2）道路状况很差，全部路段均存在拥堵情况

由《交通工程学》建议的服务水平分级标准中车辆排队长度＞100 m，即为拥堵路段。故在每条道路前的排队长度具体数据为，直行车道：200、510、240、395、310、275、435、244、409、319、294、457、324、356、352、232、386、244、326、254、218、450、245、430、30、0 m；左转车道：230、288、290、185、273、245、276、232、341、186、185、228、216、229、330、199、258、231、283、148、149、380、216、294、30、0 m；右转车道：195、208、269、254、208、178、202、169、219、170、170、259、209、238、214、175、202、163、199、157、181、340、178、227、25、0 m。仿真结果见表6。

由上文得出遇到左转少的情况，行驶时间会变短。但是在表6 中，可以看出路线6 的时间会由第一变为第六，这是由在交叉口前的排队车辆数所决定的。其选择路线的结果如图8所示，在图中由红色线表示。

表6 大量在拥堵情况下的路线结果

（3）在某些直行路口有大量排队车辆

假设当直行道路存在大量排队的车辆，所提算法可以绕过这些排队长度很长的路口。具体数据为，在每条道路前的直行车道排队长度分别为：100、350、100、274、50、175、435、344、215、219、214、186、224、223、352、232、300、344、153、354、318、241、345、216、21、0 m；左转车道排队长度分别为：232、288、93、185、34、248、100、132、153、180、180、142、104、123、200、200、58、233、223、153、153、212、213、194、21、0 m；右转车道排队长度分别为：195、258、30、187、67、180、160、170、104、102、171、58、156、195、100、178、142、120、145、150、129、150、176、187、20、0 m。仿真结果见表7。

表7 在某些直行路口有大量排队车辆的路线结果

由表1 可以看出，在仿真（1）和（2）中序号为5 的路线的行驶时间排名第五和第三，但是在此次仿真中排名第一。由此证明可以根据交叉口的排队车辆长度来选择路线，可以很好地避开那些拥堵的路口。

（4）道路中偶发交通事故

在（1）的数据基础上，进行本次仿真。如果1到4的路段（即1-4）发生交通事故，车辆会选择绕开此路径，而走另外的路线，此时车辆选择O →①→②→⑤→⑥→⑨→D 这条路。如果1到4和5到6（即1-4和5-6）两条路同时发生交通事故，则车辆会选择O →①→②→⑤→⑧→⑨→D 这条路。

对于（4）所述，只是提供了一种解决偶发交通事故的思路，具体情形还没有具体考虑。

5 结束语

重点研究了基于无人机-智能车队协同系统下的实时路径决策方法，针对现有的基于智能交通系统下的路径决策方法无法完全保障道路数据的获取，提出两种工作模式，即路测模式和机测模式。将现有文献中考虑单一信号灯和单一车道扩展为车辆考虑在不同车道上的行驶时间以及在交叉口的延误时间，同时考虑多次排队情况，动态计算行驶时间并得到一条用时最少的路径。如果缺乏路测信息，使路测模式无法工作时，通过机测模式下无人机和智能车队形成协同工作，获得车辆排队长度信息。系统里利用机测模式考虑车辆在不同车道上行驶以及多次排队情况计算出一条行驶时间最短的路径。实验证明了所提方法的有效性。接下来计划是无人机获取视频后，通过视频处理技术得到信号灯的显示及和信号灯的当前时刻。