人工智能中的planning技术主要是研究如何获得达到目标的一系列最佳动作。Planning技术是在生产，太空，软件工程，机器人，教育与娱乐领域内建立智能系统的一项关键技术。在确定性planning问题中，graphplan方法具有明显的优势。Graphplan在类似STRIPS的确定性论域中进行规划。算法的核心思想是：首先构造出一个规划图，考虑的问题中的很多有用的约束信息可以显示地从规划图中得到从而缩小搜索空间。而且规划图可以在多项式时间与多项式空间中建立起来。规划图包括论域信息，求解问题的初始条件与目标还有显示的时间表示。然后分层进行搜索。规划图提供一种组织与保持问题高校解的搜索信息的手段，规划图的构建是多项式时间与空间的。实验表明，Graphplan可以较快地解决一些planning问题。Graphplan可以保证在那些独立动作可以同时发生的规划图中发现最短规划。graphplan可以在多项式时间与空间内构建规划图，并且从理论上证明了其完备性：若规划问题有解，则可以找到解；若无解，则停机返回。实验证明，在strips论域问题上，基于graphplan的规划器是最快的最省的。同时，graphplan也有其不可避免的缺陷。当问题过大时，graphplan构建的规划图所占空间仍旧十分巨大，构建规划图的过程所用时间与搜索时间相当。更为遗憾的是基于graphplan的规划器只适用于解决类似strips论域问题。对于非确定论域问题，由于graphplan采用回退搜索策略，因此graphplan不能很好的解决。电脑下棋，历来是人工智能(AI)的一个重要的研究领域。从学术上看，象棋属于非确定性论域问题。现在有人机相辅的比赛，人手一台机器，一个相同的软件，借助电脑人人对弈。由此，电脑软件转变为辅助者，人是决策者。这样，可以防止人犯一些低级错误，同时扩宽视野。 <WP=43>然而原始的Graphplan从理论上讲并不适合做这种具有交互过程的问题，因此需要对Graphplan做一些扩展，这需要结合minimax过程以及启发式搜索技术。古典规划方法习惯地假设论域问题是确定的，而且一些可以在非确定的环境中可以执行的规划算法常常假设世界是完全可以观察的。考虑到很多条件，在非确定论域中进行规划是非常费时的。一个减少在非确定论域中进行规划的时间的方法就是交叉规划与规划执行。不这样的话，为了解决规划问题必须发现一个很大的条件规划。相反的是，当交叉规划与规划执行的时候，agent只需要发现规划的开始。当执行完这个子规划后，agent可从得到的状态开始重复上述过程。交叉规划与规划执行的规划方法必须克服两个问题。第一，规划方法必须确认朝着目标前进而不是永远循环。第二，当碰到相似的规划问题，规划方法应该能提高规划执行效率。Min-Max LRTA*给状态提供一些信息以防止发生循环，交叉规划与规划执行，并且只在当前状态的邻域中进行规划。然后，我们介绍一种新的规划器AltAlt，它成功地结合了graphplan与状态启发搜索的优点，并且比二者都优。AltAlt结合stan(一种最好的graphplan)与hsp-r（一个启发搜索规划器）。实验表明：这种综合方法明显优于stan与hsp-r。graphplan方式的系统要搜索每一长度的规划空间直到找到解或证明没有解。这需要很大的时间与空间。相反的，状态搜索规划器在最好情况下所花费的时间与空间与问题的规模呈线性关系。但是不幸的是，现有的状态搜索规划器的启发信息无法处理子目标交互的一些问题，这些问题graphplan方式的规划器可以很好的解决。它综合了graphplan方式的规划系统与启发状态搜索的优点以及他们之间的一些互补特性。我们从规划图中提取启发信息，并利用这些启发信息控制搜索过程。本文尝试对graphplan做一扩展。在原来graphplan的基础上综合启发信息搜索与minimax LRTA*过程，使之可以处理非确定性论域问题，并使之用于象棋。在有些问题中，过程所使用启发信息较难提取。由于启发信息提取方法的问题，有些可能是解的可能被剪掉。带有启发信息的graphplan的特点是先构建一个规划图，然后从最后一层开始回退搜索，它适合处理确定性论域问题；minimax LRTA*则是在当前状态下往前搜索，它适合目标明确的非确定性论域问题。我们可以比较容易地从规划图中提取启发信息，但是对于非确定性问题，利用回退搜索存在很多问题。比如，对于一个可能的结果，我们不知道它是哪个动作的结果，这就需要回退搜索多个分支。采用minimax LRTA*<WP=44>前项搜索过程则可以避免这一缺点。同时，graphplan可以给minimax LRTA*提供启发信息。简而言之，我们的工作就是在象棋的人机相辅中利用graphplan提取启发信息，然后利用minimax LRTA*以及graphplan的结构信息进行前向搜索，从而解决预设目标。我们的工作的意义在于：通过对graphplan做一些扩展，并以一个象棋残局为实验对象，希望为处理非确定性论域问题提供一种方法。