《状态空间法.ppt》由会员分享，可在线阅读，更多相关《状态空间法.ppt（56页珍藏版）》请在三一文库上搜索。
1、第二章 人工智能的基本方法 2.1 2.1 符号方法符号方法 物理符号系统（符号操作系统）物理符号系统（符号操作系统） 假设假设 有限合理性原理有限合理性原理 搜索 Computer Science Empirical InquiryComputer Science Empirical Inquiry： Symbols and SearchSymbols and Search 嘶 湿 饿 徽 迢 糕 绒 颂 箩 珠 儡 贸 美 反 赵 酒 仿 贝 蒂 仔 叙 绍 莫 葵 况 雇 拂 师 咸 蕊 桐 券 状 态 空 间 法 状 态 空 间 法 Herbert Alexander Simon （1
2、916- 2001） 1975年第一届图灵 奖获得者，LT发明 者之一，1978年诺 贝尔经济学奖获得 者 Allen Newell （1927 -1992 ） 1975年第 一届图灵奖获得者 ，LT发明者之一， 美国人工智能学会 AAAI的发起人之一 鸳 熙 依 舵 葬 叛 狮 梆 庶 膀 碗 抑 统 谚 辕 姥 复 冯 谋 逐 性 伦 赴 港 歹 玛 龟 韩 烦 哆 们 需 状 态 空 间 法 状 态 空 间 法 LT 逻辑理论家 ILP 归纳逻辑程序设计 2.1.1 2.1.1 状态空间法状态空间法 1 1）问题描述）问题描述 状状 态：问题求解中每一步问题状况的数态：问题求解中每一步问
3、题状况的数 据结构据结构 状态描述：符号、字符串、向量、二维数状态描述：符号、字符串、向量、二维数 组、树、表等数据结构表示的问题状态组、树、表等数据结构表示的问题状态 例例 2-1 2-1 八数码难题八数码难题 万 醉 延 廖 爪 辅 基 婴 辣 鸭 狂 扼 村 铣 癣 懂 计 吃 舆 函 悟 珐 液 差 尔 幻 虹 属 态 瞳 凸 数 状 态 空 间 法 状 态 空 间 法 初始状态初始状态 目标状态目标状态 图图 2-12-1 八数码难题八数码难题 X1X2X3 X4X5 X6X7X8 X1X2X3 X4X5X6 X7X8 状状 态：态：棋盘布局每一步的状态棋盘布局每一步的状态 状态描述
4、：状态描述：图表、二维矩阵图表、二维矩阵 算算 符：符：把问题从一种状态描述转变为把问题从一种状态描述转变为 另一种状态描述的运算另一种状态描述的运算 算符集合：算符集合：问题求解中所有算符的集合问题求解中所有算符的集合 彭 墓 任 津 饲 终 醉 四 值 肖 剪 负 她 类 庄 袖 刮 炽 乾 锦 泼 详 肢 缠 戏 友 褐 艳 确 栖 策 右 状 态 空 间 法 状 态 空 间 法 八数码算符：八数码算符：EL- EL- 空格左移空格左移 ER- ER-空格右移空格右移 EU- EU-空格上移空格上移 ED- ED-空格下移空格下移 约约 束：束：E1E1，4 4，6 - 6 - 禁止禁止
5、ELEL E1 E1，2 2，3 - 3 - 禁止禁止EUEU E3 E3，5 5，8 - 8 - 禁止禁止ERER E6 E6，7 7，8 - 8 - 禁止禁止EDED 雀 佳 宵 项 喻 满 瓷 贾 酝 隅 杭 吝 扇 绰 沏 仰 霉 封 显 鹅 力 闪 呆 票 浴 特 苇 壕 修 衣 沂 罕 状 态 空 间 法 状 态 空 间 法 例例2-2 2-2 代数式简化问题。代数式简化问题。 (AB+CD)/BC A/C+D/B (AB+CD)/BC A/C+D/B 状态描述：二元树法状态描述：二元树法 非非 终终 端：节点算术运算符号端：节点算术运算符号+ +、- -、* *、/ / 终端节点
6、：变量、常量终端节点：变量、常量 树图：树图： AB C D B C ACD B 图图2-2 2-2 代数简化树图代数简化树图 吃 吗 痕 夏 缉 嫉 湿 歧 银 猎 追 德 榜 迎 遂 铡 咸 赫 零 越 咐 横 绚 殊 船 鸣 颁 凤 阔 雅 梯 搜 状 态 空 间 法 状 态 空 间 法 算符：算符：代数规则：代数规则： 分配律、结合律、。分配律、结合律、。 。 字符串法：字符串法： ABAB CDCD BC BC ACAC DBDB 前缀（只作用于两个运算数）前缀（只作用于两个运算数） 目标状态目标状态 单一目标状态单一目标状态 多目标状态：某一条件下产生的子状态集多目标状态：某一条件
7、下产生的子状态集 合。例如，象棋、围棋的终局合。例如，象棋、围棋的终局 八数码难题目标状态：最上面一行不存在编八数码难题目标状态：最上面一行不存在编 号大于号大于5 5的棋子的棋子 到 脸 瑶 及 艾 睫 咨 披 赋 闭 件 爪 荷 稻 矣 亲 社 乓 人 要 锌 蒸 恳 饮 囚 芬 犬 矾 悸 涨 摇 煌 状 态 空 间 法 状 态 空 间 法 最优化问题：最优化问题：寻找遵循某种规则的最优路寻找遵循某种规则的最优路 径径例如，例如，八数码难题求解中使用的算符最八数码难题求解中使用的算符最 少，走步最少（少，走步最少（最优解搜索问题最优解搜索问题） 状态描述三原则：状态描述三原则： （1 1
8、）状态描述方式选择，尤其是初始状态）状态描述方式选择，尤其是初始状态 （2 2）算符集合及其对状态描述的作用）算符集合及其对状态描述的作用 （3 3）目标状态描述特性）目标状态描述特性 2 2）图示法（问题求解的抽象描述）图示法（问题求解的抽象描述） （1 1）图论的几个概念）图论的几个概念 沛 岸 轧 界 进 牺 勃 淑 遣 厅 茎 淄 颇 腹 潘 弘 碧 睫 嫩 必 派 膏 砍 吵 吮 堰 豢 聪 窝 视 唯 阁 状 态 空 间 法 状 态 空 间 法 图：图：节点的集合，包括有限节点或无限节点节点的集合，包括有限节点或无限节点 。 有向图：有向图：节点之间用有向弧线联结的图。节点之间用有
9、向弧线联结的图。 节点：节点： nj 祖先祖先 后裔后裔 算符算符 状态状态i i ni 状态状态j j 图图 2 - 3 2 - 3 节点定义节点定义 他 仲 微 国 淡 厉 呀 疵 唬 屏 韶 拟 今 誉 中 刑 缚 灼 肝 拎 阵 寞 源 商 拷 圭 尿 供 潞 乎 捣 败 状 态 空 间 法 状 态 空 间 法 路径：路径：存在某个节点序列存在某个节点序列Nn=Nn=（n ni1 i1, n , ni2 i2, , n nij ij ,n ,nik ik） ）, , 令令j=2,3, ,kj=2,3, ,k，对每一个 ，对每一个n n ij ij -1-1, ,如果都存在后裔 如果都存
10、在后裔n n ij ij ，则称序列，则称序列NnNn为长为长 度为度为k k的路径的路径 可达节点：可达节点：如果两节点之间存在路径，则后如果两节点之间存在路径，则后 裔是祖先的可达节点裔是祖先的可达节点 弧线费用：弧线费用：弧线表示的算符计算的费用弧线表示的算符计算的费用 c(n c(n i i , n, n j j ) ) 路径费用：路径费用：路径上所有弧线费用之和路径上所有弧线费用之和 优化问题：优化问题：寻求图中最小费用路径寻求图中最小费用路径 见 艘 尖 奠 囚 犁 猜 袭 干 禽 骇 樟 出 助 乖 沏 阴 样 默 躲 渡 盾 孪 豹 卢 蒜 擅 靖 傲 疗 筒 牵 状 态 空
11、间 法 状 态 空 间 法 路径路径：k=10k=10 ，k=6k=6 可达节点：可达节点：j=2j=2，3 3，。，。，k k 路径费用：路径费用： n n i1i1 n n i2i2 n ni i3 3 n n ikik C(nC(ni4, i4, n n i5i5 ) ) 解 影 鸟 瑟 乎 嘛 泳 幼 玉 毛 茵 残 抛 寨 疏 铸 耶 婚 锐 芹 米 伶 右 锯 买 聂 掏 段 饶 渗 瘴 裂 状 态 空 间 法 状 态 空 间 法 优化问题：优化问题：寻求图中最小费用路径寻求图中最小费用路径 (2)(2) 问题求解的图描述问题求解的图描述 l l初始节点初始节点S S与目标节点集合
12、与目标节点集合t t i i 中任一节点中任一节点 之间的路径。之间的路径。 l l初始节点集合初始节点集合ss i i 中任一节点与目标节点中任一节点与目标节点T T 之间的路径。之间的路径。 l l初始节点集合初始节点集合ss i i 中任一节点与目标节点中任一节点与目标节点 集合集合t t i i 中任一节点之间的路径。中任一节点之间的路径。 (3) (3) 图分类图分类 障 骤 鲍 郑 厚 燃 揽 取 苟 隧 龚 号 阻 刀 皋 恕 恩 衅 瀑 柿 游 锐 羊 布 诬 题 馅 吼 缸 隙 宙 汹 状 态 空 间 法 状 态 空 间 法 显式图：显式图：各节点及其费用的弧线可以用图表各节
13、点及其费用的弧线可以用图表 或表格的形式明确给出或表格的形式明确给出 隐式图：隐式图：已知无限集合已知无限集合ss i i 及后裔算符及后裔算符L L， 则则ss i i 和和L L规定的图规定的图 3 3）状态空间求解举例）状态空间求解举例 例例 2-3 2-3 推销员旅行问题。一个推销员计划推销员旅行问题。一个推销员计划 作一次旅行，必须访问图作一次旅行，必须访问图2-42-4所示的每个所示的每个 城市。从城市城市。从城市A A出发，访问每一个城市一出发，访问每一个城市一 次，且最多一次，并返回城市次，且最多一次，并返回城市A A，求最短，求最短 距离路线。距离路线。 钝 敌 牡 淋 评
14、澡 氯 奴 婉 仑 政 赣 甥 伏 惺 堪 恕 硕 陶 显 法 邓 绦 快 鞭 毛 旱 时 磊 以 蓖 鞋 状 态 空 间 法 状 态 空 间 法 状态描述：状态描述：目前为止访问过的城市列表目前为止访问过的城市列表（AA） 初始状态初始状态: :（A A） 目标状态目标状态: : （A AA A） A A B B C C D D E 7 7 7 7 6 6 1010 5 5 6 6 9 9 1010 1313 图图2 4 2 4 推销员旅行问题地图推销员旅行问题地图 昼 乘 涂 勘 馋 荔 诣 旬 颇 瞻 止 犹 叫 蝎 潭 你 骸 铭 柳 蹭 壕 甭 须 驾 箱 综 泡 垛 亿 炊 没 嘛
15、 状 态 空 间 法 状 态 空 间 法 算符：算符：下一步走向的城市下一步走向的城市 (a)(b)(c)(d)(e) (a)(b)(c)(d)(e) 约束：约束：每个城市只能走过一次，每个城市只能走过一次，A A除外除外 (AE)(AE) (A)(A) (AB)(AB) (AC)(AC)(AD)(AD) (ACD(ACD ) ) (ACDE)(ACDE) (ACDEB)(ACDEB) (ACDEBA)(ACDEBA) 目标节点目标节点 初始节点初始节点 图图 2 - 5 2 - 5 推销员旅行问题搜索树推销员旅行问题搜索树 7 7 6 6 1010 1313 5 5 6 6 1010 7 7
16、 棱 锐 后 梯 嫉 攒 敢 烧 繁 烬 吼 盾 央 稠 酗 更 汛 脂 匪 旷 袄 骄 陀 昧 终 笨 窒 窃 狞 巴 萧 型 状 态 空 间 法 状 态 空 间 法 例例2-22-2猴子和香蕉问题猴子和香蕉问题 a c ba c b 猴子猴子 香蕉香蕉 箱子箱子 图图 2-8 2-8 猴子和香蕉问题猴子和香蕉问题 傍 息 蒲 炬 仙 主 鸟 咏 肩 压 恤 傲 惹 却 瘤 船 尿 检 吞 纤 坊 乓 倪 边 充 丹 敝 诗 允 刊 辕 剪 状 态 空 间 法 状 态 空 间 法 状态描述模式：用变量描述状态集合的表达式状态描述模式：用变量描述状态集合的表达式 猴子状态：猴子状态： 水平走动
17、水平走动 w w 上下箱子上下箱子 x0,1 x0,1，( 1=( 1=箱上，箱上，0 =0 =箱下箱下) ) 摘取香蕉摘取香蕉 z0,1 z0,1，(1= (1= 拿到拿到,0 = ,0 = 未拿到）。未拿到）。 箱子状态：箱子状态：水平移动水平移动Y Y 四种状态：四种状态：（W, x, Y, zW, x, Y, z） 算符集合：算符集合： goto(U) goto(U) (a,0,b,0) goto(U) (U,0,b,0) (a,0,b,0) goto(U) (U,0,b,0) pushbox(V) pushbox(V) (b,0,b,0) pushbox(V) (V,0,V,0) (
18、b,0,b,0) pushbox(V) (V,0,V,0) climbbox climbbox (V,0,V,0) climbbox (V,1,V,0) (V,0,V,0) climbbox (V,1,V,0) grasp grasp (c,1,c,0) grasp (c,1,c,1) (c,1,c,0) grasp (c,1,c,1) 拣 儡 农 岂 峙 惨 鞠 漾 均 靛 唯 铲 赋 蛹 槽 牛 宗 膏 呵 逮 都 厕 卯 吻 仁 宵 弊 捣 翁 谅 泛 狭 状 态 空 间 法 状 态 空 间 法 (a,0,c,0) (a,0,c,0) 初始状态初始状态 goto(U)goto(U) (U
19、,0,b,0)(U,0,b,0) goto(U)goto(U) (b,1,b,0)(b,1,b,0) U=b, climbboxU=b, climbbox U=b, pushbox(V)U=b, pushbox(V) (V,0,V,0)(V,0,V,0) pushbox(Vpushbox(V ) ) climbboxclimbbox (V,1,V,0)(V,1,V,0) V=c, graspV=c, grasp (c,1,c,1) (c,1,c,1) 目标状态目标状态 goto(U)goto(U) (U,0,V,0)(U,0,V,0) goto(U)goto(U) 图图2-9 2-9 猴子和香
20、蕉状态空间图猴子和香蕉状态空间图 窑 配 话 塌 循 铺 叭 力 廖 塑 阎 扒 狞 与 骤 恤 腻 纤 龋 邓 物 掉 斑 孤 澳 遭 钳 募 爆 附 乎 拽 状 态 空 间 法 状 态 空 间 法 人工智能经典问题：人工智能经典问题： 1 1 设有三个传教士和三个野人来到河边，打设有三个传教士和三个野人来到河边，打 算乘一只船从河右岸渡到河左岸去。该船算乘一只船从河右岸渡到河左岸去。该船 的最大负荷能力为两人。在任何时候，如的最大负荷能力为两人。在任何时候，如 果野人人数超过传教士人数，野人就会把果野人人数超过传教士人数，野人就会把 传教士吃掉。他们传教士吃掉。他们怎样怎样才能用才能用这条
21、船安全这条船安全 地地把把所有人都渡过河去所有人都渡过河去？ 2 2 把八个皇后摆在一个标准的国际象棋棋盘把八个皇后摆在一个标准的国际象棋棋盘 上，使得每行、每列以及每个对角线上都上，使得每行、每列以及每个对角线上都 只包含不多于一个皇后。画出部分状态空只包含不多于一个皇后。画出部分状态空 间图，写出算符规则。间图，写出算符规则。 结 趾 叁 寥 径 誉 莲 鲤 陀 呜 勋 宦 秆 牢 蓄 佛 姚 凭 帖 停 障 铰 阂 吟 搪 其 灯 沟 控 搏 泣 且 状 态 空 间 法 状 态 空 间 法 图图2 - 10 2 - 10 过河问过河问 题题 ？ 保 得 农 惦 戌 事 矽 翅 氏 翁 禾
22、 烫 蚜 袁 盂 蔓 禹 挤 课 扣 归 阅 腕 滤 哪 篓 腑 褐 监 糯 盯 硬 状 态 空 间 法 状 态 空 间 法 图图 2- 11 2- 11 八皇后问题八皇后问题 ？ ？ ？ ？ ？ 烩 满 瑞 话 喘 瓜 屏 帖 油 刃 睹 舞 歧 珍 毡 麓 渝 长 佬 堰 臣 支 澡 胞 肿 尖 琅 傍 这 框 宰 根 状 态 空 间 法 状 态 空 间 法 4 4）状态空间搜索策略）状态空间搜索策略 搜索过程要点：搜索过程要点： 图论法：图论法：起始节点起始节点 - -算符算符 扩展后继节点扩展后继节点 （子节点）（子节点）- -加指针加指针 - - - -检查后继检查后继 节点是否为目
23、标节点节点是否为目标节点 - -是，终止搜索是，终止搜索。 上述路径为问题的解上述路径为问题的解。否，继续扩展否，继续扩展。 搜索控制：宽度优先搜索 深度优先搜索 启发式搜索 刷 阮 横 排 声 吏 类 异 忘 蚊 诣 邢 摊 充 贷 窝 玻 眶 党 毯 兵 蔡 脂 殴 炎 爹 叙 橱 腑 传 穷 亨 状 态 空 间 法 状 态 空 间 法 图图2-12 2-12 宽度优先搜索宽度优先搜索 图图2-13 2-13 深度优先搜索深度优先搜索 盲目搜索盲目搜索: : 宽度优先搜索宽度优先搜索, ,深度优先搜索深度优先搜索 启发式搜索：启发式搜索：利用启发式信息进行搜索的过程利用启发式信息进行搜索的
24、过程 启发式信息：用来加速搜索的特别信息用来加速搜索的特别信息 孵 心 稽 试 合 进 塘 呢 阮 佑 秧 潭 胀 省 池 说 拭 骇 集 醉 载 士 漠 蛤 刃 描 斟 衙 坟 领 歼 锣 状 态 空 间 法 状 态 空 间 法 计算费用计算费用 信息量信息量 完整信息完整信息 规则应用费用规则应用费用 控制策略费用控制策略费用 系统总费用系统总费用 图图 2 - 12 2 - 12 人工智能系统计算费用人工智能系统计算费用 蝎 涣 程 煌 癣 雀 赌 屉 豁 孔 傣 圾 捧 义 瘫 聘 叠 钠 荫 袭 耿 憎 促 疙 虞 畔 后 砌 蚜 胁 窃 梧 状 态 空 间 法 状 态 空 间 法
25、如何选择下一节点？ . 如何决定选定下一个节点 的过程中生成的节点数？ 如何决定搜索树中抛弃或 修剪的节点？ 估价函数（启发信息）：估计节点可扩展“ 希望”程度的 函数 虎 惶 拥 较 氨 膊 郊 局 侄 盛 僳 荷 炸 染 凹 酒 提 怀 诣 汪 汽 围 抬 硝 掩 谈 戊 厕 万 捻 娶 娩 状 态 空 间 法 状 态 空 间 法 S 1 2 3 45 6 S 1 2 3 45 6 （a a）节点）节点1 1扩展前扩展前 （b b）节点）节点1 1扩展后扩展后 修剪：节点修剪：节点1 1扩展前后的搜索树扩展前后的搜索树 已扩展节点 未扩展节点 溃 险 神 家 挠 痛 朴 光 霍 乱 泊 杂
26、 誊 妨 如 特 渠 熬 头 谢 莽 刁 矛 疮 拆 乞 捐 康 锤 瑶 墅 澡 状 态 空 间 法 状 态 空 间 法 启发式搜索算法：启发式搜索算法：有序状态空间搜索有序状态空间搜索 定义：定义： S S - - 问题初始状态问题初始状态 T - T - 问题目标状态问题目标状态 n n i i - i - i时刻的问题状态时刻的问题状态 f(n) - f(n) - 估价函数，单调减估价函数，单调减 OPEN OPEN表表-节点未扩展时，搜索图的数据结构节点未扩展时，搜索图的数据结构 CLOSED CLOSED表表-节点扩展后，搜索图数据结构节点扩展后，搜索图数据结构 履 疮 咏 匀 备
27、姜 桌 续 衰 学 骚 指 蕾 埔 辟 漆 悍 骆 忙 兆 太 拢 磐 酝 鹏 脑 提 迸 莉 突 推 旧 状 态 空 间 法 状 态 空 间 法 S入OPEN 标出f(S) OPEN空？ 失败，退出 计算f(ni)，i=1,2 MINf(ni)入CLOSED Y N ni=T？ Y N 扩展ni,生成全部后继 节点。计算每个后继 节点f(nij) nij=T？ nij在CLOSED？ nij,加入OPEN，从nj加一指向节点nij的 指针。计算f(nij),按 f(n)小-大排序 N N f(nij)f*(S)， 携 早 凛 祈 锚 整 贞 判 塔 俱 沽 寐 缕 渝 呆 胰 淳 拂 苹 心
28、 段 娟 慈 量 罐 痹 沧 滤 试 亥 晤 素 状 态 空 间 法 状 态 空 间 法 根据结论1，终止前OPEN表上存在一个 节点n，且满足： f(n)h1(n)，且存在一条从S到T 的最佳路径, A1, A2都中止在最佳路径上。 砍 侄 掇 冒 序 畏 纸 寞 焕 岁 巳 罢 陛 篮 滨 荤 耕 损 头 无 亡 咎 孪 镇 馅 啤 很 铁 菲 敢 勾 调 状 态 空 间 法 状 态 空 间 法 证明：在终止的地方，如果图G的节点n能够 用A2来扩展，那么，也必定能用A1来扩展。因 此， A1扩展的节点数至少与用A2扩展的节点数 一样多。 n = S，若S=T，两种算法都不必扩展节点 b.
29、 若ST，两种算法都要扩展S 归纳法假设：A1扩展了A2搜索树中深度 k 的 所有节点 证明：A2搜索树中由A2扩展的深度k+1的任意节 点n也可由A1扩展 A2 d=k n A1 d=k+1 牵 炳 绒 坤 皮 彪 痹 匆 苏 萌 交 米 瑰 柿 狈 劣 纤 由 满 弓 芬 恋 趋 暂 秽 燕 豌 羌 盘 昔 拽 袄 状 态 空 间 法 状 态 空 间 法 根据假设，A2搜索树中n的任一父辈节点都可由 A1扩展。因此，节点n也在搜索树A1中 存在： g1(n) g2 (n) (1) 反证：A1不能扩展由A2扩展的节点n A1终止的地方，节点n必须在OPEN表上。因为A1 已扩展了n的一个父辈
30、节点。由于A1没有扩展节 点n而在最小路径上终止。所以： f1(n)=g1(n)+h1(n) f*(S) (2) g2(n)+h1(n)g1(n)+h1(n)f*(S) (3) h1(n)f*(S)g2(n) (4) 认 柏 枢 茬 祭 胳 液 捉 孝 泵 犁 效 邑 轧 仿 淡 莫 醛 跃 棕 签 九 藐 粮 蒙 昌 拜 振 塌 挺 围 披 状 态 空 间 法 状 态 空 间 法 由A*选来扩展的任一节点n，满足： f(n) f*(S) 由于A2已经扩展了节点n，所以： f2(n) = g2(n)+h2(n) f*(S) (5) h2(n) f*(S) g2(n) (6) 比较（4），（6）
31、两式得： h2(n) f*(S) g2(n) h1(n) 至少在节点n，h1(n)=h2(n)，与A2比A1有更多信 息的假设矛盾。 俯 荤 属 佬 比 尉 壳 譬 遁 拈 化 大 舵 利 趋 乙 牌 菲 冕 秦 爸 召 盂 禄 据 袁 抨 衰 着 区 檬 垣 状 态 空 间 法 状 态 空 间 法 结论4： 若A1和A2是A*的两种搜索形式，且A2 比A1有更多的信息。则在从S到T的路径搜索终 止处，由A2所扩展的每一个节点，也可以由A1 扩展。因此，A1扩展的节点数至少和A2一样多 。 h的单调限制 为避免生成的后继节点在OPEN或CLOSED表中 ，给h一个合理的限制 单调限制：如果对所
32、有节点ni 及其后继节 点nj，使得当h(t)=0时下式成立： 0 h(ni) h(nj) c(ni,nj） 则h满足单调 品 巍 副 翘 铲 豌 感 籽 滑 蛆 板 卒 坍 括 摧 持 娠 陛 姨 渤 笔 糙 秉 盐 坤 拭 尹 仇 孩 花 窝 救 状 态 空 间 法 状 态 空 间 法 结论5：如果h满足单调限制，若A*选n扩展，则 g(n)=g*(n) 证明： 设 n为A*要扩展的节点 a. 若n=S,则A*已找到一条最佳路径 b. 若nS,设序列S=n0,n1, ,nk=n是S到n 的一条最佳路径。令nl是这个序列的最后一个节 点。 A*扩展时nl在CLOSED表上，nk，nl+1在O
33、PEN 表上 驯 材 昧 隧 财 幼 拭 替 槛 师 租 踢 捅 匡 伏 酪 耻 悟 蕴 哀 斤 惶 逞 孵 辉 勿 医 联 缕 山 竹 嫂 状 态 空 间 法 状 态 空 间 法 h单调： h(ni) c(ni,ni+1)+ h(ni+1) g*(ni)+h(ni) g*(ni)+h(ni+1)+c(ni,ni+1) 又 ni和ni+1在最佳路径上 g*(ni+1)=g*(ni)+c(ni,ni+1) g*(ni)+h(ni) g*(ni+1)+h(ni+1) g*(nl+1)+h(nl+1) g*(nk)+h(nk) f(nl+1) g*(n)+h(n)=f(n) 当A*选择节点n而不是节
34、点nl+1时，g(n) g*(n) 必须成立，否则，f(n)可能大于f(nl+1)。但是 ，由定义,对搜索树中所有节点m存在： g(m) g*(m) 必有 g(n)=g*(n) 证毕 置 模 邱 佯 载 摊 凉 堑 滋 跑 缸 书 高 姥 雁 次 反 勉 隘 际 跳 蘸 呛 食 腥 纪 饥 悠 体 续 驴 按 状 态 空 间 法 状 态 空 间 法 结论6：如果满足单调限制，那么由A*所扩展的 节点序列的f值非递减。 证明： a. 设扩展n1时，n2在OPEN表上 f(n1) f(n2) b. 设扩展n1时，n2不在OPEN表上，则 f(n2)=g(n2)+h(n2)= g*(n2)+h(n2
35、) =g*(n1)+c(n1,n2)+h(n2) =g(n1)+ c(n1,n2)+h(n2) c(n1,n2)+h(n2) h(n1) f(n2) g(n1)+h(n1)=f(n1) 证毕 枚 侄 昔 佛 藩 院 善 幅 壮 糖 扣 恫 缉 凹 侥 酌 藻 下 忌 厉 柑 坏 弛 尉 朋 辗 融 旭 碴 葬 吁 捻 状 态 空 间 法 状 态 空 间 法 h的启发能力 例： 八数码难题的较好估计： h(n)=P(n)+3S(n) P(n): 每个棋子离家距离的总和。 S(n): 棋子排列顺序的计分值。依次检验非中 心方格的棋子，如果某棋子后跟的棋子和目标 顺序不同，则该棋子得2分，一致得0分
36、，所有 棋子得分综合为S(n)。 影响启发能力的因素 u路径费用 u寻找路径时所扩展的节点数目 uh的计算量 从 诀 蕊 烧 详 幅 晋 斥 解 嗡 羚 谓 憎 灰 逆 本 胀 凑 吼 蒜 姑 骂 荔 墨 说 静 掸 久 桅 搬 奴 饱 状 态 空 间 法 状 态 空 间 法 美卫星首次实现在轨自动补给燃料 2007年4月5日美国宇航局太空网报道 ASTRO卫星(左)与NextSat卫星(右) ASTRO卫星的太阳能帆板 悯 红 粥 喊 祥 茅 睫 苹 仰 亿 苛 澳 找 哀 丛 按 虐 盟 楚 峭 柯 甸 龋 灸 宙 年 蚜 樊 芋 疑 什 卜 状 态 空 间 法 状 态 空 间 法 美国“
37、轨道快车计划”(Orbital Express ) 发起单位：美国国防预先研究计划局（DARPA） 美国首创技术：卫星修复、自主机器人、在轨 燃料加注 任务：发送低成本航天器对更昂贵的故障卫星 进行修复和燃料燃料补给 平台：航天器（3亿美元） ASTRO：主动航天器，模拟自主空间转移及机 器人轨道器 NextSat：扮演补给站，又扮演被修复的客户 卫星的角色 位 撇 东 葛 脚 弗 阜 熙 盾 疵 钡 境 桌 瞥 诞 谐 霍 拙 貌 柜 培 了 串 攒 贷 虎 翅 冈 月 鸽 拧 滩 状 态 空 间 法 状 态 空 间 法 航天器制造：波音幻影工作室和鲍尔宇航公司 建造 实验过程：2007年3
38、月8日从卡纳维拉尔角空军 基地发射。两颗卫星绕距地球300英里（483公 里）高的轨道飞行。系列实验包括：利用机器 臂进行多次交会、捕获与转移操作 “情景0”试验： l ASTRO推进剂箱中的肼燃料泵入到NextSat 中， ASTRO携带约重300磅（136千克）的推进 剂，用于燃料加注试验和之后的交会操作 疲 卫 故 咙 栏 衙 削 诧 柳 嘲 译 蹿 怂 连 浊 家 止 药 控 苦 啪 蕊 佯 锡 荒 举 哉 缄 援 孰 熬 作 状 态 空 间 法 状 态 空 间 法 燃料输送试验：尝试以不同的流动速率，利用 泵式加注和压力加注两种方法进行试验 机械臂目标捕获试验：机器臂将从ASTRO抓
39、取 替换单元（一节电池、传感器处理计算机 ）备用电池，并插入到NextSat上。（机器 臂数次将电池在ASTRO和NextSat之间进行 来回转移，但在不进行转移时，电池将会 留在NextSat上提供外部动力。依照设计 程序，在任务后期加入传感器处理计算机 ，将其从ASTRO移走后再放置回去，以试 验传感器处理计算机的接口界面） 站 酪 秉 琉 徘 日 泛 物 耸 掩 层 绕 摘 犯 召 识 架 杂 粮 战 昭 惭 臻 禽 宽 粗 媚 缘 獭 曲 胁 赠 状 态 空 间 法 状 态 空 间 法 情景1（Scenario 1）：重达156磅的机器臂抓住NextSat ，把它推离ASTRO，预计持
40、续11天。试验中，NextSat未 固定，以便丢弃连接两颗卫星的结合环。此后，ASTRO 还将再次抓取NextSat进行燃料补给试验，转移备用轨 道替换单元。NextSat可通过对接或利用ASTRO上的机器 臂被抓取 在情景2（Scenarios 2） 情景5：设计了一系列渐进 的步骤，将使ASTRO与NextSat分离，在3周内逐渐增大 它们之间的距离 情景6（Scenarios 6） 情景8：为进行远距离 交会验证试验，ASTRO将上升至距离NextSat7千 米的高度上。当NextSat再次对接时，ASTRO将 再次向NextSat输送燃料，并与NextSat进行备 用部件的转移。 团
41、拐 镜 郎 囊 嗽 嫂 掳 囊 椰 茅 晰 袜 猩 数 逆 全 卧 扭 喊 泪 产 寺 欺 派 梁 疥 罗 苫 嗅 利 我 状 态 空 间 法 状 态 空 间 法 虽然试验计划允许ASTRO主动飞近NextSat，但 控制对接试验的自动控制软件给地面控制者在 出现错误时中断验证的机会。 “轨道快车”任务计划预计持续三个月，两颗卫星 设计寿命为至少一年。计划任务完成，该任务 将继续参加最多四项空军太空司令部的附加试 验。 目标及意义 l 使未来军用侦察卫星通过提供足够的燃料， 对地面目标进行位置保持 l该项技术还可以通过在轨维修和设备更换与 升级，帮助延长民用卫星的使用寿命 谤 沼 谨 韧 衡
42、天 膘 耗 闯 佣 欧 里 诗 怨 缸 问 杂 砧 坤 悔 悬 败 策 瑞 彼 谴 苍 祖 莫 拥 懊 亨 状 态 空 间 法 状 态 空 间 法 民用卫星： 运行在赤道上空35887公里轨道上的 通信卫星，适于开展轨道维修任务；后勤服务 还适用于航天器组件。操作者可以计划定期更 换电池或计算机（这两样装置都限制卫星寿命 ）以保持卫星状态或对老化的卫星进行系统升 级。 军事卫星：军方可以在危险地区进行卫星机动 ，而不必担心推进剂的用量，因为可以发射燃 料补给航天器。 轨道容错：因发射问题而定位于错误轨道的卫 星，也可以利用轨道燃料补给卫星解决这一问 题。未进入轨道的卫星离开低轨道所消耗的储 备
43、燃料可以得到补充，使得卫星可以完成任务 ，不至于完全失败。实用型的“轨道快车”还 将包括在轨卫星网络。 蘸 酉 蚁 支 踊 勒 戈 淆 忙 硅 滓 久 漂 咕 定 鞘 汤 岁 维 仔 醚 茧 慈 奇 减 帖 迪 四 砸 浙 狠 皂 状 态 空 间 法 状 态 空 间 法 例： 卫星在轨油料补给系统的故障诊断 Orbital Refueling System（ORS） 氮气 氮气 氮气 氮气 横膈膜 肼 肼 高压 低压 高压 阀门 羞 螺 桩 檀 蔫 洛 掖 腆 烩 屡 仟 慎 容 隆 滚 赫 娄 攻 拳 遭 韵 牺 纠 嫌 递 镊 弄 翠 庇 奥 蒜 重 状 态 空 间 法 状 态 空 间 法
44、 状态描述： （ Ti ,pu ,pd ,v） i = 1,2 pu = a,b,c,d,e pd = a,b,c,d,e v = v1,v2,vn 算符集合： Open_v Increase_Ti_Pu decrease_Ti_Pu 她 阳 楚 该 斥 晃 棺 弓 窍 追 拒 级 士 痈 泛 猴 窍 串 青 世 寺 由 赋 道 混 撮 蔬 楼 授 硅 贷 讽 状 态 空 间 法 状 态 空 间 法 Increase_Ti_Pd decrease_Ti_Pd 约 束：PMin Pu PMax, 0 Pu VMax 搜索策略： A* 启发式信息： 人工燃料补给工作及故障排除手册 潦 隅 陋 坯 堰 啤 昔 八 吩 帜 缎 幅 抱 命 刘 镐 锭 伴 寄 冶 撼 政 呈 魂 顷 普 阻 树 胡 唐 芍 螟 状 态 空 间 法 状 态 空 间 法