Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Satisfaction Problems

约束满足问题在人工智能领域有着广泛的应用.研究了约束满足问题的粗粒度维持弧相容求解算法,发现在求解过程中,对于指向已赋值变量的弧存在无效的修正检查,证明了这类修正检查是冗余的.提出一种方法避免这类冗余的修正检查,给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR,该改进框架可用于改进所有粗粒度弧相容算法.实验结果表明,经过AC3 frame ARR改进后的算法最多可以节省80％的修正检查次数和40％的求解耗时.     

基于启发式的约束满足问题AC系列算法改进研究

约束满足问题是人工智能领域中一个重要的研究方向,其研究结果在符号推理、系统诊断、真值维护系统、资源分配和产品配置等问题中有广泛的应用。局部相容性定义了约束满足问题在约束传播过程中必须满足的性质,是约束传播发展的主要方向。而对于较为复杂的相容性问题中的AC系列算法的改进可谓难上之难。本文围绕着以弧相容、Singleton弧相容为代表的相容性技术和求解算法展开,主要针对AC-2001算法、SAC算法等进行优化改进,重点基于启发式进行改进,使之获得了更快的筛选速度。尤其对于SAC算法,大大减少了约束检查次数,获得了较为成功的基于启发式的改进结果。     

最大受限路径相容约束传播算法的研究进展

约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。     

最先失败原则的约束传播算法

约束满足问题是人工智能研究领域的重要问题.而弧相容算法是求解约束满足问题的重要工具.在弧相容算法中应用启发式规则已经证明是一种很有效的方式.本文提出一个基于最先失败原则的约束传播算法,该算法在搜索过程中更早地发现含有空域的变量并提前进行回溯,从而提高问题求解效率.同时,在"明月1.0"架构下实现了该算法,实验结果表明使用最先失败原则的弧相容算法要比原来的算法效率上提高了约40%.     

负表约束的简单表缩减广泛弧相容算法

广泛弧相容算法（generalized arc consistency,简称GAC）,是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势.     

基于关联约束非二元弧一致性的约束满足问题求解

弧一致性算法在二元约束满足问题中取得了成功的应用,但并不能被有效泛化至预处理非二元约束满足问题(NCSP).本文提出了处理NCSP的关联约束非二元弧一致性算法.通过随机NCSP生成器产生问题实例,分别采用关联约束非二元弧一致性算法和非二元弧一致性算法进行预处理,并对预处理后的问题实例应用回溯算法进行求解.对比分析采用两种预处理算法和不采用预处理下回溯算法的求解性能,仿真实验结果表明关联约束非二元弧一致性算法可以有效地剔除冗余的约束元组和变量域值,使关联约束非二元弧一致性回溯算法具有更良好的鲁棒性.     

概率最大受限路径相容算法

研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.     

一种基于预处理技术的约束满足问题求解算法

相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT MPAC和BT MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2~50倍.     

一种基于环切割的约束满足问题求解算法

该文首先给出一种无环约束满足问题的无回溯搜索算法Tree_Search,然后将环切割思想嵌入到目前最流行的MAC3rm算法中,给出一种新算法CCS.CCS将原同溯搜索过程分为两部分:第1部分通过回溯搜索求解环切割集中变量,将原问题化简成一个满足弧相容的无环问题；第2部分通过无回溯的Tree_Search算法求解化简后的...     

一种维持约束网络相容性的双向传播策略

约束满足问题是经典NP-hard问题,其基本算法是递归形式的回溯算法和弧一致性算法.将弧相容与回溯搜索结合,可以有效降低解空间大小.针对弧相容的维持问题,提出一种新的基于时序计数的传播方案,用于增量更新约束子网.将accumulateRevision和pushRevison作为双向修订的主要方法,以减少修订次数和域过滤变量的数量.实验结果表明,与经典的基于关系的方案和基于变量的传播方案相比,该方案的整体求解速度明显提高,且具有较少的修订时间.     

An optimal coarse-grained arc consistency algorithm

The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints.     

Constraint satisfaction algorithms1

Constraint satisfaction problems are ubiquitous in artificial intelligence and many algorithms have been developed for their solution. This paper provides a unified survey of some of these, in terms of three classes: (i) tree search, (ii) arc consistency (AC), and (iii) hybrid tree search/arc consistency algorithms. It is shown that several important algorithms, when slightly rearranged, are of the latter hybrid form, but with arc consistency components that do not necessarily achieve full arc consistency at the tree nodes. Accordingly, we define several new partial AC procedures, AC1/5, AC1/4, AC1/3, and AC½, analogous to the well-known full AC algorithms which Mackworth has called AC1, AC2, and AC3. The fractional suffixes on our AC algorithms are roughly proportional to the degree of partial arc consistency they achieve. Unlike traditional versions, our AC algorithms (full and partial) are presented in a parameterized form to allow them to be embedded efficiently at the nodes of a tree search process. Algorithm complexities are compared empirically, using the n-queens problem and a new version called confused n-queens. Gaschnig's Backmarking (a tree search algorithm) and Haralick's Forward Checking (a hybrid algorithm) are found to be the most efficient. For the hybrid algorithms, we find that it pays to do little arc consistency processing at the nodes, incurring more nodes, but sufficiently reducing the work per node so as to obtain less work over the whole tree. The unified view taken here suggests several new algorithms. Preliminary results show one of these to be the best algorithm so far.     

深度时空能量特征表示下的人体行为识别

目的 利用深度图序列进行人体行为识别是机器视觉和人工智能中的一个重要研究领域,现有研究中存在深度图序列冗余信息过多以及生成的特征图中时序信息缺失等问题。针对深度图序列中冗余信息过多的问题,提出一种关键帧算法,该算法提高了人体行为识别算法的运算效率;针对时序信息缺失的问题,提出了一种新的深度图序列特征表示方法,即深度时空能量图（depth spatial-temporal energy map,DSTEM）,该算法突出了人体行为特征的时序性。方法 关键帧算法根据差分图像序列的冗余系数剔除深度图序列的冗余帧,得到足以表述人体行为的关键帧序列。DSTEM算法根据人体外形及运动特点建立能量场,获得人体能量信息,再将能量信息投影到3个正交轴获得DSTEM。结果 在MSR_Action3D数据集上的实验结果表明,关键帧算法减少冗余量,各算法在关键帧算法处理后运算效率提高了20% 30%。对DSTEM提取的方向梯度直方图（histogram of oriented gradient,HOG）特征,不仅在只有正序行为的数据库上识别准确率达到95.54%,而且在同时具有正序和反序行为的数据库上也能保持82.14%的识别准确率。结论 关键帧算法减少了深度图序列中的冗余信息,提高了特征图提取速率;DSTEM不仅保留了经过能量场突出的人体行为的空间信息,而且完整地记录了人体行为的时序信息,在带有时序信息的行为数据上依然保持较高的识别准确率。     

基于改进分块颜色特征和二次提取的关键帧提取算法

关键帧提取技术是视频摘要、检索、浏览和理解中的一项重要技术。目前关键帧提取算法存在一些问题,例如特征选择复杂、阈值选择难、自适应性不强等。为了更有效地提取视频关键帧,提出了一种基于改进分块颜色特征和二次提取的关键帧提取算法。首先,对视频帧进行等面积矩形环划分;其次,提取矩形环的HSV量化颜色特征,并由帧图像中心到外依次减小每个矩形环特征的权值以突出图像主体部分;然后,依据相邻视频帧间特征的显著性变化初步选取关键帧;最后,依据初次提取的关键帧在视频中的位置间隔大小进行二次提取优化关键帧。实验结果表明,该方法具有良好的适应性,同时能够有效避免因镜头有突然闪光或物体快速运动而提取过多的关键帧,最终提取的关键帧能够比较全面准确地表达视频内容。     

改进RetinaNet的轻量化工件检测算法研究

针对传统目标检测模型参数量巨大,制约算法部署与模型推理实时性的问题,提出一种基于改进RetinaNet检测模型的轻量化实时目标检测网络。使用MobileNet-V2代替RetinaNet模型中的ResNet骨干网络,降低整体模型的参数量;设计锚框引导采样机制,基于特征金字塔输出特征层生成感兴趣区域掩码,减少背景区域冗余锚框,降低后处理过程中的计算复杂度;引入GFocalLossV2损失函数统计预测边框分布特征,优化预测边框质量以及提升分类准确度。该模型在自制多类别工件数据集WP和Pascal VOC公开数据集上进行验证实验,改进模型的检测准确率分别达到99.5%、80.5%,检测速度分别达到39.8 FPS、38.3 FPS。实验结果表明,该轻量级目标检测模型能够实现实时检测,同时保证了检测精度。     

提升预测框定位稳定性的视频目标检测

目的 目前视频目标检测（object detection from video）领域大量研究集中在提升预测框定位准确性,对于定位稳定性提升的研究则较少。然而,预测框定位稳定性对多目标跟踪、车辆行驶控制等算法具有重要影响,为提高预测框定位稳定性,本文提出了一种扩张性非极大值抑制（expanded non-maximum suppression,Exp_NMS）方法和帧间平滑策略（frame bounding box smooth,FBBS）。方法 目标检测阶段使用YOLO（you only look once）v3神经网络,非极大值抑制阶段通过融合多个预测框信息得出结果,增强预测框在连续视频流中的稳定性。后续利用视频相邻帧信息关联的特点,对预测框进行平滑处理,进一步提高预测框定位稳定性。结果 选用UA-DETRAC（University at Albany detection and tracking benchmark dataset）数据集进行分析实验,使用卡尔曼滤波多目标跟踪算法进行辅助验证。本文在MOT（multiple object tracking）评价指标基础上,设计了平均轨迹曲折度（average track-tortuosity,AT）来直观、量化地衡量预测框定位稳定性及跟踪轨迹的平滑度。实验结果表明,本文方法几乎不影响预测框定位准确性,且对定位稳定性有大幅改善,相应跟踪质量得到显著提升。测试视频的MOTA（multiple object tracking accuracy）提升6.0%、IDs（identity switches）减少16.8%,跟踪FP（false positives）类型错误下降45.83%,AT下降36.57%,mAP（mean average precision）仅下降0.07%。结论 从非极大值抑制和前后帧信息关联两个角度设计相关策略,经实验验证,本文方法在基本不影响预测框定位准确性的前提下,可有效提升预测框定位稳定性。     

A formal modeling and analysis approach for access control rules,policies, and their combinations

Approaches to access control (AC) policy languages, such as eXtensible access control markup language, do not provide a formal representation for specifying rule- and policy-combining algorithms or for verifying properties of AC policies. Some authors propose formal representations for these combining algorithms. However, the proposed models are not expressive enough to represent formally history-based classes of these algorithms, such as ordered-permit-overrides. In addition, some other authors propose a formal representation but do not present automated support for formal verification of properties of AC policies that use these algorithms. This paper demonstrates a new representation that can express all existing AC rule and policy combinations of which the authors are aware. This representation can also be used to automate the formal verification of properties of AC policies related to these algorithms. A new modeling representation for rule- and policy-combining algorithms based on state machines is used to specify rule- and policy-combining algorithms. Examples of these algorithms are programmed in the language of the SPIN model checker, and the programs are then used to support the automated formal verification of properties of AC policies. We present our approach and then use the AC policies and properties of CONTINUE, a conference management system, to compare it with prior work. Our first contribution is a new modeling representation for combining algorithms based on state machines. The second contribution is the formal verification of AC properties under certain combining algorithms that are beyond the capability of other approaches.     

入侵检测多模式匹配算法

基于模式匹配的入侵检测是目前最重要的一种入侵检测方法,面字符串匹配效率是该方法的核心,直接影响检测效率。该文在充分分析BM算法、AC算法及AC_BM算法的基础上提出了一种新的更好搜索步长的多模式匹配算法NMSA,并具体分析了该算法的效率,通过实验数据对比,再次证明NMSA算法具有更好的搜索步长、更好的效率。     

基于冗余代码的控制流混淆算法

目前的平展控制流主要是结合不透明谓词使用,例如混沌映射和同余方程算法。这些算法会引起大量额外开销。此外,这种结合不透明谓词的平展控制流混淆方法难抵御动态逆向攻击。针对这些问题,提出了在插入与原基本块结构类似、但数据随机生成且与原基本块不同的冗余块,使攻击者难以区分实际执行基本块的基础上,对实际执行基本块和冗余块进行控制流平展化处理,进一步混淆控制流结构。此外,构建分支函数动态赋值算法,对分支变量进行强化,提高混淆弹性。该控制流混淆算法在mbed TLS程序测试集上进行控制流、逆向工程和性能测试与分析,测试与分析结果表明该混淆算法不仅能大大提高混淆强度,还能有效保护程序控制流信息,抵抗动静态逆向分析。