Research On Strong Planning Solution And Weak Planning Solution

Automated Planning is an important research field in Artificial Intelligence, it has a great significance effect in practical applications. Though its history is not long, Planning based on model checking becomes an important research field, it can deal with nondeterminism. Because the actions of a nondeterministic state-transition system is uncertain, we used to use backward search method which searches strong solution and weak solution from goal states, but it is difficult to improve the efficiency of the algorithm. In this paper, it introduces a method with high efficiency for searching strong solution and weak solution. In addition, the numeric planning problems also have a great significant effect in practical applications, and we'll discuss it in this paper too. For these proplems, in this paper, we propose some methods based on model checking, and these research achievements are as follows:1. This paper proposes a forward search method, which can deal with the strong solution and weak solution of nondeterministic state-transition system. At first, this paper analyses the algorithms based on backforward method in reference[1], which can be used to deal with nondeterminism, by analyzing many samples of the algorithms, we can point out the deficiencies of it. Algorithms in reference[1] need to search plenty of state-action pairs repeatedly, it also need to search many state-action pairs which are not in the state-action table of solution. If the algorithms can avoid searching these useless state-action pairs, we can get high-efficiency solutions. This paper designs a way that obtains hierarchical states of nondeterministic state-transition system, if the system is hierarchical, we will delete these state-action pairs, so algorithms needn't search these state-action pairs which are not included in solution, then algorithms in strong planning solution and weak planning solution based on forward search method in the field of nondeterministic state-transition system is given. Finally, the experimental results show that the algorithm based on forward search method is superior to the algorithm based on backward search method.2. A way for searching strong planning solution and weak planning with minimal cost is designed. At first, the concept of strong planning solution with minimal costs is proposed, we add the weight to actions of nondeterministic state-transition system, which is the cost that the action makes its effects true, so the weak solution and strong solution has a total cost, then we can get a planning solution with minimal action cost. Plan with miniman action cost is a kind of numerical plan problems, corresponding to the optimization problem, it has a great significance effect in practical applications. Then algorithms for searching strong planning solution and weak planning with minimal cost are designed. Finally, the experimental results show that the method for searching strong planning solution with minimal costs can deal with the strong planning solution with minimal costs and weak planning solution with minimal costs effectively and correctly.