有限状态控制器学习与FactForge数据服务：结合规划与学习应对复杂任务

### 有限状态控制器学习与FactForge数据服务：结合规划与学习应对复杂任务 #### 有限状态控制器的生成与学习 在解决复杂任务时，结合自动规划和强化学习技术是一种有效的方法。这里介绍一种用于指定控制器的方法，它分为生成和学习两个阶段。 ##### 分层抽象机器（HAM）基础 分层抽象机器（HAM）在任何给定时间，要么指定要执行的动作，要么处于选择状态。当处于选择状态时，下一个动作由底层的马尔可夫决策过程（MDP）决定，并且仅在这些状态下进行学习。机器H和MDP M的组合H ◦M的构建过程如下： 1. 计算H和M状态空间的笛卡尔积。 2. 通过从机器或MDP中选取转换来定义新的MDP。如果状态是动作状态，则从H借用动作；如果是选择状态，则从M借用动作。只有选择状态有多个可用动作。 3. 如果转换是动作，则奖励取自MDP；否则为零。 这个过程得到的仍然是一个MDP，并且已证明不需要存储整个状态空间，因为总是存在一个半马尔可夫决策过程（SMDP），其最优策略与H ◦M相同，且该SMDP仅包含机器状态q为选择状态的⟨q, s⟩状态。 ##### 控制器生成阶段 此阶段的主要步骤如下： 1. 从编码为非确定性规划域的环境的形式化表示开始。 2. 将该域作为输入提供给TLV系统，以计算一组保证实现目标的策略。目标是针对给定域D构建一组强解决方案策略。 3. 使用一种改进的强规划算法来计算最小成本的强解决方案。以下是该算法的伪代码： ```plaintext Algorithm 1. Computes minimal-cost strong solutions Input: a planning domain problem Prob = ⟨D, G⟩ Output: a set of minimal strong solutions Let Z := G, Z′ := ∅, TG := ∅; While(s0 /∈Z ∧Z ̸= Z′) do Let N := {⟨s, a⟩ ∈ (S \ Z) × A | T (s, a) ̸= ∅∧T (s, a) ⊆ Z}; Let TG := TG ∪{⟨s, a, s′⟩∈S × A × S | ⟨s, a⟩∈N ∧s′ ∈T (s, a)}; Let Z′ := Z; Let Z := {s ∈S | ∃a.⟨s, a⟩∈N} ∪Z; End if(s0 ∈Z) return TG; else return ∅; ``` 该算法迭代计算所有能实现目标状态的策略的状态集合Z。在第i次迭代结束时，Z包含了在最多i步（取决于非确定性动作的结果）内可以实现目标状态的状态集合。关系N将状态s与那些后继状态都属于Z的动作关联起来，关系TG则补充了执行动作时发生的转换信息。 虽然这里主要关注强解决方案，但原则上也可以考虑较弱的解决方案概念，如弱解决方案（保证至少有达到目标的可能性）或强循环解决方案（在动作效果的公平性假设下保证实现目标），甚至可以混合使用这些概念。需要注意的是，最短的解决方案不一定是最优的，因为实际成本取决于环境，通常难以建模。因此，虽然规划器可能认为扩展最小成本（以动作数量衡量）的策略质量较低，但在实践中它们可能会有更好的性能，这将在后续的学习阶段进行探索。 ##### 控制器学习阶段 上一阶段生成的控制器可以转换为一级HAM，具体步骤如下： 1. 控制器生成器的输出是一个图G = ⟨S, TG⟩，其中S是原始域D的状态集合。当域处于状态s时，代理可以确定任何满足TG(s, a, s′)的动作a都是向目标靠近的有效选择。 2. 将G视为一个接受器，将转换上的动作作为其符号，通过最小化自动机的方法得到HAM H。这个最小化过程会去除环境状态信息，并且自动机状态与域状态之间的一一对应关系在新表示中不再保留。 在学习过程中，这个状态机与观察结果（域的MDP状态）结合使用。MDP的动态不需要预先知道，因为在选择点的学习可以是无模型的。如果状态空间是完全可观察的，系统就属于半马尔可夫决策过程的范畴，相关理论保证了收敛性。 以一个简单的规划问题为例，Bar - bot需要为客户提供咖啡或茶。可用的动作包括goto(location)、pickup(object)、pour、call - barman和serve。其中pour是一个非确定性动作，可能成功也可能失败。如果失败，Bar - bot可以通过呼叫酒保来恢复。客户对咖啡和茶有偏好，但代理并不知道。纯学习方法会随机尝试动作，以发现Bar - bot在拿起咖啡之前需要去冰箱，或者在能够倒咖啡之前需要先拿起咖啡。将模型和用线性时态逻辑描述的目标输入到规划器中，TLV会生成一个图，该图代表了两种不同的强计划（能够从非确定性中恢复）：一种是提供咖啡，另一种是提供茶。在这个阶段，图的状态与环境状态之间仍然存在一一对应关系。但当图被最小化后，这种对应关系以及某个状态下某个动作是否实际允许的信息都会丢失。最小化后的自动机就是自动生成的HAM，在这个自动机中，状态3同时有call - barman和serve两个动作可用，但call - barman只有在之前的pour动作失