智能车辆导航系统

车 载 GPS定 位 技 术 与 应 用 1、 智 能 车 辆 的 分 类 2、 路 径 规 划 3、 自 主 式 车 辆 导 航 系 统 的 设 计 4、 中 心 决 定 式 车 辆 导 航 系 统 的 设 计第 五 章 智 能 车 辆 导 航 系 统 6.1 智 能 车 辆 导 航 系 统 的 分 类 智 能 车 辆 导 航 系 统 是 集 成 了 自 动 车 辆 定 位 系 统 技术 、 地 理 信 息 系 统 技 术 、 数 据 库 技 术 、 多 媒 体 和现 代 通 信 技 术 等 的 高 科 技 综 合 系 统 。 从 实 现 导 航 功 能 的 角 度 看 ， 目 前 可 分 为 两 大 类 ： 自 主 式 （ 分 布 式 ） 车 辆 导 航 系 统 ， 其 定 位 和 路 径 规 划等 功 能 全 部 在 车 载 设 备 实 现 。 中 心 决 定 式 导 航 系 统 ， 它 的 某 些 功 能 需 要 借 助 通 信 网络 才 能 实 现 。 6.2 路 径 规 划 解 决 的 是 ： 在 给 定 的 数 字 道 路 地 图 中 寻 找 从 出 发 地 到目 的 地 的 最 优 路 线 。 针 对 实 际 应 用 ， 可 以 采 用 不 同 的优 化 标 准 ， 如 最 短 行 车 距 离 、 最 少 旅 行 时 间 、 最 低 通行 收 费 等 。 计 算 道 路 网 络 中 两 点 之 间 的 最 优 路 线 问 题 都 可 以 归 结为 求 解 带 权 有 向 图 的 最 短 路 问 题 。 最 短 路 问 题 最 短 路 径 ： 就 是 指 在 带 权 有 向 图 中 ， 寻 找 从 指 定起 点 到 终 点 的 一 条 具 有 最 小 权 值 总 和 的 路 径 。 6.2.1 经 典 的 最 短 路 算 法 1、 迪 杰 斯 特 拉 (Dijkstra)算 法 ： 由 荷 兰 数 学 家 E.W.D ijkstra于 1959年 提 出 的 一 个 适用 于 非 负 权 值 网 络 的 单 源 最 短 路 算 法 ， 是 目 前 求解 最 短 路 问 题 的 理 论 上 最 完 备 、 应 用 最 广 的 经 典算 法 ， 它 可 以 给 出 从 某 指 定 节 点 到 图 中 所 有 其 他节 点 的 最 短 路 。 迪 杰 斯 特 拉 (Dijkstra)算 法 主 要 思 想 是 ： 按 照 路 径 长 度逐 点 增 长 的 方 法 构 造 一 棵 路 径 树 ， 从 而 得 到 从 该 树 的根 节 点 (即 指 定 起 点 )到 其 它 所 有 节 点 的 最 短 路 。 具 体 做 法 是 ： 设 集 合 S存 放 已 经 求 出 的 最 短 路 径 的 终 点 ，初 始 状 态 时 ， 集 合 S中 只 有 一 个 源 点 V0。 以 后 每 求 得一 条 最 短 路 径 (V0， ， Vk)， 就 将 Vk加 入 到 集 合 S中 ，直 到 全 部 顶 点 都 加 入 S中 为 止 。51 6 4320856 230 13 717329 13长 度最 短 路 径 813192120 按 路 径 长 度 递 增 次 序 产 生 最 短 路 径 算 法 ：1、 把 V分 成 两 组 ：（ 1） S： 已 求 出 最 短 路 径 的 顶 点 的 集 合（ 2） V-S=T： 尚 未 确 定 最 短 路 径 的 顶 点 集 合2、 将 T中 顶 点 按 最 短 路 径 递 增 的 次 序 加 入 到 S中 ， 保 证 ： （ 1） 从 源 点 V0到 S中 各 顶 点 的 最 短 路 径 长 度 都 不 大 于 从 V0到 T中 任 何 顶 点 的 最 短 路 径 长 度 （ 2） 每 个 顶 点 对 应 一 个 距 离 值 S中 顶 点 ： 从 V0到 此 顶 点 的 最 短 路 径 长 度 T中 顶 点 ： 从 V0到 此 顶 点 的 只 包 括 S中 顶 点 作 中 间 顶 点 的 最 短 路 径 长 度 3、 依 据 ： 可 以 证 明 V0到 T中 顶 点 Vk的 最 短 路 径 ， 或 是 从 V0到 Vk的 直 接 路 径 的 权 值 ； 或 是 从 V0经 S中 顶 点 到 Vk的 路 径 权值 之 和 。 求 最 短 路 径 步 骤1、 初 始 时 令 S=V0,T=其 余 顶 点 ， T中 顶 点 对 应 的距 离 值 若 存 在 ， 为 弧 上 的 权 值 若 不 存 在 ， 为 2、 从 T中 选 取 一 个 其 距 离 值 为 最 小 的 顶 点 W， 加 入 S3、 对 T中 顶 点 的 距 离 值 进 行 修 改 ： 若 加 进 W作 中 间 顶点 ， 从 V0到 Vi的 距 离 值 比 不 加 W的 路 径 要 短 ， 则 修改 此 距 离 值4、 重 复 上 述 步 骤 ， 直 到 S中 包 含 所 有 顶 点 ， 即 S=V为止 终 点 从 V0到 各 终 点 的 最 短 路 径 及 其 长 度V1V2V3V4V5V6Vj 1383032V2:8 13-133032V1:13 -13302220V3:13 -192220V4:19 -2120V6:20 51 64320856 230 13 717329 -21-21 每 一 对 顶 点 之 间 的 最 短 路 径 方 法 一 ： 每 次 以 一 个 顶 点 为 源 点 ， 重 复 执 行Dijkstra算 法 n次 方 法 二 ： 弗 洛 伊 德 (Floyd)算 法 2、 弗 洛 伊 德 (Floyd)算 法 算 法 思 想 ： 逐 个 顶 点 试 探 法 求 最 短 路 径 步 骤 初 始 时 设 置 一 个 n阶 方 阵 ， 令 其 对 角 线 元 素 为 0， 若 存 在弧 ， 则 对 应 元 素 为 权 值 ； 否 则 为 逐 步 试 着 在 原 直 接 路 径 中 增 加 中 间 顶 点 ， 若 加 入 中 间 点后 路 径 变 短 ， 则 修 改 之 ； 否 则 ， 维 持 原 值 所 有 顶 点 试 探 完 毕 ， 算 法 结 束 例 A C B2643 11 0 4 116 0 23 0初 始 ： 路 径 ： AB ACBA BCCA0 4 66 0 23 7 0加 入 B： 路 径 ： AB ABCBA BCCA CAB0 4 116 0 23 7 0加 入 A： 路 径 ： AB ACBA BCCA CAB0 4 65 0 23 7 0加 入 C： 路 径 ： AB ABCBCA BCCA CAB 6.2.2 算 法 的 时 间 复 杂 度 估 计 （ 1） 一 个 算 法 的 时 间 复 杂 度 ， 就 是 执 行 该算 法 的 计 算 工 作 量 ， 即 算 法 的 时 间 代 价 。 为 了 能 够 比 较 客 观 的 评 价 一 个 算 法 的 效 率 ， 在 度 量 一 个 算法 的 工 作 量 时 ， 应 该 与 具 体 的 计 算 机 软 硬 件 因 素 无 关 ， 而只 依 赖 于 问 题 的 规 模 n。 1892年 P Bachmann发 明 了 一 种 表 示 函 数 渐 进 特 征 的 方 法 ，称 为 大 O表 示 法 ， 它 的 定 义 为 :当 且 仅 当 存 在 正 整 数 c和 n0，使 得 T(n) cf(n)对 所 有 的 nn0成 立 ， 则 称 该 算 法 的 渐 进时 间 复 杂 度 为 T(n)= O(f(n)， 简 称 时 间 复 杂 度 ， 它 表 示 当问 题 规 模 n充 分 大 时 ， 算 法 的 时 间 复 杂 度 随 n变 化 。 在 使 用 大 O表 示 法 时 ， 需 要 考 虑 关 键 操 作 的 程 序 步数 ， 在 大 多 数 场 合 里 ， 程 序 步 数 与 执 行 频 度 是 一一 对 应 的 ， 如 果 最 后 给 出 的 是 渐 进 值 ， 可 以 直 接考 虑 关 键 操 作 的 执 行 频 度 ， 找 出 其 与 n的 函 数 关 系 ，从 而 得 到 渐 进 时 间 复 杂 度 。 常 见 的 算 法 时 间 复 杂 度 有 ： 常 量 阶 ， 表 示 运 行 时间 与 问 题 规 模 无 关 或 不 超 过 某 一 常 数 ;线 性 阶 ， 表示 运 行 时 间 与 问 题 规 模 呈 线 性 关 系 ， 类 似 的 还 有平 方 阶 、 对 数 阶 、 指 数 阶 等 。 （ 2） 优 化 运 行 数 据 结 构 经 典 Dijkstra算 法 的 核 心 代 码 用 C语 言 实 现 如 下 :算 法 的 时 间 复 杂 度 为 要 降 低 算 法 的 时 间 复 杂 度 ， 关 键 在 于 对 子 循 环 加 以 改进 ， 该 子 循 环 的 目 的 是 从 不 断 变 化 的 V-S集 合 中 ， 找 出 下一 条 最 短 路 径 并 返 回 其 父 节 点 指 针 和 累 计 权 值 ， 如 果 采用 各 个 节 点 在 算 法 中 距 离 源 点 的 最 短 路 径 长 度 来 构 造 优先 级 队 列 ， 将 具 有 较 高 优 先 级 的 节 点 放 在 队 列 的 头 部 ，则 能 有 效 提 高 选 择 V-S集 合 中 最 短 路 径 顶 点 的 效 率 。 引 入 堆 结 构 作 为 优 先 级 队 列 的 存 储 表 示 ， 能 大 大 提 高 运算 效 率 ， k叉 堆 是 一 种 最 普 及 的 堆 结 构 ， 它 把 一 个 关 键 码集 合 K = k0,k1, ， kn-1:中 的 所 有 元 素 按 完 全 k叉 树 的顺 序 存 储 在 一 个 一 维 数 组 中 ， 显 然 该 完 全 k叉 树 的 高 度 为log k(n +k-1)-1， 如 图 6-1是 一 个 四 叉 堆 优 先 级 队 列 及 其对 应 的 完 全 四 叉 树 。 堆 结 构 中 除 了 根 节 点外 的 所 有 其 它 节 点 i的关 键 码 ki必 须 满 足 : ki kparent(i)(或 者ki k parent(i), i = 1,2, n-1 即 某 个 节 点 的 值 不 小于 (不 大 于 )其 父 节 点 的值 ， 这 样 堆 中 最 小 (最大 )元 素 的 值 就 存 放 在根 节 点 中 。 图 6.1 四 叉 堆 及 对 应 的 完 全 四 叉 树 在 Dijkstra算 法 中 需 要 用 到 堆 结 构 的 四 种 操 作 : (1) heapescr eate(h):创 建 堆 h， 其 时 间 复 杂 度 为 O(1); (2) heap-in sert(h,x):在 堆 h中 插 入 一 个 新 数 据 项 x， 其 时 间复 杂 度 为 (logn) ; (3) heap一 delete min(h,x):从 堆 h中 找 到 具 有 最 小 属 性 值 的数 据 项 ， 将 其 删 除 并 作 为 操 作 结 果 返 回 ， 其 时 间 复 杂 度 为O(logn) ; (4) heapsede crease一 key(h,x,value):将 堆 h中 的 数 据 项 x的属 性 值 用 一 个 更 小 的 数 value代 替 ， 其 时 间 复 杂 度 为O(logn)。 k叉 堆 结 构 操 作 的 时 间 复 杂 度 6.2.3启 发 式 搜 索 算 法 启 发 式 搜 索 是 基 于 知 识 的 搜 索 策 略 ， 即 通 过 选 定一 种 估 价 函 数 ， 在 搜 索 过 程 中 的 每 一 步 ， 寻 找 估价 函 数 数 值 最 高 的 节 点 作 为 下 一 个 搜 索 节 点 。 基 于 启 发 式 搜 索 的 最 短 路 算 法 有 Costed算 法 、 分 支界 定 法 、 限 制 搜 索 区 域 法 、 A*算 法 等 ， 利 用 启 发式 信 息 的 有 效 方 法 是 计 算 启 发 式 函 数 ， 该 函 数 估价 每 一 生 成 节 点 处 于 最 佳 路 径 解 上 的 可 能 性 ， 从而 优 先 搜 索 可 能 性 大 的 节 点 ， 达 到 提 高 搜 索 效 率的 目 的 。 6.2.3.1 A*算 法 该 算 法 在 选 择 下 一 个 被 检 查 的 节 点 时 ， 对 当 前 节 点 距 离 终点 的 长 度 作 为 估 计 ， 评 价 其 处 于 最 优 路 线 上 的 可 能 性 量 度 ，这 样 就 可 以 首 先 搜 索 可 能 性 较 大 的 节 点 ， 从 而 提 高 搜 索 过程 的 效 率 ， 如 下 图 所 示 。 6.2.3.1 A*算 法 原 理 简 介 A*（ A-Star)算 法 是 一 种 静 态 路 网 中 求 解 最 短 路 有 效 的 方 法 。 公 式 表 示 为 ： f(n)=g(n)+h(n), 其 中 f(n) 是 从 初 始 点 经 由 节 点 n到 目 标 点 的 估 价 函 数 ， g(n) 是 在 状 态 空 间 中 从 初 始 节 点 到 n节 点 的 实 际 代 价 ， h(n) 是 从 n到 目 标 节 点 最 佳 路 径 的 估 计 代 价 。 保 证 找 到 最 短 路 径 （ 最 优 解 的 ） 条 件 ， 关 键 在 于 估 价 函数 h(n)的 选 取 ： 估 价 值 h(n)实 际 值 , 搜 索 的 点 数 少 ， 搜 索 范 围 小 ， 效 率高 ， 但 不 能 保 证 得 到 最 优 解 。 1)如 果 选 择 最 短 距 离 为 优 化 标 准 ， 那 么 以 顶 点 累 计权 值 d(v)作 为 当 前 顶 点 的 实 际 费 用 ， 以 当 前 顶 点 到终 点 的 欧 式 距 离 d(v)作 为 最 小 费 用 估 计 函 数 ， 那么 顶 点 v的 启 发 式 估 价 函 数 为 : f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)； 这 样 估 价 函 数 f在 g值 一 定 的 情 况 下 ， 会 或 多 或 少的 受 估 价 值 h的 制 约 ， 节 点 距 目 标 点 近 ， h值 小 ， f值 相 对 就 小 ， 能 保 证 最 短 路 的 搜 索 向 终 点 的 方 向进 行 。 明 显 优 于 Dijkstra算 法 的 毫 无 无 方 向 的 向 四周 搜 索 。 估 价 值 与 实 际 值 越 接 近 ， 估 价 函 数 取 得 就 越 好 如 果 选 择 最 少 出 行 时 间 为 优 化 目 标 ， 则 可 定 义 顶 点v的 启 发 式 估 价 函 数 为 其 中 t(v) 为 出 行 时 间 ， d(v)为 从 起 点 到 当 前 顶 点的 最 短 路 径 ， di(v) 为 路 段 i的 长 度 ， Vi(v) 为 路 段 i的 行 驶 速 度 ， V(v) 为 估 计 的 最 大 行 驶 速 度 主 要 搜 索 过 程 伪 代 码 如 下 ： 创 建 两 个 表 ， OPEN表 保 存 所 有 已 生 成 而 未 考察 的 节 点 ， CLOSED表 中 记 录 已 访 问 过 的 节 点 。 算 起 点 的 估 价 值 ; 将 起 点 放 入 OPEN表 ; while(OPEN!=NULL) 从 OPEN表 中 取 估 价 值 f最 小 的 节 点 n; if(n节 点 =目 标 节 点 ) break; for(当 前 节 点 n 的 每 个 子 节 点 X) 算 X的 估 价 值 ; if(X in OPEN) if( X的 估 价 值 小 于 OPEN表 的 估 价 值 ) 把 n设 置 为 X的 父 亲 ; 更 新 OPEN表 中 的 估 价 值 ; /取 最 小 路 径 的 估 价 值 if(X inCLOSE) continue; if(X not inboth) 把 n设 置 为 X的 父 亲 ; 求 X的 估 价 值 ; 并 将 X插 入 OPEN表 中 ; /还 没 有 排 序 /end for 将 n节 点 插 入 CLOSE表 中 ; 按 照 估 价 值 将 OPEN表 中 的 节 点 排 序 ; /实 际 上是 比 较 OPEN表 内 节 点 f的 大 小 ， 从 最 小 路 径 的 节点 向 下 进 行 。 /end while(OPEN!=NULL) 保 存 路 径 ， 即 从 终 点 开 始 ， 每 个 节 点 沿 着 父节 点 移 动 直 至 起 点 ， 这 就 是 要 求 的 路 径 ； 6.2.4 双 向 搜 索 算 法 双 向 搜 索 是 指 ： 除 了 像 普 通 单 向 搜 索 那 样 从 起 点出 发 向 终 点 搜 索 最 优 路 线 外 ， 同 时 还 由 终 点 出 发向 起 点 进 行 反 向 搜 索 。 计 算 某 一 顶 点 对 之 间 的 最 短 路 径 ， 算 法 包 括 两 个部 分 : 第 一 部 分 选 择 一 条 用 于 扩 展 的 路 径 ， 并 扩 展 该 路 径 ； 第 二 部 分 检 查 是 否 己 经 找 到 最 短 路 径 。这 两 步 循 环 进 行 ， 直 到 第 二 步 中 的 条 件 满 足 ， 最 短 路 径 找到 为 止 。 如 果 需 要 计 算 网 络 中 从 起 点 s到 终 点 t之 间 的 最 短 路 径 ， 并 设 S(i)和 T(i)分别 表 示 从 S到 顶 点 i和 顶 点 i到 t的 当 前最 短 路 径 长 度 ， P(i)表 示 从 s到 i的 当前 最 短 路 径 中 顶 点 i的 前 驱 ， Q(i)表 示从 i到 t的 当 前 最 短 路 径 中 顶 点 i的 后 继 ，ds,dt分 别 表 示 从 s,t出 发 的 当 前 最 短 路径 长 度 ， 那 么 双 向 搜 索 算 法 可 以 描 述如 下 : 双 向 搜 索 示 意 图 1) 设 置 初 值 ， 令 6.2.4 基 于 分 层 地 图 的 搜 索 算 法 采 用 多 层 地 图 的 分 级 搜 索 技 术 可 实 现 对 搜 索 空 间 的 控 制 。基 于 分 层 地 图 的 路 线 规 划 算 法 对 道 路 网 络 的 分 层 规 则 要 求具 备 以 下 特 点 和 假 设 : (1 ) 针 对 不 同 的 优 化 标 准 ， 层 次 可 以 按 照 道 路 等 级 或 者 预 计的 行 车 速 度 进 行 划 分 ; (2 ) 层 次 细 节 由 高 到 低 逐 渐 增 多 ， 高 层 次 是 低 层 次 的 子 集 ; (3 ) 每 个 层 次 的 道 路 网 络 是 连 通 的 ， 对 于 低 层 次 这 是 肯 定 的 ，在 高 层 次 中 大 部 分 情 况 下 也 是 连 通 的 , 如 果 不 连 通 ， 可 以通 过 将 低 层 次 中 的 某 些 路 段 提 取 到 高 层 次 中 , 使 之 构 成 连 通的 网 络 。 一 种 分 层 规 则 是 按 网 络 中 的 路 段 等 级 进 行 划 分 ， 如 图 6.4(a)所 示 ， 算 法 在 递 归 运 行 过 程 中 总 是 从 低 层 次 向 高 层 次上 溯 ， 使 得 算 法 运 行 有 时 会 出 现 舍 近 求 远 的 不 可 靠 解 。 可 以 这样 对 分 层 规 则 加 以 修 改 :如 果 两 个 层 次 上 下 毗 邻 ， 则 在 高 层 节 点集 中 存 储 公 共 边 上 的 毗 邻 低 层 次 节 点 ， 如 图 6.4(b)， 这 样 使 得 算法 在 递 归 运 行 过 程 中 ， 能 够 找 到 更 为 合 理 的 高 层 次 邻 近 节 点 ，求 得 的 最 优 路 径 解 更 为 可 靠 时 增 加 了 空 间 存 储 。 6.4 道 路 网 络 的 层 次 划 分 以 构 造 分 层 地 图 搜 索 算 法 ， 给 定 起 点 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， 如 果 i2Si2- SN-1-SN,在 N 层 计 算 最 短 路 SN-Tj1=TN， 依 次 连 接 最 短 路 ， 即得 最 优 路 径 ;如 果 j1 Si2-,Sj1-1-Sj1,Sj1- Tj1,依 次 连 接 最 短 路 ， 即 得 最 优 路 径 ; 4)如 果 j1 Si2 ,Sk-1-Sk,Sk-Tk,Tk-Tk-1,Tj2-Tj1,将 以 上 最 短路 径 依 次 连 接 起 来 ， 就 构 成 了 从 起 点 S到 终 点 T的 最 优 路 j径 。 对 于 j1 i1的 情 况 ， 也 按 照 以 上 方 法 进 行 ， 这 时 必 须 首 先 向较 高 层 次 上 溯 终 点 t。 需 要 注 意 的 是 ， 这 种 分 层 搜 索方 法 在 高 端 层 次 逐 渐 回 溯 ， 如果 按 照 距 离 最 短 的 优 化 标 准 ，那 么 求 得的 最 优 路 线 可 能 并 不 是 真 正 的最 短 路 ， 因 此 是 有 损 算 法 。 但是 一 般 的 驾 驶 员 更 喜 欢 在 等 级高 或 者 速 度 快 的 公 路 上 行 驶 ，这 种 结 果 反 而 是 更 优 的 。 由 于 基 于 分 层 地 图 的 搜 索 方 法 在 起 点 S1和 终 点 T1附 近 寻 找高 一 层 的 邻 近 节 点 S2和 T2， 将 路 线 规 划 过 程 划 分 为 几 个 最短 路 计 算 过 程 ， 从 图 6.5中 可 以 看 出 ， 低 层 次 的 节 点 规 模 庞大 ， 但 其 搜 索 空 间 C2, C3大 大 减 小 ， 而 高 层 次 的 搜 索 空 间C1,虽 然 和 Dijkstra算 法 的 搜 索 空 间 C0接 近 ， 但 其 中 的 节 点数 目 大 大 减 少 ， 从 而 提 高 了 算 法 效 率 。 6.2.6仿 真 试 验 结 果 与 分 析 利 用 Embedded Visual C +编 写 了 最 优 路 线 搜 索 程 序 并 进 行 了仿 真 试 验 。 程 序 分 别 按 5种 方 法 搜 索 最 短 路 径 ， 它 们 是 :传 统Dijkstra算 法 、 应 用 四 叉 堆 运 行 结 构 的 改 进 Dijkstra算 法 、 应 用四 叉 堆 的 A*算 法 、 应 用 四 叉 堆 的 双 向 搜 索 A*算 法 、 应 用 四 又 堆的 双 向 分 层 搜 索 A*算 法 。 机 器 主 频 206MHz， 内 存 32M， 共 进行 了 两 组 试 验 。 第 一 组 采 用 的 数 字 道 路 地 图 是 北 京 市 五 环 以 内 的 城 区 图 ， 共32172个 路 段 ， 12562个 顶 点 ， 按 照 道 路 等 级 将 地 图 分 成 两 层 :主干 道 为 一 层 (高 速 、 环 线 和 快 速 路 )， 普 通 公 路 和 胡 同 为 一 层 。这 组 试 验 中 每 种 方 法 分 别 进 行 了 5次 试 验 ， 它 们 分 别 穿 越 地 图 的约 1/5, 2/5, 3/5, 4/5和 整 个 地 图 ， 即 这 5次 试 验 起 点 和 终 点 的 距 离越 来 越 长 。 第 二 组 采 用 的 是 部 分 全 国 数 字 道 路 地 图 ， 包 含 上 海 城 区 图(28265个 路 段 ， 10832个 顶 点 )、 杭 州 城 区 图 (18765条 路 段 ， 7136个 顶 点 )、 南 京 (22293条 路 段 ， 8471顶 点 )、 宁 波 城 区 图 (20 548条 路 段 ， 8182个 顶 点 )以 及 含 有 高 速 公 路 和 国 道 的 全 国 道 路 地 图(15713条 路 段 ， 6167个 顶 点 )， 每 种 方 法 也 进 行 了 5次 试 验 。 表 6.1北 京 道 路 地 图 中 儿 种 路 线 搜 索 算 法 运 行 时 间 结 果 (单 位 :5)表 6.2全 国 道 路 地 图 中 几 种 路 线 搜 索 算 法 运 行 时 间 结 果 (单 位 :5) 在 引 入 四 叉 堆 运 行 结 构 、A*算 法 、 双 向 搜 索 和分 层 搜 索 后 ， 算 法 的 效率 得 到 了 很 大 提 高 。 特别 是 在 全 国 道 路 地 图 中 ，分 层 搜 索 的 引 入 对 算 法效 率 的 提 高 有 显 著 作 用 。 由 于 分 层 搜 索 在 高 层 搜索 中 忽 略 了 低 层 细 节 ，所 以 最 优 路 线 不 是 最 短路 径 ， 而 是 更 多 的 选 择了 高 层 次 路 网 中 的 主 干道 ， 这 也 符 合 一 般 驾 驶者 的 喜 爱 。 6.3 自 主 式 车 辆 导 航 系 统 的 设 计 人 机 接 口地 图 显 示 地 图 检 索 路 径 规 划 路 径 引 导 地 图 匹 配 电 子 地 图 数 据 GPS 数据解析 DR 传感器数据解析速 率 传 感 器 角 速 率传 感 器图 6-6 车 载 定 位 导 航 系 统 的 系 统 结 构 我 在 哪 里 ？从 出 发 地 到 目 的地 的 最 佳 路 径如 何 到 达 目 的地 ？附 近 有 无 加 油站 /停 车 场 ？ 实 时 地 显 示 当 前 位 置路 径 规 划路 径 引 导附 近 设 施 查 询 *电 子 地 图 数 据*GPS/DR信 号 解 析*地 图 匹 配*GIS空 间 分 析*拓 扑 分 析*检 索 服 务 点 信 息*GPS/DR信 号 解 析*地 图 匹 配*检 索 道 路 网 络 信 息用 户 的 问 题 导 航 系 统 功 能 应 用 的 技 术图 - 导 航 系 统 的 功 能 解 析 6.3.1 系 统 总 体 设 计 设 计 自 主 式 车 辆 导 航 系 统 时 需 要 考 虑 的 具 体 因 素包 括 ： 系 统 的 单 位 成 本 、 所 能 提 供 的 定 位 精 度 、导 航 功 能 的 复 杂 程 度 、 是 否 需 要 无 线 通 信 系 统 以及 是 否 需 要 其 他 特 定 的 功 能 等 。 典 型 的 自 主 式 车辆 导 航 系 统 应 具 备 的 功 能 ： (1)系 统 能 在 90%以 上 的 行 程 时 间 里 确 定 车 辆 的 实时 位 置 ， 与 实 际 位 置 的 偏 差 应 小 于 20m; (2) 能 够 将 车 辆 的 实 时 位 置 转 化 为 地 图 坐 标 ， 并 与道 路 网 相 匹 配 ， 以 提 供 车 辆 在 路 网 中 最 可 能 的 行驶 路 段 以 及 车 辆 在 路 段 中 的 具 体 位 置 ; (3)系 统 能 向 驾 驶 员 提 供 以 地 图 为 背 景 的 图 形 化 实时 车 辆 位 置 显 示 : (4)系 统 能 接 受 行 驶 目 的 地 请 求 ， 按 照 合 适 的 规 划标 准 给 出 当 前 位 置 或 者 指 定 位 置 到 达 目 的 地 的 最佳 行 驶 路 线 ； （ 5） 系 统 能 根 据 已 经 规 划 好 的 行 车 路 线 产 生 实 时的 引 导 指 令 ， 并 以 文 字 、 图 像 或 语 音 提 示 (或 者 三者 混 合 )的 方 式 提 供 给 驾 驶 员 ; （ 6） 系 统 能 确 定 车 辆 当 前 是 否 偏 离 了 预 定 行 车 路线 ， 并 及 时 作 出 处 理 。 （ 7） 能 够 通 过 多 种 方 式 如 分 类 查 询 、 拼 音 模 糊 查询 等 ， 检 索 指 定 目 的 地 或 者 兴 趣 点 的 位 置 ， 也 能快 速 查 询 指 定 位 置 附 近 的 各 种 兴 趣 点 信 息 。 设 计 考 虑 到 以 下 几 个 原 则 : I. 可 靠 性 原 则 :系 统 要 充 分 适 应 车 载 环 境 的 恶 劣 性 ，系 统 必 须 稳 定 可 靠 。 2. 易 用 性 原 则 :为 加 强 产 品 的 市 场 需 要 ， 系 统 的 操作 过 程 必 须 尽 可 能 简 单 方 便 ， 硬 件 接 口 和 软 件 操作 简 洁 明 了 ， 用 户 界 面 直 观 友 好 。 3. 经 济 性 原 则 :在 保 证 完 成 实 现 目 标 的 前 提 下 ， 尽可 能 优 化 方 案 设 计 ， 精 简 系 统 的 功 能 部 件 ， 降 低 单 位 产 品 的 制 造 成 本 。 4. 灵 活 性 原 则 :系 统 硬 件 具 有 可 扩 展 性 ， 系 统 软 件要 能 够 方 便 地 升 级 ， 在 预 期 的 产 品 生 命 周 期 内 能够 适 应 市 场 需 求 和 运 行 环 境 的 变 化 6.3.2 导 航 计 算 机 系 统 设 计 硬 件 结 构 设 计 图 6. 车 辆 导 航 系 统 硬 件 体 系 结 构 导 航 计 算 机 是 车 辆 导 航 系 统 硬 件 体 系 的 核 心 部 分 ， 导 航 计 算 机的 设 计 要 求 符 合 下 列 要 求 : 具 有 复 杂 高 速 的 运 算 能 力 ， 满 足 地 图 刷 新 、 定 位 计 算 、 路 线引 导 等 具 有 较 高 实 时 性 要 求 的 计 算 任 务 ; 具 有 大 容 量 的 程 序 存 储 器 (Flash)和 动 态 随 机 存 储 器(SDRAM)， 满 足 操 作 系 统 的 运 行 要 求 以 及 显 示 缓 存 的 要 求 ; 具 有 便 携 式 的 可 移 动 存 储 介 质 ， 满 足 地 图 数 据 升 级 更 新 方 便的 要 求 ; 具 有 高 清 晰 度 的 彩 色 显 示 能 力 ， 满 足 图 形 文 字 显 示 的 要 求 ，且 要 求 显 示 接 口 标 准 规 范 ， 与 其 它 娱 乐 系 统 的 显 示 兼 容 ; 具 有 语 音 输 出 的 能 力 ， 能 够 实 现 语 音 引 导 和 操 作 提 示 ; 具 有 各 种 串 行 接 口 ， 能 够 与 定 位 模 块 、 无 线 通 信 模 块 、控 制 系 统 等 连 接 ， 同 时 具 有 IO扩 展 以 及 AD扩 展 的 能 力 ， 满 足 系 统 控 制 外 设 以 及 升 级 的 要 求 ; 最 后 还 要 求 整 个 系 统 稳 定 可 靠 ， 连 接 牢 固 ， 满 足 车 载 环境 的 恶 劣 要 求 。 硬 件 系 统 一 般 采 用 嵌 入 式 计 算 机 设 计 方 案 ， 如 图 6. 所 示 中 央 处 理 采 用 的 是 基 于 ARMv4内 核 的 Intel公 司 的StrongARM. SA1110， 除 了 采 用 高 性 能 的 CPU以 外 ， 连同 32M的 SDRAM和 32M的 FLASH一 起 构 成 了 系 统 内 核 ; 同 时 ， 计 算 机 系 统 还 具 有 SID13806构 成 的 多 模 式 2D显示 加 速 模 块 ; 由 X3032, 16244,16245构 成 的 总 线 缓 冲 模 块 ; 162374构 成 的 板 上 状 态 /控 制 寄 存 器 ; 语 音 输 出 功 能 由 Philips公 司 的 UCB 1300来 实 现 ， 它 的 语音 处 理 功 能 可 以 实 现 录 音 和 放 音 ， 而 月 利 用 它 的 AD功能 能 监 控 主 板 上 的 电 压 和 温 度 ; 通 过 系 统 总 线 ， 将 两 路 UART串 口 ， 多 路 GPIO信 号 以 及UCB 1300提 供 的 触 摸 屏 /AD信 号 集 成 起 来 。 图 6 .9 基 于 IntelStrong ARM SA1110 的 导 航 计 算 机 结 构 6.3.3 软 件 体 系 设 计 根 据 系 统 功 能 的 要 求 ， 整 个 软 件 有 两 大 部 分 :操 作系 统 和 应 用 程 序 。 图 6 9自 主 式 车 辆 导 航 系 统 软 件 体 系 结 构 在 软 件 体 系 中 采 用 分 层 结 构 使 得 应 用 软 件 具 有 硬 件 无 关 型 ，即 不 依 赖 与 具 体 硬 件 的 独 立 性 。 无 关 性 有 两 层 含 义 ： 一 、 系 统 中 所 有 的 硬 件 设 备 都 由 操 作 系 统 接 管 ， 应 用 程序 不 直 接 对 硬 件 进 行 访 问 。 二 、 所 有 涉 及 硬 件 的 操 作 都 通 过 调 用 标 准 的 API函 数 来完 成 。 这 种 无 关 性 极 大 的 增 强 了 应 用 程 序 的 可 移 植 性 ， 为 系 统的 软 、 硬 件 开 发 、 升 级 和 改 进 带 来 了 方 便 。 操 作 系 统 是 构 建 整 个 软 件 体 系 的 基 础 目 前 比 较 成 熟 的 操 作系 统 有 很 多 ， 其 中 嵌 入 式 操 作 系 统 随 着 计 算 机 技 术 的 发 展也 出 现 了 很 多 种 ， 比 较 有 名 的 有 Embedded Linux, Windows CE, VxWorks, Palm os等 等 。 这 些 操 作 系 统 各 有所 长 ， 支 持 的 CPU以 及 函 数 功 能 也 各 不 相 同 。 选 择 操 作 系 统 的 要 求 : 1、 为 满 足 系 统 功 能 的 要 求 ， 操 作 系 统 应 提 供 良 好 的 图 形 显示 支 持 和 强 大 的 多 任 务 管 理 能 力 ; 2、 为 适 应 嵌 入 式 硬 件 系 统 ， 操 作 系 统 应 体 积 小 ， 可 以 按 用户 的 要 求 来 增 减 功 能 。 这 样 才 能 最 大 程 度 地 去 除 不 需 要的 冗 余 ， 节 省 存 储 空 间 ， 同 时 也 要 方 便 用 户 自 己 的 功 能 扩 展 。 3、 从 应 用 软 件 开 发 的 角 度 考 虑 ， 应 选 择 开 发 平 台 功 能 强 、共 享 软 件 资 源 丰 富 、 支 持 多 种 嵌 入 式 硬 件 的 操 作 系 统 ; 4、 从 适 应 恶 劣 的 车 载 环 境 考 虑 ， 操 作 系 统 必 须 能 够 脱 离 硬盘 ， 直 接 从 ROM/FLASH中 启 动 ， 对 内 存 开 销 、 存 储 容 量等 硬 件 资 源 的 需 求 应 尽 可 能 低 。 5、 从 用 户 使 用 的 方 便 程 度 考 虑 ， 要 求 操 作 系 统 支 持 即 时 关机 ， 另 外 也 要 考 虑 操 作 系 统 的 成 本 。 Windows CE是 美 国 微 软 公 司 开 发 的 专 门 为 各 种 移 动和 便 携 移 动 电 子 设 备 、 个 人 信 息 产 品 、 消 费 类 电 子产 品 等 有 严 格 资 源 限 制 的 硬 件 系 统 设 计 的 一 种 32位高 性 能 嵌 入 式 操 作 系 统 ， 它 有 一 个 简 洁 、 高 效 的 完全 抢 占 式 多 任 务 内 核 ， 支 持 强 大 的 通 信 和 图 形 显 示功 能 ， 能 够 适 应 广 泛 的 系 统 需 求 。 Windows CE系 统 的 主 要 特 点 包 括 （ 5点 ） 1)兼 容 于 微 软 公 司 的 视 窗 (Windows)电 脑 操 作 系 统 ， 支 持 多 种应 用 程 序 编 程 接 口 (Win3 2 A PI)函 数 ; 2)提 供 最 广 泛 的 硬 件 支 持 ， 包 括 通 信 接 口 、 高 分 辨 率 真 彩 色显 示 和 打 印 设 备 、 输 入 输 出 设 备 、 音 频 设 备 、 网 络 和 存 储设 备 等 ; 3)支 持 数 十 种 不 同 的 32位 微 处 理 器 芯 片 ， 如 :Intel和 AMD公司 的 x86系 列 、 摩 托 罗 拉 公 司 的 PowerPC、 日 立 公 司 的 SH3系 列 、 东 芝 公 司 的 MIPS系 列 等 ; 4)采 用 模 块 化 结 构 ， 配 置 灵 活 ， 运 行 时 仅 需 很 少 的 存 储 器(RAM)资 源 ， 并 且 可 以 直 接 从 只 读 存 储 器 (ROM)中 启 动 和运 行 ; 5)微 软 公 司 为 Windows CE的 开 发 提 供 了 一 套 完 整 的 功 能 强大 的 系 列 工 具 ， 从 硬 件 调 试 到 软 件 开 发 都 为 用 户 提 供 了 方便 。 Windows CE是 目 前 最 强 大 的 嵌 入 式 操 作 系 统 ， 所 提 供 的 功能 包 括 系 统 与 应 用 程 序 的 初 始 化 与 同 步 管 理 、 内 存 管 理 和分 配 、 系 统 时 钟 管 理 、 设 备 驱 动 管 理 、 程 序 进 程 间 通 信 和数 据 交 换 控 制 、 磁 盘 和 文 件 系 统 操 作 与 管 理 等 ， windows CE操 作 系 统 是 车 辆 导 航 系 统 应 用 软 件 运 行 的 理 想 平 台 。 Embedded Linux的 开 放 源 码 特 性 ， 它 的 可 移 植 性 和 可 扩 展性 提 供 了 最 大 的 灵 活 度 。 但 开 发 工 作 量 很 大 ， 目 前 还 没 有一 家 能 给 出 一 套 从 硬 件 到 软 件 的 完 善 的 开 发 调 试 系 统 。Linux在 图 形 功 能 的 支 持 上 也 差 强 人 意 。 长 远 来 看 ， Linux的 公 开 和 免 费 ， 使 它 具 有 强 大 的 生 命 力 ， 它 的 功 能 也 会 在众 多 开 发 者 的 努 力 下 日 臻 完 善 。 6.3.4 功 能 子 系 统 设 计 1、 定 位 子 系 统 定 位 子 系 统 是 车 辆 导 航 系 统 的 重 要 组 成 部 分 ， 它 包 括定 位 模 块 和 地 图 匹 配 模 块 ， 为 满 足 高 精 度 连 续 车 辆 定位 的 要 求 ， 最 佳 的 定 位 方 式 是 组 合 定 位 。 考 虑 到 整 个 系 统 的 不 同 成 本 和 档 次 ， 以 及 安 装 的 复 杂程 度 ， 在 设 计 定 位 子 系 统 时 在 不 同 的 系 统 中 采 取 了 不同 的 组 合 定 位 方 案 ， 一 种 是 GPS+MM， 为 了 便 于 功能 升 级 ， 预 留 了 DR接 口 ， 另 一 种 是 GPS十 DR+MM。如 下 页 图 6 11所 示 。 图 6 11 GPS十 DR+MM组 合 定 位 系 统 框 图GPS+ DR +MM组 合 定 位 子 系 统 首 先 在 每 个采 样 时 刻 k=nT由 扩 展 Kalman滤 波 器 处 理DR传 感 器 和 GPS的 量 测 数 据 并 给 出 车 辆 位置 估 计 、 行 车 方 向 估 计 以 及 定 位 误 差 估 计 ;然 后 将 滤 波 器 输 出 的 这 些 最 优 估 计 输 入 到 地图 匹 配 模 块 ， 由 地 图 匹 配 算 法 计 算 出 当 前 时刻 的 匹 配 位 置 坐 标 ， 即 为 车 辆 当 前 的 位 置 输出 。 2、 导 航 子 系 统 导 航 子 系 统 负 责 完 成 车 辆 导 航 功 能 ， 包 括 路 线 规 划 和 路 线 引导 ， 前 面 已 经 讨 论 了 论 了 路 线 规 划 算 法 的 设 计 与 实 现 ， 而 路线 引 导 则 是 指 挥 驾 驶 员 沿 着 路 线 规 划 模 块 计 算 的 最 佳 路 线 行驶 的 过 程 ， 它 包 括 两 个 任 务 :一 是 产 生 行 驶 引 导 指 令 ， 二 是 跟踪 车 辆 在 规 划 路 线 上 的 行 驶 情 况 。 路 线 导 航 子 系 统 与 其 它 模块 的 相 互 关 系 如 图 6.12所 示 。 6.12 路 线 导 航 子 系 统 与 其 它 模 块 的 相 互 作 用 图 6 13 表 示 了 一 种 引 导 生 成 算 法 ， 其 中 的 角 度 标 注 代 表两 条 相 邻 路 段 在 交 叉 点 处 的 取 向 角 差 值 ， 顺 时 针 为 正 ； 路段 取 向 角 定 义 为 路 段 取 向 与 正 北 方 向 的 差 值 ， 取 值 为 0360度 ， 引 导 指 令 产 生 后 就 是 实 时 监 视 车 辆 在 预 定 路 径 上 的行 驶 情 况 ， 以 确 定 什 么 时 候 向 用 户 输 出 引 导 信 息 。 将 引 导 信 息 分 为 三 种 :早 期 提 示 、 准 各 提 示 和 到 达 提 示 。 早 期 提 示 在 车 辆 通 过 上 一 交 叉 路 口 后 给 出 ， 通 知 驾 驶 员在 下 一 个 路 口 所 要 采 取 的 操 作 ; 准 备 提 示 在 车 辆 进 入 距 路 口 一 定 范 围 内 的 区 域 时 给 出 ，提 示 驾 驶 员 做 好 操 作 准 备 ， 注 意 路 标 、 出 日 标 记 等 有 关交 通 标 志 。 到 达 提 示 通 知 驾 驶 员 已 经 接 近 交 叉 路 口 ， 注 意 执 行 引 导指 令 。 动 态 导 航 的 另 一 个 重 要 内 容 是车 辆 偏 离 预 定 的 路 径 。 处 理 方法 ： 一 旦 系 统 确 定 车 辆 不 再 行驶 在 给 定 的 路 线 上 ， 系 统 必 须先 对 驾 驶 员 给 出 提 示 ， 同 时 在屏 幕 上 只 是 预 定 目 的 地 的 相 对方 位 ， 以 方 便 驾 驶 员 能 返 回 原来 的 路 径 ， 当 一 段 时 间 后 车 辆仍 然 没 有 回 到 预 定 路 线 ， 则 重新 规 划 一 条 由 当 前 车 辆 位 置 通往 目 的 地 的 最 佳 行 车 路 线 。 3、 人 机 接 口 一 个 完 整 的 车 辆 导 航 系 统 ， 必 须 具 有 良 好 的 人 机 接 口 ， 它 提 供 用户 与 导 航 设 备 的 交 互 。 地 图 与 车 辆 位 置 显 示 、 路 线 规 划 、 路 线 引导 和 其 它 活 动 的 各 种 不 同 要 求 通 过 人 机 接 口 传 送 到 计 算 机 ， 并 且反 馈 给 用 户 。 人 机 接 口 包 括 两 个 部 分 :输 入 控 制 部 分 和 输 出 部 分 ，其 中 有 些 接 口 与 其 它 汽 车 电 子 产 品 是 兼 容 和 共 享 的 。 （ 1） 输 出 接 口 输 出 接 口 是 向 用 户 提 供 与 车 辆 导 航 功 能 等 相 关 的 信 息 手 段 ，视 频 和 音 频 接 口 是 两 种 最 常 用 和 有 效 的 手 段 ， 因 此 在 设 计 输 出 接口 时 ， 可 以 采 用 高 清 晰 的 真 彩 TFT LCD显 示 器 ， 车 辆 行 进 过 程中 某 一 时 刻 显 示 器 提 供 的 可 视 内 容 包 括 :彩 色 数 字 地 图 ， 车 辆 的位 置 点 ， 车 辆 行 驶 方 向 ， 当 前 行 驶 的 道 路 名 称 ， 最 优 路 线 的 突 出显 示 ， 路 线 引 导 过 程 中 的 文 字 和 图 像 提 示 (如 拐 弯 方 向 ， 重 要 单位 等 )， 到 达 目 的 地 和 下 一 个 提 示 交 叉 口 的 距 离 提 示 等 等 。 为 了 避 免 分 散 驾 驶 员 的 注 意 力 ， 从 而 影 响 安 全 驾 驶 ， 因 此 系 统还 应 该 具 有 语 音 输 出 ， 并 且 语 音 输 出 的 内 容 简 短 而 有 效 ， 主 要内 容 包 括 :操 作 提 示 、 路 线 引 导 指 令 、 超 速 提 醒 、 当 前 车 辆 行 驶道 路 或 重 要 兴 趣 点 提 示 等 。 （ 2） 输 入 接 口 在 设 计 车 辆 导 航 系 统 的 输 入 控 制 系 统 时 ， 主 要 强 调 安 全 和 操 作方 便 ， 首 先 是 提 供 多 种 操 作 控 制 方 式 ， 包 括 红 外 遥 控 、 按 键 和触 摸 操 作 方 式 ， 任 用 户 选 择 使 用 ， 其 次 简 化 各 个 功 能 的 操 作 过程 。 （ 3） 导 航 和 娱 乐 共 享 部 件 近 些 年 来 ， 汽 车 信 息 电 子 设 备 发 展 迅 速 ， 它 们 现 在 已 经 被 集 成到 车 辆 结 构 中 ， 作 为 复 杂 电 路 的 组 成 部 分 ， 如 汽 车 音 响 、 汽 车VCD/DVD等 ， 因 此 车 辆 导 航 系 统 的 人 机 接 口 要 求 标 准 规 范 ，例 如 视 频 设 备 既 可 以 用 来 显 示 导 航 地 图 与 信 息 ， 也 可 以 用 来 显示 VCD/DVD图 像 或 者 TV;存 储 设 备 既 可 以 用 来 存 储 地 图 ， 也 可以 用 来 存 储 MP3音 乐 等 。 将 车 辆 导 航 系 统 与 这 些 汽 车 娱 乐 设 备 集 成 到 一 体 也 是 汽 车 电 子 信 息 产 品 的 一 个 发 展 趋 势 。 6.4 中 心 决 定 式 车 辆 导 航 系 统 的 设 计 中 心 决 定 式 车 辆 导 航 系 统 具 有 的 特 点 ：（ 1） 利 用 信 息 点 指 令 处 理 机 制 来 实 现 终 端 的 多 种 功 能 。（ 2） 终 端 不 需 要 存 有 地 图 数 据 ， 节 省 了 大 量 的 存 储 资 源和 运 算 资 源 。（ 3） 路 径 规 划 在 中 心 进 行 。（ 4） 能 够 提 供 信 息 采 集 、 信 息 服 务 等 多 种 增 值 服 务 功 能 。（ 2） 具 备 成 为 车 辆 导 航 器 、 车 辆 黑 匣 子 的 硬 件 平 台 的 能力 。 6.4.1 系 统 组 成 及 原 理 三 大 部 分 组 成 ： 控 制 中 心 、 车 载 导 航终 端 通 信 网 以 GPRS作为 通 信 系统 组 成 如图 6 13所示 。 控 制 中 心 主 要 由 网 络 服 务 器 、 数 据 库 、 显 示 终 端 组 成 。 完 成 功 能 ： 指 令 下 载 、 信 息 点 数 据 管 理 、 实 时 监 视 、 路径 导 航 等 功 能 。 车 载 导 航 终 端 主 要 由 嵌 入 式 处 理 器 模 块 和 GPS模 块 、GPRS模 块 等 组 成 ， 且 包 含 一 个 独 特 的 指 令 系 统 ， 根 据信 息 点 指 令