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

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

改进求解约束满足问题粗粒度弧相容算法

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

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

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

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

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

优化求解约束满足问题的MDDc和STR3算法

广义弧相容是求解约束满足问题应用最广泛的相容性,MDDc、STR2和STR3是表约束上维持广义弧相容应用较多的算法,其中MDDc基于对约束压缩表示的思想,将表约束表示成多元决策图,对各个元组之间存在较多交叠部分的约束具有很好的压缩效果;STR3同STR2一样基于动态维持有效元组的思想,当元组集规模缩减较慢时STR3维持广义弧相容的效率高于STR2.通过深入分析发现MDDc中查找节点的有效出边和STR3中检测并删除无效元组是耗时最多的操作.本文分别对MDDc和STR3提出一种自适应查找有效出边和检测删除无效元组的方法AdaptiveMDDc和AdaptiveSTR,对于同一操作,可以根据回溯搜索不同阶段的局势自适应地选择代价最小的实现方法,得益于较低的判断代价以及回溯搜索不同阶段采用不同方法的效率差异,AdaptiveMDDc和AdaptiveSTR相比原算法速度提升显著,其中AdaptiveSTR在一些问题上相比STR3提速三倍以上.     

异质信息网络的复杂条件社区搜索

社区是信息网络的重要属性, 社区搜索旨在寻找满足用户给定条件的节点集合, 是信息网络分析的重要研究内容. 异质信息网络由于包含更加全面、丰富的结构和语义信息, 所以异质信息网络的社区搜索近年来受到人们的广泛关注. 针对现有异质信息网络的社区搜索方法难以满足复杂条件社区搜索要求的不足, 定义了复杂条件社区搜索问题, 提出了考虑非对称元路径、受限元路径和禁止节点约束的搜索算法. 3种算法分别通过元路径补全策略、调整带标签的批量搜索策略和拆分复杂搜索条件的方式搜索社区, 同时针对禁止节点约束的搜索算法设计了基于剪枝策略和近似策略的优化算法以提高搜索效率. 在真实数据集上进行了大量实验, 实验结果证明了所提算法的有效性和高效性.     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

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

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

基于时间约束的配送网络可行路径算法研究

图论中的路径问题一般是求解最短路径问题。然而在军事物流配送过程中,由于网络中的边可能会失效,所以应求出所有满足需求点时间约束的路径。设计了求解满足时间约束的可行路径的算法,该算法可以避免重复边,及时排除超过时间约束的路径,并且能在有限的(n-1)步之内完成。     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.     

约束满足问题的局部一致性维护理论与方法

人工智能与计算机科学中的许多问题都可视为约束满足问题,为了简化问题的求解,常采用局部一致性方法减小搜索空间。本文首先介绍与分析了着眼于全局一致性的局部处理的理论与方法,以及尽可能消除回溯因素的局部一致性方法,最后给出了一种在减少局部一致性维护代价上优于已有方法的新算法。     

New algorithms for max restricted path consistency

Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that enforces a higher order of consistency than arc consistency. Despite the strong pruning that can be achieved, maxRPC is rarely used because existing maxRPC algorithms suffer from overheads and redundancies as they can repeatedly perform many constraint checks without triggering any value deletions. In this paper we propose and evaluate techniques that can boost the performance of maxRPC algorithms by eliminating many of these overheads and redundancies. These include the combined use of two data structures to avoid many redundant constraint checks, and the exploitation of residues to quickly verify the existence of supports. Based on these, we propose a number of closely related maxRPC algorithms. The first one, maxRPC3, has optimal O(end ³) time complexity, displays good performance when used stand-alone, but is expensive to apply during search. The second one, maxRPC3 ^rm , has O(en ² d ⁴) time complexity, but a restricted version with O(end ⁴) complexity can be very efficient when used during search. The other algorithms are simple modifications of maxRPC3 ^rm . All algorithms have O(ed) space complexity when used stand-alone. However, maxRPC3 has O(end) space complexity when used during search, while the others retain the O(ed) complexity. Experimental results demonstrate that the resulting methods constantly outperform previous algorithms for maxRPC, often by large margins, and constitute a viable alternative to arc consistency on some problem classes.     

基于循环寻优RRT算法的无人机航迹规划

针对快速扩展随机树（RRT）算法在无人机在线自主航迹规划中的寻优性问题,提出基于循环寻优RRT算法。将航迹长度代价约束作为启发条件引入RRT算法,可以有效地剪除搜索空间的无用节点,获得较优航迹。通过引入已规划可行航迹的航迹长度代价约束作为下一次算法运行的启发条件,采用循环迭代策略有效地剪除搜索空间的无用节点,使得算法每次运行后的航迹长度代价减小,多次运行后最终得到的航迹接近最优航迹,充分利用航迹长度代价的启发性,克服了RRT算法的缺点,同时获得了一系列不同航迹代价的可行备选航迹,在协同任务中可以根据协同到达时间进行快速选择。仿真结果表明该算法能够快速生成安全并且满足无人机动力学约束的较优航迹。     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Extending GENET with lazy arc consistency

Many important applications, such as graph coloring, scheduling and production planning, can be solved by GENET, a local search method which is used to solve binary constraint satisfaction problems (CSPs). Where complete search methods are typically augmented with consistency methods to reduce the search, local search methods are not. We propose a consistency technique, lazy arc consistency, which is suitable for use within GENET. We show it can improve the efficiency of the GENET search on some instances of binary CSPs, and does not suffer the overhead of full arc consistency     

Backtracking and random constraint satisfaction

The average running time used by backtracking on random constraint satisfaction problems is studied. This time is polynomial when the ratio of constraints to variables is large, and it is exponential when the ratio is small. When the number of variables goes to infinity, whether the average time is exponential or polynomial depends on the number of variables per constraint, the number of values per variable, and the probability that a random setting of variables satisfies a constraint. A method for computing the curve that separates polynomial from exponential time and several methods for approximating the curve are given. The version of backtracking studied finds all solutions to a problem, so the running time is exponential when the number of solutions per problem is exponential. For small values of the probability, the curve that separates exponential and polynomial average running time coincides with the curve that separates an exponential average number of solutions from a polynomial number. For larger probabilities the two curves diverge. Random problems similar to those that arise in understanding line drawings with shadows require a time that is mildly exponential when they are solved by simple backtracking. Slightly more sophisticated algorithms (such as constraint propagation combined with backtracking) should be able to solve these rapidly. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于结合空间拓扑和方向关系信息的空间推理

结合了定性空间推理中著名的区域连接演算（region connection calculus，RCC）和基于区域的方向关系演算（cardinal direction calculus，CDC），并且给出两个演算在两个方向上的交互表，即RCC8-To-CDC和CDC-To-RCC8．给出了结合RCC8和CDC知识的约束满足问题的路径一致算法（path consistency algorithm）（该算法是对Allen著名的路径一致算法的修改），并且采用两个队列实现了该算法，采用这种结构可以实现并行计算．在该算法中，基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性．算法的计算复杂性证明是多项式的，