2019, Volume 5, Issue 2
Engineering >> 2019, Volume 5, Issue 2 doi: 10.1016/j.eng.2018.11.032
A Flexible Multi-Layer Map Model Designed for Lane-Level Route Planning in Autonomous Vehicles
State Key Laboratory of Automotive Safety and Energy, Department of Automotive Engineering & Collaborative Innovation Center of Intelligent New Energy Vehicles, Tsinghua University, Beijing 100084, China
Next Previous
Abstract
An increasing number of drivers are relying on digital map navigation systems in vehicles or mobile phones to select optimal driving routes in order to save time and improve safety. In the near future, digital map navigation systems are expected to play more important roles in transportation systems. In order to extend current navigation systems to more applications, two fundamental problems must be resolved: the lane-level map model and lane-level route planning. This study proposes solutions to both problems. The current limitation of the lane-level map model is not its accuracy but its flexibility; this study proposes a novel seven-layer map structure, called as Tsinghua map model, which is able to support autonomous driving in a flexible and efficient way. For lane-level route planning, we propose a hierarchical route-searching algorithm to accelerate the planning process, even in the presence of complicated lane networks. In addition, we model the travel costs allocated for lane-level road networks by analyzing vehicle maneuvers in traversing lanes, changing lanes, and turning at intersections. Tests were performed on both a grid network and a real lane-level road network to demonstrate the validity and efficiency of the proposed algorithm.
Keywords
Lane-level ; Route planning ; Tsinghua map model ; Travel cost model
Figures
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
References
[ 1 ] Skog I, Handel P. In-car positioning and navigation technologies—a survey. IEEE Trans Intell Transp Syst 2009;10(1):4–21. link1
[ 2 ] Lecce VD, Amato A. Route planning and user interface for an advanced intelligent transport system. Iet Intell Transp Syst 2011;5:149–58. link1
[ 3 ] Schultes D. Route planning in road networks. Saarbrücken: VDM Verlag; 2008. link1
[ 4 ] Ress C, Balzer D, Bracht A, Löwenau J. Adasis protocol for advanced in-vehicle applications. Meas Sci Rev 2008;11(5):154–9. link1
[ 5 ] Durekovic S, Smith N. Architectures of map-supported ADAS. In: Proceedings of the 2011 IEEE Intelligent Vehicles Symposium (IV); 2011 Jun 5–9; BadenBaden, Germany. New York: IEEE; 2011. p. 207–11. link1
[ 6 ] Bohren J, Foote T, Keller J, Kushleyev A, Lee D, Stewart A, et al. Little Ben: the Ben Franklin Racing Team’s entry in the 2007 DARPA Urban Challenge. J F Robot 2008;25(9):598–614. link1
[ 7 ] Wei J, Snider JM, Gu T, Dolan JM, Litkouhi B. A behavioral planning framework for autonomous driving. In: Proceedings of Intelligent Vehicle Symposium; 2014 Jul 8–11; Dearborn, MI, USA. New York: IEEE; 2014. p. 458–64. link1
[ 8 ] Zhang J, Singh S. LOAM: LiDAR odometry and mapping in real-time. In: Proceedings of the Robotics: Science and Systems Conference; 2014 Jul 12–16; Berkeley, CA, USA; 2014.
[ 9 ] Joshi A, James MR. Generation of accurate lane-level maps from coarse prior maps and LiDAR. IEEE Intell Transp Syst Mag 2015;7(1):19–29. link1
[10] Chen A, Ramanandan A, Farrell JA. High-precision lane-level road map building for vehicle navigation. In: Proceedings of the IEEE/ION Position, Location and Navigation Symposium; 2010 May 4–6; Indian Wells, CA, USA. New York: IEEE; 2010. p. 1035–42. link1
[11] Vu A, Ramanandan A, Chen A, Farrell JA, Barth M. Real-time computer vision/ DGPS-aided inertial navigation system for lane-level vehicle navigation. IEEE Trans Intell Transp Syst 2012;13(2):899–913. link1
[12] Crash Avoidance Metrics Partnership. Enhanced digital mapping project final report. Report. Washington: United States Department of Transportation, Federal Highway Administration and National Highway Traffic and Safety Administration; 2004.
[13] Betaille D, Toledo-Moreo R. Creating enhanced maps for lane-level vehicle navigation. IEEE Trans Intell Transp Syst 2010;11:786–98. link1
[14] Schindler A, Maier G, Janda F. Generation of high precision digital maps using circular arc splines. In: Proceedings of the 2012 IEEE Intelligent Vehicles Symposium; 2012 Jun 3–7; Alcala de Henares, Spain. New York: IEEE; 2012. p. 245–51. link1
[15] Liu J, Cai B, Wang Y, Wang J. Generating enhanced intersection maps for lane level vehicle positioning based applications. Procedia Soc Behav Sci 2013;96:2395–403. link1
[16] Guo C, Meguro J, Kojima Y, Naito T. Automatic lane-level map generation for advanced driver assistance systems using low-cost sensors. In: Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA); 2014 May 31–Jun 7; Hong Kong, China. New York: IEEE; 2014. p. 75–82. link1
[17] Zeng W, Church RL. Finding shortest paths on real road networks: the case for A*. Int J Geogr Inf Sci 2009;23(4):531–43. link1
[18] Delling D, Sanders P, Schultes D, Wagner D. Engineering route planning algorithms. In: Lerner J, Wagner D, Zweig KA, editors. Algorithmics of large and complex networks. Berlin: Springer; 2009. p. 117–39. link1
[19] Zhu Q, Li Y. Hierarchical lane-oriented 3D road-network model. Int J Geogr Inf Sci 2008;22(5):479–505. link1
[20] OpenDRIVE v1.4 format specification. Report. Bad Aibling: VIRES Simulationstechnologie GmbH; 2015 Nov. Report No.: VI2014.106.
[21] Martin Schleicher. NDS association: right in time—a standardized system is the key for the future autonomous drive. In: Proceedings of the Electronics in Vehicles 2015, 17th International Congress; 2015 Oct 14; Baden, Germany; 2015.
[22] Zhang T, Yang D, Li T, Li K, Lian X. An improved virtual intersection model for vehicle navigation at intersections. Transp Res Part C 2011;19(3):413–23. link1
[23] Volker L. Route planning in road networks with turn costs. Interpret A J Bible Theol 2008:1–30. link1
[24] Zhang T, Arrigoni S, Garozzo M, Yang D, Cheli F. A lane-level road network model with global continuity. Transp Res Part C Emerg Technol 2016;71:32–50. link1
[25] Fu L, Sun D, Rilett LR. Heuristic shortest path algorithms for transportation applications: state of the art. Comput Oper Res 2006;33:3324–43. link1
[26] Zhang X, Wang Q, Adamatzky A, Chan FTS, Mahadevan S, Deng Y. A Biologically inspired optimization algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. J Optim Theory Appl 2014;163:1049–56. link1
[27] Geisberger R, Sandersn P, Schultes D, Delling D. Contraction hierachies: faster and simpler hierachical routing in road networks. In: MeGeoch CC, editor. WEA 2008: experimental algorithms. Heidelberg: Springer; 2008. p. 319–33. link1
京公网安备 11010502051620号
