计算机科学 ›› 2018, Vol. 45 ›› Issue (6A): 130-134.

• 智能计算 • 上一篇    下一篇

复杂障碍空间中基于移动对象运动规律的不确定轨迹预测

宫海彦1,耿生玲1,2   

  1. 青海师范大学计算机学院 西宁8100081
    青海师范大学物联网省级重点实验室 西宁8100082
  • 出版日期:2018-06-20 发布日期:2018-08-03
  • 作者简介:宫海彦(1993-),女,硕士,CCF会员,主要研究方向为智能控制与优化、决策方法和决策支持系统;耿生玲(1970-),女,博士,教授,CCF会员,主要研究方向为计算理论、数据挖掘、控制与决策,E-mail:geng_sl@126.com(通信作者)。
  • 基金资助:
    国家自然科学基金项目(61261047,61403290),国家社科项目(15XMZ057),青海省自然基金项目(2014-ZJ-908,2016-ZJ-920Q),青海省重大研发项目(2016-SF-130),青海省物联网重点实验室建设专项(2017-ZJ-Y21)资助。

Prediction of Uncertain Trajectory Based on Moving Object Motion in Complex Obstacle Space

GONG Hai-yan1,GENG Sheng-ling1,2   

  1. School of Computer,Qinghai Normal University,Xining 810008,China1
    Key Laboratory of IoT of Qinghai Province,Qinghai Normal University,Xining 810008,China2
  • Online:2018-06-20 Published:2018-08-03

摘要: 现有移动对象的轨迹预测大部分是针对路网空间,然而在实际地理环境中往往存在障碍物,移动对象的运动基本在障碍空间中进行。近年来,已有较多关于路网空间中移动对象轨迹预测的研究以及障碍空间中障碍范围查询、最近邻查询等的研究,但是目前尚没有障碍空间中移动对象不确定轨迹预测的相关研究。为此,提出障碍空间中基于移动对象运动规律的不确定轨迹预测方法。首先,利用障碍物之间的区域关系对障碍空间进行剪枝;其次,提出障碍空间期望距离概念,对障碍空间的轨迹数据进行轨迹聚类,从而挖掘移动对象的热点区域;然后,根据各热点区域间的障碍距离和历史访问习惯得到转移的综合概率,提出基于移动对象运动规律的轨迹预测算法;最后,通过实验验证了算法的准确性和高效性。

关键词: 不确定轨迹预测, 移动对象, 运动规律, 障碍空间

Abstract: Most of the existing moving objects trajectory prediction is in the road network space,however,in the actual geographical environment,there exists obstacles,the movement of moving objects is basically carried out in the obstacle space.In recent years,there have been many studies on moving object trajectory prediction in road network space,such as obstacle range query,nearest neighbor query and so on.However,there is no research on the uncertain trajectory prediction of moving objects in obstacle space.For this reason,this paper proposed an uncertain trajectory prediction algorithm based on moving object motion in obstacle space.Firstly ,the obstacle space was pruned by using the regional relation among obstacles.Secondly,the concept of obstacle space expectation distance was proposed,and the trajectory data of obstacle space is clustered,thereby excavating the moving object hot spot region.Next,according to the obstacle distance and the historical visiting habit of each hotspot region,a Markov trajectory prediction algorithm based on the motion law was proposed.Finally,the accuracy and efficiency of the algorithm were verified by experiments.

Key words: Moving object, Obstacle space, Pattern of motion, Uncertain trajectory prediction

中图分类号: 

  • TP311.131
[1]ZHOU Y C,ZHANG Y,GE Y,et al.An efficient data proces- sing framework for mining the massive trajectory of moving objects [J].Computers Environment & Urban Systems,2015,61:129-140.
[2]MAMOULIS N,CAO H P,KOLLIOS G,et al.Mining,inde- xing,and querying historical spatiotemporal data[C]∥Tenth ACM Sigkdd International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2004:236-245.
[3]CHEN L,LV M Q,CHEN G C.A system for destination and future route prediction based on trajectory mining[J].Pervasive and Mobile Computing,2010,6(6):657-676.
[4]ASHBROOK D,STARNER T.Using GPS to learn significant locations and predict movement across multiple users[J].Personal and Ubiquitous Computing,2003(7):275-286.
[5]KIM S W,WON J I,KIM J D,et al.Path prediction of moving objects on road networks through analyzing past trajectories[C]∥Proc.of the 11ndInt’l Conf.on Knowledge-Based Intelligent Information and Engineering Systems.Berlin:Springer-Verlag,2007:379-389.
[6]DING Z M,ZHOU X.Location update strategies for network-constrained moving objects[C]∥13nd International Conference on Database Systems for Advanced Applications.Berlin:Sprin-ger-Verlag,2008:644-652.
[7]SONG M B,RYU J H,LEE S K,et al.Considering mobility patterns in moving objects database[C]∥The 2003 International Conference on Parallel Processing.Washington:IEEE,2003:597-604.
[8]QIAO S,SHEN D Y,WANG X T,et al.A self-adaptive parameter selection trajectory prediction approachvia hidden Markov models[J].IEEE Trans.on Intelligent Transportation Systems,2015,16(1):284-296.
[9]QIAO S J,JIN K,HAN N,et al.Trajectory prediction algorithm based on Gaussian mixture model[J].Journal of Software,2015,26(5):1040-1063.
[10]GAO Y J,ZHENG B H.Continuous obstructed nearest neighbor queries in spatial databases[C]∥Proc.of the SIGMOD Providence on Management of Data.RhodeIsland,USA,2009:577-590.
[11]GAO Y J,ZHENG B H,CHEN G C,et al.Visible reverse k-nearest neighbor query processing in spatial databases[J].IEEE Trans.on Knowledge and Data Engineering,2009,21(9):1314-1327.
[12]LIU Q,DENG M,SHI Y.Adaptive spatial clustering in the presence of obstacles and facilitators[J].Computers &Geoscie-nces,2013,56:104-118.
[13]曹科研,王国仁,韩东红,等.障碍空间中不确定数据聚类算法[J].计算机科学与探索,2012,6(12):1087-1097.
[14]李实吉,秦小麟,施竣严.障碍空间中的移动对象位置预测[J].计算机科学,2014,41(7):216-221.
[15]乔少杰,彭京,李天瑞,等.基于CTBN的移动对象不确定轨迹预测算法[J].电子科技大学学报(自然科学版),2012,41(5):759-763.
[16]LI S J.A layered graph representation for complex regions[C]∥12nd International Conference on the Principles of Knowledge Representation and Reasoning.2010:581-583.
[17]http://en.wikipedia.org/wiki/Markov_model.
[1] 李冰荣, 皮德常, 候梦如.
基于CNN和LSTM的移动对象目的地预测
Destination Prediction of Moving Objects Based on Convolutional Neural Networks and Long-Short Term Memory
计算机科学, 2021, 48(4): 70-77. https://doi.org/10.11896/jsjkx.200200024
[2] 韩京宇, 许梦婕, 朱曼.
路网上基于时空锚点的移动对象群体和个体运动监测方法
Detecting Group-and-individual Movements of Moving Objects Based on Spatial-Temporal Anchors of Road-network
计算机科学, 2020, 47(11): 294-303. https://doi.org/10.11896/jsjkx.191100083
[3] 张彤,秦小麟.
时间依赖路网上的移动对象K近邻查询算法
K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks
计算机科学, 2020, 47(1): 79-86. https://doi.org/10.11896/jsjkx.181102231
[4] 张怀峰, 皮德常, 董玉兰.
iBTC:一种基于独立森林的移动对象轨迹聚类算法
iBTC:A Trajectory Clustering Algorithm Based on Isolation Forest
计算机科学, 2019, 46(1): 251-259. https://doi.org/10.11896/j.issn.1002-137X.2019.01.039
[5] 王波涛,梁伟,赵凯利,钟汉辉,张玉圻.
基于HBase的支持频繁更新与多用户并发的R树
R-tree for Frequent Updates and Multi-user Concurrent Accesses Based on HBase
计算机科学, 2018, 45(7): 42-52. https://doi.org/10.11896/j.issn.1002-137X.2018.07.007
[6] 董天阳, 尚跃辉, 程强.
方向感知的路网移动对象范围查询算法
Direction-aware Moving Object Range Query Algorithm in Road Network
计算机科学, 2018, 45(11): 210-219. https://doi.org/10.11896/j.issn.1002-137X.2018.11.033
[7] 刘凯洋.
AP-I:一种快速预测路网中移动对象未来位置的索引
AP-I:An Index to Quickly Answer Predictive Queries for Moving Objects
计算机科学, 2017, 44(Z6): 314-318. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.072
[8] 薛忠斌,白利光,何宁,周烜,周歆,王珊.
路网中高吞吐量移动对象实时查询算法
Throughput Oriented Real-time Query Processing Algorithm for Moving Objects in Road Network
计算机科学, 2017, 44(3): 16-19. https://doi.org/10.11896/j.issn.1002-137X.2017.03.004
[9] 周翔宇,程春玲,杨雁莹.
基于分布式内存数据库的移动对象全时态索引
Full-temporal Index of Moving Objects Based on Distributed Main Memory Database
计算机科学, 2016, 43(7): 203-207. https://doi.org/10.11896/j.issn.1002-137X.2016.07.037
[10] 张丽平,经海东,李松,崔环宇.
障碍空间中基于Voronoi图的k最近邻查询
k Nearest Neighbor Query Based on Voronoi Diagram for Obstructed Spaces
计算机科学, 2016, 43(5): 174-178. https://doi.org/10.11896/j.issn.1002-137X.2016.05.032
[11] 易显天,徐 展,张 可,郭承军.
一种基于受限网络的移动对象索引结构
Index Structure for Moving Objects Based on Restricted Network
计算机科学, 2015, 42(5): 211-214. https://doi.org/10.11896/j.issn.1002-137X.2015.05.042
[12] 贲婷婷,秦小麟,王 丽.
基于语义和访问权限的室内移动对象索引
Index of Indoor Moving Objects Based on Semantics and Access Permission
计算机科学, 2015, 42(3): 178-184. https://doi.org/10.11896/j.issn.1002-137X.2015.03.037
[13] 李实吉,秦小麟,施竣严.
障碍空间中的移动对象位置预测
Location Prediction of Moving Objects in Obstructed Space
计算机科学, 2014, 41(7): 216-221. https://doi.org/10.11896/j.issn.1002-137X.2014.07.045
[14] 汤志俊,樊明锁,何贤芒,陈华辉,董一鸿.
位置不确定移动对象的连续概率反Skyline查询
Continuous Probabilistic Reverse Skyline Query on Moving Objects with Uncertainty
计算机科学, 2013, 40(7): 147-152.
[15] 成莎莎,蒋夏军,皮德常.
基于动态距离的近邻查询算法研究
Research on Nearest Neighbor Query Based on Temporal Distance
计算机科学, 2012, 39(Z11): 149-153.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!