利用有向环的性质求解可达关系

Solving Reachability Relationship by Property of Directed Cycle

不确定规划研究的最终目标是求出规划解,但是由于缺少引导信息,直接求规划解会导致大量的无用状态和动作被搜索。获得状态间的可达关系可以避免冗余计算。目前求可达关系的方法效率较低,因此设计了一种求可达关系的新方法。将不确定状态转移系统抽象成一个图,在这个图中,查找状态之间的可达信息是否形成一个有向环。若存在一个有向环,说明环内每两个状态之间都有可达关系。将其中一个状态作为父节点,并且将这个环内所有状态的可达关系记录在父节点中,通过访问父节点的可达信息更新环内状态的可达信息,减少了许多无用的状态和动作被搜索。实验结果表明,所设计的算法不仅能得到更全面的可达关系,而且效率也高于已有的算法。

The goal of non-deterministic planning is getting the planning solution. Due to the lack of the helpful infor- mation, searching the problem space directly leads to a large number of useless work, which can be reduced dramatically by capturing the reachability relationship between states. But current methods perform poorly with respect to efficiency, thus we designed a new algorithm. We built a graph from the non-deterministic system, and checked whether there are some paths between states leading to some cycles. We concluded that every two states in the cycle are mutually reach- able,if such a cycle does exist. We could treat vertex as the parent,and tagged it with the reachability relationships. By using this relationships and updating the reachability information of the states in the cycle, we could prevent many useless states to be searched. The experimental results show that the designed algorithm not only gains more complete reachability relationships,but also outperforms the current algorithms in efficiency.