Final Project

For the final project you have the option of a programming-oriented or a research-oriented final project. Whichever project you decide to do you must first meet with me to get it approved.

Programming Project

Choose a paper from the AAMAS proceedings (see also my AAMAS 2012 local copy, because their website is down a lot) and implement the algorithm they describe. In many cases you will need to make some simplifying assumptions. The papers discuss in class are especially good choices.

Or, you can also choose to implement any of the algorithms referenced in the our textbook that are not already implemented, or provide better visualizations of existing algorithms (for didactic purpose).

Another, very popular, option is to build a NetLogo simulation of a multiagent problem in a separate domain, one which you are already familiar with, say, because you are doing a PhD thesis on that problem.

Research Project

Your deliverable will be a paper that summarizes exisiting research on a specific topic, with appropriate citations, and
either presents a new algorithm/protocol/etc. along the same lines or organizes these results in a novel way (think "survey paper").

The final paper should be at least 10 pages long. I will be looking to see that you understand the topic at hand and how the various contributions relate to each other. You will be looking at papers beyond the above conferences.


The final projects are due Wednesday May 1.

HW3: Stability in Cooperative Games

We have discussed cooperative games, the core, the nucleolus, and excess. For this homework you will implement a simulation of agents participating in a cooperative game and acting selfishly to join their preferred coalition. The simulation will show how long it takes for the system to achieve a stable solution where no one agent has an excess.

Specifically, your simulation will have number-agents agents, all of which start out in their own coalition, that is, alone.

An agent can have any one of the colors: red, blue, black, green, cyan
An agent can have any one of the shapes: circle, square, triangle

These are assigned randomly on setup.

The value function v(S) is defined as: the number of different colors in the coalition + 3 - number of different shapes - (size of the coalition / 2).

Each time the 'go' button is pressed each agent will: check the value of the coalition where he joins one of the other existing coalitions, for all other coalitions. Of these, he finds the one with the highest value. If that value is bigger than the value of his current coalition then he will leave his current coalition and join the new one. In other words, each agent asks himself: "what would the value be if I joined this other coalition? what about this one? and this one? and so on to find the biggest value. If that value is bigger than his current coalition then he joins that coalition. If the biggest value is less than the value of his current coalition, the agent does not do anything.

The coalitions are represented as fully-connected graphs. That is, an agent has a link to all the other agents in his coalition, and to no one else.

You will then plot the number of agents that change coalition on each tick, the total number of coalitions over time, and a histogram of the current size of coalitions.

Anyway, all this is easier to see in a video:



Email me your finished program by Monday, March 11 @10am.

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.

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.

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.

Final Project

For the final project you have the option of a programming-oriented or a research-oriented final project. Whichever project you decide to do you must first meet with me to get it approved.

Programming Project

Choose a paper from the AAMAS proceedings and implement the algorithm they describe. In many cases you will need to make some simplifying assumptions. The papers discuss in class are especially good choices.

Or, you can also choose to implement any of the algorithms referenced in the our textbook that are not already implemented, or provide better visualizations of existing algorithms (for didactic purpose).

A final option is to build a NetLogo simulation of a multiagent problem in a separate domain, one which you are already familiar with, say, because you are doing a PhD thesis on that problem.

Research Project

Your deliverable will be a paper that summarizes exisiting research on a specific topic, with appropriate citations, and
either presents a new algorithm/protocol/etc. along the same lines or organizes these results in a novel way (think "survey paper").

The final paper should be at least 10 pages long. I will be looking to see that you understand the topic at hand and how the various contributions relate to each other. You will be looking at papers beyond the above conferences.


The final projects are due Wednesday May 1.

HW4: Learning Correlated Equilibria

For this homework you will implement the learning algorithm in this paper by Cigler and Faltings. The algorithm in question allows the agents to reach a correlated equilibrium by using only a learning mechanism, that is, without the need for a separate coordination device.

The game is a broadcasting coordination game. There are N agents and C channels (both sliders), where N >= C. At each time step all agents choose a channel for broadcasting but, due to physical limitations, only one agent can actually transmit on each channel at a time. Thus, if an agent uniquely chooses a channel then he gets a utility of 1, if 2 or more agents choose the same channel they all receive a utility of 0.

You will first solve this problem by having all the agents implement the Q-learning algorithm. Note that there is only 1 state in this game, so the Q-learning will only happen over the actions of the players. Run it for a while and plot the sum of the utilities to see how well they do as a group.

Then, you will implement the algorithm from the paper (use the same NetLogo model, just add a toggle switch so the user can choose between the two). The algorithm is described in Section 2 and works roughly as follows (but, see the paper):

1. At each tick, there is a randomly generated integer (signal), from 1 to K, that all agents can observe. They use this signal in their learning.
2. Each agent keeps a table f(k), for k = 1..K and where f(k) is either the channel the agent will transmit if it sees signal k, or 0 if will not transmit at all when it sees that signal. Table f(k) is initialized to random channels.
3. At each tick, with signal k, the agent transmits on channel f(k). If f(k) = 0 then the agent chooses a random channel to monitor.
4. The agents get their utility based on the collisions. If the agent gets 0 utility then it sets f(k) = 0 with probability p (slider).
5. If the agent was monitoring channel c then if no one transmitted on it the agent will set f(k) = c.

The .nlogo model is due on Monday, November 21 @9am.

HW3: Security Circumvention Games

For this homework you will build an airport security simulation loosely based on the model presented in GUARDS-Game Theoretic Security Allocation on a National Scale. We simplify their model by using only a few simple types of security circumvention techniques but also extend it by taking into account the effects that extra screening has on passenger waiting times.

Your model will have a passenger breed of agent. Each tick corresponds to a minute. The number of passengers that arrive each minute is given by random-poisson 1, a Poisson arrival rate of mean 1. Each passenger has random 3 luggage items with him, where luggage is also a breed. When a passenger arrives he is at the Boarding Pass area of the airport.


There are five areas in the airpot: Boarding Pass (B), Luggage (L), Security scan (S), Gate (G), and Plane (P). The passengers will traverse these in the order, B-S-G-P, while the luggage goes B-L-P.


At each tick the earliest random-poisson 1 turtles to arrive (smallest who) passenger or luggage that is not currently being screened in each area is moved to the next area. When there are 30 passengers and their luggage in P then they leave (die).


Each passenger is really a terrorist with probability terrorist-prob (a slider from 0 to 0.1). Each terrorist can carry out an attack of one of three types: 1, 2, 3. Also, he will do it in one of the areas (B,L,S,G,P) (if L then consider his luggage agent as the one that will perform the attack). The terrorist activates his attach 10 minutes after reaching his target area.


There are also 5 screener agents. The user has the choice of where to place each screener agent and which type of attack they screen for. That is, each screener is at one of the locations and can only identify one type of attack. Use 10 dropdown boxes to let the user pick which area (B-L-S-G-P) and which attack (1-2-3) to give each screener. At each time tick each screener randomly chooses a passenger/luggage in his area and screens him. If the agent is a terrorist with the same attack as the screener then he is marked as caught and removed. Every screening takes random-exponential 5 minutes, during this time the agent being screened cannot move to the next area.


Your simulation will let the user choose which types of screeners to put where and will then simulate a whole day (24 hours) of activity, keeping track of how many terrorists are successful and how many planes take off without incident (if 10 minutes go by on a full plane then it was OK, you can delete all those agents).  This simulation forms the first part of the homework.


In the original GUARDS paper, the terrorists are assumed to know where the screeners are placed. For the second part you will change the behavior of the terrorists so they know where the screeners are placed, and their type, and calculate their best response given this knowledge. In our simplified game this simply means that your terrorists should set their type of attack to be the one that is less often used by the screeners.

This homework is due Monday, October 10 @9am.

HW2: Graph Coloring

For this homework you will implement a simple distributed hill-climbing algorithm and test its behaviors on various graphs. The goal is for you to become proficient at using the NetLogo link primitives and to gain first-hand experience with the problems and benefits of distributed hill-climbing algorithms.

1. Read the link primitives section of the NetLogo manual.
2. Implement a NetLogo model that generates a random graph, by using a simple algorithm: first create num-nodes nodes (a slider), then create num-nodes * edge-ratio edges, each one connected to two randomly chosen nodes.
3. Implement another button which instead generates the graph using preferential attachment. Specifally: first create num-nodes nodes, then create num-nodes * edge-ratio 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.
4. Implement a num-colors slider and randomly color the nodes using that many colors.
5. Implement a layout button which calls one of the built-in NetLogo layout methods to make the graph look pretty.
6. Implement a basic hill-climbing algorithm. On each tick every node looks at the colors of its neighbors and changes its color to one that does not conflict with any. If there is no such color then it will change to one that minimizes the number of constraint violations with its neighbors (min-conflict heuristic). If at any tick none of the nodes changes its color then we stop since a coloring has been found.
7. Add a test button which performs a more extensive test. Specifically, for the given number of nodes and edge ratio, it will generate 100 graphs of random and preferential attachment types and run the hill climbing algorithm, plotting the number of time steps it took to find a solution in a histogram, one for random and one for preferential attachment. You will need to set an arbitrary large number for the 'does not stop' case.

Add your name and describe your results in the model description tab. Email me you .nlogo file by Wednesday September 21 @9am.

HW1: Trackers

Our first project is a simple multiple-tracker multiple-target distributed allocation problem. Since you are learning NetLogo as you do this, I am breaking it up into steps that you can do sequentially while learning different aspects of NetLogo. The final project consists of randomly moving targets that emit 'utility signals' which are captured by the trackers that are near the target.

1. Start by creating a target breed. You will have a slider to choose the number of targets we want to create (100 by default). The setup button will create that many targets. The targets are all circles (set shape "circle")and red.
2. Create the go button and procedure. You will have a regular and a forever version of the go button. The go button makes the targets move randomly. They do this by changing their heading by a random amount (+- 45 degrees) and then moving forward 1.
3. Change the field so that it does not wrap-around (right-click on it then 'edit'). Make the targets bounce off the walls. Search the "Programming Guide" for this bit of code:
   

   if patch-at dx 0 = nobody [
     set heading (- heading)
   ]
   if patch-at 0 dy = nobody [
     set heading (180 - heading)
   ]
   

   which implements bouncing.
   
4. On startup, all patches turn white except 100 random patches turn green. The targets bounce off the green patches.
5. Create a tracker breed, and a slider to chose how many to create (100). The tracker can only see targets that are less than 5 away and follows the nearest one but can only move forward by .8 (towards min-one-of in-radius). Run an experiment with 100 trackers and 100 targets.
6. At every tick, each target emits 1 unit of utility which gets divided equally among all the trackers that are within 5 of it. Add a plot to show the mean utility received by the trackers over time. Run the experiment again for several thousand steps. You should see the mean utility decrease over time.
7. Finally, an open problem, change the behavior of your trackers so the mean utility does not decrease so much. Try not to violate the constraints that the trackers can only see up to a distance of 5 around them, or communicate with anything outside that radius, or any of the other 'physical' constraints of the problem as described.

Notice that, as a system designer, you might be concerned with utility loss, the total utility emitted by the targets that is not harvested by anyone, or you might be concerned with social welfare, that all trackers receive roughly the same utility. On the other hand, as the owner of a tracker you might only be concerned with how much utility your tracker consumes. So, if you want to minimize utility loss but cannot control the actions of the trackers, what do you do? You don't have to answer that for this homework, just think about it.

Update: changed date:This homework is due Wednesday, 7 September @9am, just email me the .nlogo file. Make sure to use "Info" tab to include your name and email, as well as a short explanation of the strategy you used for 7.