时态规划中基于CSP技术的时态约束方法

在规划图框架下,定义了动作图,并进一步扩展为时态动作图,使之能体现处理具有时间资源约束的时态规划问题中的时态信息.在此基础上,提出一种对时态信息进行表示与管理并且能够进行时态约束推理的时态一致性赋值方法,利用约束可满足问题(CSP)技术对时序约束进行表示和处理,包括过滤、约减及时态信息的一致性检验,使时态推理技术能更好地应用于时态规划的求解过程中.最后,给出一个基于时态规划图的遗传规划算法GP-td,通过对国际智能规划大赛提供的Satellite规划领域问题进行实验.结果表明:该方法能够有效地提高大规模时态规划问题的求解效率和求解成功率.     

基于动态奖惩的CDCL SAT求解器分支启发式算法

分支启发式算法在CDCL SAT求解器中有着非常重要的作用,传统的分支启发式算法在计算变量活性得分时只考虑了冲突次数而并未考虑决策层和冲突决策层所带来的影响。为了提高SAT问题的求解效率,受EVSIDS和ACIDS的启发,提出了基于动态奖惩DRPB的分支启发式算法。每当冲突发生时,DRPB通过综合考虑冲突次数、决策层、冲突决策层和变量冲突频率来更新变量活性得分。用DRPB替代VSIDS算法改进了Glucose 3.0,并测试了SATLIB基准库、2015年和2016年SAT竞赛中的实例。实验结果表明,与传统、单一的奖励变量分支策略相比,所提分支策略可以通过减少搜索树的分支和布尔约束传播次数来减小搜索树的规模并提高SAT求解器的性能。     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

基于变量决策层的启发式变量选择策略

启发式分支策略是SAT求解器中不可或缺的一部分，直接影响求解器的效率。早期的启发式分支决策需要遍历整个子句数据库，效率比较低。随着独立变量状态衰减和（Variable State Independent Decaying Sum, VSIDS）分支策略的出现，SAT求解器的效率有所提高，但VSIDS策略以及它的延伸策略中变量的增量都只是与变量的冲突次数有关，没有考虑变量的决策层在分支策略中的影响。因此当发生冲突时，如果与冲突有关的变量的得分相同而决策层不同时，对于变量的选择就具有随机性。基于此，本文在阐述变量的决策层的重要性之后在VSIDS策略的基础上，提出一种基于变量决策层的启发式变量选择策略--HSVDL策略。然后通过实例显示HSVDL策略在变量决策阶段选择决策层低的变量的可能性比选择决策层高的变量的可能性要大，而且得分比较小，减少了内存的占用。最后通过实验表明HSVDL策略能够求解出更多的实例，求解器的效率也有所提高，说明该策略有一定的优势。     

基于加权平均值的一种分支启发式方法

在可满足性(Satisfiability,SAT)问题算法中提出有效的分支策略可以提高求解器的效率,文中主要从冲突分析的角度出发,依据变量是否发生冲突和冲突的次数,提出 一种基于加权平均值的分支启发式方法。该方法首先采用一组序列来记录变量是否参与冲突;其次赋予一个加权平均函数,依据变量的序列和决策层求出函数值;最后选择具有最大的函数值变量赋值,执行实例分析比较。由于该方法是对控制编码方法的改进,因此在进行例子分析时,采用了比较法和分析法,同时分析比较了所提方法、 SUM(Sum in experiment)策略和 ACIDS(Average Conflict-index Decision Score)策略。对SATLIB(SAT Little Information Bank)中的实例进行分析,结果表明所提方法能够实现更多子句被满足或最新冲突子句优先满足。     

结合启发式算子的单变量边缘分布算法求解SAT问题

单变量边缘分布算法(UMDA)是一种新的进化算法,是求解复杂问题的一种有效算法.根据SAT问题的特点,本文提出了一种求解SAT问题的改进单变量边缘分布算法(HeUMDASAT),该算法结合SAT问题本身固有的结构信息与当前群体的优秀解所提供的全局信息,构造了一个新的启发算子,并将此算子结合到单变量边缘分布算法中.此算子不同于随机搜索算子,由其产生的个体可以使得算法跳出局部最优并探索新的潜在区域,并且加快算法的收敛速度.用SATLIB库中的标准SAT问题对HeUMDASAT算法进行测试,实验结果表明该算法在求解速度和成功率方面都有明显的改善.     

时态变量"Now"语义及相应时态关系运算

讨论了时态变量"Now"的基本语义,即Now不仅可以表示当前时间,还能表示过去时间和将来时间.在语义分析的基础上,讨论了带变量时态关系运算中需要解决的基本问题,即变量Now值的确定问题,研究了相应时态关系数据操作,建立了带变量时态关系代数系统.     

E-CARGO模型在CSP问题中的描述

基于角色的协同RBC(Role-Based Collaboration)是一套研究角色及它们之间复杂关系的方法、理论和技术。在RBC中,群组角色分配GRA(Group Role Assignment)既是一个关键问题,也是一个难题。已有许多研究探讨了基于Q(Qualification)矩阵来处理GRA问题,但仅利用Q矩阵难以描述问题中的复杂约束关系。因此,将约束集(Constraint)引进E-CARGO模型,提出了带约束的EC-CARGO模型,研究了RBC、GRA、SAT(SATisfaction)和CSP(Constraint Satisfaction Problem)之间的联系,建立了RBC-GRA-SAT-CSP问题求解转换关系;提出应用EC-CARGO模型求解经典CSP约束满足问题的方法,进而描述了应用GRA求解CSP约束满足问题的通用框架。最后以N皇后问题为例,验证了通过GRA的约束指派求解CSP问题的有效性。     

采用二元CSP引擎求解RTL数据通路的可满足性

针对寄存器传输级(RTL)验证和测试过程中非常重要的数据通路可满足性求解问题,提出一种基于二元约束满足问题(CSP)的求解方法,包括数据通路提取、二元CSP建模和搜索求解3个步骤.数据通路提取通过对接口布尔变量和某些字变量赋值,为各个数据通路器件建立环境;二元CSP建模则根据该环境和各个数据通路器件的功能,将数据通路的可满足性问题转化为二元CSP描述;该二元CSP问题的描述被送入到二元CSP引擎,并采用冲突引导的回跳搜索策略进行求解,获得有解的例证或无解的判定.实验结果表明,即使在没有采取很多优化策略的条件下,该方法仍有较好的性能,并优于基于线性规划(LP)的求解方法.     

基于变量混合特征的分支启发式策略

先进的SAT求解器能够通过有效的分支启发式策略解决大型应用实例.目前VSIDS策略是最具有代表性的基于冲突分析的分支策略,它因其稳健性而被广泛使用,但在每次冲突分析中其判定变量活性的增量方式过于单一.针对此问题,本文提出了一种基于变量混合特征的分支启发式算法,目的是充分地利用参与冲突分析的变量所携带的不同信息特征来区分变量,来进一步指导变量活性增长.并将所提出的分支策略算法嵌入到Glucose4.1中形成求解器Glucose4.1+MFBS,通过对比测试,实验结果表明改进的分支算法比原本的VSIDS策略,具有一定的优势,求解明显个数增加.     

基于话语间时序多模态数据的情绪分析方法

长期以来,传统的基于单模态数据情绪分析方法存在分析角度单一、分类准确率低下等问题,时序多模态数据的分析方法为解决这些问题提供了可能.本文基于话语间的时序多模态数据,对现有的多模态情绪分析方法进行了改进,使用双向门控循环网络(Bi-GRU)结合模态内和跨模态的上下文注意力机制进行情绪分析,最后在MOSI和MOSEI数据集...     

A novel method for spatio-temporal pattern analysis of brain fMRI data

1 Introduction Functional magnetic resonance imaging (fMRI) is a non-invasive brain imaging technique which has been utilized in brain function researches since the early 1990s[1]. However, it is often difficult to do analysis in fMRI data because of the low signal to noise ratio (SNR) (about 2%—4% with 1.5T magnetic field strength) and the delay within the true neural activity and the stimuli-induced signal dynamic responses. The prevalent methods applied to fMRI data could be divided i…     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.     

基于频繁变化结构的时序XML文档聚类方法

为解决XML文档对动态性表示不足的问题,通过对XML文档加入时间信息进行建模,提出2种基于时间序列的XML文档频繁变化结构挖掘算法FCSBF和FCSDF,实现对动态XML文档频繁变化结构的高效挖掘。在此基础上提出一种针对动态XML文档的聚类新方法,实验结果证明,该方法能够对动态XML文档进行有效的聚类。     

时域候选优化的时序动作检测

目的 时序动作检测（temporal action detection）作为计算机视觉领域的一个热点课题,其目的是检测视频中动作发生的具体区间,并确定动作的类别。这一课题在现实生活中具有深远的实际意义。如何在长视频中快速定位且实现时序动作检测仍然面临挑战。为此,本文致力于定位并优化动作发生时域的候选集,提出了时域候选区域优化的时序动作检测方法TPO （temporal proposal optimization）。方法 采用卷积神经网络（convolutional neural network,CNN）和双向长短期记忆网络（bidirectional long short term memory,BLSTM）来捕捉视频的局部时序关联性和全局时序信息;并引入联级时序分类优化（connectionist temporal classification,CTC）方法,评估每个时序位置的边界概率和动作概率得分;最后,融合两者的概率得分曲线,优化时域候选区域候选并排序,最终实现时序上的动作检测。结果 在ActivityNet v1.3数据集上进行实验验证,TPO在各评价指标,如一定时域候选数量下的平均召回率AR@100（average recall@100）,曲线下的面积AUC （area under a curve）和平均均值平均精度mAP （mean average precision）上分别达到74.66、66.32、30.5,而各阈值下的均值平均精度mAP@IoU （mAP@intersection over union）在阈值为0.75和0.95时也分别达到了30.73和8.22,与SSN （structured segment network）、TCN （temporal context network）、Prop-SSAD （single shot action detector for proposal）、CTAP （complementary temporal action proposal）和BSN （boundary sensitive network）等方法相比,TPO的所有性能指标均有提高。结论 本文提出的模型兼顾了视频的全局时序信息和局部时序信息,使得预测的动作候选区域边界更为准确和灵活,同时也验证了候选区域的准确性能够有效提高时序动作检测的精确度。     

多时间粒度下时态函数依赖集的成员籍算法

为了有效地进行时态数据库设计,支持多时间粒度的时态函数依赖(TFDs)被用于时态模式的规范化。类似于传统的函数依赖(FDs),TFD集的成员籍问题是时态模式规范化所要解决的一个关键问题。由于多时间粒度的使用,使得有成员籍问题变得非常复杂。为了有效地解决此问题,分析了TFDs与FDs之间存在的联系和封闭时态类型集的特性,并且基于提出的有限导出时态类型集及其求解算法,提出一个有效地解决TFD集的成员籍问题的算法。     

时序行为提名的上下文信息融合方法

在针对视频的人体活动定位和识别领域中,现有的时序行为提名方法无法很好地解决行为特征长期依赖性而导致提名召回率较低.针对此问题,提出了一种上下文信息融合的时序行为提名方法.该方法首先采用三维卷积网络提取视频单元的时空特征,然后采用双向门控循环网络构建上下文关系预测出时序行为区间.针对门控循环单元(GRU)存在参数较多和梯...     

一个多时间粒度下时态函数依赖的有限属性闭包算法

为了有效地进行时态数据库设计,支持多时间粒度的时态函数依赖(TFDs)被用于时态模式的规范化．时态模式规范化所要解决的一个关键问题是求解时态函数依赖的有限属性闭包问题．由于多时间粒度的使用,使得有限属性闭包问题变得非常复杂．实际上,TFDs与传统的函数依赖(FDs)之间存在着密切的联系．通过分析这些联系和封闭时态类型集的特性,利用传统FDs的相关算法提出一个有效的求解有限属性闭包的算法．通过分析和与相关算法的实验比较,该算法更加有效．     

On the modelling and optimization of preferences in constraint-based temporal reasoning

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.