基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.     

基于模糊约束规划的自动协商

给出了一个基于模糊约束规划模型的自动协商系统。建立了模糊约束规划模型并利用模糊模拟、神经网络和遗传算法给出了求解Pareto最优解的混合智能算法;协商过程中卖方智能体根据神经网络拟合的效用函数并运行混合智能体算法得到当前协商步的Pareto最优解,避免了对大型商品数据库的反复搜索,为系统推向实际应用奠定了基础;协商模型仿真实验表明了协商系统返回的解与实际调查得到的用户偏好相一致。     

基于变约束规划模型的炼钢连铸动态调度

针对炼钢连铸生产过程中时常出现各种扰动, 采用人工调度存在反应慢、调度结果不优化的问题, 在分析各种调整方式基础上, 建立了在线调整非线性规划模型, 通过约束变化满足不同的调整方式要求, 并将模型转化为线性规划模型后对其进行求解. 在国内某大型钢厂应用结果表明: 采用该方法在缩短动态调度时间、减少钢水冗余等待时间、提高设备负荷率方面取得显著成效.     

基于线性约束规划问题的神经网络模型

提出了一种基于梯度投影矩阵下的求解线性约束下规划问题的神经网络模型，并导出了线性约束下规划问题的稳定解法，该网络模型既适合于求解线性约束下线性或非二次规划问题，又适合于求解线性或非线性方程组，与其它规划问题的神经网络相比，更具有一般性。     

基于本体的智能规划方法研究及应用

针对经典智能规划方法在利用领域知识方面存在的不足,将先进的知识工程方法与通用智能规划算法相结合,提出了一种新型的基于本体的智能规划技术,它能够综合利用本体知识库中的领域知识对特定领域问题进行合理高效的规划求解,同时给出了一套构建用于支持这类规划过程的领域知识本体库的实用方法。实验结果表明,该方法能够有效地解决复杂的实际应用问题,使由此建立的规划系统真正达到实用水平。     

基于特定入侵检测问题的规划识别模型的研究

该文在特定的入侵检测问题中,对于规划识别技术进行了初步研究,提出了基于特定入侵检测问题的规划识别模型。     

基于约束分析与模型检测的代码安全漏洞检测方法研究

与传统的程序分析相比,模型检测具有较高的检测精度,但无法将其直接应用于缓冲区溢出、代码注入等安全漏洞的检测.为解决此问题,提出了基于约束分析与模型检测相结合的安全漏洞自动检测方法.首先,通过约束分析跟踪代码中缓冲区的信息,在涉及缓冲区操作的危险点生成相应的属性传递和属性约束语句,并将安全漏洞检测问题转化为模型检测方法可接受的可达性检测问题.然后,采用模型检测方法对安全漏洞的可达性进行判断.同时采用程序切片技术,以减少状态空间.对6个开源软件的检测结果表明,基于该方法实现的CodeAuditor原型系统发现了18个新漏洞,误报率为23％.对minicom的切片实验显示,检测性能有较大提高.     

自动获取派生谓词规划领域的通用规划

通用规划(解)是针对某个领域的像算法一样的规划解,通过对其的解释可以直接得出具体问题的规划解,而不需要调用任何规划系统.但是目前通用规划的提取只能在一些简单或者特殊的领域中进行,没有推广到复杂或者一般的规划领域.该文提出在包含派生谓词的规划领域自动获取通用规划的方法.与已有获取方法不同的是:首先,基于派生谓词规则,文中方法明确指出派生谓词目标与动作效果之间的依赖关系,用以完善通用规划中动作应用的目的;其次,在提取过程中借助角色来帮助识别规划解中的循环结构.实验结果表明,文中方法不仅容易在派生谓词规划领域中获取通用规划,而且还能够以较好的性能求解一类以派生谓词为主要目标的规划"难"题.该文是在派生谓词规划领域中提取通用规划的首创性工作.     

基于约束规划的一类排序问题通用求解方法

多约束排序问题是生产调度中常遇到的问题,传统的优化模型及方法在适应约束改变等方面存在诸多不足。鉴于此,将多约束排序问题定义为约束满足问题,系统设计时将模型定义与求解算法分离,利用约束规划平台的基本约束构建特定领域的抽象约束库,形成可重构的多约束排序问题通用求解框架。应用时,根据问题需求不同可利用抽象约束库快速重构优化模型,针对重构的优化模型配置相应的求解算法即可实现问题求解。应用结果表明,提出的方法通用性强,可满足实际应用的要求。     

基于规划识别的入侵检测研究

规划识别是人工智能的重要研究分支之一,在入侵检测领域中已有初步的应用。本文在介绍规划识别和入侵检测基本概念的基础上,按照规划识别方法分门别类地研究了基于事件层的规划识别、基于贝叶斯网络的规划识别、基于扩展目标规划图的规划识别、彩色Petri网、对手规划、行为状态图等在入侵检测领域的应用现状和进展;接着深入分析了规划识别和入侵检测的关系和相似之处;最后讨论了基于规划识别的入侵检测存在的问题,并指出了未来的发展趋势。本文综述了智能规划在入侵检测中应用的关键技术和存在的问题,研究内容对于相关人员从事入侵检测研究具有重要的参考价值。     

非完整约束下的机器人运动规划算法

由非完整约束定义提出一种改进RRT(快速搜索随机树)算法,解决受动力学约束的移动机器人运动规划问题.该算法将移动机器人的非完整约束条件与RRT搜索算法相结合.针对RRT算法在全局状态空间均匀随机搜索导致算法无谓耗费代价大的缺陷,引入目标偏向思想,并选择计算复杂度低的距离参数提高求解速度.通过几类典型的非完整约束下的机器...     

Toward Automation for Model-Checking Requirements Specifications with Numeric Constraints

Model-checking techniques have not been effective in important classes of software systems – systems characterised by large (or infinite) input domains with interrelated linear and non-linear constraints over the system variables. Various model abstraction techniques have been proposed to address this problem, but their effectiveness in practice is limited by two factors: first, the abstraction process is manual and requires a great deal of ingenuity; and, second, the abstraction may be coarse and introduce too many spurious behaviours to provide meaningful analysis results. In this paper, we wish to propose domain reduction abstraction based on data equivalence and trajectory reduction as an alternative and complement to other abstraction tech niques. Our technique applies the abstraction to the input domain (environment) instead of the model and is applicable to constraint free and deterministic constrained data transition systems. Our technique is automatable with some minor restrictions. We provide formal proofs for the theoretical soundness of the technique, algorithms for automation, and an illustration of the approach with examples. Correspondence and offprint requests to: Mats P. E. Heimdahl, Department of Computer Science and Engineering, University of Minnesota, 200 Union Street SE, 4-192 Minneapolis, MN 55455, USA. E-mail: heimdahl@cs.umn.edu     

不确定规划中的多Agent带权值强规化算法

在智能规划领域中,以往对不确定规划问题的研究主要集中于单个Agent,而对多Agent规划的研究则侧重于确定规划。针对该问题,提出基于多Agent的带权值不确定规划问题,对所求解的强规划解,设计使其所需动作权值总和近似最小的算法。根据基于模型检测的强规划分层方法,对每个Agent进行强规划分层,合并所有Agent的分层信息,并在合并的过程中得到同层状态之间的冲突表。在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。实验结果表明,该算法能较快地求解出使所选择的动作权值总和近似最小的强规划解。     

智能规划中基于遗传算法的动作模型学习

在动作间的状态未知条件下,利用遗传算法,从不完整的领域描述和规划实例中学习动作模型,并且设计了AMLS-GA(Action Model Learning System Based on Genetic Algorithm)系统来具体实现这一思想.作者为每一个动作构建一个可能谓词集,这个谓词集覆盖了动作前提表、增加表和删除表中的所有谓词.采用二进制编码的方式,把动作模型编码成GA搜索空间中的一个假设,学习过程是在标准的遗传算法框架下进行的.把学习结果的正确性定义为尽可能多的解释规划实例,并且通过实验的方法对比学习到的模型与专家预定义模型之间的差别.实验结果表明,算法能在较短的时间内,学习到一个逼近专家描述的动作模型.     

基于时间约束网络的智能活动规划

老年人认知能力的下降导致其无法正常规划日常生活的问题已经越来越受到社会的关注。利用信息技术辅助老年人独立完成日常活动,已成为目前一个新的研究领域,其中对其活动的规划和提醒是该领域的一个研究热点。在传统基于时间的活动约束表示和冲突检测的基础上,提出一种更为宽松合理的时间约束,其使活动时间更为灵活,同时引入活动规划中新的活动时间冲突问题。通过时间约束网络的相关概念和理论,将活动规划中冲突检测问题转化为简单时间约束网络是否满足一致性的问题。给出时间约束一致性的一般性检测算法,分析得出活动数较大时其算法复杂度呈指数增长。针对一般性检测算法,提出新的检测时间约束一致性的算法,以降低算法复杂度,解决活动规划中的时间冲突问题。最后通过实验对两种算法的时间复杂度进行了比较。     

基于规划图的蚁群规划算法

图规划是智能规划领域近年来出现的一种重要规划方法,对智能规划的发展起到了很重要的推动作用,图规划算法首先扩展生成规划图,然后通过逐层组合不断回溯的穷举方式进行解提取,这种方式使解提取不仅耗时而且容易陷入局部搜索中.在规划图基础上定义了蚁群智能体,并定义了在规划图上的蚁群搜索方式,提出了蚁群规划算法,使搜索具有较好的全局性和并发性,并具备加速收敛的寻解能力.实验表明,蚁群规划算法在求解一些相对规模较大的规划问题时有更好的优越性.     

模型检测规划中的状态分层方法

基于模型检测的规划方法是最近发展起来的新方法,它可以处理带有不确定性的规划问题.分别设计了对求弱规划解、强规划解和强循环规划解的问题中的状态进行分层的方法.状态被分层后,求规划解只需要在从上层到其下一层状态之间寻找状态动作序偶就可以了,其他状态动作序偶都可以去掉.分别获得了求弱规划解、强规划解和强循环规划解时状态被分层后的一些重要性质,这些性质是关于一些状态动作序偶是否可以不参与构成弱规划解、强规划解和强循环规划解的结论.通过所获得的性质可以将大量的状态动作序偶直接去掉,从而减少问题规模.以往的对基于模型检测规划的研究都是采用从目标状态开始的反向搜索方法,在状态被分层以后可以采用正向搜索技术展开相应的研究.     

基于领域模型的网页搜索排序算法

通用搜索引擎在检索过程中会出现查询结果与关键词所属领域无关的主题漂移现象.本文提出了面向特定领域的网页重排序算法-TSRR(Topic Sensitive Re-Ranking)算法,从一个新的视角对主题漂移问题加以解决. TSRR算法设计一种独立于网页排序的模型,用来表示领域,然后建立网页信息模型,在用户检索过程中结合领域向量模型和网页信息模型对网页搜索结果进行重排序.在爬取的特定领域的数据集上,以用户满意度和准确率为标准进行评估,实验结果表明,本文中提出的TSRR算法性能优异,比经典的基于Lucene的排序算法在用户满意度上平均提高17.3%,在准确率上平均提高41.9%.     

基于领域特征的神经机器翻译领域适应方法

神经机器翻译在资源丰富领域上训练的翻译模型往往在其他资源稀缺领域中表现较差,领域适应是利用资源丰富的领域帮助资源稀少的领域提升翻译质量的一种方法。该文提出基于领域特征的领域适应方法以提升资源稀缺领域的神经机器翻译质量。具体而言,该文尝试构建领域敏感网络以获得领域特有特征,构建领域不敏感网络以获得领域间的共有特征。一个领域判别器被用于区分领域。该文通过训练领域敏感网络使得该领域判别器更易做出准确判断,同时引入对抗机制,使得领域不敏感网络欺骗该领域判别器。最后,提出一种系统集成机制,融合基准神经翻译网络、领域敏感网络、领域不敏感网络以完成神经机器翻译的领域适应。实验结果显示,该方法在中英广播对话领域上和英德口语领域上的翻译效果均有显著提升。     

基于领域知识的图模型词义消歧方法

对领域知识挖掘利用的充分与否,直接影响到面向特定领域的词义消歧(Word sense disambiguation, WSD)的性能.本文提出一种基于领域知识的图模型词义消歧方法,该方法充分挖掘领域知识,为目标领域收集文本领域关联词作为文本领域知识,为目标歧义词的各个词义获取词义领域标注作为词义领域知识;利用文本领域关联词和句子上下文词构建消歧图,并根据词义领域知识对消歧图进行调整;使用改进的图评分方法对消歧图的各个词义结点的重要度进行评分,选择正确的词义.该方法能有效地将领域知识整合到图模型中,在Koeling数据集上,取得了同类研究的最佳消歧效果.本文亦对多种图模型评分方法做了改进,进行了详细的对比实验研究.