graphplan扩展与中国象棋
摘要
人工智能中的planning技术主要是研究如何获得达到目标的一系列最佳动作。Planning技术是在生产，太空，软件工程，机器人，教育与娱乐领域内建立智能系统的一项关键技术。在确定性planning问题中，graphplan方法具有明显的优势。
Graphplan在类似STRIPS的确定性论域中进行规划。算法的核心思想是：首先构造出一个规划图，考虑的问题中的很多有用的约束信息可以显示地从规划图中得到从而缩小搜索空间。而且规划图可以在多项式时间与多项式空间中建立起来。规划图包括论域信息，求解问题的初始条件与目标还有显示的时间表示。然后分层进行搜索。
规划图提供一种组织与保持问题高校解的搜索信息的手段，规划图的构建是多项式时间与空间的。实验表明，Graphplan可以较快地解决一些planning问题。
Graphplan可以保证在那些独立动作可以同时发生的规划图中发现最短规划。
graphplan可以在多项式时间与空间内构建规划图，并且从理论上证明了其完备性：若规划问题有解，则可以找到解；若无解，则停机返回。实验证明，在strips论域问题上，基于graphplan的规划器是最快的最省的。
同时，graphplan也有其不可避免的缺陷。当问题过大时，graphplan构建的规划图所占空间仍旧十分巨大，构建规划图的过程所用时间与搜索时间相当。更为遗憾的是基于graphplan的规划器只适用于解决类似strips论域问题。对于非确定论域问题，由于graphplan采用回退搜索策略，因此graphplan不能很好的解决。
电脑下棋，历来是人工智能(AI)的一个重要的研究领域。从学术上看，象棋属于非确定性论域问题。现在有人机相辅的比赛，人手一台机器，一个相同的软件，借助电脑人人对弈。由此，电脑软件转变为辅助者，人是决策者。这样，可以防止人犯一些低级错误，同时扩宽视野。
然而原始的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*
前项搜索过程则可以避免这一缺点。同时，graphplan可以给minimax LRTA*提供启发信息。
简而言之，我们的工作就是在象棋的人机相辅中利用graphplan提取启发信息，然后利用minimax LRTA*以及graphplan的结构信息进行前向搜索，从而解决预设目标。我们的工作的意义在于：通过对graphplan做一些扩展，并以一个象棋残局为实验对象，希望为处理非确定性论域问题提供一种方法。
Planning in artificial intelligence is concerned with developing methods that reason about the consequences of actions to determine how best to achieve given objectives. Planning is a key technology for building intelligent systems in areas such as manufacturing, space systems, software engineering, robotics, education, and entertainment.
Graphplan algorithm involves two interleaved stages– expansion of the “planning graph” data structure,and a backward search on the planning graph to see if any subgraph of it corresponds to a validsolution for the given problem. The expansion of the planning graph is a polynomial time operationwhile the backward search process is an exponential time operation.
The critical asset of the planning graph, for our purposes, is the efficient marking and propagation of mutex constraints during the expansion phase. The propagation starts at level 1, with the actions that are statically interfering with each other (i.e., their preconditions and effects are inconsistent) labeled mutex. Mutexes are then propagated from this level forward by using two simple propagation rules: Two propositions at level k are marked mutex if all actions at level k that support one proposition are pair-wise mutex with all actions that support the second proposition. Two actions at level k + 1 are mutex if they are statically interfering or if one of the propositions (preconditions) supporting the first action is mutually exclusive with one of the propositions supporting the second action.
Graphplan outputs “No Plan Exists” if and only if the problem is unsolvable.
Graphplan has its inner shortcomings. It is sometimes that the problem is so large that the space needed for constructing planning graph outweighes the system ’s space;and the time of constructing the planning graph is approximate to the time of searc; and the more pity about graphplan is that it is only suitable for strips domain.Graphplan can’t deal with domain under uncertainty because of its regression search.
Computer chess is an important field of artificial intelligence. The game of Chinese chess belongs academically to one of underteministic domains. There are some contests of chess in which every competitor is allowed to have a computer as an assistant. The key of the computer only acts as an assistant,and people makes their decisions. This kind of contest can prevent people from making apparent errors and widen their skies.
But the primitive graphplan does not theoretically fit for the chess process which is a kind of underterministic domains. Combining with minima LRTA* and heuristic search technologies, we extend graphplan to deal with chess process.
Classical planners traditionally assume that domains are deterministic, and the few planners that can operate in nondeterministic domains often assume that the state of the world is completely observable. However, operate in nondeterministic domains, and planning in nondeterministic domains can be time-consuming due to the many contingencies. One general principle that can reduce the planning time in nondeterministic domains is interleaving planning and plan executions .Without interleaving planning and plan executions, the agent have to find a large conditional plan that solves the planning task. When interleaving planning and plan executins, the agent only needs to find the begin of the plan, and when the subplan is finished, the agent repeats the discripted process.
Planning methods that interleave planning and plan executions have to overcome two problems. First, they have to make sure that they make progress towards the goal instead of cycling forever. Second, they should be able to improve their plan-execution time as they solve similar planning tasks, otherwise they do not behave efficiently in the long run in case similar planning tasks unexpectedly repeat. in case similar planning tasks unexpectedly repeat. Min-Max LRTA* associates information with the states to prevent cycling, interleaves planning and plan executions, and plans only in the
Graphplan在类似STRIPS的确定性论域中进行规划。算法的核心思想是：首先构造出一个规划图，考虑的问题中的很多有用的约束信息可以显示地从规划图中得到从而缩小搜索空间。而且规划图可以在多项式时间与多项式空间中建立起来。规划图包括论域信息，求解问题的初始条件与目标还有显示的时间表示。然后分层进行搜索。
规划图提供一种组织与保持问题高校解的搜索信息的手段，规划图的构建是多项式时间与空间的。实验表明，Graphplan可以较快地解决一些planning问题。
Graphplan可以保证在那些独立动作可以同时发生的规划图中发现最短规划。
graphplan可以在多项式时间与空间内构建规划图，并且从理论上证明了其完备性：若规划问题有解，则可以找到解；若无解，则停机返回。实验证明，在strips论域问题上，基于graphplan的规划器是最快的最省的。
同时，graphplan也有其不可避免的缺陷。当问题过大时，graphplan构建的规划图所占空间仍旧十分巨大，构建规划图的过程所用时间与搜索时间相当。更为遗憾的是基于graphplan的规划器只适用于解决类似strips论域问题。对于非确定论域问题，由于graphplan采用回退搜索策略，因此graphplan不能很好的解决。
电脑下棋，历来是人工智能(AI)的一个重要的研究领域。从学术上看，象棋属于非确定性论域问题。现在有人机相辅的比赛，人手一台机器，一个相同的软件，借助电脑人人对弈。由此，电脑软件转变为辅助者，人是决策者。这样，可以防止人犯一些低级错误，同时扩宽视野。
然而原始的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*
前项搜索过程则可以避免这一缺点。同时，graphplan可以给minimax LRTA*提供启发信息。
简而言之，我们的工作就是在象棋的人机相辅中利用graphplan提取启发信息，然后利用minimax LRTA*以及graphplan的结构信息进行前向搜索，从而解决预设目标。我们的工作的意义在于：通过对graphplan做一些扩展，并以一个象棋残局为实验对象，希望为处理非确定性论域问题提供一种方法。
Planning in artificial intelligence is concerned with developing methods that reason about the consequences of actions to determine how best to achieve given objectives. Planning is a key technology for building intelligent systems in areas such as manufacturing, space systems, software engineering, robotics, education, and entertainment.
Graphplan algorithm involves two interleaved stages– expansion of the “planning graph” data structure,and a backward search on the planning graph to see if any subgraph of it corresponds to a validsolution for the given problem. The expansion of the planning graph is a polynomial time operationwhile the backward search process is an exponential time operation.
The critical asset of the planning graph, for our purposes, is the efficient marking and propagation of mutex constraints during the expansion phase. The propagation starts at level 1, with the actions that are statically interfering with each other (i.e., their preconditions and effects are inconsistent) labeled mutex. Mutexes are then propagated from this level forward by using two simple propagation rules: Two propositions at level k are marked mutex if all actions at level k that support one proposition are pair-wise mutex with all actions that support the second proposition. Two actions at level k + 1 are mutex if they are statically interfering or if one of the propositions (preconditions) supporting the first action is mutually exclusive with one of the propositions supporting the second action.
Graphplan outputs “No Plan Exists” if and only if the problem is unsolvable.
Graphplan has its inner shortcomings. It is sometimes that the problem is so large that the space needed for constructing planning graph outweighes the system ’s space;and the time of constructing the planning graph is approximate to the time of searc; and the more pity about graphplan is that it is only suitable for strips domain.Graphplan can’t deal with domain under uncertainty because of its regression search.
Computer chess is an important field of artificial intelligence. The game of Chinese chess belongs academically to one of underteministic domains. There are some contests of chess in which every competitor is allowed to have a computer as an assistant. The key of the computer only acts as an assistant,and people makes their decisions. This kind of contest can prevent people from making apparent errors and widen their skies.
But the primitive graphplan does not theoretically fit for the chess process which is a kind of underterministic domains. Combining with minima LRTA* and heuristic search technologies, we extend graphplan to deal with chess process.
Classical planners traditionally assume that domains are deterministic, and the few planners that can operate in nondeterministic domains often assume that the state of the world is completely observable. However, operate in nondeterministic domains, and planning in nondeterministic domains can be time-consuming due to the many contingencies. One general principle that can reduce the planning time in nondeterministic domains is interleaving planning and plan executions .Without interleaving planning and plan executions, the agent have to find a large conditional plan that solves the planning task. When interleaving planning and plan executins, the agent only needs to find the begin of the plan, and when the subplan is finished, the agent repeats the discripted process.
Planning methods that interleave planning and plan executions have to overcome two problems. First, they have to make sure that they make progress towards the goal instead of cycling forever. Second, they should be able to improve their plan-execution time as they solve similar planning tasks, otherwise they do not behave efficiently in the long run in case similar planning tasks unexpectedly repeat. in case similar planning tasks unexpectedly repeat. Min-Max LRTA* associates information with the states to prevent cycling, interleaves planning and plan executions, and plans only in the
引文
[1] Avrim L.Blum &Merrick L.Furst,“fast planning through planning graph analysis”，final version in Artificial Intelligence,90:281-300,1997.
[2] 赵殿中，《中国象棋软件评测》，中国象棋网。
[3] Sven Koenig,“Minimax real time heuristic search”,artificial intelligence 129(2001),165-197.
[4] Nils J.Nilsson著，郑扣根等译，《人工智能》227-250，2000，9，机械工业出版社。
[5] 刘叙华&姜云飞，《人工智能原理》，1995，吉林大学。
[6] Romeo Sanchez Nigenda & XuanLong Nguyen,“AltAlt:Combining the Advantages of Graphplan and Heuristic State Search”,2000.9。
[7] Avrim L.Blum & John C.Landford,“Probabilistic Planning in the Graphplan Framework”，School of Computer Science,Carnegie Mellon University,Pittsburgh PA15213-3891.
[8] Craig Boutilier & Tom Dean,“Editorial”,Artificial Intelligence 147(2003)1-4.
[9] Maria Fox & Derek Long,“PDDL2.1:An Extension to PDDL for Expressing Temporal Planning Domains”，University of Durham，UK，2003.4.
[10] Henry Kautz & Bart Selman,“BLACKBOX:A New Approach to the Application of Theorem Proving to Problem Solving”,www.washton.edu.
[11] XuanLong Nguyen & SubbaraoKambhampati,“Planning Graph as the Basis for Deriving Heuristics for Plan Sysnthesis by State Space and CSP Search”,email:{xuanlong,rao,rsanchez}@asu.edu.
[12] Alfonso Gerevini & Alessandro Saetti,“Planning through Stochastic Local Search and Temporal Action Graphs in LPG”，Journal of Artificial Intelligence Research.
[13] Michel Cayrol & Pierre Regnier,“Least commitment in Graphplan”,Artificial Intelligence130(2001)85-118.
[2] 赵殿中，《中国象棋软件评测》，中国象棋网。
[3] Sven Koenig,“Minimax real time heuristic search”,artificial intelligence 129(2001),165-197.
[4] Nils J.Nilsson著，郑扣根等译，《人工智能》227-250，2000，9，机械工业出版社。
[5] 刘叙华&姜云飞，《人工智能原理》，1995，吉林大学。
[6] Romeo Sanchez Nigenda & XuanLong Nguyen,“AltAlt:Combining the Advantages of Graphplan and Heuristic State Search”,2000.9。
[7] Avrim L.Blum & John C.Landford,“Probabilistic Planning in the Graphplan Framework”，School of Computer Science,Carnegie Mellon University,Pittsburgh PA15213-3891.
[8] Craig Boutilier & Tom Dean,“Editorial”,Artificial Intelligence 147(2003)1-4.
[9] Maria Fox & Derek Long,“PDDL2.1:An Extension to PDDL for Expressing Temporal Planning Domains”，University of Durham，UK，2003.4.
[10] Henry Kautz & Bart Selman,“BLACKBOX:A New Approach to the Application of Theorem Proving to Problem Solving”,www.washton.edu.
[11] XuanLong Nguyen & SubbaraoKambhampati,“Planning Graph as the Basis for Deriving Heuristics for Plan Sysnthesis by State Space and CSP Search”,email:{xuanlong,rao,rsanchez}@asu.edu.
[12] Alfonso Gerevini & Alessandro Saetti,“Planning through Stochastic Local Search and Temporal Action Graphs in LPG”，Journal of Artificial Intelligence Research.
[13] Michel Cayrol & Pierre Regnier,“Least commitment in Graphplan”,Artificial Intelligence130(2001)85-118.