Research On State Reachability Relationship And Minimum Weight Planning Solution In Uncertain Planning

With the expansion and application of intelligent planning,the research object of planning has changed from defined classic planning to uncertain planning,and the model of planning graph has also been extended from the certain graph model to the uncertain graph model.There are two important research topics in the field of uncertain planning which are the accessibility between states in planning and the solution of minimum weight planning.Uncertain planning and some more complicated query problems are based on the reachability relationship between states of the system.In the past,the research on state-reachable relationship is more about the solution in static environment,less about the research on states reachability in the field of uncertain planning in dynamic environment,which is more about the solution based on the situation when the deterministic action is not executable,but the possibility of the uncertainty action change is not involved,and the uncertain system studied exists unity.Therefore,this paper studies the state reachability relationship in the uncertain planning field under dynamic environment and the minimum weight planning solution of the uncertain planning.The main work is as follows:1.A new ITMSRR algorithm is proposed to maintain the states reachability.In view of the limitations of existing algorithms for maintaining state reachability,this paper proposes ITMSRR algorithm for updating state reachability in cyclic and acyclic systems,extending the possibility and diversity of executing actions in dynamic situation,and analyzing several situations of reachability transition between states affected by them.Considering the increase of deterministic actions and the possibility of the change of uncertain actions in the system,the ITMSRR algorithm is proposed,which can be applied to the reachability relationship of update states in both cyclic and acyclic systems.The algorithm uses a matrix to establish a model for updating the state reachability.Finally,the algorithm examples and experiments show the correctness of the algorithm,which is more efficient than resolving the state-reachable matrix.2.This paper proposes two algorithms based on a subset solution and a dynamic reachable matrix solving minimum weight programming,where the action cannot be performed in a dynamic environment,or a branch of an uncertain action cannot be performed.The subset-based solution algorithm is to solve the key states and actionsin the system,and then solve the minimum weight planning solution after the action is deleted in the system;the dynamic reachable matrix-based solution algorithm uses the ITMSRR algorithm to solve the state reachability matrix in the dynamic environment,then simplify the problem model according to the state reachability matrix,and then solve the minimum weight planning solution by reverse search.Finally,the algorithm examples and experiments are given to illustrate the flow and correctness of the two algorithms.