The Research For Planning Solution Algorithm Via The Reachability Relation Of The Uncertainty System

Intelligent planning is a hot research field of artificial intelligence in recent years.Uncertainty planning is one of the important branches. Because of the uncertainty ofthe action in uncertainty planning, the already existed method to get strong planningsolution、weak planning solution and strong cycle planning solution is reverse searchmethod that search taken from the target states, but because there is no guidanceinformation, there will be a large number of useless states and actions in the planningsolution searching. How to establish the guidance information for system and use it toimprove the solving efficiency has always been a difficult problem of the research.To solve the above problem, this paper discusess how to solve the problem inuncertainty planning system based on the reachability relation in uncertainty planningsystem,the major two aspects of the research as following:1. In uncertainty planning field, since there is no information and direction ingetting planning solution of uncertainty state transition system, there is a largenumber of redundant operations frequently, which leads unnecessary searching andcalculation. This paper converts uncertainty state transition system to an adjacencymatrix. Get reachability matrix of the system through the addition and multiplicationoperation of the adjacency matrix, which is the reachable relationship of the system.Therefore, we designed algorithms on the basis of the characteristics of the twomatrices to get strong planning solution and weak planning solution. In the process ofgetting planning solution, through the adjacency matrix we determine the next actionwhich the system should choose, and determine whether the results of the action canreach the target states or not, so we can determine the action and the state can be inthe planning solution or not. If a state is inaccessible, you can avoid searching theseactions and states which are useless in searching the strong planning solution and theweak planning solution. To determine whether a state and an action are usefulaccording to the values in the matrix in the process of searching, delete it if it isuseless, it can avoid a large amount of redundant calculation, improving the efficiencyof the planning solution.2. The first discussion of the multi-agent planning problem was arised on theICAPS2010, at present the multi-agent planning research focused on the multi-agentplanning field with only certainty actions, and the multi-agent planning problem withuncertainty action is still a very new field. In this paper, we design an algorithm basedon reachable relationship to get multiple-agent collaborative planning solution. Under the assumption that every action of the agents takes the same time, this algorithmuses transfer information of states and reachability in adjacency matrix and reachablematrix in order to determine the next action for the agents. After executed actions, ifan agent reach the same state with the last agent and the total execution times of themare equal, make the agent to perform an action time to wait, which can avoid conflictand finding the collaborative planning solution for all agents. Through the experimentproves the feasibility and effectiveness of the algorithm.