斯坦福研究院问题解决者

在人工智能领域，斯坦福研究所的问题解决机是由 Richard Fikes 和 Nils Nilsson 于1971年在SRI国际开发的自动规划机。STRIPS这个名字后来被用来指这个planer输入的正式语言。这种语言是大多数用于表达自动化规划问题实例；而这个词条主要介绍 Stanford Research Institute Problem Solver。

STRIPS是植入与机器中，它的挑战是建立一个控制机器人Flakey(照片)的系统:

1. 执行任务，比如移动对象或在有多个房间的环境中导航。
2. 在非常有限的硬件上实时有效地解决问题。

多年来，这些领域的研究已经取得了很大进展，特别是在低水平传感器和执行器的处理方面。对于这种高水平的机器人人工智能，STRIPS仍有许多优势。

Stanford Research Institute Problem Solver 的提出有两大贡献。即使是在今天，这两项贡献仍然是人工智能规划社区的核心:

• 用于规划问题的表示语言。其基本思想是用操作控制一个世界模型，它有一组先决条件和side effects。side effects是从世界模型中添加或删除的事实列表。例如，一个射击操作需要一个枪，并且有side effects，如一个损坏的目标（需要添加到模型中），并且不再有装载的子弹（删除）。
• 使用两种不同的搜索算法：第一种是做规划本身，它计算出下一步应该在更高层次上做什么，第二种是在世界上什么是真实的，检查目标是否满足了。例如，一个算法将负责制定一套用于刺杀目标的操作集合，另一个搜索算法通过事实来检查世界模型中是否已经实现目标。

实际上，在应用中也有一些值得注意的想法:

• planner使用的是一种叫做“means-end”的策略。通过查看世界模型中什么需要修改，并选择合适的操作符来执行此任务。例如，如果目标位置不同，则使用move-to操作。这有助于更有效地推进搜索。
• 而且，由于A*是在SRI AI中心发明的，所以它通过应用启发式来帮助选择搜索图中的哪个节点是下一步要走的。
• 它的系统使用依赖跟踪 dependency tracking来找出一个计划的所有操作的先决条件。当发生意想不到的事情时，系统会知道是否需要重新规划。

正是这些想法的结合，使得系统的效率足以在实时控制机器人。当将STRIPS应用于游戏中时，也要记住这些技巧。

使用STRIPS的搜索树的示例

STRIPS algorithm的流程图

[来源：AIGAMEDEV， URL: http://aigamedev.com/open/article/strips-theorem-proving-problem-solving/#Motivation]

发展历史

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提出用一种基于图来进行规划，从而减少了从对状态空间图的直接探索中找到解决方案所需的搜索量。

规约到别的问题

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

时间规划

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

[出处：wiki， URL：https://en.wikipedia.org/wiki/Automated_planning_and_scheduling#Classical_planning]

主要事件

发展分析

瓶颈

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

未来发展方向

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

Contributor：Ruiying Cai