2022年规划求解系统.pdf
《2022年规划求解系统.pdf》由会员分享,可在线阅读,更多相关《2022年规划求解系统.pdf(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第 七 章 规 划 求 解 系 统 与 需 求 解 的 一 般 典 型 问 题 相 比,人 工 智 能 规 划 求 解 系 统 往 往 注 重 大 型 复 杂 对 象 的 研 究。前 者 关 心 的 是 具 体 问 题 的 具 体 解 答 结 果,而 后 者 注 重 的 是 系 统 求 解 过 程 及 解 路 径(Solution Path)的 寻 取。其 次,人 工 智 能 研 究 的 传 统 规 划 问 题,关 注 高 层 次 求 解 系 统 技 术 的 自 动 完 成,重 视“拟 人 智 能 特 性 的 发 挥,使 系 统 能 对 现 场 具 体 任 务 和 环 境,自 动 进 行 分
2、析 与 描 述,自 动 选 择 求 解 步 骤,形 象 生 动 地 完 成 其 过 程。例 如 机 器 人 规 划(Robot planning),计 算 机 下 棋(Computerchess)等。应 该 指 出,目 前 关 于 规 划 求 解 问 题,客 观 上 已 形 成 了 两 分 支 开 展 的 格 局:一 条 是 人 工 智 能 科 学 关 于 研 究 自 动 规 划 系 统 及 其 完 成 技 术 的 道 路,另 一 条 则 是 治 理 运 筹 科 学 中 关 于 应 用 数 学 规 划 的 研 究 分 支。后 者 针 对 诸 如 如 何 合 理 配 置 使 用 资 源,取 得
3、最 优 生 产 及 经 济 效 益 等 类 具 体 问 题,运 用 数 学 方 法,设 法 建 立 或 找 到 容 纳 假 设 干 环 境 参 数 相 约 束 的 数 学 模 型,并 依 照 实 验 不 断 修 正 模 型,最 后 依 靠 模 型 计 算,寻 取 本 原 问 题 最 优 解。如 何 将 上 述 两 种 不 同 的 研 究 思 路 互 取 所 长,协 同 开 展 呢 二 者 如 何 兼 容 并 蓄,纵 横 综 合,以 便 共 展 规 划 科 学 的 新 蓝 图 呢 这 或 许 正 是 新 时 代 研 究 规 划 科 学 工 作 者 又 一 新 课 题。本 章 重 点 在 于 介
4、绍 并 深 刻 探 讨 人 工 智 能 规 划 求 解 问 题 的 原 理、方 法 和 技 术。第 一 节 规 划 规 划 的 概 念 规 划(Planning),可 认 为 是 循 规 筹 划 的 缩 略 词。意 即 在 行 动 之 前,确 定 到 达 系 统 目 标 的 进 程。换 言 之,是 寻 求 快 速 到 达 目 标 的 步 骤 和 路 径。究 其 规 划 内 涵,具 有 两 层 含 义:既 要 遵 循 客 观 规 律,确 立 到 达 系 统 目 标 的 方 略 方 案,又 须 依 照 肯 定 的 技 术 方 法,实 施 运 作 步 骤,力 求 取 得 最 正 确 解 操 作 序
5、列。简 言 之,规 划 就 是 制 定、实 施 行 动 的 步 骤 与 决 策。一 个 规 划,就 是 一 个 行 动 过 程 的 描 述。如 图 7-1所 示 结 构,是 一 位 大 学 生 一 天 正 常 的 作 息 安 排,它 就 是 一 个 规 划 构 成。图 7 T 的 例 子 还 简 要 范 表 现 出:一 个 总 规 划,可 以 含 有 假 设 干 子 规 划 和 求 解 流 程 的 结 构。规 划 的 特 性 和 作 用 缺 少 规 划,将 导 致 求 解 效 率 极 大 程 度 的 降 低。例 如,有 人 为 了 买 邮 票 和 寄 信,因 为 缺 少 规 划,跑 了 两 次
6、 邮 局。在 问 题 规 划 求 解 中,规 划 范 表 现 出 既 有 相 互 独 立,多 条 局 部 解 路 经 可 选 的 特 性,又 包 含 序 列 相 贯,不 可 随 意 颠 倒 顺 序 的 环 节 特 性。例 如,走 出 大 森 林,到 达 目 的 地,可 以 有 多 条 路 线,但 每 条 路 线 所 须 跨 越 的 山 谷 川 流 的 次 序 大 致 都 是 固 定 的。=子 约 束 2=子 约 束 3图 7-2 规 划 的 相 关 性 例 如,欲 建 一 座 优 质 大 楼,规 划 环 节 应 包 含:预 先 设 计 图 纸,施 工 先 须 打 好 地 基,预 留 地 下 管
7、 道 等。地 下 工 程 完 毕,再 实 施 地 上 工 程,先 起 地 面 楼 层,再 逐 渐 续 起 高 层。但 是,如 果 缺 少 合 理 规 划,工 程 施 工 颠 倒 了 次 序,该 工 程 就 将 失 败 或 造 成 极 大 损 失。按 规 划 实 施,还 可 用 以 监 控 系 统 运 行 进 程。这 样,可 以 及 时 觉 察 并 预 防 过 失。例 如,考 虑 某 个 在 深 海 打 捞 作 业 的 潜 水 机 器 人,它 必 须 能 够 规 划 一 个 探 测 海 域 环 境,随 时 掌 握 现 场 作 业 面 的 步 骤 和 进 程。当 发 生 深 海 潜 流 影 响,导
8、 致 目 标 物 位 置 变 动 时,机 器 人 能 依 据 检 测 到 的 环 境 参 数 与 预 期 不 符 的 差 异,在 向 海 面 指 挥 中 心 发 出 告 警 信 息 的 同 时:还 须 启 动 作 业 修 改 进 程 规 划,采 取 必 要 调 整 作 业 进 程 步 骤 和 操 作 措 施。三.系 统 规 划 求 解 的 方 法 与 途 径 把 大 型 复 杂 系 统 的 规 划 求 解,化 为 假 设 干 复 杂 度 低 得 多 的 子 系 统、子 目 标 寻 优 过 程 的 综 合 作 用,这 种 降 低 复 杂 问 题 求 解 难 度 的 分 析 方 法,称 为 分 解
9、 技 术。它 是 完 成 规 划 求 解 的 主 要 技 术 手 段。按 照 采 纳 规 划 决 策 的 不 同 思 维 方 法,规 划 技 术 可 以 有 许 多 分 解 途 径。图 7-3列 出 了 局 部 规 划 分 解 的 技 术 实 施 方 案。规 划 分 解 技 术 等 物 理 时 空 性 度 量 X等 区 划 进 程 分 解 j 规 划 空 间 分 解 时 空 混 合 分 解 关 键 子 目 标 规 划 分 解 按 目 标 技 术 功 能 J 关 键 指 标 功 能 规 划 分 解 特 点 及 重 要 性 I 关 键 过 程 规 划 分 解 静 态 规 划 按 系 统 运 动 Y
10、持 性 分 为 动 态 规 划 与/或 树 规 划 描 述 分 解 按 A I知 识 范 表 司 状 态 空 间 描 述 规 划 分 解 技 术 分 为 I 框 架 技 术 规 划 分 解、产 生 式 规 划 分 解 图 7-3 问 题 规 划 分 析 的 技 术 途 径 如 图 7-4所 示 的 规 划 与/或 树,是 人 们 常 喜 欢 采 纳 的 一 种 简 化 规 划 求 解 难 度 的 重 要 思 想。图 中,问 题 的 难 度 逐 层 降 低。其 中:Po=PiAP2Ap3P=PnVPi2P2=P21 八 P22P3(P3I A P 32)VP33第 二 节 机 器 规 划 成 功
11、 性 根 本 原 理.概 述 完 成 机 器 智 能 的 自 动 规 划 系 统,存 在 许 多 非 本 原 问 题 的 因 素。对 机 器 规 划 成 功 性 的 考 察,更 重 要 的 是 从 历 史 性 开 展,总 体 性 和 心 理 学 上 去 探 询 认 识。机 器 自 动 规 划 问 题,是 现 实 科 技 领 域 中 高 难 度 问 题。现 实 中 人 类 智 能 规 划,尚 难 保 证 不 出 过 失,机 器 智 能 规 划 又 岂 能 轻 易 成 功!事 实 上,规 划 的 研 究 不 在 于 一 次 性 猎 取 成 功,而 在 于 可 从 假 设 干 次 不 成 功 中,进
12、 行 机 器 归 纳 学 习,使 得 修 订 的 规 划 比 以 前 任 何 一 次 都 更 加 接 近 成 功。早 在 1958年,人 工 智 能 先 驱 者 和 大 师 Newell和 Simon曾 就 机 器 自 动 规 划 问 题,作 出 了 非 常 乐 观 的 预 言:(1)计 算 机 将 要 成 为 世 界 象 棋 冠 军;(2)计 算 机 将 要 制 造 和 证 明 重 要 的 数 学 定 理;(3)计 算 机 将 能 谱 写 具 有 优 秀 作 曲 家 水 平 的 乐 曲;(4)大 多 数 心 理 学 理 论 将 在 计 算 机 上 形 成。当 时 预 言 10年 内 就 可
13、完 成 的 目 标,却 直 到 假 设 干 个 10年 后,这 几 个 问 题 才 渐 有 转 机 和 答 案。人 工 智 能 科 学 界 也 曾 因 这 几 个 问 题 的 认 识 和 争 论,引 起 过 大 起 大 落 的 轩 然 大 波。目 前,机 器 自 动 规 划 研 究 成 果 已 经 揭 示:上 述 除 第 条 外,前 三 条 或 已 获 成 功,或 已 根 本 获 得 成 功。例 如,1997年 5 月 美 国 IBM公 司“深 蓝(Deeper Blue)计 算 机,战 胜 国 际 象 棋 世 界 冠 军 加 里 卡 斯 帕 罗 夫(GarryKasporrov),第 一 次
14、 登 上 了 国 际 象 棋 世 界 冠 军 的 宝 座;1976年,美 国 数 学 家 Appel和 Haken,运 用 计 算 机 辅 助 证 明(CAP)的 规 划 思 想,一 举 攻 克 了 世 界 三 大 数 学 难 题 之 一 的“四 色 定 理”的 证 明。至 于 利 用 多 媒 体 计 算 机 音 响 装 置,让 计 算 机 弹 奏 出 具 有 随 机 数 字 符 号 音 乐,人 们 已 是 司 空 见 惯。上 述 事 例 说 明,机 器 自 动 规 划 全 面 成 功 地 解 决,虽 然 很 难,但 又 是 必 定 的。人 类 应 该 保 持 平 常 心 态,欢 迎 这 一
15、划 时 代 的 来 临:正 如 汽 车 比 人 跑 得 快,起 重 机 比 人 举 得 重,计 算 机 比 人 算 得 快,机 器 人 可 能 将 在 假 设 干 方 面 超 过 人 的 能 力,这 又 有 什 么 稀 奇 呢 综 上 所 述,面 对 机 器 自 动 规 划 系 统 成 功 性 的 研 究,尚 需 研 讨 下 述 假 设 干 具 体 问 题:其 一、如 何 进 行 问 题 总 规 划 的 设 计 其 二、当 规 划 失 败 时,如 何 确 诊 规 划 失 败 的 环 节,并 进 行 规 划 修 正,其 三、如 何 进 行 机 器 规 划 的 自 学 习 如 何 自 动 生 成
16、规 划 系 统 及 过 程 诸 如 上 述 问 题 的 研 究,实 际 上 当 前 只 能 结 合 具 体 规 划 生 成 系 统,针 对 具 体 问 题 环 境,进 行 具 体 分 析 和 设 计。下 面 仅 就 前 两 个 问 题,综 合 进 行 原 则 性 的 商 量 分 析,在 此 根 底 上,介 绍 假 设 干 根 本 原 理。二.总 规 划 的 设 计 与 分 层 规 划 原 理 普 遍 常 用 的 原 则 是:先 产 生 一 个 粗 略 的 规 划,再 设 法 将 它 细 化 成 假 设 干 较 简 单 的 根 本 级 规 划;依 此 类 推,逐 级 分 层,下 级 比 上 一
17、级 更 精 细,形 成 多 级 分 层 规 划(如 图 7-5所 示)。假 设 单 纯 从 多 级 分 层 规 划 结 构 图 来 考 察,不 难 觉 察 该 结 构 图 客 观 上 具 有 这 样 的 一 种 特 性:假 设 某 规 划 的 各 级 子 规 划 均 有 解,则 说 明 该 规 划 已 可 解;相 反,假 设 高 级 规 划 有 解,则 并 不 说 明 其 随 机 划 分 的 低 级 子 规 划 也 肯 定 有 解。事 实 上,按 照 分 层 规 划 思 想,既 然 高 级 规 划 已 可解,人 们 也 无 须 对 它 再 进 行 低 级 子 规 划 的 分 解 了。综 上 所
18、 述,规 划 成 功 可 解 的 原 理 可 简 叙 为:在 多 级 分 层 规 划 中,只 要 任 意 找 到 一 条 从 初 态 集 到 目 标 集 的 可 解 路 径,则 该 规 划 可 解;否 则 该 规 划 无 解。上 述 原 理 的 正 确 性 验 证 显 而 易 见,此 处 不 再 赘 述。三.规 划 问 题 求 解 与 最 优 规 划 原 理 规 划 问 题 求 解,i 般 应 包 含 寻 取 解 路 径 和 解 结 果 两 个 方 面。而 规 划 最 优 解 问 题 则 可 概 括 为 寻 取 其 中 之 一。因 为 最 正 确 解 路 径 和 最 正 确 解 结 果 是 相
19、 互 唯 一 对 应 的,故 知 其 一 就 可 马 上 得 到 另 一 个。假 设 最 正 确 解 路 径 是 全 部 解 路 中 深 度 最 小 的,且 对 应 于 操 作 序 列 所 使 用 的 策 略 集 是 最 精 炼 的,即 数 量 上 是 最 少 的。设 D。为 总 规 划 策 略 集,SP为 规 划 最 正 确 解 路 径 上 任 一 中 间 结 点,D.为 已 使 用 的 子 策 略 集,S 为 规 划 的 初 态 集,G为 目 标 集。则 最 优 规 划 原 理 可 范 表 达 为:假 设 D。为 最 优 规 划 策 略 集,则 余 下 的 SP G 策 略 子 集 DC=
20、(D0-DP)也 必 是 最 优 的。换 言 之,一 个 最 优 规 划 策 略 集 的 余 子 集 总 是 最 优 的。上 述 最 优 性 规 划 原 理 也 可 称 作 最 优 性 规 划 定 理,且 可 作 为 操 作 规 则 运 用 于 规 划 问 题 求 解 中。上 述 定 理,可 用 常 识 性 推 理 论 证 如 下:已 知 D。是 最 优 的,依 照 最 优 规 划 策 略 集 取 得 最 小 值 的 前 提,假 设 SJ S,已 使 用 的 不 肯 定 是 最 优 的,则 S f S,必 定 存 在 一 个 对 应 最 正 确 路 径 的 最 优 策 略 子 集,且 有 假
21、设 设 不 一 是 最 优 的,则 G也 必 定 存 在 一 个 最 优 策 略 子 集。于 是 则 有 假 设 设 O.不 肯 定 是 最 优 的,则 也 必 定 存 在 一 个 最 优 策 略 子 集。于 是 有 而 由 已 知 D&=D.-Dp D-Dp=D;得 到 D8;为 对 应 于 最 正 确 解 路 径 的 最 优 策 略 子 集。同 理,还 进 一 步 说 明 了 2,也 必 定 是 的 最 优 策 略 子 集。需 要 强 调 的 是,这 里 提 出 关 于 最 优 规 划 原 理 及 其 证 明 的 前 提 虽 然 不 十 分 严 密,但 仍 不 失 为 既 具 理 论 意
22、义,又 有 极 强 的 实 践 指 导 意 义 的 分 析 研 究 方 法。这 是 因 为:建 立 在 极 值 条 件 下,可 找 到 最 优 解 相 关 判 据,它 是 科 学 规 律 中 一 般 自 然 法 则。当 然,针 对 具 体 自 动 规 划 系 统,应 用 最 优 规 划 原 理 分 析,将 成 为 要 考 察 多 参 数、多 变 量、多 极 值 方 向 条 件 下,确 定 最 正 确 解 路 径 的 复 杂 问 题。尽 管 如 此,依 照 相 关 泛 函 知 识 和 最 优 规 划 原 理 综 合 分 析,仍 可 导 出 相 关 规 划 和 推 理。后 续 深 刻 研 究,详
23、见 有 关 研 究 文 献。四.规 划 的 双 序 求 解 与 诊 断依 据 问 题 规 划 求 解 的 方 向,假 设 从 初 始 起 点 出 发,逐 级 前 向 推 理,直 至 获 得 到 达 目 标 的 序 列 操 作,并 能 完 成 终 点 的 全 部 状 态 条 件。系 统 这 种 按 顺 序 方 法 求 得 解 路 的 过 程,称 为 顺 序 规 划 求 解。反 之,从 目 标 终 点 逆 向 推 理,直 至 系 统 到 达 与 初 态 一 致 的 约 束 条 件。这 种 反 向 求 解 过 程,称 为 逆 序 规 划 求 解。顺 序 求 解 和 逆 序 求 解 统 称 为 双 序
24、 法。顺 序 规 划 求 解 是 一 种 顺 其 自 然 方 法 的 常 规 方 法。而 逆 序 规 划,依 据 目 标 要 求 来 验 证 前 提 条 件:或 依 据 目 的 分 析,确 定 必 要 的 相 应 手 段 与 操 作 规 则,这 种 思 路 似 乎 更 加 符 合 人 类 思 维 习 惯,且 又 称 之 为“目 的 一 一 手 段 规 划 分 析 法。例 如,警 卫 机 器 人 的 行 动 规 划 之 一:机 器 人 为 了 照 亮 房 间,启 动 了 电 灯 开 关,为 了 应 付 入 侵 者,又 拿 起 了 武 器;并 对 准 猎 物,发 出 了 要 开 枪 的 警 告 人
25、 们 还 觉 察 很 多 情 况 下,逆 序 法 比 顺 序 法 更 易 找 到 最 正 确 解。例 如,凡 属 可 范 表 示 为 树 状 性 质 的 问 题,采 纳 逆 序 规 划,从 树 叶 寻 其 根 十 分 简 单,且 往 往 得 到 的 解 就 是 最 正 确 解。而 采 纳 顺 序 法,从 根 求 其 某 片 特 别 的 叶 子,却 要 困 难 复 杂 得 多 了。为 了 诊 断 系 统 规 划 是 否 出 错,通 常 采 纳 逐 级 规 划 分 段 测 试 法 和 双 序 法 相 结 合 的 方 法 进 行。针 对 某 级 子 规 划,可 先 选 取 逆 序 检 查 法;假 设
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 规划 求解 系统
限制150内