你要去哪里？你应该朝那个方向去吗？
本文介绍了一种使用来自嘈杂GPS传感器的过去行程数据库来预测数字道路网络上的车辆轨迹的方法。除了预测未来的行驶方向外，该方法还为任意位置序列分配概率。
这个想法的核心是使用数字地图，将所有采样位置投影到地图上，通过将它们聚合成个体轨迹并将它们与地图匹配来离散化连续的GPS空间为预定位置和序列。在将这些位置编码为唯一的地理空间令牌之后，我们可以更容易地预测序列，评估当前观测的概率并估计未来的行驶方向。这是本文的要点。
问题
我在这里试图解决什么问题？如果您需要分析车辆路径数据，您可能需要回答文章副标题中的问题。
你要去哪里？你应该朝那个方向去吗？
您如何评估观察路径是否遵循常走方向的概率？这是一个重要问题，通过回答这个问题，您可以编写一个自动化系统，根据观察到的频率对行程进行分类。得分较低的新路径将引起关注并立即标记。
您如何预测车辆将做出哪些操纵？它会一直直行，还是在下一个交叉口右转？您预计在接下来的十分钟或十英里内在哪里看到车辆？对这些问题的快速回答将帮助在线跟踪软件解决方案提供答案和洞察给交付计划员、在线路线优化器，甚至是机会充电系统。
解决方案
我在这里提出的解决方案使用了一个历史轨迹数据库，每个轨迹由特定车辆的运动生成的一系列定时位置组成。每个位置记录必须包含时间、位置信息、对车辆标识符的引用和轨迹标识符。一个车辆有多个轨迹，每个轨迹有多个位置记录。下面的图1显示了我们输入数据的一个示例。
上面的数据来自Extended Vehicle Energy Dataset（EVED）[1]的文章。您可以按照我之前的一篇文章中的代码构建相应的数据库。
使用Quadkeys估计旅行时间
本文介绍了如何使用由Quadkeys索引的已知速度向量来估计旅行时间。
towardsdatascience.com
我们的第一个任务是将这些轨迹与支持的数字地图匹配。这一步的目的不仅是消除GPS数据采样误差，更重要的是将获取的行程数据强制转换为已知和固定的现有道路网络，其中每个节点和边都是已知的。因此，每个记录的轨迹都被转换为与现有数字地图节点相符的一系列数字令牌。在这里，我们将使用开源数据和软件，地图数据来自OpenStreetMap（由Geofabrik编译），地图匹配包使用Valhalla，地理空间令牌化使用H3。
边缘匹配与节点匹配
地图匹配比起初看起来更加复杂。为了说明这个概念的含义，让我们看一下下面的图2。
图2显示了我们可以从原始GPS序列中推导出两条轨迹。通过将原始GPS位置投影到最近（最可能的）道路网络段，我们得到第一条轨迹。正如你所见，由于地图使用图节点来定义其基本形状，所以得到的折线有时会沿着道路走。通过将原始位置投影到地图边缘，我们得到属于地图的新点，但连接到下一个点时可能会偏离地图的几何形状。
通过将GPS轨迹投影到地图节点，我们得到一条完全覆盖地图的路径，如图2中的绿线所示。尽管这条路径更好地表示了最初的行驶轨迹，但它不一定与原始轨迹具有一对一的位置对应关系。幸运的是，这对我们来说没有问题，因为我们将始终将任何轨迹与地图节点进行匹配，因此我们将始终得到一致的数据，只有一个例外。Valhalla地图匹配代码始终将初始和最终轨迹点投影到边缘上，因此我们将系统地丢弃它们，因为它们与地图节点不对应。
H3标记化
不幸的是，Valhalla不报告唯一的道路网络节点标识符，因此我们必须将节点坐标转换为唯一的整数标记，以便进行后续的序列频率计算。这就是H3的作用，它允许我们将节点坐标编码为一个六十四位的整数。我们选择Valhalla生成的折线，去掉初始和最终点（这些点不是节点，而是边缘投影），然后将所有剩余的坐标映射到15级H3索引。
双重图
使用上述过程，我们将每个历史轨迹转换为一系列H3标记。下一步是将每个轨迹转换为一系列标记三元组。序列中的三个值表示预测图的两个连续边，我们想要知道这些边的频率，因为它们将成为预测和概率评估的核心数据。下面的图3以可视化方式描述了这个过程。
上述转换计算了道路图的对偶，颠倒了原始节点和边的角色。
现在我们可以开始回答提出的问题了。
你应该朝那个方向走吗？
我们需要知道到给定时刻的车辆轨迹才能回答这个问题。我们使用与上述相同的过程对轨迹进行地图匹配和分词，并使用已知的历史频率计算每个轨迹三元组的频率。最终结果是所有单独频率的乘积。如果输入轨迹有一个未知的三元组，它的频率将为零，作为最终路径概率。
三元组概率是特定序列（A，B，C）的计数与所有（A，B，*）三元组的计数的比值，如下图所示。
行程概率只是各个行程三元组的乘积，如下图所示。
你要去哪里？
我们使用相同的原理来回答这个问题，但是只从最后一个已知的三元组开始。我们可以通过枚举所有以输入的最后两个标记作为其前两个标记的三元组来预测最有可能的 k 个后继。下图说明了三元组序列生成和评估的过程。
我们可以提取前 k 个后继三元组并重复这个过程来预测最有可能的行程。
实现
我们准备讨论实现细节，从地图匹配和一些相关概念开始。接下来，我们将看到如何使用 Python 中的 Valhalla 工具集，提取匹配路径并生成标记序列。将结果存储在数据库中后，数据预处理步骤将结束。
最后，我使用 Streamlit 展示了一个简单的用户界面，可以计算任何手绘轨迹的概率，然后将其投影到未来。
地图匹配
地图匹配将从移动对象路径中采样的 GPS 坐标转换为现有的道路图。道路图是基础物理道路网络的离散模型，由节点和连接的边组成。每个节点对应于道路上已知的地理空间位置，以纬度、经度和高度的元组形式进行编码。每个有向边连接相邻的节点，沿着底层道路走向，并包含许多属性，例如航向、最大速度、道路类型等。下图用一个简单的示例说明了这个概念。
当成功时，地图匹配过程会在采样轨迹上产生相关和有价值的信息。一方面，该过程将采样的GPS点投影到最可能的道路图边缘上的位置。地图匹配过程通过将观察到的点垂直放置在推断的道路图边缘上来“校正”这些观察到的点。另一方面，该方法还通过提供与采样的GPS位置相对应的道路图上最可能的路径来重构图节点的顺序。请注意，如前所述，这些输出是不同的。第一个输出包含沿最可能路径的边缘的坐标，而第二个输出由重构的图节点序列组成。下面的图8说明了这个过程。
地图匹配过程的副产品是使用共享道路网络表示标准化输入位置，特别是考虑到第二个输出类型：最可能的节点序列。将采样的GPS轨迹转换为一系列节点时，我们通过将推断的路径简化为一系列节点标识符来使它们可比较。我们可以将这些节点序列看作是已知语言的短语，其中每个推断的节点标识符是一个词，它们的排列传达行为信息。
这是我探索扩展车辆能源数据集¹（EVED）[1]的第五篇文章。该数据集是对先前工作的改进和审查，并提供了原始GPS采样位置的地图匹配版本（图8中的橙色钻石）。
不幸的是，EVED仅包含投影的GPS位置，没有重构的道路网络节点序列。在我之前的两篇文章中，我解决了从转换后的GPS位置中重新构建道路段序列的问题，但结果令人有些失望，因为我预计的缺陷重构比例低于观察到的16％。您可以从下面的文章中了解更多讨论。
使用三角形进行道路网络边缘匹配
三角形在地理空间查询中具有强大的属性
towardsdatascience.com
更多关于道路网络匹配的内容
道路网络匹配的诡计
towardsdatascience.com
现在我正在查看源地图匹配工具，看看它在纠正有缺陷的重构方面能走多远。所以让我们来测试Valhalla。以下是我在Docker容器中运行Valhalla所使用的步骤、参考资料和代码。
Valhalla设置
这里我紧密遵循Sandeep Pandey [2]在他的博客上提供的说明。
首先，确保您的计算机上已安装Docker。要安装Docker引擎，请按照在线说明进行操作。如果您使用的是Mac，一个很好的替代方案是Colima。
安装完成后，您必须从GitHub上拉取Valhalla的镜像，方法是在命令行上输入以下命令，如下所示图9中的shell代码。
图9 — 从命令行拉取Valhalla的docker镜像。（图片来源：作者）
在执行上述命令时，您可能需要输入您的GitHub凭据。另外，请确保您已经克隆了这篇文章的GitHub存储库，因为一些文件和文件夹结构是指向它的。
完成后，您应该打开一个新的终端窗口，并发出以下命令以启动Valhalla API服务器（MacOS，Linux，WSL）：
图10 — 上述命令在Docker容器中运行了拉取的Valhalla镜像。在首次执行时，该命令还会下载并准备最新的Geofabrik密歇根数据文件后才开始。（图片来源：作者）
上述命令行明确指定了从Geofabrik服务下载的OSM文件，即最新的密歇根文件。这意味着在首次执行时，服务器将下载和处理该文件，并生成优化的数据库。在后续调用中，服务器将省略这些步骤。在需要时，删除目标目录下的所有内容以刷新下载的数据并重新启动Docker。
现在我们可以使用专用客户端调用Valhalla API了。
进入PyValhalla
这个衍生项目简单地提供了对fantastic Valhalla项目的打包Python绑定。
使用PyValhalla Python包非常简单。我们从以下命令行开始进行整洁的安装过程。
图11 — 您可以使用PIP安装PyValhalla。（图片来源：作者）
在您的Python代码中，您必须导入所需的引用，从处理过的GeoFabrik文件实例化一个配置，最后创建一个Actor对象，这是连接到Valhalla API的网关。
图12 — 上述代码展示了在Python应用程序或笔记本上设置PyValhalla是多么简单。（图片来源：作者）
在调用Meili地图匹配服务之前，我们必须使用下面图13中列出的函数获取轨迹的GPS位置。
图13 — 上述函数加载车辆轨迹的唯一位置，返回一个包含纬度、经度和时间戳的Pandas DataFrame。（图片来源：作者）
现在，我们可以设置参数字典，以传递给PyValhalla调用以跟踪路径。请参考Valhalla文档以获取有关这些参数的更多详细信息。下面的函数调用Valhalla（Meili）中的地图匹配功能，并包含在数据准备脚本中。它演示了如何从包含观测到的GPS位置编码为纬度、经度和时间元组的Pandas数据帧中确定推断的路径。
图14 — 上述函数接受一个PyValhalla Actor对象和一个包含源路径的Pandas DataFrame，并返回一个地图匹配的字符串编码的折线。此字符串稍后将解码为与数字地图网络节点对应的地理位置列表，除了极端点，它们是边缘投影的。（图片来源：作者）
上述函数返回匹配的路径作为字符串编码的折线。如下所示的数据准备代码中所示，我们可以使用PyValhalla库调用轻松解码返回的字符串。请注意，此函数返回的折线的第一个和最后一个位置被投影到边缘，而不是图节点。您将在本文后面的代码中看到这些极端点被删除。
现在让我们来看看数据准备阶段，将EVED数据库中的所有轨迹转换为一组地图边缘序列，从中我们可以推导出模式频率。
数据准备
数据准备旨在将嘈杂的GPS获取轨迹转换为与已知地图位置相对应的地理空间令牌序列。主要代码逐个处理现有的行程。
在本文中，我使用SQLite数据库来存储所有数据处理结果。我们首先填充匹配的轨迹路径。您可以使用下面图15中的代码来进行描述。
图15 — 上述代码包含了预处理数据循环。此循环逐个迭代已知轨迹，计算其地图匹配路径（如果有），将节点标记化并将其扩展为三元组。代码将所有中间和最终结果存储在数据库中。（图片来源：作者）
对于每个轨迹，我们实例化一个Actor类型的对象（第9行）。这是一个未声明的要求，因为每次调用地图匹配服务都需要一个新实例。接下来，我们加载由车辆GPS接收器获得的带有噪声的轨迹点（第13行），如原始VED文章所述。在第14行，我们调用Valhalla进行地图匹配，检索字符串编码的匹配路径，并将其保存到数据库中。接下来，我们将字符串解码为地理空间坐标的列表，删除极端点（第17行），然后将它们转换为在第15级计算的H3索引列表（第19行）。在第23行，我们将转换后的H3索引和原始坐标保存到数据库中，以备以后进行逆映射。最后，在第25到27行，我们根据H3索引列表生成一个3元组序列，并将其保存以供以后的推断计算。
让我们逐步详细解释每个步骤。
轨迹加载
我们已经知道如何从数据库中加载每个轨迹（参见图13）。轨迹是一个按时间顺序排列的采样GPS位置序列，编码为纬度和经度对。请注意，我们没有使用EVED数据提供的匹配版本的这些位置。在这里，我们使用噪声和原始坐标，即它们在初始VED数据库中的存在状态。
地图匹配
调用地图匹配服务的代码已经在上述图14中呈现。它的核心问题是配置设置；除此之外，它是一个相当简单的调用。将结果编码的字符串保存到数据库中也很简单。
图16 — 上面的代码将编码的折线字符串保存到新的数据库中。（图片来源：作者）
在主循环的第17行（图15），我们将几何字符串解码为一串纬度和经度的元组列表。请注意，这是我们剥离初始和最终位置的地方，因为它们没有投射到节点上。接下来，我们在第19行将此列表转换为相应的H3令牌列表。我们使用最大细节级别来尝试避免重叠，并确保H3令牌与地图图形节点之间的一对一关系。我们在以下两行中将令牌插入数据库。首先，我们保存整个令牌列表，并将其与轨迹关联。
图17 — 上面的函数将轨迹H3令牌列表插入数据库。（图片来源：作者）
接下来，我们插入节点坐标与H3令牌之间的映射，以便根据给定的令牌列表绘制折线。这个特性在推断未来行程方向时将会很有帮助。
图18 — 我们插入H3令牌和节点坐标之间的映射，以便根据给定的推断令牌重新构建轨迹。（图片来源：作者）
现在，我们可以生成并保存相应的令牌三元组了。下面的函数使用新生成的H3令牌列表将其扩展为另一个三元组列表，如上述图3中所述。扩展代码如下图19所示。
图19 — 上面的代码将H3令牌列表转换为相应的三元组列表。（图片来源：作者）
在三元组扩展之后，我们最终可以将最终产品保存到数据库中，如下面的代码所示。通过巧妙地查询此表，我们将推断当前行程概率和未来最可能的轨迹。
图20 — 上面的函数将H3三元组保存到数据库中。这是数据准备阶段的最后一步。现在我们可以继续探索我们收集的信息了。（图片来源：作者）
我们现在已经完成了一次数据准备循环。一旦外部循环完成，我们就会有一个将所有轨迹转换为令牌序列的新数据库，我们可以随意探索。
您可以在GitHub存储库中找到完整的数据准备代码。
概率和预测
现在我们转向估计现有行程概率和预测未来方向的问题。让我们从定义“现有行程概率”开始。
行程概率
我们从通过地图匹配将任意路径投影到道路网络节点开始。因此，我们有一串来自地图的节点，并希望评估使用已知行程数据库作为频率参考的该序列的概率。我们使用上述图5中的公式。简而言之，我们计算所有单个令牌三元组概率的乘积。
为了说明这个特性，我实现了一个简单的Streamlit应用程序，允许用户在覆盖的安阿伯地区绘制任意行程，并立即计算其概率。
一旦用户在地图上绘制代表行程或假设的GPS采样的点，代码将对它们进行地图匹配以检索底层的H3令牌。从那时起，只需要计算单个三元组频率并将它们相乘以计算总概率。下面的图21中的函数计算任意行程的概率。
图21 — 上述函数从三元频率数据库中计算出任意路径的概率。（图片来源：作者）
该代码依赖于另一个函数，该函数检索任何现有的H3令牌对的后继。下面的图22中列出的函数查询频率数据库，并返回一个包含输入令牌对的所有后继计数的Python Counter对象。当查询找不到后继时，该函数返回None常量。请注意，该函数使用缓存来提高数据库访问性能（此处未列出代码）。
图22 — 上述函数查询频率数据库以获取任何H3令牌对的已知后继，并返回一个包含所有后继计数的Counter对象。（图片来源：作者）
我设计了这两个函数，使得当任何给定节点没有已知的后继时，计算出的概率为零。
让我们看看如何预测轨迹的最可能未来路径。
预测方向
我们只需要从给定的运行轨迹中获取最后两个令牌，就可以预测其最可能的未来方向。这个想法涉及到扩展该令牌对的所有后继，并选择最常见的后继。下面的代码显示了该函数作为预测方向服务的入口点。
图23 — 上述函数使用Folium中的FeatureGroup对象填充已知用户提供的行程的预测路径。（图片来源：作者）
上述函数首先将用户绘制的轨迹作为地图匹配的H3令牌列表检索并提取最后一对令牌。我们称这个令牌对为种子，并将在代码中进一步扩展它。在第9行，我们调用种子扩展函数，该函数返回与输入扩展条件（每次迭代的最大分支数和总迭代次数）对应的折线列表。
让我们通过以下图24中列出的代码了解种子扩展函数的工作原理。
图24 — 种子扩展函数使用PredictedPath类来管理每次迭代。有关此类的更多详细信息，请参见下面的内容。（图片来源：作者）
通过调用生成最佳后继路径的路径扩展函数，种子扩展函数通过从初始路径开始迭代扩展路径。如下所示，路径扩展通过选择路径并生成最可能的扩展来进行操作。
图25 — 上述路径扩展函数迭代当前路径的最常见后继。它使用一个专门的函数为每个最常见的后继创建一个新路径。（图片来源：作者）
代码通过将后继节点附加到源路径来生成新路径，如下面的图26所示。
图26 — 要生成“子”路径，我们只需要将后继节点附加到现有路径中，如下所示。请注意，在附加新节点之前，代码会创建原始路径的副本。（图片来源：作者）
代码使用一个专门的类来实现预测路径，如图27所示。
图27 — 上述类实现了具有概率排序支持、从种子令牌对创建和地图折线生成的预测路径。（图片来源：作者）
应用程序
现在我们可以在下面的图28中看到生成的Streamlit应用程序。
结论
在本文中，我介绍了一种在数字化地图道路网络中预测车辆未来轨迹的方法。利用历史轨迹数据库，该方法为任何行程分配概率，并预测未来最可能的方向。因此，该方法可以检测到从未见过的不太可能甚至是新颖的轨迹。
我们从感兴趣区域的大量车辆轨迹数据库开始。每条路径都是地理空间坐标（纬度和经度）和其他相关属性（如速度）的时间顺序。我们通常从车载GPS接收器收集这些轨迹，并将它们集中编译到数据库中。
由于信号测量过程中不可避免的错误，GPS样本存在噪声。自然和人工障碍物，例如城市峡谷，可能会显著降低信号的接收精度并增加地理定位误差。幸运的是，可行的解决方案通过概率地将GPS样本与数字地图匹配来解决这个问题。这就是地图匹配的全部内容。
通过将噪声GPS样本与已知的数字地图匹配，我们不仅通过将每个实例投影到地图上最可能的道路段来纠正精度问题，还获得了一系列现有地图定义的位置，该车辆很可能通过这些位置。这个最后的结果对于我们的轨迹预测非常重要，因为它实质上将一组噪声GPS坐标转换为数字地图中的干净且众所周知的点的集合。这些数字标记是固定的且不会改变的，通过将GPS样本序列投影到它们上面，我们可以得到一串我们以后可以用于预测的众所周知的标记。
我们使用已知标记序列频率计算所有概率，用于任意轨迹及其未来演化。结果是一对Python脚本，一个用于数据准备，另一个用于使用Streamlit平台进行数据输入和可视化。
注释
- 原论文作者在Apache 2.0许可下授权了该数据集（请参阅VED和EVED GitHub存储库）。请注意，这也适用于派生作品。
参考资料
[1] 张晟，Fatih，D.，Abdulqadir，F.，Schwarz，T.和Ma，X.（2022）。扩展车辆能源数据集（eVED）：用于车辆行程能耗深度学习的增强大规模数据集。arXiv。https://doi.org/10.48550/arXiv.2203.08630
[2] 使用Valhalla进行高效快速的地图匹配- Sandeep Pandey（ikespand.github.io）
[3] 通过Valhalla的Meili正确完成地图匹配 | 作者：Serge Zotov | Towards Data Science
João Paulo Figueira是葡萄牙里斯本Daimler Truck的tb.lx的数据科学家。