The Study On Algorithm Of Weighted Strong Planning In Uncertain Planning

Planning by model checking for its ability to plan under uncertainty in a practical way, it has become one of the main research methods of uncertain planning. When using the planning by model checking to solve the uncertain planning problem, you can get three different types of solutions that weak solutions, strong cycle solutions and strong solutions; among them, strong solutions are plans that are finite and guaranteed to achieve the goal when executing the plans, thus strong solutions is the most valuable. In addition, in practice, executing the planning action requires a certain amount of time, money, etc.; these costs can be represented with movement weight; so the research of minimum weight of strong solutions is very meaningful. This paper mainly studied the fully observed with single agent of weighted uncertain planning problem and fully observed with multi-agent of weighted uncertain planning problem.In this paper, the third chapter first introduces the strong planning hierarchical algorithm based on model checking, and making strong planning hierarchical for the uncertain planning system. Then using hierarchical information to determine whether there is a strong planning solution, quickly ruled out the absence of a strong solution of planning; when there is a strong planning solution, it using the hierarchical information designed a reverse search algorithm of the minimum weight, the algorithm search by dynamically determine upper and lower bounds of the strategy, avoid a lot of useless search. Through the analysis of experimental results shows that the designed algorithm can quickly solve the solution of the minimum weight of strong planning, solving efficiency higher than the existing algorithm of direct solving the minimum weight strong planning solution.Currently, the study of uncertain planning problem is mainly focused on a single agent, and the study of multi-agent planning is focused on the determine planning. In response to this situation, this paper first puts forward the fully observed with multi-agent of weighted uncertain planning problem, and designed the strong solutions algorithm SPSMNPW which can solving the problem and the sum of the solution action weights is approximately minimal. In SPSMNPW algorithm, it firstly using the strong planning hierarchical algorithm based on model checking to make strong planning hierarchical for each agent, then using the information of agent's initial state collection to merge all agents' hierarchical information, and got the conflicting table between states of the same layer. At last, ensuring the minimal conflicting, using positive search method to obtain the solution of strong planning with minimum weight priority greedy method. Through the analysis of experimental results it shows that the designed algorithm can quickly obtain the strong solution, and the sum of the solution action weights is approximately minimal.