A unified framework for consistency check

Constraint Satisfaction Problem (CSP) involves finding values for variables to satisfy a set of constraints. Consistency check is the key technique in solving this class of problems. Past research has developed many algorithms for such a purpose, e.g., node consistency, are consistency, generalized node and arc consistency, specific methods for checking specific constraints, etc. In this article, an attempt is made to unify these algorithms into a common framework. This framework consists of two parts. the first part is a generic consistency check algorithm, which allows and encourages each individual constraint to be checked by its specific consistency methods. Such an approach provides a direct way of practical implementation of the CSP model for real problem-solving. the second part is a general schema for describing the handling of each type of constraint. the schema characterizes various issues of constraint handling in constraint satisfaction, and provides a common language for expressing, discussing, and exchanging constraint handling techniques. © 1995 John Wiley & Sons, Inc.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

High-Order Consistency in Valued Constraint Satisfaction

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.     

Relatively quantified constraint satisfaction

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.     

New constraints on data-closeness and needle map consistency forshape-from-shading

This paper makes two contributions to the problem of needle-map recovery using shape-from-shading. First, we provide a geometric update procedure which allows the image irradiance equation to be satisfied as a hard constraint. This not only improves the data closeness of the recovered needle-map, but also removes the necessity for extensive parameter tuning. Second, we exploit the improved ease of control of the new shape-from-shading process to investigate various types of needle-map consistency constraint. The first set of constraints are based on needle-map smoothness. The second avenue of investigation is to use curvature information to impose topographic constraints. Third, we explore ways in which the needle-map is recovered so as to be consistent with the image gradient field. In each case we explore a variety of robust error measures and consistency weighting schemes that can be used to impose the desired constraints on the recovered needle-map. We provide an experimental assessment of the new shape-from-shading framework on both real world images and synthetic images with known ground truth surface normals. The main conclusion drawn from our analysis is that the data-closeness constraint improves the efficiency of shape-from-shading and that both the topographic and gradient consistency constraints improve the fidelity of the recovered needle-map     

New filtering algorithms for combinations of among constraints

Several combinatorial problems, such as car sequencing and rostering, feature sequence constraints, restricting the number of occurrences of certain values in every subsequence of a given length. We present three new filtering algorithms for the sequence constraint, including the first that establishes domain consistency in polynomial time. The filtering algorithms have complementary strengths: One borrows ideas from dynamic programming; another reformulates it as a regular constraint; the last is customized. The last two algorithms establish domain consistency, and the customized one does so in polynomial time. We provide experimental results that demonstrate the practical usefulness of each. We also show that the customized algorithm applies naturally to a generalized version of the sequence constraint that allows subsequences of varied lengths. The significant computational advantage of using a single generalized sequence constraint over a semantically equivalent collection of among or sequence constraints is demonstrated empirically.     

Redundant modeling in permutation weighted constraint satisfaction problems

In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose m\text -NC_{\text c}^*m\text {-NC}_{\text c}^* and m\text -AC_{\text c}^*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying 2\text -NC_{\text c}^*,  2\text -AC_{\text c}^*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.     

REASONING WITH TOPOLOGICAL AND DIRECTIONAL SPATIAL INFORMATION

Current research on qualitative spatial representation and reasoning mainly focuses on one single aspect of space. In real‐world applications, however, multiple spatial aspects are often involved simultaneously. This paper investigates problems arising in reasoning with combined topological and directional information. We use the RCC8 algebra and the rectangle algebra (RA) for expressing topological and directional information, respectively. We give examples to show that the bipath‐consistency algorithm Bipath‐Consistency is incomplete for solving even basic RCC8 and RA constraints. If topological constraints are taken from some maximal tractable subclasses of RCC8, and directional constraints are taken from a subalgebra, termed DIR49, of RA, then we show that Bipath‐Consistency is able to separate topological constraints from directional ones. This means, given a set of hybrid topological and directional constraints from the above subclasses of RCC8 and RA, we can transfer the joint satisfaction problem in polynomial time to two independent satisfaction problems in RCC8 and RA. For general RA constraints, we give a method to compute solutions that satisfy all topological constraints and approximately satisfy each RA constraint to any prescribed precision.     

Consistent specification of interface suites in UML

The paper motivates and describes a model oriented approach for consistent specification of interface suites in UML. An interface suite is a coherent collection of interfaces defining interactions that transcend component boundaries. The specification of interface suites contains diagrammatic views and documentation, but it is extended with templates for structured specifications deriving from the ISpec approach. To guarantee that the specification views, documentation and templates are consistent, a specification model has been constructed. The model contains both structural and behavioural information, represented in the form of sequences of carefully designed tuples. The model provides the underlying structure for the tool supporting the design process. The tool directs the designer to specify all elements of the model in a consistent way. The specification is collected both by customized specification templates and by diagrams. The documentation and the diagram elements – both derived from the template information – are automatically generated. This prevents errors and provides specification consistency. Initial submission: 15 February 2002 / Revised submission: 20 September 2002 Published online: 2 December 2002 RID="*" ID="*"Supported by PROGRESS grant EES.5141 and ITEA DESS grant IT990211.     

Fast algebraic methods for interval constraint problems

We describe an effective generic method for solving constraint problems, based on Tarski’s relation algebra, using path-consistency as a pruning technique. We investigate the performance of this method on interval constraint problems. Time performance is affected strongly by the path-consistency calculations, which involve the calculation of compositions of relations. We investigate various methods of tuning composition calculations, and also path-consistency computations. Space performance is affected by the branching factor during search. Reducing this branching factor depends on the existence of ‘nice’ subclasses of the constraint domain. Finally, we survey the statistics of consistency properties of interval constraint problems. Problems of up to 500 variables may be solved in expected cubic time. Evidence is presented that the ‘phase transition’ occurs in the range 6 ≤ n.c ≤15, where n is the number of variables, and c is the ratio of non-trivial constraints to possible constraints. This revised version was published online in June 2006 with corrections to the Cover Date.     

Designer’s preferences regarding equality constraints in robust design optimization

Robust design optimization (RDO) problems can generally be formulated by appropriately incorporating uncertainty into the corresponding deterministic optimization problems. Equality constraints in the deterministic problem need to be carefully formulated into the RDO problem because of the strictness associated with their feasibility. In this context, equality constraints have been generally classified into two types: (1) those that must be satisfied regardless of uncertainty, examples include physics-based constraints, such as F = ma, and (2) those that cannot be satisfied because of uncertainty, which are typically designer-imposed, such as dimensional constraints. This paper addresses the notion of preferred degree of satisfaction of deterministic equality constraints under uncertainty. Whether or not a particular equality constraint can be exactly satisfied depends on the statistical nature of the design variables that exist in the constraint and on the designer’s preferences. In this context, this paper puts forth three contributions. First, we develop a comprehensive classification of equality constraints in a way that is mutually exclusive and collectively exhaustive. Second, we present a rank-based matrix approach to interactively classify equality constraints, which systematically incorporates the designer’s preferences into the classification process. Third, we present an approach to incorporate the designer’s intra-constraint and inter-constraint preferences for designer-imposed constraints into the RDO formulation. Intra-constraint preference expresses how closely a designer wishes to satisfy a particular constraint; for example, in terms of its mean and standard deviation. A designer may express inter-constraint preference if satisfaction of a particular designer-imposed constraint is more important than that of another. We present an optimization formulation that incorporates the above discussed constraint preferences, which provides the designer with the means to explore design space possibilities. The formulation entails interesting implications in terms of decision making. Two engineering examples are provided to illustrate the practical usefulness of the developments proposed in this paper.     

Information assimilation framework for event detection in multimedia surveillance systems

Most multimedia surveillance and monitoring systems nowadays utilize multiple types of sensors to detect events of interest as and when they occur in the environment. However, due to the asynchrony among and diversity of sensors, information assimilation – how to combine the information obtained from asynchronous and multifarious sources is an important and challenging research problem. In this paper, we propose a framework for information assimilation that addresses the issues – “when”, “what” and “how” to assimilate the information obtained from different media sources in order to detect events in multimedia surveillance systems. The proposed framework adopts a hierarchical probabilistic assimilation approach to detect atomic and compound events. To detect an event, our framework uses not only the media streams available at the current instant but it also utilizes their two important properties – first, accumulated past history of whether they have been providing concurring or contradictory evidences, and – second, the system designer’s confidence in them. The experimental results show the utility of the proposed framework.     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

Localized event-based reasoning for multiagent domain1

This paper presents the GEM concurrency model and GEMPLAN, a multiagent planner based on this model. Unlike standard state-based AI representations, GEM is unique in its explicit emphasis on events and domain structure. In particular, a world domain is modeled as a set of regions composed of interrelated events. Event-based temporal-logic constraints are then associated with each region to delimit legal domain behavior. The GEMPLAN planner directly reflects this emphasis on domain structure and constraints. It can be viewed as a general-purpose constraint satisfaction facility which constructs a network of interrelated events (a “plan”) that is subdivided into regions (“subplans”), satisfies all applicable regional constraints, and also achieves some stated goal. GEMPLAN extends and generalizes previous planning architectures in the range of constraint forms it handles and in the flexibility of its constraint satisfaction search strategy. One critical aspect of our work has been an emphasis on localized reasoning—techniques that make explicit use of domain structure. For example, GEM localizes the applicability of domain constraints and imposes additional “locality constraints” on the basis of domain structure. Together, constraint localization and locality constraints provide semantic information that can be used to alleviate several aspects of the frame problem for multiagent domains. The GEMPLAN planner reflects the use of locality by subdividing its constraint satisfaction search space into regional planning search spaces. Utilizing constraint and property localization, GEMPLAN can pinpoint and rectify interactions among these regional search spaces, thus reducing the burden of “interaction analysis” ubiquitous to most planning systems. Because GEMPLAN is specifically geared towards parallel, multiagent domains, we believe that its natural application areas will include scheduling and other forms of organizational coordination.     

A business model for deploying Web services:A data-centric approach based on factual dependencies

The standards XML, SOAP, WSDL and UDDI allow (i) services to be accessed and executed via the Web; and (ii) a loose coupling of these services. Thanks to these standards, Web services technology is becoming not only a de facto integration standard, but also a de facto Internet standard instance of the SOA architecture. However, the deployment of such a technology is still hindered by some technical as well as methodological issues. This paper proposes a business model with multiple interfaced abstraction levels as a framework to methodologically deploy Web services technology with respect to SOA architecture. The attributes describing the business objects and coordination artifacts as described in the highest abstraction level of the business model, i.e. the universe of discourse, are aggregated according to a time/space constraint called factual dependency. Each aggregation of factually dependent attributes is validated with regard to an actual business event. The aggregation is then interfaced to lead to a well-specified Web service. The resulting comprehensive set of consistent Web services are then registered in a public or a private UDDI to be discovered and invoked by any business process. The proposed Web services generation process aims at unlocking and turning informational assets into actions. It differs from the current IT perspective approaches that generate Web services directly from redundant and inconsistent elements in the enterprise information systems.     

Periodic Constraint Satisfaction Problems: Tractable Subclasses

We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of generating constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints; the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.     

相接行凸约束网络的快速识别算法

约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n³d²),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.     

Reference,Synthesis and Constraint Satisfaction*

In this paper we discuss two kinds of constraint satisfaction problems that arise in the context of geometric modelling, In particular in the modification of 2-D wire-frame diagrams that are subject to an arbitrary number of geometrical and topological constraints. We argue that problems in this domain can be classified in two categories that we shall call problems of reference and problems of synthesis. Since Sutherland's Sketchpad program [16], a large number of systems have addressed constraint satisfaction in terms of the representation of constraints sets as equation systems, which in turn are solved by numerical methods like local propagation, relaxation and Gaussian elimination. Here, we present an alternative framework. We argue that conceptualising constraint satisfaction as symbolic rather than “numerical” problems helps to clarify the notion of “constraint”, simplify solution methods, and to explain the intuitive inferential processes underlying the modification of drawings in the course of interactive drafting sessions. The theory presented in this paper has been tested with an experimental computer program called Graflog [5, 8, 9, 10, 11, 12]. The program has been implemented during the last four years, and has evolved through several stages. The current version is implemented in terms of two Unix-processes connected by Unix-pipes. The first is a “C” program running X windows, and handles the external aspects of the interaction. The second is a Prolog program supporting the representational structures and interpreters of the system.