Al Planning 吉建民 USTC jianminOustc.edu.cn 2022年4月22日 口·三4，进分双0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . AI Planning 吉建民 USTC jianmin@ustc.edu.cn 2022 年 4 月 22 日
Used Materials Disclaimer:本课件大量采用了网络课程课件，也采用了GitHub 中开源代码，以及部分网络博客内容 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Used Materials Disclaimer: 本课件大量采用了网络课程课件，也采用了 GitHub 中开源代码，以及部分网络博客内容
Table of Contents 自动规划概述 经典规划(Cl3 ssical Planning 规划问题 状态空间规划(State-Space Planning 规划空间规划(Plan-Space Planning 新经典规划(Neoclassical Planning 规划图技术(Planning-Graph Techniques) Planning as SAT.CSP.ILP... 经典规划的扩展 分层任务网规划 不确定规划 非确定规划 概率规划 口卡4三4色进分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 自动规划概述 经典规划 (Classical Planning) 规划问题 状态空间规划 (State-Space Planning) 规划空间规划 (Plan-Space Planning) 新经典规划 (Neoclassical Planning) 规划图技术 (Planning-Graph Techniques) Planning as {SAT, CSP, ILP, …} 经典规划的扩展 分层任务网规划 不确定规划 非确定规划 概率规划
Automatic Planning Planning in Artificial Intelligence is decision making about the actions to be taken. 自动规划(Automatic Planning)起源于60年代，是人工智 能的一个重要领域。近年来，自动规划在问题描述和问题求 解两方面分别取得新的突破，从而在理论和应用方面取得长 足进展，应用在智能机器人、网络服务、自动驾驶等 ·自动规划有两大任务； ·(1)问题描述，如何方便（紧凑、便于计算）的表示规划问题 (2)问题求解，如何高效的求解规划问题（等价于一个搜索 问题) 每于 我们从这两个方面出发，介绍人工智能规划领域的主要工 作，包括经典规划(Classical Planning),新经典规划 (Neoclassical Planning),不确定规划(Planning under Uncertainty) 口◆461三1，是90C
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Automatic Planning ▶ Planning in Artificial Intelligence is decision making about the actions to be taken. ▶ 自动规划 (Automatic Planning) 起源于 60 年代，是人工智 能的一个重要领域。近年来，自动规划在问题描述和问题求 解两方面分别取得新的突破，从而在理论和应用方面取得长 足进展，应用在智能机器人、网络服务、自动驾驶等 ▶ 自动规划有两大任务: ▶ (1) 问题描述，如何方便 (紧凑、便于计算) 的表示规划问题 ▶ (2) 问题求解，如何高效的求解规划问题（等价于一个搜索 问题） ▶ 我们从这两个方面出发，介绍人工智能规划领域的主要工 作，包括经典规划 (Classical Planning)，新经典规划 (Neoclassical Planning)，不确定规划 (Planning under Uncertainty)
规划方法分类 规划方法可以分为以下三类 ·领域特定(Domain-specific):针对具体领域专门设计的特定 规划方法。通常会利用领域特性，设计出更高效的算法 领域无关(Domain-independent):不针对具体领域的通用规 划方法。相较于领域特定的规划方法有以下不同： ·领域无关规划是对规划方法共性的研究，其成果可以用来提 高领域特定规划方法的效率 ·是对通用规划行为的研究，从人工智能的角度研究其所表现 出的理性行为 ·对具体问题可以直接应用，相对于领域特定方法是更廉价的 规划器 是一般智能体所需要具备的通用规划能力 可配置(Configurable):在领域无关方法的基础上，针对具体 问题可以增加控制信息，从而利用问题领域特征，使规划更 高效 在Al领域，规划(Planning)一般指Domain-independent Configurable Planning 口+，·三。4进分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 规划方法分类 规划方法可以分为以下三类 ▶ 领域特定 (Domain-specific): 针对具体领域专门设计的特定 规划方法。通常会利用领域特性，设计出更高效的算法 ▶ 领域无关 (Domain-independent): 不针对具体领域的通用规 划方法。相较于领域特定的规划方法有以下不同: ▶ 领域无关规划是对规划方法共性的研究，其成果可以用来提 高领域特定规划方法的效率 ▶ 是对通用规划行为的研究，从人工智能的角度研究其所表现 出的理性行为 ▶ 对具体问题可以直接应用，相对于领域特定方法是更廉价的 规划器 ▶ 是一般智能体所需要具备的通用规划能力 ▶ 可配置 (Configurable): 在领域无关方法的基础上，针对具体 问题可以增加控制信息，从而利用问题领域特征，使规划更 高效 在 AI 领域，规划 (Planning) 一般指 Domain-independent 和 Configurable Planning
智能规划 ·规划领域主要两个工作：如 何方便的（紧凑并且方便求 解)表达和如何高效求解 Initial state (搜索) ·表示：状态、行动 ·状态：（动态）系统在 桌只 某时刻的情况，问题 Goal state 的状态描述 初始状态、目标状态 ·行动：状态空间上的 部分映射，对状态描 述进行变换的一组操 作 求解：计算（搜索）出从 初始状态变化到目标状 态的一个操作序列 onh道asau 日e绿里 状态空间搜索，偏序 规划，规划图 Planning as {SAT CSP,ILP,-},等 日+4+4二1在)QG
. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . 智能规划 ▶ 规划领域主要两个工作：如 何方便的（紧凑并且方便求 解）表达和如何高效求解 （搜索） ▶ 表示：状态、行动 ▶ 状态：（动态）系统在 某时刻的情况，问题 的状态描述 初始状态、目标状态 ▶ 行动：状态空间上的 部分映射，对状态描 述进行变换的一组操 作 ▶ 求解：计算（搜索）出从 初始状态变化到目标状 态的一个操作序列 ▶ 状态空间搜索，偏序 规划，规划图， Planning as {SAT, CSP, ILP, …}，等
规划问题基本假设 规划问题非常复杂，为简化问题而提出一些简化的假设（经 典规划基本假设)： ,(AO)有限系统(Finite system):问题只涉及有限的状态、行 动、事件等 ·(A1)完全可观察(Fully observable):永远知道系统当前所在 的状态 ·(A2)确定性(Deterministic):每个行动只会导致一种确定的 影响 ·(A3)静态性(Static):不存在外部行动，环境所有的改变都来 自控制者的行动 ·(A4)状态目标(Attainment goals):目标是一些需要达到的目 标状态 ,(A5)序列规划(Sequential plans):规划结果是一个线性行动 序列 ·(A6)隐含时间(Implicit time):不考虑时间持续性 ~(A7)离线规划(Off--line planning):规划器不考虑执行时状态 ，口，。三，4告进 )Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 规划问题基本假设 ▶ 规划问题非常复杂，为简化问题而提出一些简化的假设（经 典规划基本假设）： ▶ (A0) 有限系统 (Finite system): 问题只涉及有限的状态、行 动、事件等 ▶ (A1) 完全可观察 (Fully observable): 永远知道系统当前所在 的状态 ▶ (A2) 确定性 (Deterministic): 每个行动只会导致一种确定的 影响 ▶ (A3) 静态性 (Static): 不存在外部行动，环境所有的改变都来 自控制者的行动 ▶ (A4) 状态目标 (Attainment goals): 目标是一些需要达到的目 标状态 ▶ (A5) 序列规划 (Sequential plans): 规划结果是一个线性行动 序列 ▶ (A6) 隐含时间 (Implicit time): 不考虑时间持续性 ▶ (A7) 离线规划 (Off-line planning): 规划器不考虑执行时状态
规划问题分类 利用上述假设我们可以区分所研究的规划问题，其中经典规划问 题就是满足从A0到A7所有假设的规划问题 Stochastic Parkally Obsorvabla Oees常e游脚一 "Classical Planning 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 规划问题分类 利用上述假设我们可以区分所研究的规划问题，其中经典规划问 题就是满足从 A0 到 A7 所有假设的规划问题
经典规划扩展 经典规划虽然做了很多简化，但复杂性还是很高，在实际应 用中很难使用 新经典规划在这方面带来了可喜的进展，分别用图规划技 术、SAT技术、CSP技术等方法来解决经典规划问题 ~另一方面，现实不可避免的具有不确定性(uncertainty),因 为： ·信息不完全性：对世界的描述是不可能完全的 ·不可预测性：外部事件的发生是不可预测的 行动不确定性：有些行动效果本质上就是不确定，如投骰子 对不确定性的描述可以采用非确定性(Nondeterministic)方 法，也可以采用概率方法：对于环境观察可以是完全的，也 可以是部分的或者完全不可观察的 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 经典规划扩展 ▶ 经典规划虽然做了很多简化，但复杂性还是很高，在实际应 用中很难使用 ▶ 新经典规划在这方面带来了可喜的进展，分别用图规划技 术、SAT 技术、CSP 技术等方法来解决经典规划问题 ▶ 另一方面，现实不可避免的具有不确定性 (uncertainty)，因 为: ▶ 信息不完全性: 对世界的描述是不可能完全的 ▶ 不可预测性: 外部事件的发生是不可预测的 ▶ 行动不确定性: 有些行动效果本质上就是不确定，如投骰子 ▶ 对不确定性的描述可以采用非确定性 (Nondeterministic) 方 法，也可以采用概率方法; 对于环境观察可以是完全的，也 可以是部分的或者完全不可观察的
Table of Contents 自动规划概述 经典规划(Classical Planning) 规划问题 状态空间规划(State-Space Planning 规划空间规划(Plan-Space Planning 新经典规划(Neoclassical Planning 规划图技术(Planning-Graph Techniques) Planning as [SAT,CSP.ILP.. 经典规划的扩展 分层任务网规划 不确定规划 非确定规划 概率规划 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents 自动规划概述 经典规划 (Classical Planning) 规划问题 状态空间规划 (State-Space Planning) 规划空间规划 (Plan-Space Planning) 新经典规划 (Neoclassical Planning) 规划图技术 (Planning-Graph Techniques) Planning as {SAT, CSP, ILP, …} 经典规划的扩展 分层任务网规划 不确定规划 非确定规划 概率规划