导航系统中路径规划的研究
|
摘要
车辆自主导航系统是智能交通系统的重要组成部分,先进的车辆自导航系统结合了全球定位技术,地理信息系统技术和现代计算机技术,从而实现了车辆的自主定位、自主导航,使车辆能够在陌生的地形环境中顺利地通行,极大提高了车辆的运行效率和安全,使驾驶员能够准确及时地控制车辆到达预定的目的地。
自主导航系统一般分为硬件平台、系统层和应用软件3部分,本论文主要讨论应用层,偏重于算法研究与实现。
在系统外围的软硬件环境建立好之后,针对当前匹配算法的单一性,为了提高算法的适用范围和准确度,本文论述了一种适合于嵌入环境的电子地图匹配算法。该算法采用基于记忆点的曲线拟合,拟合直线与道路的角度和点与道路的距离的综合信息来匹配定位点所在的线图元,简单实用,并给出了相应的实验结果。
在车辆导航系统中,最重要和最关键的是最优路径规划。本文比较了几种常见的搜索算法,着重讨论了人工智能中的A*算法在城市道路网中任意两点间的路径寻优的实现,给出了在ARM硬件平台上的实验结果,并详细分析了不同的启发因子对算法空间复杂度,时间复杂度和结果路径的影响。
Vehicle autonomous navigation system is an important part of the intelligent transportation system. At present, advanced vehicle navigation system combines the global positioning system, Geographic Information System and modern computer science to implement autonomous vehicle positioning and navigation. With this technology, the vehicles can drive anywhere in an unfamiliar city. It has greatly improved the efficiency and security of vehicles. The drivers can also reach the destination in the optimum path for the lowest cost.
System hardware platforms operate system and application software are the three basic parts of vehicle autonomous navigation system. The user interface and application software are generally discussed in this paper, especially focused on algorithms and implementation.
After the hardware and software environment in the system are set up, in order to improve the availability and accuracy of current matching algorithm, a method of establishing an electronic mapping environment with embedded system has been discussed, particularly proposed an arithmetic fit for embedded map positioning system. This arithmetic based on the history curve fitting, the angle of fitting line and road, and the distance between positioning point and road. It is used on matching the best line feature and has been proved simple and practical. The result figures on Pocket PC 2003 and ARM are also given in this paper.
In the vehicle navigation system, the most important and most critical thing is the optimal path planning. This paper compares several common search algorithm, focused on A * algorithm in the artificial intelligence for the urban road network which is used to be finding the optimum path between any two points .It precisely analyses the impact of different elicitation factors on the space complexity, time complexity and the result path, and proposes a realization of the algorithm on embedded platform.
自主导航系统一般分为硬件平台、系统层和应用软件3部分,本论文主要讨论应用层,偏重于算法研究与实现。
在系统外围的软硬件环境建立好之后,针对当前匹配算法的单一性,为了提高算法的适用范围和准确度,本文论述了一种适合于嵌入环境的电子地图匹配算法。该算法采用基于记忆点的曲线拟合,拟合直线与道路的角度和点与道路的距离的综合信息来匹配定位点所在的线图元,简单实用,并给出了相应的实验结果。
在车辆导航系统中,最重要和最关键的是最优路径规划。本文比较了几种常见的搜索算法,着重讨论了人工智能中的A*算法在城市道路网中任意两点间的路径寻优的实现,给出了在ARM硬件平台上的实验结果,并详细分析了不同的启发因子对算法空间复杂度,时间复杂度和结果路径的影响。
Vehicle autonomous navigation system is an important part of the intelligent transportation system. At present, advanced vehicle navigation system combines the global positioning system, Geographic Information System and modern computer science to implement autonomous vehicle positioning and navigation. With this technology, the vehicles can drive anywhere in an unfamiliar city. It has greatly improved the efficiency and security of vehicles. The drivers can also reach the destination in the optimum path for the lowest cost.
System hardware platforms operate system and application software are the three basic parts of vehicle autonomous navigation system. The user interface and application software are generally discussed in this paper, especially focused on algorithms and implementation.
After the hardware and software environment in the system are set up, in order to improve the availability and accuracy of current matching algorithm, a method of establishing an electronic mapping environment with embedded system has been discussed, particularly proposed an arithmetic fit for embedded map positioning system. This arithmetic based on the history curve fitting, the angle of fitting line and road, and the distance between positioning point and road. It is used on matching the best line feature and has been proved simple and practical. The result figures on Pocket PC 2003 and ARM are also given in this paper.
In the vehicle navigation system, the most important and most critical thing is the optimal path planning. This paper compares several common search algorithm, focused on A * algorithm in the artificial intelligence for the urban road network which is used to be finding the optimum path between any two points .It precisely analyses the impact of different elicitation factors on the space complexity, time complexity and the result path, and proposes a realization of the algorithm on embedded platform.
引文
[1] 陈健飞.地理信息系统导论[M].北京:科学出版社,2004:4-28.
[2] 李跃军.GIS 在交通领域中的应用[M].长沙:湖南交通科技出版社,2001:17-23.
[3] 姜波.Windows CE.Net 程序设计[M],北京:机械工业出版社,2007:54-74 页,295-359.
[4] 田东风. Windows CE 应用程序设计[M]. 北京:机械工业出版社.2003.
[5] 田宇,侯长勇,李洪霞.基于 Pocket PC 的 MapX Mobile 开发[J].交通与计算机.2003.6(21):95-96.
[6] 马红皎,胡永辉,张志武.使用 MapX Mobile 开发 Pocket PC 上导航软件[J].全国时间频率学术交流会.西安.2005.11.
[7] 齐瑞,屈韶琳,阳琳赟.用 MapX 开发地理信息系统[M]. 北京:清华大学出版社,2003.
[8] 贾国宪,边少锋,尚延生.基于 MapX 的 GPS 与 GIS 集成应用系统的开发[J].海洋测绘.2003.1 第 23 卷第 1 期.
[9] 黄维通.Visual C++面向对象与可视化程序设计[M],北京:清华大学出版社,2003.
[10] 陈佳瑜,肖桂荣,基于权重的地图匹配算法[J],计算机工程与应用,2005.11 P:168-170.
[11] 许志海, 张昭云, 陈应东,车辆导航系统中匹配数据处理和地图匹配技术[J],测绘学院学报,第 20 卷第 4 期,P247-250.
[12] 周颖,程荫杭 基于曲线拟合的地图匹配算法[J],交通运输系统工程与信息 2004,5 P68-70.
[13] 王楠,王勇峰,刘积仁,一个基于位置点匹配的地图匹配算法[J],东北大学学报, 第20 卷第 4 期 P344-347.
[14] 崔晓东,郑玉华,基于距离准则的地图匹配算法研究[J],城市交通 2006,5:P53-57.
[15] MapX Mobile 5.05 Developer Guide[M],MapInfo Corporation.
[16] 任福. 基于 PDA 的个人导航系统的设计与实现[M]. 武汉:武汉大学,2002.
[17] 严寒冰,刘迎春. 基于 GIS 的城市道路网最短路径算法探讨. 计算机学报,2000,23(2): 210~215.
[18] Fawcett J,Robinson P.Adaptive Routing for Road Traffic[J].IEEE Computers Graphics and Applications,2000,20(3):26-53.
[19] 陆汝钤. 人工智能. 北京:科学出版社,1995.
[20] Zhan F B. Three fastest shortest path algorithms on real road networks[J] . Journal of Geographic Information and Decision Analysis ,1997 ,1 (1) :69～82.
[21] 石纯一,黄昌宁,王家钦.人工智能原理(下)[M],科学出版社.1993.
[22] 刘光.地理信息系统-组件开发[M].中国电力出版社,2003.
[23] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
[24] Zedong Nie, Kangling Fang, Xu Xin. A Portable Positioning System Based on SOPC Technology[C]. 8th International Conference on Signal Processing, Guilin, 2006.
[25] 聂泽东,方康玲,徐新. 基于 FPGA 的贴片式定位导航系统设计[J]. 计算机工程与应用, 2007 年第 7 期.
[26] Eric Abbott, David Powell. Land-vehicle navigation using GPS [A]. Proceedings of the IEEE[C]. VOL.87, NO. 1, JANUARY 1999:145-162.
[27] 许志海, 张昭云, 陈应东.车辆导航系统中匹配数据处理和地图匹配技术[J].测绘学院学报.
[28] 王颖. 卫星导航定位技术应用与产业化[J]. 全球定位系统, 2001, 26(01):22-24.
[29] Jones C B, KidnerD B.DatabaseDesign for a MultiScale Spatial Information System[J]. Geographical Information Systems,1996.
[30] Stephen Prata,Sams.C++Primer Plus,Fourth Edition[M].2002.
[31] 侯俊杰.深入浅出 MFC[M].华中科技大学出版社,2001.1.
[32] Plazanet C J G. Affholder and E Fritsch. The importance of geometric modeling in linear feature generalization[J]. Cartography and Geographic Information Systems, 1995, 22(4): 291-305.
[33] 石旺来,王立胜,王成道.基于 MapX Mobile 的嵌入式开发[J].电子工程师.2005,31(6):79-81.
[34] 刘小虎.汽车导航系统中的嵌入式软件平台技术研究[J].导航.2005(3):99-101.
[35] 甘浩.车辆定位导航系统的最优路径规划技术研究[D].武汉理工大学硕士学位论文.2005.6.
[36] 朱志宇.基于 Windows CE 的嵌入式手持 GPS 导航仪[J].中国惯性技术学报.2005.5.
[37] 付梦印,李杰,邓志红.一种适于车辆导航系统的快速地图匹配算法[J].北京理工大学学报,2005,25(3):225-229.
[38] 卢珺.基于 GIS 的路径规划系统研究[D].大连理工大学硕士学位论文.2005.6.
[39] Boyce D,Bar-Gera H. Validation of multiclass urban travel forecasting models combining origina- estination, mode and route choices[J]. Journalof Regional Science,2003,43(3):517-540.
[40] 朱俊岭,崔平远,陈阳舟.MapX 在路径规划系统中的应用[J].计算机工程与设计.2006,27(8):50-53.
[41] 王东.信息技术在现代汽车及交通领域中的应用[J].城市车辆.2006(1):59-61.
[42] GIS 空间站[DB].http://www.gissky.net.
[43] Sinn Kim,Jong-Hwan Kim. Q-factor Map Matching Method Using Adaptive Fuzzy Network[J]. IEEE International Fuzzy Systems Conference Proceedings,1999.
[2] 李跃军.GIS 在交通领域中的应用[M].长沙:湖南交通科技出版社,2001:17-23.
[3] 姜波.Windows CE.Net 程序设计[M],北京:机械工业出版社,2007:54-74 页,295-359.
[4] 田东风. Windows CE 应用程序设计[M]. 北京:机械工业出版社.2003.
[5] 田宇,侯长勇,李洪霞.基于 Pocket PC 的 MapX Mobile 开发[J].交通与计算机.2003.6(21):95-96.
[6] 马红皎,胡永辉,张志武.使用 MapX Mobile 开发 Pocket PC 上导航软件[J].全国时间频率学术交流会.西安.2005.11.
[7] 齐瑞,屈韶琳,阳琳赟.用 MapX 开发地理信息系统[M]. 北京:清华大学出版社,2003.
[8] 贾国宪,边少锋,尚延生.基于 MapX 的 GPS 与 GIS 集成应用系统的开发[J].海洋测绘.2003.1 第 23 卷第 1 期.
[9] 黄维通.Visual C++面向对象与可视化程序设计[M],北京:清华大学出版社,2003.
[10] 陈佳瑜,肖桂荣,基于权重的地图匹配算法[J],计算机工程与应用,2005.11 P:168-170.
[11] 许志海, 张昭云, 陈应东,车辆导航系统中匹配数据处理和地图匹配技术[J],测绘学院学报,第 20 卷第 4 期,P247-250.
[12] 周颖,程荫杭 基于曲线拟合的地图匹配算法[J],交通运输系统工程与信息 2004,5 P68-70.
[13] 王楠,王勇峰,刘积仁,一个基于位置点匹配的地图匹配算法[J],东北大学学报, 第20 卷第 4 期 P344-347.
[14] 崔晓东,郑玉华,基于距离准则的地图匹配算法研究[J],城市交通 2006,5:P53-57.
[15] MapX Mobile 5.05 Developer Guide[M],MapInfo Corporation.
[16] 任福. 基于 PDA 的个人导航系统的设计与实现[M]. 武汉:武汉大学,2002.
[17] 严寒冰,刘迎春. 基于 GIS 的城市道路网最短路径算法探讨. 计算机学报,2000,23(2): 210~215.
[18] Fawcett J,Robinson P.Adaptive Routing for Road Traffic[J].IEEE Computers Graphics and Applications,2000,20(3):26-53.
[19] 陆汝钤. 人工智能. 北京:科学出版社,1995.
[20] Zhan F B. Three fastest shortest path algorithms on real road networks[J] . Journal of Geographic Information and Decision Analysis ,1997 ,1 (1) :69～82.
[21] 石纯一,黄昌宁,王家钦.人工智能原理(下)[M],科学出版社.1993.
[22] 刘光.地理信息系统-组件开发[M].中国电力出版社,2003.
[23] 严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.
[24] Zedong Nie, Kangling Fang, Xu Xin. A Portable Positioning System Based on SOPC Technology[C]. 8th International Conference on Signal Processing, Guilin, 2006.
[25] 聂泽东,方康玲,徐新. 基于 FPGA 的贴片式定位导航系统设计[J]. 计算机工程与应用, 2007 年第 7 期.
[26] Eric Abbott, David Powell. Land-vehicle navigation using GPS [A]. Proceedings of the IEEE[C]. VOL.87, NO. 1, JANUARY 1999:145-162.
[27] 许志海, 张昭云, 陈应东.车辆导航系统中匹配数据处理和地图匹配技术[J].测绘学院学报.
[28] 王颖. 卫星导航定位技术应用与产业化[J]. 全球定位系统, 2001, 26(01):22-24.
[29] Jones C B, KidnerD B.DatabaseDesign for a MultiScale Spatial Information System[J]. Geographical Information Systems,1996.
[30] Stephen Prata,Sams.C++Primer Plus,Fourth Edition[M].2002.
[31] 侯俊杰.深入浅出 MFC[M].华中科技大学出版社,2001.1.
[32] Plazanet C J G. Affholder and E Fritsch. The importance of geometric modeling in linear feature generalization[J]. Cartography and Geographic Information Systems, 1995, 22(4): 291-305.
[33] 石旺来,王立胜,王成道.基于 MapX Mobile 的嵌入式开发[J].电子工程师.2005,31(6):79-81.
[34] 刘小虎.汽车导航系统中的嵌入式软件平台技术研究[J].导航.2005(3):99-101.
[35] 甘浩.车辆定位导航系统的最优路径规划技术研究[D].武汉理工大学硕士学位论文.2005.6.
[36] 朱志宇.基于 Windows CE 的嵌入式手持 GPS 导航仪[J].中国惯性技术学报.2005.5.
[37] 付梦印,李杰,邓志红.一种适于车辆导航系统的快速地图匹配算法[J].北京理工大学学报,2005,25(3):225-229.
[38] 卢珺.基于 GIS 的路径规划系统研究[D].大连理工大学硕士学位论文.2005.6.
[39] Boyce D,Bar-Gera H. Validation of multiclass urban travel forecasting models combining origina- estination, mode and route choices[J]. Journalof Regional Science,2003,43(3):517-540.
[40] 朱俊岭,崔平远,陈阳舟.MapX 在路径规划系统中的应用[J].计算机工程与设计.2006,27(8):50-53.
[41] 王东.信息技术在现代汽车及交通领域中的应用[J].城市车辆.2006(1):59-61.
[42] GIS 空间站[DB].http://www.gissky.net.
[43] Sinn Kim,Jong-Hwan Kim. Q-factor Map Matching Method Using Adaptive Fuzzy Network[J]. IEEE International Fuzzy Systems Conference Proceedings,1999.