摘要
在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。
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.
出处
《计算机应用研究》
CSCD
北大核心
2013年第9期2689-2693,共5页
Application Research of Computers
基金
国家自然科学基金资助项目(61070232)
关键词
不确定规划
状态可达性
矩阵
循环可达关系
non-determinate planning
state accessibility
matrix
circular reachability relation
