简报文档：时间表示、行动、规划与学习 1. 引言与背景 本简报基于Malik Ghallab、Dana Nau和Paolo Traverso所著《Acting, Planning, and Learning》的第17章和第18章，以及Dana S. Nau关于“时间表示、行动、规划”的大学讲义（其中包含Mark "mak" Roberts的贡献）。文档核心在于理解如何在人工智能系统中表示和处理时间，以及这些概念如何应用于规划和执行任务。 主要应用案例包括： * RAX/PS： “深空一号”飞船的规划/控制 (NASA Ames and JPL, 1999) * CASPER： 航天器规划/控制 (NASA JPL, ≈ 1999–2017) * T-ReX： 自主水下航行器（AUVs）的规划/控制 (Monterey Bay Aquarium Research Institute, ≈ 2005-2010) 这些案例表明，时间规划和控制技术在复杂、自主系统中的实际应用价值。 2. 时间模型与表示 传统上，我们使用“状态导向视图”，将时间看作是状态s0, s1, s2…的序列，瞬时动作将一个状态转换为下一个状态，且没有重叠动作。然而，本章节引入了“时间导向视图”，其中时间点是整数 (t = 1, 2, 3, …)，每个状态变量x都有一个时间线，表示“x在不同时间间隔内的值”。 时间模型的核心特征包括： * 状态变量和事件的约束： 反映预测的动作和事件。 * 动作的持续时间： 前置条件和效果可能在开始和结束之外的其他时间发生。 * 目标的时间约束： 相对或绝对。 * 未来预期发生的外生事件。 * 维护动作： 维持一个属性（例如，跟踪移动目标，保持门关闭）。 * 并发动作： 相互作用的效果，联合效果。 * 延迟提交： 在行动时实例化。 2.1 时间线（Timelines） 时间线是一个(T,C)对，其中 T = {时间断言}，C = {约束}。它“部分地预测了一个状态变量的演变”，并不一定指定每个时间点的值。 * 时间断言（Temporal Assertions）： 描述状态变量在特定时间段内的值或变化。例如：[t1, t2] loc(r1) = loc1（r1在t1到t2期间位于loc1），[t3, t4] loc(r1) : (l, loc2)（r1在t3到t4期间从l变化到loc2）。 * 约束（Constraints）： 定义时间点之间的关系或对象属性。例如：t1 < t2 < t3 < t4，l ≠ loc2。 一致性（Consistency）： 一个时间线(T,C)是一致的，如果它至少有一个满足所有约束的“地面实例（ground instance）”，并且在该实例中，“没有状态变量在同一时间具有多个值”。 安全性（Security）： 一个时间线(T,C)是安全的，如果它一致，并且“每个满足约束的地面实例都是一致的”。这类似于PSP（Partial Order Planning）中没有威胁的部分计划。可以通过添加“分离约束”（separation constraints）来使一致时间线安全，这类似于PSP中的解决器（resolvers）。 2.2 因果支持（Causal Support） 时间线中的每个断言都需要因果支持。这意味着：“信息表明 α 是先验支持的”，或者“另一个断言在时间 t1 产生 x = v1”。有三种方法可以修改时间线以添加因果支持： 1. 添加持久性断言： 例如，[t2,t3] loc(r1) = loc2。 2. 添加约束： 例如，t2 = t3, r = r1, l = loc2。 3. 添加一个动作： 该动作包含所需的因果断言，例如[t2,t3] loc(r1):(loc1,loc3)。 2.3 动作模式（Action Schemas）与任务方法（Tasks and Methods） * 动作模式（Action Schemas）： 也称为“原语（primitive）”，是一个三元组(head, T, C)，包含名称和参数，以及时间断言T和约束C的集合。每个动作模式都有起始时间ts和结束时间te。 * leave(r,d,w): 机器人r从装货码头d离开到相邻的路点w。 * take(k,c,r,d): 起重机k从机器人r那里取走容器c。 * 任务（Tasks）： 描述要完成的复合目标。例如：[ts ,te] move(r,d)（将机器人r移动到码头d）。 * 方法（Methods）： 将复合任务分解为子任务或动作序列。例如，m-move1方法可以将move(r,d)任务细化为leave、navigate和enter动作序列。 2.4 纪事（Chronicles） 纪事 ϕ = (A,S,T,C) 是一种更全面的表示形式，包括： * A: 带有时间限定的任务。 * S: 先验支持的断言（例如当前状态、未来预测事件）。 * T: 带有时间限定的断言。 * C: 约束。 纪事可以表示一个规划问题，也可以表示一个计划或部分计划。 3. 规划 规划问题被定义为“一个具有某些缺陷的纪事 ϕ0”。这些缺陷包括： * 没有因果支持的时间断言： 类似于PSP中的开放目标。 * 可能冲突的时间断言： 类似于PSP中的威胁。 * 未细化的任务： 类似于HTN规划中的任务。 **解决器（Resolvers）**用于解决这些缺陷，它们可以是持久性断言、约束、动作、任务或细化方法。 4. 约束的一致性与可控性 在规划过程中，检测和修剪不一致的搜索空间至关重要。 4.1 约束一致性 C包含两种约束：对象约束和时间约束。在假设它们相互独立的情况下，可以分别检查它们的一致性。 对象约束（Object Constraints）： * 这是一个NP-hard的约束满足问题（CSP）。 * 可以使用完整的（但可能是指数级的）CSP算法，或不完整但多项式时间的启发式方法（例如弧一致性、路径一致性）。 时间约束（Time Constraints）： * 用**简单时间网络（STN）**表示。STN是一个(V,E)对，V = {时间变量}，E = {表示约束的弧}。每条弧(ti,tj)用一个区间[a,b]标记，表示a ≤ tj − ti ≤ b。 * 操作： 交集（Intersection）、组合（Composition）。 * 一致性检查： 通过Path Consistency (PC)算法实现，该算法可以将网络最小化（缩小时间区间以排除非解决方案），并检测不一致的网络。PC算法的时间复杂度为O(n^3)。 * TemPlan通过将C中的时间约束写成STN，并使用PC算法检查其一致性，从而实现搜索空间的修剪。 4.2 可控性（Controllability） 当纪事需要被执行时，需要考虑可控性，即“选择起始时间来满足约束”。这里的挑战在于，某些时间点是可控的（例如动作的起始时间），而另一些是偶发的/不确定的（contingent，例如动作的结束时间，它们是满足持续时间约束的随机变量）。 * STNU（Simple Temporal Network with Uncertainty）： 一个四元组(V,Ṽ,E,Ẽ)，其中V是可控时间点，Ṽ是偶发时间点，E是可控约束，Ẽ是偶发约束。 三种可控性： * 强可控性（Strongly controllable）： 演员可以离线选择V的值，无论Ṽ的实际值如何，都能保证成功。 * 弱可控性（Weakly controllable）： 演员可以选择V的值，但需要提前知道Ṽ的值才能做出正确的选择。 * 动态可控性（Dynamically controllable）： 存在一种动态执行策略，演员可以在每个时间点根据已发生的事件来分配V中的变量值，以确保约束得到满足。 动态可控性可以通过博弈论模型来建模，演员（player）和环境（environment）之间进行零和博弈。TemPlan可以集成代码来保持STNU的动态可控性，并在检测到不可控情况时回溯。 4.3 部分可观察性（Partial Observability） 实际情况中，并非所有偶发事件都是可观察的。**POSTNU（Partially Observable STNU）**模型引入了“可见（visible）”和“隐藏（hidden）”事件的概念。一个POSTNU是动态可控的，如果“存在一种执行策略，可以在观察到过去可见点的情况下，选择未来的可控点来满足所有约束”。 5. 执行（Acting） 执行阶段主要涉及动作的细化和调度。 5.1 动作的非时间细化（Atemporal Refinement of Actions） TemPlan中的动作可能对应于复合任务。在RAE（Reactive Action Executive）中，使用细化方法将它们细化为命令。 * 优点： 简单的在线细化，可增强一些时间监控功能。 * 缺点： “不处理命令级别的时间要求”，例如同步两个必须并发行动的机器人。 5.2 调度（Dispatching） 调度过程是一种动态执行策略，它“控制何时开始每个动作”。给定一个具有可执行原语的动态可控计划，调度程序根据在线观察触发动作。 调度过程（Dispatch(V,Ṽ,E,Ẽ)）的主要步骤： 1. 初始化网络。 2. 循环直到所有可控时间点都被触发： * 更新当前时间now。 * 更新自上次迭代以来已触发的偶发时间点Ṽ。 * 更新“已启用（enabled）”的时间点（即当前时间在区间内，所有前置约束已发生，所有等待约束已满足或过期）。 * 触发所有enabled且now = ui（截止时间）的时间点。 * 任意选择并触发其他enabled时间点。 * 传播已触发时间点的值，更新未来时间点的[lj,uj]区间。 截止时间失败（Deadline Failures）： 如果无法按时开始某个动作，可以采取以下措施： * 停止延迟的动作，寻找新计划。 * 让延迟的动作完成；尝试通过解决STNU传播级别上的违规约束来修复计划（例如，通过延迟整个计划来适应延迟）。 * 让延迟的动作完成；尝试通过其他方式修复计划。 6. 总结 本简报回顾了时间规划和执行的关键概念： * 表示： 时间导向视图、时间线、时间断言、对象约束、时间约束、因果支持、动作模式、方法、纪事。 * 规划： 缺陷、解决器、TemPlan。 * 时间约束： 简单时间网络（STN）、路径一致性（PC）算法。 * 执行： 动态可控性、STNU、RAE和eRAE（扩展RAE）、调度。 理解这些概念对于设计和实现能够有效管理时间和不确定性的自主系统至关重要。

该文档介绍了RAE（Refinement Acting Engine）框架，它利用层次化操作模型使智能代理能在动态、不可预测的环境中执行任务。文档重点阐述了如何通过UPOM（不确定性感知操作模型规划）和蒙特卡洛推演将深思熟虑的规划集成到RAE中，以优化方法选择。此外，它还探讨了机器学习（Learnπ和LearnH）如何进一步增强这一规划过程，并展示了该组合系统在网络安全等复杂应用中的有效性。 层次化精化执行引擎 (RAE) * 定义与操作: RAE是一种执行引擎，通过层次化精化方法在动态、不可预测且部分可观测的环境中执行任务。 * 模型区别: 使用操作模型（包含执行指令和通常为层次化的结构）而非描述性模型，以适应上下文并对事件做出反应。 * 核心机制: 循环处理外部任务或事件，为每个任务选择方法实例，创建精化堆栈，并通过Progress程序推进执行，若失败则通过Retry机制尝试其他方法。 * 任务与方法: 任务是执行器要执行的活动，每个任务可对应一个或多个精化方法，这些方法是扩展的HTN（分层任务网络）方法，包含前置条件和执行体。 RAE的规划集成 * 规划需求: RAE在选择方法实例时需要规划，以避免代价高昂或不可恢复的失败，尤其是在存在多种可选方法时。 * SeRPE的挑战: 早期尝试SeRPE（顺序精化规划引擎）通过模拟RAE并使用经典动作模型进行规划，但面临实现困难（需要回溯代码执行）和经典动作模型局限性（如无法预测感知操作的效果）的问题。 * UPOM方法: 提出UPOM（不确定性感知操作模型规划）作为解决方案，它通过蒙特卡洛推演在模拟环境中运行RAE，评估不同方法实例的预期效用，并利用UCT（Upper Confidence Bound for Trees）算法指导选择。 RAE与UPOM的协同作用 * 紧密集成: RAE在需要选择方法实例时，会调用UPOM进行规划，从而实现行动与规划的紧密耦合。 * 对比优势: 相比于其他预见性方法（如Run-Lazy-Lookahead），RAE+UPOM能更好地处理执行过程中状态的意外变化，因为它能根据新状态重新进行规划选择，提高系统的适应性。 * 开源实现: RAE+UPOM的Python实现已开源，供研究和应用。 规划与行动中的学习 * 学习必要性: 考虑到在线规划的时间限制，学习算法可以优化RAE的决策过程，特别是在时间不允许进行全面搜索时。 * Learnπ: 通过训练分类器学习一个选择函数，当时间不足以执行UPOM时，根据当前任务和上下文直接选择最佳方法。 * LearnH: 学习一个启发式函数来指导UPOM的搜索，用于估计搜索树叶节点的预期效用，从而在时间只允许部分搜索时提高效率。 评估与实际应用 * 实验验证: 实验结果表明，RAE结合UPOM或学习算法能显著提高效率和成功率，证明规划和学习对RAE性能的提升作用。 * 网络安全应用: 在软件定义网络（SDN）中的网络攻击自动恢复领域得到原型应用，通过RAE+UPOM自动化恢复程序，在效率、重试率、成功率和弹性方面均优于人工专家。

本资料主要探讨在非确定性模型下进行行动和规划的方法。它首先定义了非确定性规划域，引入了策略（policies）的概念及其不同类型（如不安全、安全、无环和循环策略），并详细介绍了寻找这些策略的各种算法。最后，文章讨论了在线规划方法以应对模型近似和大规模问题带来的挑战。 非确定性模型与规划域 * 非确定性模型定义: 非确定性规划域由三元组 (S, A, γ) 组成，其中 S 是状态集，A 是动作集，γ: S × A → 2^S 表示动作在给定状态下可能导致的所有下一个状态。 * 挑战: 非确定性动作的可能结果可能呈组合爆炸式增长，使得传统表示方法效率低下。 * 示例: 以“港口管理”为例，描述了物品从船上卸载到港口内移动的简化过程，展示了 park 动作如何导致多个非确定性结果（parking1, parking2, transit1）。 策略及其类型 * 策略定义: 策略 π 是一个函数，将状态映射到可执行的动作 (π : S′ → A)，其中 S′ 是 S 的子集。 * 策略执行: ActPolicy(π) 算法描述了如何根据策略在当前状态下执行动作并观察新状态。 * 解决方案类型:解决方案 (Solution): 只要至少一个执行路径能到达目标状态即可。 安全策略 (Safe Policy): 保证从策略作用域内的任何状态出发，至少有一个执行路径能到达目标状态。 无环安全策略 (Acyclic Safe Policy): 策略图是无环的，且所有叶节点都是目标状态，保证最终到达目标。 循环安全策略 (Cyclic Safe Policy): 策略图可以有循环，但仍保证每个“公平”执行都能到达目标状态。 寻找解决方案的算法 * Find-Solution (查找不安全解决方案): 通过前向搜索找到一个可行的动作序列，不考虑所有可能的结果。 * Find-Acyclic-Solution (查找无环解决方案): 在查找过程中检查并避免循环，以确保找到的策略是无环的。 * Find-Safe-Solution (查找安全解决方案): 类似于 Find-Acyclic-Solution，但需检查并避免“不安全循环”，即无法逃脱的循环。 * Guided-Find-Safe-Solution (引导式查找安全解决方案): 迭代地寻找（可能不安全的）解决方案，并针对未达到目标的叶节点或死胡同进行修正，通过修改动作适用性来解决问题。 * Find-Safe-Solution-by-Determinization (通过确定化查找安全解决方案): 将非确定性动作转换为多个确定性动作（即“确定化”），然后使用经典规划器在确定化域中寻找解决方案，并将其转换回策略。 在线规划方法 * 动机: 规划模型通常是近似的，且非确定性会使规划时间和策略大小呈指数级增长，因此需要在线方法。 * Lookahead-Partial-Plan: Run-Lazy-Lookahead 的变体，执行部分规划，然后根据需要重新规划。 * FS-Replan: Lookahead-Partial-Plan 的特例，调用经典规划器在确定化域中生成计划，执行后若有需要则再次调用。 * Min-Max LRTA*: 在“安全可探索域”中（即从任何状态都能到达目标），通过选择具有最优最坏情况成本的动作并更新启发式函数，保证最终到达目标。

这份资料深入探讨了强化学习（RL）的基本概念，包括基于值的RL和Q学习，强调了智能体通过试错和奖励函数进行学习。它进一步介绍了参数化学习，如线性回归和神经网络（包括McCulloch-Pitts单元、前馈网络和反向传播），旨在解决传统Q学习在泛化和存储方面的局限性，并提出了参数化Q学习的理念。核心在于通过学习参数化的函数来优化智能体的行为。 强化学习概述 * 智能体通过与环境直接交互，通过试错（trial and error）来提高性能。 * 需要一个奖励函数 r(s,a,s′) 来衡量从状态 s 经动作 a 到状态 s′ 的收益。 * 智能体试图记住哪些状态/动作带来了好的或坏的奖励，并最大化其行动的长期感知收益。 基于值的强化学习与Q学习 * 通过试错来估计 V*（最优值函数）或 Q*（最优动作-值函数）。 * 示例通过帕埃利亚（paella）食谱的客人评分来展示奖励计算和平均值更新。 * 使用时间差分（Temporal Difference）更新规则 Q(a) ← Q(a) + α ( r(a) – Q(a))，其中 α 是学习率。 * Q学习适用于我们不知道 γ（状态转移函数）的马尔可夫决策过程（MDP），通过修改Bellman更新规则来最大化奖励。 * Q学习面临需要存储庞大的 Q(s,a) 表和泛化能力不足的问题。 参数化学习与线性回归 * 通过调整参数 θ 来使参数化函数 fθ(x) 逼近 y 值。 * 以线性回归 fθ(x) = θ0 + θ1x 为例，通过最小化经验损失函数 Loss = (1/|D|) Σ (fθ(x) – y)^2 进行学习。 * 通过计算损失函数对参数的偏导数来找到最小值。 * 梯度下降法是常用的优化方法，分为批量（Batch）和随机（Stochastic）两种模式。 参数化Q学习 * 动机是解决传统Q学习中 Q(s,a) 表存储量大和难以泛化到新情况的问题。 * 核心思想是开发一个参数化的公式 Qθ(s,a) 来近似 Q(s,a)。 * 通过梯度下降算法调整参数 θ，使其能够拟合观察到的奖励。 神经网络基础与学习 * McCulloch-Pitts单元： 一个简单的数学模型，其输出 aj 取决于输入 ai 的加权和 in_j = Σ wi,j ai 经过激活函数 g 的结果 g(in_j)。 * 多层前馈网络： 由单元组成的非循环网络，通常分层组织，连接从左到右。 * 表达能力： 具有足够单元的两层网络可以近似所有连续函数，三层网络可以近似所有函数。 * 反向传播学习： 通过梯度下降调整网络的权重，以最小化损失函数，分为批量和在线两种更新方式。 * 激活函数： 包括逻辑（Sigmoid）、Softplus和ReLU（修正线性单元）；Sigmoid在深度网络中存在梯度消失问题，ReLU和Softplus被广泛用作替代。

本资料深入探讨了在不确定环境下进行行动和规划的核心概念与算法。首先，它介绍了概率域模型、策略定义以及安全/不安全解决方案等基础理论，并利用贝尔曼最优性原理来量化期望成本。随后，资料详细阐述了策略迭代、值迭代等经典算法，以及AO*、LAO*和蒙特卡洛树搜索（UCT）等更高级的规划与执行方法，这些方法旨在高效地在随机环境中寻找最优策略。 概率模型与策略 * 核心概念: 定义了状态（S）、动作（A）、状态转移函数（γ）、转移概率（Pr）和成本（cost），共同构成概率域模型 Σ。 * 策略定义: 策略（π）是一个将状态映射到动作的函数，指导智能体在不确定环境中采取行动。 * 历史与可达性: 历史是策略在特定初始状态下生成的状态序列；可达性图谱则描绘了从起始状态可达的所有可能状态集合。 解决方案与最优性 * 问题类型: 主要关注随机最短路径（SSP）问题，即在存在不确定性的情况下寻找从起始状态到目标状态的最低期望成本路径。 * 解决方案类型: 区分了安全解决方案（保证以1的概率达到目标）和不安全解决方案（有一定概率达到目标但非必然）。 * 期望成本与贝尔曼方程: 使用 Vπ(s) 表示从状态 s 开始遵循策略 π 到目标的期望成本，并通过贝尔曼最优性原理（V*(s)）来定义并计算最优策略的期望成本。

分层任务网络（HTN）规划是一种通过将复杂任务分解为更小、更易管理子任务来寻找解决方案的方法。本资料详细介绍了HTN的表示、全序（TOHTN）和偏序（POHTN）规划的原理、相关算法及其在Pyhop等工具中的实现。此外，它还探讨了HTN模型在非确定性、动态环境中的应用，以及如何通过不同的策略处理意外事件和实现错误恢复。 分层任务网络(HTN)规划基础 * 核心理念: HTN规划通过将复杂活动分解为一系列子任务或“食谱”，模仿人类解决问题的方式，以应对大量组合的可能性。 * 关键组成部分: 包括状态变量规划域、任务（原始任务、复合任务、目标任务）和定义如何执行任务的HTN方法。 * 全序HTN (TOHTN): 任务严格按照顺序执行，其方法定义包含头部、非原始任务、前置条件和子任务列表。 * 偏序HTN (POHTN): 任务可以部分有序，通过任务网络（包含任务节点集合和偏序关系）表示，TOHTN是POHTN的一种特殊情况。 HTN规划算法与实现 * 规划过程: 递归地应用HTN方法将非原始任务分解为子任务，直到所有任务都成为可直接执行的原始任务（对应具体动作）。 * 复杂性与表达能力: HTN规划是图灵完备的，TOHTN规划可判定但比经典规划更具表达力，某些子集可转换为经典规划或命题逻辑。 * 主要实现工具:Pyhop: 一个简单的Python HTN规划器，实现了深度优先的全序HTN向前搜索，不包含目标任务。 GTPyhop: Pyhop的扩展，支持复合任务和目标任务（如单目标和多目标），并提供了更灵活的状态和目标表示方式。 HTN在实际行动中的应用 * 动态环境挑战: 执行者的环境可能非确定性或动态，存在外部事件和意外的动作结果，导致无法回溯到之前的状态。 * HTN模型的价值: 为执行者提供操作模型，用于执行标准操作程序、处理复杂任务、避免不良结果以及从意外事件中恢复。 * 响应式HTN执行器: 类似于TO-HTN-Forward算法，但直接执行每个动作，并在方法失败时尝试其他可选方法。 * 重规划策略:Run-HLookahead: 在执行每个动作之前即时调用HTN规划器进行重规划，适用于频繁发生意外的情况。 Run-Lazy-HLookahead: 仅当当前计划用尽或动作执行失败时才进行重规划，减少规划频率。 HTN规划中的错误恢复机制 * 恢复目标: 在意外事件发生后，确保恢复过程仍能满足规划中隐含的轨迹要求（如安全规定、对其他代理的承诺或公司标准操作程序）。 * 三种恢复方法:修改TO-HTN-Act以调用HTN规划器: 在执行出错时，让规划器选择不同的方法来继续任务。 遍历解决方案树: HTN规划器返回一个完整的解决方案树，执行者遍历该树，并在执行错误时引导规划器选择不同的方法分支。 修改规划域并重新调用规划器: 在执行路径偏离预期时，通过修改初始状态和/或规划域（以反映已执行的动作和新的状态），重新调用HTN规划器来生成新的计划。

本文深入探讨了确定性模型中的规划问题，将其视为搜索过程。它详细介绍了前向状态空间搜索、各种确定性搜索算法（如BFS、DFS、A*），以及启发式函数的设计与应用。此外，文章还涵盖了后向搜索的原理，并着重阐述了如何将规划问题转化为约束满足问题的方案空间规划（PSP），包括其核心概念、缺陷及解决策略。 前向状态空间搜索 * 搜索树术语: 定义了规划搜索中关键概念，如节点（包含状态和计划）、路径、深度和分支因子，以及扩展节点的流程。 * 确定性算法框架: 详细介绍了通用确定性前向搜索算法（Forward-Search-Det），通过管理“前沿”和“已扩展”集合来选择和剪枝节点。 * 主流搜索算法: 阐述了广度优先搜索 (BFS)、深度优先搜索 (DFS)、统一代价搜索 (Uniform-Cost Search)、贪婪最佳优先搜索 (Greedy Best-First Search) 和 A* 搜索的节点选择、剪枝策略及其特性（如完备性、最优性）。 * 启发式理论: 引入了启发式函数的“可采纳性”和“支配性”概念，解释了它们如何影响 A* 算法寻找最优解的能力。 启发式函数 * 核心作用: 启发式函数用于估计从当前状态到达目标状态的最小成本。 * 创建方法: 一种主要方法是通过“松弛”原始规划问题（即弱化约束）来获得一个更容易解决的近似问题，并从其最优解中导出启发式。 * 删除松弛启发式: 介绍了允许状态变量同时拥有多个值的松弛模型，如最优松弛解启发式 h+（可采纳）和快速前向启发式 hFF（非可采纳但有效）。 * 地标启发式: 识别在任何解决方案中都必须被满足的关键公式（地标），通过将其分解为子问题或利用松弛规划图 (RPG) 来计算。 后向搜索 * 基本原理: 后向搜索从目标状态逆向工作，通过选择相关动作并应用逆状态转移函数来推导出前一个状态应满足的条件。 * 动作相关性: 定义了动作被视为对给定目标“相关”的条件，即它必须使目标中的某个原子为真且不使任何目标原子为假。 * 算法与特性: 介绍了非确定性后向搜索算法，并通过循环检查机制确保其健全性和完备性。 * 提升式搜索: 讨论了通过保持变量未实例化（提升）来有效降低搜索分支因子的策略。 方案空间规划 (PSP) * 规划范式: 将规划问题建模为约束满足问题，旨在生成部分有序的计划，以提供更大的执行灵活性。 * 核心概念: 定义了部分有序计划、因果链接（表示动作间的前后条件依赖）以及部分计划中的“缺陷”（开放目标和威胁）。 * 缺陷解决: 解释了如何解决开放目标（通过添加新动作或现有动作来满足前置条件）和威胁（通过添加优先级或不等式约束来消除冲突）。 * 启发式策略: 探讨了在 PSP 算法中选择缺陷（如“最少替代优先”FAF）和选择解析器（如“最少约束解析器”LCR、“避免新动作”ANA）的启发式方法。

这份资料详细阐述了确定性规划的基础理论与实际应用，首先定义了状态转移系统和行为、规划、学习的核心概念，接着深入探讨了状态变量表示法和经典表示法，并介绍了规划领域定义语言（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内。这些是理论最坏情况结果，平均情况通常远低于此。