Proposed Master Theses - August 2004
The following list of Master Theses is related to the general domain of
Distributed Constraint
Processing. Our DisCSP group of graduate students is active and had
a weekly seminar all through this year (actually continuing in the
summer too). Material is available in the group's homepage http://www.cs.bgu.ac.il/~discsp
and includes papers by the group members on the topics below and
recent and relevant papers by others. The student will need to
read extensively on constraint
processing and
on distributed constraints or take my course "Constraints Processing".
Designing a
Concurrent version of Asynchronous Forward-Checking (AFC)
- Asynchronous forward-checking (AFC)
is an innovative search
algorithm on DisCSPs, that propagates assignments asynchronously. The
original design of AFC was
good enough to beat the ruling algorithm of
asynchronous backtracking (ABT). The core of the thesis consists of
three topics:
- Design a concurrent version of AFC, that uses dynamic splits of
the search space combined with a smart heuristic.
- Experiment with heuristics for triggering splits and with the
impact of message delays on Conc_AFC,
comparing to ABT and to ConcDB.
- Construct theoretical (worst-case) evaluation measures for AFC
etc. and compute them - total number of messages; etc.
Distributed
Local Search for DisCSPs
- Local search (or stochastic search) is very common for
solving complex optimization (or satisfaction) problems. It is
commonly used for solving large CSPs or real world timetabling
problems. For the distributed constraints satisfaction problem
(DisCSP), very few versions of local search have been proposed . The
common feature of existing distributed local search algorithms is
their synchronization. In order to make decisions about improving
moves they all need to work in coordinated steps. The central
problem in this thesis is to construct an asynchronous local search
algorithm for DisCSPs. Roie and me have a couple of ideas that seem
right and have to designed into a well behaved algorithm. This topic
leads naturally into questions of distributed optimization and
competition with existing complete DCOP algorithms.
There is a natural domain for evaluating distributed optimization
algorithms - SensorCSP. A family of distributed problems in which
sensor/agents have to track targets in a distributed (but cooperative)
way. A simulator of SensorCSP, or another interesting, large,
real-world problem will have to be designed and constructed. All
algorithmic ideas will be compared to existing local search algorithms
on this family of problems.
SensorCSP
and Sensor Networks
Sensor networks are attracting a lot of general attention in
distributed computing. A specific problem of sensor network that was
proposed for DisCSP modeling and study has resulted in the SensorCSP
model. Very few DisCSP search algorithms have been implemented for
SensorCSP, let alone evaluated. A central challenge is to widen the
scope of SensorCSP, to a general sensor network distributed search
problem. The range of problems is wide. From detection (i.e. the
existing SensorCSP), to navigation and exploration. This thesis will
start from a survey of Sensor Networks literature and from there it
will construct the search problem at its center.
-