人工智能基础（第2版）-高济-第五章.pptVIP

第五章 自动规划 规划是人类生产和社会活动的重要形式。 规划旨在为活动实体（人、组织、机器）设计合理的行为——按时间顺序的活动序列。 从知识工程的角度，自动规划是综合和构造型问题求解任务。 规划问题处理的对象是动作，而约束动作的主线是时间顺序。 经典的自动规划技术： 经典规划技术的发展， 规划的基本概念， 早期的自动规划技术， 部分排序规划技术； 自动规划技术的新进展及其实际应用（简略）。 5.1.经典规划技术5.1.1. 经典规划技术的发展 规划技术的研究起始于60年代，依赖于有哪些信誉好的足球投注网站和定理证明技术的开发。 GPS（通用问题求解系统）——最早的规划系统： 基于操作符-差别表技术； 给规划的实现设置了以下假设： 计划（作为规划的结果）是动作序列， 执行计划的目的是到达目标状态， 动作的执行结果是完全可预言的。 经典规划——遵循该假设的规划技术，八十年代中期以前盛行。 Green方法——将规划问题的解决归约到定理证明：引入状态演算去演绎动作序列。 GPS和Green方法都只能用于解决简单的规划问题——难以使用和效率低。 5.1.1. 经典规划技术的发展 STRIPS——机器人动作规划系统，斯坦福研究所，1969年，著名； 用类似于状态演算形式的动作定义取代GPS中的操作符-差别表， 在综合运用GPS和Green方法优点的同时避免了它们的许多缺点； 有哪些信誉好的足球投注网站控制方式过于简单，难以解决复杂的规划问题。 部分排序规划技术——70年代中期，突破性进展： NOAH系统和目标回归方法——开拓了基于部分计划集的有哪些信誉好的足球投注网站技术， 能解决所有的经典规划问题——通过层次规划和非线性规划， 未得到广泛的应用——大量实际规划问题并不遵从经典规划问题的假设。 开拓非经典的实际规划问题（八十年代中期后）： 为消除规划理论和实际应用间存在的差距， 部分排序规划技术仍是开发规划新技术的基础。 5.1.2. 规划的基本概念 总体描述： 用状态空间表示法来描述规划： 设计一个动作序列（也称为动作块），使得通过执行该动作序列，可以将系统从初始状态转变为目标状态。 自动规划系统由规划器和执行器二个部分构成（图5.1）。 引入五个方面的基本概念：状态、动作、数据库、框架问题和计划。 玩具世界——积木块世界中的机器人动作规划： 积木块世界中有三个积木块：A、B、C， 机器人只有一个机器手，且每次只能拿起一个积木块。 1 状态 在一个给定的时间点对于世界的一个快照。 二元约束T——描述某个状态S下关于世界的特性， 特性用谓词公式加以表示——On、Clear和Table。 积木块世界的某个状态S1（见图5.2）： {T(On(A，B), S1), T(On(B,C), S1), T(Clear(A), S1), T(Table(C), S1)} 目标状态的非唯一性。 5.1.2. 规划的基本概念2 动作 经典规划的假设——世界的变化只能是由于执行器(如机器人)执行了某些动作。 动作——规划系统定义的操作符的实例。 积木块世界为机器人定义的三个操作符： U：Unstack(x, y)——将x从y上取走，并放置到桌子上， S：Stack(x, y)——将桌子上的x放置到y上， M：Move(x, y, z)——将x从y上移动到z上。 Do函数——动作的执行对于世界的影响： 以Do(a, s)表示动作a的执行将状态s转变为下一状态： Do: A X S ? S， A和S分别指示动作集和状态集； Do(a. s)指示下一状态。 2 动作 关于操作符的规则——形式地描述操作符的激活条件和其执行对于世界的影响： U: T(On(x, y), s) ∧ T(Clear(x), s) ? T(Table(x), Do(U(x, y), s))∧T(Clear(y), Do(U(x, y), s))； S: T(Table(x), s)∧T(Clear(x), s)∧T(Clear(y), s)∧x ≠ y ? T(On(x, y), Do(S(x, y), s))； 关于操作符M的规则留给读者自行建立。 [U(A, C), S(B, C), S(A, B)] 动作序列——规划的结果，以方括号括起，称为动作块（图5.3）。 动作块公理：T(P, Do(a.l, s)) ? T(P, Do(l, Do(a, s))) 定义：Do(a.l, s) ? Do(l, Do(a, s))， 例：Do([U(A, C), S(B, C), S(A, B)], s) ? Do([S(B, C), S(A, B)], Do(U(A, C), s)) ? Do(S(A, B), Do