CSCE 782: Problem Set 1

Due: Monday, 17 September 2007 @2pm

Email me your .nlogo file.

Figure 1: The basic idea behind the nagging algorithms, taken from Segre's paper.

Nagging Algorithms for Distributed Constraint Optimization

You will implement a nagging strategy to solve the distributed constraint optimization problem using the branch and bound algorithm from Figure 2.12 in our text book.


The nagging idea is described in the following paper:

You really only need to read the first two sections of the paper. The rest of the paper shows how they apply nagging to A* and Davis-Putnam, which you won't be using for this PS. Instead, you will extend branch and bound to support nagging.


The first to note is that the assumptions in nagging are different from those in Chapter 2. Specifically, while the textbook assumes that each variable is an agent, in the nagging algorithm this assumption no longer holds. Instead, your agents all know the complete graph and perform parts of the branch and bound search over arbitrary sets of nodes.

Your first step for this problem set is to implement a centralized branch and bound function which solves the constraint optimization problem. That is, start with one of our existing NetLogo models which already solve the DCOP problem, get rid of the algorithm part and replace it with one function which implements Figure 2.12 from the textbook.

Once you have a centralized function then you can start implementing the nagging strategy by creating a fixed set of worker agents which perform parts of the search. You are free to implement the details of the nagging strategy in the way you think will be best, but there are some specific requirements you should obey:

  1. There should be a slider with num-workers which lets the user change the number of worker agents on each run.
  2. There should be a plot of the work performed by each worker, as well as a measure of how much of that work resulted in an Abort.

What we are looking for is a nagging algorithm that

  1. Does as little wasted (Abort) work as possible.
  2. Evenly distributes work among all workers regardless of the number of workers, again, as much as possible.
  3. Has linear speedup in the number of workers: with twice as many workers it finds the solution in half the time.

These are really just a wish list. Do the best you can.

Alternate PS1

YOu can also try to implement Asynchronous Backtracking for graph coloring. There is already an implementation of this algorithm in my netlogo mas page but it does not work anymore under 4.0. It also needs to be updated as it does not use the new links primitives (which should make everything much easier). Note that implementing the hyperesolution rule is also not easy, in fact, I would be happy with just a partial implementation. The current implementation only finds some possible nogoods.

José M. Vidal
Last modified: Wed Sep 5 12:06:15 EDT 2007