Distributed Constraints

On Friday we will start the next chapter which is concerned with constraint satisfaction and optimization. A lot of real-world problems can, in part, be reduced to a distributed constraint satisfaction problem.

Farmers and Cows

You can grab a copy of the model I built in class. For fun, see if you can make the cows die of starvation and reproduce when well fed.

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.

Agent Based Models and the Open ABM

Agent Based models are used in many other scientific disciplines and the techniques, both programming and mathematical, that you will learn in this class can be used in many domains. The Open ABM consortium is a place where scientists from various disciplines can share their models and experiences in building models. They can also learn from each other. You should browse their model selection to see the range of ABMs that others have built, and maybe get some inspiration for your final project.

Multiagent Models

We start the semester with a quick historical overview of the field and move on to multiagents models. We use the word model in its scientific sense to mean a mathematical abstraction that captures some aspects of real-world phenomena. You should read the first chapter (Models) of the textbook.

Fall 2011 Class

This blog will now become the official site of my multiagent systems class.

Check out our syllabus for grading and other information. The class will follow my textbook but you can also consult the Shoham and Leyton-Brown textbook for another view of the same material. Once we finish the book we will spend a few weeks going over recent publications in the field.

I like to focus on algorithms and agent-based modeling so, to give you a hands-on experience, we will be using NetLogo. Namely, most of the problem sets involve implementing a multiagent model in NetLogo. You can see my own gallery of netlogo models for the type of work we will be doing.

If you are interested in this type of research, check out my papers.