智能导航车载终端动态路径引导

        随着国内车载智能导航产业的深入发展，电子地图数据、交通信息等导航数据日益标准化。本文主要解决如何使用导航背景数据和拓扑数据进行动态路径计算。并从导航数据的组织方式、路径规划算法以及交通信息的动态成效等方面对动态路径计算理论进行了系统的论述。

　　1导航数据的组织方式

　　路径规划与引导是基于电子地图实现的，导航地图数据的设计主要考虑4个方面:内容、组织、关系和存取方法。车辆定位和导航系统要求能支持地图匹配、路径规划、路径引导、地图显示和相关兴趣点的查询的导航数据，同时，还应考虑到车载设备的硬件条件，运行时的存取速度。为了使电子地图能够真实、有效的反映交通状态，高效准确的完成导航任务，结合KIWI、NavTech、TeleAtlas、GDF等主流导航数据标准的分析，设计一种新的地图数据组织方式。

　　按照不同的应用方式，将数据分为两大类:背景数据和拓扑网数据。背景数据负责导航电子地图的可视化，其中包含了各类地物要素和地图要素的可视化表达信息，包括点、线、面类型要素的空间信息和标注层信息等。拓扑网数据是各种导航计算的基础，由路径数据和信息点数据组成。

　　1.1背景数据的组织方式

　　背景显示包括数据的收集、图标的定义、路径的显示格式和地图的渲染方式等方面。普通的数据格式是从实际的交通网络中抽取出的矢量信息。但是由于地图的渲染需要占用很多系统资源，在这里，采用牺牲空间换取时间的策略，为每个单位的背景矢量数据，通过截屏处理，制作了一份图片数据(png格式)，并将背景的显示方式设置为可选的，当使用者处于非导航模式时，在显示器上出现的就是这些图片。当使用者切换到导航模式时才将真正的矢量背景数据调入。这样做，不仅提高了非导航模式时系统的执行效率，也为使用者的偏好提供更多可选择的余地。

　　1.2拓扑网数据存储

　　拓扑网数据可以分为路径数据和信息点数据两种，分别对应于拓扑网络中的边和点，在车载导航地图中，分别对应的是地图上的路径和信息。

　　1.2.1路径数据的物理组织

　　路径数据是一组按区域进行组织的二进制文件模块。如表1所示。

　　表1 路径数据物理组织方式

文件名（中文）	文件名（英文）	内容
路段文件	LinkFile	存放路段信息
结点文件	NodeFile	存放节点信息
拓扑文件	MatrixFile	存放交通拓扑网络信息
转向文件	TurnFile	存放转向交通规则
时间文件	TimeFile	存放禁止时间段信息
节点对应文件	NCFiIe	表述同一节点在不同Level之间的对照

         这些文件统称为路径文件。每个文件均含一个自解释的信息头，说明数据的版本、精度、对象数量等。一般而言，低级的路径区域对应于地市级行政区划，相邻的地图路径数据区域可以无缝的拼接在一起。更高级的路径区域对应的省级乃至全国级的道路区域，并且相对其中的路径弧段和结点信息进行抽取简化，越是高级的路径区域中的道路级别就越高，级别越低的路径区域中的道路信息也就相应的越完整。

　　1.2.2信息点数据的物理组织

　　信息点数据与路径数据一样按区域进行组织，用于记录该区域内所有信息点的详细信息。每个信息点数据文件也都含一个自解释的信息头，说明数据的版本、精度、要素个数等。

　　信息点数据文件的对象不仅可以表示一个通常意义上的信息点也可用于记录该区域内所有有名称的交叉路口信息，因为在一些城市交叉路口信息也常常被用来表示方位。

　　1.3各文件间的逻辑关联

　　实时车载导航应用对地图文件、数据的查找和引用提出了较高的要求。所设计的导航地图数据的索引主要依靠对数据文件的操作来实现，在基于文件索引的基础之上再提供特殊的文件数据存贮机制，来优化对文件内数据的索引速度。

　　首先，背景数据文件和路径数据文件的分层分区分块存贮，己经提供了一种基于行政边界的地图区域索引机制。应用层可以快速的依据目标地物所属的行政区划来确定所需调用的数据文件，这里的地图数据文件是处于文件系统中的一系列规则组织的目录和文件集合，目录和文件的名字均以一定的规则进行命名。以确定的文件形式来进行调用在嵌入式系统中就把索引的工作交给系统层来处理，可以很轻松的实现地图数据文件的系统无关性，大大减化应用层的工作量，并且在文件系统中对文件的索引速度是相当快的。

　　其次，背景数据文件和路径数据文件中的所有数据都是分层分类地进行结构化组织的。每一层次及其之下的每一类别的数据都有显示的偏移量或隐含的偏移量进行索引，保证在无须对文件内数据进行搜索的情况下可以直接定位到所查找的数据体。隐含的偏移量的实现是依据文件数据组织的规则性来实现的，所有数据均尽可能地按统一的规范组织起来，并相应地分配以连续递增的ID值，依据ID值及数据体单位结构的大小即可求出每一特定的数据体在文件中偏移，从而实现快速地提取。

　　再次，各类数据文件间内在的逻辑联系保证了查询检索匹配的高速度和有效性。背景数据文件、路径数据文件和信息点数据文件等三大类数据体都含有内在的匹配关系，应用层可以快速地在这几类文件之间进行交叉索引定位。例如信息点数据文件中的每一个信息点数据体内均含有该信息点所归属的弧段Link的全国唯一ID值，这一ID值是直接对应到同一区域LinkFile内的Link数据体的，我们可以根据前述的隐含的偏移量计算，在LinkFile中快速的提取出这一Link数据体的具体内容信息，包括Link本身描画用的经纬信息，也可以从当前信息点的位置经纬度信息很快地推算出其所处比例尺下的背景图幅编号及其在该图幅的相对位置坐标，使得其可在这一图幅中直接表示出来。同时，根据预先得到的LinkID值相应获得的LinkData或FromNode, ToNode信息可以来确定相应的背景图幅，或依据NodeFile来直接定位图幅位置。这些处理方法都是可行且迅速的。

　　2路径规划算法(Dijkstra算法)

　　车载自主导航最优路径规划问题是指找出从起始结点到终结点车辆行驶时间最短的一条路线，这是一个源点到汇点的最短路径问题，典型算法有Floyd算法、Dijkstra算法，A*算法等。其中以迪杰斯特拉(Dijkstra)算法在实际应用中最为广泛。其思想是由近及远的寻找起点到其它所有节点的最短路径，当刚好找到所求终点的最短路径的时候，算法终止。道路网可简化抽象为一个权值为正值的有向图。在有向图的最短路径问题中，Dijkstra 算法是一种较好解决这一问题的方法。Dijkstra 算法基本思路是假设每个点都有一对标号(dj，pj)，其中 dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。

　　3动态权值计算

　　在动态导航过程中，需要计算路道在某一时刻的动态权值，具体实现方法如下。

　　假设搜索最佳路径的网络矩阵为DT[dtij]M*N，则车辆从i交叉口行驶到j交叉路口的行驶时间为车辆在路段i-j的行驶时间和交叉路口的时间延误以及交通管制措施等来决定。

　　要事先得到车辆在路段i-j的确切行驶时间是不可能的，因此，利用交通部门发布的实时交通信息获得车流密度和空间平均速度Vs再根据路段的长度dij估计该行驶时间。

　　经过修正的路权即为路网的实时路权。将此路权存人路权历史数据库，作为下次路权计算的历史数据。实际中，需要对已计算的新路权进一步修正:如果车道禁行，则将该路段的路权改为无穷大。为保证路权的实时性，以一定的时间间隔(例如15min)对路网的路权进行重新赋值。每次最优路径选择都是基于实时路权进行计算，从而实现了车辆调度的实时性。

　　4交通信息在车载终端的动态呈现方法

　　目前的动态交通信息的展现方式有地图、文字、数字、语音等。其中地图展现是最主要的也是最复杂的一种方式。导航电子地图是指在传统的地图上添加了详细的交通信息，并从数据结构和路网拓扑结构上进行了专门的设计，适用于车辆导航所需的高效路径计算、路径引导等功能，并能够支持动态交通信息的电子地图。导航电子地图是车载终端子系统的重要组成部分，是各种动态交通信息及路径诱导实现的载体。利用导航电子地图，车载终端可以完成定位显示、地址查询、地图匹配等功能，结合地图中存储交通信息，完成合理的路径规划，并用语音或箭头的方式在电子地图上完成路径诱导功能。

　　4.1电子地图数据更新流程

　　利用GPRS无线数据网络传输协议，车载终端可以通过 GSM 无线公众网以及 Internet 和信息中心进行数据交换，车载终端接收到中心发布的动态交通信息后，将其解析、存储，与地图数据相关联，利用这些信息动态更新地图数据，参与导航最优路径的计算，同时，这些信息还需要动态显示在车载终端的导航地图上，简洁、直观地呈现给用户。

　　4.2基于线性参照技术的地图匹配

　　线性参照技术是交通信息与地图匹配的关键技术。线性参照系(LRS)是公路地理信息系统理论研究和实际应用中的关键问题之一。线性参照系是一种具有线性特征的事件通过与已知大地坐标的参照点间的距离来计算其大地坐标的基准和方法。应用线性参照系可以减少因重复记录路径信息造成的数据冗余，便于进行事件的分析、查询和网络分析，并能很好地符合公路管理习惯。线性参照系包括线性参照基准和线性参照算法两部分。线性参照基准的基本要素是数据点和控制段:数据点是代表公路上具有大地坐标和公路线性坐标的点。控制段由数据点构成并具有公路识别代码等属性值，其划分通常由应用要求决定，具有一定的灵活性。线性参照算法则是依据线性参照基准计算事件空间位置的方法。

　　4.2.1线性参照基准

　　建立满足应用需求的线性参照基准是线性参照系的应用基础.通常，我们利用GPS或地图矢量化沿路径采集公路数据点，由点组成折线路径。但公路路径实际上是由直线、圆曲线和缓和曲线3种基本线形所组成。为了减少数据冗余和提高数据点的线性坐标精度，需要将折线识别为直线段、圆曲线段和缓和曲线段，并据此进行不同的处理。

　　将不同的路段分别标识为直线段、圆曲线段和缓和曲线段后，可以计算出各自的几何线形参数。同时根据不同的线形分别采用不同的方法来压缩其冗余数据，如相邻3点间最大允许斜率差值法、相邻两点的最大允许距离法或将这两种方法结合起来使用等。

　　经过压缩处理的数据点只具有大地坐标，还没有相应的公路线性坐标.可以将经过准确测量的、具有大地坐标和线性坐标的数据点加人经过压缩处理的数据点集中，采用适当的坐标分配算法，使所有的数据点都具有合理的线性坐标。在实际应用中，可按两相邻控制点间的路段几何参数所计算的长度为其数据点分配线性坐标。将上述经过处理的数据点按照应用的要求划分成控制段，并由数据点和控制段形成线性参照基准。

　　4.2.2线性参照算法

　　线性参照算法是将一维线性系中的事件和二维参照系中的空间数据相联系的方法，使公路数据库中的多个事件集与一维路线中的特定部分相关联，而不必考虑每个事件所对应的二维坐标，便于对公路事件实现存贮、动态显示、查询和分析。线性参照算法不是对道路进行物理上的分段，而是在查询、分析道路的某类属性时，根据建立的线性参照系动态分段，并显示事件的空间位置。

　　基于空间对象的坐标线性内插是一种常用的线性参照算法。但由于不考虑公路线形的影响，所以控制点的位置精度和用于内插的相邻两参考点的精度与间隔，对内插的事件点的定位精度产生较大的影响。而基于道路几何特征的线性参照算法，则充分考虑公路线形的影响，采用分段曲线积分来确定事件的空间坐标，因而具有较高的精度。

　　上述方法考虑了不同道路线形的影响，但线形几何参数的识别是根据矢量化数据结果运算得来的，与实际公路线形有较大的出入，利用上述方法计算得到的事件位置在显示时可能位于路线外，影响显示效果.为了避免上述情况的发生，可以找出与事件位置相邻的两参考点，将计算的结果投影到分别以两参考点为起点和终点的直线段上，以垂足坐标作为显示坐标，这样就可以保证在放大显示时事件仍位于路线上。

　　实际应用中，我们根据前述线性基准生成算法对电子地图相关图层数据进行处理，得到有关的线形参数和路线点，再划分控制段、建立线性参照系基准.然后，根据前述线性参照算法将实时交通信息的事件与地图道路数据相关联，利用GIS地图控件进行地图的二次开发，将交通信息在地图上动态显示出来。

　　4.3实时交通状况显示

　　根据我国公安部 2002 年公布的《城市交通管理评价指标体系》中规定，用城市主干道上机动车的平均行程速度来描述其交通拥挤程度：畅通：城市主干路上机动车的平均行程速度不低于 30km/h；轻度拥挤：城市主干路上机动车的平均行程速度低于 30km/h，但高于20km/h；拥挤：城市主干路上机动车的平均行程速度低于20m/h，但高于10km/h；严重拥挤：城市主干路上机动车的平均行程速度低于 10km/h。

　　首先在程序中设置4个不同的判别道路交通状态的标准，再调用计算出的道路样本车辆的模拟平均速度结果。根据这些标准进行对比，可以自动得出电子地图中的每条道路的实时交通状态。得到实时的道路交通状态的结果后，调用每条道路的实时道路交通状态信息数据，根据不同的实时道路交通状态级别，分别选择相对应的彩色图标，以列表形式显示在系统主界面上，同时将实时道路交通状态以文字形式显示在系统界面上。

　　4.4动态最优路径显示及路径引导

　　车载终端完成路径规划后,根据路径中包含的点的坐标，确定路径中的边。这时在电子地图上创建一个动态图层，在此图层中根据已经确定的边和点画出相对应的路径，显示出相对应的动态最优路径。同时，车载终端按照规划好的路径引导用户向前。主要完成以下两个任务：通过人机接口界面提示用户引导信息和对规划好的路径进行跟踪。

　　4.4.1途中引导

　　当车辆正确匹配到初始路网后，导航系统便按照规划好的行车路线引导用户从当前位置到达目的地。在整个导航过程中，系统通过 LCD 界面显示车辆所在路径，并且在车辆到达下一节点(十字路、立交桥或环岛)之前，通过图形图标和语音告诉用户转入道路名称，转向以及到达节点的距离等相关信息上述提示不能太早，如果车辆和下一节点之间还有其它节点，容易给用户造成误导，弄错转向路口；太晚提示则容易造成驾驶者事先没有任何思想准备的情况下仓促转向，或者驾驶者已经驶过路口才提示转向信息。

　　4.4.2离路引导

　　用户可能由于各种原因偶尔地偏离规划的路径行驶。他们可能在指示的交叉路口转错了弯，对于一个交叉路口可能不能行驶到正确的车道，也可能临时离开路径等。一旦系统确定车辆不再行驶在规划的路径上，系统必须提醒用户，使其回到规划的路径上。一旦确定车辆偏离了规划路径，可采用不同的方法解决这个问题。最简单的解决办法是提醒司机注意车辆偏离了他的路径，接着在屏幕上显示一个方向箭头指向原来目的地方向，提示用户原路返回。第二种解决办法是通过局部导航电子地图查找用户当前所在路段和规划中的行车路线的各个节点是否连通，如果连通则自行改变规划好的路径，将用户重新引导到规划的路径上。第三种情况是用户迷路，则重新申请导航。如图1所示，车辆应该按照 A → B → C路线行驶，但车辆却由 A行驶到B′。图1(a)由于B′处路段数据包含在局部地图中，系统可以引导用户沿着 A → B ′→ C路线行驶到规划的路径中；图1(b)由于B′处虚线路段并不存在于局部导航电子地图，所以不能规划新的路径，用户只能原路返回或者重新申请导航。

　　参考文献

　　[1]国家标准化管理委员会，GB/T 19711-2005，《导航地理数据的数据模型和交换格式》

　　[2]国家标准化管理委员会，GB/T 20268-2006，《车载导航地理数据采集处理技术规程》

本文来源：《卫星与网络》    作者：中寰卫星导航通信有限公司 郗默洋 刘艳梅

隐藏原文↑