改进双向启发式搜索算法及其车载导航仪中应用

2016-10-10来源: eechina关键字:车载导航仪  双向启发  搜索算法
车载导航仪也称为车载定位和导航系统(Vehicle Location and Navigation System。它的主要功能是利用全球定位系统(GPS)获取定位信息并与电子地图进行匹配,以决定车辆的当前位置并用图形化方式显示;按要求规划从出发地到目的地的最优驾驶路线;按照预先设定的路线,自动根据车辆的位置向驾驶员提供操作指令引导驾驶;提供与电子地图相关的集成信息服务;提供无线通信服务等。车载导航仪把先进的全球卫星定位技术、地理信息技术、数据库技术、多媒体技术和现代通信技术综合在一起?能够实时、高效地向驾驶员提供多种重要信息,具有很强的实用价值和广阔的市场前景。

路径规划是车载导航仪的重要功能模块。在开发车载导航仪过程中,为了实现路径规划模块,对单车辆路径规划算法进行了研究。

1 路径规划算法

所谓路径规划,就是在路网中找到任意给定两点之间的最优路径。最优的标准是旅行费用最小或最大。旅行费用可以是距离、时间或速度等因素。路径规划主要算法有:迪杰斯特拉(Dijkstra)算法及其改进算法、启发式搜索算法、双向搜索算法和双向启发式搜索算法等。

迪杰斯特拉算法是解决两点之间最短距离的有效算法。算法的思想是?从原节点开始,算法每前进一步,都找到一个与原节点之间费用(距离)最小的节点,直至找到所有节点离原节点的最小费用。该算法的特点是?只要各段路径的费用非负,一定可以找到从原节点到各节点的最优解。缺点是需遍历所有节点。算法的运行时间为O slogn 1,其中n、s分别为路径节点和路段的总数。单车导航没有必要找到所有节点到原节点的最优路径。改进的迪杰斯特拉算法在找到目标节点的最优路径后,算法停止。其运行时间为O bd,其中b是各节点的平均后继节点数,d为算法的搜索深度,即遍历树的层数。

启发式搜索算法引入启发式估价函数f'n=g n+h'n,其中gn表示从原节点到当前节点n的实际费用,h'n为当前节点n到目标节点的估计费用。启发式搜索算法基本同于改进的迪杰斯特拉算法,唯一不同的是前者的费用是f'n,而后者为g n。估计费用h' n能引导算法优先搜索接近目标节点的节点,因此比改进的迪杰斯特拉算法有更快的速度。其运行时间为O bd。注意这里的d要比改进的迪杰斯特拉算法中的d要小。若路网中任意两点之间存在最优路径,而且估计费用满足可纳性,即h' n小于从节点n到目标节点之间的实际费用,那么通过该算法一定可以找到一条最优路径。

前面两种算法都是从原节点到目标节点没单一方向进行搜索的算法。双向搜索算法的思想是:不仅进行从原节点到目标节点的前向搜索,而且进行从目标节点到原节点的后向搜索。在单CPU硬件平台条件下,两个方向的搜索交替进行。成功实现双向搜索有两个条件,即合适的搜索停止条件和前向后向搜索切换标准。其算法时间为O bd/2。若双向搜索算法中加入估计费用函数,便是更快的双向启发式搜索算法1。

2 双向启发式搜索算法的改进和实现

2.1 算法的优化与改进

通过对双向启发式搜索算法的仔细分析,发现算法主要围绕两个表进行操作,即OPEN表和CLOSE表。前者用于存放已经搜索但尚未确定最小费用的节点,称labbled节点;后者用于存放已经搜索且最小费用已知的节点,称scanned节点。后者也用于存放路径回朔指针等。对OPEN表的主要操作有插入一个i节点insert i,删除费用值最小的节点delete 和减小其中某个节点i的费用decrease i。算法对OPEN表的操作极为频繁。若用高效的数据结构来实现该表及其操作,可以提高算法的效率和速度。最后用有高效算法的最小堆4实现了OPEN表及其操作,优化了算法。具体实现的函数如下:

void filter_down int START int ENDOFHEAP//由起点START从上而下排列堆;
void decrease int NODE//更新减少堆中节点NODE的费用f'值;
void filter_up int START //由起点START从下而上排列堆;
void heap_create int MAXSIZE //创建堆;
void heap_destructor//析构函数;
int insert int NODE//把节点NODE插入堆;
int remove_min int &iMinNode//删除堆中最小费用f'值的节点。

在实际的路网中,路段有不同的属性,如高速公路、收费路段、单行路段等。有些路段可能因修建或发生交通故障而暂时封闭。因此在进行路径规划时,算法应该考虑路网中路段的属性,才能进行符合实际的规划,否则理论上规划出来的最优路径可能是不通的。为此,对算法进行了改进。增加一个变量纪录各路段的属性,算法每搜索一新的路段,都要检查该路段的属性,若是限制的路段,算法不做任何处理。同时路径规划算法入口参数中应说明限制的内容。这样就能根据用户的意愿或实时交通信息,避免走某些特定的路段。

2.2 搜索停止条件、搜索切换标准和估计费用函数

前面提到,成功实现双向搜索算法必须有合适的搜索停止条件和切换标准。两个标准没有现成的理论依据。经过对车载导航仪实际应用的分析和反复试验,终于找到可靠有效的标准。其中停止条件为:(1)搜索到这样一个节点iNODEmin,它在前向后向搜索过程中均被标为scanned节点;(2)gl iNODEmin +g2 iNODEmin确实是最小的,其中gl iNODEmin表示从原节点到iNODEmin的最小费用,g2 iNODEmin表示从目标节点到iNODEmin的最小费用。如果只满足第一个条件就停止搜索,找到的最优路径不一定是最优的。只有加上第二个条件,才能确保找到最优的路径,但付出的代价是要多搜索几十个点。具体的搜索停止条件如图1所示。


此外,经过实验发现,如前向搜索的步数和后向搜索的步数不同,则算法的总的搜索节点数增加。因此两个方向上的搜索步数应相同,然后切换。但搜索步距过小或过大,也会增加总搜索量。最后定下的切换标准是,每个方向搜索20步后切换方向。此外,前向搜索估计费用函数hl'n定义为从当前节点n到终点的欧氏距离,后向估计费用函数h2' n定义为从n到原节点的欧氏距离。由于这两个距离均小于从n到目标节点或原节点的路径的实际距离,因此hl'n和h2'n满足可纳性。 

2.3 算法流程

改进的双向启发式搜索算法主要流程如下:

(1)把原节点移入前向CLOSE表,即令flagl原节点=scanned,其费用gl原节点=0,其它节点的费用为无穷。 

(2)对原节点所有后继节点i进行如下操作:

·判断路径(原节点,I)是否限制路段,是处理下一个后继节点,否则继续;
·计算i的费用f1I =g1 I+hl'i;
·置i的搜索状态flag1 i=labbled;
·把i的后向指针指向原节点,即link1 i=原节点;
·把i插入OPEN1表,即insert1 i。

(3)判断OPEN1表是否为空,若为空提示出错,算法停止;否则从OPEN1表中移出费用值f1最小的节点iNODEmin,令节点i的搜索状态flag1 iNODEmin=scanned,判断iNODEmin是否满足搜索终止条件。若满足跳转至(7),否则对iNODEmin的所有后继节点i进行如下操作: 

·判断路径(iNODEmin,I)是否限制路段,是处理下一节点,否则继续;
·计算i的费用f1 i=g1 I+h1'i;
·若节点i的搜索状态flag1 i=unlabbled,则令其费用f1 i=g1 I+h1' i,link1i=iNODEmin insert1 i;
·如果节点i的flag1 i=labbled,计算节点i新的费用g1'I =g1 iNODEmin+从iNODEmin到i的实际费用,若g1' I <g1 i,令g1 i=g1'I ,link1 i=iNODEmin,decrease1 i;否则继续。
·若flag1 i=scanned,计算g1'i =g1 iNODEmin+从iNODEmin到i的实际费用,若g1' i<g1 i,令g1 i=g1' i,link1i=iNODEmin,flag1 i=labbled,inertl i;
·判断前向搜索是否进行了20步,是跳转至(4)(第一次切换)或(6)(第二次以后的切换),否则跳转至(3)。

(4)同(1),只是对CLOSE2操作;

(5)同(2),只是对OPEN2和CLOSE2操作;

(6)同(3),只是对OPEN2和CLOSE2操作,切换时跳转至(3);

(7)计算最优路径的费用,分别从搜索停止节点到原节点和从搜索停止节点到目标节点回朔,报告解路径。上述流程中(1~3)步为前向搜索,(4~6)为后向搜索。

3 试验结果及结论

作者用C语言实现了双向启发式搜索算法和其它三种算法,并用约有10000个节点的美国纽约地图进行了大量路径规划试验。试验的部分数据如表1所示。


表中的数据除起止节点外,为相关算法的搜索节点数,括弧中数据为一次测试中该算法的搜索点数少于改进的迪杰斯特拉算法的搜索点数的百分比。大量试验统计表明,启发式搜索算法的搜索空间比改进的迪杰斯特拉算法少1.5%,双向搜索算法的搜索空间比改进的迪杰斯特拉算法减少26.6%,双向启发式搜索算法的搜索空间比改进的迪杰斯特拉算法少28.0%。算法运算时间与搜索点数成正比。双向搜索的效果较好,启发式的效果较差。主要原因是试验地图数据库给出的节点坐标是经纬度,估计费用直接用两点的经纬度算出,其值很小,所以引导的效果不好。进行坐标变换后,启发式的效果应有比较大的改善,双向启发式搜索算法的速度会更快。 

算法程序全部用C语言编写,所用功能模块均以函数的形式给出,以便移植到基于WindowCE的硬件平台。总之改进的双向启发式搜索算法快速高效,已经成功用于正在开发的车载导航仪。

关键字:车载导航仪  双向启发  搜索算法

编辑:什么鱼 引用地址:http://news.eeworld.com.cn/qrs/article_2016101030902.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:比特斯拉充电速度快了近三倍,保时捷电动车不仅仅只有酷
下一篇:用于车速传感器测试平台的串行口-以太网桥设计

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

Flash硬盘及其在GPS车载导航仪中的应用

1 GPS车载导航仪概述 随着现代交通运输网络和汽车工业的飞速发展车辆的自主导航和实时监控越来越受到人们的普遍关注,并被广泛地应用到交通运输网络的各个方面。 TRACK-II型GPS车载导航仪是我研究所与香港ARCON公司合作研制的最新一代车载导航仪。它是一种基于GPS技术并融合电子和通信技术的集成信息的硬件和软件平台,具有GPS准确定位、路线最优引导、旅行信息查询、出行信息查询、驾驶员信息查询等信息综合服务功能。从所完成的功能来划分,GPS车载导航仪可以划分为物理层、数据链路层和应用层。物理层获取当前车辆的相关信息,包括姿态、位置、方向和时间等信息,以及与当前位置相关的地理信息数据;数据链路层则在所获取的原始数据
发表于 2015-10-12

JVC建伍首次量产带平视显示器的车载导航仪

JVC建伍将于2013年5月中旬开始销售采用平视显示器(HUD)显示驾驶辅助信息的车载导航仪“MDV-737HUD”。HUD采用了该公司在投影仪领域培育出的LCOS(反射型液晶)技术“D-ILA”(直接驱动图像光源放大器)。该公司过去曾以其他方式作为选配件销售HUD,而此次是首次应用于市售的车载导航仪量产品。新产品的车载导航仪部分在印度尼西亚生产,HUD在日本生产,二者配套销售。价格为开放式,预计实际售价在25万日元左右(约1.55万元人民币)。 HUD安装在室内镜上使用,D-ILA器件为0.37英寸,显示画面为7英寸(投影距离为2m时),总像素约为92万。采用白色LED光源,色温为4000K,亮度为1.5万cd/m2。使用
发表于 2013-05-13

智能手机“逼迫”车载导航仪实现差异化

传统式的车载导航仪如今面临着重新定义的要求。这缘于智能手机的崛起。面对智能手机实时在线、可以通过应用软件不断增加功能的灵活性,车载导航仪已经没有还手之力。为了促进车载信息终端的进化,汽车企业和车载产品企业正在加紧采取行动。 智能手机的崛起正在使车载导航仪市场发生巨变。最先受到影响的是简易型车载导航仪(PND)。其发展势头从往日的如日中天状态一落千丈。 瑞典调查公司Berg Insight表示,2011年全球的PND销量为3300万台,比2010年的3800万台减少了500万台。到2016年预计将减少到2300万台。 而多功能内置型导航仪由于汽车企业正在加强原装品的配备,供货量预计在今后还将扩大。但情况并非高枕无忧。因为了解
发表于 2012-12-03

未来车载有智慧 SIRI也能充当导航仪

”。不过,从目前得到的信息来看,该模式还是与手机上的SIRI功能同步,也就是说,你能够通过语音控制,指挥SIRI为你打电话、发短信、开音乐等功能,唯一的亮点就是你不用边开车边用手操作手机,直接用语音就能控制电话操作,让你在开车的时候眼睛依然能够直视前方,双手也不用离开方向盘,提高行车安全性。     其次,SIRI也能充当你的导航仪。苹果自己开发了一套地图系统,能够提供3D功能和全程导航功能,同时还推出了Yelp的餐馆评价和推荐。此外,该系统与福特的inkaNet荣威识别模式、通用人工语音服务台等车载服务系统相比,最大的优点在于免费,但它并没有远程开锁及防盗功能,相比之下安全性欠佳。     “车联网”市场硝烟暗起     据《中国移动
发表于 2012-07-03

动力的源泉 车载GPS导航仪供电方式深度解析

目前市场上出售的导航产品按类型分有手持机、车载GPS、GP手机、以及GPS模块等,不论是哪种类型的导航产品,供电问题都是购买时要考虑的重要因素之一。而在这几类GPS设备中对供电要求最小的恐怕算是车载GPS产品了,这些产品一般都可以利用车载电源供电,因而行驶中可不必为续航能力而担忧。 但是,随着众多附加娱乐功能融入其中,车载GPS产品的功能已经不单单局限于导航指路,而慢慢的演变成一台功能丰富的PND产品,电池电量这个因素也就显得比较重要。续航能力的长短直接影响了机体的正常使用,对于用户购买车载GPS产品的影响也越来越大。 提供给车载导航仪产品的供电方式我们归纳为四种,借机来解析一下作为车载导航产品动力源泉的几种供电方式
发表于 2012-05-21

改进的双向启发式搜索算法及其在车载导航仪中的应用

    摘要:介绍单车辆路径规划的有关算法,针对车载导航仪的应用,对双向启动式搜索算法进行了改进和优化,提出了可靠有效的搜索终止条件和搜索切换标准,给出了改进算法的流程。最后给出了四种算法的实际测试和比较结果。结果表明改进的双向启发式搜索算法快速高速效。     关键词:路径规划 启发式搜索算法 双向搜索算法
发表于 2006-05-07

小广播

何立民专栏

单片机及嵌入式宝典

北京航空航天大学教授,20余年来致力于单片机与嵌入式系统推广工作。

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2019 EEWORLD.com.cn, Inc. All rights reserved