A Flexible Multi-Layer Map Model Designed for Lane-Level Route Planning in Autonomous Vehicles

Kun Jiang; Diange Yang; Chaoran Liu; Tao Zhang; Zhongyang Xiao

doi:10.1016/j.eng.2018.11.032

PDF(4153 KB)

Engineering ›› 2019, Vol. 5 ›› Issue (2) : 305-318. DOI: 10.1016/j.eng.2018.11.032

Research

Research Intelligent Transportation—Article

A Flexible Multi-Layer Map Model Designed for Lane-Level Route Planning in Autonomous Vehicles

Author information +

History +

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

Cite this article

EndNote

Ris (Procite)

Bibtex

Download citation ▾

Kun Jiang, Diange Yang, Chaoran Liu, Tao Zhang, Zhongyang Xiao. A Flexible Multi-Layer Map Model Designed for Lane-Level Route Planning in Autonomous Vehicles. Engineering, 2019, 5(2): 305‒318 https://doi.org/10.1016/j.eng.2018.11.032

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Skog I., Handel P.. In-car positioning and navigation technologies—a survey. IEEE Trans Intell Transp Syst. 2009; 10(1): 4-21.

[2]	Lecce V.D., Amato A.. Route planning and user interface for an advanced intelligent transport system. Iet Intell Transp Syst. 2011; 5: 149-158.

[3]	Schultes D.. Route planning in road networks.

[4]	Ress C., Balzer D., Bracht A., Löwenau J.. Adasis protocol for advanced in-vehicle applications. Meas Sci Rev. 2008; 11(5): 154-159.

[5]	Durekovic S., Smith N.. Architectures of map-supported ADAS. In: Proceedings of the 2011 IEEE Intelligent Vehicles Symposium (IV); 2011 Jun 5–9; Baden-Baden, Germany. New York: IEEE; 2011. p. 207-211.

[6]	Bohren J., Foote T., Keller J., Kushleyev A., Lee D., Stewart A., . Little Ben: the Ben Franklin Racing Team’s entry in the 2007 DARPA Urban Challenge. J F Robot. 2008; 25(9): 598-614.

[7]	Wei J., Snider J.M., Gu T., Dolan J.M., 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-464.

[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 M.R.. Generation of accurate lane-level maps from coarse prior maps and LiDAR. IEEE Intell Transp Syst Mag. 2015; 7(1): 19-29.

[10]	Chen A., Ramanandan A., Farrell J.A.. 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-1042.

[11]	Vu A., Ramanandan A., Chen A., Farrell J.A., 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.

[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-798.

[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-251.

[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-2403.

[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.

[17]	Zeng W., Church R.L.. Finding shortest paths on real road networks: the case for A*. Int J Geogr Inf Sci. 2009; 23(4): 531-543.

[18]	Delling D., Sanders P., Schultes D., Wagner D.. Engineering route planning algorithms. In: editor. Algorithmics of large and complex networks. Berlin: Springer; 2009. p. 117-139.

[19]	Zhu Q., Li Y.. Hierarchical lane-oriented 3D road-network model. Int J Geogr Inf Sci. 2008; 22(5): 479-505.

[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-423.

[23]	Volker L.. Route planning in road networks with turn costs. Interpret A J Bible Theol. 2008; 1-30.

[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.

[25]	Fu L., Sun D., Rilett L.R.. Heuristic shortest path algorithms for transportation applications: state of the art. Comput Oper Res. 2006; 33: 3324-3343.

[26]	Zhang X., Wang Q., Adamatzky A., Chan F.T.S., 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-1056.

[27]	Geisberger R., Sandersn P., Schultes D., Delling D.. Contraction hierachies: faster and simpler hierachical routing in road networks. In: editor. WEA 2008: experimental algorithms. Heidelberg: Springer; 2008. p. 319-333.

Acknowledgements

This work was supported in part by the National Key Research and Development Program of China (2018YFB0105000), in part by the National Natural Science Foundation of China (61773234 and U1864203), in part by the Project of Tsinghua University and Toyota Joint Research Center for AI Technology of Automated Vehicle (TT2018-02), in part by the International Science and Technology Cooperation Program of China (2016YFE0102200). This work is also supported by the software developed in the Beijing Municipal Science and Technology Program (D171100005117001 and Z181100005918001).

Compliance with ethics guidelines

Kun Jiang, Diange Yang, Chaoran Liu, Tao Zhang, and Zhongyang Xiao declare that they have no conflict of interest or financial conflicts to disclose.