Search

In this paper we study a reactive extension of constraint logic programming (CLP). Our primary concerns are search problems in a dynamic environment, where interactions with the user (e.g. in interactive multi-criteria optimization problems) or interactions with the physical world (e.g. in time evolving problems) can be modeled and solved efficiently. Our approach is based on a complete set of query manipulation commands for both the addition and the deletion of constraints and atoms in the query. We define a fully incremental model of execution which, contrary to other proposals, retains as much information as possible from the last derivation preceding a query manipulation command. The completeness of the execution model is proved in a simple framework of transformations for CSLD derivations, and of constraint propagation seen as chaotic iteration of closure operators. A prototype implementation of this execution model is described and evaluated on two applications.

There are two well known transformations from non-binary constraints to binary constraints applicable to constraint satisfaction problems (CSPs) with finite domains: the dual transformation and the hidden (variable) transformation. We perform a detailed formal comparison of these two transformations. Our comparison focuses on two backtracking algorithms that maintain a local consistency property at each node in their search tree: the forward checking and maintaining arc consistency algorithms. We first compare local consistency techniques such as arc consistency in terms of their inferential power when they are applied to the original (non-binary) formulation and to each of its binary transformations. For example, we prove that enforcing arc consistency on the original formulation is equivalent to enforcing it on the hidden transformation. We then extend these results to the two backtracking algorithms. We are able to give either a theoretical bound on how much one formulation is better than another, or examples that show such a bound does not exist. For example, we prove that the performance of the forward checking algorithm applied to the hidden transformation of a problem is within a polynomial bound of the performance of the same algorithm applied to the dual transformation of the problem. Our results can be used to help decide if applying one of these transformations to all (or part) of a constraint satisfaction model would be beneficial.

Symmetry often appears in real-world constraint satisfaction problems, but strategies for exploiting it are only beginning to be developed. Here, a framework for exploiting symmetry within depth-first search is proposed, leading to two heuristics for variable selection and a domain pruning procedure. These strategies are then applied to two highly symmetric combinatorial problems, namely the Ramsey problem and the generation of balanced incomplete block designs. Experimental results show that these general-purpose strategies can compete with, and in some cases outperform, previous more ad hoc procedures.

Real-world autonomous systems are often controlled using conventional model-based control methods. But if accurate models of a system are not available, these methods may be unsuitable. For many safety-critical systems, such as robotic systems, a model of the system and a control strategy may be learned using data. When applying learning to safety-critical systems, guaranteeing safety during learning as well as testing/deployment is paramount. A variety of different approaches for ensuring safety exists, but the published works are cluttered and there are few reviews that compare the latest approaches. This paper reviews two promising approaches on guaranteeing safety for learning-based robust control of uncertain dynamical systems, which are based on control barrier functions and control Lyapunov functions. While control barrier functions provide an option to incorporate safety in terms of constraint satisfaction, control Lyapunov functions are used to define safety in terms of stability. This review categorises learning-based methods that use control barrier functions and control Lyapunov functions into three groups, namely reinforcement learning, online and offline supervised learning. Finally, the paper presents a discussion of the suitability of the different methods for different applications.

Cyber–physical system (CPS) is the product of technological development to a certain stage, and also is the future trends in information technology. High-performance computing ability is the guarantee of CPS’s real-time and accuracy applications, and the emergence of distributed technology provides the implementation possibility of high-performance CPS. Task scheduling is a typical combination optimization problem and the task allocation problem on multi-processor distributed systems refers to how to use system resources most efficiently in a distributed computing environment to complete a limited set of tasks. Based on the behavior of ants searching for food in nature, ant colony algorithm is a kind of positive feedback algorithm with good robustness and easy parallel implementation and has certain advantages for dealing with constraint satisfaction. In order to introduce an adaptive mechanism and mutation strategy, shorten the calculation time of ant colony algorithm, speed up CPS algorithm convergences, and improve distributed CPS prediction accuracy, this paper analyzed the research status and significance of ant colony algorithm, expounded the development background, current situation, and future challenges of task optimization and scheduling of distributed CPS, elaborated the principles and methods of ant colony optimization algorithm model and mathematical description of CPS task scheduling, proposed a task management model of distributed CPS based on improved ant colony algorithm, explored the task optimization scheduling of distributed CPS based on improved ant colony algorithm, and finally conducted an numerical simulation to test the effect the proposed algorithm and model. The simulation results show that the proposed algorithm model enhances the local search ability and improves the quality of the task scheduling problem, and has good effectiveness, stability and adaptability. The study results of this paper provide a reference for the further research on the optimization and scheduling of distributed CPS tasks.

This paper introduces a new distributed approach to solve multi-objective planning problem applied to multimodal transport network planning (MTNP) problem. In this problem, the commodities should be transported on the international network by at least two different transport modes. The main goal is to find the best multimodal transportation modes and itineraries. The aim of the new approach has assured us that a distributed optimization. We split the MTNP problem into two sub-problems. These sub-problems are the assignment and the planning problems. Each sub-problem is solved at a corresponding layer. Each layer is executed by an agent. These agents interact, collaborate and communicate together to solve the MTNP problem. In this paper, we contribute by introducing a multi-layer distributed approach to solve real case’s problems. Firstly, we define the MTNP problem as a distributed constraint satisfaction multi-criteria optimization problem (DCSMOP). Secondly, we show that the split of the main problem reduces the computational complexity and the communication between the planner agent and the modes agents lead to faster convergence. The experimental results are proof of this work efficiently. This method proves their efficiency, according to the complexity of the problem and the exchange of information, the computational time and the solution quality.

Timetable generation is an important part of every educational institution and is a complex and multi constraint satisfaction problem. It appears to be a monotonous job in every academic institute once or twice a year. In earlier days, timetable scheduling was done manually by a single person or a group of individuals, which is a very tedious task and takes a lot of effort and time. Planning a timetable is a very complex task. Timetable generation involves the efficient allocation of resources such as Rooms, Lecturers, Student Groups, etc. keeping in mind the availability, preferences and conveniences of the resource. The preferences and conveniences of the resource can include frequencies of a lecture, number of hours in a day and week, preferred time slots of a day, preferred working days, etc. This paper discusses the use of Genetic Algorithm and its operations, viz. Selection, Crossover and Mutation for solving of this problem. Based on the research, Genetic Algorithm is proved to improve this process as it focuses on various constraints and provides a global optimal solution rather that converging on a premature local optimum. The paper gives a conceptual design for the generation of a timetable for an institution using Genetic Algorithm.

International audience; Invariant set theory has been recognized as an important tool for control design of constrained systems subject to disturbances. Indeed, for a given control law, entering an invariant set guarantees recursive state and input constraint satisfaction in closed-loop. This paper focuses on discrete-time linear systems subject to bounded matched additive disturbance. The problem of the joint synthesis of control laws and associated invariant sets that are optimized with regards to the state constraints is investigated. An interpolation method is used to enlarge the controllable region.

We present a novel programming concept called temporal constrained objects for modeling of dynamic systems. It is an extension of the paradigm of constrained objects which provides a principled approach to modeling complex engineering systems based upon two main principles: a compositional specification of the structure of the system, using objects, and a declarative specification of its behavior, using constraints. A novel feature of temporal constrained objects is the series variable, the sequence of whose values is determined by constraints that include metric temporal operators. The emergent behavior of a dynamic system is determined through a process of time-based simulation and constraint satisfaction at each step. Each class definition for a temporal constrained object is translated into a Prolog rule with constraint-solving capability. In order to improve the performance for long simulations, a partial evaluation technique is adopted for optimized code generation. This paper describes the syntax of a language called TCOB along with several examples, our objective being to demonstrate the benefits of the programming paradigm. TCOB has been implemented and all examples presented in this paper were tested using this implementation. An overview of the translation as well as partial execution and its performance improvements are presented in the paper. A novel programming concept called temporal constrained objects.Series variable and metric temporal operators for specifying dynamic behavior.Computational model involves time-based simulation and constraint satisfaction.Class definitions translated into Prolog predicates, optimized by partial evaluation.Examples from engineering domain and performance results.

This paper addresses an adaptive output-feedback tracking problem of arbitrarily switched pure-feedback nonlinear systems with time-varying output constraints and unknown control directions. In this work, the tracking problem of switched non-affine nonlinear systems with output constraints is transformed into the stabilization problem of switched unconstrained affine systems. The main contribution of this paper is to present a universal formula for constructing an adaptive state-observer-based tracking controller with only two adaptive parameters by using the common Lyapunov function method. These adaptive parameters in the proposed control scheme are derived using the function approximation technique and a priori knowledge of the signs of control gain functions is not required. The theoretical analysis is presented for the Lyapunov stability and the constraint satisfaction of the resulting closed-loop system in the presence of arbitrary switchings.

This paper focuses on the design of a stabilizing control law for an aerial vehicle which is physically connected to a ground station by means of a tether cable. By taking advantage of the tensile force acting along the taut cable, it is shown that the tethered UAV is able to maintain a non-zero attitude while hovering in a constant position. The control objective is to stabilize the desired configuration while simultaneously ensuring that the cable remains taut at all times. This leads to a nonlinear control problem subject to constraints. This paper provides a two-step solution. First, the system is stabilized using a cascade control scheme based on thrust vectoring. Then, constraint satisfaction is guaranteed using a novel Reference Governor scheme.

The paper discusses the problem of the induction of a minimal nondeterministic finite automaton (NFA) consistent with a given set of examples and counterexamples. The main contribution of the paper is the proposal of an efficient parallel algorithm transforming the NFA induction problem into a family of constraint satisfaction problems (CSP). Two original techniques for fast CSPs evaluation are proposed and discussed. The efficacy of the parallel algorithm is evaluated experimentally on selected benchmarks. The proposed algorithm solves all analyzed benchmark examples, so called Tomita languages, in the time below half a minute, which should be considered an important achievement, as compared to our previous efforts which required minutes or hours to solve some of the aforementioned benchmarks.

Real life optimization problems involve a number of constraints arising out of user requirements, physical laws, statutory requirements, resource limitations etc. Such constraints are routinely evaluated using computationally expensive analysis i.e., solvers relying on finite element methods, computational fluid dynamics, computational electro magnetic, etc. Existing optimization approaches adopt a full evaluation policy, i.e., all the constraints corresponding to a solution are evaluated throughout the course of search. Furthermore, a common sequence of constraint evaluation is used for all the solutions. In this paper, we introduce a novel scheme for constraint handling, wherein every solution is assigned a random sequence of constraints and the evaluation process is aborted whenever a constraint is violated. The solutions are sorted based on two measures i.e., the number of satisfied constraints and the violation measure. The number of satisfied constraints takes precedence over the amount of violation and the most efficient sequence of constraint evaluation is evolved during the course of search. The performance of the proposed scheme is rigorously compared with other state of the art constraint handling methods using single objective inequality constrained test problems of CEC-2006 and CEC-2010. The constraint handling approach is generic and can be easily used for the solution of constrained multiobjective optimization problems or even problems with equality constraints. A bi-objective welded beam design problem, a tri-objective car side impact problem and an equality constrained optimization problem of CEC-2006 is solved as an illustration. The results clearly highlight potential savings offered by the proposed strategy and more importantly the paper provides a detailed insight on why such a strategy performs better than others.

This paper studies the effect of the predictor structure and tuning in the robustness of model predictive controllers (MPC) when controlling dead-time processes. It is shown that although MPC techniques can easily cope with systems with dead time because of their internal predictor structure, this implicit predictor can make the stability margins of the controller dependent on the nominal dead-time. This delay dependency can be an important drawback of the controller, causing instability even for small modelling errors when controlling processes with large delays. Therefore, it is necessary to define a proper predictor for the MPC algorithm in order to improve robustness. In this paper a predictor structure derived from the Filtered Smith Predictor is proposed which simplifies the tuning and allows improved robustness. The analysis of stability and robustness is first done for the linear MPC case, and then generalized for nonlinear MPC for a class of nonlinear systems. The key idea of this approach is to separate the predictor structure from the optimization stage in such a way that input-to-state stability and constraint satisfaction can be guaranteed by using an equivalent dead-time free system.

The concept of the natural computation for optimal scheduling in high level synthesis, for resource constraint and time constraint scheduling problem in automated integrated circuit synthesis using Integer Linear Programming (ILP) modeling is presented in this paper. This paper compares three natural computations paradigms: (i) evolution optimizer technique genetic algorithm, (ii) evolutionary programming, and (iii) swarm intelligence based particle swarm optimization. Experimental results indicate that evolution based Genetic Algorithm search is more powerful search compared to Evolutionary Programming and Particle Swam Optimization.

This paper presents a methodology to improve CPM/LOB scheduling method for deadline constraint satisfaction. A complete and simple heuristic approach called “heuristic line of balance” (HLOB) is introduced for scheduling projects with serial activities. It employs four heuristic rules and their appropriate combination in addition to seeking CPM/LOB initial calculation. As an improvement to the HLOB algorithm, the “search-based heuristic line of balance” (SHLOB) algorithm is also presented, which is more efficient as projects grow in size. Finally, a complete mathematical version of the LOB model in the form of mixed integer nonlinear programming (MINLP) is applied for verification of the proposed models. Two simple case studies and a hypothetical large-scale highway project are used to test the performance of the improved models. Due to the results of this paper, HLOB and SHLOB are able to present optimum/near optimum solutions in a much more economical way that may justify their widespread use.

Standard numerical integration schemes for multibody system (MBS) models in absolute coordinates neglect the coupling of linear and angular motions since finite positions and rotations are updated independently. As a consequence geometric constraints are violated, and the accuracy of the constraint satisfaction depends on the integrator step size. It is discussed in this paper that in certain cases perfect constraint satisfaction is possible when using an appropriate configuration space (without numerical constraint stabilization). Two formulations are considered, one where R^3 is used as rigid body configuration space and another one where rigid body motions are properly modeled by the semidirect product SE(3)=SO(3)@?R^3. MBS motions evolve on a Lie group and their dynamics is naturally described by differential equations on that Lie group. In this paper the implications of using the two representations on the constraint satisfaction within Munthe-Kaas integration schemes are investigated. It is concluded that the SE(3) update yields perfect constraint satisfaction for bodies constrained to a motion subgroup of SE(3), and in the general case both formulations lead to equivalent constraint satisfaction.

Workflows are used to formally describe processes of various types such as business and manufacturing processes. One of the critical tasks of workflow management is automated discovery of possible flaws in the workflow - workflow verification. In this paper, we formalize the problem of workflow verification as the problem of verifying that there exists a feasible process for each task in the workflow. This problem is tractable for nested workflows that are the workflows with a hierarchical structure similar to hierarchical task networks in planning. However, we show that if extra synchronization, precedence, or causal constraints are added to the nested structure, the workflow verification problem becomes NP-complete. We present a workflow verification algorithm for nested workflows with extra constraints that is based on constraint satisfaction techniques and exploits an incremental temporal reasoning algorithm. We then experimentally demonstrate efficiency of the proposed techniques on randomly generated workflows with various structures and sizes. The paper is concluded by notes on exploiting the presented techniques in the application FlowOpt for modeling, optimizing, visualizing, and analyzing production workflows.

This paper presents the self-controlling software paradigm and reports on its use to control the branch and bound based constraint satisfaction problem solving algorithm. In this paradigm, an algorithm is first conceptualized as a dynamical system and then a feedback control loop is added to control its behavior. The loop includes a Quality of Service component that assesses the performance of the algorithm during its run time and a controller that adjusts the parameters of the algorithm in order to achieve the control goal. Although other approaches - generally termed as ''self-*'' - make use of control loops, this use is limited to the structure of the software system, rather than to its behavior and its dynamics. This paper advocates the analysis of dynamics of any program with control loops. The self-controlling software paradigm is evaluated on two different NP-hard constraint satisfaction and optimization problems. The results of the evaluation show an improvement in the performance due to the added control loop for both of the tested constraint satisfaction problems.

Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for artificial intelligence and multi-agent systems. Also, Ant Colony Optimization (ACO) is an important evolutionary method for solving various optimization problems. This paper demonstrates the power of ants in solving DCSPs and describes a new approach for such a solution, showing how it differs from previous ACO-based DCSP solvers. The presented algorithm is designed to provide the special requirements that are important in the distributed form of Constraint Satisfaction Problem (CSP). The paper describes the important criteria for distributed CSP and then demonstrates how the presented algorithm stands out over similar DCSP solvers considering these criteria. Finally, the proposed approach is evaluated on random binary problems. The practical results show that this method, in most of the cases, outperforms the Asynchronous Backtracking Algorithm (ABT) and Distributed Breakout Algorithm (DBA) two important algorithms in this field of research.

This paper deals with fault diagnosis for a class of nonlinear continuous-time systems based on an interval extension of continuous-time parity equations. The parity equations are designed based on ordinary differential equations modeling some links between the successive output and input vector derivatives. The noisy inputs and outputs are evaluated through a high-order sliding-mode differentiator. The redundancy relations are formulated as a Constraint Satisfaction Problem (CSP) with faults as unknown variables. In this case, a reliable estimation of the fault magnitude can be performed by solving the CSP using interval techniques. This technique is well suited to deal with actuator faults as well as parametric or sensor faults. However, in this paper, we choose to focus on actuator faults and the performance of the proposed approach is illustrated through simulations on oscillatory failure detection in aircraft surface servo loops. input observer, fault reconstruction, consistency techniques, nonlinear systems.

The prime aim of this paper is to embed a predictive control (MPC) algorithm with constraint handling capabilities into a programmable logic controller (PLC). In order to achieve it, this paper develops parametric approaches to MPC but differs from more conventional approaches in that it predefines the complexity of the solution rather than the allowable suboptimality. The paper proposes a novel parameterisation of the parametric regions which allows efficiency of definition, effective spanning of the feasible region and also highly efficient search algorithms. Despite the suboptimality, the algorithm retains guaranteed stability, in the nominal case. A laboratory test was carried out to demonstrate the code on real hardware and the effectiveness of the solution.

The aim of the job-shop scheduling problem is to optimize the task planning in an industrial plant satisfying time and technological constraints. The existing algorithmic and mathematical methods for solving this problem usually have high computational complexities making them intractable. Flexible job-shop scheduling becomes even more complex, since it allows one to assign each operation to a resource from a set of suitable ones. Alternative heuristic methods are only able to satisfy part of the constraints applicable to the problem. Moreover, these solutions usually offer little flexibility to adapt them to new requirements. This paper describes research within heuristic methods that combines genetic algorithms with repair heuristics. Firstly, it uses a genetic algorithm to provide a non-optimal solution for the problem, which does not satisfy all its constraints. Then, it applies repair heuristics to refine this solution. There are different types of heuristics, which correspond to the different types of constraints. A heuristic is intended to evaluate and slightly modify a solution that violates a constraint in a way that avoids or mitigates such violation. This approach improves the adaptability of the solution to a problem, as some changes can be addressed just modifying the considered chromosome or heuristics. The proposed solution has been tested in order to analyse its level of constraint satisfaction and its makespan, which are two of the main parameters considered in these types of problems. The paper discusses this experimentation showing the improvements over existing methods.

The guarantee of feasibility given feasibility at initial time is an issue that has been overlooked by many of the recent papers on stochastic model predictive control. Effective solutions have recently been proposed, but these carry considerable online computational load and a degree of conservativism. For the case that the elements of the random additive disturbance vector are independent, the current paper ensures that probabilistic constraints are met and that a quadratic stability condition is satisfied. A numerical example illustrates the efficacy of the proposed algorithm, which achieves tight satisfaction of constraints and thereby attains near-optimal performance. © 2010 Elsevier Ltd. All rights reserved.

Structural redundancies in mathematical programming models are nothing uncommon and nonlinear programming problems are no exception. Over the past few decades numerous papers have been written on redundancy. Redundancy in constraints and variables are usually studied in a class of mathematical programming problems. However, main emphasis has so far been given only to linear programming problems. In this paper, an algorithm that identifies redundant objective function(s) and redundant constraint(s) simultaneously in multi-objective nonlinear stochastic fractional programming problems is provided. A solution procedure is also illustrated with numerical examples. The proposed algorithm reduces the number of nonlinear fractional objective functions and constraints in cases where redundancy exists.

This paper presents a constraint programming approach to the Enigma 1225, a mathematical puzzle published in the New Scientist magazine in February 2003. An approach based on Prolog was published recently. In this paper we give a constraint programming perspective on the problem, highlighting the differences between the two methodologies. We show how problem-specific knowledge can be easily incorporated into a constraint-based approach, giving an efficient constraint model for the generalized version of the puzzle. From the constraint programming point of view, the Enigma 1225 puzzle exhibits interesting symmetries, that can be eliminated using only a small number of constraints added to the model. Furthermore, properties of the puzzle can be used to derive a strong constraint propagation scheme that limits the search once an optimal solution has been found.

This paper presents techniques for solving the problem of minimizing investment costs on an existing gas transportation network. The goal of this program is to find, first, the optimal location of pipeline segments to be reinforced and, second, the optimal sizes (among a discrete commercial list of diameters) under the constraint of satisfaction of demands with high enough pressure for all users. The paper develops new heuristics for solving this large-scale integer NLP problem, based on a two phases approach. The first one solves a continuous relaxation of the problem. A generalized potential formulation of the gas transportation networks including valves and compressor stations is introduced in order to find an initial point of the optimization solver. Phase two consists in choosing discrete values of diameters only among the set of pipes that have been reinforced in the continuous relaxation. A Branch & Bound scheme is then applied to a limited number of values in order to generate good solutions with reasonable computational effort on real-world applications.

Constraint Handling Rules (CHR) is an extension to Prolog which opens up a spectrum of hypothesis-based reasoning in logic programs without additional interpretation overhead. Abduction with integrity constraints is one example of hypothesis-based reasoning which can be implemented directly in Prolog and CHR with a straightforward use of available and efficiently implemented facilities. The present paper clarifies the semantic foundations for this way of doing abduction in CHR and Prolog as well as other examples of hypothesis-based reasoning that is possible, including assumptive logic programming, hypotheses with priority and scope, and nonmonotonic reasoning. Examples are presented as executable code so the paper may also serve the additional purpose of a practical guide for developing such programs, and it is demonstrated that the approach provides a seamless integration with existing constraint solvers.

The aim of this paper is to transform a multi-choice linear programming problem to a standard mathematical programming problem where the right hand side goals of some constraints are 'multi-choice' in nature. For each of the constraint there may exist multiple number of goals, out of which exactly one is to be chosen. The selection of goals should be in such a manner that the combination of choices for each constraint should provide an optimal solution to the objective function. There may be more than one combination which will provide an optimal solution. However the problem cannot be solved by standard linear programming techniques. In order to solve the present multi-choice linear programming problem, this paper proposes a new transformation technique. Binary variables are introduced in the transformation technique to formulate a non-linear mixed integer programming model. Using standard non-linear programming software optimal solution of the proposed model can be obtained. Finally, a numerical example is presented to illustrate the transformation technique and the solution procedure.

In this paper a combination of the two most important problems in distribution logistics is considered, known as the two-dimensional loading vehicle routing problem. This problem combines the loading of the freight into the vehicles, and the successive routing of the vehicles along the road network, with the aim of satisfying the demands of the customers. The problem is solved by different heuristics for the loading part, and by an ant colony optimization (ACO) algorithm for the overall optimization. The excellent behavior of the algorithm is proven through extensive computational results. The contribution of the paper is threefold: first, on small-size instances the proposed algorithm reaches a high number of proven optimal solutions, while on large-size instances it clearly outperforms previous heuristics from the literature. Second, due to its flexibility in handling different loading constraints, including items rotation and rear loading, it allows us to draw qualitative conclusions of practical interest in transportation, such as evaluating the potential savings by permitting more flexible loading configurations. Third, in ACO a combination of different heuristic information usually did not turn out to be successful in the past. Our approach provides an example where an ACO algorithm successfully combines two completely different heuristic measures (with respect to loading and routing) within one pheromone matrix.

The constraint diagram language was designed to be used in conjunction with the unified modelling language (UML), primarily for placing formal constraints on software models. In particular, constraint diagrams play a similar role to the textual object constraint language (OCL) in that they can be used for specifying system invariants and operation contracts in the context of a UML model. Unlike the OCL, however, constraint diagrams can be used independently of the UML. In this paper, we illustrate a range of intuitive and counter-intuitive features of constraint diagrams and highlight some (potential) expressiveness limitations. The counter-intuitive features are related to how the individual pieces of syntax interact. A generalized version of the constraint diagram language that overcomes the illustrated counter-intuitive features and limitations is proposed. In order to discourage specification readers and writers from overlooking certain semantic information, the generalized notation allows this information to be expressed more explicitly than in the non-generalized case. The design of the generalized notation takes into account five language design principles which are discussed in the paper. We provide a formalization of the syntax and semantics for generalized constraint diagrams. Moreover, we establish a lower bound on the expressiveness of the generalized notation and show that they are at least as expressive as constraint diagrams.

This paper is concerned with the Constraint Satisfaction Problem (CSP). It is well-known that the general CSP is NP-hard. However, there has been significant success in discovering subproblems which are tractable (polynomial time solvable). One of the most effective ways to obtain a tractable subproblem has been to force all of the constraint relations to lie in some tractable language. In this paper we define a new way of identifying tractable subproblems of the CSP. Let P be an arbitrary CSP instance and @C be any tractable language. Suppose there exists, for each variable of P, a permutation of the domain such the resultant permuted constraint relations of P all lie in @C. The domain permuted instance is then an instance of a tractable class and can be solved by the polynomial time algorithm for @C. Solutions to P can be obtained by inverting the domain permutations. The question, for a given class of instances and language @C, whether such a set of domain permutations can be found efficiently is the key to this method's tractability. One of the important contributions made in this paper is the notion of a ''lifted constraint instance'' which is a powerful tool to study this question. *We consider the open problem of discovering domain permutations which make instances max-closed. We show that, for bounded arity instances over a Boolean domain this problem is tractable, while for domain size three it is intractable even for binary instances. *We give a simple proof verifying the tractability of discovering domain permutations which make instances row convex. We refute a published result by giving a simple proof of the intractability of discovering domain permutations which make instances, even with domain size four, connected row convex. *We demonstrate that triangulated and stable marriage instances are reducible, via domain permutations, to max-closed instances. This provides a simple explanation for arc consistency deciding these instances. *We verify with a simple direct proof the tractability of identification of renamable Horn instances, and the intractability of finding the largest renamable Horn subset of clauses of an instance of SAT. *We describe natural tractable classes which properly extend the maximal relational classes arising from tractable constraint languages. We believe that domain permutation reductions have a significant chance of being useful in practical applications.

This paper addresses the issue of the practical implementation of closed-form Model Predictive Controllers (MPC) to processes with very short sampling times. Such questions come in consideration when the solution to MPC problems is expressed in a so-called parametric or closed-form fashion. The underlying idea of this paper is to approximate the optimal control law defined over state space regions by a higher degree polynomial which then guarantees closed-loop stability, constraint satisfaction, and a bounded performance decay. The advantage of the proposed scheme lies in faster controller evaluation and lower storage demand compared to currently available techniques.

This paper proposes a new passive robust fault detection scheme using non-linear models that include parameter uncertainty. The non-linear model considered here is described by a group method of data handling (GMDH) neural network. The problem of passive robust fault detection using models including parameter uncertainty has been mainly addressed by checking if the measured behaviour is inside the region of possible behaviours based on the so-called forward test since it bounds the direct image of an interval function. The main contribution of this paper is to propose a new backward test, based on the inverse image of an interval function, that allows checking if there exists a parameter in the uncertain parameter set that is consistent with the measured system behaviour. This test is implemented using interval constraint satisfaction algorithms which can perform efficiently in deciding if the measured system state is consistent with the GMDH model and its associated uncertainty. Finally, this approach is tested on the servoactuator being a FDI benchmark in the European Project DAMADICS.

In modern DSL systems, multi-user crosstalk is a major source of performance degradation. Optimal spectrum balancing (OSB) is a centralized algorithm that mitigates the effect of crosstalk by allocating optimal transmit spectra to all interfering DSL modems. By the use of Lagrange multipliers the algorithm decouples the spectrum management problem into per-tone optimization problems. The remaining issues are then finding the Lagrange multipliers that enforce the constraints and solving the per-tone optimization problems. Finding the optimal Lagrange multipliers can become complex when more than two users are considered. Starting from the single-user case, this paper presents a number of properties, which are then extended to the multi-user case and lead to an efficient search algorithm for the Lagrange multipliers. Simulations show that the number of Lagrange multiplier evaluations is as small as 20-50, independent of the number of users. Secondly, the complexity of the per-tone optimization problems grows exponentially with the number of lines in the binder. For multiple-user scenarios this becomes computationally intractable. This paper presents an efficient branch-and-bound approach for the per-tone optimization problem. Simulations show enormous complexity reductions, especially for a large number of users.

This paper illustrates the use of multi-objective optimization to solve three types of reliability optimization problems: to find the optimal number of redundant components, find the reliability of components, and determine both their redundancy and reliability. In general, these problems have been formulated as single objective mixed-integer non-linear programming problems with one or several constraints and solved by using mathematical programming techniques or special heuristics. In this work, these problems are reformulated as multiple-objective problems (MOP) and then solved by using a second-generation Multiple-Objective Evolutionary Algorithm (MOEA) that allows handling constraints. The MOEA used in this paper (NSGA-II) demonstrates the ability to identify a set of optimal solutions (Pareto front), which provides the Decision Maker with a complete picture of the optimal solution space. Finally, the advantages of both MOP and MOEA approaches are illustrated by solving four redundancy problems taken from the literature.

P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type. In this paper, some restrictions on the general form of the developing rules are considered, under which it is still possible to solve NP-complete problems. We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using two polarizations and rules of restricted versions of types (a), (c), (e). The result obtained in this paper answered an open problem proposed by Alhazov and Freund in the aspect of computing efficiency.

In this paper, the robust fault detection problem for non-linear systems considering both bounded parametric modelling errors and noises is addressed. Fault detection is formulated as a set-membership estimation problem being this one the contributions of the paper. A state estimator that describes the set of all the states consistent with modelling uncertainty, measured data and noise bounds is presented. Two possible implementations of such state estimation, based on constraint satisfaction and set computation techniques, of the state estimator are proposed and compared, being this a second contribution. Finally, the proposed approaches are applied to detect faults in limnimeters of a piece of Barcelona sewer network.

6 pages; International audience; In order to reduce cost and to optimize the use of resources, hospitals are prompted to regroup facilities and human resources, especially in the surgical suite. This paper focuses on the anaesthesiology nurse scheduling problem (ANSP) of a French public hospital, where the anaesthesiology nurses constitute one of the most shared resources. They work in a cross way over surgical specialities and assume various activities. Two methods are proposed to solve the ANSP based on integer programming and constraint programming. The objective is to maximize the fairness of the schedule. Theses two techniques are tested in order to be compared.

The problem we tackle is progressive scheduling with temporal and resource uncertainty. Operation durations are imprecise and alternative resources may break down. Operation end times and resource breakdowns are observed during execution. In this paper, we assume we have a representation of uncertainty in the form of probability distributions which are used in the simulation of schedule execution. We generate the schedule piece by piece during execution and use simulation to monitor the execution of the partial schedule. This paper describes the basis on which the decision to select and schedule a new subset of operations is made.

This paper presents a portable and scalable approach for a class of constrained combinatorial optimization problems (CCOPs) which requires to satisfy a set of constraints and to optimize and objective function simultaneously. In particular, this paper is focused on the class of CCOPs that admits a representation in terms of a square matrix of constraints C.The algorithm consists of a hybrid neural-genetic algorithm, formed by a Hopfield Neural Network (HNN) which solves the problem's constraints, and a Genetic Algorithm (GA) for optimizing the objective function. This separated management of constraints and optimization procedures makes the proposed algorithm scalable and robust. The portability of the algorithm is given by the fact that the HNN dynamics depends only on the matrix C of constraints.We show these properties of scalability and portability by solving three different CCOPs with our algorithm, the frequency assignment problem in a mobile telecommunications network, the reduction of the interference in satellite systems and the design of FPGAs with segmented channel routing architecture. We compare our results with previous approaches to these problems, obtaining very good results in all of them.

This paper is concerned with the analysis of a recently-proposed robust control policy for linear discrete-time systems subject to bounded state disturbances with mixed constraints on the states and inputs, which parameterizes the input as an affine function of the past disturbance sequence. The paper shows that this disturbance feedback policy is equivalent to the class of affine state feedback policies with memory of prior states, and thus subsumes the wellknown classes of open-loop and pre-stabilising control policies. Furthermore, the parameterization transforms the non-convex problem of finding an admissible state feedback policy to an equivalent and tractable convex problem.

Collaborative CAD systems enabling collaboration in computer-aided design processes among distributed designers are gaining more and more attention. Yet, such systems, especially in support of collaborative assembly modeling, are hardly achievable. Targeting this gap, this paper addresses an Internet-enabled real-time collaborative assembly modeling system, named e-Assembly. This emerging system allows a group of geographically dispersed designers to jointly build an assembly model in real time over the Internet. In particular, this paper proposes a new assembly representation, called Collaborative Assembly Representation, for Internet-based collaborative assembly modeling. Also, collaborative assembly constraint satisfaction is addressed based on three coordination rules embedded in e-Assembly. Furthermore, the system architecture and realization of e-Assembly are provided. Finally, a prototypic implementation of e-Assembly is presented for demonstration and discussion.

Constraint satisfaction is a fundamental Artificial Intelligence technique for knowledge representation and inference. However, the formulation of a static constraint satisfaction problem (CSP) with hard, imperative constraints is insufficient to model many real problems. Fuzzy constraint satisfaction provides a more graded viewpoint. Priorities and preferences are placed on individual constraints and aggregated via fuzzy conjunction to obtain a satisfaction degree for a solution to the problem. This paper examines methods for solving an important instance of dynamic flexible constraint satisfaction (DFCSP) combining fuzzy CSP and restriction/relaxation based dynamic CSP: fuzzy rrDFCSP. This allows the modelling of complex situations where both the set of constraints may change over time and there is flexibility inherent in the definition of the problem. This paper also presents a means by which classical planning can be extended via fuzzy sets to enable flexible goals and preferences to be placed on the use of planning operators. A range of plans can be produced, trading compromises made versus the length of the plan. The flexible planning operators are close in definition to fuzzy constraints. Hence, through a hierarchical decomposition of the planning graph, the work shows how flexible planning reduces to the solution of a set of fuzzy rrDFCSPs.

Virtual prototyping tools have already captivated the industry's interest as viable design tool. One of the key challenges for the research community is to extend the capabilities of Virtual Reality technology beyond its current scope of ergonomics and design reviews. The research presented in this paper is part of a larger research programme that aims to perform maintainability assessment on virtual prototypes. This paper discusses the design and implementation of a geometric constraint manager that has been designed to support physical realism and interactive assembly and disassembly tasks within virtual environments. The key techniques employed by the constraint manager are direct interaction, automatic constraint recognition, constraint satisfaction and constrained motion. Various optimization techniques have been implemented to achieve real-time interaction with large industrial models.

The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to satisfiability (SAT) theories and integer linear programming (ILP). In this paper we will show that CSP is a better substrate for the compilation approach, compared to both SAT and ILP. We describe GP-CSP, a system that does planning by automatically converting Graphplan's planning graph into a CSP encoding and solving it using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is superior to both the Blackbox system, which compiles planning graphs into SAT encodings, and an ILP-based planner in a wide range of planning domains. Our results show that CSP encodings outperform SAT encodings in terms of both space and time requirements in various problems. The space reduction is particularly important as it makes GP-CSP less susceptible to the memory blow-up associated with SAT compilation methods. The paper also discusses various techniques in setting up the CSP encodings, planning specific improvements to CSP solvers, and strategies for variable and value selection heuristics for solving the CSP encodings of different types of planning problems. Copyright 2001. Elsevier Science B.V.

This paper describes the derivation of a consistent and comprehensive set of geometrical constraints for shape definition in CAD. Such a set is needed to enable compatibility in parametric data exchange and to promote both standard capabilities and predictable solutions from constraint solving software kernels. The paper looks at the mathematical basis for constraints present in the literature and elaborates about all types of constraints that can be described by the same mathematical basis. Exhaustive combinations of distance and angle constraints, on one point or all points of curves and surfaces, as well as transformations and mappings that are required in mechanical design are included in the proposed taxonomy and representation. Consistency is promoted by distinguishing necessary constraint types from redundant constraint types. Comprehensiveness is promoted by including all constraint types from the literature that are within the scope and considering combinatorial variations of them.

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate. Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.

The attributed variable data type plays an important role in many extensions to the basic Logic Programming language. It provides a flexible mechanism to implement constraint solvers over different domains in a standard logic programming system. To combine the technique of constraint solving with tabling and build a tabled constraint logic programming system, special work has to be done to handle attributed variables when they are copied into and out of tables. In this paper, we describe the implementation of attributed variables in XSB — a tabled logic programming system. We first introduce the internal representation of attributed variables and the interface between the internal representation and the user defined high level unification handler. Then, as the primary focus of the paper, we describe how the tabling mechanism in XSB can be extended to efficiently handle attributed variables. To save attributed variables in tables, the structure of subgoal table and answer table is modified, and the tabling engine itself requires extension as well.

This paper provides the foundation of connections between default reasoning and constraint satisfaction. Such connections are important because they combine fields with different strengths that complement each other: default reasoning is broadly seen as a promising method for reasoning from incomplete information, but is hard to implement. On the other hand, constraint satisfaction has evolved as a powerful, and efficiently implementable, problem solving paradigm in artificial intelligence. In this paper, we show how THEORIST knowledge bases and theories in Constrained Default Logic with prerequisite-free defaults may be mapped to partial constrained satisfaction problems. We also extend these results to deal with priorities among defaults.