13
0这份资料详细阐述了确定性规划的基础理论与实际应用，首先定义了状态转移系统和行为、规划、学习的核心概念，接着深入探讨了状态变量表示法和经典表示法，并介绍了规划领域定义语言（PDDL）。此外，资料还分析了在不确定环境中执行计划时可能遇到的挑战，并提出了包括前瞻、延迟前瞻和计划修复在内的多种应对策略，最后简要提及了规划问题的计算复杂性。
确定性规划基础
- 经典规划假设: 经典AI规划通常假定一个有限、静态、单一行动者、无并发、无不确定性、完全可观察且行动成本单一的世界。
- 状态转移系统: 由有限状态集 (S)、有限行动集 (A)、预测函数 (γ: S×A → S) 和可选的成本函数组成，用于描述行动如何改变状态。
- 计划与解决方案: 计划是行动序列，其适用性通过连续的状态转移定义；解决方案可以是最小的、最短的或最优的，取决于目标。
状态变量表示法
- 对象与属性: 环境中的对象具有两种属性：刚性属性（在所有状态中保持不变，如相邻关系）和变量属性（在不同状态中可能改变，如位置），后者用状态变量表示。
- 状态表示: 每个状态被表示为一个函数，将状态变量映射到其对应的值，或等效地表示为一组基正文字（原子）。
- 行动模式 (Action Schemas): 参数化的行动集，包含头部（名称和参数）、前置条件（行动可执行的条件）和效果（行动导致的状态改变），以及可选的成本。
实际行动策略
- 行动中遇到的问题: 实际环境中可能出现执行失败、传感器错误、信息不准确或不完整、以及外部事件导致行动不再适用或不再必要等问题。
- 前瞻式行动: 通过反复调用规划器（Lookahead），执行第一个行动后立即重新规划，适用于不可预测的环境。
- 延迟前瞻与计划修复: 延迟前瞻在计划执行过程中尽可能不重新规划，仅在必要时（如模拟失败）才重新规划；计划修复则是在计划偏离预期时，尝试修改现有计划而非生成全新计划。
- 前瞻方法: 包括完整规划、回溯地平线搜索、采样（如蒙特卡洛模拟）和子目标分解，以适应不同实时性要求。
经典表示法与PDDL
- 经典表示法: 将状态表示为一组基原子（逻辑谓词），不区分刚性与变量属性，所有属性均在当前状态中。
- 与状态变量表示法的关系: 两种表示法在表达能力上等价，可在线性时间和空间内相互转换，但各有侧重（前者更偏逻辑，后者更偏工程）。
- 规划领域定义语言 (PDDL): 定义规划领域和问题的标准语言，有多个版本和扩展，包括经典规划的子集，支持无类型和有类型参数。
计算复杂性
- 规划问题类型: 关注“计划存在性”（是否存在解决方案）和“计划长度”（是否存在长度≤k的解决方案）等决策问题。
- 复杂性结果: 对于状态变量表示，计划存在性问题是EXPSPACE-完全的，计划长度问题是NEXPTIME-完全的；若规划域Σ固定，则两者均在PSPACE内。这些是理论最坏情况结果，平均情况通常远低于此。
这份资料详细阐述了确定性规划的基础理论与实际应用，首先定义了状态转移系统和行为、规划、学习的核心概念，接着深入探讨了状态变量表示法和经典表示法，并介绍了规划领域定义语言（PDDL）。此外，资料还分析了在不确定环境中执行计划时可能遇到的挑战，并提出了包括前瞻、延迟前瞻和计划修复在内的多种应对策略，最后简要提及了规划问题的计算复杂性。
确定性规划基础
- 经典规划假设: 经典AI规划通常假定一个有限、静态、单一行动者、无并发、无不确定性、完全可观察且行动成本单一的世界。
- 状态转移系统: 由有限状态集 (S)、有限行动集 (A)、预测函数 (γ: S×A → S) 和可选的成本函数组成，用于描述行动如何改变状态。
- 计划与解决方案: 计划是行动序列，其适用性通过连续的状态转移定义；解决方案可以是最小的、最短的或最优的，取决于目标。
状态变量表示法
- 对象与属性: 环境中的对象具有两种属性：刚性属性（在所有状态中保持不变，如相邻关系）和变量属性（在不同状态中可能改变，如位置），后者用状态变量表示。
- 状态表示: 每个状态被表示为一个函数，将状态变量映射到其对应的值，或等效地表示为一组基正文字（原子）。
- 行动模式 (Action Schemas): 参数化的行动集，包含头部（名称和参数）、前置条件（行动可执行的条件）和效果（行动导致的状态改变），以及可选的成本。
实际行动策略
- 行动中遇到的问题: 实际环境中可能出现执行失败、传感器错误、信息不准确或不完整、以及外部事件导致行动不再适用或不再必要等问题。
- 前瞻式行动: 通过反复调用规划器（Lookahead），执行第一个行动后立即重新规划，适用于不可预测的环境。
- 延迟前瞻与计划修复: 延迟前瞻在计划执行过程中尽可能不重新规划，仅在必要时（如模拟失败）才重新规划；计划修复则是在计划偏离预期时，尝试修改现有计划而非生成全新计划。
- 前瞻方法: 包括完整规划、回溯地平线搜索、采样（如蒙特卡洛模拟）和子目标分解，以适应不同实时性要求。
经典表示法与PDDL
- 经典表示法: 将状态表示为一组基原子（逻辑谓词），不区分刚性与变量属性，所有属性均在当前状态中。
- 与状态变量表示法的关系: 两种表示法在表达能力上等价，可在线性时间和空间内相互转换，但各有侧重（前者更偏逻辑，后者更偏工程）。
- 规划领域定义语言 (PDDL): 定义规划领域和问题的标准语言，有多个版本和扩展，包括经典规划的子集，支持无类型和有类型参数。
计算复杂性
- 规划问题类型: 关注“计划存在性”（是否存在解决方案）和“计划长度”（是否存在长度≤k的解决方案）等决策问题。
- 复杂性结果: 对于状态变量表示，计划存在性问题是EXPSPACE-完全的，计划长度问题是NEXPTIME-完全的；若规划域Σ固定，则两者均在PSPACE内。这些是理论最坏情况结果，平均情况通常远低于此。
