STRIPS 表达式

STRIPS 表达式一种以行动为中心的表示，它对于每个动作（action）来说，都需要指定这个动作所获得的效果（effect）。一个这样的表示就是STRIPS representation。“斯坦福研究院问题解决器”(Stanford Research Institute Problem Solver)的缩写，

首先，将描述世界的特征划分为原始的primitive和派生的primitive特征。一定数量的子句用来确定从任何给定状态的原始primitive特征值得出的派生derived特征的值。STRIPS表示基于先前状态和之前agent所采取的操作，来确定一个状态下的原始特征值，

STRIPS representation是基于大多数事物不受单个动作影响的观点设计的。对于每一个动作，当动作可行时，STRIPS models中原始primitive特征值会被动作所影响。动作的效果依赖于STRIPS assumption: 动作描述中所提到的所有原始特征保持不变。

一个动作的STRIPS representation包括：

• 前置条件precondition，它是一组值的赋值，操作发生时，它们必须是True的。
• 效果effect，它是一组结果赋值给那些由于动作而改变的原始特征。

原始特征V在动作act行为后具有v值，如果V= v在行为列表中，或者在act的效果列表中没有提到V，则V在动作act前立即具有v值。非原始的特性可以从原始特性的值中派生出来。

当变量是布尔值时，有时将效果划分为一个删除列表delete list是很有用的，其中包括那些可能导致false的变量，以及一个add list添加列表，其中包含导致True的变量。

例:Rob拿起咖啡(puc)的动作如下，STRIPS representation:

也就是说，机器人必须在咖啡店cs里，并且没有咖啡。在行动之后，rhc持有((i.e., RHC=true),并且所有其他特征值都不受此操作的影响。

送咖啡(dc)的作用可以被定义为：

基于特征的表示法STRIPS representation更强大，因为它可以表示条带中的任何可表示的东西。它可以更详细，因为它需要显式的框架公理，这在STRIPS representation中是隐式的。

可以将一组操作的STRIPS representation形式转换为基于特征的表示形式。如果动作行为的效果列表是[e1,...,ek]，STRIPS representation法等同于因果规则。act导致 ei‘的效果。

于每个ei，通过动作和框架规则实现。

对于每个条件c，它在效果列表中不包含变量。表示中的每个动作的前提是相同的。

条件效应conditional effect是一种取决于其他特征值的动作的效果。基于特征的表示可以指定条件效果，而STRIPS representation不能直接表示它们。

基于特征的表示形式如下：

 Rob's的位置取决于它之前的位置和它移动的位置。RLoc'是指定结果状态的位置。下面的规则说明了Rob's在咖啡店的条件:

前两个规则是因果规则，最后一个规则是框架规则。

为了在STRIPS representation法中表示这一点，我们构造了在最初的情况下不同的多个动作。例如，mc_cs(从咖啡店顺时针方向移动)有一个precondition [RLoc=cs]和effect [RLoc=off]。

举例：

一只猴子在实验室的A位置，在c位置有一个盒子，猴子想要在B位置悬挂在天花板上的香蕉，但是它需要移动盒子并爬上它才能够到它们。

Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
Goal state:    Have(bananas)

Initial state: At(A), Level(low), BoxAt(C), BananasAt(B)
Goal state:    Have(bananas)
Actions:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

来源：Artificial Intelligence，http://artint.info/html/ArtInt_204.html

发展历史

20世纪60年代到20世纪80年代，早期的规划工作植根于最优控制理论的领域，它提供了强大的工具来表征和和产生最佳轨迹时，这是高速运动所需的必要条件，由Pontryagin’s maximum principle，导致最优控制会有一个two-point boundary value problem，并寻找最优控制算法，产生最佳的轨迹。

经典的规划算法

• 向前链式空间状态搜索，可能通过启发式算法强化
• 向后链式搜索backward chaining search, 使用状态约束进行强化(see STRIPS, graphplan)
• 偏序规划partial-order planning

1971年，斯坦福研究所 SRI International的Richard Fikes和Nils Nilsson开发了一种新的方法来应用定理证明来解决问题。该模型试图在一个世界模型的空间中找到一个操作序列，将初始的世界模型转化为一个目标状态存在的模型。它将世界建模为一组一阶谓词公式，并设计用于与包含大量公式的模型一起工作。这也是所谓的STRIPS。

在STRIPS，roblem solver的任务是找到一个算子序列，将给定的初始问题转化为满足目标条件的初始问题。操作是构建解决方案的基本元素。每个操作符对应一个动作例程，其执行导致代理执行某些操作。定理证明和搜索的过程通过一个世界模型的空间被分开。

Graphplan是Avrim Blum和Merrick Furst在1995年开发的自动规划算法。Graphplan将一个规划问题作为输入，在STRIPS 表示，如果可能的话，就会产生一个达到目标状态的操作序列。

graphplan的名称是一个新的planning graph，从而减少了从对状态空间图的直接探索中找到解决方案所需的搜索量。

降低到别的问题 Reduction to other problems

• 降低到命题可满足性问题(satplan)，1992年，H. A. Kautz and B. Selman提出的Satplan(更被称为“可满足性计划”)是一种自动规划的方法。它将规划问题实例转化为布尔可满足性问题的实例，然后用一种建立可满足性的方法(如DPLL算法或WalkSAT)来解决。
• 降低到模型检查Model checking,两者本质上都是遍历状态空间的问题，而经典的规划问题可以堪为模型检查问题的子问题。为检验硬件和软件设计的模型，开发了一种重要的模型检查方法，该模型由时序逻辑公式给出。

时间规划 Temporal planning

时间规划可以用与经典规划相似的方法来解决。主要的区别是，由于可能有几个临时重叠的行动，同时持续地同时进行，因此，状态的定义必须包括关于当前绝对时间的信息，以及每一个行动的执行情况。此外，在合理或实时的规划中，状态空间可能是无限的，不像古典规划或整数时间的规划。时间规划与调度问题密切相关。时间规划也可以是timed automata。

在时序逻辑规范的开创性工作是由Amir Pnueli完成的，获得了1996图灵奖，‘将时序逻辑引入计算机科学的开创性工作”。模型检查开始创业的E. M. Clarke和 E. A. Emerson和J. P. Queille和J. Sifakis。Clarke, Emerson, and Sifakis 共同获得了2007图灵奖，应为在模型检验的开创性工作。

概率规划

在状态空间足够小的情况下，概率规划可以用迭代方法(如值迭代和策略迭代)来解决。在部分可观察性的情况下，概率规划同样用迭代方法解决，但使用的是信任空间而不是状态定义的值函数的表示。MDPs（Markov decision process）至少早在20世纪50年代就已经为人所知(cf. Bellman 1957)。关于马尔可夫决策过程的一个核心研究机构是 Ronald A. Howard在1960年出版的书，Dynamic Programming and Markov Processes动态规划和马尔可夫过程。它们被广泛应用于学科领域，包括机器人、自动控制、经济学和制造业。（e.g. Markov decision process 和Partially observable Markov decision process）

基于优先级/偏好的规划

在基于优先级的规划中，目标不仅是生成规划，而且还满足用户指定的首选项。不同于更常见的基于奖励的规划，例如与MDPs对应的，首选项不一定具有精确的数值。基于偏好的规划软件的例子包括PPLAN和HTNPlan-P(基于优先级的HTN规划)。

规划系统的应用

 Hubble Space Telescope（哈勃太空望远镜）短期的系统SPSS，长期的规划系统Spike。哈勃太空望远镜(HST)是NASA/ESA资助的项目，于1990年发射进入轨道。太空望远镜科学研究所(STScI)负责管理科学项目的征集/选择、计划和日程安排，以及对HST的数据存档。

https://en.wikipedia.org/wiki/Automated_planning_and_scheduling#Classical_planning

主要事件

发展分析

瓶颈

尽管已经有超过三分之一世纪的历史，这项研究仍处于游戏AI的最前沿。然而，大多数游戏不会使用(或要求)完全都用STRIPS实现；他们会保留planner并抛弃定理证明。它没有足够的效率来呈现一个一阶谓词的列表。

未来发展方向

相反，开发人员如果使用一个简单的C/C++数据结构或位域来代表整个世界。然后，将世界上不同的状态存储起来并与操作符进行操作就变得更加高效了。

Contributor: Ruiying Cai