Archives of Control Sciences

Last issue
2018 (vol. 28) - Number 2

E. Roszkowska:

Hybrid motion control for multiple mobile robot systems

C. Civelek:

Stability analysis of engineering/physical dynamic systems using residual energy function

M. Ziolko, M. Nowak:

Design of transmultiplexer integer filters

S. Vaidyanathan, S. Jafari, V.-T. Pham, A.T. Azar:

A 4-D chaotic hyperjerk system with a hidden attractor, adaptive backstepping control and circuit design

T. Kaczorek:

An extension of Klamka's method to positive descriptor discrete-time linear systems with bounded inputs

A. Ratajczak:

Motion planning for nonholonomic systems with earlier destination reaching

K.C. Patra, B.K. Dakua:

Investigation of limit cycles and signal stabilization of two dimensional systems with memory type nonlinear elements

ACS Abstract:

2006 (Volume 16)
Number 2

1.	Principles of constraint systems and constraint solvers
2.	An introduction to interval-based constraint processing
3.	Filtering algorithms for the Same and UsedBy constraints
4.	Message delay and asynchronous DisCSP search

Principles of constraint systems and constraint solvers Download full PDF article

Thom Frühwirth
(Faculty of Computer Science, University of Ulm, Germany)

Slim Abdennadher
(Department of Computer Science, German University Cairo, Egypt)

In this compact overview, we introduce the most common constraint systems used in constraint programming languages and algorithms to solve them. Constraint systems are the result of taking a data type together with its operations and interpreting the resulting expressions as constraints. These constraint systems use the universal data types of numbers (integers or reals) to represent scalar data or terms to represent structured data. Algorithms are presented as logical inference rules that are directly executable in the Constraint Handling Rules language.

keywords: computational logic, executable specifications, rule-based programming, program analysis, algorithms

^top

An introduction to interval-based constraint processing Download full PDF article

Gerrit Renker, Hatem Ahriz
(School of Computing, The Robert Gordon University, Aberdeen, UK)

Constraint programming is often associated with solving problems over finite domains. Many applications in engineering, cad and design, however, require solving problems over continuous (real-valued) domains. While simple constraint solvers can solve linear constraints with the inaccuracy of floating-point arithmetic, methods based on interval arithmetic allow exact (interval) solutions over a much wider range of problems. Applications of interval-based programming extend the range of solvable problems from non-linear polynomials up to those involving ordinary differential equations.

In this text, we give an introduction to current approaches, methods and implementations of interval-based constraint programming and solving. Special care is taken to provide a uniform and consistent notation, since the literature in this field employs many seemingly different, but yet conceptually related, notations and terminology.

keywords: constraint programming, interval-based computation, interval consistency techniques

^top

Filtering algorithms for the Same and UsedBy constraints Download full PDF article

Nicolas Beldiceanu
(Ecole des Mines de Nantes, Nantes Cedex, France)

Irit Katriel, Sven Thiel
(Max-Planck-Institut fur Informatik, Saarbrucken, Germany)

We define the Same and UsedBy constraints. UsedBy takes two sets of variables X and Z such that |X| > |Z| and assigns values to them such that the multiset of values assigned to the variables in Z is contained in the multiset of values assigned to the variables in X. Same is the special case of UsedBy in which |X|=|Z|. We show algorithms that achieve arc-consistency and bound-consistency for these constraints.

keywords: arc-consistency, bound-consistency, constraint programming, filtering algorithm, global constraint, network flow, strongly connected component

^top

Message delay and asynchronous DisCSP search Download full PDF article

Roie Zivan, Amnon Meisels
(Department of Computer Science, Ben-Gurion University of the Negev, Israel)

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been shown in experimental studies of asynchronous backtracking algorithms. To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the number of non-concurrent steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. The performance of two asynchronous search algorithms is measured on randomly generated instances of DisCSPs with delayed messages. The Asynchronous Weak Commitment (AWC) algorithm and Asynchronous Backtracking (ABT). The intrinsic reordering process of AWC dictates a need for a more complex count of non-concurrent steps of computation. The improved counting algorithm is also needed for Dynamic ordered ABT. The delay of messages is found to have a strong negative effect on AWC and a smaller effect on dynamically ordered ABT.

keywords: distributed constraint satisfaction, search, distributed AI

^top

<< Back