Table of Contents 自动规划概述 经典规划(Classical 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, …} 经典规划的扩展 分层任务网规划 不确定规划 非确定规划 概率规划
经典规划基本假设 ·经典规划就是满足从A0到A7所有假设的规划问题，这种 系统是确定的，静态的，有限的，完全可观察的，并且是受 限目标和隐藏时间的状态转移系统 经典规划的任务，简单说就是：Computing paths from an initial state to a goal state in the transition graph. ~已知transition graph,用Dinkstra算法（时间复杂度 为O(n log n))】 ·但状态空间一般非常大(109,1012,1015，)，所以无法构造 出整个transition graph ,规划算法要避免构造出整个transition graph 4口◆4⊙t4三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 经典规划基本假设 ▶ 经典规划就是满足从 A0 到 A7 所有假设的规划问题，这种 系统是确定的，静态的，有限的，完全可观察的，并且是受 限目标和隐藏时间的状态转移系统 ▶ 经典规划的任务，简单说就是：Computing paths from an initial state to a goal state in the transition graph. ▶ 已知 transition graph，用 Dinkstra 算法（时间复杂度 为 O(n log n)） ▶ 但状态空间一般非常大 (109 , 1012 , 1015, …)，所以无法构造 出整个 transition graph ▶ 规划算法要避免构造出整个 transition graph
经典规划 经典规划只考虑确定的、静态的、有限的、完全可观察的、 离散环境的、目标受限和忽略时间的状态转移系统 多子 经典规划的主要问题包括： ·如何在不显式枚举的情况下，形式化描述系统状态和动作。 描述本身要紧凑，同时便于求解 ·如何在选定描述的基础上，有效的进行解的搜索 E 即使在受限条件下，规划问题的求解仍然是非常困难的，奢 求用经典规划技术来解决实际规划问题是不现实的 需要用一种通用的表达方式，compact表达状态和动作，并 且便于搜索求解，一般的思路是： ~用features来表达单个状态。状态为features特定值的集合 用operators来计算状态转移。operators为features之间的 转换关系 ·不需显示表达出所有状态，只给出初始状态，然后通 过operators计算出需要的状态 ，口+心。之，4色是分QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 经典规划 ▶ 经典规划只考虑确定的、静态的、有限的、完全可观察的、 离散环境的、目标受限和忽略时间的状态转移系统 ▶ 经典规划的主要问题包括： ▶ 如何在不显式枚举的情况下，形式化描述系统状态和动作。 描述本身要紧凑，同时便于求解 ▶ 如何在选定描述的基础上，有效的进行解的搜索 ▶ 即使在受限条件下，规划问题的求解仍然是非常困难的，奢 求用经典规划技术来解决实际规划问题是不现实的 ▶ 需要用一种通用的表达方式，compact 表达状态和动作，并 且便于搜索求解，一般的思路是： ▶ 用 features 来表达单个状态。状态为 features 特定值的集合 ▶ 用 operators 来计算状态转移。operators 为 features 之间的 转换关系 ▶ 不需显示表达出所有状态，只给出初始状态，然后通 过 operators 计算出需要的状态
经典规划的集合论表达(Set-Theoretic Representation) ·用有限的命题符号集()来表达状态转移系统： ~SC2,状态s为L的子集，命题的集合，表示在5上真的 命题 action是三元组(precond,effect,effect+) ·S的性质：对于任意状态s和可应用于s的行动a,集合 (s\effect (a))Ueffect(a)ES ·如果a可应用于5，则状态转移函数为 y(s,a)=(s\effect(a)Jeffect+(a),否则无定义 ·规划问题是在状态转移系统的基础上增加初始状态和目标状 态集 s0∈S ~gCL,目标状态集合为Sg={s∈S|g二s} e 规划是一个动作序列π=(a1,·,ak),如果g二y(s0,π)， 则规划π是此规划问题的一个解 ·并不是每一个状态转移系统都可以用集合论表达，但可以构 造一个与其等价的系统，而此系统可以用集合论表达
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 经典规划的集合论表达 (Set-Theoretic Representation) ▶ 用有限的命题符号集 (L) 来表达状态转移系统： ▶ S ⊆ 2 L，状态 s 为 L 的子集，命题的集合，表示在 s 上真的 命题 ▶ action 是三元组 ⟨precond, effect−, effect+⟩ ▶ S 的性质：对于任意状态 s 和可应用于 s 的行动 a，集合 (s \ effect−(a)) ∪ effect+(a) ∈ S ▶ 如果 a 可应用于 s，则状态转移函数为 γ(s, a) = (s \ effect−(a)) ∪ effect+(a)，否则无定义 ▶ 规划问题是在状态转移系统的基础上增加初始状态和目标状 态集 ▶ s0 ∈ S ▶ g ⊆ L，目标状态集合为 Sg = {s ∈ S | g ⊆ s} ▶ 规划是一个动作序列 π = ⟨a1, . . . , ak⟩，如果 g ⊆ γ(s0, π)， 则规划 π 是此规划问题的一个解 ▶ 并不是每一个状态转移系统都可以用集合论表达，但可以构 造一个与其等价的系统，而此系统可以用集合论表达
经典规划的经典表达(Classical Representation) ·经典表达是对集合论表达的推广，使用一阶逻辑符号，用公 式来表达状态集和行动，通过语义解释来确定具体的状态和 行动 用一阶逻辑语言（有限多谓词，变元，常元，没有函数符号）】 来描述系统。一个状态是一个grounded atoms集合。谓词又 分为状态谓词(fluent)和刚性关系(rigid relation),前者是状 态集的函数，后者不随状态变化而变化 ,规划操作是一个三元组o=(name(o),precond(o),effects(o), 其中： =name(o),操作的名字，形如n(X1,,x) precond(o)和effects(o)分别是o的前提和效果，都是文字 集。刚性关系不能出现在任何操作o的效果中。action ground instance of an operator 例如：move(r,lm)表示机器人r从位置I移动到位置m: precond:adjacent(I,m),at(r,-occupied(m) effect:at(r,m).occupied(m).occupied(1).at(r,) ,经典表达grounding后与集合论表达等价，不过grounding 结果可能指数增大 状态变量表达(State-Variable Representation)」 ·状态为向量值，动作为函数映射。经典表达与状态变量方法 在表达能力上是等价的 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 经典规划的经典表达 (Classical Representation) ▶ 经典表达是对集合论表达的推广，使用一阶逻辑符号，用公 式来表达状态集和行动，通过语义解释来确定具体的状态和 行动 ▶ 用一阶逻辑语言（有限多谓词，变元，常元，没有函数符号） 来描述系统。一个状态是一个 grounded atoms 集合。谓词又 分为状态谓词 (fluent) 和刚性关系 (rigid relation)，前者是状 态集的函数，后者不随状态变化而变化 ▶ 规划操作是一个三元组 o = (name(o), precond(o), effects(o))， 其中： ▶ name(o)，操作的名字，形如 n(x1, . . . , xk) ▶ precond(o) 和 effects(o) 分别是 o 的前提和效果，都是文字 集。刚性关系不能出现在任何操作 o 的效果中。action 是 ground instance of an operator ▶ 例如：move(r, l, m) 表示机器人 r 从位置 l 移动到位置 m： ▶ precond: adjacent(l, m), at(r, l), ¬occupied(m) ▶ effect: at(r, m), occupied(m), ¬occupied(l), ¬at(r, l) ▶ 经典表达 grounding 后与集合论表达等价，不过 grounding 结果可能指数增大 ▶ 状态变量表达 (State-Variable Representation): ▶ 状态为向量值，动作为函数映射。经典表达与状态变量方法 在表达能力上是等价的