基于概率自动机的操作条件反射计算模型

基于概率自动机构造了反应操作条件反射行为的随机学习自动机,以模拟斯金纳(Skinner)鸽子试验.该随机学习自动机是一种能在未知的随机环境中完成自适应决策的智能单元,它与随机环境构成闭环,能在与环境的交互过程中学习选取给予奖赏的最佳动作.试验结果表明:该自动机模型体现了动物的操作条件反射行为,具有和实际类似的学习效果,对于处理先验知识缺乏或不完备的问题具有优越性.

模糊操作条件概率自动机仿生自主学习系统和机器人自平衡控制

为了实现两轮机器人的自平衡控制,利用Skinner操作条件反射机理,以概率自动机为平台,融入模糊推理,构造了模糊操作条件概率自动机(OCPA)仿生自主学习系统.该学习系统是一个从状态集合到操作行为集合的随机映射,采用操作条件反射学习机制,从操作行为集合中随机学习作为控制系统控制信号的最优行为,并利用学习到的操作行为取向值信息,调整操作条件反射学习算法.此外,学习系统还引入行为熵,以验证其自学习和自组织能力.应用于两轮机器人自平衡控制的仿真结果,验证了模糊OCPA学习系统的可行性.

关于概率自动机的等价性与极小化问题

本文给出了两概率自动机按顺序初始等价的充要条件,证明了初始等价的概率自动机的基矩阵秩必相等及判定极限极小概率自动机的一个充要条件.同时也更正了[1]中的一个错误。

概率自动机的等价性

本文研究概率自动机初始等价和等价之间的关系,基矩阵的性质,某些等价类的结构,并得到判定极限最小自动机的一个充分条件。

关于概率自动机的分解

在[1]中给出了有穷状态概率自动机A(BA A)可以分解为随机编码源T与确定型自动机B(DA B)的顺次连结,并用例子说明了分解的算法。该结论及算法是建立在随机向量的蕴含与随机矩陈凸分解的基础上。由于BA A的转移矩阵A(y/x)一般不是随机矩阵,因而[1]中首先由A(y/x)构造出相应的随机矩阵A(x)与C(x)才能进行分解。本文是在推广了[1]中有关概念及结论的基础上给出了一个不依赖于随机矩阵的分解方法。本文所引用的符号与概念可参考[1]与[2]。

基于概率时间自动机的异构多agent自适应运行时验证

多agent自适应系统在运行过程中需要根据环境进行自适应调整。异构agent能够提高agent的使用效率和降低系统的构建成本,但存在复杂的协作问题,因此提出一种基于概率时间自动机的异构多agent自适应系统运行时验证方法。该方法通过形式化描述异构agent的功能特征并融合环境中的随机因素构建概率时间自动机模型模拟自适应系统的运行过程,针对异构agent之间的协作逻辑制定安全约束条件以确保系统运行中状态迁移流程的安全性。通过模型检查结合运行时定量验证方法进行实验验证,在智能泊车系统案例中应用该方法。实验结果表明,agent之间协作逻辑的正确性可以有效保证系统运行时的稳定性,且相较于不使用运行时定量验证的初始系统在相同时间内正常运行的时间提升了21%左右。

概率有限状态自动机的代数性质

利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.

模型检测基于概率时间自动机的反例产生研究

模型检测基于概率系统的反例产生问题,在最近引起人们的关注.已有的工作主要围绕模型检测Markov链的反例产生而开展.基于概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展.关注的是模型检测PTA的反例产生问题.首先通过在PTA上寻找概率之和恰好大于λ的k条最大概率的路径,并根据这些路径和原PTA构造原PTA的一个子图,从而快速找到违背性质的具有较少证据的反例.然后精化此结果——通过逐条加入上述各条最大概率的路径来精确地计算已加入路径所构成的PTA子图的最大概率.由于考虑到符号状态交集对概率系统的影响,可以得到证据更少的反例.

概率有限自动机的商和同态

本文主要是通过概率有限自动机的有效划分来研究概率有限自动机的同态与商概率有限自动机的相关问题,得到了在同态或同构(弱同构)意义下概率有限自动机相互之间的关系,以及它们的商概率有限自动机的相互关系,得到了一些有意义的结果。

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。

多态概率元胞自动机森林火灾模型及应用

通过对概率元胞自动机模型的改进,分析了在既不能生长又不能燃烧的空地存在或森林砍伐形成的多态邻居条件下,森林中树木占有率的变化。模拟结果表明在适度留一些既不能生长又不能燃烧的空地或适度砍伐的条件下,不但不会减少森林中树木的比率反而有利于树木的生长。模拟结果与真实情况比较吻合。

概率元胞自动机的大偏差

研究了一类元胞自动机,证明了带随机扰动的元胞自动机即概率元胞自动机具有大偏差性质。

利用信息检索和概率有限自动机的程序理解

为提高基于信息检索的程序理解方法的准确性,提出了一种结合信息检索和概率状态机的两阶段程序理解方法.在该方法中使用概率有限自动机(probabilistic finite-state automata,PFA)解决了信息检索结果在程序理解中的不确定性,同时采用信息检索构建了多个简单的PFA,而不是单个复杂的PFA,提高了PFA分析的伸缩性.训练阶段先采用隐式语义分析对源代码进行聚类,然后在聚类结果上生成PFA.在识别阶段以词法处理后的程序作为检索项在程序模板库中进行信息检索,取检索结果中的最相关的n项作为候选模板,由候选模板对应得到相应的PFA,通过分析找到最大概率的PFA,完成对源码内容的语义标注.

概率有限自动机的交换性

提出了一类概率有限自动机并给出其交换的概念,得到了此类自动机交换的一些刻画,定义了两个概率有限自动机的和与积,并且得到了和自动机、积自动机交换的充要条件。

基于概率时间自动机的模型检测反例表示研究

近年来,概率系统在实际中应用越来越广泛,其中模型检测基于概率系统的反例生成问题,已引起人们的广泛关注,现有的工作主要围绕模型检测Markov链反例生成展开.概率时间自动机(PTA)是Markov链的不确定性和系统时钟的扩展,针对模型检测PTA的反例表示问题,首先将PTA的语义表示为Markov决策过程(MDP),通过策略解决MDP不确定性,将MDP转换为离散时间Markov链(DTMC);然后将DTMC转换为带权有向图,则PTA中最小反例问题转化为带权有向图中最短路径问题;最后采用正则表达式表示求得的反例.

基于概率时间自动机Web服务质量的形式化建模分析

针对拓展的Web服务体系结构,利用概率时间自动机(probabilistic timed automata,PTA)对Web服务组合进行形式化建模,将Web服务组合的过程理解为一个实时系统的运行过程,进而对Web服务组合的整体服务质量(quality of service,QoS)进行定量分析,从而克服了已有Web服务质量研究方式主要集中在对单个Web服务分析评估上的局限性,在整个分析过程中充分考虑Web服务组合执行过程所具有的随机性和不确定性,具有较高的可信度.通过实验说明了建模分析方法的可行性,并证明了采取相应的服务选择策略有助于提高Web服务组合的成功率.

MA建模的概率混成自动机转换方法研究

信息物理融合系统(CPS)是物联网进一步发展的产物,CPS将物理过程与信息计算过程紧密联系,是一种复杂的混合系统,Modelica与AADL是适用于信息物理融合系统(CPS)的嵌入式系统体系结构建模语言。利用Modelica对物理系统部分建模,AADL对信息系统部分建模,将信息物理系统的建模分割开来,设计了Modelica-AADL接口将二者结合起来,使得物理世界与计算过程相融合。概率混成自动机是对信息物理融合系统验证分析的有效形式化建模方式,Modelia-AADL模型无法进行直接的形式化模型检测工作,根据Modelica与AADL行为附件各自的特点,抽象出状态,定义了一系列规则,给出转换算法,完成了MA模型向概率混成自动机的转换,使得系统模型能够形式化描述,有助于信息物理融合系统的可靠性与安全性验证。

基于扩展RED图的概率时间自动机可达性分析

RED图可以表示一个完整的时间自动机上的状态集,包括其连续时间部分和离散部分.在它基础上实现的模型检测工具RED,在时间自动机模型检测中表现出了优良的性能.另一方面,现有的概率时间自动机模型检测工具仍然使用不同的方法来分别表示概率时间自动机状态的连续时间和离散部分.我们在复用原始RED图的数据结构的基础上,对其做出了扩展,以令其支持概率状态的表达,同时保持其性能方面的优势.我们又为此实现了一个概率时间自动机可达性分析工具原型,并将其与两个概率模型检测工具(PRISM和Modest)就概率时间自动机可达性分析作实验对比,来评估该工具原型的性能.实验结果显示,我们的集成表示概率状态空间的方式,确实提高了概率时间自动机模型检测的时间效率和延展性.

基于抽取-精化的概率系统假设-保证验证

假设-保证推理是标记迁移系统组合验证的有效手段,近期,假设-保证推理在概率系统的验证中也得到了应用。在推理中,假设的学习是通过Lstar算法来完成的。针对概率系统的假设-保证推理,提出了一种新的方法:首先直接对组合系统的一个组件进行抽取,得到一个初步的假设;通过与假设-保证规则进行多次交互,不断精化该假设;最后,要么得到一个适当的假设以证明结论的正确性,要么得到一个反例来证明结论不成立。

通用型自动物种识别算法的对比研究

在大数据时代,通用型自动物种识别算法的研究对于算法的共享性及可扩展性至关重要。Raven和Song Scope作为通用型自动识别算法的先驱,虽然被广泛使用,但是没有采用实时现场监测数据进行深入的对比研究。在细致挖掘Raven和Song Scope设计原理的基础上,提出时间概率自动机TPA(Timed and Probabilistic Automata),并对Raven、Song Scope和TPA进行了实验对比研究。结果表明,与Raven和Song Scope相比,TPA的平均准确率、回溯率及精确度均提高了大约20%.