一种适用于自动驾驶汽车的多层地图模型和车道级轨迹规划
|
摘要
越来越多的司机依赖于汽车或手机上的电子地图导航系统来选择最佳的驾驶路线,以节省时间和提高安全性,在不久的将来,电子地图和导航系统有望在未来交通运输系统中发挥更大的作用。为了将现有的导航系统扩展到更多的应用领域,如自动驾驶,需要考虑在传统道路地图模型的基础上,建立车道级地图模型和车道级轨迹规划。本研究针对传统电子地图内容不够丰富的局限性,提出了一种全新的七层自动驾驶地图结构模型,并将它命名为清华地图模型。考虑车辆换道、转向和直行等不同行车特点,建立了车道级路段行车代价模型,建立一种分层路径轨迹搜索方法,能够在道路和车道网络中实现快速的轨迹规划,能够很好地支持自动驾驶的车道级轨迹规划。通过在虚拟道路网络和实际道路网络上的测试,充分验证了该地图模型和算法的灵活性和有效性。
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.
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.
引文
[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 VD,Amato A.Route planning and user interface for an advanced intelligent transport system.Iet Intell Transp Syst 2011;5:149-58.
[3]Schultes D.Route planning in road networks.Saarbrücken:VDM Verlag;2008.
[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.
[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.
[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 FRobot 2008;25(9):598-614.
[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.
[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.
[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.
[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.IEEETrans 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-98.
[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.
[15]Liu J,Cai B,Wang Y,Wang J.Generating enhanced intersection maps for lane level vehicle positioning based applications.Procedia Soc Behav Sci2013;96:2395-403.
[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 RL.Finding shortest paths on real road networks:the case for A*.Int J Geogr Inf Sci 2009;23(4):531-43.
[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.
[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:VIRESSimulationstechnologie 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.
[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 Technol2016;71:32-50.
[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.
[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.
[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.
[2]Lecce VD,Amato A.Route planning and user interface for an advanced intelligent transport system.Iet Intell Transp Syst 2011;5:149-58.
[3]Schultes D.Route planning in road networks.Saarbrücken:VDM Verlag;2008.
[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.
[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.
[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 FRobot 2008;25(9):598-614.
[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.
[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.
[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.
[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.IEEETrans 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-98.
[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.
[15]Liu J,Cai B,Wang Y,Wang J.Generating enhanced intersection maps for lane level vehicle positioning based applications.Procedia Soc Behav Sci2013;96:2395-403.
[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 RL.Finding shortest paths on real road networks:the case for A*.Int J Geogr Inf Sci 2009;23(4):531-43.
[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.
[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:VIRESSimulationstechnologie 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.
[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 Technol2016;71:32-50.
[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.
[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.
[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.