MiniProject - Distributed Constraints Processing
Fall  2003 Sylabus   Instructor :  Amnon  Meisels

General :   Distributed constraints satisfaction problems started to attract attention, especially distributed search algorithms on DisCSPs, in the last decade. DisCSPs are composed of a set of Agents connected by constraints. Agents cooperate by exchanging messages reporting assignments to their variables, or refuting assignments of other agents that conflict with their own assignments. The goal of the distributed algorithm, run by all agents, is to find a globaly consistent assignment to the variables of all agents. 

   The main goal of the Mini Project is to write a Simulator for a distributed application, Meeting Scheduling, implementing distributed search algoithms for  Agents. All programming will be done in Java.

   Both  centralized and distributed constraints networks will be introduced in class. Algorithms and heuristics will be described and their implementations discussed. The design of the Simulator and its main modules will be distributed among pairs of students and discussed extensively in class. The design that will result from the class design will be implemented by the teams.

Classes:  Wed. 14:00-16:00  room   109/34

The Teams:

1.  Sagi Ben-Akiva; Itamar Avni; Eran Shteinmetz; Maya Formanski; Asnat Etgar; Asaf Kutner; Keren Dotan
2.  Arie Yelovicz; Saar Samocha; Reut Navon; Asaf Levi; Amir Raban; Dror Banayan; David Sabag
3. Leonid Sudakov; Maxim Stolier;  Yakov Lacher; Alon Klein; Alexander Galperin; Sergey Pankratov

Topics in Class:

  1. Introducing Constraints Networks and Search Algorithms (week 1-2)
  2. Distributed Constraints Networks
    1. What are DisCSPs - a static search algorithm
    2. Asynchronous search algorithms (week 3)
    3. Comparing algorithm behaviors - simulator
  3. Meetings Scheduling - the problem and domain (week 4)
        A paper will be presented in class by 2-3 students (for a bonus), to initiate the definition of the Meetings Scheduling project for the teams.
  1. Presentations of the design and implementation of the teams (week 6; week 8; week 10)


Project : The main programming assignments will be distributed among teams. Pairs within the different teams will either implement a distributed algorithm or a random problem generator and the experiments, or the graphic monitor that interfaces the run of the simulator. Marking will be based on the teams/pairs design and implementation and presentations.  

  Marks: 
proposal -  December 17  -  10%;
Improved Design -  December  31 -  10%;
Prototype  -  January 14 -  30%;
Project + Final paper -  February 16-17 -  30% + 20%

Detailed Marking:
* 5 points "factor" added to all marks

ID
 Proposal (10)
 Design (10)
 Prototype  (30)
 Project +  Paper  (50)
 Total
33973397
 8
 8
 27
 48
 91
34323493
 8
 7
 25
 47
 87
33756891
 8
 9
 28 48
 93
34460667
 8
 7
 25
 48
 88
307716191
 7
 7
 26
 48
 88
35836923
 8
 7
 25
 47
 87
35719145
 8
 9
 28 48
 93 + 3 = 96
36351260
 8
 10 28
 47
 93
52821204
 7
 7
 24
 48
 86
43163963
 8
 7
 26
 47 88
38696365
 8
 10 28
 47
 93
308780154
 7
 6
 25
 45
 83
303841712
 7
 7
 26
 48
 88
21761697
 8
 7
 26
 47 88
11592565
 8
 8
 27
 48
 91
313644783
 7
 6
 25
 45
 83
31564172
 8
 7
 25
 48
 88   + 3 =   91
34054874
 7
 7
 24
 48
 86
35929959
 8
 9
 28 48
 93
32911786
 8
 8
 27
 48
 91

 Prototype sessions:
Team #1:
a. Experiments generation -  the user can select sets of problems with no option to
            select the parameters of the sets (-2); for a single problem, too many parameters
            need selection (-2);  no option for sets of experiments on  selected parameters
            and selected statistics (-1)
b. Algorithm                     - messages are delivered immediately, which generates a
             completely synchronous "behavior" (-2); does not deliver run-time information
             to UI, like rate of success, number of steps, etc. (-1)

c. User Interface               - no explanation/selection of parameters to user (-2); no presentation
             of run-time behavior (-2); no graphical summary to a set of experiments (-1)

Team #2:
a. Experiments generation - fixed number of meetings per agent (-1); imposes on the user a very                         complex experiment (-1)
b. Algorithm                     - messages are delivered immediately and agents are run in a fixed
            order, which generates a completely synchronous "behavior" (-2);
c. User Interface               - No run-time information on number of steps (-1); no option for user
             to select a flexible family of problems (-3)

Team #3:
a. Experiments generation - the prototype contained no option for selecting any parameter (-3);
             the specific family of problems selected is too trivial (-3);

b. Algorithm                     - was written just for the extremely limited case generated (-3); not
             delivering enough measures (# of messages etc.) to the UI (-2)

c. GUI                              - no run-time parameters of interest (-2); no selection of experimental
             parameters for the user (-2)