2. 成都信息工程大学 管理学院, 四川 成都 610225;
3. 南宁师范大学 计算机与信息工程学院, 广西 南宁 530100;
4. 深圳大学 计算机与软件学院, 广东 深圳 518060;
5. 广西教育学院, 广西 南宁 530023;
6. Department of Computer Science, Rensselaer Polytechnic Institute, New York 12180, USA
2. School of Management, Chengdu University of Information Technology, Chengdu 610225, China;
3. School of Computer and Information Engineering, Nanning Normal University, Nanning 530299, China;
4. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;
5. Guangxi College of Education, Nanning 530023, China;
6. Department of Computer Science, Rensselaer Polytechnic Institute, New York 12180, USA
将情景感知技术[1]应用于大规模移动对象轨迹预测是当前学术界相对空白的研究领域, 而此技术在其他领域的应用已经初见成效, 考虑到轨迹预测的实用性, 将情景感知技术应用于轨迹预测具有较高科学意义和研究价值. 当前移动对象轨迹预测研究工作并未涉及复杂多变的情景信息, 预测结果偏差较大. 而且, 移动对象所处的场景会频繁变化, 考虑到情景的不断改变加上种类不同的移动对象以及由于情境变化导致它们随时有可能变化的移动模式, 因此在情景感知技术的驱动下预测多模式轨迹的研究显得更切合实际.
由于无线技术和定位传感器设备的空前发展, 移动对象在日常生活中无处不在. GPS传感器不间断地捕捉数据, 呈现诸如人、动物和车辆等移动物体的空间轨迹数据[2, 3], 同时使用社交网络的用户在社交网络上签到或使用同城推荐服务时, 用户将有意识的记录位置信息; 当手机呼叫接通时, 通过手机信号可被动记录位置信息; 刷卡或扫码交易时, 也会被动记录位置信息. 通过对上述时空数据的利用可以为社会生活带来众多帮助, 如现实生活中越来越多自主智能系统的出现, 利用这些系统感知、识别和预测移动对象的行动变得越来越重要. 具体来说, 轨迹预测问题定义为是利用移动对象当前已有的位置点信息来预测移动对象未来的连续位置并考虑对这些预测结果进行规划, 通常情况下表现为, 已知前序轨迹序列集p1=(x1, y1, t1), p2=(x2, y2, t2), …, pn=(xn, yn, tn)的情况下对最后一个采集到的轨迹点之后的轨迹序列进行预测, 即预测未来连续轨迹点组成的轨迹序列<pn+1=(xn+1, yn+1, tn+1), pn+2 = (xn+2, yn+2, tn+2), …>. 该技术的运用是智能导航、无人驾驶车辆、服务型机器人和监控系统等领域的关键任务. 这些领域内的相关系统通常以移动对象数据库或时空数据库为基础创建, 大量的轨迹形式的数据存储在其中, 数据中潜藏了移动对象的行动规律和特点. 目前, 许多研究人员已经利用轨迹数据来挖掘隐藏在数据中的潜在模式, 提取运动模式来分析移动对象的行为. 如Brown等人[4]指出在自动驾驶车辆的研究中模拟人类驾驶员的行为是实现安全高效的自动驾驶系统必须解决的问题, 该课题组介绍了现有的模拟和预测人类驾驶员行为的方法, 给出一个通用的数学框架, 用于对任意交通场景中的驾驶员行为进行建模, 构建了一个分类法, 该分类法根据现有模型对部分属于驾驶员建模范畴的算法进行分类. 位置预测通常采用许多技术, 包括轨迹数据预处理、识别兴趣点聚类、轨迹模式挖掘等[5]. 此外, 情景感知应用产生和积累了海量、动态、异构、无规律、分布在系统各处的情景信息. 而轨迹数据研究的最终目的是回答: “在何时(When)、何地(Where)、时空对象(Who或What)发生了什么样的变化(What)以及如何变化的(How)”, 这与情景感知研究中的4W (Who、When、Where和What)非常契合, 而移动对象所处的运动环境是动态变化的, 不能单纯依赖静态交通网络环境预测其运动行为, 需要综合考虑用户的行为习惯、所处的位置、社会关系等用户场景; 交通状况、天气情况等物理场景; 出行高峰、季节等时间场景对移动对象运动行为的影响. 本文将综述轨迹预测的基本定义, 轨迹数据的来源和表现形式, 经典的算法、模型和关键技术, 以及不同的应用场景. 其次, 介绍情景感知的基本概念与定义, 其所包含的关键技术以及实现方法, 情景感知技术与实际应用的结合, 以及情景感知应用于轨迹预测的方法, 最后总结当前研究的进度和存在的问题, 展望未来的研究方向.
现实生活场景中有许多不同类型的轨迹数据, Zheng等人[6]根据轨迹来源将轨迹数据分为主动或被动记录. 例如: 在社交媒体签到打卡时主动记录了自己的位置, 或者拍摄了基于位置的图片, 图片与位置标签相关联. 被动记录则是轨迹大数据的重要来源, 如今移动便携式信息采集器已经普及, 这些装置会自动记录大量轨迹点. 交易记录等也可看作轨迹数据, 因为其记录了时间和地点. 而情景信息一般通过两种方法获取: (1)感知环境:环境信息和用户物理信息可以通过物理或软件传感器获得. 用户的交互习惯和交互历史记录主要是通过主机的逻辑传感器获得的. (2)明确提供的情景:例如, 当用户的偏好被明确传达给发出请求的应用程序时, 可以获得这些偏好. 轨迹数据通常被表述为移动对象坐标随时间的变化情况, 如GPS中返回的数据是某一时刻的经纬度, 则可以用类似p=(x, y, t)的形式表示, x和y分别代表移动对象的经纬度, t代表时间. 每隔一个单位时间返回一次, 一段时间后反映在地图上便是一系列轨迹点形式的位置信息, 按时间先后顺序连接起来便是一条线型轨迹, 如图1所示. 通常一条轨迹中包含多个重合点, 当一段时间内移动距离相对骤减时, 则推断附近存在一个停留点. 同理, 如果有多条轨迹相交于某一点时也可推断此处为停留点或热点. 当然这些推断需要数据经过特定模型计算后才能得出结论. 而对情景信息的利用则需要更加灵活多变, 例如在相同时间间隔返回的轨迹点数据之中, 距离间隔有长有短, 这或许是因为这条轨迹之中移动对象的承载的交通工具发生了变化, 即运动模式发生了改变, 因此可以用不同的数学变量来表示不同的运动模式. 在将这些数据用以预测模型的输入之前需要一系列准备工作, 包括数据清理、噪声去除[7]、轨迹压缩[8-10]、轨迹分割[11, 12]和轨迹语义[13]等处理.
|
Fig. 1 Example of a simple trajectory 图 1 简单轨迹举例 |
预处理是将原始轨迹数据修改为有用且有意义形式的必要步骤, 进而获得更好的预测准确性. 数据清理具有噪声过滤和停留点检测功能[14, 15]. 数据收集中可能出现的噪声则需要将其过滤掉, 通常可以通过中值、卡尔曼[16]、粒子滤波器[17, 18]进行滤波去噪. 停留点检测是指, 在轨迹点采样间隔相同的情况下, 一定单位时间内返回的位置点间隔较短甚至无间隔. 在情景感知驱动的轨迹预测算法中, 常将轨迹序列中位置点之间的时间和空间间隔以权重的形式表示, 移动对象在某一位置停留了一段时间, 在该位置停留的时间越多, 其权重值就越高, 以此可通过将上述权重作为参数考虑到模型中来预测移动对象未来的轨迹. 轨迹压缩则是在尽可能小的影响预测精度的情况下减少数据量. 数据压缩的性能指标主要表现在压缩率和误差量. Meratnia等人[19]和Muckell等人[8]提出了两种误差指标, 即垂直欧式距离和时间同步欧式距离. 如图2所示, 垂直欧式距离顾名思义是计算预测点到实际轨迹点的投影, 图中将{p1, p2, …, p13}压缩到3个点, 每一个轨迹点pn都有一个时间标记. 时间同步欧式距离则是将轨迹看作匀速运动, 根据返回的时间戳估计两点之间的轨迹点.
|
Fig. 2 Euclidean distance 图 2 欧氏距离 |
轨迹压缩算法可分为在线和离线两种, 如将曲线近似表示为折线的Douglas-Peucker离线算法[20]等. 特征提取是为了获取有意义的数据属性和数据特点以使机器学习算法能够正常工作, 如经常访问的兴趣点, 这是重要的特征. 为了提取兴趣点, 可以考虑基于聚类的方法[21], 如图3所示, 图中显示了在轨迹中所有点上对兴趣点收集的迭代过程, 图中x表示集群的中心点, 虚线区域是上一步迭代前的集群位置.
|
Fig. 3 Examples of clustering algorithm for identifying points of interest 图 3 识别兴趣点的聚类算法图例 |
轨迹预处理的方法不仅只适用于收集到的位置信息, 也包括收集得到的情景信息, 但由于情景信息的特殊性, 其无法像轨迹数据一样已经有了成熟的记录方法和记录标准, 因此需要更有针对性的方法来处理情景信息. 最简单的方法就是将情景信息变量化, 例如, 将天气情况映射为一定范围内连续可变的数量, 又或使不同运动模式用不同变量表示, 通常将这些变量以参数的形式输入轨迹预测模型.
轨迹预测的已有模型涉及不同领域的不同算法, 数学统计学方法中包含: 隐马尔可夫模型[22], 朴素贝叶斯[23], 高斯过程[24], 灰色模型[25]等. 机器学习[26]方法中包含: SVM[27], BP神经网络[28]. 另外还有启发式算法, 滤波算法卡尔曼滤波[29]等.
如表1所示, 隐马尔可夫模型优点在于对状态多变的轨迹有相对较好的预测效果, 因为该模型在历史信息的利用上仅与其前一个状态有关, 更适用于情景多变的场景. 不足之处在于因为该模型的无记忆性, 不能利用轨迹序列的前序信息, 如果希望使用更多的已知信息只能建立高阶的隐马尔可夫模型. 朴素贝叶斯多用于分类算法领域, 其算法核心是基于概率的预测, 例如在某路口通过车辆速度, 车型大小, 行驶车道等特征计算直行或转弯的概率来进行预测. 优点在于对大规模数据的训练有较高的速度, 对小规模数据的训练效果较好, 对缺失数据不敏感. 不足是需要计算先验概率, 对输入的特征敏感, 并且输入样本需要独立. 该方法适用于在交叉路口等有约束性的地点进行轨迹预测, 因为此类地点的运动方向具有局限性. 高斯过程的优点是预测值符合高斯分布, 因此可以计算经验置信区间, 然后根据这些信息, 在某个区域重新拟合预测, 不足在于需要使用完整的样本训练, 并且在特征个数多之后预测效果骤降. 该方法适用于单一运动模式下的轨迹预测, 因为随着不同运动模式的轨迹特征个数增加, 该方法性能会降低, 若要对包含多个运动模式的轨迹序列进行预测, 则需要用多个高斯过程回归模型. 灰色模型的优点是不需要大量的训练样本, 样本也不必有规律性, 对于不确定因素的复杂系统预测效果较好, 但是没有考虑系统的样本随机性, 中长期预测精度较差, 即无论是何种运动模式的轨迹, 该方法适用于变化频率较低的场景. SVM的优势在于当有很少特征即低维数据和很多特征即高维数据上均表现良好, 因为使用核函数可以向高维空间映射, 不足是对大规模训练样本难以实施, 同时对缺失数据很敏感, 对调参敏感, 需要参数调节. 该方法适用于单一监控下的轨迹预测, 数据量不大且轨迹变化平稳的场景. BP神经网络与深度学习从数学理论上来说3层网络已能够逼近任何非线性连续函数, 所以BP神经网络具有较强的非线性映射能力, 具有自学习和自适应能力, 同时在少部分神经元破坏的情况下对训练结果不会造成很大影响, 不足在于: 由于BP神经网络对初始网络权重非常敏感, 同时存在局部最小化问题, 导致如果初始网络权重不统一的情况下, 训练结果可能各不相同. 该方法适用于绝大多数轨迹预测场景, 但在复杂环境更具优势, 因为简单环境的轨迹可能存在前序轨迹重合的情况, 这使得神经网络的初始权重类似, 不能做到有区分性的预测, 在复杂场景下输入参数更多, 更容易做到有区分性的预测. 再者, 神经网络的结构没有一个统一的标准, 只能根据具体实例的情况选择合适的网络结构. 卡尔曼滤波与隐马尔可夫模型类似, 极度依靠前一个序列点的信息和当前位置信息来做下一时刻预测, 优点在于在状态估计中途非常平稳, 不足在于其计算过程是一个不断预测修正的过程, 适用于需要强实时性的轨迹预测场景, 对于长序列的预测效果并不显著.
|
Table 1 Different trajectory prediction models 表 1 不同轨迹预测模型 |
1 情景感知与多模式轨迹预测技术研究 1.1 情景感知概述
情景感知(context awareness)自提出至今已受到了广泛关注, 并被认为是未来的热点研究领域, 可以利用不断发展的便携式传感器和移动通信设备获取用户所在的周边地理信息、移动轨迹和时间等信息[30], 分析用户意图、预测用户行为, 有针对性地提供基于位置的服务. 情景感知通过相关技术使计算机设备能够“感知”到用户当前的所处环境等相关信息, 进而可以加深了解用户的行为动机等, 目的是让计算机能自适应地改变满足用户不同情景的需求[31]. 情景的3个重要方面是: 在哪里、和谁在一起、附近有什么资源, 且情景不断变化会产生不同的影响, 如照明、噪音、有无网络连接等[32]. 情景感知最早由Schilit 等人[1]提出, 并描述了情景感知应用的四种类型:近似选择、情景自动重构、情景信息和命令、情景操作. 随着用户由传统的台式计算环境转变到可移动计算环境, 应用程序越来越需要利用隐藏式信息或情景, Dey等人[33]定义情景感知为: 无论是用桌面计算机还是移动设备, 普适计算环境中使用情景的应用. 同时认为情景感知可以在调整应用程序执行任务的方式以及更改任务的可执行性方面发挥作用.
情景感知大致分为独立的和基于基础设施的[34]. 从信息获取方面考虑, 包括收集定制传感器信息或者便携式通信设备自带的摄像头、语音接收装置、现有数据库等, 系统从用户主动输入、数据库或通信设备收集情景信息, 并将其添加到存储库中. 此外, 系统可将当前情景信息收集以作备用. 最后, 系统使用情景并给出反应, 并向用户揭示适当的情景. 情景获取是情景感知的基础, 通常由3种方法获取情景: (1) 环境感知方法: 环境信息和用户的物理信息可以通过物理传感器和软件获得; (2) 推导情景: 通过动态计算得到情景信息; (3) 已提供的情景: 当用户偏好被明确传达给发出请求的程序时获得情景. 当系统中存在大量的情景信息时, 最关注的是用户的位置、时间和活动. 位置可以通过GPS获取, 这是最广泛和准确的方法, 还有WiFi, 蓝牙等通信手段可以在某个区域通过网络接收获取位置信息. 时间可以从计算机的内置时钟获得, 但当前用户活动的获取则是一个难点, 若能获取移动设备摄像头权限利用机器视觉技术[35]能获取一部分活动. 或使用AI技术通过多个简单的传感器信息来识别情景活动. Qiao等人[36]通过利用社交网络中的位置信息, 社会关系, 购买习惯等情景数据来推断人们的地点的偏好, 从而提出SocialMix位置推荐算法. 该算法充分考虑了用户的偏好相似性以及用户之间的关系, 使用3个特征变量来计算用户之间的熟悉度, 即: 共同的朋友数, Jaccard指数和余弦相似度. 采用最大似然估计确定这些特征变量的权重, 将这些特征拟合到逻辑回归模型中, 以计算熟悉度. 此外, 引入一种新的用户相似度计算方法, 将偏好相似度和熟悉度结合起来, 考虑用户的社会影响, 用该方法计算用户的位置兴趣度.
1.2 情景感知计算和推理信息的收集完成后接下来是情景感知计算和推理, 情景感知计算被视为普适计算[37]的一种, 具有普适性、自适应性、动态性等特性, 主要思想是网络与物理空间的融合, 以及无干扰的计算[38]. 移动设备所提供的应用服务使得情景感知计算成为热门研究领域, 这项工作的挑战是通过一类新的应用程序来利用不断变化的环境信息, 这些应用程序知道它们运行的环境. 情景感知系统可利用当前环境、用户类型、可访问数据库、传感器信息进行工作. 具有这些能力的系统可以检查计算环境, 并对环境的变化做出反应. 情景不仅包括用户的位置, 因为其他影响系统的东西也是移动和变化的. 情景包括照明、噪音水平、网络连接、通信成本、通信带宽等信息. 为了帮助用户从情景推断中做出决策, 数据分析技术提供了很大的帮助. 一般来说情景感知计算和推理分为两类, 确定性语境推理和不确定性语境推理[39]. 由于情景信息的复杂性、不可控性和动态性. 相比于传统计算的确定性推理, 不确定性推理更加适用于情景感知计算, 不确定性推理的数据模型构建主要有多传感器融合技术, 包括基于证据理论、基于神经网络和贝叶斯网络的方法.
图4显示了从输入传感器收集的数据被预处理并转发给知识获取模块, 接下来将前面步骤中生成的数据提交给基于规则的分类器. 然后将数据挖掘算法应用于训练数据集以生成分类器, 这些分类器将做出情景感知决策[40]. 而从获取到情景信息到利用这些信息作为模型的参数需要一系列处理步骤, 这些步骤包括: (1)基于当前所面对的任务创建合适的计算模型来获取情景信息; (2)对收集到的信息聚合, 进行情景提取; (3)针对当前任务进行情景特征概括; (4)选择合适的算法; (5)进行情景识别并得出推论; (6)得出结论并帮助用户选择最合适的决策[41].
|
Fig. 4 The multi-layer architecture of a context processing system 图 4 情景处理系统的多层体系结构 |
表2给出了各种情景建模方案, 这些方案中得到最广泛应用的是基于本体的建模[42], 缺陷则是随着数据量增加, 从中检索情景非常耗时.
|
|
Table 2 Comparison of context modeling schemes 表 2 情景建模方案比较 |
Liu等人[43]总结了6种情景感知计算推理方法, 包括4种确定性推理方法和2种不确定性推理方法, 前者包括贝叶斯网络、基于规则的推理、基于案例的推理和基于本体的推理, 后者包括模糊推理和证据推理. Liu等人[44]针对实际工作中的不确定性和不精确性问题, 提出了一种模块化贝叶斯网络系统. 它通过虚拟链接保持了模块间的依赖关系, 在复杂环境中具有较低的计算复杂度. 然而, 即使使用上述方法来减少贝叶斯网络推理所需要的假设量, 与其他推理技术相比, 它仍然需要更高的计算开销, 而且静态贝叶斯网络无法对动态环境进行推理. 基于规则的推理隶属于基于知识的专家系统, 它使用提前设定的规则或先决条件来推荐内容并得到相应结果或结论. 移动平台要求情景建模语言和推理引擎简单、轻量级. 针对这一问题, 推出了一种基于规则的情景推理平台[45, 46]. 此外, 为了实现更高级的情景推理, 包括情景处理和基于实际情景的新信息的推导, Meng等人[47]提出了一种名为HeaRT的基于规则的推理引擎, 使用扩展列表树表达知识, 从而提供自主的推理服务. 规则推理具有明显、推理清晰、模块化强等优点, 有效解决了推理能力差、不确定性强的问题, 不足是规则需要手动定义, 而且容易出错. 基于案例的推理[48]是一个类似的推理方法, 其核心思想是利用先前的经验和知识来解决类似的问题和调整新旧之间的差异情况进而求解新问题, 形成新案例并添加到知识库中. 基于案例的推理是一种根据过去不同问题的经验来解决新问题的方法, 它与人类决策具有高度相关性, 均为通过总结过去来寻找解决当前所面临的情况的方式, 也因此缺少分析情景的能力. 同时还存在一些问题, 例如如何基于案例集自动生成新的案例, 如何比较两个案例之间的相似度等. 基于本体的推理主要使用一组描述逻辑(description logic)从原始信息中推理出潜在的情景, 描述逻辑是本体语言推理的重要设计基础, Mok等人[49]提出一种基于本体的情景感知模型, 并应用于家用电器的能耗最小化问题. 工作原理为: 首先, 由家庭服务器收集由网络本体语言描述的各种情景数据(例如, 小电器的用户位置、偏好和电源状态); 然后, 推理引擎将收集到的情景实例转换成一阶逻辑的形式, 在此基础上使用推理规则来生成控制家庭设施能耗的高级情景. 在不确定性推理中, 基于模糊的推理将模糊集理论应用于不确定概念的收集、表示和推理, 用置信度而不是概率来表示情景信息之间的关系程度. 可以将两个或多个模糊集的元素组合在一起, 生成一个具有各自成员函数的新的模糊集. 模糊推理适合于描述主观情景, 实现多传感器融合, 解决不同情景之间潜在的冲突, 但它不适用于需要准确情景的环境. 证据推理是一种基于信任函数和不确定性推理的证据理论, 它将独立的部分情景信息作为预测事件可能性的证据, 常用作为传感器信息融合的一种方法, 情景感知应用程序收集的多源情景由于类型不同, 很难融合. Zhang等人[50]提出了一种基于Demspter-Shafer证据理论的推理机制来实现情景融合. 首先, 预处理器为每个传感器的情景信息分配一个先验概率. 然后, 根据Dempster理论, 如公式(1)所示, 将两个情景证据反复组合, 得到最终的融合结果. 其中Bi和Cj表示情景证据信息, mi(Bi)和mj(Cj)表示可信度, A表示Bi和Cj融合后产生的新证据.
| $ \left( {{{{m}}_{{i}}} \oplus {{{m}}_{{j}}}} \right)\left( {{A}} \right){{ = }}\frac{{\displaystyle\mathop \sum \nolimits_{{{{B}}_{{i}}} \cap {{}}{{{C}}_{{j}}}{{ = A}}} m_i{{(}}{{{B}}_{{i}}}{{)}}{{{m}}_{{j}}}{{(}}{{{C}}_{{j}}}{{)}}}}{{{{1 - }}\displaystyle\mathop \sum \nolimits_{{{{B}}_{{i}}} \cap {{Cj = \varphi }}} {{{m}}_{{i}}}{{(}}{{{B}}_{{i}}}{{)}}{{{m}}_{{j}}}{{(}}{{{C}}_{{j}}}{{)}}}}$ | (1) |
情景的存储和原始情景数据以及过滤和融合的情景信息可以存储起来, 以便进一步检索, 同时应该被很好地整理为各种数据结构, 如表、对象、树、图形等. 此外, 情景的存储对于获取历史记录是很有帮助的, 以便将处理过的情景信息输出. 情景存储的体系结构可以是集中式的, 也可以是分布式的. 情景信息的有效和可靠存储涉及很多问题, 如: 即时性、情景和对象之间的相关性、情景检索需要范围而不是单一条件等.
1.3 多模式轨迹研究与传统数据相比, 轨迹数据具有独特属性, 例如: 变化的采样率、不同的长度和稀疏性等, 意味着位置预测面临诸多挑战. 同时, 由于用户的当前位置与该用户历史位置信息相关, 移动对象在不断运动的过程中周围的运动环境会随之发生转变, 轨迹数据也会受到情景信息的影响. 如果用户没有轨迹历史, 则很难建立关于他的未来位置的预测器, 这被称为冷启动问题[29]. 如果用户只有几个访问位置, 也很难建立他未来位置的预测器, 这是一个稀疏性问题[30]. 冷启动和稀疏性问题在预测应用中普遍存在, 尤其是那些使用主动记录的轨迹数据的应用. 所以无法用单纯的理想化环境对运动行为进行预测, 如: 所有车辆不可能一直在完全空旷的道路上行驶. 特别是, 实际应用中可研究的连续轨迹大多不是单一的运动模式, Rudenko等人[51]总结和分析了大量的多运动模式下人类轨迹预测方法, 并将这些方法分为3大类: (1)基于物理的方法(感知-预测), 通过正向模拟一组遵循物理模型且明确定义的动力学方程来预测运动; (2)基于模型的复杂性还可分为单一动态运动模型和多动态运动模型; (3)基于模式的方法(感知-学习-预测), 根据训练数据近似任意的动力学函数. 上述方法能够在观察到的运动轨迹中发现统计行为模式, 并分为有序列方法和无序列方法; 基于计划的方法(感知-推理-预测) 明确推理移动对象的长期运动目标, 并应用计算策略预测移动对象运动趋势, 使用预定义的回报函数对移动对象的运动做出基于最优假设的前向规划, 使用统计学习技术从观测到的轨迹点中估计基于回报函数的逆向规划方法. 同时由于移动模式的混合性, 在包含较为复杂的轨迹模式场景下, 典型运动模式不止一个, 一条轨迹可能隶属于多个轨迹模式, 称之为多模式[52]. 移动对象的类型不同会产生不同的运动行为, 即使同一类型的移动对象也会由于各种主客观因素而导致不同的运动模式. 例如, 移动对象的一段行程中有出租车、公交车、步行等多种轨迹数据来源, 这些运动物体通常具有不同的采样率和运动模式. Xu等人[53]指出移动对象数据库应该能够管理多个真实运动环境中的轨迹数据, 如人行道的行走轨迹, 道路上的行车轨迹, 公共交通工具的轨迹等, 因此设计了一个能够在表示多种环境中描述移动对象的数据模型, 其中基础设施覆盖移动对象的空间, 每个基础设施对应于一个环境. 每个基础设施由一组表示移动对象可用位置的组件组成. 移动对象的位置映射到这些基础设施组件, 提出了新的数据类型来定义每个基础设施中的移动对象和组件, 以支持对不同环境和不同交通方式出行的基于语义的查询. 在许多场景中, 数据集还包括社交关系或短信. 因此, 这种多源异构的轨迹数据融合分析是位置预测系统中的另一个挑战. 难点在于: (1) 尽管移动对象数据库[54]中存储了大量移动对象的轨迹信息和运动状态, 但因为实际应用场景中移动对象数量多且移动方式复杂, 所以通过地理坐标定位和时间戳结合的方式获取的轨迹数据信息量大且难以分类, 需要有针对性的挖掘方法; (2) 预测时间需要尽可能的短, 以此来保证预测下一位置的时效性; (3) 移动对象的主客观因素需要以参数形式设置, 例如移动对象的交通工具种类和交通状况, 有可能极大地影响预测模型的准确性.
1.4 情景感知驱动的轨迹预测模型情景感知技术在轨迹预测领域的也能一定程度上解决本文提到的冷启动与稀疏性问题, 冷启动和稀疏性问题在推荐系统领域较为常见, 由于新用户鲜有可利用的行为信息, 难以给出推荐, 所以许多应用会在注册时要求用户填写一定个人信息进行粗粒度推荐, 但这在轨迹预测领域无法实施, 因为移动对象的移动是突发事件. 所以情景感知技术在这种情况下显得尤为重要, 结合情景感知技术让移动对象输入一些特征参数到预测模型中, 例如周围兴趣点的密度, 兴趣点的种类, 移动对象的种类, 当前的地理位置, 交通状况, 历史数据中从当前位置出发的移动对象的轨迹等.
情景感知驱动的大规模多模式轨迹预测研究架构划分为如图5所示的4个层次, 研究主要集中于数据处理和轨迹预测, 情景信息的采集和数据形式多样化需要有针对性的方法, 在多样化的信息中进行特征识别和提取, 并将其运用于轨迹预测模型.
|
Fig. 5 The architecture of multiple-motion-pattern trajectory prediction of moving objects with context awareness 图 5 情景感知驱动的移动对象多模式轨迹预测架构 |
情景感知驱动的大规模多模式轨迹预测模型研究的目标旨在将情景感知技术应用于大规模多模式轨迹预测的研究中, 设计轨迹大数据处理新型算法、数据结构和框架, 以时空数据库、情景感知计算、大数据技术为手段, 建立高效准确的数学模型和方法, 在一个或两个具体应用(如智慧交通预测、城市计算)上解决实际问题, 对提出的应用基础问题和理论进行深入探索. 情景感知驱动是作为技术枢纽和创新点与轨迹预测紧密相关, 是课题组提出的新型大规模多模式轨迹预测的新技术新方法, 在该技术领域中, 可利用的情景包括但不限于时间间隔、距离间隔、路况、车辆(或其他运动模式)状况、天气、日期等. 通过给这些情景赋予适当的权重, 或者将其嵌入向量化作为模型的参数, 改进已有的轨迹预测模型或新建专用模型, 将情景参数加入预测模型以此达到精准预测的目的. 例如, LSTM作为一种特殊的RNN网络, 是为了解决传统RNN无法解决的长期依赖问题而设计的, 适合处理预测时间序列中间隔较长的问题. 由于LSTM将时间序列分为长期效应和短期效应, 于是在连续轨迹点中, 可以尝试将轨迹点之间的时间和距离间隔分别赋予权重通过衰减函数加入短期效应, 构造新的短期效应, 将长期效应和衰减后的短期效应合并组成调整后的前序记忆, 进入下一次预测. 将时空间间隔作为一般情景加入轨迹预测模型是当前最优先考虑的情景感知驱动方式. 再者, 设计新型情景感知轨迹大数据处理技术, 这些技术包括: 情景感知数据特征提取、大数据降维分析, 保证时空轨迹数据的质量; 由于多种因素存在, 移动对象常具有不确定性, 现有索引技术大多面向确定性移动数据, 无法直接索引不确定移动数据. 从当前相关研究工作来看, 重点问题集中于两点: (1) 情景感知计算关键技术[55], 情景获取, 利用信息抽取技术获取不同粒度层面的感知信息, 包括: 初级情景(位置, 时间, 邻近对象, 来源)、高级情景(用户的当前活动, 社会环境)、情景变化(从一中状态到另一种); 情景处理与识别, 包括情景说明与表述、表示与转换、识别与应用, 利用知识表达、数据预处理和数据转换技术结合不同应用背景需求准确识别简单和复杂情景信息, 并对情景信息建模应用于不同的轨迹预测场景. (2) 融合情景信息的多模式轨迹预测模型, 研究需要对影响移动对象运动行为的复杂情景建模, 设计新型移动对象多模式轨迹预测算法, 尽可能保证在数据量增大的情况下减小位置点获取和预测的成本, 同时提高准确性. 此外, 位置信息的不规则性和情景信息的大数据量、动态变化性, 需要算法性能不会随移动对象数目增加剧烈地下降, 具有稳定性、鲁棒性和可伸缩性.
情景感知驱动的大规模多模式轨迹预测研究的技术路线是: 通过便携式通信设备、手机互联网、城市智慧监控等获取用户情景信息和轨迹大数据, 经过特征提取和数据降维分析等处理后存入数据库. 通过轨迹数据库中的数据做热点区域挖掘, 进而实施轨迹预测, 如图6所示.
|
Fig. 6 Technical roadmap of multiple-motion-pattern trajectory prediction of moving objects with context awareness 图 6 情景感知驱动的多模式轨迹预测技术路线图 |
整体研究可分为3个部分: (1) 情景感知轨迹大数据的处理, 包括算法、数据结构等; (2) 轨迹热点区域挖掘; (3) 情景感知驱动的多模式轨迹预测模型. 在第(1)部分研究内容中, 情景感知大数据处理首先需要对情景感知数据的特征提取, 标准GPS数据包含时间、位置、状态和信号质量4类数据, 可以从中获得包括用户情景和时间情景在内的初级情景信息, 对于位置点之间的关系、用户当前活动、交通拥挤情况等高级社会情景, 拟采用隐马尔可夫或者条件随机场模型进行深层次抽取, 构建轨迹时空语义网络. 然后是轨迹大数据降维分析, 对轨迹数据实现空间维度和时间维度的降维分析, 空间维度通过分析路网中节点的介数(betweenness), 减少路网中的区域或减少边, 抽取关键节点和路径. 此外, 采用主成分分析技术将关键分量的分析获得全局特征, 实现进一步空间降维. 对于时间尺度的降维分析, 设计找寻和量化移动对象的整体移动模式在各自时间片下显著差异的算法, 进而实现精确的时间片划分, 降低各时间段间的相似性. 最后是采用混合时空索引结构索引移动对象历史、当前和未来轨迹信息, 实现轨迹及位置点的高效查询. 设计一种新型混合索引结构, 其基于历史树和双层索引结构DISC-tree[56], 历史树采用四叉树索引移动对象历史轨迹点, DISC-tree索引移动对象现在和最近将来的位置信息. 同时, 随着时间的推移, 将DISC-tree的内容过渡到历史树中. 此外, 为移动对象的各段轨迹建立双向链表, 当要查找某一移动对象的完整或者部分轨迹时, 只要找到一段, 就可以依据前向后向指针找到轨迹所有各段. 这样既保证了历史轨迹的空间性, 又实现了轨迹的连续性.
第(2)部分研究内容为轨迹热点区域挖掘, 由于移动技术的巨大进步, 许多网络位置信息的出现可以帮助用户导航或预测可能感兴趣的热点位置, 这些位置可能不同于往常地理信息系统中的一成不变的地标建筑型兴趣点, 而是更贴近于人们移动生活的热点区域. 基于位置的社交网络日益流行, 人们借此可以很容易地分享他们的想法、评论、图片、和他们朋友的位置. 在线签到数据的快速增长为从人们的历史轨迹中了解他们的移动行为并预测他们未来的足迹提供了一个很好的机会, 通过对上述信息进行挖掘, 可以发现轨迹热点区域, 进而对移动对象的位置进行有针对性的预测. 设计一种例如基于Hausdorff距离的轨迹点相似性度量方法对具有相似行为特征的时空点进行聚集操作. 基于时间、空间和环境特征, 设计层次型聚类算法自下而上地把较小的cluster合并聚集. 聚集过程分为两个阶段: (1)局部匹配, 将轨迹划分成不同基本单元, 给定一个距离阈值θ, 如果两个基本单元之间的距离小于θ, 则认为基本单元匹配; (2)全局匹配, 计算任意两条轨迹的基本单元集合中局部匹配轨迹点的数量, 如果大于给定的数量阈值ξ, 则认为两条轨迹全局匹配. 基于平移的最小Hausdorff距离的思想, 不仅比较两个基本单元的形状及其蕴含的运动规律, 而且能够消除一定范围内基本比较单元的公共偏差, 提高热点区域挖掘的准确性. 具体工作原理如图7所示.
|
Fig. 7 Working mechanism of trajectory hotspot region mining algorithms 图 7 轨迹热点区域挖掘算法工作原理 |
第3部分研究内容为情景感知驱动的多模式轨迹预测模型, 如图8所示首先是情景感知信息建模. 可以利用关键值偶模型(key & value pair models)对时间和位置情景等简单情景信息建模; 利用面向对象模型(object oriented models)对用户情景和社会情景等复杂情景信息建模, 模型将每一种可能出现的情景因素组合映射为一种关于移动对象行为模式的状态, 每一种状态信息能够充分反映动态情景的变化, 与轨迹上不同位置点相对应, 将移动对象的一条完整轨迹表示为一条包含复杂情景信息的状态链. 然后是模型训练和学习预测, 结合情景感知信息, 针对稀疏离散的轨迹大数据和密集复杂的轨迹大数据分别考虑利用高斯混合模型和卡尔曼滤波算法建模.
|
Fig. 8 Working mechanism of multiple-motion-pattern trajectory prediction with context awareness 图 8 情景感知驱动的多模式轨迹预测模型工作原理 |
2 轨迹预测方法 2.1 数学统计学类
数学概率统计类算法中, 隐马尔可夫模型HMM (hidden Markov model)常用于长序列预测问题[57], 乔少杰等人[58]提出了一种自适应参数选择的高阶隐马尔可夫轨迹预测模型, 模型能够有效地对轨迹大数据进行聚类分析和分区定位, 并利用密度聚类算法提取隐含和可见状态, 可以自动选择输入轨迹的参数, 避免了出现不连续的隐含状态以及状态保留问题. 另外, HMM在诸如序列分析、模式识别领域有广泛的应用. 在基于HMM的轨迹预测问题上, 通常包含五组数据描述模型: 隐藏状态、可观测状态、隐含状态转移概率矩阵、混淆矩阵、初始概率矩阵. 过去的轨迹则是可观测的状态, 一定时间内的轨迹状态可建立初始状态概率矩阵, 隐状态转移概率矩阵表示模型中各个隐藏状态之间的转移概率, 混淆矩阵中元素表示模型各个隐状态和可观测状态之间的转移概率.
Lim等人[59]提出了一种基于检测到的车辆中心坐标预测其他车辆轨迹的方法, 通过使用基于车辆中心坐标历史数据的高斯过程自动回归来预测二维像素平面上的未来位置来实现, 算法过程使用YOLO检测车辆, 找出中心坐标点并存入序列, 将收集到的数据通过一个低通滤波器, 对坐标的时间序列数据进行时间平滑处理, 通过过滤后的数据用高斯过程自动回归更准确地进行轨迹预测. 同时, 与卡尔曼滤波、移动平均和LSTM不同, 高斯过程自动回归能够预测车辆的未来像素坐标, 不需要基于规则的模型, 只需一个单一的摄像机传感器就可以实现. 乔少杰等人[60]提出高斯混合轨迹预测模型, 将包含多种移动模式的轨迹用高斯混合回归建模, 分析不同移动模式的概率占比, 然后利用高斯过程回归利用概率占比预测轨迹. Liu等人[61]基于隐马尔可夫模型建立了驾驶行为估计和分类模型. 通过在车道变换过程的开始阶段观察车辆状态来估计车道变换行为, 然后在车辆穿过车道标志之前利用分类器分类. 此外, 结合由分类器估计的驾驶员状态, 以统计方式预测变道车辆的未来轨迹. 该分类器使用真实驾驶数据进行训练和测试, 方法根据分类结果生成不同的轨迹. Ding等人[62]致力于现代智能交通系统中的轨道管理, 给定车辆的运动轨迹, 获得其在任意给定时刻的完整运动过程, 即其位置. 还可以针对大型车辆的行驶轨迹, 支持交通流分析、驾驶模式分析等复杂功能. 轨道管理包含复杂的路况信息和不同类型的移动对象, 是一种典型的多模式轨迹相关工作. 基于欧几里得插值的路网轨迹预测是通过移动对象不同采样点进行插值得到的, 然而由于真实路网中复杂多变的交通情况, 这种方法会导致频繁地出现误差. 而基于路网的运动轨迹是一系列具有时间戳的运动向量. 文章将安装在移动对象端和服务器端的地图分别称为“移动地图”和“服务器地图”. 将采样的GPS点与交通网络匹配, 得到网络运动向量. 采样时间以外的位置可以通过基于网络的插值得到. 但这需要进行密集地位置更新, 导致很大的通信代价. 同时, 当服务器地图由于真实交通网络的变化而发生变化时, 所有的移动地图都应该更新. 这大大增加了成本, 降低了系统的灵活性. 由此提出了一种基于网络匹配轨迹的运动对象数据库NMTMOD, 并提出了一种基于NMTMOD数据库的交通流分析方法. 网络匹配轨迹是由一系列网络运动向量和描述运动目标路径的路径组成. 在NMTMOD中, 不需要安装移动地图. 通过密集采样批量上传方法跟踪运动目标的位置, 并在服务器端进行网络匹配. 为了减少网络匹配轨迹的存储空间, 服务器丢弃不重要的采样, 只在轨迹中保留关键信息. Qiao等人[63]提出了一种三合一的道路约束交通网络轨迹预测模型, 主要包含3项新技术: (1) 约束网络R树(CNR-tree), 一种基于交通网络的双层运动目标动态索引结构; (2) 采用兴趣区域(region of interest, ROI)发现算法将大量轨迹点划分为不同的簇; (3) 提出一种基于频繁轨迹模式树的方法发现频繁轨迹模式推断目标在ROI内移动的未来位置. Dai等人[64]提出了一种基于大规模轨迹数据的个性化路径推荐方法. 其提供的技术根据众多行程的出发地和目的地之间的行驶轨迹, 利用不同司机的驾驶偏好, 例如更多考虑行驶时间、最短距离、油耗等出行成本进行建模和更新, 然后根据司机的偏好以及指定的出发地、目的地和出发时间, 从所有轨迹中有效地选择轨迹子集. 同时构建一个具有适当边权的小图, 用图中边的权重大小表示不同路径的适用概率, 配合最短路径得出推荐路线. 算法的新颖之处在于: 在考虑驾驶偏好的情况下, 从大规模轨迹中选取参考路径; 此外, 不同的路线方案中包含本地视角或全球视角方案. 工作原理为: 本地路线推荐算法输入参考轨迹设置RTraj, 运行个性路线推荐算法, 输出推荐路线. 首先根据参考轨迹RTraj建立局部参考图Gref, 根据局部参考图建立双向图Gref, 随之计算双向图Gref中双顶点的PageRank值, 计算公式如公式(2)所示.
| $ PageRan{k^{\left( k \right)}}({\mathop \vartheta \limits^{\rm{ - }} _x}) = \sum\nolimits_{{{\mathop \vartheta \limits^{\rm{ - }} }_x} \in IN({{\mathop \vartheta \limits^{\rm{ - }} }_i})} {\frac{{PageRan{k^{(k - 1)}}({{\mathop \vartheta \limits^{\rm{ - }} }_x})}}{{out({{\mathop \vartheta \limits^{\rm{ - }} }_x})}}} $ | (2) |
算法中参考轨迹即是已有的从目标起始点到目的地点的轨迹, 局部参考图则由这些轨迹通过的定点和边组成. 个性路线推荐算法将起始点, 目的点, 行驶时间和驾驶偏好作为输入, 返回参考图中的最短路径. 边的权值与驾驶偏好相关联. 驾驶偏好由各类出行成本的偏好比来表示, 如行驶距离, 行驶时间和油耗各自之间的比例组成. 文章中采用的构建带权重轨迹图, 结合最短路径的方法对轨迹预测有极高的参考价值, 当移动对象身处复杂情境中时, 周围的路况信息, 交通状况等都将对移动对象的路线选择产生影响, 而将各类情景设置为带权重的参数对模型的改进有优化效果, 例如Time-LSTM. 乔少杰等人[65]设计了一种基于前缀投影的轨迹预测算法PrefixTP, 该算法包含3个基本阶段: 首先, 数据收集, 配备传感器的互联车辆组成了一个车辆网格, 并生成大量的时空数据, 以通信和共享交通信息; 然后, 建模训练, 只检查前缀子序列, 并只将它们对应的后缀子序列投影到投影集; 最后, 轨迹匹配, 递归地寻找满足最小支持度要求的后缀序列, 输出最频繁的序列模式作为最可能的运动轨迹. 张润生等人[66]将电荷耦合摄像机装在车辆前方获取实时道路信息, 利用灰度和梯度特征构成目标函数, 用抛物线模型拟合道路边界, 统一化识别弯道和直道. 通过图像识别得到道路行驶参数, 包括行驶预瞄点, 侧向变差, 道路曲率等. 再通过这些参数结合车重和观测车辆的侧倾角度, 建立动力学模型, 以前面所提参数为输入, 输出车辆的运动轨迹. Pan等人[67]扩展了SCTM框架, 考虑了交通流的时空相关性, 并支持短期交通状态预测. 首先, 采用基于多元正态分布(MND)的最佳线性预测器作为原SCTM (social cognitive transition model)的辅助动力系统来预测边界变量和/或供给函数. 因为从历史交通数据分析, 预测器能够通过捕获实时测量和历史平均值之间的误差来调整预测, 预测的边界变量和供给函数作为SCTM的输入, 进行短期交通状态预测. 通过结合空间相关性分析经过校准的协方差结构来放宽SCTM的独立假设, 以进行概率交通状态评估. 为了实现实时应用, 提出滚动水平算法进行预测, 对于使用实时测量来调整预测的交通状态非常有效. 该方法的不足在于STCM框架有时间滞后的显示, 无法进行实时预测. 乔少杰等人[52]利用高斯混合回归方法建模来计算单一移动对象在移动过程中采用的不同移动模式的密度分布. 首先将轨迹数据分类来代指不同的移动模式, 再利用高斯过程回归通过分类集中的不同密度分布的移动模式预测轨迹. 基本思想为: 当轨迹在复杂移动模式环境下时, 多次采用高斯过程, 利用高斯混合回归进行轨迹预测. 高斯混合回归模型利用训练集输出数据的条件密度函数进行预测, 通过使用EM算法来估计概率密度函数相应的参数, 基于正态分布数据的条件分布为多个高斯分量回归函数, 使用预测回归函数的输出加权混合实现训练输出集的总体数据分析预测. 高斯混合回归训练模型的输入为, 已知轨迹矢量S={(x1, y1), (x2, y2),…, (xn, yn)}转化的X和Y方向上的n维矢量集X=(x1, x2,…, xn)T与Y=(y1, y2,…, yn); 输出为最佳训练轨迹矢量集X={x1, x2,…, xn}; 具体过程为: 首先计算出一次高斯过程的某移动模式在X方向的均值和协方差矩阵, 然后求取轨迹矢量相对某个移动模式的高斯概率函数, 再计算出在X和Y方向上矢量所有移动模式出现的总概率, 其由高斯混合回归计算不同移动模式的概率混合而成, 具体求取方法如公式(3)所示.
| $ {{p(}}{{{x}}_{{n}}}{{|\lambda ) = }}\mathop \sum \limits_{{{i = 1}}}^{{{M}}} {{{w}}_{{i}}}GP\left({{{x}}_{{n}}}{{|}}{{{\mu }}_{{{x,i}}}}{{,}}{\sum _{{{x,i}}}}\right)p({{{x}}_{{n}}}|\lambda ) = \mathop \sum \limits_{{{i = 1}}}^{{{M}}} {{{w}}_{{i}}}GP\left({{{y}}_{{n}}}{{|}}{{{\mu }}_{{{y,i}}}}{{,}}{\sum _{{{y,i}}}}\right) $ | (3) |
整个轨迹训练集高斯混合模型似然函数如公式(4)所示.
| $ {{p(X|\lambda ) = }}\mathop \prod \limits_{{{n = 1}}}^{{{N}}} {{p(}}{{{x}}_{{n}}}{{|\lambda )p(Y|\lambda ) = }}\mathop \prod \limits_{{{n = 1}}}^{{{N}}} {{p(}}{{{y}}_{{n}}}{{|\lambda )}} $ | (4) |
通过从已知的轨迹集中训练得到最佳似然函数参数, 再利用EM迭代选出概率密度最大的运动模式, 为轨迹预测模型使用. 高斯混合回归轨迹预测模型已有训练集为S=(x, y), 其中输入为x, 输出为y. 测试数据集S*=(x*, y*). 利用高斯混合回归模型和[y, y*]T的联合概率密度函数求取y的边缘密度函数和条件密度函数, 利用上述函数对预测数据概率密度函数建模, 使用期望最大化进行参数调整, 依据正态分布函数的条件分布得到多个高斯分量回归函数, 利用高斯混合回归将总体回归函数加权混合实现整体数据的回归预测.
2.2 机器学习类机器学习被定义为: 如果一个计算机程序在任务M中的性能(由T测量)随着经验而提高, 则该程序被称为从任务M和性能度量T的经验E中学习[68]. 同时在训练期间修正模型参数以最小化预测误差. 在机器学习方法中, 常将轨迹预测定义为一个有监督学习的回归性问题, 常规方法包括数据收集、数据准备、算法训练、预测. 有监督学习回归方法包括广义线性模型、支持向量机、支持向量回归[69]和人工神经网络等.
当前针对复杂动态环境下的轨迹预测逐渐得到重视. Fang等人[70]提出了一个基于时空轨迹数据的多源深层次的交通预测框架, 称为MDTP (multi-source deep traffic prediction framework). 该框架包括时空特征建模和多源桥接两个阶段. 然后, 他们提出了一个增强的图形卷积网络(graph convolutional network, GCN)模型和长短期记忆网络(LSTM)相结合, 在特征建模阶段捕捉流量的空间相关性和时间动态性. 在多源桥接阶段采用了两种方法, Sum(·)和Concat(·), 来连接来自不同轨迹数据源的学习特征. 以此捕捉动态时空交通网络中多种运动对象之间的相关性. Fang等人[71]认为从大量的轨迹数据中学习, 然后直接回归出未来轨迹的数据驱动类轨迹预测方法很难提供多模式预测. 例如, 对同一交通路网范围中的不同载具的轨迹预测, 由此提出一个新的两阶段轨迹预测框架, 用于对移动对象主体周围的其他运动对象进行准确的运动预测. 作者提出两阶段轨迹建议网络(TPNet), 在第1阶段中, TPNet预测一个粗略的未来终点位置以减少轨迹搜索空间, 然后根据预测的终点生成一组可能的未来轨迹. 在第2阶段, TPNet对生成的轨迹建议进行分类和细化, 然后输出得分最高的轨迹建议作为最终预测. 在第1阶段生成不同意图的方案, 以实现多样化的多模式预测. 利用可移动区域, 交通规则等约束对建议结果进行过滤, 使该模块更加有效. Zhang等人[72]提出一个新的概念时间相关流图(time-respecting flowgraph), 所有路径传播从一个顶点到另一个顶点都是时间相关的, 其中一个顶点被区分为根, 其他顶点可以通过时间相关路径到达该根. 在此基础上, 文章探讨了基于时态图的分布式时间相关流图模式匹配问题, 提出了一种基于GraphX的分布式基线算法以及一种优化算法, 该算法利用了时间相关流图的特性和分布式算法的分析来提高效率. Sun等人[73]的工作表明, 单纯学习移动对象之间的距离来计算不同个体之间社会联系的强度, 以此预测某一移动对象轨迹的研究无法表示人类社会中众多社会关系导致的不同行为, 因此提出了基于群体的社会互动建模方法, 利用实时监控的画面, 学习人群中的行为, 移动方向等. 将监控场景中的画面用相同颜色的圆圈标记有紧密社会关联的人群, 用相同颜色的箭头表示他们的运动方向, 以此可以将该场景表述为一个图, 这是特征传播的一种常见结构. 为了模拟这个结构, 作者提出了一个神经网络模型递归地提取社会关系, 并将它们形成一个社会行为图, 称为递归社会行为图. 利用图卷积神经网络来传播递归社会行为图引导下的特征. 每个行人都被视为一个节点, 其特征考虑了历史轨迹. 这些节点由社会关系连接起来, 这些社会关系被认为是图的边, 同时使用群体注释来监督社会关系的生成, 通过社会关系递归地更新交互作用范围内的个体轨迹特征, 进而利用更好的个体特征来更新社会表征. 该方法避免了考虑复杂的社会关系, 仅考虑有移动社会关系的人接下来的进行路线, 进而减少了大量的计算代价.
De Leege等人[74]在空中交通管理领域致力于增加每条飞行航道的每小时吞吐量, 利用真实的历史飞行轨迹和气象数据提出了基于机器学习的轨迹预测方法, 在该方法中, 使用历史数据训练模型, 模型输入是飞机类型、飞机地面速度和到达路线开始时的高度、地面风和海拔风. 采用逐步回归方法确定飞机连续下降运行所需的初始间距, 并考察其对跑道吞吐量和冲突的影响, 使得吞吐量相比固定初始间距每小时可增加4架飞机. Zhou等人[75]提出了一种名为Semi-Lazy的路径预测方法, 利用动态规划算法将轨迹点通过轨迹网格分开, 并采用改进的凝聚分层聚类算法使轨迹网格较小且保持高覆盖率, 该方法动态选择参考轨迹以实现动态地构建预测模型, 当预测的运动与实际运动不匹配, 可以动态地重新构建新的模型, 因此该方法可以持续地自我修正.
Wang等人[76]提出传统LSTM网络存在的问题, 例如泛化能力差, 错误累积性等. 为了解决这些问题, 提出一种基于Seq2Seq (sequence to sequence)学习的多用户多轨迹预测框架, 基于LSTM编解码器结构来获取轨迹中的信息, 如时间和方向等. 从这些信息可以提取出某些移动行为特征和潜在的地理特征, 再考虑类似自回归模型的训练策略, 将前一步不精确输出作为下一步输入, 这样框架的设计可以更加注重轨迹的全局信息而忽略局部预测误差. Alahi等人[77]提出Social-LSTM模型旨在解决在拥挤环境下的行人轨迹问题, 由于人有与生俱来的判断能力, 当人们走在拥挤环境中, 如车站、机场、购物中心时, 会有意识地避让其他行人, 这得益于人能够根据当前行人的路线判断短时间内他们的未来轨迹, 并调整自己的路线, 这一问题可看作序列生成问题. 同时已有研究也表明, 关于静态情景环境的知识有助于更准确地预测未来行人的轨迹, 结合社会作用的方法, 提出利用在此类问题上性能优越的LSTM模型进行工作. 由于每个人都有不同的运动模式: 他们速度不同, 步态不同等, 因此场景中的每个人都有一个LSTM, 同时在LSTM模型中每一次递归运行之间加入“Social”池化层, 使其学习发生在时间重合的轨迹之间的交互, 同时整合其他行人的隐藏状态, 并作为隐藏状态的一部分向下传递形成Social-LSTM. 如图9所示, 场景中的每个轨迹使用单独的LSTM网络. 然后, LSTM通过“Social”池化层彼此连接. 与传统的LSTM不同, 该池化层允许空间上近邻LSTM彼此共享信息. 此外, 提出O-LSTM模型, 用以对行人的轨迹进行独立训练.
|
Fig. 9 Social-LSTM model 图 9 Social-LSTM模型 |
2.3 启发式算法和滤波算法
启发式算法是为了解决传统的优化算法而出现的, 如线性规划或动态规划等算法在解决大规模优化问题时存在计算代价过大等问题, 于是启发式算法尽可能逼近最优解. 得到相对最优解这种情况在很多实际应用中是可以接受的, 例如如何使用最小的代价遍历指定的几座城市这种路径规划问题. 将启发式算法应用在轨迹预测领域的基本思想为: 当知道了前序轨迹序列和目的地时, 算法根据当前移动对象的位置, 对路线进行全局的预测, 同时结合实时的情景信息, 如交通流量, 天气等信息, 对算法进行优化. 滤波算法以贝叶斯滤波为例[78], 它主要功能在已知可观测值和根据已有条件所计算的估计值这两个值的概率, 如何计算出最终估计值的可信度. 卡尔曼滤波则是提供了贝叶斯滤波的一种实现, 即如何计算观测值和估计值的概率. 并且卡尔曼滤波假设观测值符合正态分布, 同时是线性变化的. He等人[79]提出了一种改进卡尔曼滤波的自适应滤波算法用于平衡车路线规划问题, 是一种在确定终点位置的情况下预测平衡车的路线问题, 该方法在简化Sage-Husa滤波器的基础上采用滤波收敛准则. 通过融合来自多个传感器的数据, 可以在算法中使用更为精确的时空间信息. 此外, 结合强跟踪滤波器的思想, 在系统模型不确定的情况下, 调整系统增益矩阵, 提高滤波器的性能, 增强对突变状态的处理能力. 乔少杰等人[29]提出基于卡尔曼滤波的动态轨迹预测算法, 利用当前时刻的观测值和前一时刻状态下对当前的估计值来更新状态估计, 然后结合下一时刻点的观测值对轨迹位置进行预测. 如: X(k+1, k+1)=X(k+1, k)+K(k+1)[Z(k+1) – Z(k+1, k)]. 其中X(k+1)表示k+1时刻的状态, K(k+1)为k+1时刻的增益矩阵, Z(k)表示观测向量. 由于卡尔曼滤波是通过当前的观测和前一时刻的估计来对下一时刻进行预测, 空间几何误差采用均方根误差RMSE计算, 如公式(5):
| $ {{\textit{RMSE}}=}\frac{{\displaystyle\sum }_{{i}{=1}}^{{k}}\sqrt{{{(}{{x}}_{{i}}{{'}}-{{x}}_{{i}}{)}}^{{2}}+{{(}{{y}}_{{i}}{{'}}-{{y}}_{{i}}{)}}^{{2}}}}{{k}} $ | (5) |
均方根误差公式中( xi, yi )表示实际轨迹点的位置, (
|
|
Table 3 Category comparison of prediction models 表 3 预测模型类别对比 |
2.4 情景感知驱动的多模式轨迹预测技术应用举例
在实际应用方面, 情景感知可以在兴趣点相关的服务中应用, Chen等人[80]提出了一种深度导航(DeNavi)的兴趣点推荐系统, 主要处理轨迹中兴趣点之间间隔时间和间隔距离不规则问题, 提出将序列中连续元素之间的时间和距离的不规则性合并到存储单元中, 以提高标准递归网络的性能. 同时假设经过的时间和距离越大, 先前的存储单元对当前输出的影响就越小. 基于这一假设, 间隔的时间和距离被公式化为适当的权重. 此外, 兴趣点预测不仅基于用户的短期兴趣, 还基于用户的长期兴趣. DeNavi中有3种学习模型: DeNavi-LSTM考虑了基于LSTM的时间和距离感知, 并利用衰减函数对存储单元和隐藏状态进行子空间分解, 根据区间差异对历史信息进行贴现; DeNavi-GRU同样也考虑了时间和距离感知, 并利用衰减函数对隐藏状态进行轻量级学习; DeNavi-Alpha基于LSTM动态地感知间隔时间和距离, 并利用指数加权平均来调整每个情景的重要性. 笔者在社交网络数据集Gowalla和BrightKite上分别完成了实验, 实验标准用准确度ACC@N、查准率P@N、查全率R@N、F指数F@N. 准确度ACC@N即下一个轨迹点的真实值是否在预测值序列当中, N为预测值序列的个数, 依次取值为1, 5, 10, 20. 当真实值在预测值序列中时, 准确度取1, 否则取0. 最后取值为所有测试实例的均值. 查准率即预测正确的序列占所有预测序列数量的比例, 查全率即预测正确的序列占总测试序列数量的比例,F指数即查全率和查准率的综合评判标准. 实验对比了MF (传统的矩阵分解方法通过对现有的用户物品评分进行回归, 学习潜在因素, 准确预测用户签到), RNN (递归神经网络)、LSTM (长短期记忆, 包含遗忘门、输入门、输出门和一个记忆单元的特殊递归神经网络), GRU (门控循环单元, 配备了更新门和复位门的特殊递归神经网络)、ST-RNN (考虑了时空情景的递归神经网络)、STF-RNN、SERM (将基于语义轨迹中的潜在用户意图融入递归神经网络的方法)、Time-LSTM (在LSTM中加入时间门来模拟时间间隔)等方法. 结果表明在准确度方面, RNN由于其强大的序列建模能力, 性能明显优于MF约70%. 其次LSTM和GRU的性能优于RNN, 这是由于这两种方法更适用于对复杂且较长的轨迹序列建模, ST-RNN、SERM和Time-LSTM与标准LSTM和GRU相比略有优化, 这表明考虑时间和距离间隔是性能提高的一个关键因素. 与LSTM相比DeNavi-LSTM的性能大约17%的提高, 而DeNavi-Alpha相比LSTM更有30%的性能提高. 同时在查准率、查全率、F指数的比较当中, DeNavi-Alpha的性能同样最高, 其次是DeNavi-LSTM.
Bartoli等人[81]提出了一种基于情景感知递归神经网络模型的人体轨迹预测新方法. 为了考虑在拥挤环境中人和人以及人和周围物体对于行动产生的影响, 改善了上文所提及的Alahi等人提出的Social-LSTM模型, 并为每个移动对象定义了LSTM网络和一个情景感知池, 允许模型可以考虑只有一个人时附近的静态对象. 提出的模型观察人过去的位置和他与周围环境的相互作用, 以预测他的短期轨迹. 为了模拟人与人之间的相互影响, 在每个时间步长, 将某条轨迹周围相邻人的位置通过一个大小为m×n的网格汇集, 通过指示函数计算占用矩阵, 用于为网格中的每个单元分配相应的轨迹, 这个矩阵可以模拟每个人是否有相邻人. 如图10所示, LSTM的输入由被分析人的轨迹(绿色)、用于人与人汇集的交互网格(红色)和情景感知池(蓝色)来表示. 灰色轨迹表示其他邻近行人, 蓝色虚线连接静态物体, 在整个场景中计算人的移动空间是为了获得更准确的预测, 为此首先识别场景中能够影响人活动的静态物体, 在此研究中手动标记这些点, 例如出入口等来模拟人与空间的互动. 实验中采用真实博物馆中的场景, 在此实验中考虑了不同展品对于不同的游客会展现出带差异性的吸引力, 这会导致行人的运动轨迹发生不可预估的改变, 所以应在模型建立的过程中充分考虑展品的位置, 并且分配有不一样的权重. 实验的数据集通过一个大型艺术博物馆中的4个相机获得, 所记录的数据不仅包括人群还有固定位置的艺术品, 通过不同角度的4个相机, 可以清晰地获得该场景下人群的相互运动. 将部分人的完整轨迹用作模型训练, 同时考虑到大多数人都是结伴观展, 故将人群分组标记, 例如, 一组人一起走, 在一件艺术品前停留一段时间, 表明这组人有一定的社会关联. 实验中观察移动对象前3.2 s的运动轨迹, 然后用训练好的模型预测其后4.8 s的位置信息. 对轨迹进行采样, 以便每10帧保留1帧, 结果以均方误差的形式评判. 对比LSTM、O-LSTM (ordered neurons-LSTM)和S-LSTM (social-LSTM)等模型, 实验结果表明加了情景感知信息的O-LSTM模型性能在模型预测点和真实点之间的均方误差平均值最小.
|
Fig. 10 Application example of social-LSTM trajectory prediction modes with context awareness 图 10 情景感知Social-LSTM轨迹预测应用举例 |
3 相关技术和未来趋势展望
在安全和隐私问题方面, 由于情景感知驱动的服务需要利用大量的敏感信息来描述复杂环境, 需要处理大规模的网络数据[82], 同时随着云计算技术的发展, 情景感知服务逐渐向云化方向发展. 因此, 移动计算的环境更加多变、复杂和隐藏风险. 一般的解决方案是限制未经授权的操作, 保护信息存储的隐私, 确保处理过程中的信息安全, 或者可能创建专用于公共部门的私有云. 具体来说, 安全与隐私的研究应该同时关注终端用户和云. 首先, 对于终端用户信息的保护, 潜在的解决方案可以是实体认证、情景置乱算法、对称密钥加密和公开密钥加密技术; 其次, 对于云数据保护, 数据的准确性是关键. 潜在的解决方案可以是隐私保护数据挖掘、安全多方计算和可验证计算.
异质性和动态是情景感知最突出和重要的特征, 动态追踪的问题目前已经有了很好的解决方案, 然而异质性的问题仍然棘手. 首先, 如何在异构环境中使用多个传感器来捕获有用的情景信息, 从而实现正确的决策; 其次, 随着情景数据量的增大, 需要高性能的数据密集型处理框架, 能够在动态异构环境下实现情景感知调度机制.
服务的准确性和效率方面, 在大数据时代, 由于数据源和数据类型的多样性, 效率和准确性是情景感知系统的重要评估指标. 首先, 实时情景数据处理不完整, 相关研究领域涉及情景数据存储、数据获取、数据访问、并行流计算和信息检索; 其次是情景数据的降维. 情景信息的维数决定了服务的准确性, 然而, 高维数会带来很大的计算复杂性. 如何降低情景维度并保持良好的服务准确性是一个关键问题.
未来研究工作可以重点放在情景感知技术和多模式轨迹预测的深度结合上, 例如: 对解决冷启动问题有帮助的情景获取、情景处理与识别, 抽取高层次环境情景和社会情景信息. 构建包含轨迹点时空维度和社会维度在内的多粒度、多层次轨迹情景语义网络, 设计新型基于局部和全局相似性的层次型轨迹热点区域挖掘算法, 从局部和全局角度综合考量, 发现用户感兴趣的位置点, 使轨迹预测更加有针对性. 与自然语言处理的词嵌入类似, 轨迹中的地点嵌入也可采用相似的方法. 但是不同于文本信息的是, 轨迹中包含有时间维度的信息, 在轨迹中不同地点返回的时间差可以反映出移动对象的访问频率以及停留时间等情景信息; 另一方面, 从长序列的轨迹数据中的时间差来看, 不同类型的地点, 移动对象访问时间的分布也可能不同; 再者, 多功能兴趣点在现实生活中是常见地点, 例如商场会有健身房和餐厅, 访问统一地点可能是为了不同的目的, 未来工作可以考虑将位置信息嵌入为向量表示, 并结合周围实时的情景信息, 这对于实现复杂环境下的轨迹预测具有一定的帮助. 在实际应用上来说, 融合情景感知的轨迹预测技术有极强的现实应用前景. 例如相对极端的交通路况下, 如隧道或高原等信号微弱地点, 普通导航系统无法提供持续可靠的精确的路线, 有情景感知的驾驶辅助系统在此时有巨大帮助. 又如无人机在自动跟随目标的活动中, 当跟随目标被遮挡或周围有多个相似目标, 融合实时情景信息的算法能预测跟随目标的轨迹, 实现精确跟踪定位. 从多角度考虑融合复杂情景信息, 如环境情景、社会关联情景的移动对象的轨迹预测模型, 提高预测的准确性, 应用新型高效的预测算法对不确定轨迹建模、训练, 进而预测具有不同特征和运动轨迹的多模式轨迹.
4 结束语移动对象多模式轨迹预测早已成为热点研究领域, 在当前的大数据时代下, 数据的多样性给研究者提供了不同角度的研究方案, 本文详述了该领域内的不同研究方法, 如数学统计类、机器学习类和滤波算法等. 并综述了当前在该研究领域较为空白的情景感知技术, 介绍了该技术的组成原理、运用方法、技术支撑和应用案例等. 利用情景感知技术, 可以更好地将复杂客观环境因素、个体偏好和关联考虑进来, 减少轨迹预测的不确定性, 提高挖掘的有效性. 情景感知和轨迹数据相辅相成, 使挖掘准确性更高, 挖掘的知识更加有意义. 情景感知技术驱动下对大规模移动对象的复杂多变运动行为进行预测, 可以为轨迹预测领域提供新的思路和方向, 且研究有利于解决社会群体性问题. 研究情景感知计算理论, 对于人类行为分析、普适计算等交叉学科的研究具有重要的科学意义.
致谢 感谢所有参与本课题研究和本文工作没有在文中署名的课题组成员及对本项目提供技术支持的专家和学者; 感谢所有评阅本文的匿名评审人及对本文提出的宝贵修改意见.
| [1] |
Schilit BN, Adams N, Want R. Context-aware computing applications. In: Proc. of the 1st Workshop on Mobile Computing Systems and Applications. Santa Cruz: IEEE, 1994. 85–90.
|
| [2] |
Liu JJ, Zhao K, Sommer P, Shang S, Kusy B, Lee JG, Jurdak R. A novel framework for online amnesic trajectory compression in resource-constrained environments. IEEE Trans. on Knowledge and Data Engineering, 2016, 28(11): 2827-2841.
[doi:10.1109/TKDE.2016.2598171] |
| [3] |
Richter KF, Schmid F, Laube P. Semantic trajectory compression: Representing urban movement in a nutshell. Journal of Spatial Information Science, 2012(4): 3-30.
[doi:10.5311/JOSIS.2012.4.62] |
| [4] |
Brown K, Driggs-Campbell K, Kochenderfer MJ. A taxonomy and review of algorithms for modeling and predicting human driver behavior. arXiv: 2006.08832, 2020.
|
| [5] |
Wu RZ, Luo GC, Shao JM, Tian L, Peng CZ. Location prediction on trajectory data: A review. Big Data Mining and Analytics, 2018, 1(2): 108-127.
[doi:10.26599/BDMA.2018.9020010] |
| [6] |
Zheng Y. Trajectory data mining: An overview. ACM Trans. on Intelligent Systems and Technology, 2015, 6(3): 29.
[doi:10.1145/2743025] |
| [7] |
Lee WC, Krumm J. Trajectory preprocessing. In: Zheng Y, Zhou XF, eds. Computing with Spatial Trajectories. New York: Springer, 2011. 3–33.
|
| [8] |
Muckell J, Hwang JH, Patil V, Lawson CT, Ping F, Ravi SS. SQUISH: An online approach for GPS trajectory. In: Proc. of the 2nd Int’l Conf. on Computing for Geospatial Research & Applications. Washington: ACM, 2011. 1–8.
|
| [9] |
Muckell J, Olsen PW Jr, Hwang JH, Lawson CT, Ravi SS. Compression of trajectory data: A comprehensive evaluation and new approach. GeoInformatica, 2014, 18(3): 435-460.
[doi:10.1007/s10707-013-0184-0] |
| [10] |
Gao Q, Zhang FL, Wang RJ, Zhou F. Trajectory big data: A review of key technologies in data processing. Ruan Jian Xue Bao/Journal of Software, 2017, 28(4): 959–992 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5143.htm
|
| [11] |
Tiwari S, Kaushik S. Popularity estimation of interesting locations from visitor’s trajectories using fuzzy inference system. Open Computer Science, 2016, 6(1): 8-24.
[doi:10.1515/comp-2016-0002] |
| [12] |
Zheng Y, Zhang LZ, Xie X, Ma WY. Mining interesting locations and travel sequences from GPS trajectories. In: Proc. of the 18th Int’l Conf. on World Wide Web. Madrid: ACM, 2009. 791–800.
|
| [13] |
Ying JJC, Lee WC, Weng TC, Tseng VS. Semantic trajectory mining for location prediction. In: Proc. of the 19th ACM SIGSPATIAL Int’l Conf. on Advances in Geographic Information Systems. Chicago: ACM, 2011. 34–43.
|
| [14] |
Li HY, Ge Y, Hong RC, Zhu HS. Point-of-interest recommendations: Learning potential check-ins from friends. In: Proc. of the 22nd ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. San Francisco: ACM, 2016. 975–984.
|
| [15] |
Zheng Y. Location-based social networks: Users. In: Zheng Y, Zhou XF, eds. Computing with Spatial Trajectories. New York: Springer, 2011. 243–276.
|
| [16] |
Barrios C, Himberg H, Motai Y, Sadek A. Multiple model framework of adaptive extended kalman filtering for predicting vehicle location. In: Proc. of the 2006 IEEE Intelligent Transportation Systems Conf. Toronto: IEEE, 2006. 1053–1059.
|
| [17] |
Hightower J, Borriello G. Particle filters for location estimation in ubiquitous computing: A case study. In: Proc. of the 6th Int’l Conf. on Ubiquitous Computing. Nottingham: Springer, 2004. 88–106.
|
| [18] |
Gustafsson F. Particle filter theory and practice with positioning applications. IEEE Aerospace and Electronic Systems Magazine, 2010, 25(7): 53-82.
[doi:10.1109/MAES.2010.5546308] |
| [19] |
Meratnia N, de By RA. Spatiotemporal compression techniques for moving point objects. In: Proc. of the 9th Int’l Conf. on Extending Database Technology. Heraklion: Springer, 2004. 765–782.
|
| [20] |
Wu ST, Marquez MRG. A non-self-intersection douglas-peucker algorithm. In: Proc. of the 16th Brazilian Symp. on Computer Graphics and Image Processing. Sao Carlos: IEEE, 2003. 60–66.
|
| [21] |
Song L, Kotz D, Jain R, He XN. Evaluating location predictors with extensive Wi-Fi mobility data. In: Proc. of the 2004 IEEE INFOCOM. Hong Kong: IEEE, 2004. 1414–1424.
|
| [22] |
Qiao SJ, Shen DY, Wang XT, Han N, Zhu W. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models. IEEE Trans. on Intelligent Transportation Systems, 2015, 16(1): 284-296.
[doi:10.1109/TITS.2014.2331758] |
| [23] |
Wu WT, Jin WZ, Lin PQ. Research on choice of travel mode model based on naive Bayesian method. In: Proc. of the 2011 Int’l Conf. on Business Management and Electronic Information. Guangzhou: IEEE, 2011. 439–444.
|
| [24] |
Hong J, Chun C, Kim SJ, Park FC. Gaussian process trajectory learning and synthesis of individualized gait motions. IEEE Trans. on Neural Systems and Rehabilitation Engineering, 2019, 27(6): 1236-1245.
[doi:doi:10.1109/TNSRE.2019.2914095] |
| [25] |
Zhou ZJ, Chen JL, Shen BB, Xiong ZG, Shen H, Guo FY. A trajectory prediction method based on aircraft motion model and grey theory. In: Proc. of the 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conf. (IMCEC). Xi’an: IEEE, 2016. 1523–1527.
|
| [26] |
Wang M, Fu WJ, He XN, Hao SJ, Wu XD. A survey on large-scale machine learning. IEEE Trans. on Knowledge and Data Engineering, 2020: 1–20.
|
| [27] |
Boubezoul A, Koita A, Daucher D. Vehicle trajectories classification using Support Vectors Machines for failure trajectory prediction. In: Proc. of the 2009 Int’l Conf. on Advances in Computational Tools for Engineering Applications. Beirut: IEEE, 2009. 486–491.
|
| [28] |
Zhou H, Chen YJ, Zhang SM. Ship trajectory prediction based on BP neural network. Journal on Artificial Intelligence, 2019, 1(1): 29-36.
[doi:10.32604/jai.2019.05939] |
| [29] |
Qiao SJ, Han N, Zhu XW, Shu HP, Zheng JL, Yuan CA. A dynamic trajectory prediction algorithm based on Kalman filter. Acta Electronica Sinica, 2018, 46(2): 418-423(in Chinese with English abstract).
[doi:10.3969/j.issn.0372-2112.2018.02.022] |
| [30] |
Boutamina S, Maamri R. A survey on context-aware workflow systems. In: Proc. of the Int’l Conf. on Intelligent Information Processing, Security and Advanced Communication. Batna: ACM, 2015. 92.
|
| [31] |
Shi YC. Context awareness, the spirit of pervasive computing. In: Proc. of the 1st Int’l Symp. on Pervasive Computing and Applications. Urumqi: IEEE, 2006. 6.
|
| [32] |
Liu W, Li X, Huang DL. A survey on context awareness. In: Proc. of the 2011 Int’l Conf. on Computer Science and Service System (CSSS). Nanjing: IEEE, 2011. 144–147.
|
| [33] |
Dey AK. Providing architectural support for building context-aware applications [Ph.D. Thesis]. Atlanta: Georgia Institute of Technology, 2000.
|
| [34] |
Gu JZ. Context aware computing. Journal of East China Normal University (Natural Science), 2009(5): 1-20(in Chinese with English abstract).
[doi:10.3969/j.issn.1000-5641.2009.05.001] |
| [35] |
Xue B, Sun C, Chu HH, Meng QS, Jiao SB. Method of electronic component location, grasping and inserting based on machine vision. In: Proc. of the 2020 Int’l Wireless Communications and Mobile Computing (IWCMC). Limassol: IEEE, 2020. 1968–1971.
|
| [36] |
Qiao SJ, Han N, Zhou JL, Li RH, Jin CQ, Gutierrez LA. SocialMix: A familiarity-based and preference-aware location suggestion approach. Engineering Applications of Artificial Intelligence, 2018, 68: 192-204.
[doi:10.1016/j.engappai.2017.11.006] |
| [37] |
Clinch S, Alexander J, Gehring S. A survey of pervasive displays for information presentation. IEEE Pervasive Computing, 2016, 15(3): 14-22.
[doi:10.1109/MPRV.2016.55] |
| [38] |
Chang EY. Context-aware computing: Opportunities and open issues. Proc. of the VLDB Endowment, 2013, 6(11): 1172-1173.
[doi:10.14778/2536222.2536245] |
| [39] |
Gandodhar PS, Chaware SM. Context aware computing systems: A survey. In: Proc. of the 2nd Int’l Conf. on I-SMAC. Palladam: IEEE, 2018. 605–608.
|
| [40] |
Li X, Eckert M, Martinez JF, Rubio G. Context aware middleware architectures: Survey and challenges. Sensors, 2015, 15(8): 20570-20607.
[doi:10.3390/s150820570] |
| [41] |
Temdee P, Prasad R. Context-aware communication and computing: Applications for smart environment. Cham: Springer, 2018.
|
| [42] |
Wu JH. An ontology-based context awareness approach in autonomous mobile learning. In: Proc. of the 2010 Int’l Conf. on E-business and E-government. Guangzhou: IEEE, 2010. 1755–1759.
|
| [43] |
Liu S, Zhang XY, Sun XD, Yin XH, Tang RC, Jiang QY. Survey on context-aware systems and their applications. In: Proc. of the 9th Int’l Conf. on Electronics Information and Emergency Communication (ICEIEC). Beijing: IEEE, 2019. 234–237.
|
| [44] |
Liu FG, Deng DC, Li P. Dynamic context-aware event recognition based on markov logic networks. Sensors, 2017, 17(3): 491.
[doi:10.3390/s17030491] |
| [45] |
Vrbaski M, Petriu D, Amyot D. Tool support for combined rule-based and goal-based reasoning in Context-Aware systems. In: Proc. of the 20th IEEE Int’l Requirements Engineering Conf. (RE). Chicago: IEEE, 2012. 335–336.
|
| [46] |
Nalepa GJ, Bobek S. Rule-based solution for context-aware reasoning on mobile devices. Computer Science and Information Systems, 2014, 11(1): 171-193.
[doi:10.2298/CSIS130209002N] |
| [47] |
Meng Z, Lu J. A rule-based service customization strategy for smart home context-aware automation. IEEE Trans. on Mobile Computing, 2016, 15(3): 558-571.
[doi:10.1109/TMC.2015.2424427] |
| [48] |
Li PS, Liu AL, Zhou PC. Context reasoning for smart homes using case-based reasoning. In: Proc. of the 18th IEEE Int’l Symp. on Consumer Electronics (ISCE 2014). Jeju: IEEE, 2014. 1–2.
|
| [49] |
Mok J, Min H. Ontology-based context-aware model by applying Bayesian network. In: Proc. of the 12th Int’l Conf. on Fuzzy Systems and Knowledge Discovery (FSKD). Zhangjiajie: IEEE, 2015. 2660–2664.
|
| [50] |
Zhang J, Zhan ST, Ji Y, Zhang P. Reasoning mechanism based on the demspter-shafer evidence theory for pervasive context aware computing application. In: Proc. of the 1st Int’l Conf. on Communications and Networking in China. Beijing: IEEE, 2006. 1–3.
|
| [51] |
Rudenko A, Palmieri L, Herman M, Kitani KM, Gavrila DM, Arras KO. Human motion trajectory prediction: A survey. The Int’l Journal of Robotics Research, 2020, 39(8): 895-935.
[doi:10.1177/0278364920917446] |
| [52] |
Qiao SJ, Han N, Ding ZM, Jing CQ, Sun WW, Shu HP. A multiple-motion-pattern trajectory prediction model for uncertain moving objects. Acta Automatica Sinica, 2018, 44(4): 608-618(in Chinese with English abstract).
[doi:10.16383/j.aas.2017.c160575] |
| [53] |
Xu JQ, Güting RH. A generic data model for moving objects. GeoInformatica, 2013, 17(1): 125-172.
[doi:10.1007/s10707-012-0158-7] |
| [54] |
Roopak KE, Rao KSS, Ritesh S, Chickerur S. Performance comparison of relational database with object database (DB4o). In: Proc. of the 5th Int’l Conf. and Computational Intelligence and Communication Networks. Mathura: IEEE, 2013. 512–515.
|
| [55] |
Alegre U, Augusto JC, Clark T. Engineering context-aware systems and applications: A survey. Journal of Systems and Software, 2016, 117: 55-83.
[doi:10.1016/j.jss.2016.02.010] |
| [56] |
Qiao SJ, Han N, Wang C, Zhu F, Tang CJ. A two-tiered dynamic index structure of moving objects based on constrained networks. Chinese Journal of Computers, 2014, 37(9): 1947-1958(in Chinese with English abstract).
[doi:10.3724/SP.J.1016.2014.01947] |
| [57] |
Yusoff MIM, Mohamed I, Bakar MRA. Hidden Markov models: An insight. In: Proc. of the 6th Int’l Conf. on Information Technology and Multimedia. Putrajaya: IEEE, 2014. 259–264.
|
| [58] |
Qiao SJ, Li TR, Han N, Gao YJ, Yuan CA, Wang XT, Tang CJ. Self-adaptive trajectory prediction model for moving objects in big data environment. Ruan Jian Xue Bao/Journal of Software, 2015, 26(11): 2869–2883 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4889.htm
|
| [59] |
Lim Q, Johari K, Tan UX. Gaussian process auto regression for vehicle center coordinates trajectory prediction. In: Proc. of the 2019 IEEE Region 10 Conf. (TENCON). Kochi: IEEE, 2019. 25–30.
|
| [60] |
Qiao SJ, Jin K, Han N, Tang CJ, Gesang DJ, Gutierrez LA. Trajectory prediction algorithm based on Gaussian mixture model. Ruan Jian Xue Bao/Journal of Software, 2015, 26(5): 1048–1063 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4796.htm
|
| [61] |
Liu P, Kurt A, Özgüner Ü. Trajectory prediction of a lane changing vehicle based on driver behavior estimation and classification. In: Proc. of the 17th Int’l IEEE Conf. on Intelligent Transportation Systems (ITSC). Qingdao: IEEE, 2014. 942–947.
|
| [62] |
Ding ZM, Yang B, Güting RH, Li YG. Network-matched trajectory-based moving-object database: Models and applications. IEEE Trans. on Intelligent Transportation Systems, 2015, 16(4): 1918-1928.
[doi:10.1109/TITS.2014.2383494] |
| [63] |
Qiao SJ, Han N, Zhu W, Gutierrez LA. TraPlan: An effective three-in-one trajectory-prediction model in transportation networks. IEEE Trans. on Intelligent Transportation Systems, 2015, 16(3): 1188-1198.
[doi:10.1109/TITS.2014.2353302] |
| [64] |
Dai J, Yang B, Guo CJ, Ding ZM. Personalized route recommendation using big trajectory data. In: Proc. of the 31st Int’l Conf. on Data Engineering. Seoul: IEEE, 2015. 543–554.
|
| [65] |
Qiao SJ, Han N, Li TR, Li RH, Li BY, Wang XT, Gutierrez LA. Large-scale trajectory prediction model based on prefix projection technique. Ruan Jian Xue Bao/Journal of Software, 2017, 28(11): 3043−3057 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5340.htm
|
| [66] |
Zhang RS, Huang XY, Liu J, Ma L, Han R, Zhao YQ, Yang XH. Image vehicle motion trajectory prediction method under complex environment. Journal of Mechanical Engineering, 2011, 47(2): 16-24(in Chinese with English abstract).
[doi:10.3901/JME.2011.02.016] |
| [67] |
Pan TL, Sumalee A, Zhong RX, Indra-Payoong N. Short-term traffic state prediction based on temporal-spatial correlation. IEEE Trans. on Intelligent Transportation Systems, 2013, 14(3): 1242-1254.
[doi:10.1109/TITS.2013.2258916] |
| [68] |
Valiant LG. A theory of the learnable. Communications of the ACM, 1984, 27(11): 1134-1142.
[doi:10.1145/1968.1972] |
| [69] |
Xue T, Liu Y. Trajectory prediction of a flying object based on hybrid mapping between robot and camera space. In: Proc. of the 2018 IEEE Int’l Conf. on Real-time Computing and Robotics (RCAR). Kandima: IEEE, 2018. 567–572.
|
| [70] |
Fang ZQ, Pan L, Chen L, Du YT, Gao YJ. MDTP: A multi-source deep traffic prediction framework over spatio-temporal trajectory data. Proc. of the VLDB Endowment, 2021, 14(8): 1289-1297.
[doi:10.14778/3457390.3457394] |
| [71] |
Fang LJ, Jiang QH, Shi JP, Zhou BL. TPNet: Trajectory proposal network for motion prediction. In: Proc. of the 2020 IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR). Seattle: IEEE, 2020. 6796–6805.
|
| [72] |
Zhang TM, Gao YJ, Qiu LS, Chen L, Linghu QY, Pu SL. Distributed time-respecting flow graph pattern matching on temporal graphs. World Wide Web, 2020, 23(1): 609-630.
[doi:10.1007/s11280-019-00674-0] |
| [73] |
Sun JH, Jiang QH, Lu CW. Recursive social behavior graph for trajectory prediction. In: Proc. of the 2020 IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR). Seattle: IEEE, 2020. 657–666.
|
| [74] |
de Leege AMP, van Paassen MM, Mulder M. A machine learning approach to trajectory prediction. In: Proc. of the AIAA Guidance, Navigation, and Control (GNC) Conf. Boston: AIAA, 2013.
|
| [75] |
Zhou JB, Tung AKH, Wu W, Ng WS. A “semi-lazy” approach to probabilistic path prediction in dynamic environments. In: Proc. of the 19th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Chicago: ACM, 2013. 748–756.
|
| [76] |
Wang CJ, Ma L, Li RP, Durrani TS, Zhang HG. Exploring trajectory prediction through machine learning methods. IEEE Access, 2019, 7: 101441-101452.
[doi:10.1109/ACCESS.2019.2929430] |
| [77] |
Alahi A, Goel K, Ramanathan V, Robicquet A, Li FF, Savarese S. Social LSTM: Human trajectory prediction in crowded spaces. In: Proc. of the 2016 IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). Las Vegas: IEEE, 2016. 961–971.
|
| [78] |
Banerjee P, Corbetta M. In-time UAV flight-trajectory estimation and tracking using bayesian filters. In: Proc. of the 2020 IEEE Aerospace Conf. Big Sky: IEEE, 2020. 1–9.
|
| [79] |
He QS, Wei C, Xu YZ. An improved adaptive Kalman filtering algorithm for balancing vehicle. In: Proc. of the 2017 Chinese Automation Congress (CAC). Jinan: IEEE, 2017. 5721–5725.
|
| [80] |
Chen YC, Thaipisutikul T, Shih TK. A learning-based POI recommendation with spatiotemporal context awareness. IEEE Trans. on Cybernetics, 2020, 1(1): 1-14.
[doi:10.1109/TCYB.2020.3000733] |
| [81] |
Bartoli F, Lisanti G, Ballan L, Del Bimbo A. Context-aware trajectory prediction. In: Proc. of the 24th Int’l Conf. on Pattern Recognition (ICPR). Beijing: IEEE, 2018. 1941–1946.
|
| [82] |
Qiao SJ, Han N, Gao YJ, Li RH, Huang JB, Guo J, Gutierrez LA, Wu XD. A fast parallel community discovery model on complex networks through approximate optimization. IEEE Trans. on Knowledge and Data Engineering, 2018, 30(9): 1638-1651.
[doi:10.1109/TKDE.2018.2803818] |
| [10] |
高强, 张凤荔, 王瑞锦, 周帆. 轨迹大数据: 数据处理关键技术研究综述. 软件学报, 2017, 28(4): 959–992. http://www.jos.org.cn/1000-9825/5143.htm
|
| [29] |
乔少杰, 韩楠, 朱新文, 舒红平, 郑皎凌, 元昌安. 基于卡尔曼滤波的动态轨迹预测算法. 电子学报, 2018, 46(2): 418-423.
[doi:10.3969/j.issn.0372-2112.2018.02.022] |
| [34] |
顾君忠. 情景感知计算. 华东师范大学学报(自然科学版), 2009(5): 1-20.
[doi:10.3969/j.issn.1000-5641.2009.05.001] |
| [52] |
乔少杰, 韩楠, 丁治明, 金澈清, 孙未未, 舒红平. 多模式移动对象不确定性轨迹预测模型. 自动化学报, 2018, 44(4): 608-618.
[doi:10.16383/j.aas.2017.c160575] |
| [56] |
乔少杰, 韩楠, 王超, 祝峰, 唐常杰. 基于路网的移动对象动态双层索引结构. 计算机学报, 2014, 37(9): 1947-1958.
[doi:10.3724/SP.J.1016.2014.01947] |
| [58] |
乔少杰, 李天瑞, 韩楠, 高云君, 元昌安, 王晓腾, 唐常杰. 大数据环境下移动对象自适应轨迹预测模型. 软件学报, 2015, 26(11): 2869–2883. http://www.jos.org.cn/1000-9825/4889.htm
|
| [60] |
乔少杰, 金琨, 韩楠, 唐常杰, 格桑多吉, Gutierrez LA. 一种基于高斯混合模型的轨迹预测算法. 软件学报, 2015, 26(5): 1048–1063. http://www.jos.org.cn/1000-9825/4796.htm
|
| [65] |
乔少杰, 韩楠, 李天瑞, 李荣华, 李斌勇, 王晓腾, Gutierrez LA. 基于前缀投影技术的大规模轨迹预测模型. 软件学报, 2017, 28(11): 3043–3057. http://www.jos.org.cn/1000-9825/5340.htm
|
| [66] |
张润生, 黄小云, 刘晶, 马雷, 韩睿, 赵玉勤, 杨新红. 基于视觉复杂环境下车辆行驶轨迹预测方法. 机械工程学报, 2011, 47(2): 16-24.
[doi:10.3901/JME.2011.02.016] |