车载GPS定位技术与应用习题及资料.doc

车载GPS定位技术与应用习题及资料
1、 什么是道路交通系统？具有什么样的特点
答：由人、车、路、环境四大要素组成的一个总体。
特点：（1）系统性；（2）开放性；（3）动态性；（4）突变性；（5）非线性。
2、解决交通问题，除了新建必要的道路，完善路网布局，加强对现有道路的管理，从全局和长远来看，主要的对策是什么？
答：
1)大力发展高效、安全的公共交通系统。
2）积极研发低污染、低能耗的新型汽车。
3）积极发展新一代智能交通系统（ITS）。
4）坚持土地规划、开发与交通规划、建设相协调，将土地利用、道路建设与环境保护统一在系统中研究、以路网容量和环境容量作为土地利用的约束条件加以分析，有机地协调三者之间的关系，确保道路交通的可持续发展。
3、什么是ITS？
答：ITS（Intelligent Transportation Systems）即智能交通系统是在较完善的道路设施基础上，将先进的电子技术、信息技术、传感器技术和系统工程技术集成运用于地面交通管理所建立的一种实时、准确、高效、大范围、全方位发挥作用的交通运输管理系统。它是充分发挥现有交通基础设施的潜力，提高运输效率，保障交通安全，缓解交通拥挤的有力措施。
ITS的智能化特点体现在什么方面？
4、ITS的主要功能有哪些？
答：（1）顺畅功能：增加交通的机动性，提高运营效率；提高道路网的通行能力，提高设施效率；调控交通需求。
（2）安全功能：提高交通的安全水平，降低事故的可能性/避免事故；减轻事故的损害程度；防止事故后灾难的扩大。
（3）环境功能：减轻堵塞；低公害化，降低汽车运输对环境的影响。
5、目前国际上公认的ITS的服务领域有哪些？
答：（1） 先进的交通信息服务系统（ATIS）；
• ATIS是建立在完善的信息网络基础上的，交通参与者通过装备在道路上、车上、换乘站上、停车场上以及气象中心的传感器和传输设备，可以向交通信息中心提供各地的实时交通信息；该系统得到这些信息并通过处理后，实时向交通参与者提供道路交通信息、公共交通信息、换乘信息、交通气象信息、停车场信息以及与出行相关的其他信息；出行者根据这些信息确定自己的出行方式、选择路线。更进一步，当车上装备了自动定位和导航系统时，该系统可以帮助驾驶员自动选择行驶路线。 
（2） 先进的交通管理系统（ATMS）
• 这个系统有一部分与ATIS共用信息采集、处理和传输系统，但是ATMS主要是给交通管理者使用的，它将对道路系统中的交通状况、交通事故、气象状况和交通环境进行实时的监视，根据收集到的信息，对交通进行控制，如：信号灯、发布诱导信息、道路管制、事故处理与救援等。
（3） 先进的公共交通系统（APTS）
• 这个系统的主要目的是改善公共交通的效率（包括：公共汽车、地铁、轻轨交通、城郊铁路和城市间的长途公共汽车），使公交系统实现安全便捷、经济、运量大的目标。

（4）先进的车辆控制系统（AVCS），AVCS目前还处于研究试验阶段，从当前的发展看，可以分为两个层次：
l 一是车辆辅助安全驾驶系统，该系统有以下几个部分：车载传感器（微波雷达、激光雷达、摄像机、其他形式的传感器等）、车载计算机和控制执行机构等，行驶中的车辆通过车载的传感器测定出与前车、周围车辆以及与道路设施的距离和其他情况，车载计算机进行处理，对驾驶员提出警告，在紧急情况下，强制车辆制动。
l 二是自动驾驶系统，装备了这种系统的汽车也称为智能汽车，它在行驶中可以做到自动导向，自动检测和回避障碍物，在智能公路上，能够在较高的速度下自动保持与前车的距离。必须指出的是，智能汽车在智能公路上使用才能发挥出全部功能，如果在普通公路上使用，它仅仅是一辆装备了辅助安全驾驶系统的汽车。
（5） 货运管理系统
• 这里的货运管理系统是指以高速道路网和信息管理系统为基础，利用物流理论进行管理的智能化的物流管理系统。综合利用卫星定位、地理信息系统、物流信息及网络技术有效组织货物运输，提高货运效率。
（6）紧急救援系统（EMS）
• 紧急救援系统是一个特殊的系统，它的基础是ATIS、ATMS和有关的救援机构和设施，通过ATIS和ATMS将交通监控中心与职业的救援机构联成有机的整体，为道路使用者提供车辆故障现场紧急处置、拖车、现场救护、排除事故车辆等服务。
（7）电子收费系统（ETC）
• 使用者在市场购买车载的电子收费装置，经政府指定的部门加装安全模块后即可安装在自己的车上，然后向高速公路公司或银行预交一笔通行费，领到一张内部装有芯片的通行卡（即IC卡），将其安装在自己汽车的指定位置，这样当汽车通过收费站的不停车收费车道时，该车道上安装的读取设备与车上的卡进行相互通信，自动在预交帐户上将本次通行费扣除。
6、ITS智能化的特点体现在哪些方面？
答：（1）交通基础设施智能化；
（2）交通工具智能化；
（3）交通系统智能化。
7、标准化研究对ITS发展的有什么作用？
答：标准化研究对ITS的发展有很大的促进作用，主要表现在以下几点：
（1）经济性。不仅带给用户很大的经济性(如便于维护、避免重复投资等)，对设备供应商也同样具有经济性(如扩大市场)。
（2）互操作性。包括设备（软、硬件）的互换性与兼容性，实现信息共享性。
（3）用户设备获取。有了全国性或全球性标准，用户采购设备就有了很大的自由，而不用局限于某一厂商，对于一些小国或地区更是至关重要。
8、国际ITS标准化组织建立的时间和名称是什么？中国的ITS标准化正式启动的时间和组织是什么？
答：1992年由国际标准化组织（ISO）设置了TC204，即“交通信息与控制系统（TICS）技术委员会”，全面负责ITS领域的标准化工作。标志着ITS标准化组织的建立。
我国科技部2000年成立全国智能交通系统专家委员会，标志着中国ITS标准化组织的正式建立。
9、什么是子午卫星系统？子午卫星系统的组成有哪些？它的缺点表现在什么方面？
答：子午卫星系统，即NNSS – Navy Navigation Satellite System（海军导航卫星系统），由于其卫星轨道都通过地极，故称为子午卫星系统（Transit），它采用利用多普勒效应进行导航定位，也被称为多普勒定位系统。
系统组成包括三部分：
（1）空间部分：
卫星：发送导航定位信号（信号：4.9996MHz ´ 30 = 149.988MHz；4.9996MHz ´ 80 = 399.968MHz；星历）
卫星星座 – 由6颗卫星构成，6轨道面，轨道高度1075km
（2）地面控制部分
包括：跟踪站、计算中心、注入站、控制中心和海军天文台
（3）用户部分
多普勒接收机
它的主要缺点：
l 卫星少，观测时间和间隔时间长，无法实现实时定位；
l 卫星轨道低，难以进行精密定轨
l 卫星信号频率低，不利于补偿电离层折射效应的影响
10、GPS的发展简史
（1）方案论证阶段
• 1973年12月，美国国防部批准研制GPS。
• 1978年2月22日，第1颗GPS试验卫星发射成功。
• 从1973年到1979年，共发射了4颗试验卫星。研制了地面接收机及建立地面跟踪网。
（2）全面研制和试验阶段
• 从1979年到1987年，又陆续发射了7颗试验卫星，研制了各种用途接收机。实验表明，GPS定位精度远远超过设计标准。
（3）实用组网阶段
• 1989年2月14日，第1颗GPS工作卫星发射成功。
• 1991年，在海湾战争中，GPS首次大规模用于实战。
• 1993年底实用的GPS网即（21+3）GPS星座已经建成，今后将根据计划更换失效的卫星。
• 1995年7月17日，GPS达到FOC – 完全运行能力（Full Operational Capability）

11、GPS卫星系统与之前其他导航系统相比，具有什么特点？
答：（1）全球地面覆盖。地球上任何地点均可连续同步观测到至少4颗卫星， 从而保障了全球、全天候连续三维定位。
（2）功能多，精度高。GPS可为各类用户连续地提供动态目标的三维位置、三维速度和时间信息。
（3）实时定位。
12、什么是SA政策？什么是AS政策？
答：SA（Selective Availability ）即降低C/A码定位精度的选择可用性政策，包括对GPS卫星基准信号采用技术即为卫星钟加高频抖动，则所有的派生信号均引入一个快速变化的高频抖动。对导航电文采用技术即降低星历精度，加入随机变化。
AS（Anti-Spoofing）即将P码经过加密处理变成Y码，Y码是p码与高度机密w码 模2求和得到的码，当实施AS技术时，非特许用户不但不能使用P码作实时定位，而且不能进行P码和C/A码码位测量的联合求解，甚至进行P码数据平滑。
13、GPS、GLONASS、GALILEO之间有什么不同，各自有什么特点？ppt第二章23--31

14、GPS的组成主要有哪些，各组成部分的主要设备有哪些？各个部分的作用是什么？ppt 第二章（2）2-21
15、GPS的常用时间系统有哪些？它们之间有什么联系？ppt第二章（2） 25--27

16、常用的GPS坐标系统有哪些？ppt第二章（2）29--38

17、L1载频上的信号结构和L2载频上的信号结构是什么样的？P40-41
答：L1载频上有数据流和两种PRN码分别以同向和正交方式进行调制，信号结构为：
SL!i（t）＝ApiPi（t）cos(wL1t+)+AciCi(t)Di(t)sin(wL1t+)
在L2载频上，只有P码进行BPSK调制，其信号结构为：
SL2i（t）＝BpiPi（t）Di(t)cos(wL2t+)
式中：i为卫星的编号；Api，Aci分别为P码和C/A码信号的振幅；Pi(t),Ci(t)分别为P码和C/A码；
Di（t）为数据流；WL1，WL2为载波L1和L2的角频率；，为信号的起始相位。
18、产生C/A码和P码的m序列具有什么特征？p41－42
答:1、均衡性 2、游程分布；3移位相加特性；4、自相关函数。
19、GPS卫星发送的两种伪随机测距码是什么？是如何产生的？ppt第二章（3）9――15

20、GPS导航电文包括哪些信息？导航电文的基本结构？ppt第二章（3）16－25

21、GPS接收机的基本功能结构图

22、GPS距离观测量的两种观测方式：
（1）测量GPS卫星发射的测距码信号（C/A或P码）到达用户接收机的时间；
（2）测量接收机接收到的具有多普勒频移的载波信号与接收机产生的参考信号之间的相位差。
23、什么是单点定位？有什么优缺点？ppt第二章（4）6－13

24、什么是差分定位？有哪些类型？ppt第二章（4）45――57

25 误差计算中常用的精度因子有哪些？ppt第二章（4）22－23
26、GPS定位的误差来源有哪些？ppt 第二章（4）61－80
27 电子地图数据与导航应用功能之间的关系
车 辆 定 位
地 图 显 示
路 径 规 划
路 线 导 引
地 址 定 位
实时交通数据处理
POI(信息点)
车辆导航系统功能
道路形状数据库
背景数据
拓扑数据
属性数据
电子地图数据库

28、在车辆导航系统中，与数字地图相关的功能有哪些？
地图显示、地址匹配、地图匹配、路径规划，路径引导
• 地图显示是车辆导航系统的重要组成部分，它构成了人机接口的基础，地图显示的成功与否直接影响到用户对产品的印象。为了展示地图的道路信息，地图显示需要依赖数字地图中的道路位置、宽度、级别等属性以及道路附近的各种设施。
• 地址匹配又称为地理编码，即通过给定的经纬度坐标确定地图上街道的地址，或者相反的过程。
• 地图匹配是利用数字地图的路网信息修正车辆定位模块的位置输出，位置修正的前提是车辆在道路上行驶。当定位传感器输出的车辆位置与数字地图的道路存在偏差时，地图匹配算法寻找当前最可能的行驶道路并计算在该道路上的位置。地图的拓扑连接必须是完整正确的，以反映真实道路的情况。
• 路线规划和路线引导更是与数字地图密切相关，它的几乎所有数据来源都是数字地图中的道路信息，如路网的空间分布、几何坐标、拓扑连接、道路平均时速、转向限制等等。
29、路网的基本要素是什么？如何将实际道路网络能够转化成节点—路段模型和路段－链模型？

实际道路网络及对应的节点一路段模型

实际道路 路段一链的道路网络模型
30、车辆导航系统的数字地图和通用数字地图侧重点有什么不同？
首先，地图要素种类不同。道路是车辆导航系统中数字地图数据库需要着重处理的对象，系统不仅仅需要知道每条道路的地理坐标，还需要知道每条道路之间的拓扑关系，尤其是道路交叉口的交通限制情况。因此设计导航数字地图数据库时，要把道路的各种情况表达清楚，同时要有一个高效的访问道路信息的机制，以便可以高效率的进行诸如路线规划，路线引导等功能。路网是一个庞大的系统，包含大量方方面面的信息，对于车辆导航系统来说，应该根据功能需要选择合适的信息进行表达和存储。数字道路地图是导航数字地图数据库的重点和基础，是数字地图的核心内容。
其次，数据层次划分不同。考虑到车辆导航系统的功能要求，以及我国数字地图生产的现状与特点，地图数据层次划分应该强调道路的分层，同时要求能够方便扩展，便于地图的升级维护。
31、地图数据的数字化过程？
数据准备－>（数字化仪状态设置）->地图分块->图纸定向->地图分层->数字化->图像检查与编辑

32、传统地图和数字地图的不同（分层组织）
最初传统的数字地图，没有分层组织组织，一幅图包含有各类不同的信息，如边界、城市、村镇、河流、注记、道路等，在进行某一专题或地理分析时，只注重对某一单项同类对象进行显示和分析，而其他内容不作为分析对象，从直观上给人杂乱的感觉。计算机处理也不方便。
目前的GIS软件都采用分层结构组织地图数据。一般地，矢量数字地图的分层结构采用按图层组织的方法，即把同一类或几类地理要素的信息放在同一个图层，每一个图层存储为一个或一组独立的文件，如图3.9所示，在这组文件中进行叠加显示操作。
33、单图集分层结构的特点，优缺点？ppt第三章（1）38－40页

34、数字道路地图的多图集分层结构的内容和存储。PPt 第三章（1）41－43

35、地图数据库按照功能用途可以分为哪几种数据库类型？各有什么作用？
分析数据库：记录道路数据，主要用于路径搜索；
查询数据库：POI信息，主要用于信息查询；
显示数据库：多边形、区域、点的图形信息，主要用于地图显示。
36、建立网格单元基本思想是什么？
根据地图数据的X和Y方向的最大、最小值，将存储层所覆盖的区域分割成等大的区域单元，区域单元的大小视局部放大的程度而定，一般局部放得越大，区域单元分得越小，相反则大一些。
以区域单元为单位，用“相关区域”法记录地图要素与区域单元间的对应关系，即对每一地图要素，求出要素所覆盖的相关区域单元。这就必须要判断点、线、面要素是否全部或有部分落在该格网单元内。
在这些相关的区域单元中记录该地图要素数据所在数据文件中的存储地址。
37、什么是数字道路地图的空间索引？建立空间索引的目的是什么？目前代表性的有哪些？
空间索引就是指依据空间对象的位置和形状或空间对象间的某种空间关系，按一定的顺序排列的一种数据结构。
空间索引是介于空间操作算法和空间对象之间的一种辅助性措施，其主要目的是对空间数据进行筛选和过滤，从而在进行空间操作时，大量与空间操作无关的空间对象被预先排除，提高空间数据访问的效率，缩短计算时间。
目前的空间索引研究成果比较代表性的有K-D-B树、四叉树、 R-树及其改进型、网格索引等。
38、航位推算（DR）的基本原理是什么？产生定位误差积累的原因主要是什么？减少误差的方法有哪些？ppt第四章（1）4-6

39、常用的GPS/DR组合方案有哪些？各有什么优缺点？ppt第四章（1）7――10

40、什么是地图匹配？基本思想，地图匹配应用的两个基本前题是什么？地图匹配的算法处理过程？ppt第四章（2） 4-6页
地图匹配（MM——Map Matching）是一种纯软件技术的定位修正方法,利用数字化地图信息融合传感器定位数据以产生最佳位置估计的技术就是地图匹配
其基本思想是：将车辆定位轨迹与数字地图中的路网信息联系起来，通过计算车辆行驶轨迹与数字地图中道路的相似性，来确定车辆最可能的行驶路段以及车辆在该路段最大可能的位置。另一方面，还可以利用高精度的数字道路地图来修正定位系统的误差，从而使系统性能得到改善。
应用基于以下假设:
①用于匹配的数字化地图包含高精度的道路位置坐标; （误差<15m）
②被定位车辆正在道路上行驶。
地图匹配算法处理过程
• 一个 完 整 的地图匹配算法包括三个主要的处理过程：
– 即确定误差区域
– 选取匹配路段
– 计算修正结果
• 误差区域指：可能包含车辆真实位置的区域范围，应根据传感器定位结果和误差情况来确定。误差区域内的道路被称为候选路段。地图匹配算法认为其中包含了车辆的真实位置，
• 匹配路段的选取是从候选路段中挑选最有可能的车辆行使路段的过程，挑选的原则依据具体的算法设计而不同，通常的标准是数字地图中的道路形状与车辆轨迹的相似程度。
• 确定匹配路段后，计算车辆在该路段中最可能的位置，并用结果修正原有的定位输出。

41、常用的地图匹配方法有哪些？了解其计算的基本思路。Ppt第四章（2）8――12

42、地图匹配中怎样确定误差区域？Ppt第四章（2）13――17

43、影响地图匹配正确性的因素有哪些？Ppt第四章（2）18

44、什么是匹配度？候选路段的匹配度应该具有的特点是什么？ppt第四章（2）19
匹配度：衡量候选路段是车辆真实行驶路段的可能性大小的程度量。
候选路段的匹配度的定义，应该具有以下特点:
(1 ) 车辆行驶的真实路段的匹配度大于所有其它候选路段的匹配度;
(2) 车辆行驶的真实路段的匹配度大于阀值QT。
45、要有效的进行地图匹配，匹配度Q(k)需要满足的标准？
1) Q ( k)是 递推计算的，应该收敛在有限数值，并且尽量少地受到测量噪声的影响。
2) 真实道路的Q(k)很容易的与其它道路区分开。
46、基于匹配度加权递推的地图匹配算法的设计？ppt第四章（2）25－26
• 考虑到车辆当前行驶的道路在数字地图上并不存在、或者车辆驶出道路的情况，算法中包括两种工作模式:“捕获” 模式和“跟踪” 模式。
– 捕获模式是指正在寻找真实道路。
– 跟踪模式则是跟踪由捕获模式下寻找到的真实路段。跟踪模式包括两个状态:车辆在道路上和车辆在节点处。
– 用md表示算法当前的工作模式，md = 0表示捕获模式and=1表示跟踪模式，用s表示当前车辆状态，s=0表示车辆在道路上，s=l表示车辆在节点处，并设当前位置的候选路段有M个，则地图匹配算法完整的描述如下:

47、根据移动通信的特点与实现方式，在车辆定位系统中应用的移动通信可以归纳为哪些？p129－133
常规通信、集群通信、蜂窝通信、无线数据广播、专业数据通信、卫星通信等。
48、车辆定位系统的多址接入方式有哪几种？各自的特点？p144
（1）固定分配多址方式。特点：在此方式下，用户所占用的资源是固定的，即使某用户不进行数据传输，其它用户也不能石灰岩为其分配的资源。主要有FDMA、TDMA与CDMA三种。
（2）按需分配多址方式。特点：适用于占有时间不固定的动态数据传输用户，当用户需要服务时，由系统内的控制中心分配空闲的信道，服务完成后信道仍可供其它用户使用。该方式需要控制中心进行多用户通信的管理，并占用独立的信道进行动态分配信息的传送。
（3）随机分配多址方式。特点：该方式下，多个用户的数据传输是随机的，不同用户同时进行数据传输时将会引起碰撞。对数据碰撞采取不同的处理手段对应不同的随机多址方式。

49、从实现导航功能的角度看，目前智能车辆导航系统的分类？
自主式（分布式）车辆导航系统，其定位和路径规划等功能全部在车载设备实现
中心决定式导航系统，它的某些功能需要借助通信网络才能实现。

50、路径规划解决的是什么问题？
解决的是：在给定的数字道路地图中寻找从出发地到目的地的最优路线。针对实际应用，可以采用不同的优化标准，如最短行车距离、最少旅行时间、最低通行收费等。
51、图论中许多比较成熟的最短路算法在车辆导航系统中通常不能直接使用的两个方面原因？
在实际应用中的数字道路数据库往往规模庞大，而负责路线规划的导航计算机系统受车载环境和成本限制，处理能力和数据存储资源都十分有限，难以承担苛刻的计算量要求。
在图论中，只要两个顶点之间存在连通的路径，则认为从其中某一顶点经过该路径可到达另一顶点，而在实际交通行为中，不可避免的存在着交叉口延迟。如果选择行驶时间作为优化标准，就使得表示路网的带权有向图不仅弧带权，节点也带权，而且交通管制信息如交叉口转向限制等也普遍存在，这些使得常规的最短路算法难以满足路线规划的要求。
52、什么是最短路径？经典的最短路径算法过程？ppt第六章 5-11
最短路径：就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径。
经典的最短路算法
1、迪杰斯特拉(Dijkstra)算法：
由荷兰数学家E.W.D ijkstra于1959年提出的一个适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从某指定节点到图中所有其他节点的最短路。
迪杰斯特拉(Dijkstra)算法主要思想是：按照路径长度逐点增长的方法构造一棵路径树，从而得到从该树的根节点(即指定起点)到其它所有节点的最短路。
按路径长度递增次序产生最短路径算法：
把V分成两组：
（1）S：已求出最短路径的顶点的集合
（2）V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，
保证：（1）从源点V0到S中各顶点的最短路径长度都不大于
从V0到T中任何顶点的最短路径长度
（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的最短路径长度
T中顶点：从V0到此顶点的只包括S中顶点作中间
顶点的最短路径长度
求最短路径步骤
1）初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
1. 若存在<V0,Vi>，为<V0,Vi>弧上的权值
2. 若不存在<V0,Vi>，为µ
2）从T中选取一个其距离值为最小的顶点W，加入S
3）对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
4） 重复上述步骤，直到S中包含所有顶点，即S=V为止

终点 从V0到各终点的最短路径及其长度
V1

V2

V3

V4

V5

V6

Vj
13
<V0,V1>
8
<V0,V2>
µ
30
<V0,V4>
µ
32
<V0,V6>
V2:8
<V0,V2>
13
<V0,V1>

-------
13
<V0,V2,V3>
30
<V0,V4>
µ
32
<V0,V6>
V1:13
<V0,V1>

-------

-------
13
<V0,V2,V3>
30
<V0,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V3:13
<V0,V2,V3>

-------

-------

-------
19
<V0,V2,V3,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V4:19
<V0,V2,V3,V4>

--------

--------

--------

--------
21
<V0,V2,V3,V4,V5>
20
<V0,V1,V6>
V6:20
<V0, V1,V6>
5
1
6
4
3
2
0
8
5
6
2
30
13
7
17
32
9

• 2、弗洛伊德(Floyd)算法
• 算法思想：逐个顶点试探法
• 求最短路径步骤
– 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为µ
– 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
– 所有顶点试探完毕，算法结束
例
A
C
B
2
6
4
3
11
0 4 11
6 0 2
3 µ 0
初始：
路径：
AB AC
BA BC
CA
0 4 6
6 0 2
3 7 0
加入B：
路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入A：
路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入C：
路径：
AB ABC
BCA BC
CA CAB

53、什么是启发式搜索？基于启发式搜索的最短路径算法主要有哪些？
启发式搜索是基于知识的搜索策略，即通过选定一种估价函数，在搜索过程中的每一步，寻找估价函数数值最高的节点作为下一个搜索节点。
基于启发式搜索的最短路算法有Costed算法、分支界定法、限制搜索区域法、A*算法等，
54、A*算法的基本思想
该算法在选择下一个被检查的节点时，对当前节点距离终点的长度作为估计，评价其处于最优路线上的可能性量度，这样就可以首先搜索可能性较大的节点，从而提高搜索过程的效率。
A*算法的估价函数可表示为：
f '( v) = g( v)+ h '(v )
其中g(v)是从起点到当前顶点，的实际费用的量度，h’(v)是从当前顶点，到终点的最小费用的估计，如果h’(v)= 0 ，即没有利用任何启发式信息，这时的A*算法就变成了普通的Dijkstra算法。h’(v)具体形式的选择取决于路线优化标准，在选择h’(v)时，要满足一个要求，就是不能过高估计当前顶点的最小费用，这被称为可纳性条件，只要启发式函数满足可纳性条件，且原问题存在最优解，则A*算法一定能够计算出最优路径。
A*算法的程序编写原理
如图有如下的状态空间：（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）

　　搜索过程中设置两个表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。具体搜索过程如下：
1） 初始状态：　　　　　　　　　　　　　　　　
　OPEN=[A5]；CLOSED=[]；
2）估算A5，取得搜有子节点，并放入OPEN表中；
　OPEN=[B4，C4，D6]；CLOSED=[A5]
3）估算B4，取得搜有子节点，并放入OPEN表中；
　OPEN=[C4，E5，F5，D6]；CLOSED=[B4，A5]
4）估算C4；取得搜有子节点，并放入OPEN表中；
　OPEN=[H3，G4，E5，F5，D6]；CLOSED=[C4，B4，A5]
5）估算H3，取得搜有子节点，并放入OPEN表中；
　OPEN=[O2，P3，G4，E5，F5，D6]；CLOSED=[H3，C4，B4，A5]
6）估算O2，取得搜有子节点，并放入OPEN表中；
　OPEN=[P3，G4，E5，F5，D6]；CLOSED=[O2，H3，C4，B4，A5]
7）估算P3，已得到解；
55、基于分层地图的搜索算法
• 基于分层地图的路线规划算法对道路网络的分层规则要求具备以下特点和假设:
(1 ) 针对不同的优化标准，层次可以按照道路等级或者预计的行车速度进行划分;
(2 ) 层次细节由高到低逐渐增多，高层次是低层次的子集;
(3 ) 每个层次的道路网络是连通的，对于低层次这是肯定的，在高层次中大部分情况下也是连通的 , 如果不连通，可以通过将低层次中的某些路段提取到高层次中, 使之构成连通的网络。
56、最优路线规划分层搜索算法描述
给定起点s和终点t, i1、j1分别是包含s、t的最高层次，记为Si1 ，Tj1，假设将道路网络划分成N个层次1,2,…，N，则最优路线规划分层搜索算法可以描述为：
1) 如果 i1=j1= N，则s、t都位于最高层网络，直接在N层道路网中计算最短路，结果即最优路线Si1= SN- >Tj1= TN;
2)否则，如果i1< j1，必有i1< N ，找到距离Si最近的上一层的节点Si2，如果i2<j1,继续 寻找距离Si2更上一层的节点，直到寻找到节点Sj1,。
3)如果j1=N,那么分别在第1,2,...,N -1层计算最短路Si1->Si2->… SN-1->SN,在N 层计算最短路SN->Tj1=TN，依次连接最短路，即得最优路径;如果j1< N,且Sj1和Tj1处于第j1层的同一区域，那么分别在第1,2, …，j1层计算最短路Si1-> Si2->,…,Sj1-1->Sj1,Sj1-> Tj1,依次连接最短路，即得最优路径;
4)如果j1<N ·但Sj1和Tj1不在同一区域，那么继续寻找距离Sj1更上一层的节点，寻找 距离Tj1最近的上一层的节点，直到寻找到节点Sip，Tjq满足ip＝jq＝k,且Sk和Tk处于同一区域内，或者k=N为止;
5)然后分别在不同层次的道路网络中计算最短路Si1－> Si2 ,…,Sk-1->Sk,Sk->Tk,Tk->Tk-1,…,Tj2->Tj1,将以上最短路径依次连接起来，就构成了从起 点S到终点T的最优路j径。
对于j1< i1的情况，也按照以上方法进行，这时必须首先向较高层次上溯终点t。
57、自主式导航系统的系统结构
人 机 接 口
地图显示
地图检索
路径规划
路径引导
地图匹配
电 子 地 图 数 据
GPS数据解析
DR传感器数据解析
速率
传感器
角速率传感器
图6-6 车载定位导航系统的系统结构

58、导航系统的功能解析
我在 哪里？
从出发地到目的地的最佳路径
如何到达目的地？
附近有无加油站/停车场？
实时地显示当前位置
路 径 规 划
路 径 引 导
附近设施查询
*电子地图数据
*GPS/DR信号解 析
*地 图 匹 配
*GIS空间分析
*拓扑分析
*检索服务点信息
*GPS/DR信 号 解 析
*地 图 匹 配
*检索道路网络信息
用户的问题
导航系统功能
引用的技术
图６-７导航系统的功能解析

59、典型的自主式车辆导航系统应具备哪些功能？
(1)系统能在90%以上的行程时间里确定车辆的实时位置，与实际位置的偏差应小于20m;
(2)时能够将车辆的实时位置转化为地图坐标，并与道路网相匹配，以提供车辆在路网中最可能的行驶路段以及车辆在路段中的具体位置;
(3)系统能向驾驶员提供以地图为背景的图形化实时车辆位置显示:
(4)系统能接受行驶目的地请求，按照合适的规划标准给出当前位置或者指定位置到达目的地的最佳行驶路线；
（5）系统能根据已经规划好的行车路线产生实时的引导指令，并以文字、图像或语音提示(或者三者混合)的方式提供给驾驶员;
（6）系统能确定车辆当前是否偏离了预定行车路线，并及时作出处理。
（7）能够通过多种方式如分类查询、拼音模糊查询等，检索指定目的地或者兴趣点的位置，也能快速查询指定位置附近的各种兴趣点信息。
60、导航系统设计考虑的几个原则:
1. 可靠性原则:系统要充分适应车载环境的恶劣性，系统必须稳定可靠。
2. 易用性原则:为加强产品的市场需要，系统的操作过程必须尽可能简单方便，硬件接 口 和 软 件 操作简洁明了，用户界面直观友好。
3. 经济性原则:在保证完成实现目标的前提下，尽可能优化方案设计，精简系统的功能 部 件 ， 降 低单位产品的制造成本。
4. 灵活性原则:系统硬件具有可扩展性，系统软件要能够方便地升级，在预期的产品生 命 周 期 内 能够适应市场需求和运行环境的变化。
61、硬件结构和软件结构
图 6.８ 车辆导航系统硬件体系结构

62、自主式车辆导航的软件体现结构
图6－9自主式车辆导航系统软件体系结构

63.在软件体系中采用分层结构使得应用软件具有硬件无关性的两层含义：
一、系统中所有的硬件设备都由操作系统接管，应用程序不直接对硬件进行访问。
二、所有涉及硬件的操作都通过调用标准的API函数来完成。这种无关性极大的增强了应用程序的可移植性，为系统的软、硬件开发、升级和改进带来了方便。

64、操作系统是构建整个软件体系的基础，选择操作系统的要求:
1、 为 满 足系统功能的要求，操作系统应提供良好的图形显示支持和强大的多任务管理 能 力 ;
2、 为 适 应嵌入式硬件系统，操作系统应体积小，可以按用户的要求来增减功能。这样 才 能 最 大 程度地去除不需要的冗余，节省存储空间，同时也要方便用户自己的功能扩展 。
3、从应 用 软 件 开 发的角度考虑，应选择开发平台功能强、共享软件资源丰富、支持多 种 嵌 入 式 硬件的操作系统;
4、从适 应 恶 劣 的 车载环境考虑，操作系统必须能够脱离硬盘，直接从ROM/FLASH中启 动 ， 对 内 存 开 销、存储容量等硬件资源的需求应尽可能低。
5、从用 户 使 用 的 方 便 程度考虑，要求操作系统支持即时关机，另外也要考虑操作系统 的 成 本 。
GPS+ DR +MM组合定位子系统首先在每个采样时刻k=nT由扩展Kalman滤波器处理DR传感器和GPS的量测数据并给出车辆位置估计、行车方向估计以及定位误差估计;然后将滤波器输出的这些最优估计输入到地图匹配模块，由地图匹配算法计算出当前时刻的匹配位置坐标，即为车辆当前的位置输出。
65、GPS+DR＋MM组合定位系统

图6－11 GPS十DR+MM组合定位系统框图

66、路径引导的任务？路线导航子系统与其它模块的相互关系
路线引导则是指挥驾驶员沿着路线规划模块计算的最佳路线行驶的过程，它包括两个任务:一是产生行驶引导指令，二是跟踪车辆在规划路线上的行驶情况。
路线导航子系统与其它模块的相互关系如图6.12所示。

6.12 路 线 导 航 子 系 统与 其 它 模 块 的 相互 作 用
67、当车辆偏离预定的路线，该如何处理？
处理方法：一旦系统确定车辆不再行驶在给定的路线上，系统必须先对驾驶员给出提示，同时在屏幕上只是预定目的地的相对方位，以方面驾驶员能返回原来的路径，当一段时间后车辆仍然没有回到预定路线，则重新规划一条由当前车辆位置通往目的