The Study On Algorithm Of Hierarchical State In Uncertain Planning

Uncertain planning is an important branch of a combination with automatedplanning and uncertainty. There are many repeated searches in current algorithmcontacting with uncertain planning because of the uncertainty of state transfer. So,how to avoid repeated search, and improve the efficiency of solving is always whatwe focus on when study uncertain planning.Hierarchical states and reachability relations of states are important tools toimprove the efficiency of planning problem solving. Hierarchical status can directlyimprove the efficiency of planning problem solving, but also take quite some time;reachability relations of state can significantly improve the solving efficiency of allplanning problems in a planning field, but the complexity of getting reachabilityrelations of states is high.This paper mainly studies layer algorithm of uncertain planning solving, thendeeply studies the feature, properties of weak planning hierarchical, strong cycleplanning hierarchical and strong planning hierarchical, and their layer algorithm,based on existing hierarchical algorithm. This paper’s main results are as follows:Define three kinds of states layer hierarchical requirements formally. Detaillyanalyze properties of states layer which follow the requirements of states layer.Propose the concept of complete hierarchical state, and part hierarchical state, analyzeits nature and function.For uncertain planning field hypergraph, design a two direction action graph datastorage structure. Uncertain planning actions and their results are stored directly in thecorresponding state to ease search actions and status, and efficiently use storage space.The hyper-arc edges in the hypergraph are saved at the start point and end point intwo directions in order to research in two directions. Using the data storage structureimproves hierarchical algorithm, and improves the efficiency of layered.Based on data storage structure of two direction action graph, use includesrelationship between strong planning hierarchical and strong cycle planninghierarchical, and the feature of strong planning hierarchical more efficient than thestrong planning hierarchical, via integrating strong planning hierarchical to strongcycle planning hierarchical, reuse the result of strong planning hierarchical in strongcycle planning hierarchical, design a more efficient strong cycle planning algorithm. By recording the reachability relationships of states in layer with original statesand goal states, combine the relationship between the information up to the targetstate, the strong cycle hierarchical algorithm and search algorithms, and design a moreefficient algorithm for strong cycle planning.Apply the state hierarchical algorithm to solve the reachability relationships ofstates, and define reachability four types of based relationships. Design flexibilityalgorithms to solve part of the reachability relationships, and can use different typesof states hierarchical to obtain reachability relationships of states of differentprecision.