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.     

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.     

Don’t care in SMT: building flexible yet efficient abstraction/refinement solvers

This paper describes a method for combining “off-the-shelf” SAT and constraint solvers for building an efficient Satisfiability Modulo Theories (SMT) solver for a wide range of theories. Our method follows the abstraction/refinement approach to simplify the implementation of custom SMT solvers. The expected performance penalty by not using an interweaved combination of SAT and theory solvers is reduced by generalising a Boolean solution of an SMT problem first via assigning don’t care to as many variables as possible. We then use the generalised solution to determine a thereby smaller constraint set to be handed over to the constraint solver for a background theory. We show that for many benchmarks and real-world problems, this optimisation results in considerably smaller and less complex constraint problems. The presented approach is particularly useful for assembling a practically viable SMT solver quickly, when neither a suitable SMT solver nor a corresponding incremental theory solver is available. We have implemented our approach in the ABsolver framework and applied the resulting solver successfully to an industrial case-study: the verification problems arising in verifying an electronic car steering control system impose non-linear arithmetic constraints, which do not fall into the domain of any other available solver.     

Generating customized yet factually consistent information: a constraint satisfaction approach

We present an information customization framework that leverages a hybrid of adaptive hypermedia and intelligent techniques, in particular constraint satisfaction methods, to generate customized and factually consistent information based on a user profile. Information customization is modeled as a constraint satisfaction problem, whereby a solution is derived by (a) satisfying user-model constraints to select a user-specific set of ‘information snippets’; and (b) establishing inter-snippet consistency to ensure that all snippets are compatible with each other. Our approach takes the unique step of establishing factually consistency – via the satisfaction of inter-snippet constraints – between heterogeneous information snippets. A customized information package is generated by systematically synthesizing the set of user-specific and factually consistent information snippets. The featured information customization framework incorporates variations of various search and constraint satisfaction methods. The work is applied in an E-Healthcare setting leading to the generation of customized healthcare information.     

Conjecture Synthesis for Inductive Theories

We have developed a program for inductive theory formation, called IsaCoSy, which synthesises conjectures ‘bottom-up’ from the available constants and free variables. The synthesis process is made tractable by only generating irreducible terms, which are then filtered through counter-example checking and passed to the automatic inductive prover IsaPlanner. The main technical contribution is the presentation of a constraint mechanism for synthesis. As theorems are discovered, this generates additional constraints on the synthesis process. We evaluate IsaCoSy as a tool for automatically generating the background theories one would expect in a mature proof assistant, such as the Isabelle system. The results show that IsaCoSy produces most, and sometimes all, of the theorems in the Isabelle libraries. The number of additional un-interesting theorems are small enough to be easily pruned by hand.     

Integrating Standard Dependency Schemes in QCSP Solvers

Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers.In this paper we apply variab...     

A pseudo-sensitivity based discrete-variable approach to structural topology optimization with multiple materials

An algorithm has been developed which uses material as a discrete variable in multi-material topology optimization and thus provides an alternative to traditional methods using material interpolation and level-set approaches. The algorithm computes ‘pseudo-sensitivities’ of the objective and constraint functions to discrete material changes. These are used to rank elements, based on which a fraction of elements are selected for material ID modification during the optimization iteration. The algorithm is of general applicability and avoids frequent matrix factorizations so that it is applicable to large structural problems. In addition to the conventionally used evolutionary and morphogenesis approaches for iteration, a new iteration scheme of ‘resubstitution’ which combines the two approaches is presented. The application and functioning of the algorithm is demonstrated through case studies and comparisons with a few benchmark problems, showing its capability in providing mass-optimal topologies under stiffness constraints for various structural problems where multiple materials are considered.     

A methodology for design and analysis of cooperative behaviors with mobile robots

New methodologies are needed for modeling of physically cooperating mobile robots to be able to systematically design and analyze such systems. In this context, we present a method called the ‘P-robot Method’ under which we introduce entities called the p-robots at the environmental contact points and treat the linked mobile robots as a multiple degree-of-freedom object, comprising an articulated open kinematic chain, which is manipulated by the p-robots. The method is suitable to address three critical aspects of physical cooperation: a) analysis of environmental contacts, b) utilization of redundancy, and c) exploitation of system dynamics. Dynamics of the open chain are computed independent of the constraints, thus allowing the same set of equations to be used as the constraint conditions change, and simplifying the addition of multiple robots to the chain. The decoupling achieved through constraining the p-robots facilitates the analysis of kinematic as well as force constraints. We introduce the idea of a ‘tipping cone’, similar to a standard friction cone, to test whether forces on the robots cause undesired tipping. We have employed the P-robot Method for the static as well as dynamic analysis for a cooperative behavior involving two robots. The method is generalizable to analyze cooperative behaviors with any number of robots. We demonstrate that redundant actuation achieved by an adding a third robot to cooperation can help in satisfying the contact constraints. The P-robot Method can be useful to analyze other interesting multi-body robotic systems as well.     

An application of fuzzy set theory to the external performance evaluation of distribution centers in logistics

 The purpose of this paper is to propose an algorithm for external performance evaluation in the area of logistics from retailers' viewpoint under fuzzy environment. The fundamental concepts we have adopted include the factor analysis, eigenvector method, fuzzy Delphi method, fuzzy set theory and multi-criteria decision-making method. We use factor analysis to condense twenty external performance sub-criteria into six criteria to construct the hierarchical structure of external performance evaluation of distribution centers. The fuzzy Delphi method is integrated with the eigenvector method to form a set of pooled weights of the extracted criteria. The concepts of triangular fuzzy number and linguistic variables are used to assess the preference ratings of linguistic variable, ‘importance’ and ‘appropriateness’. Through the hierarchy integration, we obtain the final scores of distribution centers' performance. Then we use a revised Chang and Chen's ranking method to rank the final scores of distribution centers for choosing the best distribution center in the area of logistic management.     

The octagon abstract domain

This article presents the octagon abstract domain, a relational numerical abstract domain for static analysis by abstract interpretation. It allows representing conjunctions of constraints of the form ± X ± Y ≤ c where X and Y range among program variables and c is a constant in ℤ, ℚ, or ℝ automatically inferred. Abstract elements are represented using modified Difference Bound Matrices and we use a normalization algorithm loosely based on the shortest-path closure to compute canonical representations and construct best-precision abstract transfer functions. We achieve a quadratic memory cost per abstract element and a cubic worst-case time cost per abstract operation, with respect to the number of program variables. In terms of cost and precision, our domain is in between the well-known fast but imprecise interval domain and the costly polyhedron domain. We show that it is precise enough to treat interesting examples requiring relational invariants, and hence, out of the reach of the interval domain. We also present a packing strategy that allows scaling our domain up to large programs by tuning the amount of relationality. The octagon domain was incorporated into the ASTRéE industrial-strength static analyzer and was key in proving the absence of run-time errors in large critical embedded flight control software for Airbus planes. This paper is the journal version of an earlier conference paper [44] sharing this title. However, the present version, extracted from the author’s PhD [46] is extended in many ways and enriched with new experimental results. Partially supported by the exploratory project ASTRéE of the Réseau National de recherche et d’innovation en Technologies Logicielles (RNTL).     

Special factors,periodicity, and an application to Sturmian words

Let w be a finite word and n the least non-negative integer such that w has no right special factor of length and its right factor of length n is unrepeated. We prove that if all the factors of another word v up to the length n + 1 are also factors of w, thenv itself is a factor ofw. A similar result for ultimately periodic infinite words is established. As a consequence, some ‘uniqueness conditions’ for ultimately periodic words are obtained as well as an upper bound for the rational exponents of the factors of uniformly recurrent non-periodic infinite words. A general formula is derived for the ‘critical exponent’ of a power-free Sturmian word. In particular, we effectively compute the ‘critical exponent’ of any Sturmian sequence whose slope has a periodic development in a continued fraction. Received: 6 May 1999 / 21 February 2000     

A full first-order constraint solver for decomposable theories

Over the last decade, first-order constraints have been efficiently used in the artificial intelligence world to model many kinds of complex problems such as: scheduling, resource allocation, computer graphics and bio-informatics. Recently, a new property called decomposability has been introduced and many first-order theories have been proved to be decomposable: finite or infinite trees, rational and real numbers, linear dense order,...etc. A decision procedure in the form of five rewriting rules has also been developed. This latter can decide if a first-order formula without free variables is true or not in any decomposable theory. Unfortunately, this decision procedure is not enough when we want to express the solutions of a first-order constraint having free variables. These kind of problems are generally known as first-order constraint satisfaction problems. We present in this paper, not only a decision procedure but a full first-order constraint solver for decomposable theories. Our solver is given in the form of nine rewriting rules which transform any first-order constraint ϕ (which can possibly contain free variables) into an equivalent formula φ which is either the formula true, or the formula false or a simple solved formula having at least one free variable and being equivalent neither to true nor to false. We show the efficiency of our solver by solving complex first-order constraints over finite or infinite trees containing a huge number of imbricated quantifiers and negations and compare the performances with those obtained using the most recent and efficient dedicated solver for finite or infinite trees. This is the first full first-order constraint solver for any decomposable theory.     

Scope control and grammatical dependencies

This paper develops a semantics with control over scope relations using Vermeulen’s stack valued assignments as information states. This makes available a limited form of scope reuse and name switching. The goal is to have a general system that fixes available scoping effects to those that are characteristic of natural language. The resulting system is called Scope Control Theory, since it provides a theory about what scope has to be like in natural language. The theory is shown to replicate a wide range of grammatical dependencies, including options for, and constraints on, ‘donkey’, ‘binding’, ‘movement’, ‘Control’ and ‘scope marking’ dependencies.     

Random Constraint Satisfaction: Flaws and Structure

A recent theoretical result by Achlioptas et al. shows that many models of random binary constraint satisfaction problems become trivially insoluble as problem size increases. This insolubility is partly due to the presence of flawed variables, variables whose values are all flawed (or unsupported). In this paper, we analyse how seriously existing work has been affected. We survey the literature to identify experimental studies that use models and parameters that may have been affected by flaws. We then estimate theoretically and measure experimentally the size at which flawed variables can be expected to occur. To eliminate flawed values and variables in the models currently used, we introduce a flawless generator which puts a limited amount of structure into the conflict matrix. We prove that such flawless problems are not trivially insoluble for constraint tightnesses up to 1/2. We also prove that the standard models B and C do not suffer from flaws when the constraint tightness is less than the reciprocal of domain size. We consider introducing types of structure into the constraint graph which are rare in random graphs and present experimental results with such structured graphs.     

Tableaux-based optimization of schema mappings for data integration

The task of combining data residing at different sources to provide the user a unified view is known as data integration. Schema mappings act as glue between the global schema and the source schemas of a data integration system. Global-and-local-as-view (GLAV) is one the approaches for specifying the schema mappings. Tableaux are used for expressing queries and functional dependencies on a single database. We investigate a general technique for expressing a GLAV mapping by a tabular structure called mapping assertion tableaux (MAT). In a similar way, we also express the tuple generating dependency (tgd) and equality generating dependency (egd) constraints by tabular forms, called tabular tgd (TTGD) and tabular egd (TEGD), respectively. A set consisting of the MATs, TTGDs and TEGDs are called schema mapping tableaux (SMT). We present algorithms that use SMT as operator on an instance of the source schema to produce an instance of the target schema. We show that the target instances computed by the SMT are ‘minimal’ and ‘most general’ in nature. We also define the notion of equivalence between the schema mappings of two data integration systems and present algorithms that optimize schema mappings through the manipulation of the SMT.     

A Temporal Logic for Supporting Historical Databases

Tackling data with gap-interval time is an important issue faced by the temporal database community. While a number of interval logics have been developed, less work has been reported on gap-interval time. To represent and handle data with time, a clause ‘when’ is generally added into each conventional operator so as to incorporate time dimension in temporal databases, which clause ‘when’ is really a temporal logical sentence. Unfortunately, though several temporal database models have dealt with data with gap-interval time, they still put interval calculus methods on gap-intervals. Certainly, it is inadequate to tackle data with gap-interval time using interval calculus methods in historical databases. Consequently, what temporal expressions are valid in the clause ‘when’ for tackling data with gap-interval time? Further, what temporal operations and relations can be used in the clause ‘when’? To solve these problems, a formal tool for supporting data with gap-interval time must be explored. For this reason, a gap-interval-based logic for historical databases is established in this paper. In particular, we discuss how to determine the temporal relationships after an event explodes. This can be used to describe the temporal forms of tuples splitting in historical databases. Received 2 February 1999 / Revised 9 May 1999 / Accepted in revised form 20 November 1999     

Spanning trees and shortest paths in monge graphs

We investigate three problems onMonge graphs, i.e. complete, undirected weighted graphs whose distance matrix is a Monge matrix: (A) the minimum spanning tree problem, (B) the problem of computing all-pairs shortest paths and (C) the problem of determining a minimum weighted 1-to-all shortest path tree. For all three problems best possible algorithms (in terms of complexity) are presented. This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’/Projektbereich Diskrete Optimierung.     

Scenario Development and Practical Decision Making under Uncertainty: Application to Requirements Engineering

In this paper, we address the question of how flesh and blood decision makers manage the combinatorial explosion in scenario development for decision making under uncertainty. The first assumption is that the decision makers try to undertake ‘robust’ actions. For the decision maker a robust action is an action that has sufficiently good results whatever the events are. We examine the psychological as well as the theoretical problems raised by the notion of robustness. Finally, we address the false feeling of decision makers who talk of ‘risk control’. We argue that ‘risk control’ results from the thinking that one can postpone action after nature moves. This ‘action postponement’ amounts to changing look-ahead reasoning into diagnosis. We illustrate these ideas in the framework of software development and examine some possible implications for requirements analysis.     

What the <0.70, 1.17, 0.99, 1.07> is a Symbol?

The notion of a ‘symbol’ plays an important role in the disciplines of Philosophy, Psychology, Computer Science, and Cognitive Science. However, there is comparatively little agreement on how this notion is to be understood, either between disciplines, or even within particular disciplines. This paper does not attempt to defend some putatively ‘correct’ version of the concept of a ‘symbol.’ Rather, some terminological conventions are suggested, some constraints are proposed and a taxonomy of the kinds of issue that give rise to disagreement is articulated. The goal here is to provide something like a ‘geography’ of the various notions of ‘symbol’ that have appeared in the various literatures, so as to highlight the key issues and to permit the focusing of attention upon the important dimensions. In particular, the relationship between ‘tokens’ and ‘symbols’ is addressed. The issue of designation is discussed in some detail. The distinction between simple and complex symbols is clarified and an apparently necessary condition for a system to be potentially symbol, or token bearing, is introduced.     

Study on IAC networks models: learning and stability

This paper presents a methodology that uses evolutionary learning in training ‘A’ model networks, a topology based on Interactive Activation and Competition (IAC) neural networks. IAC networks show local knowledge and processing units clustered in pools. The connections among units may assume only 1, 0 or −1. On the other hand, ‘A’ model network uses values in interval [−1, 1]. This feature provides a wider range of applications for this network, including problems which do not show mutually exclusive concepts. However, there is no algorithm to adjust the network weights and still preserve the desired characteristics of the original network. Accordingly, we propose the use of genetic algorithms in a new methodology to obtain the correct weight set for this network. Two examples are used to illustrate the proposed method. Findings are considered consistent and generic enough to allow further applications on similar classes of problems suitable for ‘A’ model IAC Networks.