状态空间规划

在人工智能和计算机程序设计中，状态空间规划是用于设计程序来搜索数据或解决问题的过程。在搜索数据结构的计算机算法中，例如在计算机字典中查找单词的程序，状态空间是要搜索的所有数据的集合项。类似地，人工智能程序经常采用一个过程，通过有限的搜索程序来达到目标，找到一个程序或达到目标的最佳程序。被搜索的可能解的宇宙称为状态空间。状态空间规划是决定程序将搜索的状态空间的哪些部分，以及按何种顺序进行的过程。

定义：

最简单的经典规划算法是状态空间搜索算法。其中搜索空间是状态空间的一个子集: 每个节点对应一个世界的状态，每条边对应一个状态转换，当前的规划对应于搜索空间中的当前路径。正向搜索和反向搜索是状态空间规划的两个主要样本。

前向搜索 Forward Search

前向搜索 (forward search) 是从初始状态找到在状态空间中满足目标状态的算法。定义Forward-search(O, s0, g)。该函数返回一个规划 P，否则返回失败。

s = s0 P = the empty plan loop if s satisfies g then return P applicable = {a | a is a ground instance of an operator in O,and precond(a) is true in s} if applicable = ∅ then return failure nondeterministically choose an action a from applicable s = γ(s,a) P = P.a

后向搜索 Backward Search

后向搜索是从目标状态向后追溯到初始状态的算法。定义Backward-search(O, s0, g)

s = s0 P = the empty plan loop if s satisfies g then return P relevant = {a | a is a ground instance of an operator in O that is relevant for g} if relevant = ∅ then return failure nondeterministically choose an action a from relevant P = a.P s = γ−1(s,a)

上图（a）就是向前搜索的案例，（b）就是向后搜索的案例

来源：wiki, URL:https://en.wikipedia.org/wiki/State_space_planning

发展历史

19世纪，法国数学家查尔斯·皮埃尔·特雷莫(Charles Pierre Tremaux)对深度优先搜索 Depth-first search (DFS) 的一个版本进行了研究，认为这是一种解决迷宫的策略。BFS(breadth-first search) 和它在寻找图形的连接部分的应用是由Michael Burke和Konrad Zuse在1945年发明的。Edsger Dijkstra在1959年在ARMAC计算机上写出了Dijkstra算法，它来搜索最短路径的算法，只使用f(p)=cost(p)。

在1968年，人工智能研究员尼尔斯·尼尔森(Nils Nilsson)试图改进机器人Shakey所做的路径规划，这个机器人原型可以通过在一个包含障碍物的房间进行导航。这种寻路算法，Nilsson称之为A1，是当时最著名的Hans Berliner于1979算法的更快版本，用于在图中找到最短路径。Bertram Raphael建议对这个算法进行一些重要的改进，并调用了修改后的A2。然后Peter E. Hart引入了一个论证，建立了A2，只有微小的变化，才能成为寻找最短路径的最佳算法。此时A星算法使用的评价函数是f(p)=cost(p)+h(p).

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

对于state-space search planning的系统或语言来说：

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

在人工智能中，动作描述语言(Action description language，ADL)是一个自动化的计划和调度系统，特别是机器人。它被认为是STRIPS的拓展。Edwin Pednault(数据抽象和建模领域的专家，自1996年以来一直是数据抽象研究小组的IBM研究工作人员）在1987年提出了这种语言。它是动作语言的一个例子。

Graphplan是Avrim Blum和Merrick Furst在1995年开发的自动规划算法。Graphplan将一个规划问题作为输入，在STRIPS中，就会产生一个达到目标状态的操作序列。graphplan的名称是由于使用了一个新的 planninggraph,，从而减少了从对状态空间图的直接探索中找到解决方案所需的搜索量。

Planning Domain Definition Language (PDDL) 是一种标准化人工智能(AI)规划语言的尝试。它最早由Drew McDermott 和他的同事在1998年开发(灵感来源于STRIPS和ADL)，主要是为了使1998/2000国际规划比赛( International Planning Competition IPC)成为可能，然后在每一场比赛中都得到了发展。

主要事件

发展分析

瓶颈

近年来，人工智能社区见证了解决状态空间规划问题的方法的成功(如，Weld 1999)。 Kautz and Selman (1996)也提出了 通用随机SAT算法(SATPLAN)被运用于AI规划中，然而，这个平台依旧存在一些问题：

• 一个问题是处理资源和相关的约束的困难。
• 从应用的角度来看，一个更重要的限制是SATPLAN框架固有的最优性概念可能太弱了。

具体详细内容：http://www.aaai.org/Papers/AAAI/1999/AAAI99-075.pdf

未来发展方向

在资源限制和优化目标下的人工智能规划问题。问题依旧属于practical planning optimization domains 优化领域的问题. 时间复杂度，空间复杂度，最优性，完全性都是衡量一个优化算法的重要指标，如何在合适的场景运用合适的规划算法这就需要我们的选择。

Contributor: Ruiying Cai