不确定规划中状态循环可达关系的求解方法  

Method of getting circular reachability relation in non-determinate planning

作　　者：黄丽芳[1] 文中华[1] 胡雨隆[1] 吴正成[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机应用研究》2013年第9期2689-2693,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61070232)

摘　　要：在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。It is frequent to search a lot of useless states and actions which can result in redundant calculations in solving plan- ning problems over a non-deterministic state-transition system in non-determinate plan field. Getting state accessibility relation for the nondeterministic state-transition system can avoid useless searching, reduce redundant calculations and create a guided information for the nondeterministic state-transition system. Based on acyclic reachability relation , this paper defined the cal- culation rules of matrix multiplication, classification of circular reachability relation and two-reachability relation. It aslo pres- ented the method to get circular reachability relation and designed an algorithm for this. The example proves the validity and correctness of the algorithm. If the non-determinate plan has the information of state accessibility, it can delete useless states and actions to reduce the size of the problem and improve solution efficiency of solving planning problem.

关 键 词：不确定规划 状态可达性 矩阵 循环可达关系 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]