PathletRL++：通过强化学习优化轨迹小路径提取和字典构建

《ACM Transactions on Spatial Algorithms and Systems》：PathletRL++: Optimizing Trajectory Pathlet Extraction and Dictionary Formation via Reinforcement Learning

　　摘要
跟踪技术的进步推动了大规模轨迹数据的快速增长。构建一个紧凑的路径片段集合，即所谓的轨迹路径片段字典，对于支持与移动性相关的应用至关重要。现有方法通常采用自上而下的方法，生成大量候选路径片段并选择其中的子集，这导致内存使用率高以及由于路径片段重叠而产生冗余存储。为了克服这些限制，我们提出了一种自下而上的策略，逐步合并基本路径片段来构建字典，与基线方法相比，内存需求减少了多达24,000倍。该方法从单位长度的路径片段开始，在优化效用的同时进行迭代合并，效用是通过新引入的轨迹损失和可表示性指标来定义的。我们开发了一个深度强化学习框架PathletRL，它利用深度Q网络（DQN）来近似效用函数，从而得到了一个紧凑且高效的路径片段字典。在合成和真实世界数据集上的实验表明，我们的方法优于现有技术，构建的字典大小减少了65.8％。此外，我们的结果还显示，只需字典中一半的路径片段就可以重构85％的原始轨迹数据。在PathletRL的基础上，我们引入了PathletRL++，通过增加更丰富的状态表示和改进的奖励函数来优化路径片段合并过程中的决策制定。这些增强使代理能够对环境有更细致的理解，从而生成更高质量的路径片段字典。PathletRL++进一步减少了字典的大小，超过了PathletRL的性能。

人工智能总结
本摘要是使用自动化工具生成的，并非由文章作者编写或审阅。它旨在帮助发现、帮助读者评估相关性，并帮助相关研究领域的读者理解这项工作。它旨在补充作者提供的摘要，后者仍然是论文的主要总结。完整文章才是权威版本。点击这里了解更多信息。点击这里评论该摘要的准确性、清晰度和实用性。这样做将有助于改进和未来的重新生成版本。要查看这段人工智能生成的简单语言摘要，您必须拥有高级访问权限。

1 引言
动机和关注的问题。收集和跟踪位置数据的技术的发展导致了大量轨迹数据的积累，这些数据包含了移动对象（如人或车辆）的空间和时间信息。由于轨迹数据在交通系统分析[36]、人类移动性[47]、基于位置的服务[62]、时空流行病[4, 42, 43]等广泛的应用中具有很高的研究价值，因此从轨迹数据中挖掘有趣的模式变得越来越重要。近年来，研究人员和实践者关注了轨迹数据挖掘中的几个技术问题，包括轨迹相似性[14]、聚类[20]、分类[5, 50]、预测[34, 35, 60]和简化[57]。关于这个主题的几项综合性调查可以在Zheng [67]、Alturi等人[8]和Hamdi等人[19]的文献中找到。除了这些已建立的任务外，最近的工作将轨迹数据挖掘视为移动性智能的基础，模型必须支持在动态城市环境中的推理、规划和适应[41]。
在这项研究中，我们专注于构建一组基本构建块的问题，这些构建块可以表示各种各样的轨迹，称为（轨迹）路径片段字典（PD）。在文献中，路径片段有许多名称，如子轨迹、轨迹段或片段[2, 10, 29, 39, 45, 64]。为了保持一致性，我们将使用路径片段这一术语来指代这些构建块。

更广泛的影响。有效地构建路径片段字典具有较高的研究和实际意义，因为它可以应用于多种任务，例如路线规划[61]、旅行时间预测[21]、个性化目的地预测[59]、轨迹预测[35, 60]和轨迹压缩[65]（有关这些应用的补充讨论，请参见附录A）。

现状和限制。许多现有工作将分析和推导路径片段的问题视为（子）轨迹聚类问题，其中（子）轨迹聚类代表了常见的路径（即路径片段）[2, 25, 51]。一些工作考虑了带有约束的整数规划公式来解决这个问题[10, 29]。一些工作根据路线“代表性”标准设计了他们的路径片段[39, 56]。不幸的是，这些现有工作存在一些限制。例如，Chen等人[10]假设使用的数据集没有噪声。Zhou等人的[68]袋段方法要求轨迹段的长度固定。Van Krevald等人[51]要求输入轨迹具有相同的起点/终点。（子）轨迹聚类方法[2, 25, 51, 54]中的聚类中心并不一定反映道路网络中的真实道路。此外，Wang等人[56]通过实验证明这些聚类方法计算速度较慢。尽管运行时间有所改进[56]还要求用户在路线代表性发现任务中提供一些预算约束B，这是一个需要领域专家知识的特定于领域的参数。另一种相关方法是Traculus[25]，它要求路径片段是直线段，而在实际的道路地图中并非总是如此。此外，所有这些工作都没有限制路径片段必须是边不相交的；如果两个路径片段不共享任何边，则认为它们是边不相交的。因此，现有工作允许字典中的路径片段（部分）重叠。这些方法在设计上遵循自上而下的方法来构建字典。这首先涉及形成所有可能的路径片段候选者，考虑各种配置和大小的路径片段，然后消除候选者以形成一个仅包含最重要路径片段的更小字典（例如，最受欢迎的路径片段）。虽然简单直观，但其主要限制是需要大量内存来最初存储大量的路径片段，其中大多数是多余的。这也限制了其在现实世界设置中的适用性，特别是在处理大型道路网络和轨迹数据时，因为初始候选者的数量可能会迅速变得难以处理。

我们的方法和贡献。为了应对这些限制，我们提出了一种自下而上的方法来构建符合边不相交路径片段的PD（见图1），并减少了内存存储需求。例如，在图2中，我们展示了我们提出的方法比现有方法节省了多达约24K×的内存空间（有关详细信息，请参见实验（Q2），附录C提供了更多的理论证明）。我们方法的关键思想是初始化单位长度的路径片段，并在最大化效用的同时逐步合并它们，以形成更长、更高阶的路径片段[3, 31]。较长的路径片段更受青睐（因为它们包含了更多的时空信息，如轨迹中的移动模式[10]）。提出了一种深度强化学习方法来近似效用函数。我们的贡献总结如下：
图1. (a) 多伦多一个小区域的图形表示；(b) (a)中各种长度的边不相交路径片段的例子。
图2. 我们提出的自下而上解决方案使用的边不相交路径片段可以减少自上而下（现有）方法所需的内存。
- 我们引入了比以往工作中更严格的路径片段定义，以符合边不相交路径片段的要求。这使得构建路径片段字典时可以减少内存存储需求。
- 我们引入了两个新的指标，即轨迹损失和轨迹可表示性，使我们能够更全面地评估路径片段的效用以及构建的PD的整体质量。
- 我们将PD构建问题表述为一个效用最大化问题，其中较短的路径片段被合并以形成一组具有更高效用的较长路径片段。
- 我们提出了PathletRL，这是一种深度强化学习方法，它利用深度Q网络（DQN）策略来近似构建PD的效用函数。据我们所知，这是首次尝试使用深度学习方法来解决这个问题。
- 我们通过引入优化技术来解决原始PathletRL模型的局限性，以提高构建的路径片段字典的质量和稳定性，确保在轨迹建模中的关键目标之间有更好的权衡。
- 我们引入了PathletRL++，它通过结合更丰富的状态表示和更强大的奖励函数来优化路径片段合并过程中的决策制定。这一扩展显著提高了构建的PD的稳定性和质量。PathletRL++的新颖之处在于它将这些针对性的创新、增强的图感知嵌入、先进的多目标标量化技术和更丰富的状态表示集成到了现有的DQN框架中，这种方法与跨领域的专门RL框架的发展一致。
- 我们通过实验证明，由我们的PathletRL及其扩展构建的字典质量优于传统的非学习基方法。我们的方法将字典的大小减少了65.8％。此外，使用字典中只有一半的路径片段就足以重构85％的原始轨迹数据。
- 我们将代码开源，以鼓励可重复性。

论文组织
本文的其余部分组织如下。第2节介绍初步内容和问题的正式定义。第3节概述我们的方法论和所提出方法的详细信息。第4节描述实验设置、展示结果并提供有意义的讨论。第5节介绍对原始PathletRL框架的优化和扩展。第6节回顾相关工作，第7节进行总结。

2 初步内容和问题定义
在本节中，我们简要介绍一些定义和符号（见表1）。然后，我们正式定义所关注的问题。
表1. 符号定义
\(\tau\) 和 \(\mathcal {T}\) 一条轨迹 \(\tau\) 和一组轨迹 \(\mathcal {T}\)
\(\mathcal {G} \langle \mathcal {V}, \mathcal {E} \rangle\) 带有交叉口的道路网络 \(\mathcal {V}\) 和路段 \(\mathcal {E}\)
\(\rho\) 和 \(\mathcal {P}\) 一个路径片段 \(\rho\) 和一组路径片段 \(\mathcal {P}\)
\(\mathcal {G}_p \langle \mathcal {V}_p, \mathcal {E}_p \rangle\) 道路网络 \(\mathcal {G}\) 的路径片段图表示
\(\Psi (\rho)\) 路径片段 \(\rho\) 的邻居
\(\Phi (\tau)\) 基于路径片段的轨迹 \(\tau\) 的表示
\(\Lambda (\rho)\) 路径片段 \(\rho\) 的轨迹遍历集
\(\mu (\tau)\) 轨迹 \(\tau\) 的可表示性
\(L_{traj}\) 轨迹损失
\(\mathbb {S}\) 路径片段字典
\(\phi\) 在 \(\mathcal {T}\) 中表示每个 \(\tau\) 的平均路径片段数量

2.1 主要定义和符号
定义2.1（轨迹）。设 \(\mathbf {O} = \lbrace o_1, o_2, \ldots , o_{|\mathbf {O}|} \rbrace\) 是在某个地理地图 \(\mathcal {M} \subset \mathbb {R}^2\) 中的一组移动对象。单个对象 \(o \in \mathbf {O}\) 的轨迹 \(\tau\) 可以表示为一系列带时间戳的地理坐标点：\(\tau = \left\langle \left(x_1, y_1, t_1 \right), \ldots , (x_{|\tau |}, y_{|\tau |}, t_{|\tau |}) \right\rangle\)，其中每个 \(x_i\) 和 \(y_i\) 分别代表对象 \(o\) 在特定时间实例 \(t_i \in [0,T]\) 的经度和纬度坐标。我们让 \(|\tau |\) 表示其长度，或者说是轨迹的时间戳点数量。此外，我们让轨迹（数据）集 \(\mathcal {T}\) 包含所有 \(o \in \mathbf {O}\) 的所有轨迹：\(\mathcal {T} = \bigcup _{o \in \mathbf {O}} \, \mathcal {T}_o\)，其中 \(\mathcal {T}_o\) 是所有 \(o\) 的轨迹集合。
定义2.2（道路网络）。我们用 \(\mathcal {G} \langle \mathcal {V}, \mathcal {E} \rangle\) 表示地图 \(\mathcal {M}\) 内的道路网络，其中 \(\mathcal {V}\) 和 \(\mathcal {E} \subseteq \mathcal {V} \times \mathcal {V}\) 分别表示 \(\mathcal {G}\) 的道路交叉口（节点）和路段（边）。
在 \(\mathcal {M}\) 之外的轨迹点（GPS轨迹）作为预处理步骤被过滤掉。剩余的轨迹还需要进行地图匹配（详见附录D）。有了地图匹配的数据，我们现在可以正式定义本工作中的基本构建块。
定义2.3（路径片段）。路径片段 \(\rho\) 被定义为道路网络 \(\mathcal {G}\) 中的任何子路径（即连续的连接路段序列），\(\mathcal {P}\) 是所有这样的路径片段的集合。
在我们的工作中，我们考虑边不相交的路径片段，即没有两个 \(\rho _1, \rho _2 \in \mathcal {P}\) 共享任何边。为了简单起见，我们假设路径片段是离散的——意味着它们在图的交叉口开始和结束（节点，起点/终点在 \(\rho .s\)/\(\rho .e\)），但这项工作可以很容易地推广到包括不遵循此限制的连续路径片段。
用 \(\ell\) 表示路径片段 \(\rho\) 在道路网络中的路径长度。具体来说，\(\ell\) 计算了构成路径片的 road segments（边）的数量，这是从图谱上下文中得出的，并且不应与 road segment 的物理距离测量混淆。单位长度的路径片（即单个 road segments）的长度为 \(\ell = 1\)。此外，我们将所有路径片 \(\rho \in \mathcal {P}\) 限制在长度 \(\ell \le k\) 的范围内，这里的 k 是用户定义的。在这种情况下，我们称 \(\mathcal {P}\) 为一个 k-阶路径片集合。定义 2.5（路径片图）。路径片图 \(\mathcal {G}_p \langle \mathcal {V}_p, \mathcal {E}_p \rangle\) 是从物理 road 网络 \(\mathcal {G} \langle \mathcal {V}, \mathcal {E} \rangle\) 中抽象出来的表示。在这个抽象图中，节点 \(\mathcal {V}_p\) 对应于路径片本身，而边 \(\mathcal {E}_p\) 代表它们之间的连通性。重要的是，虽然 \(\mathcal {G}\) 表示物理基础设施，但 \(\mathcal {G}_p\) 表示抽象的可合并性图，其中如果有 directed edge \((u, v) \in \mathcal {E}_p\)，则意味着在字典构建过程中路径片 u 可以与路径片 v 顺序合并。例如，图 1(a) 表示了多伦多一个较小区域的图谱表示，而 (b) 描述了不同长度的一些路径片。在我们的工作中，我们考虑一个初始路径片图，其中每个路径片的长度为 \(\ell = 1\)。定义 2.6（路径片邻居）。给定一个路径片 \(\rho \in \mathcal {P}\)，它的邻居路径片表示为 \(\Psi (\rho)\)，即所有与其他路径片 \(\rho ^{\prime } \in \mathcal {P} \setminus \lbrace \rho \rbrace\) 共享一个端点的路径片：\[\begin{equation*} \Psi (\rho) = \bigcup _{\rho ^{\prime } \in \mathcal {P} \setminus \lbrace \rho \rbrace , \, (\rho .s \in \lbrace \rho ^{\prime }.s, \rho ^{\prime }.e\rbrace) \vee (\rho .e \in \lbrace \rho ^{\prime }.s, \rho ^{\prime }.e\rbrace)} \rho ^{\prime } \end{equation*}\] 例如，图 1(b) 中的灰色路径片有两个邻居：橙色和蓝色的路径片。定义 2.7（基于路径片的轨迹表示）。轨迹 \(\tau \in \mathcal {T}\) 可以基于路径片集合 \(\mathcal {P}_{sub} \subseteq \mathcal {P}\) 的某个子集来表示。此外，\(\mathcal {P}_{sub}\) 中的路径片可以按某种顺序连接起来，从而形成 \(\tau\) 在 road 网络 \(\mathcal {G}\) 上的路径。我们用 \(\Phi (\tau) = \lbrace \rho ^{(1)}, \rho ^{(2)}, \ldots , \rho ^{(|\mathcal {P}_{sub}|)} \rbrace\) 来表示这一点，其中 \(\rho ^{(i)} \in \mathcal {P}_{sub}\) 表示表示 \(\tau\) 的路径片序列中的第 i 个路径片。注意，当 \(\mu (\tau)\lt 100\%\) 时，\(\Phi (\tau)\) 可能不能完全覆盖 \(\tau\)（见定义 2.9）。基于此，我们还可以定义轨迹的路径片长度，在构建路径片图之前先设定这个值。每个轨迹 \(\tau \in \mathcal {T}\) 的路径片长度等于 \(\sum _{\rho \in \Phi (\tau)} \ell (\rho)\)，这个值在整个路径片合并过程中保持不变。定义 2.8（路径片的轨迹遍历集）。设 \(\Lambda (\rho)\) 为所有通过或遍历路径片 \(\rho \in \mathcal {P}\) 的轨迹 \(\tau \in \mathcal {T}\) 的集合。这也可以写成 \(\Lambda (\rho) = \lbrace \tau \, | \, \forall \tau \in \mathcal {T}, \, \rho \in \Phi (\tau) \rbrace\)。我们还可以为路径片分配权重 \(\omega\)。在无权重的情况下，所有路径片的权重相同；而在加权版本中，路径片的权重根据遍历该路径片的轨迹的归一化数量来确定，即 \(\omega (\rho) = \frac{|\Lambda (\rho)|}{|\mathcal {T}|}\)。这些权重表明了每个路径片在 road 网络/路径片图中的重要性。

2.2 新颖的轨迹度量
现在我们可以介绍一些新颖的度量标准，以便更全面地评估我们的路径片和路径片字典。
定义 2.9（轨迹可表示性）
轨迹 \(\tau\) 的（轨迹）可表示性 \(\mu \in [0\%,100\%]\) 表示使用路径片集合 \(\mathcal {P}\) 可以表示的 \(\tau\) 的百分比。显然，基于路径片的 \(\tau\) 的表示与其可表示性直接相关，即对于无权重情况 \(\mu (\tau) = \sum _{\rho \in \Phi (\tau)} \frac{\ell (\rho)}{|\tau |}\)，对于加权版本 \(\mu (\tau)\) = \(\sum _{\rho \in \Phi (\tau)} \omega (\rho)\)。注意，通过归一化 \(\omega (\rho) = \frac{|\Lambda (\rho)|}{|\mathcal {T}|}\)，这一公式确保了 \(\mu \in [0,1]\)（或 `[0\%, 100\%]\)。
定义 2.10（轨迹损失）
我们定义轨迹损失 \(L_{traj}\) 为具有可表示性值 \(\mu = 0\%\) 的轨迹 \(\tau \in \mathcal {T}\) 的数量，即 \(L_{traj} = |\lbrace \tau | \tau \in \mathcal {T}, \, \mu (\tau) = 0 \rbrace |\)。我们也可以将这些轨迹描述为从给定轨迹集 \(\mathcal {T}\) 中“丢失”或“丢弃”的轨迹，并且可以将这个数字表示为百分比。随着我们详细讨论方法论，这两个度量的相关性和影响将会变得清晰。

2.3 问题定义
在正式化问题之前，我们首先介绍 PD 和一些优化定义。
定义 2.11（路径片字典）
（轨迹）PD 是一种数据结构，用于存储路径片 \(\rho \in \mathcal {P}\）（键）及其相关的轨迹遍历集 \(\Lambda (\rho)\）（值）。
见图 3。
图 3. PathletRL 架构概述。该框架将 DQN 学习与基于路径片的 road 网络抽象相结合。（左）DQN 代理与 road 网络环境交互：观察 \(s_t\)，通过 \(\epsilon\)-greedy 选择 \(a_t\)，接收奖励 \(R_t\)，并将转换存储在重放记忆中。（中）原始地图 \(\rightarrow\) 单位长度路径片（\(\ell =1\)）的初始图。（右上）轨迹数据映射到长度为 1 的路径片以构建初始字典。（右下）由 DQN 策略指导的迭代合并产生了一个紧凑的多尺度字典（\(\ell =1,2,\ldots ,k\)），在可表示性、紧凑性和重建质量之间进行权衡。当轨迹损失 \(\gt M\)、平均可表示性 \(\lt \mu _{\text{threshold}}\) 或没有路径片剩下时终止。（橙色和蓝色面板内的右侧框）用于说明 PD 的一个示例。我们感兴趣的是构建一个 PD，旨在实现以下一个或多个目标：
(O1) 候选路径片集 \(\mathbb {S}\) 的最小尺寸，或者具有最少路径片数量的候选集（即 \(\min |\mathbb {S}|\)）
(O2) 最小 \(\phi\)，或者表示每个轨迹 \(\tau \in \mathcal {T}\) 的平均路径片数量（即 \(\min \phi = \min \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} |\Phi (\tau)|\)
(O3) 最小轨迹损失 \(L_{traj}\)（即 \(\min L_{traj}\)）
(O4) 最大 \(\bar{\mu }\)，或者剩余轨迹的平均可表示性值（即 \(\max \bar{\mu } = \max \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} \mu (\tau)\)
换句话说，我们希望优化的目标函数基于上述四个目标——可以建模为：
\[\begin{equation} \min \left(\alpha _1 |\mathbb {S}| + \alpha _2 \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} |\Phi (\tau)| + \alpha _3 L_{traj} - \alpha _4 \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} \mu (\tau) \right), \quad \text{s.t.} \sum _i \alpha _i = 1 , \end{equation} (1)\]
其中 \(\alpha _i\) 是用户定义的目标权重。注意，所有组成部分（(\(|\mathbb {S}|\), \(\phi\), \(L_{\text{traj}}\), \(\bar{\mu }\) 都被归一化到 \([0,1]\) 以确保数值可比性。尽管如此，线性标量化仍然对权重分配敏感；这促使我们在第 5 节中引入了 Chebyshev 和动态标量化。

问题 1（路径片字典构建）
给定一个特定地图 \(\mathcal {M}\) 的 road 网络 \(\mathcal {G}\langle \mathcal {V}, \mathcal {E} \rangle\)、轨迹集 \(\mathcal {T}\)、最大路径片长度 k、最大轨迹损失 M 和平均轨迹可表示性阈值 \(\hat{\mu }\)，构建一个 k-阶 PD \(\mathbb {S}\)。字典 \(\mathbb {S}\) 由长度最多为 k 的不相交的路径片组成，并根据某些效用函数实现最大可能的效用，如图 (1) 所示，使得 \(L_{traj} \lt M\) 且 \(\bar{\mu } \ge \hat{\mu }\)。

3 方法论
我们现在描述我们解决问题的方法（其架构见图 3）。特别是，我们描述了所提出的 PathletRL 模型的组成部分（使用强化学习构建路径片字典）。有两个主要组成部分：（1）负责通过基于合并的过程提取候选路径片集的方法；（2）一个基于深度强化学习的架构，用于近似合并过程的效用函数。

3.1 提取候选路径片
在本节中，我们详细描述了合并我们不相交的路径片的算法。该算法的高层次思想基于最大效用理论 [3, 31]，即迭代合并（相邻的）路径片，直到这对效用几乎没有改进（效用的详细信息稍后给出）。该算法输入一个 road 网络 \(\mathcal {G}\)、在 \(\mathcal {G}\) 中操作的轨迹集 \(\mathcal {T}\)、轨迹损失的最大阈值 M、轨迹可表示性阈值 \(\hat{\mu }\) 以及表示所需 k-阶路径图的正整数 k。作为输出，它返回一个符合定义 2.11 中描述的路径片信息的 PD。提取的 PD 旨在满足四个目标 (O1)-(O4)。详见算法 1 的伪代码。

初始化。算法首先设置一个空的候选集 \(\mathcal {C} = \emptyset\) 来跟踪已处理的路径片。它从输入的 road 网络 \(\mathcal {G}\) 构建初始路径片图 \(\mathcal {G}_p\)，该图由长度为 1 的初始路径片组成。对于每个轨迹 \(t_i \in \mathcal {T}\)，它计算初始轨迹覆盖率 \(\phi\)（定义为表示每个轨迹所需的平均路径片数量，见目标 O2）和可表示性 \(\mu\)。从未处理的路径片集合 \(\mathcal {G}_p \setminus \mathcal {C}\) 中随机选择一个初始路径片 \(p_{\text{current}}\)。

迭代算法。算法在一个循环中运行，在每次迭代中，代理观察环境的当前状态 \(s_t\) 并使用 DQN 的 \(\epsilon\)-greedy 策略选择一个动作 \(a_t\)。动作定义如下：
— 跳过动作 (\(a_t = 0\))：代理选择跳过当前的路径片 \(p_{\text{current}\)，通过将其添加到 \(\mathcal {C}\) 来标记它为已处理。如果仍有未处理的路径片（即 \(\mathcal {G}_p \setminus \mathcal {C} \ne \emptyset\)），代理从这个集合中随机选择一个新路径片作为下一个 \(p_{\text{current}}\)。否则，流程终止，并生成最终的 PD \(\mathcal {S}\)。
— 合并动作 (\(a_t \gt 0\))：代理根据动作 \(a_t\) 选择一个相邻的路径片 \(p_{\text{neighbor}}\) 与当前路径片 \(p_{\text{current}}\) 合并。如果合并这两个路径片产生的新路径片长度不超过允许的最大长度 k，则将它们合并形成一个新的路径片 \(p_{\text{merged}}\)。相应地更新遍历集 \(\Lambda (p_{\text{merged}}\) 和路径片图 \(\mathcal {G}_p\)。现在覆盖率为零的轨迹从轨迹集 \(\mathcal {T}\) 中移除。重新计算指标 \(\phi\)、\(\mu\) 和轨迹损失 \(L_{\text{traj}}\)。然后代理将 \(p_{\text{current}}\) 更新为新形成的 \(p_{\text{merged}}\)。如果由于长度限制无法合并，则代理将其视为跳过动作。在每次迭代中，代理根据 PD 的大小变化 \(|\mathcal {S}|\)、可表示性 \(\mu\)、轨迹损失 \(L_{\text{traj}}\) 和每个轨迹的平均路径片数量 \(\phi\) 计算奖励 \(R_t\)。转换 \((s_t, a_t, R_t, s_{t+1})\) 被存储在经验重放缓冲区中，DQN 使用采样经验更新其 Q 网络。循环继续进行，直到满足其中一个终止条件：轨迹损失超过阈值 M、平均可表示性 \(\mu\) 低于阈值 \(\mu _{\text{threshold}}\)，或者没有未处理的路径片剩下。

效用函数。为了完成算法的描述，我们讨论了我们使用基于学习的方法近似的效用函数的公式。特别是，利用强化学习方法来学习（序列的）动作（即合并或不合并路径片），以获得最高的效用。具体来说，我们将效用函数构建为一个我们希望优化的奖励函数（即最大化）。我们将在下一节讨论这一设计的细节。

通过基于效用理论的路径片合并过程构建的 PD，我们可以得到如图 3（右下角图）所示的结果。现在我们提供一个简单的示例。
示例 3.1。由于不相交的路径片不重叠，因此在路径片即将与其相邻路径片合并时需要做出决策。因此，与某个特定路径片合并有一些优势或收益，但这种行动也伴随着一些成本。这就是轨迹表示能力和损失发挥作用的地方。更具体地说，当轨迹的一部分由于与相邻轨迹合并而无法表示时，该轨迹的表示能力就会下降。举一个更具体的例子，考虑图4(a)中的道路网络片段。图4(b)展示了其网格表示，而图6(a)的左图展示了（初始的）轨迹图表示，在图中我们用不同的颜色标出了相关的九个轨迹片段。请参见图6(b)的左图，了解这些轨迹片段的标签及其在表2中的颜色代码。最初，我们的路径组合（PD）由以下轨迹组成，这些轨迹在图5的网格图中用紫红色标出（它们的基于轨迹的表示在表3中）：
$$
\begin{align*}
&\rho _1 : \lbrace \tau _5 \rbrace \\
&\rho _2 : \lbrace \tau _2, \tau _3 \rbrace \\
&\rho _3 : \lbrace \tau _2, \tau _3, \tau _5 \rbrace \\
&\rho _4 : \lbrace \tau _2, \tau _4, \tau _5 \rbrace \\
&\rho _5 : \lbrace \tau _1, \tau _4 \rbrace \\
&\rho _6 : \lbrace \tau _4 \rbrace \\
&\rho _7 : \lbrace \tau _1, \tau _6 \rbrace \\
&\rho _8 : \lbrace \tau _1, \tau _4, \tau _6 \rbrace \\
&\rho _9 : \lbrace \tau _1, \tau _6 \rbrace
\end{align*}
$$
图4. 示例3.1的说明性示例：(a) 一个简单的道路网络的玩具示例；(b) (a)的网格表示。
图5. 示例3.1中六条轨迹（\(\lbrace \tau _1, \tau _2, \tau _3, \tau _4, \tau _5, \tau _6 \rbrace\)）所经过的路径（道路段）的说明性示例，如图4所示；请参见表3，其中列出了每条轨迹的基于轨迹的顺序表示。
图6. 初始和最终轨迹图表示的轨迹片段标签。
表2. 轨迹片段颜色代码
\(\rho _1\) 红色
\(\rho _2\) 紫色
\(\rho _3\) 橙色
\(\rho _4\) 黄色
\(\rho _5\) 蓝色
\(\rho _6\) 粉色
\(\rho _7\) 棕色
\(\rho _8\) 绿色
\(\rho _9\) 灰色
\(\rho _{134}\) 橙黄色
\(\rho _{58}\) 海蓝色
表3. 示例3.1中玩具示例的轨迹片段颜色编码
表3. 基于轨迹的表示集合\(\Phi\)（表示能力\(\mu\)）（合并前）（合并后）
\(\tau _1\) \(\lbrace \rho _5, \rho _8, \rho _9, \rho _7 \rbrace\)（100%）
\(\lbrace \rho _{58}, \rho _9, \rho _7 \rbrace\)（100%）
\(\tau _2\) \(\lbrace \rho _2, \rho _3, \rho _4 \rbrace\)（100%）
\(\lbrace \rho _2 \rbrace\)（33%）
\(\tau _3\) \(\lbrace \rho _3, \rho _2 \rbrace\)（100%）
\(\lbrace \rho _2 \rbrace\)（50%）
\(\tau _4\) \(\lbrace \rho _4, \rho _6, \rho _8, \rho _5 \rbrace\)（100%）
\(\lbrace \rho _6, \rho _{58} \rbrace\)（75%）
\(\tau _5\) \(\lbrace \rho _4, \rho _3, \rho _1 \rbrace\)（100%）
\(\lbrace \rho _{134} \rbrace\)（100%）
\(\tau _6\) \(\lbrace \rho _7, \rho _9, \rho _8 \rbrace\)（100%）
\(\lbrace \rho _7, \rho _9 \rbrace\)（67%）
示例3.1中提供的玩具示例的基于轨迹的表示集合（及轨迹表示能力）
在整个合并过程结束后，算法返回以下最终字典——其在图6(a)（右图）中的表示，以及其在图6(b)（右图）中的标签、在表2中的颜色代码，还有轨迹的更新后的表示能力和基于轨迹的表示，在表3中：
$$
\begin{equation*}
\rho _{134} : \lbrace \tau _5 \rbrace \\
\rho _2 : \lbrace \tau _2, \tau _3 \rbrace \\
\rho _{58} : \lbrace \tau _1, \tau _4 \rbrace \\
\rho _6 : \lbrace \tau _4 \rbrace \\
\rho _7 : \lbrace \tau _1, \tau _6 \rbrace \\
\rho _9 : \lbrace \tau _1, \tau _6 \rbrace
\end{equation*}
$$
请注意，初始轨迹图中的轨迹片段\(\rho _1\)、\(\rho _3\)和\(\rho _4\)合并成了最终轨迹图中的轨迹片段\(\rho _{134}\）（在这个例子中，轨迹片段\(\rho _3\)是先与\(\rho _1\)合并还是先与\(\rho _4\)合并并不重要）。轨迹片段\(\rho _5\)和\(\rho _8\)也是如此，它们合并成了轨迹片段\(\rho _{58}\)。
最初，所有轨迹的表示能力值\(\mu = 100\%)\)，因为所有六条轨迹都可以通过初始路径组合中的轨迹片段来表示。然而，在整个合并过程之后，一些原始轨迹的表示能力值\(\mu\)降低了。例如，轨迹\(\tau _1\)的表示能力值没有下降，因为其初始基于轨迹的表示\(\Phi\)中的所有轨迹片段要么从未合并，要么是与属于\(\Phi (\tau _1)\)的相邻轨迹片段合并的。换句话说，轨迹\(\tau _1\)的整个路径仍然可以通过最终路径组合中的轨迹片段来表示；因此，其表示能力保持在100%。轨迹\(\tau _5\)的情况也是如此。对于其他轨迹来说，它们的表示能力较低。以轨迹\(\tau _2\)为例，其\(\Phi (\tau _2) = \lbrace \rho _2, \rho _3, \rho _4 \rbrace\)。然而，在算法处理后，我们只剩下\(\Phi (\tau _2) = \lbrace \rho _2 \rbrace\)；原因是轨迹片段\(\rho _1\)、\(\rho _3\)和\(\rho _4\)都合并成了\(\rho _{134}\)。但由于\(\rho _1\)不能表示轨迹\(\tau _2\)，因此在完成迭代算法后，合并后的\(\rho _{134\)不再属于\(\Phi (\tau _2)\)。因此，其表示能力下降是意料之中的。对于轨迹\(\tau _3\)、\(\tau _4\)和\(\tau _6\)也是如此。
注释：可以想象，在迭代算法的每一步中，轨迹的表示能力都可能下降，直到降为零。如果轨迹的表示能力降为零，它将从轨迹集合中移除，并被视为轨迹损失。这只是所谓的轨迹损失的温和版本。还有一种更严格的形式，即轨迹的表示能力完全消失（例如，由于轨迹片段合并导致轨迹仅失去了一小部分表示能力），这意味着整个轨迹都被视为丢失，这可能会对模型和算法的性能产生严重影响。直观上，当（比如说）只有1%的轨迹无法通过轨迹片段合并来表示时，人们可能不希望丢弃整个轨迹。后续的实验评估将展示这种考虑轨迹表示能力的温和版本的本质。
定理3.1（轨迹表示能力定理）。算法1在每次迭代中都能保证轨迹表示能力的维持。具体来说，迭代i结束时某条轨迹\(\tau \in \mathcal {T}\)的表示能力\(\mu\)由以下公式给出：
$$
\mu _i(\tau) = \frac{\sum _{\rho ^{\prime } \in \Phi _i(\tau)} \ell (\rho ^{\prime }) }{ \sum _{\rho \in \Phi _0(\tau)} \ell (\rho) }
$$
其中\(\Phi _0\)和\(\Phi _i\)分别是迭代算法初始阶段（迭代0）和迭代i阶段中轨迹\(\tau\)的基于轨迹的表示。这个公式确保了正确计算在i次合并操作后原始轨迹还有多少部分是可表示的。我们建议读者参考附录B，其中提供了该定理的完整证明。
3.2 强化学习背景
对于已经熟悉强化学习和DQN的读者，可以直接跳到第3.3节。对于新接触这个主题的读者，我们提供了基本概念的简要概述，以帮助理解我们的框架。
马尔可夫决策过程（MDP）。MDP模型描述了决策过程，其中结果部分是随机的，部分受代理的控制。它包括：
—\(\mathcal {S}\)：可能的状态集合。
—\(\mathcal {A}\)：代理可用的动作集合。
—\(\mathcal {P}(s^{\prime } | s, a)\)：在采取动作a后从状态s转移到状态\(s^{\prime }\)的概率。
—\(\mathcal {R}(s, a, s^{\prime })\)：从状态s使用动作a转移到状态\(s^{\prime }\)后立即获得的奖励。
—\(\gamma \in [0, 1]\)：未来奖励的折扣因子。
代理的目标是学习一个策略\(\pi\)，以最大化预期的累积奖励。
策略（\(\pi\)）。策略将状态映射到动作。它可以是确定性的或随机性的，为动作分配概率。目标是找到一个策略，以最大化预期回报。
价值函数。价值函数\(V^{\pi }(s)\)估计在策略\(\pi\)下从状态s开始的预期回报：
$$
V^{\pi }(s) = \mathbb {E}_{\pi } \left[ \sum _{k=0}^{\infty } \gamma ^k r_{t+k} \bigg | s_t = s \right].
$$
类似地，动作价值函数\(Q^{\pi }(s, a)\)估计在状态s采取动作a后的预期回报：
$$
Q^{\pi }(s, a) = \mathbb {E}_{\pi } \left[ \sum _{k=0}^{\infty } \gamma ^k r_{t+k} \bigg | s_t = s, a_t = a \right].
$$
强化学习中的迭代学习。强化学习本质上是迭代的。代理在一系列时间步中与环境互动。在每个时间步t：
(1) 代理观察当前状态\(s_t\)。
(2) 根据其策略\(\pi\)，代理选择一个动作\(a_t\)。
(3) 环境根据转移概率\(\mathcal {P}(s_{t+1} | s_t, a_t)\)转移到新状态\(s_{t+1}\)。
(4) 代理收到奖励\(r_t = \mathcal {R}(s_t, a_t, s_{t+1})\)。
(5) 代理更新其策略\(\pi\)以改进未来的动作。
通过这个迭代过程，代理从其动作的后果中学习，调整策略以随时间最大化累积奖励。这种学习持续进行，直到代理的策略收敛到最优或令人满意的性能水平。
Q学习和深度Q网络（DQN）。Q学习是一种算法，代理通过基于贝尔曼方程迭代更新其估计来学习最优的动作价值函数\(Q^*(s, a)\)：
$$
Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ r_t + \gamma \max _{a^{\prime }} Q(s_{t+1}, a^{\prime }) - Q(s_t, a_t) \right],
$$
其中\(\alpha\)是学习率。
DQN利用神经网络来近似Q函数，以处理大型或连续的状态空间。迭代学习包括：
—通过与环境交互收集经验\((s_t, a_t, r_t, s_{t+1})\)。
—将经验存储在重放缓冲区中。
—从重放缓冲区中采样小批量数据来训练神经网络。
—更新网络参数以最小化预测值和目标Q值之间的差异。
这个过程使代理即使在复杂环境中也能学习有效的策略。
3.3 强化学习框架
在前面介绍的强化学习概念的基础上，我们现在详细说明如何将RL应用于轨迹片段合并问题。我们的目标是训练代理来决定是合并还是保留图中的特定轨迹片段，从而优化第2.3节中提到的目标之间的权衡。
代理通过选择改变图结构的动作与轨迹图互动。它的目标是学习一个策略，以最大化累积奖励，同时保持高轨迹表示能力。
状态。每个状态\(s_t\)捕捉了轨迹图的当前配置。我们将状态表示为一个4元组：
$$
(S_1, S_2, S_3, S_4),
$$
其中：
—\(S_1\)：图中的轨迹片段数量（|\(\mathbb {S}|\)）。
—\(S_2\)：表示轨迹所需的平均轨迹片段数量。
—\(S_3\)：轨迹损失度量\(L_{traj}\)，表示无法准确表示的轨迹比例。
—\(S_4\)：平均轨迹表示能力\(\bar{\mu }\)。
这种状态表示包含了影响我们优化目标的关键因素。
动作。在每个时间t，代理对其当前处理的轨迹片段\(\rho\)有两种离散动作可供选择，由动作空间\(\mathcal {A} = \lbrace {\rm\small KEEP}, {\rm\small MERGE}\rbrace\)表示。换句话说，\({\rm\small KEEP}\)动作表示应保留当前轨迹片段\(\rho\)，不与任何邻居片段合并。因此，算法1将当前轨迹片段\(\rho\)放入处理集，然后选择一个新的轨迹片段进行处理，并对该新轨迹片段执行动作空间中的其中一个动作。然而，\({\rm\small MERGE}\)动作应当将当前轨迹片段\(\rho\)与其\(|\Psi (\rho)|\)个邻居片段中的一个合并。为此，代理需要决定与哪个邻居片段合并。因此，动作空间可以简洁地表示为：
$$
\mathcal {A} = \bigcup _{\forall \hat{\rho } \in \Psi (\rho)} \lbrace {\rm\small MERGE}(\rho , \hat{\rho }) \rbrace \cup \lbrace {\rm\small KEEP}(\rho) \rbrace .
$$
奖励函数。我们根据方程(1)中定义的优化方程来构建奖励函数R：\begin{equation} \max _{a_t} \mathbb {E}\left[ \left(- \alpha _1 |\mathbb {S}| - \alpha _2 \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} |\Phi (\tau)| -\alpha _3 L_{traj} + \alpha _4 \frac{1}{|\mathcal {T}|} \sum _{\tau \in \mathcal {T}} \mu (\tau) \right) \right] . \end{equation} (3)每当强化学习（RL）代理在路径图环境中执行动作\(a_t\)时，环境会以即时奖励的形式\(\lbrace r_t\rbrace _{t=0}^T\)向它提供反馈：\begin{equation*} r_t = -\alpha _1 \Delta |\mathbb {S}| - \alpha _2 \Delta \phi -\alpha _3 \Delta L_{traj} + \alpha _4 \Delta \bar{\mu }, \end{equation*}其中\(\Delta \odot\)表示在之前和当前时间步中\(\odot\)值的变化。最终，代理会收到这些即时奖励的总和，再加上方程(3)中描述的最终奖励。注意，为了使代理能够认识到即时奖励和长期未来奖励的重要性，引入了一个用户定义的折扣率因子\(\gamma \in [0,1]\)。策略和DQN实现。为了应对连续状态空间的挑战，我们使用DQN来近似最优动作价值函数。代理的策略\(\pi\)旨在选择能够最大化预期累积奖励的动作：\begin{equation*} Q^{\pi }(s_t, a_t) = \mathbb {E} \left[ R_t | s_t, a_t \right]. \end{equation*}由于我们的状态和动作空间很大，维护一个Q表是不切实际的，因此DQN使用神经网络来估计Q值。该网络以状态\(s_t\)作为输入，并输出可能的动作\(a_t\)的估计Q值。通过训练这个网络，代理学会了如何决定合并或保留路径片段，以最大化我们的目标所定义的累积奖励。关于选择DQN而非其他深度强化学习策略（如Actor-Critic (A2c)和Policy-gradient方法）的合理性讨论，请参阅附录F。经验回放和训练。在训练过程中，代理与环境交互并收集形式为转换\((s_t, a_t, r_t, s_{t+1})\)的经验。为了提高学习的稳定性和效率，我们利用了一个经验回放缓冲区[17]来存储这些转换。代理从这个缓冲区中采样小批量数据来训练神经网络，这有助于打破序列数据之间的时间相关性。在数据收集过程中采用了\(\epsilon\)-贪婪策略来平衡探索和利用：代理以概率\(\epsilon\)选择一个随机动作，否则选择估计Q值最高的动作。网络被训练来最小化预测的Q值和从采样经验计算出的目标Q值之间的Huber损失。这个损失函数与我们评估当前路径片段集合无法表示的轨迹数量的轨迹损失指标不同。3.4 空间复杂性分析使用边不相交的路径片段与自下而上方法相结合的主要动机之一是由于减少了内存存储需求，即初始化路径片段所需的内存，这与之前使用重叠、冗余路径片段的自上而下方案相比。实际上，我们提供了自上而下方法的空间复杂性分析，并通过以下定理将其与所提出的自下而上方法进行了比较（证明见附录C）。定理3.2（初始内存存储需求定理）。自上而下方法初始化一个PD（路径段列表）所需的内存空间，该PD枚举所有长度最多为k的连续子路径，其大小为\(\Theta \!\big (n\min \lbrace k,n\rbrace \big)\)，其中\(n=|\mathcal {E}|\)是道路段的数量。特别是如果\(k\ge n\)，则界限变为\(\Theta (n^2)\)。自下而上的方案，如所提出的PathletRL，仅需要\(\Theta (n)\)的初始内存空间，使用n个单位长度的路径片段。4 评估在本节中，我们详细介绍了用于评估我们提出方法的实验设置。我们的目标是基于以下研究问题来分析和评估我们的模型：(Q1)PathletRL与SotA方法相比，在提取的PD的质量方面如何？(Q2)自下而上的方法与自上而上的方法相比节省了多少内存？(Q3)我们的PathletRL模型与其消融变体相比，改进了多少以及效果如何？(Q4)在我们的PathletRL模型中获得的字典中路径片段的长度分布是怎样的？(Q5)构建的PD在重建原始轨迹方面的有效性如何？(Q6)用户定义的参数[\(\alpha _1\), \(\alpha _2\), \(\alpha _3\), \(\alpha _4\)]对PathletRL模型性能的影响程度如何？(Q7)超参数（如路径片段的最大长度和平均轨迹可表示性阈值）如何影响PathletRL的性能和效率？4.1 数据集我们使用了两个数据集，每个数据集描绘了一个不同的地图场景（详见附录E中的完整统计信息，以及附录G中关于数据隐私问题的简要讨论）。我们使用了OpenStreetMaps中的两个大城市的真实世界地图：多伦多4和罗马。此外，还使用Sumo mobility应用程序模拟器生成了多伦多地图的现实合成车辆移动数据集（6.7小时）。此外，从Crawdad [9]（一个无线网络和移动计算数据集的档案网站）中提取了2014年2月第一周的大规模真实世界出租车轨迹数据，用于构建罗马数据集。我们将轨迹集分为70%的训练数据和30%的测试数据，其中训练数据用于构建我们的路径片段字典，其余数据用于评估。4.2 实验参数有关实现的完整细节，请参阅附录H。为了实现RL架构，我们采用了一个具有三个隐藏全连接层的神经网络架构，分别是128个、64个和32个神经元。这种配置在表达能力和计算效率之间取得了平衡，适用于路径片段合并任务。我们使用了ReLU激活函数，并通过Adam优化器进行训练，学习率为0.001。网络中还应用了0.2的dropout率以及Huber损失函数。具体到DQN的参数，每个\(n=100\)迭代中有\(m=5\)个剧集。经验回放缓冲区的大小为100,000，内存小批量的大小为64。我们的代理使用折扣因子\(\gamma = 0.99\)，这在该环境中保持了长期优化的准确性，没有观察到发散；高折扣因子在这里是合适的，因为路径片段合并决策在整个剧集中对字典质量有持续的影响。此外，我们使用\(k=10\)作为k阶候选集，M = 25%的最大轨迹损失和\(\hat{\mu }\) = 80%的平均可表示性阈值。我们最初将\(\alpha _i\)设置为\(\?\)，\(\forall i\)，这表示方程(3)中描述的四个目标的重要性相同。然而，如第5节所讨论的，这种均匀加权在线性标量化中可能对权重分配敏感，因此引入了更高级的标量化方法（Chebyshev和动态方法）。4.3 基线我们介绍了以下基线（有关基线选择的讨论请参见第6节）。前两个是基于自上而下的SotA基线，而最后三个是我们提出模型的消融版本。表4展示了每个消融变体中省略的特征，以证明这些特征的重要性和有效性。表4. PathletRL算法可表示性度量加权网络深度学习策略PathletRL-Nr???PathletRL-Rnd???PathletRL-Unw???PathletRL（我们的）???所提出的PathletRL模型的特征及其消融基线陈等人[10]的第一篇引入路径片段概念的论文。该方法将问题表述为一个整数规划问题，即可以使用动态规划解决。阿加瓦尔等人[2]将PD提取视为子轨迹聚类问题，其中子轨迹簇被视作路径片段，他们使用了受流行的集合覆盖算法启发的路径片段覆盖方法。Sgt这种基线考虑了所有初始长度为1的路径片段（原始道路地图），不合并任何路径片段。PathletRL-Rnd这个版本的PathletRL不支持DQN，也不使用Dqn代理。每个剧集时间步的动作都是均匀随机选择的。PathletRL-Nr在这种消融下，轨迹的可表示性被移除了。如果某个轨迹\(\tau\)经过的路径片段与另一个路径片段合并，即\(\tau\)没有经过的路径片段，则路径片段集中不再存在可以表示\(\tau\)的子集；因此，我们立即丢弃轨迹\(\tau\)。PathletRL-Unw这个版本的PathletRL应用于所有路径片段权重相同的路径图环境。4.4 评估指标为了评估模型性能，我们考虑了以下指标，这些指标将衡量提取的路径片段字典的质量。注意\([\downarrow ]\) (\([\uparrow ]\))表示较低（较高）的值更好。(1)\(|\mathbb {S}|\)，PD的大小 [\downarrow ](2)\(\phi\)，表示每个轨迹的平均路径片段数量 [\downarrow ](3)\(L_{traj}\)，丢弃的轨迹数量（以百分比表示) [\downarrow ](4)\(\bar{\mu }\)，剩余轨迹的平均可表示性（以百分比表示) [\uparrow ]注意，上述第三和第四个指标不适用于陈等人[10]和阿加瓦尔等人[2]的方法，因为这些度量仅适用于路径片段合并方法。此外，第四个指标也不适用于PathletRL-Nr。在这个模型下，数据集中的所有剩余轨迹（因此平均值）总是100%可表示的，这并不有趣。4.5 结果和讨论在本节中，我们将讨论每个研究问题，展示实验结果并提供一些讨论。(Q1)提取的PD的质量。我们将我们的PathletRL算法提取的PD与SotA基线提取的PD进行比较。见表5中的数值结果，其中粗体数字表示给定PD指标表现最好的模型的结果，下划线数字是第二优秀模型的结果（注意我们没有将Sgt的数字加粗或下划线，因为该模型作为空模型，没有对路径图进行任何操作）。尽管路径片段的定义和方法不一定相同，但陈等人[10]和阿加瓦尔等人[2]的算法仍然是可比的。我们最终展示了他们的自上而下方法不如我们的自下而上策略有效。首先，我们看PD的大小，\(|\mathbb {S}|\)，数字越小，结果越好。我们的PathletRL模型在多伦多（罗马）数据集上比Sgt提高了\(\sim\)32.0%（\(\sim\)65.8%）。与陈等人[10]的模型相比，在多伦多（罗马）数据集上提高了\(\sim\)87.4%（\(\sim\)91.1%；与阿加瓦尔等人[2]的方法相比，在多伦多（罗马）数据集上提高了\(\sim\)78.2%（\(\sim\)82.9%）。这两个观察结果表明我们的方法优于最先进的方法；也就是说，自下而上的方法比自上而下的方案更好。同时也要注意，陈等人[10]和阿加瓦尔等人[2]的PD比初始的长度为1的路径片段数量更多，因为他们的方法是自上而下的——最初考虑了所有可能的路径片段大小和配置（包括重叠）。显然，与我们所提出的PathletRL模型以及PathletRL的所有消融版本相比，它们的结果并不理想。表5.基线NullPathletRL[10][2]SgtRndNrUnw（我们的）多伦多\([\downarrow ] |\mathbb {S}|\)13,8867,9822,5632,4541,8961,8011,743?\([\downarrow ] \phi\)7.025.974.763.772.893.983.75?\([\downarrow ] L_{traj}\)n/an/a0%19.7%17.6%15.1%15.2%?\([\uparrow ] \bar{\mu }\)n/an/a100%79.9%n/a80.0%80.0%罗马\([\downarrow ] |\mathbb {S}|\)59,39631,01715,4659,7187,0035,8045,291?\([\downarrow ] \phi\)202.91188.33230.15173.04158.18146.39139.89?\([\downarrow ] L_{traj}\)n/an/a0%24.9%21.1%22.9%20.4%?\([\uparrow ] \bar{\mu }\)n/an/a100%82.7%n/a86.2%85.6%表5显示了每种方法为每个数据集提取的路径片段字典的属性在表5中，Sgt（Singleton）列没有加粗或下划线，因为它作为空基线。粗体值表示每个指标表现最好的模型；下划线值表示第二好的模型。然后，我们关注表示每个轨迹的平均路径片段数量的指标（在迭代算法的每一步中这个数字可能会增加或减少）。与\(|\mathbb {S}|\)类似，较小的\(\phi\)表示更理想的字典。我们的PathletRL模型在多伦多（罗马）数据集上提取的字典比Sgt提高了\(\sim\)21.2%（\(\sim\)39.2%；而在罗马数据集上，陈等人的[10] PD的\(\phi\)质量比Sgt高\(\sim\)47.4%，仅比Sgt低\(\sim\)11.8%。在阿加瓦尔等人的[2]字典中也可以看到类似的趋势，分别在多伦多和罗马数据集上比初始数量高出\(\sim\)25.4%和低\(\sim\)18.2%。显然，我们提出的PathletRL（及其消融变体）优于这些SotA基线。我们的PathletRL还基于\(|\mathbb {S}|\)和\(\phi\)指标改进了Sgt的表现。因为在Sgt中对路径图没有采取任何行动，所以只显示了原始数字；因此，\(L_{traj}\)和\(\bar{\mu }\)对于两个数据集都保持为0%和100%。然而，我们可以通过调整这些值来看到PathletRL的好处，从而获得更小的字典以及更低的\(\phi\)分数——这由\(\alpha\)参数控制。(Q2) 内存效率。图2（以对数刻度显示）展示了PathletRL与基线[2, 10]相比在内存效率上的优势。如图2所示，我们的方法需要大约900MB（约30GB）的内存来存储一组轨迹，并且为了多伦多（罗马）数据集构建的轨迹PD只需要大约100KB（约1MB）的内存。实际上，这代表了大约7.4K×24K的节省。这种显著的改进归因于我们的方法采用了自下而上的方法，只考虑了边不相交的路径片。相比之下，当前的基线采用了自上而下的方法，其中轨迹PD由各种大小和配置的路径片组成，其中大部分都是多余的。(Q3) 消融研究。接下来，我们进行了消融实验来观察我们提出的PathletRL模型的表现。图7显示了PathletRL及其消融版本在两个数据集上经过n次迭代后的平均回报。我们可以在两个数据集上观察到类似的趋势。注意PathletRL-Rnd的表现最差，表现出完全没有学习的随机RL策略。同时，所有其他模型都显示出它们的平均回报值在经过一些迭代后（例如，PathletRL在多伦多和罗马数据集上分别为15次和20次迭代）趋于稳定，然后在一个小范围内略有波动。PathletRL-Nr虽然由于采用了Dqn策略而表现出一定程度的学习，但其表现不如PathletRL-Unw——这表明可表示性是一个关键组成部分。这种未经加权的PathletRL版本可以被视为我们提出的（加权）模型的亚军，这表明为路径片分配权重比简单地平等对待所有路径片有其价值。图7. 使用平均回报指标（\(m = 5\)个剧集，共\(n = 100\)次迭代（运行10次）来评估提出的和消融的PathletRL模型的性能。除了比较PathletRL模型性能评估的趋势外，我们还可以查看它们的PD质量（见表5的结果）。一般来说，我们提出的PathletRL的PD优于其消融变体提取的PD（即多伦多和罗马数据集的\(|\mathbb {S}|\)指标，多伦多数据集的\(\bar{\mu }\)指标，以及罗马数据集的\(\phi\)和\(L_{traj}\)指标）。在其他PathletRL没有排第一的情况下，它也是亚军，但这可以解释。例如，考虑多伦多数据集的\(\phi\)指标。PathletRL-Nr的PD质量之所以更高，是因为在PathletRL-Nr中，代表每个轨迹的路径片数量更容易减少；平均\(\phi\)值可以很容易地下降。PathletRL-Unw的PD的\(\bar{\mu }\)指标高于PathletRL在罗马数据集上的PD，可能是因为PathletRL-Unw的轨迹集中剩余的轨迹较少，而那些剩余的轨迹具有较高的可表示性\(\mu\)值。无论如何，PathletRL和PathletRL-Unw的PD在\(\bar{\mu }\)指标上的差异很小，仍然具有可比性。对于多伦多数据集上的PathletRL-Unw和PathletRL的PD的\(L_{traj}\)指标也是如此， hanya相差约0.1%，表明PathletRL仍然具有竞争力。(Q4) 路径片长度分布。我们还分析了字典中路径片的长度分布。两个数据集的趋势相似（图8显示了路径片长度分布，y轴采用对数刻度）。PathletRL-Rnd中较长路径片的数量在减少，这是合理的，因为随机策略盲目地保留和合并路径片。以这种随机概率方式维持较长路径片更加困难，因为终止增长的路径片已经被认为是“处理过的”，无法进一步增长。因此，在PathletRL-Rnd的PD中看到较高顺序的路径片比短路径片更为罕见。其他使用Dqn策略的RL模型则预期会有更长长度的路径片（字典中包含更多的长度为9和10的路径片）。我们提出的PD能够捕捉到更多这样的较高顺序的路径片——这反映在表5的结果中。同时，我们仍然观察到大量长度为1的路径片，可能是由于多种原因造成的。一种可能是某些长度为1的路径片尚未被处理（由于算法中的各种终止标准导致提前停止）。也可能是由于算法基于效用推荐，或者某些长度为1的路径片没有与其他邻居路径片合并。后一种情况表明，一个长度为1的已处理路径片\(\rho\)可能由于这些邻居路径片之间的合并而失去了所有邻居，导致\(\rho\)无法与这些形成的合并路径片中的任何路径片合并。(Q5) 部分轨迹重建。请参见图9，该图显示了此实验的结果，我们确定字典中的多少内容足以重建测试集中大部分轨迹。这里，如果一个轨迹的可表示性值\(\mu \ge 0.75\)（即，轨迹的75%可以通过PD表示），则认为该轨迹是可重建的。任何低于这个值的轨迹都因为存在过多的间隙而无法重建。理想情况下，我们希望取PD中训练集中轨迹最多遍历的top x%的路径片。然而，我们可以通过在提取的PD中选择随机样本的\(x \in [10\%,20\%,...,100\%]\)路径片，并测量测试集中有多少轨迹可以由这个路径片样本集重建来进一步消除实验中的偏差。结果显示，使用PathletRL PD中大约一半的路径片，可以重建多伦多（罗马）测试集中约80%（约85%）的轨迹；而使用整个字典，则几乎可以重建集合中的所有轨迹。这表明我们提出的模型能够提取高质量的PD。与我们的消融版本相比，它们在两个数据集上的趋势相似——即，消融模型的字典能够重建的轨迹数量少于我们提出的PathletRL的字典。表现最差的是PathletRL-Rnd的字典，它最多只能重建多伦多（罗马）数据集中约50%（约65%）的轨迹。图8. PathletRL模型及其消融版本在多伦多（上）和罗马（下）数据集上获得的路径片字典的长度分布。图9. 从提取的路径片字典中选取的样本集可重建的评估轨迹百分比。(Q6) 参数敏感性分析。然后我们讨论了四个\(\alpha\)值（\(\alpha _1\), \(\alpha _2\), \(\alpha _3\), \(\alpha _4\)）如何影响输出PD的质量，分别体现在其四个属性上：\(|\mathbb {S}|\), \(\phi\), \(L_{traj}\), \(\bar{\mu }\)。如图10所示，有四个堆叠的图表。第一个图表展示了当我们改变\(\alpha _1 = [0.0, 0.1, \ldots , 1.0]\)（同时保持其他\(\alpha\)项不变，\(\alpha _2 = \alpha _3 = \alpha _4 = \frac{1-\alpha _1}{3}\)）时PD的\(|\mathbb {S}|\)的变化。正如预期的那样，我们注意到一个下降趋势；较大的\(\alpha _1\)值表示对较小字典大小更为重视。通过改变\(\alpha _2\)并保持其他项不变，我们也观察到一个下降趋势；较高的\(\alpha _2\)值意味着更强调较低的\(\phi\)分数——也就是说，表示轨迹的路径片平均数量较少。然后当改变\(\alpha _3\)的值时，同时保持其他\(\alpha\)项不变，也显示出一个下降趋势，因为随着\(\alpha _3\)的增加。\(\alpha _3\)越大，我们越重视保持轨迹损失较低。最后，改变\(\alpha _4\)同时保持其他\(\alpha\)项不变，显示出与其它\(\alpha\)项相反的趋势。在这里，我们可以观察到较大的\(\alpha _4\)值表明更重视具有较高的可表示性值。(Q7) 超参数对模型性能的影响。我们分析了超参数\(\mu _{\text{threshold}}\)和k对属性\(|\mathbb {S}|\), \(\phi\), \(L_{\text{traj}}\), 和 \(\bar{\mu }\)的影响。当我们改变\(\mu _{\text{threshold}}\)同时固定\(k = 10\)时，我们观察到了几个趋势。集合的大小（(\(|\mathbb {S}|\)）起初是稳定的，但随着\(\mu _{\text{threshold}}\)的增加而显著增长，这表明，正如预期的那样，较高的\(\mu _{\text{threshold}}\)值会导致更多的路径片计数。这是因为随着代理更快地达到阈值，剧集变得较短。每个轨迹的平均路径片数量（(\(\phi\)）在较低的阈值下保持相对恒定，但在\(\mu _{\text{threshold}}\)较高时增加，表明需要更多的路径片来表示每个轨迹，因为达到阈值时合并发生得更少。轨迹损失（\(L_{\text{traj}}\)）和平均可表示性（\(\bar{\mu }\)之间的关系随着\(\mu _{\text{threshold}}\)的增加而呈现相反的趋势。这是因为当\(\mu _{\text{threshold}}\)设置在一个特定值以下（本例中为70%）时，轨迹损失阈值（设置为25%）成为终止的决定因素，因为它在较低的\(\mu _{\text{threshold}}\)之前就被达到。然而，当\(\mu _{\text{threshold}}\)超过70%时，\(\bar{\mu }\)与\(\mu _{\text{threshold}}\)相匹配，因为它现在成为主要的终止标准。结果，轨迹损失不再决定终止，并开始减少，因为合并的路径片较少，导致丢失的轨迹数量减少。图10. 参数敏感性实验：\(\alpha\)对PathletRL PD质量的影响。当固定\(\mu _{\text{threshold}} = 0.8\)并改变k时，出现了一组不同的趋势。随着k的增加，集合的大小（(\(|\mathbb {S}|\)）减小，这表明使用较长的路径片会导致更紧凑的PD，正如预期的那样。每个轨迹的平均路径片数量（(\(\phi\)）随着k的增加而略有增加，表明随着k的升高，轨迹被划分成更多的部分。轨迹损失（\(L_{\text{traj}}）如预期地增加，反映了由于更多路径片被合并而导致重建质量略有下降。此外，\(\mu _{\text{threshold}}\)保持为80%，与之前提到的初始参数设置一致。我们分析了在不同\(\mu _{\text{threshold}}\)值和固定\(\mu _{\text{threshold}}\)下生成的路径片长度分布。显然，增加最大路径片长度（k）鼓励代理合并更多的路径片，从而减少了初始长度为1的路径片数量。此外，图表显示，尽管每个设置中都存在不同长度的路径片，但代理主要生成接近最大长度k的路径片，而不是在1到k的长度范围内均匀分布。当检查不同的\(\mu _{\text{threshold}}\)值的影响时，我们看到较低的\(\mu _{\text{threshold}}\)值允许更多的合并，从而导致更高比例的路径片合并，这也是预期的。5 PathletRL优化基于参数敏感性分析，该分析展示了四个\(\alpha\)参数的变化如何影响PD在不同目标方面的表现，我们现在将重点放在解决原始PathletRL模型中观察到的局限性上。具体来说，分析强调了模型对奖励函数线性标量化中权重分配的敏感性，这会显著影响提取的PD的质量。为了减轻这种敏感性并进一步提高模型的性能，我们提出了PathletRL框架的三个变体。这些变体形成了方法论细化的清晰进展，如下所示：前两种变体引入了不同的标量化技术，以更好地平衡竞争目标：(1) 带有切比雪夫标量化技术的PathletRL（PathletRLCheb）和(2) 带有自定义动态标量化函数的PathletRL（PathletRLDS）。第三种变体PathletRL++通过结合更丰富的状态表示来扩展PathletRLDS。这种增强为强化学习代理提供了更详细和有信息量的环境视图，使得决策更加细致，最终提高了减少候选路径集大小的性能。总之，PathletRLCheb和PathletRLDS改进了标量化策略以改善多目标平衡，而PathletRL++则通过增加局部路径级别的信息来扩展PathletRLDS。

5.1 多目标优化中的标量化敏感性
原始的PathletRL模型采用线性标量化方法进行奖励计算，对所有目标给予相同的权重（方程式3）。这种线性标量化在多目标优化（MOO）中存在已知的敏感性问题，因为权重分配的微小变化可能导致优化的结果大相径庭[52]。具体来说，线性标量化仅在帕累托前沿（目标之间的最优权衡集合）是凸的时候才能保证最优解。如果帕累托前沿是非凸的，该方法就无法识别出非凸的帕累托最优解。这一限制意味着一些潜在理想的目标权衡可能会被完全忽略[22]。为了解决这些问题，我们提出了两种替代的标量化方法来提高解的稳定性和通用性。

5.1.1 切比雪夫标量化
第一种替代方法是切比雪夫标量化，它试图最小化目标空间中与理想点的最大偏差。这种方法的形式表达为：
\[ R_{\text{Chebyshev}} = -\max \left(\alpha _1 \left| f_1(\mathbf {x}) - z_1^* \right|, \alpha _2 \left| f_2(\mathbf {x}) - z_2^* \right|, \alpha _3 \left| f_3(\mathbf {x}) - z_3^* \right|, \alpha _4 \left| f_4(\mathbf {x}) - z_4^* \right| \right) \]
其中 \(\mathbf {x}\) 表示决策变量，\(f_1(\mathbf {x}), f_2(\mathbf {x}), f_3(\mathbf {x}), f_4(\mathbf {x})\) 是四个目标函数的值，\(z_1^*, z_2^*, z_3^*, z_4^*\) 是各自目标的理想值。权重 \(\alpha _1, \alpha _2, \alpha _3, \alpha _4\) 是用户定义的缩放因子，通常设置为 \(\sum _{i=1}^{4} \alpha _i = 1\)。
切比雪夫标量化不依赖于权重分配，并且可以在帕累托前沿的凸区域和非凸区域找到帕累托最优解[52]。它确保了所有目标的平衡优化，并导致稳健的解。

5.1.2 动态标量化
第二种替代方法引入了动态标量化函数，该函数根据代理与预定义的轨迹可表示性阈值 \(\mu _{\text{traj}}\) 和轨迹损失 \(L_{\text{traj}}\) 的接近程度来调整权重。这种方法通过使用惩罚来动态调整不同目标的权重来实现。这些惩罚是根据代理与关键阈值的接近程度计算的。

理论基础
我们的动态标量化方法借鉴了Abels等人[1]的框架，他们证明了在多目标强化学习中自适应权重调整使代理能够在训练过程中发现多样化的帕累托最优策略。我们将这一原理扩展到基于阈值的适应：我们不是均匀地循环通过权重配置，而是根据明确的性能边界 \((\mu _{\text{threshold}}, M)\) 来调整权重，这些边界编码了领域约束。这确保了代理在探索权衡前沿时遵守关键的操作限制（例如，最小轨迹可表示性和最大轨迹损失）。形式上，权重函数 \(w_{\text{traj}}(t)\) 和 \(w_{\mu }(t)\) 实现了一种软障碍机制，当代理接近约束边界时放大惩罚，从而引导策略朝向解空间中可行且效用高的区域。与之前依赖于复杂重放多样性机制的动态标量化方案不同，我们的基于阈值的公式通过将权重调整锚定到特定于任务的安全边际来产生经验上的稳定收敛。
动态权重分配的实现方式如下：
\[ w_{\text{traj}}(t) = \frac{1}{\text{max}(0.01, \frac{M - L_{\text{traj}}(t)}{M})} \]
\[ w_{\mu }(t) = \frac{1}{\text{max}(0.01, \frac{\mu _{\text{traj}}(t) - \tau _{\mu }}{0.2}) \]
其中 \(w_{\text{traj}}(t)\) 和 \(w_{\mu }(t)\) 分别是轨迹损失和轨迹可表示性的动态权重。当代理接近阈值 \(\tau _{\mu }\)（对于 \(w_{\text{traj}}\)）和 M（对于 \(L_{\text{traj}}\)）时，每个目标的权重会增加，从而鼓励代理在性能关键时优先考虑这些目标。

奖励是使用这些动态权重计算的：
\[ R = -\alpha _1 \Delta |S| -\alpha _2 \Delta \phi -\alpha _3 \Delta L_{\text{traj}} w_{\text{traj}}(t) + \alpha _4 \Delta \bar{\mu } w_{\mu }(t) \]
最初，所有目标都被赋予相同的权重，但随着代理接近关键阈值（例如，轨迹可表示性阈值 \(\tau _{\mu _{\text{traj}}\)），动态权重 \(w_{\text{traj}}(t)\) 和 \(w_{\mu }(t)\) 会增加，迫使代理更加优先考虑这些目标。
在一个剧集结束时，会根据代理的整体表现以及相同的目标准和阈值应用额外的奖励或惩罚。这种动态调整确保了代理在接近关键阈值时变得更加保守，避免过度合并路径片，从而不会降低整体性能。

5.2 增强的状态表示以实现更好的决策
虽然前两种变体改进了标量化机制，但它们仍然依赖于PathletRL使用的原始状态表示，该表示仅限于全局指标，如路径片数量、平均轨迹可表示性和轨迹损失。时间t的状态表示为：
\[ \mathbf {s}_t = \left(S_1, S_2, S_3, S_4 \right) \]
其中 \(S_1\) 表示当前路径片图中的路径片数量，\(S_2\) 表示表示轨迹所需的平均路径片数量，\(S_3\) 是轨迹损失，\(S_4\) 是平均轨迹可表示性。这种受限的全局视图使强化学习代理无法了解关于单个路径片及其邻居的关键局部信息，这可能导致次优的决策，特别是在确定合并或分割哪些路径片段时。
为了解决这个缺点，我们提出了第三种变体：PathletRL++。该模型通过引入更详细的状态表示来扩展动态标量化方法，为代理提供了当前路径片及其邻居的权重。这种丰富的表示使代理能够更好地了解其环境，从而在路径片合并过程中做出更明智和精确的决策。

5.2.1 改进状态表示的局部指标
时间t的增强状态表示表示为 \(\mathbf {s}_t^{\text{enhanced}}，扩展了全局指标和局部路径片权重。具体来说，状态现在表示为：
\[ \mathbf {s}_t^{\text{enhanced}} = \left(S_1, S_2, S_3, S_4, w_t, w_t^{\text{neighbors}} \right) \]
其中：
— \(w_t\) 表示时间t选定的路径片的权重（\(p_{\text{current}}）。
— \(w_t^{\text{neighbors}}\) 表示选定路径片的邻居的权重：
\[ w_t^{\text{neighbors}} = (w_p) \ \forall p \in \mathcal {N}(p_{\text{current}}) \]
其中 \(\mathcal {N}(p_{\text{current}})\) 表示 \(p_{\text{current}}\) 的邻居路径片集合。

处理变量大小的邻居
由于不同路径片的邻居数量可能不同，\(w_t^{\text{neighbors}}\) 在不同状态下的维度是可变的。为了实现批量训练的一致性，我们采用了填充和掩码技术。具体来说，邻居权重向量被填充到固定的最大长度（由路径片图中的最大度数决定），并且二进制掩码指示有效条目和填充条目。

5.3 对比分析
为了保持评估的一致性，所有模型都使用相同的Toronto地图和轨迹数据集进行了测试。此外，我们还使用了修改版的Rome数据集来用更多的轨迹集挑战模型。通常，出租车每15秒发送一次GPS信号。在我们的修改中，轨迹数据使用60秒的较短时间间隔进行匹配；如果出租车超过一分钟没有发送信号，其路径就被视为新轨迹，从而导致平均轨迹长度较短，但轨迹数量显著增加（从大约2.9K增加到大约75,180条）。这一修改大大增加了数据集的结构多样性，为测试模型的鲁棒性和可扩展性提供了更具挑战性的场景。

5.3.1 训练性能分析
为了更好地理解所提出变体的训练动态，我们分析了PD大小随训练剧集数量的演变。图13(a)和13(b)分别展示了每个模型变体在Toronto和Rome数据集上的路径片大小随训练剧集的减少情况。首先关注Toronto数据集，所有模型都显示出路径片大小下降的趋势，表明它们有效地学习了在达到预定义阈值之前最小化字典大小。值得注意的是，PathletRL++比其他模型更快地收敛到更小的PD大小。这种快速收敛凸显了该模型的增强训练效率，这可以归因于其对环境的详细观察和强大的奖励系统。

图11. 在不同 \(\mu _{\text{threshold}}\) 和 k 超参数下的状态变量比较。
图12. 使用核密度估计，在两种不同 \(\mu _{\text{threshold}}\) 设置（80% 和 60%）下不同 \(k\) 值的路径片长度分布比较。
图13. 不同PathletRL变体在Toronto和Rome数据集上的训练性能。

相比之下，在分析Rome数据集时，使用标准状态空间的原始PathletRL变体由于轨迹数量众多而在学习有意义的动作时遇到困难。尽管如此，PathletRL++再次展示了快速的学习速度，并实现了路径片大小的显著减少。
总体而言，很明显，在PathletRL++中整合局部路径片指标不仅提高了最终性能，还加速了训练过程。这导致在更少的训练剧集中达到了更优的解决方案。

5.3.2 离线性能比较
表6总结了原始PathletRL模型及其变体在Toronto和Rome数据集上的四个关键指标上的性能。对于Toronto数据集，PathletRL++实现了最小的PD大小 \(|\mathbb {S}|\)，仅包含1,646个路径片，明显低于原始PathletRL模型使用的1,762个路径片。考虑到表示每个轨迹的平均路径片数量 (\(\phi\))，各模型的结果相对相似，PathletRLDS略占优势。在轨迹损失 (\(L_{traj}\)) 方面，原始PathletRL模型的表现最好，损失率为15.8%。这一结果是预期的，因为其较大的PD大小导致较少的轨迹合并，从而减少了损失。所有模型保持相同的平均可表示性 (\(\bar{\mu }\))，即80.0%，这等于我们为训练设置的 \(\mu\) 阈值。

表6. PathletRL变体在Toronto和Rome数据集上的性能比较
- **Toronto数据集**
| PathletRL | PathletRLCheb | PathletRLDS | PathletRL++ |
|--------|-----------|-----------|---------|
| |\mathbb {S}|\ | 1,762 | 1,736 | 1,646 |
| φ | 3.78 | 3.77 | 3.86 |
| L_{traj}| 15.8% | 16.6% | 16.4% |
| \bar{\mu }\ | 80.0% | 80.0% | 80.0% |

- **Rome数据集**
| |\mathbb {S}|\ | 9,811 | 9,871 | 9,068 |
| φ | 19.76 | 19.68 | 19.69 |
| L_{traj}| 1.8% | 1.8% | 1.8% |
| \bar{\mu }\ | 80.0% | 80.0% | 80.0% |

在更复杂的Rome数据集上，PathletRL++再次表现出优越的性能，实现了9,068的较小PD大小，而其他模型的PD大小超过9,800。这表明了其在处理较大数据集时的可扩展性和效率。与Toronto的结果类似，每个轨迹的平均路径片数量 (\(\phi\)) 在各模型间保持相当，PathletRLCheb获得了最低值。轨迹损失 (\(L_{traj}\)) 在所有模型间几乎相同，范围从1.8%到1.9%，反映了Rome数据集中的大量轨迹。再次，所有模型保持相同的平均可表示性 (\(\bar{\mu }\))，即80.0%，与训练阈值保持一致。
尽管PathletRL++在两个数据集上的轨迹损失略有增加，但其显著减少PD大小的能力弥补了这一点。这种路径片大小的减少可以提高可扩展性和计算效率，使PathletRL++成为处理较大数据集或场景的更优选择。

6 相关工作
我们的研究与（i）轨迹数据挖掘、（ii）路径片挖掘、（iii）子轨迹聚类和（iv）时空数据的深度学习有关。下面我们介绍了与我们的工作最相关的一些重要成果。请注意，为了保持讨论的焦点，一些相关工作已在手稿中提及，因此在本节中大部分被省略。

6.1 轨迹数据挖掘
轨迹数据挖掘长期以来一直是一个活跃的研究方向[8, 19, 67]。这种高兴趣很大程度上可以归因于地理空间技术的快速发展和突出[13]、基于位置的智能设备[44]、基于GPS的应用程序的丰富[40]以及大量轨迹数据集的生成[15]。研究的重点包括流行的技术问题，如轨迹相似性[14]和轨迹聚类[20]。近年来，使用图来建模轨迹数据以解决复杂的轨迹挖掘任务也成为一个流行的方法。示例任务包括但不限于相似性搜索[14]、数据恢复[12]、节点中心性计算[43]、挖掘时空交互[46, 47]、学习地理区域的语义关系[32]、轨迹与用户关联[5, 50]、机器对移动数据的去学习[16]以及推荐系统[53, 58]。最近，该领域还开始提出更广泛的移动性智能愿景，这些愿景超越了静态预测建模，朝着结构化、体验式和基于物理的学框架发展[41]。

6.2 路径片段挖掘（Pathlet Mining）
路径片段挖掘专注于通过将复杂轨迹分解为一组基本构建块（称为路径片段）来发现模式和提取知识。这些路径片段作为基本单元，可以高效地表示各种轨迹，有助于轨迹压缩、分类和路线规划等任务。在这一领域的开创性工作中，Chen等人[10]引入了路径片段（PD）的概念来压缩和规划轨迹。他们的目标是通过学习一组常见的路径片段来捕捉一系列人类轨迹中的共享空间和时间规律，这些片段可以连接起来重构原始轨迹。他们将该问题表述为一个整数线性规划（ILP）任务，旨在最小化PD的大小以及表示每个轨迹所需的路径片段数量。为了解决在大型数据集上解决ILP的计算挑战，Chen等人[10]提出了一种高效的分解方法，该方法优化了原始目标函数的下限。这种方法随着轨迹数量的增加而线性扩展，使其适用于大规模应用。他们的方法能够提取出反映数据中常见运动模式的有意义的路径片段。所学到的PD可以用于各种应用，如路线规划和轨迹分析，从而实现轨迹的有效重构和表示。

Zhou等人[68]提出了基于“词袋”模型的方法来表示运动轨迹。该方法将每个轨迹表示为分配给预定义字典中代码的字段集合。这种方法将轨迹转换为代码空间中的向量，使得可以使用传统的机器学习算法进行轨迹分类和相似性搜索。虽然Chen等人[10]和Zhou等人[68]都关注使用基本构建块来表示轨迹，但他们的方法有所不同。Chen等人[10]强调通过优化框架来压缩轨迹和提取共享模式，以最小化PD的大小和重构成本；而Zhou等人[68]则侧重于使用聚类技术将轨迹转换为向量空间表示，从而便于轨迹分析任务。

该领域的其他重要贡献还包括Panagiotakis等人[39]的工作，他们开发了一种使用全局投票、分割和采样技术来识别代表性子轨迹的方法。他们的方法通过关注数据集中的最具代表性片段来增强轨迹摘要和模式发现。此外，Wang等人[56]解决了在预算限制和距离阈值下找到覆盖尽可能多轨迹的k条代表性路线的问题。他们提出了三种近最优解决方案，有效地解决了这个问题，为资源限制下的轨迹分析提供了有价值的策略。然而，这些自上而下的方法通常面临高内存使用和冗余存储的挑战，因为它们生成了大量候选路径片段，并从中选择一部分放入字典中。为了解决这些限制，我们提出了一种自下而上的策略，逐步合并基本路径片段以构建紧凑且高效的PD。我们的方法从单位长度的路径片段开始，并在优化效用（使用新引入的轨迹损失和可表示性指标定义）的同时进行迭代合并。通过利用深度强化学习框架，特别是DQN，该方法近似效用函数，并显著降低了内存需求——与基线方法相比，内存需求减少了多达24,000倍。

6.3 子轨迹聚类（Subtrajectory Clustering）
路径片段挖掘通常被视为准轨迹聚类问题。Lee等人[25]提出了Traculus算法，该算法将轨迹分割成线段，然后将位于相似密集区域的线段分组形成簇。这种方法通过聚类空间上接近的轨迹片段，有效地捕获了经常被穿越的路径。Van Kreveld等人[51]设计了一种新的度量方法来挖掘中位数轨迹，这些轨迹作为（子）轨迹的簇中心。他们的方法通过识别代表一组轨迹中常见运动模式的中位数路径来发现频繁访问的路线。Agarwal等人[2]通过引入路径片段覆盖的概念，提出了一个全面的子轨迹聚类模型。受经典集合覆盖问题的启发，他们的方法旨在找到一小组能够有效表示数据集中轨迹共享部分的路径片段。在他们的模型中，每个轨迹被视为一小组路径片段的串联，允许存在可能的间隙以解释独特片段或噪声。他们用一个单一目标函数来表述子轨迹聚类问题，该函数平衡了三个关键因素：最小化选择的路径片段数量、确保路径片段对子轨迹的高质量表示（通过最小化子轨迹与其分配路径片段之间的距离），以及惩罚轨迹中的间隙。意识到问题的NP难度，Agarwal等人[2]开发了具有可证明解决方案质量和运行时间保证的高效近似算法。他们的方法利用轨迹的几何属性，并采用贪婪选择和几何分组等策略来高效探索可能的路径片段空间，而不需要穷举搜索。在所有这些子轨迹聚类方法中，簇中心被视为许多轨迹经过的流行片段，也可以视为路径片段。这种视角有助于发现共享的运动模式，并支持轨迹摘要、异常检测和高效数据压缩等应用。

基线选择和方法比较。我们实验评估中选择的基线是基于方法论标准选定的。Chen等人[10]和Agarwal等人[2]直接与PD构建问题相关，是最有效的比较对象，用于评估压缩效率和表示能力。这两个基线都不依赖于基于学习的方法，使我们能够展示深度学习的重要性。其他轨迹挖掘框架在目标和形式上有所不同。Wang等人[56]针对明确预算下的路线代表性，使用了一种不适用于我们案例的代表性标准；Zhou等人[68]将轨迹转换为词袋段用于运动分析和分类；Van Kreveld等人[51]将输入限制在共享端点上；Panagiotakis等人[39]也使用了不兼容的代表性标准。它们解决了根本不同的优化问题，并使用不兼容的指标（覆盖度、稀疏性或密度而非重构损失）。需要注意的是，轨迹PD构建的技术问题是一个新兴问题，现有最先进的方法都源自Chen等人[10]的工作。我们采用强化学习方法重新审视了这个问题，并考虑了额外的约束（如路径片段的边不相交性和k阶约束）。

6.4 深度学习在时空数据中的应用
近年来，已经提出了深度学习方法来学习时空数据的表示[55]。例如，Chen等人[11]对深度学习在轨迹数据管理和挖掘中的应用进行了全面回顾。这项工作强调了使用先进AI技术进行各种任务，如轨迹预测、聚类和异常检测。一个关键贡献是提供了一个开源的轨迹相关数据集存储库，使研究人员能够访问用于多种移动性分析任务的精选资源。此外，还开发了一个扩散模型来模拟人类移动模式，允许基于真实世界运动行为更复杂地生成轨迹数据[69]。这些进展表明生成模型在轨迹挖掘中的采用率正在增加。其他工作探索了时空可达性和使用图神经网络（GNNs）从轨迹数据中挖掘复杂关系[66]。最近的工作，如Traj-LLM（Lan等人[24]），探索了在大语言模型（LLMs）中利用其捕捉复杂交通语义和场景理解的能力来提高预测准确性和适应性。Nadiri等人[34, 35]提出了TrajLearn，这是一个基于深度强化学习的轨迹预测框架，它利用基于变换器的架构来建模序列化移动模式。特别值得关注的是基于深度强化学习的方法，这些方法通常在代理玩特定游戏的情况下进行评估[49]。这些方法已经成功地适应并显示出在解决几个复杂轨迹相关问题方面的潜力，如路线规划[18]、轨迹简化[57]和自适应车辆导航问题[6, 7]。

尽管取得了这些成功，当前的神经方法解决的根本问题是与PD构建不同的问题。虽然上述方法侧重于预测、生成建模或相似性搜索[14]等任务，但没有一个是专门设计用于在图约束和复杂多目标权衡下构建或优化路径片段字典的。为了弥合这一差距，我们引入了PathletRL++，这是第一个明确为字典形成而设计的基于RL的系统，它在网络受限环境中平衡了字典大小、轨迹表示能力和重构损失。

7 结论
构建轨迹路径片段字典——能够表示大量轨迹的小型构建块集合——由于在路线规划、旅行时间估计和轨迹压缩中的应用而变得至关重要。本研究介绍了一种深度强化学习解决方案PathletRL，它生成的字典比传统方法小65.8%。值得注意的是，PathletRL的字典中只有一半的路径片段就足以重建85%的原始轨迹数据集，而基线方法则需要整个字典来重建仅65%的轨迹。此外，PathletRL实现了显著的内存节省——与现有方法相比，内存需求减少了约24,000倍——这是由于减少了存储路径片段的初始内存需求。为了进一步改进PathletRL，我们提出了三种新的变体来解决其奖励函数的局限性，并结合了更丰富和更有意义的状态表示。这些改进导致了更紧凑的字典、更快的收敛速度以及在字典大小和训练效率方面的更好整体性能，使PathletRL++成为处理大规模轨迹数据集的最佳选择。我们使用多伦多和罗马的车辆轨迹数据验证了这种有效性，选择了这两个具有对比性的实验环境：多伦大而结构化的拓扑和罗马密集不规则的网络。这两个环境测试了我们框架在极端结构拓扑下的鲁棒性。虽然当前研究集中在车辆数据上以确保受控评估，但该架构本身是模态不可知的。未来的工作可以将框架扩展到其他地理区域（例如郊区、高速公路和农村），或者通过重新定义状态描述符和调整奖励函数来专门处理行人和自行车数据集，以适应特定模态的约束。