Chap17 & Chap18：Temporal Represention, Acting, Planning张建的个人博客

Chap17 & Chap18：Temporal Represention, Acting, Planning

张建的个人博客
30分钟 ·
播放数2
·
评论数0

简报文档：时间表示、行动、规划与学习

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）、调度。

理解这些概念对于设计和实现能够有效管理时间和不确定性的自主系统至关重要。

小宇宙图标
在小宇宙打开