Academic·Papers l暖圜■圈圜 移动机器人路径规 划技术 的研究现状 与发展趋势水 Current Status and Future Developm ent of M obile Robot Path Planning and Avoidance Obstacle Technology 梁毓 明 1,2 徐 立 鸿 1 (1同济 大 学 电子 与信 息 工程 学 院 ，上 海 201804； 2江 西 理 工 大 学 机 电 工程 学 院 ，赣 州 341000) 摘 要 ：路径规划技术是移动机器人技术研究 中的一个 重要 领域。介绍了移动机器人路径规划技术的分类 ，综 述了基 于模 型的环境 已知的全局路径规划和基于传感器 的环境未知 的局部路径规划 的发展现状 ，指 出了各种方 法 的优点与不足 ；同时分别 探讨 了反应式规划 和慎思规划 、全 局规划 和局部规 划 、传统方法 和新 的智 能方法之 间的结 合状况 ，总结 了有关 路径规划技术的一些新的发展趋势 。 关键词 ：移动机器人 全局路径规划 局部路径规划 单元分解法 滚动窗 口法 Abstract： Path planning technology is one of th e im portant domains in mobile robot technologies’ research．The classifications of mobile robot path planning technology are introduced，an d th e current status of global path planning based on model that the environment of the robot is certain and local path planning based on model that the environment of the robot is uncertain is overall and systematically summarized．In addition，the advantages and disadvantages of these algorith ms are pointed out．Some new trends of path planning technology are indicated through discussing the combination state between reactive planning and deliberate plan ning，global planning and local planning，traditional methods an d new intellective means．At last，th e trend of mobile robo t path plan ning is described． K ey words： mobile robot global path planning local path planning cell decomposition rolling windows O 引 言 世 纪 90年 代 以来 ． 以研 制 高水 平 的 环 境 信 息 传 感 器 和 信 息 处 移 动 机 器 人 的 研 究 始 于 20世 纪 6O年 代 末 期 ．斯 坦 福 研 究 理 技 术 、高 适 应 性 的 移 动 机 器 人 控 制 技 术 、真 实 环 境 下 的 规 划 院研 制 出 了 Shakey自主 移 动 机 器 人 ． 目的 是 研 究 应 用 人 工 智 技 术 为 标 志 ．开展 了移 动机 器 人 更 高 层 次 的 研 究 。近 年来 ．移 动 能技 术 在 复 杂 环 境 下 机 器 人 系 统 的 自主 推 理 、规 划 和 控 制 。 70 机 器 人 技 术 在 工 业 、农 业 航 天及 空 间 探 测 等 许 多 领 域 都 起 到 了 年 代 末 ．随着 计 算 机 的 应 用 和 传 感 技术 的 发 展 ．移 动 机 器 人 研 重 要 的作 用 ．同 时 又 显 示 了广 泛 的 应 用 前 景 ．因 而 成 为 国 际 机 究 出现 了新 的 高 潮 ．特 别 是 80年 代 中 期 ．设 计 和制 造机 器 人 的 器 人 学 术 界 研 究 和 关 注 的 热 点 问题 浪 潮 席 卷 全 世 界 ．一 大 批 世 界 著 名 的 公 司开 始 研 制 移 动 机 器 人 路 径 规 划 是 移 动机 器人 研究 领 域 中的 一 个 重 要 分 支 ．是 指 平 台 ．这 些 平 台主 要 作 为 大 学 实 验 室 及 研 究 机 构 的 移 动 机 器 人 移 动 机 器 人 按 照 某 一 性 能 指 标 搜 索 一 条 从 起 始 状 态 到 目标 状 实 验 平 台 ，从 而 促 进 了 移 动 机 器 人 学 多 种 研 究 方 向 的 出现 。20 态 的 最 优 或 次 优路 径【1】。其 主 要 涉 及 的 问题 包括 ：利 用 获 得 的移 {基 金 项 目 ：国 家 自然 科 学基 金 项 目(60674070)。 作 者 简介 ：粱毓 明 博 士 研 究 生 ，讲 师 。 研 究 方 向 为 智 能 自动 化 、移 动 机 器人 技 术 。 徐 立 鸿 教 授 ，博 士 生 导 师 。研 究 方 向 为 智 能 自动化 。 2009 3l机 电一 体化 35 

圈髓卿 i Academic·Papers 动 机 器人 环 境 信 息建 立 较 为 合 理 的模 型 ．再 用 某种 算 法 寻找 一 点 的 最短 路 径 的 图 ． 即移 动 机 器人 必 须 几 乎 接 近 障碍 物 行 走 。 条 从起 始状 态 到 目标 状 态 的 最 优 或 近 似最 优 的无 碰 撞 路 径 ：能 其 缺 点是 如 果 控 制过 程 中产 生 位置 误 差 ．移 动机 器 人 碰 撞 的 可 够 处 理 环境 模 型 中 的不 确 定 因 素 和路 径跟 踪 中 出现 的误 差 ．使 能 性 会很 高 外 界 物体 对 机 器 人 的影 响 降 到 最 小 ：如 何 利 用 已 知 的所 有 信息 Vomnoi图法 用尽 可 能 远 离 障 碍 物 和 墙 壁 的 路 径 表 示 弧 ， 来 引 导 机器 人 的 动 作 ．从 而得 到相 对 更 优 的 行 为 决 策 。 本 文将 由此 从起 始 节 点 到 目标 节 点 的 路 径将 会 增 长 ：但 采 用 这 种 控制 对 移 动 机 器 人 路 径 规 划 的 一 般 方 法 进 行 分 类 和 较 为 详 细 的 阐 方 式 时 ．即使 产生 位 置 误差 ．移 动机 器 人 也不 会 碰 到 障碍 物 。 述 和 介 绍 ．并 对其 发 展 趋 势做 相 关 的 陈述 。 2．1．2 拓 扑 法 1 移 动 机 器人 路 径 规划 技 术 的 分 类 拓扑 法 fJ． I将 规 划 空 间分 割 成 具 有拓 扑 特 征 子 空 间 ．根 据彼 目前 ．对 移 动机 器 人 路径 规 划 方 法 主要 有 以下 几种 分 类 ： 此 连 通 性 建立 拓 扑 网 络 ．在 网络 上 寻 找 起 始 点 到 目标 点 的 拓扑 (1)根 据 机 器 人对 环 境 信 息 掌 握 的 程 度 和 障碍 物 的不 同 ， 路 径 ．最 终 由拓扑 路 径 求 出 几何 路 径 。拓 扑 法基 本 思 想 是 降维 可 分为 ：① 已知环境下的对静态障碍物的路径规划 ；② 未知环 法 ．即将 在 高 维 几何 空 间 中 求路 径 的 问题 转 化 为低 维 拓 扑 空 间 境下的对静态障碍物的路径规划 ；③ 已知环境下对动态障碍物 中判 别 连 通性 的问 题 其优 点 在 于利 用 拓 扑特 征 大 大缩 小 了搜 的路径规划 ；④未知环境下的对动态障碍物的路径规划。 索 空 间 ，算 法 复杂 性 仅 依 赖 于 障碍 物 数 目 ，理 论 上是 完备 的 ，而 (2)根 据对 环 境 信 息 掌握 的程 度 不 同将 移 动 机 器 人 路 径 规 且 拓 扑 法通 常 不 需要 机 器 人 的 准 确 位置 ．对 于位 置误 差 也 就有 划 分 为 两种 类 型 ：基 于 环 境 先 验完 全信 息 的全 局 路 径 规 划 和 基 了更 好 的鲁 棒 性 ：缺 点 是 建 立 拓 扑 网 络 的 过 程 相 当复 杂 ，特 别 于 传 感 器信 息 的 局 部路 径 规 划 。 在 增 加 障碍 物 时如 何 有 效 地 修 正 已经 存 在 的拓 扑 网 是 有 待解 (3)机 器 人路 径 规 划 方 法 也 可 以大 致 分 为两 类 传 统 方 法 和 决 的 问题 。 智 能 方 法 传 统 路 径规 划 方 法 主 要 有 ：视 图法 、拓扑 法 、自由 空 2．1-3 栅 格 法 间法 、栅 格 法 等 。智 能 方 法 主要 有 ：模糊 逻 辑 算 法 、神 经 网 络法 、 栅 格 法 是 由 HOW DEN W E在 1968年 提 出 的 。栅 格 法 将 遗 传 算 法等 机器 人 工 作环 境 分 解 成一 系列 具 有 二值 信 息 的网 格单 元 ．工作 (4)此 外 ，也 有 如 下 的 分 类 ：基 于 事 例 的学 习 规 划 方 法 ；基 空 间 中障 碍 物 的位 置 和 大 小一 致 ．并 且 在机 器 人 运 动 过程 中 。 于 环 境 模 型 的规 划 方法 ；基 于行 为 的路 径 规划 方 法 。 占该 物 的 位 置 和大 小 不发 生 变 化 用 尺 寸 相 同 的栅 格对 机 器人 上 述 分 类 其 实 质 不 外 乎 是对 全 局 路 径 规 划 方 法 和 局 部 路 的二 维 工 作 空 间进 行 划 分 ．栅 格 的 大小 以机 器 人 自身 的尺 寸 为 径 规 划 方法 进 行 不 同 的 归类 下 面 对这 两 种 方 法 的研 究 现 状 较 准 。若 某 个栅 格 范 围内 不 含任 何 障 碍 物 ．则 称 此 栅格 为 自由栅 为详 细 的 阐述 格 ：反 之 ，称 为 障碍 栅 格 。自由空 间 和 障碍 物 均 可表 示 为 栅格 块 2 移 动 机 器 人路 径 规 划 技 术 的研 究 现 状 的集 成 。栅 格 的标 识 方法 有 两 种 ：直角 坐标 法 和 序号 法 ，多 采用 2．1 全 局 路 径 规 划 四叉树 或八 又树 表 示工 作 环境 ．并 通过 优化 算 法完 成路 径搜 索 。 全 局 路 径 规 划 是 指 根 据 先 验 环 境 模 型 找 出从 起 始 点 到 目 栅 格 法 以栅 格 为 单 位记 录环 境信 息 ．环境 被 量 化 成具 有 一 标 点 的符 合一 定 性 能 的 可行 或最 优 路 径 ．它 涉及 的根 本 问题 是 定 分 辨率 的栅 格 ．栅 格 的 大小 直 接 影 响 着 环境 信 息 存 储 量 的大 世 界 模 型 的表 达 和 搜 寻 策 略 ．即 环 境 建模 和路 径 搜 索 策 略 在 小 和 规划 时 间 的长 短 。栅 格 划分 大 ．环 境 信 息存 储 量小 ，规 划时 此领 域 已经 有 了许 多 成 熟 的方 法 ． 主要 方 法 有 构 型 空 间 法 、拓 间 短 ，但 分 辨 率下 降 ．在 密 集 环 境下 发现 路 径 的 能 力减 弱 ：栅 格 扑 法 、栅 格 法 、自由空 间 法 、单 元分 解 法 等 。 划 分 小 ，环境 分 辨 率 高 ，在 密 集 环境 下 发 现 路 径 的 能力 强 ，但 环 2．1．1 构 型 空 间 法 境 信 息 存 储 量 大 ．规 划 时 间长 ．可 以采 用 改 进 的栅 格 法 弥 补 原 构 型 空 间 法 的 基 本 思 想 是 将 机 器 人 缩 小 为 一 个 点 ．根 据 栅 格 法 的不 足 机 器 人 形 状 和尺 寸 将 障 碍物 进 行 拓 展 。研究 较 成 熟 的 有 可视 图 2．1．4 自由 空 间法 法 [31、切 线 图法 14]和 Voronoi图法 嘲。 自由 空 间 法[81应 用 于 机 器 人 路 径 规 划 ．采 用 预 先 定 义 的如 可 视 图 法 将 所 有 障 碍 物 的 顶 点 和 机 器 人 起 始 点 及 目标 点 广 义 锥形 和 凸 多边 形 等 基 本 形 状构 造 自由空 间 ．并 将 自由 空 间 用 直 线 组 合 相 连 ．要 求 机 器 人 和 障碍 物 各 顶 点 之 间 、目标 点 和 表 示 为 连通 图 ，然 后 通 过搜 索 连 通 图 来 进 行路 径 规 划 。 自由 空 障 碍 物 各 顶点 之 间 以及 各 障 碍 物 顶 点 与 顶 点 之 间 的 连 线 均 不 间 的 构 造 方 法 是 ：从 障碍 物 的 1个 顶 点 开 始 ．依 次作 其 他 顶点 能 穿 越 障 碍 物 ．即直 线 是 “可 视 的 ”．然 后 采 用 某 种 方 法 搜 索 从 的链 接 线 ．删 除 不 必 要 的链 接 线 ．使 得 链 接 线 与 障 碍 物边 界 所 起 始点 到 目标 点 的最 优 路径 ．搜 索 最 优 路 径 的 问题 就 转 化 为 从 围成 的 每一 个 自由空 间都 是 面 积最 大 的 凸多 边 形 ：连 接 各 链接 起 始点 到 目标 点 经 过 这 些 可 视直 线 的 最 短距 离 问题 。 线 的 中点 形 成 的 网 络 图 即为 机 器人 可 自由运 动 的 路线 该 法 比 切 线 图法 用 障碍 物 的 切 线表 示 弧 因 此 是从 起 始 点 到 目标 较 灵 活 ．起 始 点 和 目标 点 的 改 变不 会 造 成 连 通 图 的 重 构 ．但算 36 机 电一体 化 ；跗 3 

Academ i c·Papers瞪 墨哑 法 的 复杂 程 度 与 障 碍 物 的 多 少 成 正 比 ．且 不 是 任 何 情 况 下 都 能 下 的 规划 问题 显 示 出很 大 优 越 性 ．对 于 解 决 用 通 常 的 定 量 方 法 获得 最 短 路 径 2．1．5 单 元 分 解 法 来 说 是 很 复 杂 的问 题 或 当 外 界 只 能 提 供 定 性 近 似 的 、不 确 定 信 息 数 据 时 非 常 有 效 ：但 模 糊 规 则 往 往 是人 们 通 过 经 验 预 先 制 定 单 元 分解 法 将 机 器 人 自 由空 间 划 分 成 许 多 单 元 ．用 一 个 的 ，所 以存 在 着 无 法 学 习 、灵 活 性 差 的 缺 点 。此 外 ．人 的 经 验 不 连通 图表 示 单 元 之 间 的 连 接关 系 当单 元 相 邻 时则 用 结 点 连 接 一 定 完 备 ．输 入量 增 多 时推 理 规 则 或 模 糊 表 会 急剧 膨 胀 起 来 ．进 行 图 搜 索 将 返 回一 个 单 元 序 列 。这 一 序 列 就 表 示 一 条 2．2．3 神 经 网络 方 法 从 起 点 到 终 点 连 续 的 自由路 径 根 据 不 同 的单 元 划 分 原 则 有 两 模 糊 控 制 算 法 有 很 多 优 点 ．但 也 有 固有 的 缺 陷 ：人 的经 验 种 单 元 分 解 法 ：完 全 单 元 分 解 法 和 近 似单 元分 解法 。 不 一 定 完 备 ．输 入 量增 多 时 推 理 规 则 或 者 模 糊 表 会 急 剧 膨 胀 完 全 单 元 分 解 法 是用 障 碍 物 的 边 界 来 生 成 单 元 的边 界 ．单 神 经 网络 法 Il3i则 另辟 蹊径 路 径 规 划 是 感 知 空 间 到 行 为 空 间 的 元 的形 状 是 不 规 则 的 ．划 分 的 单 元 完 全 准 确 地 定 义 了 自由 空 一 种 映 射 映 射关 系 可用 不 同 的 关 系 来 实 现 ．很 难 用 精 确 的数 间 近 似 单 元 分 解 法 是 用 同样 大 小 和 尺 寸 的单 元 划 分 无 障 碍 空 学 方 程 表 示 ．但 采 用 神 经 网络 易 于 表 示 。将 传 感 器 数 据 作 为 网 间 ．通 常 单元 与机 器 人 的 清扫 执 行 器 相 同 大小 ．机器 人 遍 历 每 个 络 输 入 ．由人 给 定 相 应 场 合 下 期 望 运 动 方 向角 增 量 作 为 网络 输 单 元 即完 成 了覆 盖 ．然 而 划分 的单 元 只是 近 似 与清 扫 区 重合 出 ．由 多 个 选 定 位 姿 下 的 一 组 数 据 构 成 原 始 样 本 集 ．经 过 删 除 2．2 局 部 路 径 规 划 重 复 或 者 冲 突样 本 等加 工 处 理 ，得 到 最终 样 本 集 。 局 部 路 径 规 划 方 法 侧 重 考 虑 机 器 人 探 知 的 当 前 局 部 环 境 将 神 经 网络 和 模 糊 数 学 结 合 也 可 实 现 移 动 机 器 人 的 局 部 信 息 ．这 使 机 器 人 具 有 较好 的避 碰能 力 。与全 局 规 划 方 法 相 比 ， 路 径 规 划 先 对机 器 人 传 感 器 信 息 进 行 模 糊 处 理 ．总 结 人 的经 局 部 规 划 更 具 实 时 性 和 实 用 性 ．对 动 态 环 境 具 有 较 强 适 应 能 验 形 成 模 糊 规 则 ：再 把模 糊 规 则 作 用 于 样 本 ．对 神 经 网 络 进 行 力 ：其 缺 点 是 由 于仅 依 靠 局 部 信 息 ．有 时 会 产 生 局 部 极 值 点 或 训 练 。通 过 学 习典 型样 本 ．把 规则 融会 贯 通 ．整 体体 现 出一 个 智 振 荡 ．无 法 保 证 机 器 人 能顺 利 地 到 达 目标 点 局 部 路 径 规划 的 能 。 实 际 中允 许 输 入 值 偏 离 学 习样 本 ．只 要 输 入 接 近 一 个 学 习 主 要 方 法有 人 工 势 场 法 、模 糊 逻 辑 算 法 、神经 网 络 方 法 、遗 传 算 样 本 的输 入 模 式 ．则 输 出 也 就 接 近 该 样 本 输 出 模 式 该 性 质 使 法 、滚 动 窗 口法 等 。 2_2_1 人 工 势 场 法 得 神 经 网络 可 以模 仿 人 脑 在 丢失 部 分 信 息 时 仍 具 有 对 事 物 正 确 的 辨识 力 人 工势 场 法 llU_11I是 由 KHATIB和 KR0GH 提 出 的 一 种 虚 拟 2-2．4 遗 传 算 法 力 法 其 思 想 是 将 目标 点 看 作 吸 引 点 ．障碍 物 看 成 排 斥 点 。机 器 遗 传 算 法 【l4堤：一 种 基 于 自然 选 择 和 自然 遗 传 的 全 局 优 化 人 沿 吸 引点 和排 斥 点 产 生 的 合 力 方 向 运 动 它 构造 一个 叫做 势 算 法 ．是 目前 机 器 人路 径 规 划研 究 中 应 用 较 多 的 一 种 方 法 它 函 数 的标 量 函数 ．使 得 机 器 人 的 目标 位 姿 对 应 于其 最 小 值 ．障 采 用 从 自然 界 选 择 、遗 传 操 作 中抽 象 出来 的 几 个算 子 ：选 择 、交 碍 物 区 域 对 应 于一 些 较 大 的 值 ．在 任 何 其 他 位 置 ．势 函 数 都 是 叉 和 变 异 ．对 参 数 编 码 的字 符 串 进 行 遗 传 操 作 ．每 一 字 符 串 对 向 机器 人 目标 位 姿 单 调 递 减 的 这 样 ．不 论 机 器 人 处 于 自由空 应 于一 个 可 行 解 ．这种 遗 传 操 作 是对 多个 可 行 解组 成 的 群体 进 间 的 任 何 位 置 ．只 要 有 路 径 存 在 ．它 都 能 通 过 势 能 值 的 负 梯 度 行 的 ．故 在 进 化过 程 中 可 以并 行 地 对 解 空 间 的 不 同 区 域 进行 搜 方 向找 到 目标 位 姿 对 应 于 障 碍 物 的 区域 有较 大 的值 可 以保 证 索 ．可使 搜 索趋 于 全 局最 优 解 而不 会 陷 于局 部 极小 解 正 是 由于 生 成 路 径 的无 碰 性 该 法 突 出 的 优 点 是 系统 的路 径 生 成 与控 制 这 种 内 在 的优 良特性 ．遗 传 算 法可 广 泛应 用 于 各种 优 化 问题 直 接 与环 境 实 现 了 闭环 ．结 构 简 单 。计 算 量 小 ，实 时性 好 ，便 于 2．2．5 滚 动 窗 口法 低 层 的实 时 控 制 ．从 而 大 大 加 强 了系 统 的适 应 性 与进 障性 能 ． 滚 动 窗 口法 借 鉴 了 预测 控 制 滚 动 优 化 原 理 ．把 控 制 论 中 因而 广 泛 应 用 于 实 时 避 障 和平 滑轨 迹 控 制 方 面 但 是 人 工 势 场 优 化 和 反 馈 两 种 基 本 机 制 合 理 地 融 为 一 体 ．使 得 整 个 控 制 既 基 法 也 存 在 几 个 主 要 的缺 陷 ：存 在 陷 阱 区 域 ；在 相 近 的 障 碍 物 之 于 模 型 与 优 化 的 ．又 是 基 于 反 馈 的 基 于滚 动 窗 iZl的路 径 规 划 间不 能 发 现 路 径 ；在 障 碍 物 前 振 荡 ；在 狭 窄 通 道 中摆 动 ；当 目标 算 法 的基 本 思 路 ：首 先 进 行 场 景 预 测 ，在 滚 动 的 每 一 步 ，机 器 人 点 附近 处 有 障 碍 物 时 ．机 器 人 无 法 到 达 目标 点 根 据 其 探 测 到 的 局 部 窗 口范 围 内 的 环 境 信 息 ．用 启 发 式 方 法 生 2．2．2 模 糊 逻 辑 算 法 成 局 部 子 目标 ．并 对 动 态 障 碍 物 的 运 动 进 行 预测 ．判 断 机 器 人 模 糊 逻 辑 算 法 ㈦基 于 对 驾 驶 员 的 工 作 过 程 观 察 研 究 得 出 行 进 是 否 可 能 与 动 态 障碍 物相 碰 撞 其 次 机 器 人 根 据 窗 口内 的 驾 驶 员 避 碰 动 作 并 非 对环 境 信 息 精 确 计 算 完 成 的 ．而 是 根 据 模 环 境 信 息 及 预 测 结 果 ，选 择 局 部 规 划算 法 ．确 定 向子 目标 行 进 糊 的 环 境 信 息 ．通 过 查 表 得 到规 划 出 的 信 息 ．实 现 局 部 路 径 规 的 局部 路 径 ．并 依 所 规 划 的局 部 路 径 行进 一 步 ．窗 El相 应 向前 滚 划 ，计 算 量不 大 ，易做 到边 规划 边 跟 踪 ，能 满 足 实 时性 要 求 。 其 动 然 后 在 新 的滚 动 窗 El产生 后 ．根 据 传感 器 所 获 取 的最 新 信 优 点 是 克 服 了 势 场 法 易产 生 的 局部 极 小 问 题 ．对 处 理 未 知环 境 息 ．对 窗 口内的 环境 及 障 碍物 运 动状 况 进 行更 新 。该 方 法 放弃 了 ’ - 鞠 ：；机 电一体 化 37 

圈髓哑 l Academic·Papers 对 全 局所 有 目标 的 过于 理 想 的要 求 ．利 用 机 器人 实 时测 得 的 局 可 以达 到 更 好 的 规划 效 果 。Guldnert171提 出了 三层 控 制 结 构 ．以 部 环 境 信 息 ．以滚 动 方 式 进 行 在 线规 划 ，具 有 良好 的避 碰 能 力 。 全局 规 划作 为 最 高层 ．采 用势 场 方 法 的局 部规 划 为第 二 层 ．最底 但 存 在着 规划 的路 径 是非 最 优 的问 题 ．即存 在局 部 极值 问题 。 层用 航 向角 方法 来进 行 避 障 ，适 合 于杂 乱环 境 中的 路径 规 划 。 3 移 动 机 器 人 路径 规 划 技 术新 的发 展 趋 势 3．传统规划方法 与新 的智能方法之间的结合 随 着 移动 机 器 人 应 用 范 围 的扩 大 ．对 于规 划 技 术 的要 求 也 近年 来 ．一些 新 的智 能 技 术逐 渐 被 引 入 到 路 径规 划 中来 ． 越 来 越 高 ．单 个 规 划 方 法有 时不 能 很 好 地 解 决 某 些 规划 问题 ． 也促 使 了各 种 方法 的融 合 发 展 ，例 如 人 工 势 场 与 神经 网络 、模 所 以新 的 发展 趋 向于 将 多种 方法 相 结 合 ．对此 可从 以下 几 方 面 糊控 制 的结 合 等 。智 能 化 方 法能 模 拟 人 的 经验 ．逼 近 非 线性 ．具 进 行 探 讨 有 自组 织 、自学 习 功 能并 且 具 有 一 定 的 容 错 能力 。这 些 方 法应 1．基 于 反 应式 行 为 规 划 与基 于 慎 思行 为规 划 的 结 合 用 于路 径 规 划会 使 移 动 机 器 人 在 动态 环 境 中更 灵 活 ．更 具 智 能 基 于 行 为 的 路 径 规 划 方 法 是 移 动 机 器 人 路 径 规划 问 题 研 化 KYUN Y【lq的混 合 控 制 结 构 先 用 神 经 网 络对 环 境 进 行 分类 究 中的 一 种 新 动 向 传 统 的基 于 “感 知 — — 建 模— — 规 划 — — 以 避 免 陷 人 局 部 最 小 ．并 建 立 基 于反 应 式 行 为 的 控 制 器 ．再 根 动作 ”的方 法 不 易 建 立 准 确 的 环 境 地 图模 型 ．而 且 很 难 适 应 动 据 势 场法 选 择 一 个特 定 的 反 应 式行 为来 引导 移 动 机 器 人前 进 ． 态 的 、未知 环 境 中 的路 径 规 划 。因 此 人 们 提 出 了反 应 式 的控 制 该结 构有 较 好 的 鲁棒 稳 定 性 ，对 动 态环 境 具 有一 定 的适 应性 。 方 法 反 应式 结 构 是 一 种从 感 知 到动 作 的直 接 映 射 ，机 器 人 能 4 结 束 语 够 对 外 界 环境 变 化 做 出 快速 响应 。基 于 行 为 的方 法 是 反 应方 法 综上 所 述 ．在移 动 机器 人 的 路径 规 划 与避 障技 术 的研 究 方 的扩 展 ．它 将 动 作 分 为 若 干 基 本 行 为 ．复 杂 的行 为 可 由 几 个 简 面 ，无论 是 在研 究 的深度 还 是 广度 上 都 有 了 巨大 的发 展 ．初步 形 单 行 为 按 次 序 构 成 基 于行 为 的方 法 大 体 可 以分 为反 射 式 行 成 了理 论 、算 法 和 应 用 的多 方 位研 究 。但 各 种 方法 都有 优 缺点 ． 为 、反 应 式 行 为 、慎 思行 为 3种 类 型 。反 射 式 行 为 类 似 于青 蛙 的 也没 有 任何 一 种方 法 能适 用 于 任何 场 合 因此 怎样 把 各种 方 法 膝 跳 反 射 ．是 一 种 瞬 间 的 应 激 性 本 能 反 应 ．它 可 以 对 突 发 性 情 的优 点 融合 到 一起 以 达到 更好 的 效果 是一 个 有待 探讨 的 问题 。 况 作 出迅 速 反 应 ．但 该 方 法 不 具 备 智 能 性 ．一 般 是 与 其 他 方 法 随着 科 技 不 断发 展 ．机 器 人 应 用 领 域 还 将 不 断扩 大 机 器 人 结 合 使 用 基 于反 应 式 行 为 的方 法 直接 读 取 传 感 器 数据 来 规 划 工 作 环境 会 更 复 杂 ．移 动机 器 人 路 径 规 划 与 避 障 这一 课 题 领 域 下 一 步 的 动作 ．可 以稳 定 及 时 地 对 不 可 预 知 的 障 碍 和环 境 变 化 还 将 不 断深 入 。在 研究 这 一 领域 时 ．要结 合 以前 的研 究 成果 ，把 作 出反 应 ．但 由于 缺 乏 全 局 环 境 知 识 ．因此 所 产 生 的 动 作 序 列 握 发 展趋 势 ，以实 用 性 作 为 最终 目的 。这 样 就 能 不断 推 动 其 向 可能 不 是 全局 最 优 的 ．不 适 合 于 复 杂 环 境 下 移 动 机 器人 的路 径 前 发 展 规 划 ．机 器 人 的 沿墙 走 行 为 策 略 是 其 典 型 的代 表 。慎 思 行 为 利 用 已知 的全 局 环 境 模 型为 智 能 体 系 统 到 达 某 个 特 定 目标 提 供 参 考 文 献 最 优 动 作 序 列 ．适 合 于 复 杂 静 态 环 境 下 的规 划 ．移 动 机 器 人 在 [1] 李 磊 ，叶 涛 ，谭 民 ，等 ．移 动 机 器 人 技术 研 究 现 状 与 未 来 运 动 中的 实 时重 规 划 就 是一 种 慎 思 行 为 ．机器 人 可 能 出现 倒 退 [J]．机 器人 ，2002，24(5)：475—480． 的动 作 以 走 出危 险 区 域 ．但 由于 慎 思 规 划 需要 一定 的时 间去 执 [2] 蔡 佐 军 ，孙 德 宝 ，秦 元 庆 ，等 ．基 于 构 型 空 问 法 的 机 器 人 路 径规 划 行 。所 以它 对 于 环境 中不 可 预 知 的改 变 反 应 较 慢 。 研 究 [J]．计 算 机 与 数 字 工程 ，2006，34(4)：88-90． 基 于 反 应 式 行 为 的规 划 方 法 在 能 建 立 静 态 环 境模 型 的 前 提 下 可 取 得不 错 的规 划 效果 ．但 它 不 适 合 于 环 境 中存 在 一 些 非 模 型 障 碍 物 (如 桌子 、人 等 )的 情 况 。为 此 。一 些 学 者 提 出 了混 合 控 制 的结 构 ．即 将 慎 思 行 为 与 反 应 式 行 为 相 结 合 ，可 以 较 好 地 解 决 这 种类 型 的问 题 LOW K Hl】61将结 合 两 者 的 混 合控 制 结 构 [3] NEUS M， MAOUCHE S． Motion planning using the modified visibility graph [C]．Conf on Sys Man and Cybem．Tokyo：IEEE Publish Society，1999． [4] DOYLE A B，JONES D I．A tangent based method for robo t path planning A [C]．1994 IEEE International Conference on Robotics and Automation C．San Die go： IEEE Computer Society Press。 运 用 在 不 可预 知 环 境 下 的避 撞 导 航 ．各个 行 为模 块 之 间是 异 步 1994． 运 行 的 ．与 般 的 控 制 结 构 相 比 ，其 规 划 模 块 得 出 的 是 一 系 列 的点 集 而 不 是一 条 完 整 的路 径 ．反 应 式模 块具 有 避 碰 和 目标 制 [5] TAKAHASHI O，SCHILLING R J．Motion planning in a plaIle— using generalized voronoi digrams [J]．IEEE Trans Robotics and 导 的双 重 功 能 Automation，1989，5(2)：143—150． 2．全 局 路 径 规划 与 局 部 路径 规 划 的结合 [6] 袁 曾任 ，高 明．在 动态 环 境 中 移 动机 器 人 导 航 与 避碰 的 一 种 新 全 局 规划 一 般 是 建 立 在 已知 环 境 信 息 的基 础 上 ．适 应 范 围 方法 [J]．机 器 人 ，2000，22(2)：81—88． 相 对 有 限 ：局 部 规 划 能 适 用 于 环 境 未 知 的情 况 ，但 有 时 反 应 速 [7] 马兆 青 ．基 于 栅 格 方 法 的 移 动机 器 人 实 时 导 航 避 障 [J]．机 器 人 ， 度 不 快 ．对 规 划 系 统 品质 的要 求 较 高 ，因 此 如 果 把 两 者 结 合 就 (下 转 第 68页 ) 38 机 电一体 化 l 舶 3 

l Academic·Papers 地 址 { else ，，当 TI~5510 时 钟 CLK 电平 不 为 低 时 等待 ． (+RW ，+ZI) ／／0x80000000 开 始 放 置 除 while((IOOPIN&Ox00004000)!=O)； ∥不读 取 MD 的数 据 Startup．o文 件 之外 文 件 的 变 量 } … … … 1。 )。 4 结束 语 采 用 ARM7核 的 LPC2214并 结 合 高速 TLC5510．实 现 了 (2)LPC2214的 部 分 控 制程 序 如 下 ： 数 码 复 印 机 CCD单 元 图 像 信 号 的 高 速 采 集 存 储 。 设 计 中 ip=(volatile uint8 )AD_ADDR；／／#define AD_ADDR TCD1707D 的 驱 动 频 率 是 2．5 MHz．TLC5510采 样 时 钟 也 选 用 0x81000000把 TLC5510当 成／／LPC2214外 部 的 一 个 8位 的存 储 器 ，不 需要 地 址 操 作 ．就 可 以读 取 当 前 数 据 。 while (count!=constant) ／／constant值 等 于 CCD 的像 元 数 加 上 亚元 数 的 整 数倍 { if((IOOPIN&0x00004000)= =O) ／／TLC5510时 钟 的 是 2．5 MHz，LPC2214外 部 晶 振 是 12 MHz。经 过 内部 的 PLL 锁 相环 4倍 频后 系统 时 钟 为 48 M．可 以满 足 CCD信 号 的高 速 采 集存 储 。但 当 TCDI707D 驱 动频 率 达 到 10 MHz~2_12时 ，系统 采 集存 储 的 数 据通 过 UART上传 到 PC进 行 图像 处 理 后 已经 不 能 准确 地 反 映 原稿 的 图像 ．由于 ARM7核 本 身 速度 的限 制 ，本 系 统 采 集存 储 速 度还 有 一 定 的局 限 性 。 CLK的 低 电平 时读 A／D转 换 值 { B= ； 的 8位 转 换 数 据 ／／读 取 TLC一5510 参 考 文 献 [1]邹 中 民．复 印机 原 理 与 实用 [M]．长 沙 ：湖 南 科学 出版 社 ，1996． shuju[countl=B： ，／存储 到 外 围 SRAM [2]周 立 功 ．ARM 嵌 入 式 系统 基 础 教 程 [M]．北 京 ：北 京 航 空 航 天 大学 里 面 ． 出版 社 ．2005． count++： ／／因 为 RW Base地 址 [3]周 润 景 ，图 雅 ，张 丽 敏 ．基 于 QuartusII的 FPGMCPLD的 数 字 系 为 0x80000000．所 以定 义 的 统 设 计 实 例 [M]．北 京 ：电子 工 业 出 版 社 ，2007． while ((IOOPIN&0x00004000)= =O)；／／数 组 自动 保 存 到 外 [4]杨博雄 ，张晓华 ，傅辉清 ，等．线阵 CCD数据的高速采集与存储 [J]． 围 的 SRAM 里 面 了 } (上接 第 38页 ) 大地 测 量 与 地 球动 力 学 ，2004，24(2)：124—127． 1996，l8(6)：344-348． 2O0o，l3(2)：143—148． [8] BROOKS R A．Solving the Find-path problem by good repre— [14]LIANFANG TIAN，CURTIS COLLINS．An effective robot trajectory sentation of free space [J]．IEEE Trans on Sys Man and Cybem ， planning method using a genetic algorithm[J]．Mechatronics，2OO4， 1983，13(3)：190—197． (14)：455—470． [9] CH0SET H，ACAR E，RIZZI A A， et a1． Exact Cellular [15]席裕庚 ，张纯刚．一类动态不确定环境下机器人的滚动路径规划 Decompositions in Trems of Critical Points of Morse Functions[C]． [J]．自动化 学 报 ．2002。28(2)：161—175． IEEE Intem ational Conference on Robotics and Automation，2000． [16]LOW K H，LEOW W K，ANG JR M H．A hybrid mobile robot archite- [10]KHATIB O．Real—time Obstacle Avoidance for Manipulators and cture with integrated planning an d control [C]．New Yerk：Procee。 Mobile Robots[J]．Robotics Research，1986，5(1)：90—98． dings of the Intern ational Conference on Autonomous Agents，2002． fl1]韩 永 ，刘 国 栋．动 态 环 境下 基 于人 lT势 场 的 移动 机 器 人 运 动 规 [17]GULDNER J，UTKIN VI，BAUER R．Athree—layered hierarachical 划 [J]．机 器 人 ，2006，28(1)：45-49． path control system for mobile robo ts：algorithm and experiments [12]Tu KUO-YANG．Design of fuzzy potential energy(FPE)for control [J】．Robotics Autonom System，1995，14(2—3)：l33—147． of a soccer robot[C]．IEEE Int Conf on Networking，Sensing and [18]KYUN Y，OH S—Y．Hybrid control for autonomous mobile robo t Control，2004． navigation using neural network based behavior mod ules and 『l3 1 SIMON X YANG， MAX MENG．An Efficient Neural Network environment classification [J]．Autonomous Robots，2003，15(2)： Approach to Dynamic Robot Motion Planning[J]．Neural Networks， 1 93-206． 髓 机 电一体 化{20~t9 3