Amnon Meisels
... with Sari at Bab'el Dunia ...
my Kids
(from Back...)
and
Full faces
am@cs.bgu.ac.il
Research interests
Employee Timetabling Problems - ETPs
Timetabling by constraint processing
Distributed Constraint Processing
The general area of
constraints processing is at the center of my research. A particularly hot topic
that is central to my group on
constraints processing is that of
distributed constraints Roie,
Michael, Amir, Moshe, Tal and
me are continuing a long trip of investigation of
distributed
constraints processing, or distributed constraint satisfaction problems
(DisCSPs), that started three years ago. The unique aspect of DisCSPs is that they combine search algorithms with concurrency. Constraint
satisfaction problems have served for two decades as a cristal clear
laboratory for search algorithms, due to the unique clarity of the
problem definition - Vriables;
Domains; (well-defined) Constraints. Our group's work in
the last four years has built on the clarity of CSPs and added to it
the emphasize on all aspects of concurrency - concurrent algorithms; concurrent measures
of performance; concurrent heuristics.
Our first year produced two
new algorithms:
*
Dynamically Ordered Distributed Forward
Checking (DODFC), which includes dynamic
variable ordering on DisCSP search
* A
parallel
backtrack search algorithm on DisCSPs that performed better
than
the classical asynchronous backtracking algorithm of Yokoo
In addition we defined a
correct distributed model for measuring
performance of search algorithms on DisCSPs, that uses an algorithm for
counting
non-concurrent constraints checks
(NCCCs).
The
second year of research in DisCSPs has
produced a new
search algorithm, that performs forward checking asynchronously while
searching the
search space sequentially. The new algorithm is called Asynchronous
Forward
Checking (AFC).
The parallel BT algorithm has
been improved to include dynamic splitting of the search space and has
been termed accordingly Concurrent
Backtracking (ConcBT). Most important, once one
learns how to measure concurrent performance of search algorithms on
DisCSPs one can model delays in
message delivery. This is a crucial problem - how do distributed
algorithms on DisCSPs behave in the presence of message delays ?
We have designed an asynchronous simulator for running DisCSP search
and have started experimenting with message delay.
During the third
year, 2004, we have produced advances in three different directions.
The concurrent search algorithm has been improved to include dynamic backtracking and became ConcDB.
The behavior of three families of algorithms has been studied under
random message delays and the study produced very interesting results.
Algorithms that use a single search process are affected quite badly by
random message delays and the effect grows with average delay size.
This applies to asynchronous single search algorithms, such as ABT, as
well as to synchronous single search algorithms. In contrast,
concurrent search that uses multiple search processes concurrently
experiences a relatively small effect of random message delay and as
the size of delays grows its performance stays almost constant (Msg_Delay). Research into privacy has produced a paper
on the relation between adding
information and the efficiency of search on DisCSPs. This result
also analyzed in detail the general distributed meeting scheduling
problem (DisMSP).
Last year was the fourth
and most successful of our group's intensive research on
DisCSPs. We have ventured into
additional domains. We have designed a
first search algorithm for DisCOPs (Distributed Constraint Optimization
Problems), that uses Asynchronous Forward Bounding (AFB). It turns out that
similarly to asynchronous forward-checking, for DisCOPs a coordinated
search algorithm that uses asynchronous forward bounding improves the
performance of asynchronous optimization search by a large margin. The
main result, showing the advantage of AFB over ADOPT is being submited
to ECAI in February. A very interesting result, establishing a deep
understanding of constrained search, is that the standard (by now
classical) Asynchronous Backtracking - ABT
- algorithm of Yokoo, can be modified to include dynamic variable
ordering. Enabling ABT to include dynamic variable ordering is a
notable result and has won us the best
paper award of CP-05. The award
establishes the acceptance of research on distributed constraints, by
the constraints satisfaction community.
Another study of privacy aspects of DisCSP search has proposed a search
algorithm for Asymmetric DisCSPs, which keeps
the privacy of constraints (i.e. asymmetric). This is an extension of
an algorithm for asymmetric DisCSPs that was proposed by Meseguer and
Brito in 2003. Another initial study of privacy deals with complete
(cryptographic) security for distributed search on DisCSPs and is
ongoing work of Roie Zivan and Kobbi Nissim.
There
are currently 3 PhD
students and 2 Masters students that are working on DisCSP and TTP
with me. The
current activities can be seen on the DisCSP homepage that
includes the weekly seminars and pointers to resources on distributed
constraints.
A special topic of interest is the connection
between
my research on timetabling problems and my research on distributed
constraints. This produced methods for solving distributed timetabling
problems, that we
term Scheduling Agents (SAs). Eliezer's research on SAs
addresses the problem of complex local CSPs and simple
constraints between agents. As a real world example we take scheduling
agents (SAs)
that generate timetables of nurses in wards in a hospital. The
constraints
between timetables arise from the need to provide transportation to
nurses
of several wards at the end of each shift. Currently, we are
investigating
the distributed timetabling problem of departmental schedules at
BGU.
Within
standard
constraints processing, we have developed a few search algorithms that
use extensive pruning techniques. The main new method can be thought of
as an extension of the recent work on dominance. Igor and me have
designed a lookahead method that constructs a Resposibility-Set
during search and prunes the search space during backtracking. The
paper has appeared in two workshops and is now being revised for the
Constraints journal. Another result that we are now in the process of
publishing is that ideas arising in theoretical work on search can
actually be formulated into good practical search algorithms. Our case
addressed the pure theoretical result on using "double-assignments" in
order to reduce the worst case complexity of the overall search
process. We termed our proposed algorithm Reduced Branching Factor search
and have shown that it results in a large factor of improvement over
the best versions of CSP search algorithms.
Some of my research topics can
be viewed in more
detail at additional locations - the Homepage of Employee Timetabling includes standard
definitions of ETPs, constraints,
representation of problems, file structure, etc.
Recent Publications
Master theses
on Distributed Constraints
Papers on
Cooperative Search in Unknown Environments
Address
Department of Computer Science
Ben-Gurion University
Beer-Sheva 84 105, ISRAEL
Phone: +972-8-6461622 (office) Fax: +972-8-6477650
Email: am@cs.bgu.ac.il
Last updated: Wednesday, February 20, 2002