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

对一个不确定状态转移系统求多个规划问题,那么获得不确定状态转移系统的状态可达关系可以方便求解规划问题,减少冗余计算,建立系统的引导信息。提出一个关于矩阵求不确定领域的状态可达性关系的方法,主要思想是以矩阵乘法来模拟状态转移系统中状态转移,对不确定动作带来的扩散和确定关系带来的聚合进行了统计和处理,从而获得状态可达信息。证明了方法的正确性和有效性。在不确定规划中确定了状态之间的可达性关系,可以在求规划解时删除对规划没有用的状态节点和状态动作序偶;选择能到达目标节点的状态节点和状态动作序偶;进行启发式正向搜索;减少大量冗余计算;提高求解效率。     

不确定规划中循环可达状态信息的维护

动态环境下,动作执行的不确定性会因外部因素存在变动,因此将导致不确定系统中的状态可达关系可能发生改变.为解答这一问题,论文对信息传递法中状态之间可达关系的更新方式进行改进,提出一种新的状态可达关系的维护算法.该算法将变更的状态之间可达关系与原可达矩阵对比,利用邻接矩阵中对应可达信息对变更后状态的可达信息进行修改,然后通...     

不确定规划中可达关系的快速求解算法

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。     

信息传递法求不确定系统中的状态可达关系

在不确定规划领域中,在求规划问题的解时,由于缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。所以在求规划解之前,找到不确定状态转移系统中状态之间的可达关系是很有意义的。以往的算法是通过矩阵相乘来模拟状态转移,但该类算法对于规模较大的系统开销较大。因此,提出了用信息传递法来求解可达关系,用矩阵来模拟不确定状态转移系统。其中每个状态记录了其他状态到达该状态的可达信息,通过状态之间的可达信息的传递,求得不确定系统的状态可达关系,以避免大量的矩阵运算。通过实验对比表明,当不确定系统规模较大时,所设计的算法优于矩阵相乘的算法。     

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

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

模型检测规划中的状态之间的可达关系研究

当前,对基于模型检测规划研究的算法中存在大量的冗余计算,一些不可能参与构成解的状态动作序偶被反复筛选.文中给出了一种在不确定规划领域求规划解的新思路:在求规划解之前,找到不确定状态转移系统的状态之间的可达关系,从而根据状态之间的可达关系进行约简.提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了关于弱规划解、强规划解和强循环规划解的一些重要性质.这些性质是关于一些状态动作序偶是否不可能参与构成弱规划解、强规划解和强循环规划解的结论.通过这些性质可以将大量的状态动作序偶直接去掉,从而大幅度简化求规划解的过程,提高求规划解效率.     

不确定可逆规划的强循环规划解

动作的执行在理想情况下是确定的,但现实生活中常常因为意外情况的发生而造成了不确定性,并产生不利影响.针对这种情况,建立了一种新的不确定规划模型,在不确定规划中增加了两个约束：1)所有动作的执行是可逆的;2)若一个状态在理想情况下不能达到目标,那么它不能企图在执行一个动作时发生意外而接近或达到目标.在该模型下设计了求解强循环规划的算法,首先只考虑所有动作的执行是在理想情况下发生的,这时可以将规划子图转换为规划子树并求出规划子树中每个状态的可达性;接下来考虑所有动作执行意外的情况,若动作被意外执行之后不能到达目标状态,则删除这个动作并更新规划子图和规划子树,最后通过遍历规划子图和规划子树求强循环规划解.考虑到有些意外的发生并不可预知,该算法能够在意外发生时只对部分失效的规划解进行更新而不需要重新求规划解.实验结果证明该算法能够快速地更新规划解且与问题的规模大小无关.     

顺序价值迭代算法求解不确定规划

基于Markov决策过程(MDP)的规划方法可以处理多种不确定规划问题,价值迭代算法(VI)是求解MDP的经典算法,但VI需要计算更新每个状态的值,求解过程相当缓慢。在分析了MDP状态图本身的因果依赖关系的基础上,提出一种改进的价值迭代算法,称为顺序价值迭代算法(SVI)。它先将一个MDP分解成多个拓扑有序的强连通分量,然后应用价值迭代算法顺序求解各个分量,这样处理可以避免对大量无用状态的计算并使得可用状态排成拓扑序列。对比实验结果证明了该算法的有效性及优异性能。     

车辆跟随控制策略的状态可达集建模及验证方法

车辆动态行为的不确定性会造成跟随车辆控制的不确定性.传统的车辆跟随控制方法只是针对车辆的单一行为动态的不确定性进行建模,无法遍历车辆所有可能的控制输入,因而,既无法一次性提供跟随策略下完整的可行控制方案,也不足以在理论上保证对策略安全检测的可信性.为此,提出车辆跟随控制策略的状态可达集建模及验证方法.该方法将控制策略转...     

求解不确定TSP问题的蚂蚁算法

提出了不确定旅行商问题模型,该模型将路径长度看作动态可变的。从实际应用来说,该模型考虑了交通运行中的不确定情况,比经典旅行商问题更具有灵活性及实用价值,利用该模型得到的结果将更适于指导车辆对运行路线的选择。同时提出了一种基于蚂蚁算法的混合方法求解不确定旅行商问题,并给出了解的评价标准。实验结果显示,该方法能够加速蚂蚁算法的收敛性,可以有效求解不确定旅行商问题。     

可达性等价于状态方程可满足性的petri网子类

定义了一个petri网子类:PN=(S,T;F,M0),满足条件s∈S→｜·s｜≤1。证明:当目标标识Md>0时,此petri网子类的可达性等价于状态方程Md=M0+ATX的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论:(1)对于满足M0+ATX>0的每个非平凡的非负整数向量X,都■t∈Tx:M0[t>;(2)对于满足M0+ATX>0的每个非平凡的非负整数向量X,X都是PN的一个可执行向量。     

可达性等价于状态方程可满足性的一个petri网子类

本文定义了一个petri网子类： ,满足条件 。本文证明：当目标标识 时,此petri网子类的可达性等价于状态方程 的可满足性。同时,当此petri网子类的可达性等价于状态方程可满足性时,可得出如下两点结论：①对于满足 的每个非平凡的非负整数向量 ,都 ;②对于满足 的每个非平凡的非负整数向量 , 都是 的一个可执行向量。     

确定树求强规划解

定义了确定树,设计了求确定树的方法。基于该方法设计了求强规划解的算法,找到每个初始状态对应的确定树,在找到确定树之后,求强规划解不需要从目标状态一直搜索到初始状态,只需要从目标状态反向找到确定树的任意一个节点,再通过这个节点在确定树中反向搜索到初始状态从而得到一个强规划解。实验结果表明：所设计的算法比用反向搜索方法求强规划解的算法的效率高。     

Distributed reachability testing of concurrent programs

Reachability testing is an approach to verifying concurrent programs. During reachability testing, every partially ordered synchronization sequence of a program with a given input is exercised exactly once. In this paper, we present the design and implementation of a distributed reachability testing algorithm for a cluster of workstations. This algorithm allows different test sequences to be exercised concurrently by different workstations without any synchronization, and without any duplication of sequences among workstations. Dynamic load balancing is performed using a work‐stealing scheme. A novel aspect of this scheme is that work‐stealing requests progress in rounds. This round‐based structure identifies overloaded workstations to target for work stealing. Empirical studies show good speedup for four benchmark Java programs and one Lotos specification. Copyright © 2010 John Wiley & Sons, Ltd.     

On the optimal reachability problem of weighted timed automata

We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSpace-Complete. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs: their time-transitions use a time τ which is arbitrarily close to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games. Research supported by the FRFC project “Centre Fédéré en Vérification” funded by the Belgian National Science Foundation (FNRS) under grant nr 2.4530.02.     

Reverse reachability analysis: A new technique for deadlock detection on communicating finite state machines

The communicating finite state machines can exchange messages over bounded FIFO channels. In this paper, a new technique, called reverse reachability analysis, is proposed to detect deadlocks on the communication between the communicating finite state machines. The technique is based on finding reverse reachable paths starting from possible deadlock states. If a reverse reachable path can reach the initial global state, then deadlock occurs. Otherwise the communication is deadlock-free. The effectiveness of the technique has been verified by some real protocols such as a specification of X.25 call establishment/clear protocol and Bartlet's alternating bit protocol.     

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata （DFA） and nondeterministic finite automata （NFA）.     

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata (DFA) and nondeterministic finite automata (NFA).     

软件编程构造和实现Petri Nets可达树

采用数据结构的思想和一些算法,将C 中的一些优良特性应用到Matlab编程语言中,用Matlab编程语言编程实现了PetriNets的可达树的构造。该程序对Petri Nets系统的动态性能分析具有一定的参考价值。