Wednesday, September 21, 2011

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.

Tuesday, September 20, 2011

Learning in Multiagent Systems

This week we will be discussing the chapter on learning in multiagent systems. The first test is scheduled for Monday and will cover up to this chapter.

Wednesday, September 7, 2011

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.

Tuesday, September 6, 2011

Game Theory in Practice

The Economist has a fun article on Game Theory in Practice about a few companies using agent-based modeling approaches to make predictions about real-world events. These are the same type of models that you will be building, except not as large, of course. Check out the video. Still, I think there is a large chasm to cross from saying that your model predicts the general dynamics of a population, to predicting the fall of Hosni Mubarak within a year. Until someone puts up his 'annual predictions' up on the web every year, for several years, so everyone can verify them, I shall remain a skeptic on our ability to make such fine-grained predictions.

Oh, and that same issue features pmarca's article on how software is eating the world, which he first mentioned in his WSJ piece. Indeed. Even hardware is software now (cf. 3D printers).

Game Theory for Agent Systems

This week we start our study of game theory as used for building multiagent systems.