基于环境约束的不确定车辆轨迹预测方法
张海基
摘要：
针对现有预测算法很少考虑环境因素，预测精度不高的问题，提出了一种基于环境约束的不确定轨迹数据预测算法（EGTP）。首先获取历史轨迹数据所处的环境信息，利用环境信息和轨迹数据构造一个新的轨迹参考点，模拟带有环境信息的车辆不确定轨迹数据；然后基于高斯混合模型，对轨迹参考点数据和历史轨迹数据进行训练；最后在训练的基础上利用轨迹参考点和历史轨迹数据对车辆轨迹实时预测。由于考虑了出行的环境因素，预测结果更符合现实情景。实验验证了该算法在实时性和预测准确度上较其它算法有所提高。
关键词：
环境约束；不确定轨迹；轨迹预测；轨迹参考点；高斯混合模型
DOIDOI：10.11907/rjdk.172248
中图分类号：TP306
文献标识码：A文章编号文章编号：16727800（2018）001004402
Abstract：In view of the existing prediction algorithms seldom consider environmental factors predicting accuracy， proposes a prediction algorithm for uncertain trajectory based on environmental constraints （egtp）， the main steps include： first， the historical data acquisition environment information， the combined data structure by using the trajectory reference point to simulate the environment information of the vehicle with uncertain trajectory； then Gauss mixture model trained on the trajectory reference point data and historical data based on the trajectory reference point and historical data using realtime prediction of vehicle trajectory. Considering the environmental factors of travel，the prediction results more realistic scenarios.Finally， the experimental results show that the algorithm is accurate in predicting real time and degree than the other algorithms are improved.
Key Words：environmental constraints； uncertain trajectory；trajectory prediction；trajectory reference point；GMM
0引言
卫星定位技术、无线通信技术和地理信息技术的迅速发展，使定位设备在车载以及移动终端上得到广泛应用。安装在公交车辆、出租车以及其它车辆上的GPS设备记录着城市交通、人群移动的动态变化[1]，将不同时刻的车辆位置信息收集起來就可构成多条完整的轨迹序列数据，可以利用这些历史轨迹数据对车辆未来轨迹进行预测。本文提出一种基于预测模型的车辆行驶轨迹预测方法。
对移动对象不确定轨迹预测有三方面：①将移动轨迹按照时间进行分段研究[2]；②基于历史轨迹数据推荐各种最优路径[3]；③挖掘历史轨迹的频繁模式预测未来轨迹[4]，其中研究成果主要集中在频繁模式挖掘上，通过挖掘轨迹频繁模式规划出最优路径并进行预测。与此同时，还有利用多种预测模型对轨迹进行预测，如贝叶斯网络[5]、混合马尔科夫模型[6]、隐马尔科夫模型[7]、高斯混合模型[89]等方法。陈勐[6]考虑到大部分人的移动模式都是有规律的，利用混合马尔可夫模型对行人要到达的下一地点进行预测。乔少杰等[7]通过将海量轨迹数据进行分区，根据输入轨迹自动选取参数的方法，提出了基于隐马尔可夫模型的自适应轨迹预测模型。
虽然利用时空轨迹对轨迹预测做了大量研究，但大部分都是利用历史轨迹进行预测，忽略了环境对预测结果的影响。本文考虑环境因素，利用参考点携带环境信息，结合高斯混合模型对车辆轨迹进行预测。
1基本概念
本文的数据模型中，移动对象数据集D由n条轨迹组成，每条轨迹由多个地点串联而成，用 D={Trj1，Trj2，…，Trjn}表示，轨迹的数量定义为|D|。
定义1定义具有环境特征的不确定移动轨迹形式为Trj=，{pi=|1<=i<=n}，其中Ci为当时所处的环境类别，为空间位置点的经纬度，ti（i=0，…，n）是相应时间戳。
定义2定义轨迹参考点 TRP（Trajectory Reference Point）。轨迹参考点由P={P1，P2，…Pn}表示，Pi=（（xi，yi），ER），其中（xi，yi）是位置坐标值，ER为环境参考信息。P的位置坐标由历史轨迹坐标计算得到， ER值从历史数据中获取。
定义3预测误差 PE（Prediction Error）采用均方根误差RMSE计算，预测轨迹点与轨迹参考点的集合空间误差：
式（1）中：（x′i，y′i）为预测轨迹点，（Pix，Piy）为轨迹参考点，k为得到的预测轨迹点数量。
2基于GMM的不确定轨迹预测模型
2.1不确定轨迹处理
为了提高预测精度，使预测结果更符合环境条件，在进行轨迹预测前需对轨迹数据进行处理，本文通过高斯混合模型聚类实现这一过程。首先通过轨迹点包含的信息值把历史轨迹粗聚类，然后利用GMM对历史轨迹数据重新聚类。其中利用KMeans算法初步计算出模型中的参数，接着根据得出的模型参数初步确定聚类簇的数量K，最后利用EM（最大似然估计）算法迭代优化KMeans初步聚类结果，最终得到 K个聚簇。
2.2TRP创建
由于获得的车辆轨迹数据往往不确定，为了确定预测模型的可靠性，采用TRP值代替获取的轨迹值。TRP由训练得到，能弥补不确定轨迹由于各种因素导致的误差。轨迹参考点中信息值的计算公式为：
式（2）中：pL（d0）为信息参考值，是信号距离为d0的路径损耗值；n为信息值的环境约束，主要包括天气情况、路面状况、交通状况等，是利用空间向量模型将环境因素数值化的值；σ表示均值为0的高斯随机变量。
TRP创建过程：①初始化轨迹参考点集TRP和集合C′；②将原始轨迹按照环境约束进行粗聚类；③将粗聚类后的轨迹数据重新聚类；④依次访问轨迹聚类簇C，将当前正在访问的簇Ci标记为“visited”；⑤根据时间窗大小对正在访问的轨迹簇Ci进行栅格化，得到n个子轨迹集；⑥遍历子轨迹集中的轨迹点N；⑦根据子轨迹集中轨迹点坐标计算出中心点坐标；⑧将步骤⑦得到的中心点坐标作为TRP的坐标点位置，将坐标中包含的环境信息值的平均值作为TRP的ER值；⑨判断Cj是否已被标记“visited”，如果已标记，则结束轨迹参考点创建，否则，执行步骤④。
2.3带有环境约束的高斯回归预测模型
将原始轨迹数据Ttrain=（x，y）用作训练数据，轨迹参考点P=（P1，P2，…，Pn），设输入数据为x，输出数据为y，将测试数据记为Ttest=（x′，y′）。回归预测模型计算步骤如下：①利用高斯模型计算输入TRP和训练输出的条件概率Py|p，并根据条件概率计算公式计算出输出值y；②利用高斯模型计算出训练输出y和预测输出y′的联合概率 P（y′y），训练输出的边缘概率Py及条件概率 P（y′|y）；③利用条件概率密度函数计算出预测输出的条件期望预测值；④得出具有环境约束的车辆轨迹回归预测模型公式如下：
为混合权重。
2.4轨迹在线预测算法实现
本文提出的带有环境约束的不确定轨迹预测算法如下：
输入：训练轨迹数据集
测试轨迹数据集
RMSEthres //误差阈值
输出：预测轨迹序列
T={s1，s2，…sd}；//已知轨迹序列
D={s1，s2，…sn}；//粗聚类后轨迹序列
Pa_F=K（Ttrain）；//初始化模型参数
F=EM（Pa_F，Ttest）；//迭代求取模型参数
TRP=CJ_trp（F）；//创建轨迹参考点
M=train（F，TRP）；//模型训练
k=n-d；
for i=1 to k
trj=pred（m）；//预测未来连续k步轨迹
PE[i]=sRMSE（trj，trjr）；//trj为预测轨迹，trjr为真实轨迹
End
RMSE=（∑ki=1PE[i]）/k；求取误差均值
RMSE
（trj）={trj1，trj2，…trjn}；
3实验结果与分析
本文采集了40 453条MIT停车场[10]车辆轨迹数据作为实验数据。其中训练轨迹数量为39 453条，测试轨迹数量为1 000条，环境情况模拟为晴天和雨雪两种。将本文算法和基于高斯混合模型轨迹预测算法、基于马尔科夫模型预测算法在准确性和时间代价上作比较，如图1、图2，实验证明，本算法更有优势。
图1为测试集合下所有轨迹预测误差的平均值。从图中可以看出，随着轨迹数量的增加，EGTP算法的预测误差最小，算法预测精度较高且比较稳定。
从图2可以看出，随着测试轨迹数量的增加，3种算法的预测时间都有所增加，但是EGTP的预测时间要比GMTP高一些，比MTP算法要低，这是因为EGTP算法在预测时考虑了环境因素，并且建立虚拟参考点也要消耗一些时间。但是在真实场景中，环境一般是稳定的，所以EGTP的时间代价相对较低。
4结语
本文提出了一种基于环境约束的轨迹预测算法，针对不同环境导致预测精度不高的问题，充分考虑了各种现实因素，在轨迹点中加入了环境特征，使预测出的轨迹更符合实际，更能描述行为趋势。
参考文献：
[1]张红，王晓明，过秀成，等.出租车GPS轨迹大数据在智能交通中的应用[J].兰州理工大学学报，2016，42（1）：109114.
[2]YOON H， SHAHABI C. Robust timereferenced segmentation of moving object trajectories[C].Eighth IEEE International Conference on Data Mining. IEEE Computer Society， 2008：11211126.
[3]郭黎敏，丁治明，胡泽林，等.基于路网的不确定性轨迹预测[J].计算机研究与发展，2010， 47（1）：104112.
[4]喬少杰，沈志强.PathExplorer：基于频繁模式的不确定性轨迹预测系统[J]. 计算机研究与发展，2012，49（suppl.）：413417.
[5]LI WANGAO， ZHAO XUEMEI， SUN DECHANG. Prediction of trajectory based on modified Bayesian inference[J]. Journal of Computer Applications， 2013，33（7）：19601963.
[6]陈勐.轨迹预测与意图挖掘问题研究[D].济南：山东大学，2016.
[7]乔少杰，李天瑞，韩楠，等.大数据环境下移动对象自适应轨迹预测模型[J].软件学报，2015，26（11）：28692883.
[8]DAI J， YANG B， GUO C， et al. Personalized route recommendation using big trajectory data[C].IEEE， International Conference on Data Engineering. IEEE， 2015：543554.
[9]乔少杰，金琨，韩楠，等.一种基于高斯混合模型的轨迹预测算法[J].软件学报，2015，26（5）：10481063.
[10]MIT[EB /OL]. http：//www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html/，2007.
（责任编辑：杜能钢）
摘要：
针对现有预测算法很少考虑环境因素，预测精度不高的问题，提出了一种基于环境约束的不确定轨迹数据预测算法（EGTP）。首先获取历史轨迹数据所处的环境信息，利用环境信息和轨迹数据构造一个新的轨迹参考点，模拟带有环境信息的车辆不确定轨迹数据；然后基于高斯混合模型，对轨迹参考点数据和历史轨迹数据进行训练；最后在训练的基础上利用轨迹参考点和历史轨迹数据对车辆轨迹实时预测。由于考虑了出行的环境因素，预测结果更符合现实情景。实验验证了该算法在实时性和预测准确度上较其它算法有所提高。
关键词：
环境约束；不确定轨迹；轨迹预测；轨迹参考点；高斯混合模型
DOIDOI：10.11907/rjdk.172248
中图分类号：TP306
文献标识码：A文章编号文章编号：16727800（2018）001004402
Abstract：In view of the existing prediction algorithms seldom consider environmental factors predicting accuracy， proposes a prediction algorithm for uncertain trajectory based on environmental constraints （egtp）， the main steps include： first， the historical data acquisition environment information， the combined data structure by using the trajectory reference point to simulate the environment information of the vehicle with uncertain trajectory； then Gauss mixture model trained on the trajectory reference point data and historical data based on the trajectory reference point and historical data using realtime prediction of vehicle trajectory. Considering the environmental factors of travel，the prediction results more realistic scenarios.Finally， the experimental results show that the algorithm is accurate in predicting real time and degree than the other algorithms are improved.
Key Words：environmental constraints； uncertain trajectory；trajectory prediction；trajectory reference point；GMM
0引言
卫星定位技术、无线通信技术和地理信息技术的迅速发展，使定位设备在车载以及移动终端上得到广泛应用。安装在公交车辆、出租车以及其它车辆上的GPS设备记录着城市交通、人群移动的动态变化[1]，将不同时刻的车辆位置信息收集起來就可构成多条完整的轨迹序列数据，可以利用这些历史轨迹数据对车辆未来轨迹进行预测。本文提出一种基于预测模型的车辆行驶轨迹预测方法。
对移动对象不确定轨迹预测有三方面：①将移动轨迹按照时间进行分段研究[2]；②基于历史轨迹数据推荐各种最优路径[3]；③挖掘历史轨迹的频繁模式预测未来轨迹[4]，其中研究成果主要集中在频繁模式挖掘上，通过挖掘轨迹频繁模式规划出最优路径并进行预测。与此同时，还有利用多种预测模型对轨迹进行预测，如贝叶斯网络[5]、混合马尔科夫模型[6]、隐马尔科夫模型[7]、高斯混合模型[89]等方法。陈勐[6]考虑到大部分人的移动模式都是有规律的，利用混合马尔可夫模型对行人要到达的下一地点进行预测。乔少杰等[7]通过将海量轨迹数据进行分区，根据输入轨迹自动选取参数的方法，提出了基于隐马尔可夫模型的自适应轨迹预测模型。
虽然利用时空轨迹对轨迹预测做了大量研究，但大部分都是利用历史轨迹进行预测，忽略了环境对预测结果的影响。本文考虑环境因素，利用参考点携带环境信息，结合高斯混合模型对车辆轨迹进行预测。
1基本概念
本文的数据模型中，移动对象数据集D由n条轨迹组成，每条轨迹由多个地点串联而成，用 D={Trj1，Trj2，…，Trjn}表示，轨迹的数量定义为|D|。
定义1定义具有环境特征的不确定移动轨迹形式为Trj=
定义2定义轨迹参考点 TRP（Trajectory Reference Point）。轨迹参考点由P={P1，P2，…Pn}表示，Pi=（（xi，yi），ER），其中（xi，yi）是位置坐标值，ER为环境参考信息。P的位置坐标由历史轨迹坐标计算得到， ER值从历史数据中获取。
定义3预测误差 PE（Prediction Error）采用均方根误差RMSE计算，预测轨迹点与轨迹参考点的集合空间误差：
式（1）中：（x′i，y′i）为预测轨迹点，（Pix，Piy）为轨迹参考点，k为得到的预测轨迹点数量。
2基于GMM的不确定轨迹预测模型
2.1不确定轨迹处理
为了提高预测精度，使预测结果更符合环境条件，在进行轨迹预测前需对轨迹数据进行处理，本文通过高斯混合模型聚类实现这一过程。首先通过轨迹点包含的信息值把历史轨迹粗聚类，然后利用GMM对历史轨迹数据重新聚类。其中利用KMeans算法初步计算出模型中的参数，接着根据得出的模型参数初步确定聚类簇的数量K，最后利用EM（最大似然估计）算法迭代优化KMeans初步聚类结果，最终得到 K个聚簇。
2.2TRP创建
由于获得的车辆轨迹数据往往不确定，为了确定预测模型的可靠性，采用TRP值代替获取的轨迹值。TRP由训练得到，能弥补不确定轨迹由于各种因素导致的误差。轨迹参考点中信息值的计算公式为：
式（2）中：pL（d0）为信息参考值，是信号距离为d0的路径损耗值；n为信息值的环境约束，主要包括天气情况、路面状况、交通状况等，是利用空间向量模型将环境因素数值化的值；σ表示均值为0的高斯随机变量。
TRP创建过程：①初始化轨迹参考点集TRP和集合C′；②将原始轨迹按照环境约束进行粗聚类；③将粗聚类后的轨迹数据重新聚类；④依次访问轨迹聚类簇C，将当前正在访问的簇Ci标记为“visited”；⑤根据时间窗大小对正在访问的轨迹簇Ci进行栅格化，得到n个子轨迹集；⑥遍历子轨迹集中的轨迹点N；⑦根据子轨迹集中轨迹点坐标计算出中心点坐标；⑧将步骤⑦得到的中心点坐标作为TRP的坐标点位置，将坐标中包含的环境信息值的平均值作为TRP的ER值；⑨判断Cj是否已被标记“visited”，如果已标记，则结束轨迹参考点创建，否则，执行步骤④。
2.3带有环境约束的高斯回归预测模型
将原始轨迹数据Ttrain=（x，y）用作训练数据，轨迹参考点P=（P1，P2，…，Pn），设输入数据为x，输出数据为y，将测试数据记为Ttest=（x′，y′）。回归预测模型计算步骤如下：①利用高斯模型计算输入TRP和训练输出的条件概率Py|p，并根据条件概率计算公式计算出输出值y；②利用高斯模型计算出训练输出y和预测输出y′的联合概率 P（y′y），训练输出的边缘概率Py及条件概率 P（y′|y）；③利用条件概率密度函数计算出预测输出的条件期望预测值；④得出具有环境约束的车辆轨迹回归预测模型公式如下：
为混合权重。
2.4轨迹在线预测算法实现
本文提出的带有环境约束的不确定轨迹预测算法如下：
输入：训练轨迹数据集
测试轨迹数据集
RMSEthres //误差阈值
输出：预测轨迹序列
T={s1，s2，…sd}；//已知轨迹序列
D={s1，s2，…sn}；//粗聚类后轨迹序列
Pa_F=K（Ttrain）；//初始化模型参数
F=EM（Pa_F，Ttest）；//迭代求取模型参数
TRP=CJ_trp（F）；//创建轨迹参考点
M=train（F，TRP）；//模型训练
k=n-d；
for i=1 to k
trj=pred（m）；//预测未来连续k步轨迹
PE[i]=sRMSE（trj，trjr）；//trj为预测轨迹，trjr为真实轨迹
End
RMSE=（∑ki=1PE[i]）/k；求取误差均值
RMSE
（trj）={trj1，trj2，…trjn}；
3实验结果与分析
本文采集了40 453条MIT停车场[10]车辆轨迹数据作为实验数据。其中训练轨迹数量为39 453条，测试轨迹数量为1 000条，环境情况模拟为晴天和雨雪两种。将本文算法和基于高斯混合模型轨迹预测算法、基于马尔科夫模型预测算法在准确性和时间代价上作比较，如图1、图2，实验证明，本算法更有优势。
图1为测试集合下所有轨迹预测误差的平均值。从图中可以看出，随着轨迹数量的增加，EGTP算法的预测误差最小，算法预测精度较高且比较稳定。
从图2可以看出，随着测试轨迹数量的增加，3种算法的预测时间都有所增加，但是EGTP的预测时间要比GMTP高一些，比MTP算法要低，这是因为EGTP算法在预测时考虑了环境因素，并且建立虚拟参考点也要消耗一些时间。但是在真实场景中，环境一般是稳定的，所以EGTP的时间代价相对较低。
4结语
本文提出了一种基于环境约束的轨迹预测算法，针对不同环境导致预测精度不高的问题，充分考虑了各种现实因素，在轨迹点中加入了环境特征，使预测出的轨迹更符合实际，更能描述行为趋势。
参考文献：
[1]张红，王晓明，过秀成，等.出租车GPS轨迹大数据在智能交通中的应用[J].兰州理工大学学报，2016，42（1）：109114.
[2]YOON H， SHAHABI C. Robust timereferenced segmentation of moving object trajectories[C].Eighth IEEE International Conference on Data Mining. IEEE Computer Society， 2008：11211126.
[3]郭黎敏，丁治明，胡泽林，等.基于路网的不确定性轨迹预测[J].计算机研究与发展，2010， 47（1）：104112.
[4]喬少杰，沈志强.PathExplorer：基于频繁模式的不确定性轨迹预测系统[J]. 计算机研究与发展，2012，49（suppl.）：413417.
[5]LI WANGAO， ZHAO XUEMEI， SUN DECHANG. Prediction of trajectory based on modified Bayesian inference[J]. Journal of Computer Applications， 2013，33（7）：19601963.
[6]陈勐.轨迹预测与意图挖掘问题研究[D].济南：山东大学，2016.
[7]乔少杰，李天瑞，韩楠，等.大数据环境下移动对象自适应轨迹预测模型[J].软件学报，2015，26（11）：28692883.
[8]DAI J， YANG B， GUO C， et al. Personalized route recommendation using big trajectory data[C].IEEE， International Conference on Data Engineering. IEEE， 2015：543554.
[9]乔少杰，金琨，韩楠，等.一种基于高斯混合模型的轨迹预测算法[J].软件学报，2015，26（5）：10481063.
[10]MIT[EB /OL]. http：//www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html/，2007.
（责任编辑：杜能钢）
