Distributed Breakout

Distributed Breakout is one of my favorite algorithms because the basic technique is so simple, so easy to distributed, and, while lacking an optimality guarantee, in practice it is surprisingly effective (unreasonably so!)

Here is a quick implementation in NetLogo:

Asynchronous Backtracking

Another approach to solving distributed constraint satisfaction problems is via search, as with the Asynchronous backtracking algorithm:

HW2: Distributed Breakout Analysis

In this homework you will do a bit more NetLogo programming and explore both NetLogo's ability to analyze a simulation as well as Distributed Breakout's limits at solving problems.

You will start by downloading my breakout.nlogo file, which ia a slightly updated version of the one I wrote in this video. Note that this is a simplified version of breakout since each link has only one weight, whereas in the real algorithm each node has a weight associated with each edge (so, two weights per edge). But, I think the basic functionality is the same, at least for the purposes of this exercise.

This homework will have several parts.

1. Graph Generation

In the code I gave you, when you click 'setup' the graph generate is a random graph: num-edges pair of nodes are chosen at random and an edge attached between them (if one was already there, no edge is added). You will modify the code to also generate graphs that use preferential attachment.

Specifically, first create num-nodes nodes, then create num-nodes * edge-ratio (a number between 1 and 10, from a slider) edges, each one created by picking two nodes chosen with a probability proportional to their degree (number of incident edges). For example, if there are 3 nodes, one with two edges and the other two with one edge each (the graph is a line) then the one with two edges gets chosen with probability 2 / 4 = 1/2, while each other two nodes is chosen with probability 1/4. The denominator is always the total number of edges and the numerator is the degree for that node.

You will add a switch to your model to select between the two topologies (random vs. preferential attachement).

2. Graphs with a Coloring

You will then add a toggle switch to your model solvable? If it is false then you generate the graph as before. But, if it is true then the graph you generate will have a solution.

The way you ensure your graph has a solution is simply by giving each node a random color to start with and then making sure you only connect it to other nodes that have a different color. You will need to make modifications to the two previous graph-generation methods.

3. How good is Breakout Anyway?

In this last part you will implement some methods that will plot some nice line charts to show how well breakout works.

The first button will plot generate a plot where the x-axis is the number of nodes (say from 5 to 50, or some suitable range) and the y-axis is the average number of steps (over 10 runs) that breakout took to find the solution. In this test all graphs generated are guaranteed to have a solution (using the method from step 2).


The second button will generate a plot where the x-axis is the edge-ratio, from 1 to 10 and then plot the average number of constraint violations (over 10 runs) after running breakout for 10 steps. The graphs generated for this test will be determined by the settings in the buttons.

Email me the .nlogo file by Monday, February 11 @10am.

Filtering and Hyper-Resolution Algorithms

Today we discussed the Filtering algorithm. Below is a simple implementation in NetLogo:



And, we also discussed the Hyper-resolution rule:

HW1 Solution

There are many possible solutions to the first homework, and the goal was not to find the best solution but just to get you started doing some NetLogo programming. Still, I played around with the problem for a bit and this program is the best I could come up with. If you move the cone-radius slider back and forth you will see different behaviors, as I demonstrated in class today.

Constraint Satisfaction: Centralized and Distributed

On Monday we will start the next chapter which covers Distributed Constraint Satisfaction and Optimization algorithms. The videos below cover some of this material:


A straight-forward way to solve a Constraint Satisfaction problem is via Depth-First Search:



This is how it looks like when you implement DFS in NetLogo:

Partially-Observable Markov Decision Processess

On Wednesday's lecture we discussed POMDPs. Here is a quick review:

Value Iteration in NetLogo: Finding Optimal Policies for Markov Decision Processes

On Wednesday I will talk about policies and the Value Iteration algorithm.

In the video below you can watch me implement the value iteration algorithm in NetLogo.


If that is too long to watch (it is!) then the one below gives you an overview of the finished implementation.

HW1: Single File

The first homework is a fun simple challenge to get you started learning NetLogo. You will implement a model where the turtles all form a single line (one after the other) that is constantly marching. That is, you will:

1. Set the world to be a torus.
2. Make your 'setup' button create 'num-turtles' (sliders) all in randomly chosen locations.
3. Each turtle has to behave autonomously and can only change its heading or move forward 1.

I am looking for a single line, a queue, with even spacing between each turtle. You will find that your first efforts lead to some turtles moving on top of each other. Try to spread them out.

Also, try not to solve this centrally (by having the observer calculate the exact position each turtle should be, based on their 'who' number). Instead, imagine each turtle is a person, but no one can talk to anyone else. How would people form a single line?

Email me your final .nlogo file, making sure to put your name and email in the 'Info' tab, by Monday, January 28 @10am.

Agent-Based Modeling Tools

I chose to use NetLogo for this class because it lets us build models very quickly without having to worry about all the graphical, GUI, or plotting code. There are many agent-based modeling libraries and platforms out there. NetLogo is the best at getting a novice from knowing nothing to having fun with his custom-built model.

The Mason Java library is good for large-scale simulations, of the type you would run on a 'supercomputer'. The Repast Java library and IDE is another popular library that integrates with eclipse. Obviously, you have to know Java to use either one of these.

NetLogo Tutorials

On Wednesday's lecture I will give a quick introduction to NetLogo. You should install it and start learning how to use it. The best way is to go to "Help->User Manual" and read the whole thing. I also have some video tutorials which you might find useful, starting with the ones below.

All of the homeworks consist of you writing a NetLogo program that implements a given algorithm or problem, starting with the first one, so, you will want to get proficient fast.










The NetLogo models page has the models that implement the algorithms in the book. These are good for you to play with (change paramaters/code) and get a better understanding of the algorithm and emergent behavior of the system.

Utility Theory

Our first meeting is on Monday. On that day we I will be talking about the class, the history of multiagent systems, and getting started on the first chapter of our textbook.

The first chapter talks about utility functions:


Markov Decision Processes


and Value Iteration