Graphplan Extention And Chinese Chess

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...