车辆导航系统中基于街区分块的分层路网路径规划

摘要/Abstract

摘要：

当前车辆导航系统多采用分层分块的方法提高路径规划速度，传统路网分块方法将路网经纬度形成的网格作为路网分块边界，由于路网在不同地域分布不均匀，不同网格中数据量相差较大，从而影响数据使用效率。提出了一种基于街区分块的路径规划方法，针对街区特性自适应调整路网分块中数据量的大小，利用距离、面积及邻接块来控制路网拓展等级和范围，减小了拓展区域。最后利用基于道路等级的路网分层方法实现了局域路网和广域路网的路径规划。实验表明，基于街区分块方法的分层路网进行路径规划，其规划性能可以满足嵌入式系统高效路径规划的需求。

关键词: 车辆导航, 街区分块, 分层路网, 路径规划, 嵌入式系统

Abstract:

At present, the hierarchical block methodology was commonly adopted to improve the speed of the path planning in vehicle navigation system. The traditional roadnet was blocked by the latitude and longitude. However, the roatnet was not uniformly distributed in different areas and the datasets will vary largely for different blocks, thus the datasets will be not fully utilized. Herein, a path planning methodology based on community block was adopted, which can adaptively adjust the datasets in the roadnet blocks according to the community status. Furthermore, the topo scope and level of roadnet were controlled by the distance and area as well as adjacent block. Finally, the path planning for local network and large scale network was realised through the roadnet block method based on different road grades. The test results show that the capacity of the path planning using the hierarchical roadnet based on community block can meet the high efficiency requirements of the embedded system.

Key words: vehicle navigation, community block, hierarchical roadnet, path planning, embedded system

中图分类号:

张照生, 杨殿阁, 张德鑫, 连小珉. 车辆导航系统中基于街区分块的分层路网路径规划[J]. 中国机械工程, 2013, 24(23): 3255-3260.

Zhang Zhaosheng, Yang Diange, Zhang Dexin, Lian Xiaomin. Hierarchical Path Planning Development Based on Community Block in Vehicle Navigation[J]. China Mechanical Engineering, 2013, 24(23): 3255-3260.

参考文献

[1]Zhang Tao, Yang Diange, Li Ting, et al. An Improved Virtual Intersection Model for Vehicle Navigation at Intersections[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(3): 413-423.
[2]Wang Tanbin, Chen Wuwei, Jiao Jun, et al. Study on Navigation of Intelligent Vehicles Based on Multi-sensor Fusion[J]. China Mechanical Engineering, 2009, 20(11): 1381-1385.
[3]Li Xu, Zhang Weigong. Research on Multi-sensor Integrated Navigation Technique Based on Federated Filter for Intelligent Vehicle[J]. China Mechanical Engineering, 2008, 19(12): 1446-1451.
[4]李挺. 乍辆自主导航的广域蛛式地图与点状路网跨层路径规划[D]. 北京: 清华人学, 2008.
[5]正义玺, 肖世德, 盂祥印, 等. 模糊神经网络下基于强化学习的自主式地面车辆路径规划研究[J]. 中国机械工程, 2009, 20(21): 2536-2541.
[6]Dijkstra E W. A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematik, 1959, 1: 269-271.
[7]Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transportation System Science and Cybernetics, 1968, 4(2) : 100-107.
[8]Hart P E, Nilsson N J, Raphael B. Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"[J]. ACM SIGART Bulletin, 1972, 37: 28-29.
[9]李清泉, 郑年波, 徐敬海, 等.一种基于道路网络层次拓扑结构的分层路径规划算法[J]. 中国图象图形学报, 2007, 12(7): 1280-1285.
[10]颜波. 车载自主导航系统中的动态最优路径规划[D]. 北京: 清华大学, 2004.
[11]Jagadeesh G R, Srikanthan T, Quek K H . Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2002, 3(4): 301-309.
[12]Geisberger R, Sanders P, Sehultes D, et al. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks[J]. Lecture Notes in Computer Science, 2008, 5038 : 319-333.
[13]Rajagopalan R, Mehrotra K, Mohan C, et al. Hierarchical Path Computation Approach for Large Graphs[J]. IEEE Transaction on Aerospace and Electronic Systems, 2008, 44(2): 427-440.
[14]郑烟武. 基于分层分区的动态路径规划算法研究[D]. 广州: 华南理工大学, 2011.
[15]Song Qing, Wang Xiaofan. Efficient Routing on Large Road Networks Using HierarchicalCommunities[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(1): 132-140.
[16]张静. 面向路径规划的导航路网数据模型研究[D]. 北京:中国矿业大学（北京）,2009.