Asynchronous Forward-Checking for DisCSPs
Amnon Meisels and Roie Zivan
Constraints, Vol. 12, No. 2, 2007.
A new search algorithm for solving distributed constraint satisfaction problems ({\em DisCSP}s) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking algorithm ({\em AFC}) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven.
The sequential assignment method of $AFC$ leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics are evaluated and shown to improve the performance of $AFC$ with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking ($ABT$) on randomly generated DisCSPs is also presented. $AFC$ with ordering heuristics outperforms $ABT$ by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of non-concurrent constraints checks and number of messages sent.
Dynamic Ordering for Asynchronous
Backtracking on DisCSPs
Roie Zivan and Amnon Meisels
Constraints, Vol. 11, pp. 179-197, 2006.
An algorithm that performs asynchronous backtracking on distributed CSPs, with
dynamic ordering of agents is proposed, ABT_DO. Agents propose reorderings of lower priority agents and send these
proposals whenever they send assignment messages. Changes of ordering triggers a different computation of Nogoods.
The dynamic ordered asynchronous backtracking algorithm uses polynomial space,
similarly to standard ABT. The ABT_DO algorithm with three different ordering
heuristics is compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered
heuristic, inspired by dynamic backtracking, is found to outperform static
order ABT by a large factor in run-time and improve the network load.
Retroactive Ordering for Dynamic
Backtracking
Roie Zivan, Uri Shapen, Moshe Zazone
and Amnon Meisels
Proc. 17th European Conf. on Artificial Intelligence (ECAI-06), Riva del Garda, August 2006
Dynamic Backtracking (DBT) is a well known algorithm
for solving Constraint Satisfaction Problems. In DBT, variables are allowed to
keep their assignment during backjump, if they are
compatible with the set of eliminating explanations. A previous study has shown
that when DBT is combined with
variable ordering heuristics it performs poorly compared to standard
Conflict-directed Backjumping (CBJ) [1]. The special
feature of DBT, keeping valid elimination explanations during backtracking, can
be used for generating a new class of ordering heuristics. In the proposed algorithm,
the order of already assigned variables can be changed. Consequently, the new
class of algorithms is termed Retroactive DBT.
In the proposed algorithm, the newly assigned variable can be moved to a
position in front of assigned variables with larger domains and as a result
prune the search space more effectively. The experimental results presented in
this paper show an advantage of the new class of heuristics and algorithms over
standard DBT and over CBJ. All algorithms tested were combined with forward-checking
and used a Min-Domain heuristic.
Distributed Navigation in an
Unknown Physical Environment
Arnon Gilboa, Amnon Meisels and Ariel Felner
Proc. 5th Intern. Joint Conf. on Auton. Agents
& Multi-Agent Sys., pp. 553-560, Hakodate Japan, May 2006
We address the problem of navigating from an initial node to a goal node by a
group of agents in an unknown physical environment, where traveling agents must
physically move around in the environment to discover the existence of nodes.
As a result, agents need to travel in order to
discover paths to the goal node. Agents communicate with a predefined set of
neighbors by exchanging messages. A distributed algorithm, which is run
independently by each agent, is presented. Given the current knowledge of the
agent about the environment and the positions of other agents, the algorithm
instructs the agent where to go next. The agent then updates its neighboring
agents with its new position and its discovered nodes. An experimental
evaluation of the algorithm is presented, with several different definitions of
neighborhoods, on random physical graphs. Results show that the distributed
intelligent behavior of agents generates spread of knowledge throughout the
environment efficiently. Agents reach the goal node fast and the length of the
path that they find is very close to that of the optimal path.
Message delay and
Asynchronous DisCSP search
Roie Zivan and Amnon Meisels
Archives of Control Sciences (ACS), Vol. 16, pp. 221-242, 2006
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 [1,
9]. 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.
Concurrent
Search for Distributed CSPs
Roie Zivan and Amnon Meisels
AI Journal, Vol. 170, pp. 440-461, 2006.
A distributed concurrent search algorithm for distributed constraint
satisfaction problems (DisCSPs) is presented.
Concurrent search algorithms are composed of multiple search processes (SPs)
that operate concurrently and scan non-intersecting parts of the global search
space. Each SP is represented by a unique data structure, containing a current
partial assignment (CPA), that is circulated among the different agents. Search
processes are generated dynamically, started by the initializing agent, and by
any number of agents during search. In the proposed, ConcDB,
algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a
search space can be found unsolvable by a different search process. This
enhances the efficiency of the ConcDB algorithm.
Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is
shown to be faster than former algorithms for solving DisCSPs.
Experimental evaluation of ConcDB, on randomly
generated DisCSPs demonstrates that the network load
of ConcDB is similar to the
network load of synchronous backtracking and is much lower than that of
asynchronous backtracking. The advantage of Concurrent Search is more
pronounced in the presence of imperfect communication, when messages are randomly
delayed.
Message
delay and DisCSP search algorithms
Roie Zivan and Amnon Meisels
Annals of Mathematics and Artificial Intelligence, Vol. 46, pp.
415-439, 2006.
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 recently shown in experimental studies of asynchronous
backtracking algorithms [1, 15]. 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
non-concurrent number of 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 number of
non-concurrent constraint checks calculated by the simulator serves as a good
performance measure, when messages are delayed. Two families of distributed
search algorithms on DisCSPs are investigated.
Algorithms that run a single search process, and multiple search processes
algorithms. The two families of algorithms are described and associated with
existing algorithms. The performance of three representative algorithms of
these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is
found to have a strong negative effect on single search process algorithms,
whether synchronous or asynchronous. Multi search process algorithms, on the
other hand, are affected very lightly by message delay.
Asynchronous
Forward-Bounding for Distributed Constraints Optimization
Amir Gershman, Amnon Meisels and Roie Zivan
Proc. 1st Intern. Workshop on Distributed and Speculative Constraint
Processing (in CP-05), Sitges, October, 2005
A new search algorithm for solving distributed constraint optimization
problems (DisCOPs) is presented. Agents assign
variables sequentially and propagate their assignments asynchronously. The
asynchronous forward-bounding algorithm (AFB) is a distributed optimization
search algorithm that keeps one consistent partial assignment
at all times. Forward bounding propagates the bounds on the cost of
solutions by sending copies of the partial assignment to all unassigned agents
concurrently. The algorithm is described in detail and its correctness proven. Experimantal evaluation shows AFB outperforms synchronous
branch and bound by many orders of magnitude, and
reveals a phase transition as the tighness of the
problem increases. This demonstrates that asynchronous forwardbounding
has an analogous effect to the phase transition that has been observed when
local consistency maintainance is applied to MaxCSPs.
Asynchronous
Backtracking for Asymmetric DisCSPs
Roie Zivan and Amnon Meisels
Proc. 6th Intern. Workshop on Distributed Constraint Reasoning (DCR-05), pp. 148-160, Edinburgh, July, 2005
Distributed constraint satisfaction problems (DisCSPs)
with asymmetric constraints reflect the fact that agents may wish to retain
their constraints private. The set of pairs of values of every binary
constraint is split between the two constrained agents. An asynchronous
backtracking algorithm for asymmetric DisCSPs is
presented. The new algorithm is based on asynchronous backtracking (ABT), but, propagates assignments both to lower priority agents
and to higher priority agents. The proposed ABT_ASC algorithm is proven sound
and complete. The ABT_ASC algorithm is evaluated experimentally on randomly
generated asymmetricDisCSPs. Its performance is
compared to that of the privacy keeping version of ABT, proposed by Brito and Meseguer, which splits the search into two phases. The
ABT_ASC algorithm improves the run-time of the 2-phase ABT by a large factor
with no additional load on the communication network.
Distributed
Navigation in an Unknown Physical Environment
Arnon Gilboa, Amnon Meisels and Ariel Felner
Proc. 8th Biennial Israeli Symposium on Foundations of AI - BISFAI-05 ,
June, 2005
We address the problem of navigating from an initial node to a goal node by
a group of agents in an unknown physical environment, where traveling agents
must physically move around in the environment to discover the existence of
nodes. As a result, agents need to travel in order to
discover paths to the goal node. Agents communicate with a predefined set of
neighbors by exchanging messages. A distributed algorithm, which is run
independently by each agent, is presented. Given the current knowledge of the
agent about the environment and the positions of other agents, the algorithm
instructs the agent where to go
next. The agent then updates its neighboring agents with its new position and
its discovered nodes. An experimental evaluation of the algorithm is presented,
with several different definitions of neighborhoods, on random physical graphs.
Results show that the distributed intelligent behavior of agents generates
spread of knowledge throughout the environment efficiently. Agents reach the
goal node fast and the length of the path that they find is very close to that
of the optimal path.
Dynamic
Ordering for Asynchronous Backtracking on DisCSPs
Roie Zivan and Amnon Meisels
Proc. 11th Intern. Conf. CP 2005, pp.
161-172, Barcelona, 2005
An algorithm that performs asynchronous backtracking on distributed CSPs,
with dynamic ordering of agents is proposed, ABT DO. Agents propose reorderings of lower priority agents and send these
proposals whenever they send ok? messages. Changes of
ordering triggers different computation of Nogoods.
The dynamic ordered asynchronous backtracking algorithm uses polynomial space,
similarly to standard ABT. The ABT DO algorithm with three different ordering
heuristics is compared
to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic, inspired by dynamic
backtracking, is found to outperform static order ABT by a large factor in both
run-time and network load.
Concurrent
Dynamic Backtracking for Distributed CSPs
Roie Zivan and Amnon Meisels
Proceedings CP-04, pp. 782-7, Toronto, September 2004(LNCS #3258)
A distributed concurrent search algorithm for distributed constraint
satisfaction problems (DisCSPs) is presented.
Concurrent search algorithms are composed of multiple search processes (SPs)
that operate concurrently and scan non-intersecting parts of the global search
space. Search processes are generated dynamically, started by the initializing
agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic
backtracking (DB). As a consequence of DB, a search
space scanned by one search process can be found unsolvable by a different
search process. This enhances the efficiency of the ConcDB
algorithm. Concurrent search is an asynchronous distributed algorithm and is
shown to be faster than asynchronous backtracking (ABT). The network load of ConcDB is also much lower than that of ABT.
CP04
Tutorial: Distributed Constraints Satisfaction Algorithms, Performance, Communication
Amnon Meisels
Constraints Programming 2004, Toronto, September 2004 Presentation
(ppt)
Distributed constraints satisfaction problems (DisCSPs) have been studied for over a decade. The first distributed search algorithm was asynchronous backtracking, which is still the most studied. In the last few years, several new families of distributed search algorithms have been investigated and comparative experimental studies are encouraging. A natural extension to distributed constraints satisfaction is distributed constraints optimization. Stochastic search algorithms for solving DisCSPs, such as Distributed Breakout, have appeared a few years ago. Distributed stochastic search algorithms are naturally suitable for solving distributed optimization. In contrast, asynchronous search algorithms for distributed optimization have been proposed in recent years. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of algorithms on DisCSPs. This has been shown in an experimental study that induced random delays on messages sent among agents. In order to study the impact of message delays on DisCSP search, a model of delays in terms of concurrent performance measures is needed. Within such a model, the behavior of families of search algorithms in the presence of delays is varied and interesting. An important feature of the distribution of the problem among agents is their ability to maintain some privacy. Agents may not want to share their values with other agents, and they may wish to keep constraints as private as possible. Some recent work has resulted in versions of asynchronous backtracking that maintain both privacy of values and privacy of constraints. Other investigations of privacy in DisCSPs focused on the analysis of information gain by studying a welldefined problem, that of scheduling meetings of agents.
Maintaining
Dominance Consistency
Igor Razgon and Amnon Meisels
Proceedings CP-03, pp. 945-50, Kinsale, Ireland, September 2003 (LNCS #2833).
A new type of local consistency, k-dominance consistency
is presented. It is a generalization of symmetry breaking via dominance
detection defined in [Fahle2001]. We present a method for achieving 1-dominance
consistency. We propose an algorithm for maintaining 1-dominance consistency
combined with a lookahead constraint solver. We prove that the algorithm does
not affect the superiority relation between lookahead constraint solvers
defined in [Kondrak1995,vanBeek1998]. We then show how
can a constraint solver acquire additional information during search to make
maintaining 1-dominance consistency more effective.
Synchronous vs
Asynchronous search on DisCSPs
Roie Zivan and Amnon Meisels
Proceedings EUMAS, Oxford, December 2003.
Distributed constraint satisfaction problems ($DisCSPs$)
are composed of agents, each holding its variables, that are connected by
constraints to variables of other agents. There are two known measures of
performance for distributed search - the computational effort which represents
the total search time and the number of messages sent which represents the
network load. Due to the distributed nature of the problem, the behavior of the
experimental environment is extremely important. However, most experimental
studies have used a perfect simulator with instantaneous message delivery. The
present paper investigates two families of distributed search algorithms on DisCSPs, Synchronous and Asynchronous search. Improved
versions of the two families of algorithms are presented and investigated.
The performance of the algorithms of these two extended families is measured on
randomly generated instances of DisCSPs. The results
of the investigation are twofold. First, the delay of messages is found to
deteriorate the performance of asynchronous search by a large margin. This
shows that a correct (and realistic) experimental scenario is important.
Second, when messages are delayed, synchronous search performs better than
asynchronous search in terms of computational effort as well as in network
load. It turns out that asynchronous search fails to use its multiple computing
power to an advantage.
Comparing
Performance of Distributed Constraints Processing Algorithms
Amnon Meisels, Eliezer Kaplansky, Igor Razgon and
Roie Zivan
Proc. Workshop on Distributed Constraint Reasoning, in AAMAS-2002, pp.
86-93, Bologna (July 2002)
Search algorithms on distributed constraints satisfaction problems, DisCSPs, are composed of agents performing computations
concurrently.
The most common abstract performance measurement that has been universally
adopted for centralized CSPs algorithms is the number of constraints checks
performed. However, when it comes to distributed search, constraints checks are
performed concurrently by all agents on the network
and therefore a simple measurement of constraints checks is not adequate any more. In order to be able to
compare the behavior
of different algorithms, there is a need for a new distributed method to
measure the search effort of a DisCSP algorithm.
A model for measuring concurrent constraints checks on distributed constraints satisfaction problems (DisCSPs) is presented.
The advantages of the proposed model are clarified by a series of simple constraints network examples. An algorithm for computing the
proposed measure, the {\em cumulative cost algorithm (CCA)}, is presented. A formal correctness proof of the CCA algorithm, according to the proposed model for concurrent constraints checks (CCCs) is presented.
Iterative
Restart Techniques for solving Timetabling Problems
Amnon Meisels and Eliezer Kaplansky
Europ. Jou. OR, special issue on Timetabling, Vol. 153, pp. 41-50, 2003.
Restart techniques for randomizing complete
search algorithms were proposed recently by Selman and Gomes, for solving hard
combinatorial problems. A new iterative algorithm that uses restart techniques
is proposed, and its behavior analyzed on random timetabling problems. Employee
timetabling problems (ETPs) can naturally represented
by constraints networks for real world instances which are large and difficult.
Complete search algorithms, even with good heuristics are unable to solve large
enough instances of ETPs. In fact, several local search techniques have been
proposed in the past decade for solving timetabling problems. In particular, it has been shown that local search can
efficiently solve large ETPs.
Random instances of ETPs that was generated based on real world ETPs are used to test the
proposed iterative restart algorithm - GIRA. The two main parameters of GIRA
are pointed out and investigated: the initial cutoff value for restart and the
number of idle iterations. For random sets of a large range of hardness of
ETPs, the successful values of these two parameters tend to be surprisingly
low. We conclude by recommending an optimal range of values for the initial
cutoff and demonstrate experimentally that the number of idle iterations is of
little consequence.
Assigning Resources
to Constrained Activities
Amnon Meisels and Ela Ovadia,
Proc. PATAT-2000, pp. 303-13, Konstanz, Germany, August 2000 (LNCS #2079).
Resource allocation problems are naturaly represented as constraint networks (CN),
with constraints of inequality among activities that compete for the same
resources at the same time [Faltings and Choueiry 94]. A new algorithm for solving networks of RAPs
is described and its detailed behavior is presented on
a small example and on a real world problem. The
proposed algorithm delays assignments of resources to selected activities and
processes the network during the assignment procedure, to select delays and
values. The proposed algorithm is an enhancement to standard intelligent
backtracking algorithms [Prosser 93], is complete and performs better than two
former approaches to solving constraints networks of resource allocation (cf.
[Regin 94,Faltings and Choueiry
94a+b]). One way to view the new resource assignment algorithm (RAA) is in the
form of a dynamic variable ordering heuristic. The differences between RAA and
former preprocessing heuristic methods for resource allocation problems is
discussed in the context of a simple example and a realistic problem of employee
assignment.
Bayes Networks for
Estimating the Number of Solutions to a CSP.
Amnon Meisels, Solomon Eyal Shimony, and Gadi Solotorevsky,
Anal. of Math. & AI, 28, pp. 169-186, 2000. The
problem of counting the number of solutions to a constraint network (CN) (also
called constraint satisfaction problems, CSPs) is rephrased in terms of
probability updating in Bayes networks. Approximating the probabilities in
Bayes networks is a problem which has been studied for a while,
and may well provide a good approximation to counting the number of
solutions. We use a simple approximation based on independence,
and show that it is correct for tree-structured CNs. For other CNs, it
is less optimistic than a spanning-tree approximation suggested in prior work.
Experiments show that the Bayes nets estimation is more accurate on the
average, compared to competing methods (the spanning-tree, as well as a scheme
based on a product of all compatible pairs of values). We present empirical
evidence that our approximation may also be a useful (value ordering) search
heuristic for finding a single solution to a constraint satisfaction problem.
Solving
Employee Timetabling Problems by Generalized Local Search
Andrea Schaerf and Amnon Meisels .
Proc. Italian AI, Bologna, May 1999
Employee timetabling is the operation of assigning employees
to tasks in a set of shifts during a fixed period of time.
We present a general definition of employee timetabling problems (ETPs) that
captures many real world problem formulations and
includes complex constraints. We investigate the use of several local search
techniques for solving ETPs. In particular, we propose
a generalization of local search that makes use of a novel search space that
includes also partial assignments. We describe the distinguishing features of
this generalized local search that allows it to navigate the search space
effectively. On large and difficult instances of real world ETPs, where
systematic search fails, local search methods perform well and solve the
hardest instances. According to our experimental results on various local
search techniques, generalized local search is the best method for solving
large ETP instances.
CSPs with
Counters: a Likelihood-Based Heuristic. Gadi Solotorevsky, Solomon
Eyal Shimony and Amnon Meisels.
Jou. Exp. & Theo. AI
, 10 , pp. 117-129, 1998.
Numerous applications of constraint satisfaction problems
(CSP) exhibit global constraints. Such constraints abound in resource-allocation-type
problems, as well as in other domains. The form of global constraint we
consider are {\em counter constraints}, which limit
the number of variables that may be assigned particular
values. This paper integrates counter constraints with the constraint
satisfaction problem (CSP) paradigm in a novel manner. Counter constraints are
problematic for most heuristics, which are local in scope. We suggest a useful
heuristic for value ordering during search, based on estimated likelihood of
solution, and show its advantages empirically. The heuristic is useful for
standard CSPs, as well as ones with counter constraints, where it approximates
the number of solutions for a particular value assignment to a variable.
Counter constraints can be represented in standard CSPs, at a cost. We analyze
the cost, show how a counter can be represented as a linear number of binary
constraints, and show experimentally that even with the optimal reduction it is
better to represent counters explicitly rather than as a set of local
constraints.
A Heuristic
Incremental Modeling Approach to Course Timetabling
Don Banks, Peter van Beek and Amnon Meisels .
Proceedings of AI'98 Canada, August 1998 The
general timetabling problem is an assignment of activities to fixed time
intervals, adhering to a predefined set of resource availabilities. Timetabling
problems are difficult to solve and can be extremely time-consuming without
some computer assistance. In this paper the application of constraint-based
reasoning to timetable generation is examined. Specifically, we consider how a
timetabling problem can be represented as a Constraint Satisfaction Problem
(CSP), and propose an algorithm for its solution which
improves upon the basic idea of backtracking. Normally, when a backtracking
routine fails to find a solution, there is nothing of value returned to the
user; however, our algorithm extends this process by iteratively adding
constraints to the CSP representation. A generalized random model of
timetabling problems is proposed. This model creates a diverse range of problem
instances, which are used to verify our search algorithm and identify the
characteristics of difficult timetabling problems.
FlexiMine - A Flexible Platform for KDD Research and
Application Development
R. Ben-Eliyahu-Zohary, C. Domshlak,
E. Gudes, N. Liusternik, A.
Meisels, T. Rosen, S. E. Shimony .
a revised version from Proceedings of KDD-98 New York, August 1998
FlexiMine is a KDD system designed as
a testbed for data-mining research, as well as a generic knowledge discovery
tool for varied database domains. Flexibility is achieved by an open-ended
design that enables integration of existing data-mining algorithms, new locally
developed algorithms, and utility functions such as visualization and
preprocessing. The system interfaces an INFORMIX database server via SQL
queries and thus support for new databases is simple and clean. With a view of serving remote, as well as local, users, internet
availability was a design goal. Fleximine is
implemented in Java and hence we can run the user-end of the system either as a
Java applications or (with some limitations on the
user) as a Java applet. This paper reviews the architecture, design and
operation of FlexiMine and presents new ideas
incorporated in the data-mining algorithms (Association rules, Decision trees,
Bayesian knowledge-bases and Meta-queries).
Experiments on
Networks of Employee Timetabling Problems.
Amnon Meisels and Natalia Lusternik.
Proc. PATAT97, Toronto, August 1997 (LNCS #
1408 pp. 130-142)
Constraint networks (CN) that represent employee timetabling
problems (ETP) are described and a testbed of random ETP CNs is designed. The
natural representation of ETPs as CNs has variables representing working shifts
and values representing employees that are assigned to work-shifts. In this
representation, ETPs have binary constraints of non-equality (mutual
exclusion), the networks are non uniform, and
variables have different domains of values. There is also a typical family of
non-binary constraints that represent finite capacity limits. The random
testbed of ETPs includes all of the above features and
is solved by standard constraint processing techniques, such as forward
checking (FC) and conflict directed backjumping
(CBJ). The set of ETP CNs is characterized by the average intersection of
domains, together with the usual parameters of CNs (i.e. the density and
tightness of constraints $p_{1}, p_{2}$). One major
result is that the ETPs exhibit a strong change in difficulty (as measured by
consistency checks) for small values of intersection among domains of
variables. Non binary constraints of finite capacity
are part of the experimental testbed. An enhanced FC-CBJ search algorithm is
used to test these random networks and the experimental results are presented.
Distributed
Constraint Satisfaction Problems - A Model and Application.
Gadi Solotorevsky, Ehud Gudes and Amnon Meisels.
Preprint, October 1997
A canonical model for distributed constraint satisfaction
problems (DCSP) is presented and algorithms for processing constraints on a
DCSP are described. The central idea behind a constraint network that is {\em given} as a DCSP is the existence of large differences
between the cost of {\em message passing} among
different components of a DCSP and the cost of local consistency checks {\em within} each component. Therefore, algorithms which
operate in a multi-agent environment to solve these problems are required to
take into consideration these differences. Four basic algorithms for solving
DCSPs that are sound and complete are proposed. Two of these algorithms are
sequential and two algorithms operate in parallel and are inherently
distributed. The behavior of the proposed algorithms was tested by generating
and solving a set of random DCSPs (for a variety of parameters of density and homogeneity ). The results show the superiority of the
parallel algorithms when the cost variances are large. A series of enhancements
of the basic algorithms are presented. These enhancements permit both to extend
the scope of the algorithms and their performances. To motivate and test the
approach we present a real life problem dealing with
Nurses timetabling and transportation in a large multi-department hospital. We
compare the results of solving this problem by using the basic algorithms, the
enhanced algorithms, and the sequential CSP algorithms.
Combining Rules
and Constraints for Employee Timetabling.
Amnon Meisels, Ehud Gudes and Gadi Solotorevsky.
Intern. Jou. Intell.
Sys., 12 , pp.
419-439, 1997.
Employee Timetabling Problems (ETP) are all around us. One possible
approach for solving ETPs is to use constraint processing techniques. Another
approach is to model human knowledge which is commonly used for solving such
problems into knowledge-based systems for timetabling. It is difficult to
represent the complex constraints of timetabling explicitly in constraint
networks. On the other hand, knowledge-based representations of constraints are
implicit and cannot support most of the heuristics of constraint
based processing that have been developed over the last decade. The
present paper presents an approach to representing and processing employee
timetabling problems by a combination of explicit representations of some
constraints in the network and rule-based processing in which heuristics for
generic constraints of ETPs are embedded. This mixed-mode approach has been
implemented in the form of a software package for defining and solving real
world ETPs. A general description of the design and organization of this
software tool is given. %Examples of a family %of real world ETPs are followed
all through the presentation and are quantitatively %used to explore the
constraint network (CN) parameters of these problems. Results for solving a
typical real world employee timetabling problem is
presented and a comparison with the use of standard CSP techniques is made.
Thu. Sep. 20 10:25:29 IDT 2001