logo资料库

一类用于井下路径规划问题的Dyna_Q学习算法.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：1.49M 资料格式：pdf 举报 版权申诉
第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
资料共6页，全文预览结束
    　第１２期 　２０１２年１２月 工 矿 自 动 化 Ｉｎｄｕｓｔｒｙ　ａｎｄ　Ｍｉｎｅ　Ａｕｔｏｍａｔｉｏｎ Ｎｏ．１２　 Ｄｅｃ．２０１２　 文章编号：１６７１－２５１Ｘ（２０１２）１２－００７１－０６ 朱美强，李明，张倩．一类用于井下路径规划问题的 Ｄｙｎａ＿Ｑ 学习算法［Ｊ］．工矿自动化，２０１２（１２）：７１－７６． 一类用于井下路径规划问题的 Ｄｙｎａ＿Ｑ 学习算法 朱美强，　李明，　张倩 （中国矿业大学信电学院，江苏 徐州　２２１１１６） 　　摘要：在基于目标的强化学习任务中，欧氏距离常用于 Ｄｙｎａ＿Ｑ 学 习 的 启 发 式 规 划 中，但 对 于 井 下 救 援 机器人路径规划这类状态空间在欧氏空间内不连续 的任务 效果 不理想。针对该 问 题，文 章 引 入 流 形 学 习 中 计算复杂度较低的拉普拉斯特征映射法，提出了一种基于流形距离度量的改进 Ｄｙｎａ＿Ｑ 学习算法，并在类似 于井下环境的格子世界中进行了仿真研究。仿真结果验证了该算法的有效性。 关键词：Ｄｙｎａ＿Ｑ 学习；欧氏距离；启发式规划；路径规划；拉普拉斯特征映射；流形距离 　　中图分类号：ＴＤ６７　　　文献标志码：Ａ　　　网络出版时间：２０１２－１１－２９　１５：３０ 　　网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／３２．１６２７．ＴＰ．２０１２１１２９．１５３０．０１９．ｈｔｍｌ Ａ　Ｄｙｎａ＿Ｑ－ｌｅａｒｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｕｓｅｄ　ｉｎ　Ｕｎｄｅｒｇｒｏｕｎｄ　Ｐａｔｈ　Ｐｌａｎｎｉｎｇ ＺＨＵ　Ｍｅｉ－ｑｉａｎｇ，　ＬＩ　Ｍｉｎｇ，　ＺＨＡＮＧ　Ｑｉａｎ （Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　ｏｆ　ＣＵＭＴ．，Ｘｕｚｈｏｕ　２２１１１６，Ｃｈｉｎａ） 　　Ａｂｓｔｒａｃｔ：Ｔｈｅ　Ｅｕｃｌｉｄｅａｎ　ｄｉｓｔａｎｃｅ　ｉｓ　ｕｓｕａｌｌｙ　ｕｓｅｄ　ｉｎ　ｈｅｕｒｉｓｔｉｃ　ｐｌａｎｎｉｎｇ　ｏｆ　Ｄｙｎａ＿Ｑ－ｌｅａｒｎｉｎｇ　ｂａｓｅｄ　ｏｎ ｒｅｉｎｆｏｒｃｅｍｅｎｔ　ｌｅａｒｎｉｎｇ　ｔａｓｋｓ　ｏｆ　ｇｏａｌ　ｐｏｓｉｔｉｏｎ．Ｂｕｔ　ｉｔ　ｉｓ　ｎｏｔ　ｓｕｉｔａｂｌｅ　ｆｏｒ　ｔｈｅｓｅ　ｔａｓｋｓ　ｗｈｏｓｅ　ｓｔａｔｅ　ｓｐａｃｅ　ｉｓ　ｎｏｔ ｃｏｎｔｉｎｕｏｕｓ　ｉｎ　Ｅｕｃｌｉｄｅａｎ　ｓｐａｃｅ　ｓｕｃｈ　ａｓ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｏｆ　ｄｉｓａｓｔｅｒ　ｒｅｓｃｕｅ　ｒｏｂｏｔ　ｉｎ　ｕｎｄｅｒｇｒｏｕｎｄ　ｃｏａｌ　ｍｉｎｅ．Ｆｏｒ ｔｈｅ　ｐｒｏｂｌｅｍ，ｔｈｅ　ｐａｐｅｒ　ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　Ｌａｐｌａｃｉａｎ　Ｅｉｇｅｎｍａｐ　ｗｈｏｓｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｉｓ　ｌｏｗｅｒ　ｉｎ ｍａｎｉｆｏｌｄ　ｌｅａｒｎｉｎｇ，ｔｈｅｎ　ｐｒｏｐｏｓｅｄ　ａｎ　ｉｍｐｒｏｖｅｄ　Ｄｙｎａ＿Ｑ－ｌｅａｒｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ｍａｎｉｆｏｌｄ　ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｉｍｕｌａｔｅｄ　ｉｎ　ｇｒｉｄ　ｗｏｒｌｄ　ｔｈａｔ　ｉｓ　ｓｉｍｉｌａｒ　ｔｏ　ｕｎｄｅｒｇｒｏｕｎｄ　ｅｎｖｉｒｏｎｍｅｎｔ．Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｖｅｒｉｆｉｅｄ　ｖａｌｉｄｉｔｙ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ． Ｋｅｙ　ｗｏｒｄｓ：Ｄｙｎａ＿Ｑ－ｌｅａｒｎｉｎｇ，Ｅｕｃｌｉｄｅａｎ　ｄｉｓｔａｎｃｅ，ｈｅｕｒｉｓｔｉｃ　ｐｌａｎｎｉｎｇ，ｐａｔｈ　ｐｌａｎｎｉｎｇ，Ｌａｐｌａｃｉａｎ Ｅｉｇｅｎｍａｐ，ｍａｎｉｆｏｌｄ　ｄｉｓｔａｎｃｅ ０　引言 井下定位问题已经 能 初 步 解 决，现 阶 段 需 要 重 点 研 究路径规划问题。 近年来，煤矿井下安全事故频发，研究相关特种 灾后井下机器人的救援问题可以建模为计算资 机器人用于灾后救援迫在眉睫。由于煤矿井下地形 源有限的条件下，部 分 模 型 已 知 的 机 器 人 路 径 在 线 和环境复杂，灾后很多情况无法预测，给救援机器人 的机构设计和路径规划算法带来了巨大的 挑战［１－３］。 实时规划问题。灾 后 井 下 的 环 境 具 有 不 确 定 性，同 时救援机器人因行走机构和携带多种传感器所带来 在机器人路径规划 方 面，已 有 的 方 法 主 要 针 对 开 放 的自身复杂性，使得 相 应 的 路 径 规 划 算 法 必 须 具 有 的地面环境，通常不用过多考虑计算能力、通信和定 较高的计算效率和较强自适应性。已有的路径规划 位等问题，而 井 下 救 援 时 这 些 因 素 都 需 重 点 研 究。 方法中，具有较强环境适应能力的遗传算法、蚁群和 近年来，随着物联 网 技 术、机 器 视 觉 的 发 展，机 器 人 粒子群等智能仿生 算 法 计 算 量 都 较 大，计 算 量 小 的 收稿日期：２０１２－１０－２３ 基金项目：国家自然科学基金资助项目（６１２７３１４３）；中国矿业大学青年科技基金项目（ＯＣ０８０２５２） 作者简介：朱美强（１９７９－），男，重庆人，讲师，在 职 博 士 研 究 生，主 要 研 究 方 向 为 机 器 学 习、智 能 优 化 与 控 制。Ｅ－ｍａｉｌ：ｚｈｕｍｅｉｑｉａｎｇ＠ｃｕｍｔ． ｅｄｕ．ｃｎ 中国煤炭期刊网 www.chinacaj.net
    ·２７· 工矿自动化 ２０１２年１２月　　　　　 人工势场、启发式图搜索等方法自适应能力又较弱， 同时基于预测控制原理的动态窗口的滚动规划又易 出现震荡、死循 环 等 问 题［４］，因 此，迫 切 需 要 一 种 计 算量和适应能力较为平衡的在线规划方法。 作为一 种 无 监 督 的 在 线 学 习 方 法，强 化 学 习 （Ｒｅｉｎｆｏｒｃｅｍｅｎｔ　Ｌｅａｒｎｉｎｇ，ＲＬ）强调与环境的交互， 不需要给定导师信 号 就 能 自 主 学 习，适 合 用 于 不 确 定环境下机器人 的 路 径 规 划［５］。 参 考 文 献 ［６］就 是 基于该思路 将 Ｑ 学 习 用 于 井 下 救 援 机 器 人 中。 遗 憾的是，Ｑ 学习的学习效率较低，算法需要对状态－ 动作序列进行“无限”或者“足够”多次的遍历才能收 敛［５］，在 井 下 机 器 人 救 援 这 类 与 环 境 交 互 成 本 较 高 的任务并不适用。Ｄｙｎａ＿Ｑ 学 习 是 一 种 具 有 规 划 能 力的 Ｑ 学习，其根据计算复杂度 代 替 采 样 复 杂 度 的 思想，通 过 建 立 环 境 的 模 型 来 减 小 学 习 成 本［５］。 Ｄｙｎａ＿Ｑ 学习 中，规 划 样 本 的 选 择 机 制 直 接 影 响 算 法的效率，其中 Ｄｙｎａ＿Ｈ 算 法 采 用 欧 氏 距 离 来 指 导 规划，可以在较短的 学 习 次 数 中 得 到 一 个 合 理 的 解 （不一定最优），相 对 Ｑ 学 习 而 言，更 适 合 于 在 线 实 时路径规划问题［７］。Ｄｙｎａ－Ｈ 算 法 对 于 障 碍 物 比 较 稀疏的迷宫问题比 较 有 效，并 不 能 直 接 使 用 于 煤 矿 井下路径规划这种有明显瓶颈结构的任务。 在流形 学 习 中，拉 普 拉 斯 特 征 映 射 （Ｌａｐｌａｃｉａｎ Ｅｉｇｅｎｍａｐ，ＬＥ）作 为 一 种 计 算 效 率 较 高 的 方 法，能 把流形上连续的 曲 面 在 低 维 欧 氏 空 间 里 “铺 平”［８］。 若强化 学 习 的 状 态 空 间 在 欧 氏 空 间 不 连 续，但 在 某个流形上连续，利 用 该 方 法 也 能 在 低 维 欧 氏 空 间 里将状态空间展开，用 展 开 后 的 欧 氏 距 离 作 为 启 发 式函数来选择规划样本可避免 Ｄｙｎａ＿Ｈ 不适应有明 显层次结构任务 的 缺 点。 本 文 基 于 该 思 想，考 虑 煤 ｛ Ｄｅｃｉｓｉｏｎ　Ｐｒｏｃｅｓｓ， ＭＤＰ）为 基 础［１］，一 个 离 散 的 ＭＤＰ 模型可表示为 Ｓ，Ａ，ｐ，ｒ， ｝γ 。其中，Ｓ为有 限 状态空间，Ａ 为有限动 作 空 间，γ∈ （０，１］，为 折 扣 因 子。ｐ（ｓ，ａ，ｓ′）和ｒ（ｓ，ａ，ｓ′）分 别 表 示 状 态ｓ执 行 动 作ａ 转移到状态ｓ′的概率和得到的立即回报。 状态 －动作对（ｓ，ａ）的期望回报Ｒ（ｓ，ａ）为 Ｒ（ｓ，ａ）＝ ∑ｓ′∈Ｓ ｐ（ｓ，ａ，ｓ′）ｒ（ｓ，ａ，ｓ′） （１） 　　设策略π：Ｓ→Ａ 是 从 状 态 到 动 作 的 映 射，动 作 值函数Ｑπ（ｓ，ａ）：Ｓ×Ａ→Ｒ 为 状 态 － 动 作 对 到 实 数 的映射，其表示智能体（Ａｇｅｎｔ）在状态ｓ选 择 动 作ａ 后，按照策 略π执 行 获 得 的 长 期 折 扣 回 报 的 期 望。 强化学习的目标就是在转移矩阵和期望回报的未知 情况下，求解一个可 最 大 化 长 期 累 计 折 扣 回 报 的 最 优策略π＊ ： π＊ ＝ａｒｇ　ｍａｘ Ｑ＊ （ｓ，ａ） （２） 式中：Ｑ＊ （ｓ，ａ）＝ｍａｘ π ａ∈Ａ Ｑπ（ｓ，ａ），为 最 优 状 态 － 动 作 值函数。 强化 学 习 的 算 法 较 多，其 中 应 用 最 为 广 泛 的 是 Ｑ 学习［５］。Ｑ 学习 不 用 估 计 环 境 的 模 型，直 接 利 用 式（３）所示的时间 差 分 预 测 方 法 来 迭 代 求 解 动 作 值 函数，是一类离 策 略（ｏｆｆ－ｐｏｌｉｃｙ）ＴＤ 学 习［５］，策 略 选 择机制直接决定了 算 法 的 收 敛 性，常 用 策 略 选 择 机 制有 Ｂｏｌｔｚｍａｎｎ分布、ε－ｇｒｅｅｄｙ等方法［５］。 Ｑ（ｓ，ａ）＝Ｑ（ｓ，ａ）＋α［ｒ（ｓ，ａ，ｓ′）＋ γｍａｘ ａ′∈Ａ Ｑ（ｓ′，ａ′）－Ｑ（ｓ，ａ）］ （３） 式中：α为学习率。 １．２　Ｄｙｎａ学习 强化 学 习 通 过 与 环 境 的 交 互 来 自 主 学 习，但 在 很多实际问题中，智 能 体 通 过 与 真 实 环 境 交 互 来 获 矿救援机器人的路 径 规 划 特 点，提 出 了 一 类 改 进 的 取经验与知识的 成 本 非 常 高。 因 此，可 以 考 虑 建 立 Ｄｙｎａ＿Ｑ 学习算法。尽管改 进 的 算 法 直 接 用 于 救 援 机器人中并不实际，但 相 对 于 已 有 的 强 化 学 习 算 法 性能已有很大的提升。 １　Ｄｙｎａ＿Ｑ 学习 １．１　Ｑ 学习 强化学习作为一类求解序贯优化决策问题的有 效方法，已在自 动 控 制、运 筹 学 和 计 算 科 学 等 领 域 得到了广泛应用［５］。强化学习的最大特点是在无环 境模型、无教师样本的情况下，通过与环境交互试错 来极大 化 累 计 回 报，从 而 获 得 最 优 或 者 次 优 行 为 策略［５，９］。 强 化 学 习 以 马 尔 科 夫 决 策 过 程 （Ｍａｒｋｏｖ 环境模型，代替真实 环 境 产 生 模 拟 的 经 验 样 本 以 减 小实际采样的成本。Ｓｕｔｔｏｎ的 Ｄｙｎａ学 习 框 架 正 是 基于该思路，通过建 立 环 境 模 型 并 引 入 规 划 来 辅 助 学习过程，其原理如图１所示［５］。 图１　Ｄｙｎａ学习框架原理 中国煤炭期刊网 www.chinacaj.net
    ２０１２年第１２期 朱美强等：一类用于井下路径规划问题的 Ｄｙｎａ＿Ｑ 学习算法 ·３７· 　　　 　　在 Ｄｙｎａ学 习 框 架 中，智 能 体 与 环 境 交 互 得 到 了真实的经验 样 本 Ｔ。 该 样 本 的 作 用：用 于 学 习 值 函数（或策略函数）和更新模拟真实环境的估计模型 Ｐ。同时，环境估计模型Ｐ 产生的 虚 拟 样 本 Ｈ 也用 于学习值函 数 或 策 略 函 数。 用 真 实 样 本 Ｔ 更 新 值 函数和环境估计模型Ｐ 的 过 程 称 为 学 习 过 程，用 环 境估计模型Ｐ 产生虚 拟 样 本 Ｈ 更 新 值 函 数 的 过 程 称为规划［５］。Ｄｙｎａ学 习 框 架 采 用 了 自 适 应 控 制 中 模型辨识的思想，将学习和规划过程有机结合，对于 动态环境 下 的 学 习 问 题 有 显 著 的 加 速 效 果。Ｄｙｎａ 强化学习的主要原理如下［５］：在一步迭代过程中，智 ＮＮ 近邻相邻准则构造近邻图；然后，构造 权 值 矩 阵 Ｗ。在近邻图中，利用热核法或简单法选择权值，并 构造权值矩 阵 Ｗ；最 后，计 算 ｄ 维 嵌 入。 使 用 公 式 Ｌ＝Ｄ－Ｗ 得到组合拉普拉斯矩阵（Ｄ 为度矩阵），并 计算Ｌ的ｄ 个 最 小 特 征 值 对 应 的 特 征 向 量ｙ１，ｙ２， …，ｙｄ，则数据集 Ｘ 的低 维 嵌 入 表 示 为Ｙ＝ ［ｙ１，ｙ２， …，ｙｄ］Ｔ。 　　在强化学习问 题 中，若 获 得 了 状 态 空 间 的 连 接 关系，就可以使用 ＬＥ 分析其内在几何结构，并 对 状 态空间进行降维和流形展 开［９］。 例 如，在 图 ２（ａ）所 示的五房间格子世 界 中，其 状 态 空 间 在 欧 氏 空 间 内 能体首先通过与 环 境 交 互 采 样 到 真 实 的 样 本 Ｔ；然 后，利用真实的样本去更新值函数、策略函数和环境 不连续，对应的连 接 图 如 图 ２（ｂ）所 示，状 态 相 邻 的 边权值均设为１。将 ＬＥ 应用到该状态空间连接图， 的估计模型Ｐ。最后，利用 估 计 的 环 境 模 型 Ｐ 产 生 多个虚拟样本更新值函数或策略函数。 Ｄｙｎａ学习框 架 中，环 境 估 计 模 型 Ｐ 的 精 度 和 规划样本的选择直接决定了算法的效率。环境估计 所得 组 合 拉 普 拉 斯 矩 阵 非 零 最 小 特 征 值 对 应 的 Ｆｉｅｄｌｅｒ特征向量如图２（ｃ）所示，图中Ｚ轴为各状态 相应的特征向量取值，数 字 为 状 态 编 号。Ｆｉｅｄｌｅｒ特 征向量可看作是状 态 空 间 至 特 征 空 间 的 一 维 映 射， 模型既可以是滚动 存 储 或 全 存 储 的 经 验 样 本，也 可 映射后的像将原本在欧氏空间不连续的状态空间有 以以状态转移矩阵的形式给出。规划样本的选择主 要根据基 于 某 种 准 则 的 优 先 级 机 制。 强 化 学 习 在 Ｄｙｎａ学习框架下可以扩展出众多算法，其中应用 最 为广泛的为 Ｄｙｎａ＿Ｑ 学习算法。 效地展开了，例如３８和４１在图上的距离最大（欧氏 距离并不是最大），在 图 ２（ｃ）中 Ｚ 轴 上 的 欧 氏 距 离 也最大。图２（ａ）中 的 状 态 是 二 维 的，其 形 成 的 “流 形”属于无环类，根据流形理论其可以在一维欧氏空 ２　基于 ＬＥ 的 Ｄｙｎａ＿Ｑ 学习算法 ２．１　ＬＥ 原理 ＬＥ 法 是 Ｂｅｌｋｉｎ 和 Ｎｉｙｏｇｉ在 ２００２ 年 提 出 的 一种计算效率较高 的 流 形 学 习 算 法，该 算 法 巧 妙 地 将微分流形、谱图论的知识应用于降维之中，提高了 研究者对流行学习的认识［８］。 ＬＥ 的思想是在高 维 空 间 中 距 离 很 近 的 样 本 点 投影到低 维 目 标 空 间 中 仍 然 保 持 邻 近。 其 理 论 基 础：若样本是从嵌 入 在 高 维 空 间 中 低 维 流 形 上 均 匀 采样得到的，则 流 形 上 的 Ｌａｐａｌａｃｅ－Ｂｅｌｒｔｍａｉ算 子 可 以由图的拉普拉斯 矩 阵 来 逼 近，相 应 图 矩 阵 的 最 小 特征值对应的特征向量就是对流形上拉普拉斯算子 特征函数的逼近。ＬＥ 是 一 种 典 型 的 局 部 流 形 降 维 方法，通过极小化目标函数得到低维嵌入坐标，并巧 妙地将优化问题转换为矩阵的特征值和特征向量的 求解问题［８］。 假设观察数据集 Ｘ 大小为ｎ，观测维数为Ｄ，内 在维数为ｄ，又假设使用的是组合拉 普 拉 斯 算子，则 ＬＥ 算法的 主 要 步 骤 如 下［８］：首 先，构 造 近 邻 图 Ｇ。 在数据集 Ｘ 中，计 算 每 个 样 本 点ｘｉ 同 其 他 样 本 点 之间的欧氏距离ｄ（ｘｉ，ｘｊ），并 利 用ξ－ 近 邻 和 Ｋ－ 间里有效展开。 将 ＬＥ 应用于状态空间连接图所得的特 征 向 量 在 强 化 学 习 中 称 为 原 型 值 函 数 （Ｐｒｏｔｏ－ｖａｌｕｅ ｆｕｎｃｔｉｏｎｓ，ＰＶＦ），最 小 非 零 特 征 值 对 应 的 Ｆｉｅｄｌｅｒ 特 征 向 量 称 为 ＳＰＶＦ （Ｓｅｃｏｎｄ　Ｐｒｏｔｏ－ｖａｌｕｅ Ｆｕｎｃｔｉｏｎ），较小非 零 最 小 特 征 值 对 应 的 ＰＶＦ 称 为 低频 ＰＶＦ［９］。为了统一表 述，后 文 中 将 相 应 的 特 征 向量都称为 ＰＶＦ。ＰＶＦ 事 实 上 是 一 组 反 映 任 务 状 态空间的内在结构 和 全 局 光 滑 性 的 正 交 基 函 数，即 可用于 逼 近 图 上 任 意 平 方 可 积 的 函 数 （包 括 值 函 数），也能实现状态空间的层次分解［９］。 ２．２　Ｄｙｎａ＿Ｈ 原理 Ｄｙｎａ学习框架中，规划的引入使强化学习摆脱 了简单的试错学习，具有“认知”的能力，其规划样本 的选择机制直接影响 算 法 的 效 率。 最 初 的 Ｄｙｎａ学 习中，Ｓｕｔｔｏｎ采 用 的 是 简 单 的 随 机 选 择 方 式，规 划 时很多值函数的迭代对于算法来讲是无效的。基于 优先级 查 询 思 想，Ａｎｄｒｅｗ　Ｗ．Ｍｏｏｒｅ 等 人 提 出 了 Ｐｒｉｏｒｉｔｉｚｅｄ　Ｓｗｅｅｐｉｎｇ 算 法 和 Ｑｕｅｕｅ－ｄｙｎａｍｉｃ 学 习 框架，２ 种 框 架 使 用 的 优 先 级 机 制 都 是 基 于 贝 尔 曼 误差的［５，１０］。但 Ａｎｄｒｅｗ　Ｗ．Ｍｏｏｒｅ也 指 出，合 适 的 启 发式机制也可用 于分 配优先级 ，并在迷宫 问 题 中 中国煤炭期刊网 www.chinacaj.net
    ·４７· 工矿自动化 ２０１２年１２月　　　　　 （ａ）格子世界地图 （ｂ）状态连接图 （ｃ）ＳＰＶＦ 图２　五房间格子世界的图描述 使 用 了 曼 哈 顿 距 离 来 决 定 优 先 级［１０］。 Ｍａｔｉｌｄｅ Ｓａｎｔｏｓ等人遵 循 上 述 思 想，在 最 短 路 径 问 题 中，采 用最远的欧氏 距 离 样 本 来 指 导 规 划，提 出 了 Ｄｙｎａ＿ Ｈ 方法，并认为其模拟了恶梦理论［７］。 续的状态空间有效地 展 开，这 里 将 其 与 Ｄｙｎａ＿Ｈ 结 合，利用展开的流形距离代替欧氏距离，得到一种新 的 Ｄｙｎａ＿Ｑ 学 习 算 法，其 启 发 式 规 划 函 数 的 定 义 见 式（６），ｆ表示 ＰＶＦ，ｎ为使用低频 ＰＶＦ 的数目。 假设 ＨＰ（ｓ，ａ）为 状 态 动 作 对 的 启 发 式 规 划 函 数，其可认为是 判 断 智 能 体 在 状 态ｓ执 行 动 作ａ 的 一种性能指标。Ｄｙｎａ＿Ｈ 的思 路 是 将 各 状态到 目 标 位置的 欧 氏 距 离 作 为 启 发 式 规 划 函 数，其 定 义 如 式（４）所示，其中ｓ′表 示 对 状 态 对 （ｓ，ａ）进 行 模 型 查 询的结果，即ｓ′＝Ｐ（ｓ，ａ）。 ＨＰ（ｓ，ａ）＝ｄ（ｓ′，ｓｇ） （４） 　　得 到 启 发 式 规 划 函 数 后，用 于 规 划 用 的 样 本 （ｓ，ｈａ）就可以按照 式 （５）所 示 的 最 差 启 发 式 评 价 的 原则进行选 择。 例 如，在 图 ２（ａ）的 例 子 中，假 设 智 能体有东、西、南、北４个动作，智能体的现在状态为 ３６，目标状态 为 ４１，根 据 最 远 欧 氏 距 离 启 发 式 评 价 准则，智能体选状态３０或３７作为下一个规划样本。 Ｍａｔｉｌｄｅ　Ｓａｎｔｏｓ等人认为该 机 制 模 拟 了 人 在 痛 苦 中 学习的思想，可以很好地提高算法的起始性能，在较 短的学习次数中得到一个合理的解。笔者认为最差 启发式 评 价 的 原 则 把 当 前 状 态ｓ更 新 的Ｑ 值 很 快 “扩散”到离目 标 状 态 更 远 的 状 态 中 （与ｓ相 比 较 更 远），所以有较好的起始性能。 ｈａ（ｓ）＝ａｒｇ　ｍａｘ ＨＰ（ｓ，ａ） ａ∈Ａ （５） ＨＰｓｐｅ（ｓ，ａ）＝ ∑ 槡 ｉ＝ ２ ｎ＋１ ｆｉ（ｓｇｏａｌ）－ｆｉ（ｓ′ ）） （ ２ （６） 　　基于 ＬＥ 的 Ｄｙｎａ＿Ｑ 算法的具体步骤如下： Ｓｔｅｐ　１：初 始 化 Ｑ 值 函 数、策 略 函 数π、环 境 估 计模型Ｐ、启发式规划函数 Ｈｓｐｅ和使用低频 ＰＶＦ 的 数目ｎ。 Ｓｔｅｐ　２：观察 当前 状态ｓ，根据 策略选择机制 选 择动作ａ，使 智 能 体 转 换 到 新 状 态ｓ′并 得 到 立 即 回 报ｒ，得到真实样本（ｓ，ａ，ｒ，ｓ′）。 Ｓｔｅｐ　３： 首 先，利 用 真 实 样 本 使 用 式 （３）和 ε－ｇｒｅｅｄｙ方法 更 新 值 函 数 Ｑ 和 策 略 函 数π；然 后， 利用真实样 本 更 新 环 境 估 计 模 型 Ｐ（ｓ，ａ，ｒ，ｓ′）；最 后，设置规划用的起始状态ｓｓ＝ｓ。 Ｓｔｅｐ　４：如果估计模型Ｐ（ｓ，ａ，ｒ，ｓ′）在多个学习 幕数中不变，则利用 ２．１ 所 述 方 法 计 算 组 合 拉 普 拉 斯矩阵 和 相 应 的 特 征 向 量，然 后 利 用 式 （６）得 到 Ｈｓｐｅ。 Ｓｔｅｐ　５：重复下列步骤ｋ次。 （１）根据式（５）选择动作ａａ； （２）根据环境估计模型Ｐ 得到虚拟样本 Ｈ（ｓｓ， ａａ，ｒｒ，ｓｓ′）； ２．３　基于 ＬＥ 的改进 Ｄｙｎａ＿Ｑ 学习算法 Ｄｙｎａ＿Ｈ 在障碍物较疏散的 迷宫 问 题中 可 以 取 得较好的初始性能，但对于图 ２（ａ）所 示 的 这 类 有 明 显瓶颈结构的地图 并 不 适 用，其 原 因 是 欧 氏 距 离 并 （３）利用虚拟样本 Ｈ 更新值函数Ｑ，ｓｓ＝ｓｓ′。 Ｓｔｅｐ　６：判 断 是 否 满 足 终 止 准 则，是 则 结 束 算 法，否则转 Ｓｔｅｐ　２。 所提出的算法有一个在未知环境中学习模型的 不能正确反应各状态间到目标状态的真实距离。例 过程，适合于井下局部空间的路径规划。 如，对于图 ２（ａ）中 的 状 态 ２８ 和 ３４，３４ 离 目 标 状 态 的实际 距 离 比 ２８ 要 近，但 欧 氏 距 离 却 比 ２８ 要 远。 ３　仿真研究及结果分析 前面２．１ 节已经指出 ＬＥ 能够将在欧氏空间内不连 为了验证 改 进 的 Ｄｙｎａ 算 法 的 有 效 性，分 别 在 中国煤炭期刊网 www.chinacaj.net
    ２０１２年第１２期 朱美强等：一类用于井下路径规划问题的 Ｄｙｎａ＿Ｑ 学习算法 ·５７· 　　　 与煤矿井下环境的 类 似 的 五 房 间、对 称 四 房 间 格 子 世界中进行 了 仿 真 研 究。 仿 真 中，Ｄｙｎａ＿Ｑ 学 习 算 法的相关参数为ａ＝０．０１，ｒ＝０．９５。 每 组 实 验 的 各 种算法都独立运行２０次，所有的例子都是从第五幕 开始进行规划操作，规划步数为ｋ＝５。 在五房间格 子 地 图 中，目 标 状 态 仍 然 在 ４１，初 始状态为３８，图３为相应的仿真结果。 图３　五房间格子世界任务的仿真结果 　　从图３可看出，使 用 ＳＰＶＦ 距 离 选 择 规 划 样 本 的起始性能最好，欧氏距 离 其 次，Ｑ 学 习 和 Ｄｙｎａ最 差。其原因是欧氏距离并未体现各状态与目标状态 的 实 际 距 离 ，而Ｄｙｎａ规 划 时 样 本 的 选 择 具 有 随 机 性。Ｑ 学习和 Ｄｙｎａ相比较，尽管 Ｄｙｎａ在 ５～１５ 这 几幕不够稳定，但整体性能与 Ｑ 学 习 相 当。 值 得 注 意的是，随着学 习 次 数 的 增 加，Ｄｙｎａ规 划 样 本 的 算 法性 能 更 好，原 因 是 Ｑ 学 习 的 收 敛 条 件 为 均 匀 采 样。这也是 Ｄｙｎａ＿Ｈ 算法能在较短时间内只能获取 一个令人满意的解，但并不是最优解的原因。 　　对称四房间格 子 世 界 的 相 关 描 述 如 图 ４ 所 示。 由于此任务状态空 间 所 在 的 流 形 存 在 环，所 以 一 维 ＰＶＦ 并不能很好反应各个房间 的 距 离 关 系，需 要 使 用 ＳＰＶＦ 和 ＴＰＶＦ（Ｔｈｉｒｄ　ＰＶＦ）进 行 映 射，然 后 在 二维 映 射 空 间 里 求 取 相 关 距 离 （参 见 图 ４（ｂ）和 图４（ｃ））。该实验中，状态的起始位置为１，终止状态 为４０，图５为 相 应 的 仿 真 结 果。 由 图 ５ 可 看 出，使 用欧 氏 距 离 和 ＳＰＶＦ＋ＴＰＶＦ 距 离 的 初 始 性 能 较 好，其 次 是 使 用 ＳＰＶＦ 距 离，最 差 是 Ｄｙｎａ 和 Ｑ 学 习。使用欧氏距离好的原因是该任务相对来说障碍 物比较稀疏，欧氏距离较好地反映了实际的距离（参 见图４（ｄ）和图 ４（ｅ），图 中 距 离 值 都 取 了 负）。 使 用 ＳＰＶＦ＋ＴＰＶＦ 距离与欧氏距离的效果类似，间接验 证了所提算法同样适用于欧氏距离适用的任务。 （ａ）格子世界地图 （ｂ）ＳＰＶＦ （ｃ）状态空间的二维 ＰＶＦ 表示 （ｄ）使用２个 ＰＶＦ 的欧式距离 （ｅ）欧氏距离 图４　对称的四房间格子世界的相关描述 中国煤炭期刊网 www.chinacaj.net
    ·６７· 工矿自动化 ２０１２年１２月　　　　　 ［２］　李东晓，黎彦学．机器 人 与 全 矿 山 自 动 化 ［Ｊ］．工 矿 自 动化，２００７，３３（５）：４０－４２． ［３］　李金良，孙友霞，包继华，等．救援机器人目标跟踪控 制的研究［Ｊ］．工矿自动化，２００９，３５（１２）：２０－２３． ［４］　朱大奇，颜明重．移动 机 器 人 路 径 规 划 技 术 综 述 ［Ｊ］． 控制与决策，２０１０，２５（７）：９６１－９６７． ［５］　ＳＵＴＴＯＮ　Ｒ　Ｓ， ＢＡＲＴＯ　Ａ　Ｇ． Ｒｅｉｎｆｏｒｃｅｍｅｎｔ Ｌｅａｒｎｉｎｇ：ａｎ　Ｉｎｔｒｏｄｕｃｔｉｏｎ［Ｍ ］．Ｃａｍｂｒｉｄｇｅ， ＭＡ： ＭＩＴ　Ｐｒｅｓｓ，１９９８． ［６］　王帅．基于 强 化 学 习 算 法 的 井 下 移 动 机 器 人 路 径 规 划［Ｊ］．电气技术，２００８（８）：４７－４９． ［７］　ＳＡＮＴＯＳ　Ｍ，ＭＡＲＴＩＮ　Ｈ．ＪＡ，ＬＯＰＥＺ　Ｖ，ｅｔ　ａｌ． Ｄｙｎａ－Ｈ： Ａ　 Ｈｅｕｒｉｓｔｉｃ　 Ｐｌａｎｎｉｎｇ　 Ｒｅｉｎｆｏｒｃｅｍｅｎｔ Ｌｅａｒｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ａｐｐｌｉｅｄ　ｔｏ　Ｒｏｌｅ－ｐｌａｙｉｎｇ－ｇａｍｅ Ｓｔｒａｔｅｇｙ　Ｄｅｃｉｓｉｏｎ　Ｓｙｓｔｅｍｓ ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ－Ｂａｓｅｄ Ｓｙｓｔｅｍｓ，２０１２（３２）：２８－３６． ［８］　ＢＥＬＫＩＮ　Ｍ，ＮＩＹＯＧＩ　Ｐ．Ｌａｐｌａｃｉａｎ　Ｅｉｇｅｎｍａｐｓ　ｆｏｒ Ｄｉｍｅｎｓｉｏｎａｌｉｔｙ　Ｒｅｄｕｃｔｉｏｎ　ａｎｄ　Ｄａｔａ　Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ［Ｊ］．Ｎｅｕｒａｌ　Ｃｏｍｐｕｔａｔｉｏｎ，２００３，１５（６）：１３７３－１３９６． ［９］　朱美强，程 玉 虎，李 明，等．一 类 基 于 谱 方 法 的 强 化 学习 混 合 迁 移 算 法 ［Ｊ／ＯＬ］．（２０１２－０９－０６）．ｈｔｔｐ：／／ ｗｗｗ．ｃｈｋｉ．ｎｅｔ／ＫＣＭＳ／ｄｏｃｄｏｗｎ／ｐｕｂｄｏｗｎｌｏａｄ．ａｓｐｘ？ ｄｋ＝ｕ＿ｗｅｅｖ． ［１０］　ＭＯＯＲＥ　Ａ　Ｗ， ＡＴＫＥＳＯＮ　Ｃ　Ｇ． Ｐｒｉｏｒｉｔｉｚｅｄ Ｓｗｅｅｐｉｎｇ：Ｒｅｉｎｆｏｒｃｅｍｅｎｔ　Ｌｅａｒｎｉｎｇ　ｗｉｔｈ　Ｌｅｓｓ　Ｄａｔａ ａｎｄ　Ｌｅｓｓ　Ｒｅａｌ　Ｔｉｍｅ［Ｊ］． Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９９３ （１３）： １０３－１３０． 图５　对称的四房间格子世界任务的仿真结果 ４　结语 Ｄｙｎａ＿Ｈ 算法在有稀疏障 碍 物 的 迷 宫类 路 径 规 划问题中有较好的 效 果，但 并 不 适 用 煤 矿 井 下 这 类 具有明显瓶颈状 态 任 务。 针 对 该 缺 点，本 文 利 用 拉 普拉斯 特 征 映 射，提 出 了 一 类 改 进 的 Ｄｙｎａ＿Ｑ 学 习 算法。改进的算法在稀疏障 碍 物 情 况 下 与 Ｄｙｎａ＿Ｈ 有相似的性能，在有 明 显 瓶 颈 状 态 时 的 任 务 性 能 相 对 Ｄｙｎａ＿Ｈ 算法有明显的提升。格子世界仿真结果 验证了所提算法的有效性。 参考文献： ［１］　钱善华，葛世荣，王永胜，等．救灾机器人的研究现状 与煤 矿 救 灾 的 应 用 ［Ｊ］．机 器 人，２００６，２８（３）：３４９－ ３５４． 檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿檿 第１２届西部国际煤炭及新能源产业博览会会讯 　　由陕西省发 展 和 改 革 委 员 会 能 源 局、陕 西 省 国 有 资产监督管理委 员 会、陕 西 省 煤 炭 生 产 安 全 监 督 管 理 局等主办，陕西省装备制造业协会、陕西省煤 炭 工 业 协 会等协办的“第１２届西部国际煤炭及新能 源 产 业 博 览 会”将于２０１３年３月２２日至２４ 日 在 西 安 曲 江 国 际 会 展中心举行。 本届博览会将设４大展区： （１）大企业大集团形象展区 大型煤炭、电力、石油石化、能源化工、新 能 源 企 业 新形象、新技术、新成果展示。 （２）煤炭技术设备展区 煤炭勘探、采掘、支护、输送等生产设备； 煤矿电气、照明、供 配 电、防 爆 电 器、矿 用 电 源、变 压器及变电站等； 矿用轴承、齿轮、液压、马达、传动设备、润滑油等； 矿山监测测控系统、矿山服务、电网测控系统； 井下安全设 备、救 生 舱、矿 山 安 全 防 护 产 品、应 急 救援设备等； 　　煤炭运输、装载工具，运煤专用车辆、矿 用 车 辆、轮 胎等； 煤矿井下安全避险六大系统。 （３）煤炭加工技术设备展区 煤炭洗选加工及洁净利用技术及设备； 煤焦化、液化、煤气化等现代煤化工技术及设备； 煤层气开发与利用技术设备； 大型空分设备、大型合成氨设备； 泵、阀、管道／管材、仪器仪表、通用机械设备； 危化产品的储运技术与设备。 （４）节能环保展区 能源节约、工矿环保、工业水处理技术设备等； 脱硫／脱硝／脱氮技术装备； 煤泥、煤矸石资源利用新技术设备。 联系人：寇哲 电话：１５８２９７１６８５２，０２９－８８２２３５２３ ，８８２２３５２６ 传真：０２９－８８２２３００２ 邮箱：ｋｏｕｚｈｅ６２９９＠１６３．ｃｏｍ 中国煤炭期刊网 www.chinacaj.net
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料