AAAI 2023 | TS-TrajGen: 基于城市个体移动模式感知的出行轨迹生成方法
©PaperWeekly 原创 · 作者 | 蒋炆峻等
单位 | 北京航空航天大学
研究方向 | 时空数据挖掘
硕士生蒋炆峻，赵鑫教授，王静远教授，硕士生姜佳伟
王静远教授
北京航空航天大学，中国人民大学
北航智慧城市课题组 BIGSCity（https://www.bigscity.com/）
论文链接：
代码链接：
模拟人类的流动性并生成大规模的轨迹在许多现实世界的应用中非常有用，诸如城市规划、流行病传播分析和轨迹隐私保护。尽管许多先前的工作已经研究了轨迹生成的问题，但是所生成的轨迹的连续性问题尚未得到解决。这限制了现有方法在实际的城市模拟场景中的应用。为了解决这个问题，本研究提出了一种新的两阶段生成对抗框架 TS-TrajGen，以生成道路网络上的连续轨迹。它有效地将人类移动性的先验领域知识与无模型学习范式相结合。
背景和贡献
建模人类个体移动模式并生成接近真实的轨迹在许多应用中至关重要。一方面，生成轨迹方法能够为城市规划、流行病传播分析和交通管控等城市假设分析场景提供仿仿真数据支撑。
例如，如果城市中发生了地震或恐怖袭击等突发事件，城市居民将如何逃散？如果城市中新修了一条高架桥，城市居民又将如何出行？在这些假设分析的场景中，单单依靠收集到的历史轨迹数据进行分析是很难得出可靠的结论的。而依赖于城市轨迹生成方法，研究人员便能够假设相应场景并进行模拟实验，从而辅助城市管理者进行决策。
另一方面，生成轨迹方法也是目前促进轨迹数据开源共享与解决轨迹数据隐私问题的可行解决方案——在不泄漏移动轨迹数据中个人隐私的情况下实现轨迹数据的开源共享。现今轨迹数据的开源共享困难很大程度上便是由于隐私问题所导致的，这阻碍了大多数现有城市数据挖掘研究。
例如，某出行公司A拥有城市内的出租车轨迹数据，而某共享自行车公司 B 拥有同一城市内的共享单车轨迹数据。如若两公司能够互相共享数据，那么二者能够更好地预测城市出行需求，从而改进相应的车辆调度服务。但碍于轨迹数据的强隐私性，公司 A 与 B 无法互相共享数据。此时，使用在数据效用上与真实轨迹相近的生成轨迹不仅可以完成数据共享改进各方服务，而且也可以避免用户隐私泄露。因此，生成具有良好数据效用的轨迹数据非常重要。
在过去的几十年中，轨迹生成问题得到了广泛研究。在早期阶段，研究人员旨在构建基于模型的方法来模拟人类移动的规律性，例如时间周期性、空间连续性。这些方法假设人类移动可以用特定的移动模式来描述，因此可以用具有明确物理意义的有限参数来建模。然而，事实上，人类移动行为表现出复杂的顺序转换规律，这些规律可能是时间依赖的和高阶的。因此，尽管这些基于模型的方法具有设计上可解释的优点，但由于实现机制的简单性，它们的性能受到限制。
为了解决上述限制，研究人员提出了主要使用神经网络生成范例（如生成对抗网络和变分自编码器）的无模型方法。与基于模型的方法不同，无模型方法放弃了特定人类移动模式的提取，而是直接构建神经网络来学习真实数据的分布，并从相同分布中生成轨迹。
然而，比较上述方法，仍然存在以下三个关键挑战需要解决：
1. 首先，忽略了生成轨迹的连续性问题。当前方法生成的轨迹不是道路网络上的连续路径，这使得这些生成轨迹无法用于下游应用，如城市交通仿真分析。
2. 其次，那些不利用人类移动先验知识的无模型方法难以有效地生成连续轨迹。
3. 最后，现有方法的随机生成过程存在误差积累问题。即在现有生成过程中轨迹是根据生成器给出的概率随机生成的。但是，一旦生成器预测错误，该过程将在错误的前提下继续生成，从而降低了生成轨迹的质量。
为了解决上述问题，本研究提出了一种融合 A* 搜索算法的城市个体移动模式感知的两阶段对抗生成网络。具体来说，本研究基于 A* 算法的个体移动模式假设构建生成器，以解决第一个挑战。在 A* 假设中，个体移动行为由两个因素决定：从起点道路到当前候选道路的已观察通行成本，以及从候选道路到目的地的预期通行成本。
结合以上两种成本，A* 算法评估哪条候选道路是下一步搜索的最佳候选道路，然后启发式地生成最优连续轨迹。因此，本研究的生成器由两部分组成：一个基于注意力的网络来学习观察到的通行成本，以及一个基于 GAT 的网络来估计预期通行成本。
针对第二个挑战，本研究基于轨迹数据的时空特性构建了鉴别器网络。该网络分别从时间序列相似性（序列奖励）和空间相似性（移动性偏航奖励）的角度来鉴别生成轨迹的真实性，以提高生成器的有效性。最后，针对第三个挑战，本研究提出了一个两阶段基于 A* 搜索的生成过程。在第一阶段，本研究在道路网络的基础上依据路网结构构建区域，然后生成区域轨迹。在第二阶段，本研究在区域轨迹的指导下生成连续轨迹。得益于该分阶段生成的方法，本研究的生成效率与有效性得到了提升。
本论文的主要贡献有以下三点：
1. 本研究首次使用 A* 算法与神经网络相结合以解决城市道路网络上连续轨迹生成问题。
2. 为了提高生成的有效性和效率，本研究构建了一个结合了序列性奖励和移动偏航奖励的鉴别器，并提出了一个两阶段生成过程。
问题定义
模型结构
3.1 基于 A* 思想的生成器
然而，使用朴素 A* 算法生成轨迹有以下两个缺陷：
3.1.1 函数构建
为了对当前已通行成本进行建模，本研究将 LSTM 网络与自我注意机制相结合以学习当前的移动状态，然后使用含拓扑约束的线性层预测已通行成本。
其中，函数 通过点积方式来计算当前移动状态 与历史移动状态 之间的相关性权重
其中，参数向量 是线性层权重矩阵的第 行。
最终，当前已通行成本 计算为条件概率的负对数：
3.1.2 函数构建
为了对未来通行成本建模，本研究假设一个人在估计从候选道路到目的地的预期成本时通常需要知道道路网络中两条道路的相对位置以及它们之间的距离。从这个角度出发，本研究使用图注意力网络从道路网络中提取相对位置信息，并计算两个路段之间的球形距离。基于以上信息，本研究最终使用多层感知器网络来估计未来通行成本 。
首先，本研究构建一个图形注意力网络 GAT 来学习包含相对位置信息的结构化道路表征。图注意力网络的更新可以表示为：
其中， 是第 次迭代的道路表征矩阵，第 行向量 为路段 的表征向量， 是道路邻接矩阵。
在网络初始化阶段，本研究构造道路上下文嵌入向量 并初始化 。具体来说，给定一个路段 ，本研究考虑 6 种道路属性，即路段长度、路段宽度、最大速度限制、车道数、道路类型以及经纬度。接着，本研究对连续属性进行归一化，对离散属性进行单热编码，并将编码后的属性连接为上下文嵌入向量 。
在获得道路表征后，本研究使用多层感知器网络来预测在目的地 条件下人类个体选择后选路段 作为下一跳的条件概率，如下公式所示：
其中， 和 是道路 与 的道路表征向量， 是它们之间的球形距离。最终，未来通行成本 计算为条件概率 的负对数，即
3.2 基于轨迹时空特性的鉴别器
一般来说，生成对抗网络通过生成器与鉴别器之间的最小-最大博弈来强化训练生成器的性能，如下所示：
其中， 表示来自真实数据分布的样本， 表示生成器生成的样本， 是 -参数化鉴别器。在上述最大最小化博弈中，鉴别器 的目标是区分输入样本，生成器 则根据鉴别器的输出信号进行自我优化。本研究将该信号称为奖励信号
在本研究中，输入样本 是一条轨迹 。而轨迹是一个具有空间信息的时间序列。因此，从轨迹的时空特性出发，本研究基于轨迹时间序列相似性与空间相似性区分输入轨迹，并生成相应的奖励信号 ，如下所示：
其中， 表示来自时间序列方面的序列性奖励。本研究使用 LSTM 网络学习轨迹中的隐藏序列转换模式来评估该相似性。 表示来自空间方面的移动性偏航奖励。本研究根据轨迹与真实轨迹的移动性偏航距离来评估该相似性。
3.2.1 序列性奖励信号
为了提取顺序转换模式，本研究方法按照 函数中的相同步骤构建序列鉴别器 ：本研究方法首先嵌入输入轨迹，并构建一个 LSTM 网络来提取轨迹中的序列转换模式。然后，本研究方法使用一个线性函数来预测输入轨迹是真实轨迹的概率，即序列性奖励 。
此外，本研究方法进一步利用蒙特卡洛搜索来评估轨迹中中间步骤的平均连续奖励，如下公式所示：
这是因为生成器的轨迹是按顺序逐步生成的，因而需要鉴别器为轨迹中的每一步提供奖励信号。然而，对于中间步骤 ，当前轨迹 仍未生成完。这意味着基于当前子轨迹 的奖励仅考虑当前子轨迹的序列转换模式，而忽略未来结果。因此，本研究方法应用蒙特卡罗搜索来评估中间步骤。
为此，本研究方法首先维护一个旧版本生成器 ，这是当前生成器的上一训练轮次的版本。然后，本研究使用 通过重复 次蒙特卡罗搜索来补完当前子轨迹，并将补完的轨迹输入 以生成中间步骤的序列性奖励 。
3.2.2 移动性偏航奖励
为了计算移动性偏航奖励信号，本研究方法首先定义偏航距离，并基于该距离计算偏航奖励信号。输入轨迹 的移动性偏航距离定义为到真实轨迹集 的最小距离，如下公式所示：
其中，本研究利用广泛使用的轨迹距离度量 DTW 来测量移动性偏航距离，真实轨迹集 包含与输入轨迹 共有相同 OD 的真实轨迹。
此外，本研究方法同样使用蒙特卡罗搜索为轨迹 中的每一步计算移动性偏航距离。移动性偏航奖励定义为偏航距离的变化：
其中，本研究进一步应用归一化来无量纲移动性偏航距离的变化。偏航距离 的变化表示当前步的移动性偏航距离与上一步相比减少了多少。因而偏航距离减小的越多，就能说明本步的决策越正确。相应地，当前步骤的奖励应该更大。
3.2.3 基于REINFORCE算法训练生成器
在训练开始时，本研究方法使用轨迹下一位置预测任务分别预训练 函数和 函数，因为它们从不同的角度对个体移动模式进行学习。然后，本研究方法根据生成的轨迹和真实轨迹预训练鉴别器。在所有预训练完成后，本研究方法按照 REINFORCE 强化学习算法来为生成器计算梯度，如下所示：
其中， 表示生成器 的参数， 是生成的轨迹，奖励 是来自鉴别器的序列性奖励 和的移动性偏航奖励 的和。基于策略梯度 ，参数 以如下方式： 更新，其中 是学习率。
3.3 两阶段生成过程
现有方法的随机生成过程存在误差累积的问题。即在该过程中，轨迹是根据生成器给出的概率随机生成，如下公式所示：
然而，一旦生成器预测错误，随机生成过程会在错误的前提状态下继续生成。特别是，当生成长轨迹时，生成器出错的概率随着生成器做出的预测数量的增加而增加。这使得生成轨迹难以到达目的地并降低生成轨迹的质量。
为了解决上述问题，本研究提出了一种基于 A* 搜索的新型两阶段生成过程。本研究方法首先在道路网络之上构建结构性区域。然后，本研究在第一阶段生成区域轨迹。在第二阶段，本研究在区域轨迹的前提下生成区域内的道路级别轨迹，从而完成连续轨迹生成。
得益于 A* 搜索，当生成器预测错误时，该生成过程可以通过回滚机制来纠正错误。因为在 A* 搜索中，生成过程维护了当前搜索到的所有可能轨迹，每次都选择代价最小（概率最大）的轨迹进行搜索。此外，通过两阶段生成，不仅降低了生成过程的空间和时间复杂度，还避免了长轨迹的生成。
具体来说，本研究方法利用多级图划分算法 KaFFPa 在道路网络之上构建结构性区域。通过 KaFFPa 算法，本研究方法可以获得相对独立的相似大小的结构区域，以及道路和区域之间的映射关系。形式上，本研究方法将道路和区域之间的映射关系描述为映射矩阵 ，其中每个元素定义为：
其中， 是路段集 中的第 路段， 是区域集 中的第 结构性区域。基于该映射矩阵 ，本研究方法可以从道路级别轨迹数据映射得到区域级轨迹数据。然后，本研究方法使用相同的生成对抗框架来学习区域级个体移动模式。
在第一阶段，本研究方法的目标是生成区域轨迹。一开始，本研究方法从历史 OD 矩阵中采样起点和终点元组 和开始时间戳 ，这可以从给定的真实世界轨迹数据集中计算。然后，本研究方法根据道路到区域的映射关系将道路级起点和终点映射到区域级起点和终点 ，其中本研究方法将 映射到 当且仅当 。以区域级起点和目的地以及开始时间戳作为输入，本研究方法基于 A* 搜索和区域级生成器生成区域轨迹。
在第二阶段，本研究方法在区域轨迹的引导下生成连续轨迹。在实践中，本研究方法构造每个区域 和区域 之间的边界路段集 ，并预先统计每个边界路段的访问频率。然后，根据如附图所示的算法过程将区域轨迹映射到道路级别。在得到不连续的路段轨迹 后，本研究方法使用道路级生成器完成 中每一对 之间的轨迹，即为最终的连续轨迹。这样，本研究方法只需要在一个小的结构性区域中生成，而不用在庞大的路网中生成。
实验
为了验证本研究所提出方法的有效性，本研究在北京、波尔图两座城市的道路网络与出租车轨迹数据集上进行了生成轨迹与真实轨迹之间的相似性实验（宏观相似性与微观相似性）。更进一步的，本研究选择了两个实际轨迹数据分析应用场景作为案例，以验证本研究所生成的轨迹数据的真实效用性。
4.1 实验设置
数据集：本实验采用的轨迹数据包含了两个真实城市的车辆轨迹数据集。
1. 北京出租车：该数据集包含 2015 年 11 月 1 日到 2011 年 11 月 7 日在中国北京市的 15,642 辆出租车的所有 GPS 轨迹数据。这些轨迹每分钟采样一次。
2. 波尔图出租车：该数据来自于 Kaggle 的轨迹终点预测比赛，包含了 2013 年 6 月 1 日至 7 月 31 日在西班牙波尔图 442 辆出租车的所有 GPS 轨迹数据。这些轨迹每 15 秒采样一次。
数据处理：对于这两个数据集，我们从 OpenStreetMap 中采集相应的路网信息，然后利用路网匹配工具 fmm 进行路网匹配，以得到真实的连续轨迹。为了消除异常轨迹，我们删除了长度小于 5 的轨迹和带有循环的轨迹。预处理后的两个数据集的统计数据如下表所示。对于每个轨迹数据集，我们将整个数据集按照 6:2:2 的比例随机分成三部分：训练集、验证集和测试集。
基线模型：本研究将所提出的出行轨迹生成模型与目前主流的五个轨迹生成模型进行对比，以验证其性能。这五个基线模型的介绍如下所示：
1. SeqGAN：该方法是经典的序列生成方法，将策略梯度与 GAN 对抗生成式神经网络相结合来解决离散序列生成问题。本实验直接应用这种方法来生成路段序列。
2. SVAE：该方法是第一个结合变分自动编码器和序列到序列模型来解决移动轨迹生成问题的方法。
3. MoveSim：该方法提出了一种无模型的生成对抗网络，其中基于自注意力的顺序建模网络用作生成器，移动规律性感知损失用作鉴别器。
4. TSG：该方法提出了一种两阶段轨迹生成 GAN。首先，它使用基于 CNN 的 GAN 网络生成基于网格的轨迹。然后，它使用基于 BiLSTM 的 GAN 网络生成最终轨迹。
5. TrajGen：该方法将轨迹映射到图像，然后使用 DCGAN 生成图像。在得到生成的轨迹图像后，该方法通过像素点与经纬度点之间的映射关系，得到生成轨迹的经纬度序列。考虑到该序列不一定为真实的个体移动序列，该方法进一步使用 Seq2Seq 模型推断真实轨迹序列。
评估指标：本实验从轨迹数据宏观相似性与微观相似性两个角度对生成数据集的有效性进行评估。从宏观角度来看，本实验考虑整体轨迹数据集表现的四个个体移动规律性指标：
1. Distance：个体轨迹的出行距离。该指标能够体现城市个体在空间上的移动步长变化规律特性。
2. Radius：个体轨迹的回转半径。该指标能够体现城市个体在空间上的移动范围变化规律特性。
3. Location Distribution：城市道路的访问概率分布。该指标能够体现城市个体对城市道路的偏好规律特性。
4. OD Flow：出发地-目的地流。该指标能够体现城市个体整体的出行需求规律特性。
从微观角度，本研究考虑生成的轨迹数据与那些出发-到达地点相同的真实轨迹之间的相似程度。本研究选择了三种最常用的轨迹距离度量指标来定量分析这种相似程度，分别是 Hausdorff 距离、DTW 动态时间规整距离、EDR 序列编辑距离。
4.2 相似性对比实验结果
在北京出租车数据集与波尔图出租车数据集上的评估实验结果如下表所示。
从宏观相似性的角度来看，本研究所提出的生成模型与第二好的模型相比将 Distance、Radius 和 Location Frequency 三项指标分别提高了 97.57%、98.94% 和 70.09% 在 BJ-Taxi 北京出租车数据集上。
而对于 OD Flow 出发地-目的地流指标，由于本研究方法将起点和目的地同时作为输入，本研究方法实现了完全还原城市真实的 OD 出行需求状态。而在基线模型中，TrajGen 模型表现最好，因为它生成的轨迹来自图像，这使得它能够随着图像分辨率的增加生成较为真实的轨迹。而其他序列生成的基线则无法模拟个体的连续移动模式。
而从微观相似性的角度来看，本研究所提出的方法成功地模拟了在给定出行-目的需求下的个体移动轨迹。并且，本研究所提出的方法相较于其他模型表现出明显的优势，这主要是因为其他基线模型忽略了目的地对人类移动行为的影响，从而无法根据出行-目的需求模拟生成轨迹。
4.3 案例研究：轨迹位置预测应用案例
轨迹下一位置预测任务旨在通过挖掘城市个体移动模式变化规律，来预测个体轨迹的未来位置。这项任务主要应用于城市场景下的个性化 POI 推荐。因此，本实验可以利用此任务来检验本研究所提出的方法生成的数据中是否蕴含真实的移动模式。
实验设置：在本案例研究中，本实验选择经典的轨迹位置预测深度学习模型 DeepMove 作为轨迹下一位置预测模型（模型源自 LibCity 城市时空预测算法库）。该模型将注意力机制引入到长短时记忆模型（LSTM）中，通过注意力机制来改善长短时记忆模型的遗忘问题。
本实验将生成的数据与真实数据以多种比例混合，并使用混合后的数据训练 DeepMove 模型。然后，本实验在真实数据上测试基于混合数据训练的 DeepMove 模型性能，并依据其与完全在真实数据上训练的模型版本之间的性能差异作为评估指标。如果生成的数据无法体现真实的个体移动模式，那么基于混合数据训练的模型将表现出较差的性能。
结果分析：本实验的实验结果如下图所示。其中，Recall@5 与 NDCG@5 为轨迹位置预测任务中常用的评估指标。横坐标 x 的值表示混合数据中真实数据所占的比例。例如，当 x 值为 100% 时，此时仅使用真实数据进行训练。
从该图中，本实验可以得出结论：本研究方法所生成的数据的有效性远超过了其他模型生成的数据。当仅使用我们生成的数据进行训练时，DeepMove 轨迹位置预测模型在 Recall@5 和 NDCG@5 指标上分别达到了在真实数据上训练的模型版本性能的 92.61% 和 88.59%。然而，在基线模型中，性能的最佳比例分别为 50.74% 和 50.47%。因而，本实验能够证明本方法所生成的数据包含真实的个体移动模式。
城市交通仿真是轨迹生成的一个重要下游应用。基于仿真的结果，研究人员能够更好地分析对城市交通的干预措施所会带来的影响，诸如交通管制措施、新道路修建等。在本案例研究中，本实验选择了北京三元桥交通管制的案例来验证本研究方法能够基于挖掘到的个体移动模式进行轨迹的仿真模拟。
实验设置：2015 年 11 月 13 日，北京市三环路三元桥因施工原因实施为期一天的交通管制。本实验收集到了当天的北京市出租车数据集。为了验证收集到的数据能够反应交通管控对城市出行的影响，本实验首先在三元桥（管控区与）附近随机可视化了 15 条交通管制当天和非交通管制日期的轨迹，如下图中的子图 a 与子图 b 所示。其中绿线是北京路网，蓝线是不同的车辆轨迹，绿色方框内的区域为三元桥。
在本案例研究中，本实验将受交通管制的道路设置为无法到达的路段，然后模拟生成三元桥附近的轨迹数据。模拟结果的部分可视化结果如上图的子图 c 所示。此外，本实验定量计算了真实轨迹和生成轨迹之间的微观相似性。微观相似性的评估指标采用前文实验所选的三个指标。然而，由于上述基线模型都不能处理交通控制情况，本实验在本案例研究中选择了两个路径规划模型作为新的基线模型：
1. A* 搜索算法：朴素的 A* 搜索算法基于路段之间的球面距离计算通行成本，并根据该成本规划出行路径。
2. NASR：该方法创新式地使用神经网络来预估 A* 搜索中的已观察成本与预期成本。
在本论文中，本课题组提出了一种新颖的两阶段生成对抗框架来解决连续轨迹生成问题，它将人类移动先验知识（A* 搜索）的优势与无模型学习范式相结合。尽管之前的许多工作都研究了轨迹生成问题，但我们是第一个直接在道路网络上生成连续轨迹的人。
广泛的实验表明，本研究所提出的框架显著优于五个现有基线模型，包括宏观相似性、微观相似性和数据效用方面。此外，通过交通控制模拟案例研究，我们证明我们的框架可以直接应用于现实世界的城市交通模拟。作为未来的工作，我们将进一步探索人类流动性的其他潜在因素，并将模拟扩展到各种应用。
引用
如果你觉得本文有用的话，请引用：
@inproceedings{ts_trajgen,
title={Continuous Trajectory Generation Based on Two-Stage GAN},
author={Wenjun Jiang and
Wayne Xin Zhao and
Jingyuan Wang and
Jiawei Jiang},
booktitle = {{AAAI}},
publisher = {{AAAI} Press},
year = {2023}
}
本文实验过程使用到了 LibCity 城市时空预测深度学习算法库。如果你对 LibCity 感兴趣的话，可以访问 Github 主页：
https://github.com/LibCity/Bigscity-LibCity
更多阅读
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。
📝 稿件基本要求：
• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题
• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算
📬 投稿通道：
• 投稿邮箱：[email protected]
• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿
△长按添加PaperWeekly小编
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
微信扫码关注该文公众号作者