英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
基于马尔可夫模型的车辆转向预测
一、摘要
本文描述了一种车辆驾驶员用于短期路径预测的算法。它使用一个简单的马尔可夫模型，通过观察驾驶员前一段时间驾驶的路径来进行概率预测。该模型是根据驾驶员的长期行程历史GPS数据训练而来。我们设想的应用包括驾驶员警告、预期信息传递和各种自动车辆行为。该算法基于离散的路段，平均长度为237.5米。在一个实例中，该算法能以90%的精度预测下一个路段。我们探索算法的变化，找到一个既简单又准确的算法。
二、导言
向驾驶员提供之后道路的路况警告、传递预期的信息以及允许车辆自动适应预期的操作条件对预测驾驶员下一步路径的选择非常有效。本文提出了一种基于驾驶员的历史数据的预测算法。具体地说，我们训练一个n阶的马尔可夫模型，根据短时行驶的路段序列（通常为110组）概率性地预测未来地路段选择。图1给出了这种基本方法的概念图。
我们证明出结果的精度要比随机猜测好得多。例如，查看最近的10个路段，我们可以以90%的准确度预测下一个路段。该算法非常简单，足以在车载导航上进行训练和执行，并且不需要外接网络。我们通过100个驾驶员的GPS数据来测试预测的准确性。
我们对未来的预测相对较短，下一路段的范围从单一路段到10个路段不等。这些预测包括交叉路口的合并和转弯，它们很有可能会激发出有趣的应用。我们设想的应用程序如下：
- 预测驾驶员警告
① 危险路况
② 异常缓慢的交通
③ 限速变化
④ 弯道速度警告
⑤ 交通模式的变化（例如：施工）
⑥ 辅助车道保持
⑦ 车道变化预测和警告
- 驾驶员信息
① 兴趣点
② 广告
- 自动车辆的行为
① 自动转向信号
② 前照灯指向
③ 无线基站切换
④ 挡风玻璃因预期的炫光而逐渐变暗
⑤ 发动机负载预测（例如：气缸停用）
⑥ 应急准备（如预制动、安全带张力、头枕）
本文接下来将介绍我们的实验GPS数据和我们使用的道路表示法。接着介绍我们的预测算法和准确性的结果。在结果部分，我们探讨了各种不同的训练选项如何影响预测的准确性，以找到一个既简单又准确的算法。
在此之前便对路线预测开始研究的Patterson等人[6]，将机器学习应用于GPS数据以找到一个人经常光顾的位置，从而判断该人要去哪个地方。在文章[2]中，Karbassi和Barth预测了车辆在预先建立的车站之间行驶的路线。Torkkola等人[9]学习频繁的目的地以及它们之间的GPS点的规律行驶序列，以预测提供交通咨询的路线。在Froehlich和Krumm（[1]提交给美国汽车工程师学会（SAE）大会）的研究中，目标是找到驾驶员的常规行驶路线，并预测他或她当前正在驾驶的路线。本文的工作不同于以往的研究，因为我们既不关心目的地，也不关心起点到终点的路线。相反，我们的预测是自由浮动的，因为它们不一定依赖于重复的路线或目的地。我们的马尔可夫模型只需对少数路段进行一次观测就可以做出预测。
我们还注意到，本文的工作不同于我们之前关于目的地预测的工作[3,4]。在之前的工作中，我们的目标是预测司机目的地的位置，而不是预测未来的路线。本文的工作旨在预测驾驶员下一步将行驶的路段。
与我们研究最密切相关的是来自Simmons等人的研究[8]。他们训练了一个隐马尔可夫模型（与我们简单的马尔可夫模型不同）来预测驾驶员未来的路段，同时预测驾驶员的目的地。我们将在本文的其余部分解释他们的研究和我们的研究之间的区别。
三、GPS实验数据
我们的预测算法基于对驾驶员从GPS接收器测量的行驶位置的观测。从2004年3月开始，我们在微软的多人定位调查(MSMLS)中收集了志愿者司机的GPS数据。志愿司机借走我们的55个Garmin Geko 201 GPS接收器的其中一个，该记录仪能够记录10000个时间戳纬度和经度测量值。我们指示驾驶员将GPS留在车辆仪表板上，并插入点烟器中以获取电源。在某些车辆上，拔下车辆钥匙时，点烟器的电源会切断。因此，我们插入了一个小的楔形物，使GPS接收器的“开”按钮保持按下状态，以确保其在通电后始终打开。否则，驾驶员不注意的话，他会一直关着。GPS接收器设置为自适应记录模式，该模式可以在车辆行驶和加速时记录更多点。记录点之间的中间间隔为6秒和62米。虽然我们有252名受试者的数据，但为了减少实验所需的计算时间，我们选择了100名受试者的一个子集进行研究。
四、道路表现
我们使用马尔可夫模型来预测车辆的近期未来路线。更具体地说，我们使用离散马尔可夫链表示（见[7]），这将在下一节中解释。应用到我们的问题上，这个方案将车辆的状态表示为位于一组离散的路段上，如图2所示。
道路段来自我们的数字地图表示的道路网络。路段在交叉路口、死路和道路名称变更处终止。在我们研究的路段中，中位长度为237.5米(0.15英里)。在观察期间，我们的100位驾驶员共涉足43,893个不同的路段。
我们既不尝试预测车辆在路段上的位置，也不尝试预测他会何时到达路段。我们的目标是预测车辆接下来会遇到的路段。通过这种方式，我们的预测可以显示车辆的未来路径，高度和转弯。
如上所述，我们的实验数据是一组带时间戳的纬度和经度对。为了对路段进行预测，我们需要将此数据转换为路段序列。我们首先将GPS数据分割成离散的行程，将时间上相邻点之间超过5分钟的时间序列分割为任意点。这有时会导致微小的垃圾行程，因为停车的车辆GPS数据短时间内会爆炸。因此，我们过滤掉所有小于1公里（0.62英里）的行程和所有小于10个GPS点的行程。我们还去除了最大速度低于25 mph的任何行程，以帮助消除步行和骑自行车行程。
为了从我们的GPS数据中获取路段，我们将每个行程提交给我们开发的地图匹配算法[5]。地图匹配的基本过程如图3所示。
该算法考虑到附近的道路以及道路网络的连通性和速度限制所施加的约束，从而将每个GPS点与道路段进行匹配。遵守这些约束可以显著减少GPS数据中不可避免的不准确性带来的无意义匹配。例如，在不受约束的情况下与最近的道路匹配，有时会导致在平行的、相反的车道之间跳转。我们的地图匹配程序可以最大程度地减少这些错误。
在地图匹配之后，我们首先对路段进行处理，消除任何相邻的重复路段。这些数据来自同一路段上的多个GPS样本。我们还填补了空白，因此每次旅行的路段都是连续的。通过这种处理，每个行程都由一个连接的路段序列表示，没有相邻的重复。
这项工作与以前的工作之间的区别是，我们使用离散的路段作为预测的基础，正如在[2]中所做的一样。通过使用基于符号的路线描述，而不是二维点的纬度和经度，我们能够使用基于符号的预测方法，如下面描述的马尔可夫模型。
五、马尔可夫模型
我们对车辆近期未来路线的预测是基于其近期过去路线。我们将经过的路段序列建模为X()，其中表示离散时间变量，X(.)表示路段（如，所有路段中唯一的整数）。每当我们要进行预测时，我们都将车辆的路段表示为，其中是当前路段，hellip;是紧邻的前路段，是我们试图预测的未知未来路段。路段不一定是在均匀的时间间隔遇到的。离散时间变量i作为分段的索引，按照它们遇到的顺序排列。当车辆移动到新的路段时，该路段将成为新的。在任何时候，我们都知道当前路段和过去的路段可以追溯到行程开始。未知数是我们试图预测的未来路段。
在旅途中的任何时候，驾驶员都可以选择接下来要行驶的路段。根据这种选择，我们的预测是概率性的。例如，表示所有路段上的离散概率分布，给出当前路段之后将遇到的路段，即。是之后将遇到的路段的分布，依此类推。
马尔可夫模型给出了基于过去路段的未来路段的概率预测。标准的一阶马尔可夫模型表示，下一个路段的的概率分布与当前路段以外的所有路段无关:
对于给定的驾驶员，我们可以轻松构建。对于每个路段，我们先构建一个直方图，然后对其进行归一化，得到一个离散的概率分布。对于驾驶员曾经驾驶过的每个路段，都有一个单独的概率分布。
二阶马尔可夫模型对两个最近的路段很敏感。我们以类似的方式构建这个模型，只是我们创建了所有二元有序序列的直方图。在我们的研究结果中，我们检验了使用高阶模型是否有助于预测的准确性，结果确实如此。特别是，查看最近的两个路段，可以感觉到道路上的行驶方向，这一点非常有帮助。对于一阶模型，仅通过观察当前路段，不能对行进方向进行编码。
马尔可夫模型可用于预测下一个路段以外的路段。我们可以清楚地建立，这是在给定当前路段的情况下，下一个路段之后的路段分布。我们还可以使用高阶模型来进行更远的预测，例如。在一般情况下，我们可以建立一个n阶马尔可夫模型（n1）来预测未来第m段（m1）的路段。我们通常把n阶模型表示为：
在我们的结果中，我们观察预测准确性如何随着我们观察过去（更好）的片段数量的增加而变化。我们还研究了预测准确性如何随着预测片段（更糟）数量的增加而变化。
我们注意到，马尔可夫模型并未明确约束车辆遵守道路网络的连通性。一个训练有素的模型可以令人信服地预测一个司机将跳过几个路段。然而，由于该模型是从真实数据训练而来的，在实际数据中不会发生这种跳跃，因此马尔可夫模型隐式地防止了这种无意义的预测。
概率预测的一个优点是该算法可以衡量其自身的不确定性，可以将其有效地报告给车载应用。例如，自动启用转向信号灯可能取决于接近100％的预测确定性，而呈现兴趣点则不需要相同的置信度。
六、结果
在我们的MSMLS研究中，我们对来自100名驾驶员的数据测试了我们的预测算法。100名驾驶员，平均每个人观察了12.21天。在测试给定的一组参数时，例如m和n，我们使用了留一法测试，即我们用除一次行程外的所有行程来训练马尔可夫模型，并在剩余的行程中对其进行测试。每次行程都执行一次可以得到所有行程的平均准确度。留一法测试非常接近于预测算法在实际应用中的工作方式，在该应用中所有先前的行程都将用于训练。
示例结果如图4所示。这显示了根据最近观察到的十个路段来预测前方一个路段，两个和多达十个路段的准确性。我们实验的预测路段是马尔可夫模型中概率最高的路段。在这种情况下，马尔可夫模型预测下一个路段的准确率略高于90%。正如预期的那样，预测精度随着对未来的预测深入而下降。由于路段平均长度为237.5米，提前预测相当于预测接下来的237.5米(0.15英里)。在前方10个路段（2375米或1.5英里）处，我们的预测准确性为50％。
图4还显示了使用随机猜测来评估马尔科夫模型相对准确性的预测准确性。随机猜测将在每个选择点随机预测下一个路段。例如，在连接两个四通八达的十字路口的路段上(如图5)
随机算法会为六个可能的下一路段分配1/6的概率，并从中为下一路段随机选择一个。（我们在随机猜测的分析中忽略了掉头的可能性，这使得它看起来更为准确。）预测未来的两个路段将涉及其中两个随机选择。实际上，路段选择可以方便地表示为一棵树，如图6所示。
这棵树的分支系数是2，假设随着树的深入，每个节点都分裂成两个。如果分支因子为b，并且我们要预测将来的m个路段，则该将来点的可能选择数为。当然，分支因数会因路段而异，但是我们研究中遇到的道路的平均分支因数为4.04。
对于给定的预测深度?和分支因子?，随机猜测正确的概率为1/。如果我们知道行进的方向，则分支因子将减半，因为我们知道当前段的下一个端点。在这种情况下，通过随机猜测做出正确预测的概率为1 /。这两条曲线如图4所示，表明我们的预测确实比随机猜测要好得多。
Simmons等人[8]使用隐马尔可夫模型对一名46次出行的司机进行了测试，结果显示下一路段预测准确率高达99%，该模型考虑了路段和目的地预测。他们也注意到随机猜测的问题。在它们的道路网络表示中，95%的路段端点仅连接到另一个路段，提出了一种具有单一强制选择的预测算法，保证了算法的正确性。相比之下，我们只有大约28％的路段端点具有这种强制性选择。
历史路段数量的灵敏性
我们在上面展示了基于10阶马尔可夫模型的预测有多精确，即通过观察前面的10个路段来预测未来(图4)。有时，需要检查的过去路段较少，这可能是由于旅程刚刚开始，也可能是由于驾驶员记录的路段历史中没有足够长的匹配序列。
图7显示了预测精度如何随着过去观察到的路段数量而变化。这里的预测只是下一单一的路段。预测精度随着观察到的路段数量的增加而增加，这意味着更长的路段序列更能预示未来。在一个和两个观测段之间，预测精度有显著的提升这是因为只观察一个路段并不表示驾驶员的方向，这意味着车辆可能正朝着当前路段的任何一端行驶。观察两个或更多个过去的路段可指示驾驶员的方向，并减少将来路段的可能性。
此图还显示了我们在驾驶员历史记录中发现给定长度的过去序列匹配的频率。虽然准确性随着匹配序列的增长而增加，但是通常很难在驾驶员的历史记录中找到这些更长的序列。根据图7中的精度结果，最优预测算法将寻找可用的最长匹配来进行预测。
对一天中的时间的敏感性
一天的时间可以帮助预测驾驶员的未来路段。一些常规的行程可能会从穿过相同的路段开始，然后在某个十字路口根据一定的规律而分散。我们通过建立一系列的马尔可夫模型来探索这种可能性，这些模型的训练数据被限制在以实验行
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[238830]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
