Simulating a System with Multiple
Agents
Term Project
CS211 Fall 2000 Accelerated
Stream
Questions? Please see the project
newsgroup.
(ONLY for Project Messages - also watch regular Class Newsgroup
)
Note:
This version of the Project description is essentially complete,
though some non-conflicting requirements may be added, such as a required
extension. Your comments also will be considered, and may be
used to enhance he project description. There are only small changes
compared to the draft version of Monday 10/16: vehicles reaching
the outgoing edge of a street are removed from the simulation; there
is a new GUI snapshot;
the traffic light now is the more typical 2-mode light.
Intermediate milestones will
be due prior to completion of the project at the end of the term:
-
The first milestone will be
a UML
diagram of the Classes you need to implement to implement the system.
This will be due Thursday Oct 26th at the start of the 10:10am class.
-
Second
Milestone will be completed construction of the graph "map" and simple
demonstration of it - GUI optional at this point. Due Thursday Nov
2nd 10:10am.
- For subsequent Milestones see the Accelerated/Project
main page.
Thus your first task is to go
over this description and related materials, probably more than once, and
begin sketching on paper what the modules of the system should be.
This is most definitely a thinking exercise, where "design by iterative
refinement" will pay off.
Watch this space for updates.
Good luck and enjoy the thinking and learning. Begin NOW, and you
are more likely to enjoy it.
Thanks to Evan Moran and
Vaibhav Vaish (grad TAs) for their significant contributions to this writeup.
- Matt Morgenstern
Introduction
In several fields of study, we encounter systems that consist of several
interacting objects. When the behavior of the objects is governed by a
simple set of rules, it becomes possible to simulate the entire system
on a computer. For your project, you are required to write a program to
simulate such a system. The system we're going to simulate is the road
traffic example described below.
Alternatives within the Project:
-
Additions and extensions: If you are not proposing a change
in the basic requirements, or only small changes, please talk with (or
email) either
TA, Evan or Vaibhav. If approved, then send an email summary of the
additions promptly to both TAs with a copy to matthew@cs.cornell.edu.
If none of the requirements are
altered, and you are just adding functionality, this likely will be approved.
If your extensions only slightly modify a couple of the requirements,
but provide additional functionality, a bit more explanation is needed
- to show you've thought it out carefully. Emails should begin the
Subject line with "CS211 Project"; TA email addresses are evan@cs.cornell.edu
and vaibhav@cs.cornell.edu.
-
Significant changes to requirements: Talk first with Evan
or Vaibhav, get their recommendation, send email to me (matthew@cs.cornell.edu)
and copy to both TAs, with careful description of what you propose,
the TA recommedation (and TA's name), and look for my reply as to whether
it is okay or not. Well thought out variations on the current project
are much more likely to be approved than radical changes.
The
larger the change, the more likely it is you also will need to speak with
me directly - which you are welcome to do in any case. Emails should
include copies of prior messages, and when meeting with us, please bring
hardcopy of this info and any other supporting materials.
Examples
Before describing details of implementation, it is useful to look at some
examples of such systems.
Synchronized flashing of fireflies
It's well known that ensembles of certain kinds of fireflies have a
curious tendency to synchronize their flashing... What could explain this
behavior? One model posits that an individual firefly, in isolation, will
flash in a steady cycle, with a constant interval between flashes. However,
if a firefly sees a nearby firefly flash, then it will jump forward in
its cycle slightly, so that it gets closer to being in synch with the neighboring
insect. Simulations
have demonstrated that this kind of protocol is quite effective---capable
of synchronizing not only adjacent fireflies but even fireflies that are
not able to see each other flashing (provided that there are intermediate
fireflies "connecting" them).
Slime mold aggregation / clustering of heatbugs
A slime mold is a creature that, in a sense, is both unicellular and
multicellular... When food is abundant, each cell in a slime-mold community
operates as an autonomous amoeba, detached from its brethren. When food
becomes scarce, however, the tens of thousands of individual amoebas seek
each other out, aggregate into a single multicellular organism, and migrate
to a better location (!). How does such a large group of spatially dispersed,
single-celled organisms "decide" where to congregate? Mitchel Resnick experimented
with a simple, pared-down model: each individual cell releases into the
environment a pheromone that attracts other cells---specifically, the amoebas
have a very strong tendency to move in the direction of the greatest concentration
of the pheromone, which diffuses through the environment and also slowly
evaporates. Clearly, there is a positive-feedback loop implicit in this
model: a group of amoebas will produce a "pool" of the pheromone, which
will in turn tend to attract even more amoebas to the congregation. Watching
a 1000-cell simulation of such a system is usually enough to convince the
observer that this simple, highly localized mechanism is indeed sufficient
to trigger large-scale cluster formation; chance groupings of just a handful
of amoebas slowly evolve, over several hundred iterations, into clusters
of roughly 100 cells.
(The classic "heatbug"
demo is a closely related model which uses heat instead of a pheromone.)
Road traffic
Consider a network of streets, on which vehicles are moving. Each vehicle
could have some destination it wants to reach. In doing so, it must follow
some basic traffic rules, such as obeying traffic lights, speed limits,
and most importantly, avoiding collisions. The interacting agents here
are vehicles, the environment is the network of roads with traffic lights,
stop signs, speed limits, etc. Large-scale
simulations of such systems have proved to be useful tools in the study
of metropolitan traffic congestion.
In each of these examples, we observe the following characteristics:
-
The system is made up of several agents. Generally, the time-varying components
of the system are agents.
-
Each agent's behavior is described by a set of rules. Typically, an agent
is influenced by its local environment and the agents close to it.
-
The behavior of the whole system is simply the combination of the behavior
of all the agents.
Note that this is a very general framework, which could even be
used to model games like chess, checkers or Risk.
General Framework for Simulation
Your simulator must have representations of the following components:
Agents
Each agent in the system must be represented by an object. One approach
is to have an abstract class Agent whose subclasses represent
the different varieties of agents. Alternatively, an interface could be
used instead of an abstract class.
Each agent stores its internal state. It should have a method that causes
it to observe its local environment and accordingly update its state (and
perhaps modify the local environment as well).
Environment
The environment consists of the information which agents need in order
to update their state, along with methods an agent can invoke to obtain
the desired information.
Map
The map defines the set of positions that agents may occupy as well
as the connections between "adjacent" positions. The simulations that we're
focusing on use discretized maps---there are only finitely many possible
positions. (You might think of the map as being a generalization of a checkerboard
or of the boards for games like Risk and Monopoly.)
The map is usually considered to be a part of the environment; i.e.,
there's an "aggregation" relationship between those two components of the
system.
Controller
This is the part of the program that actually carries out the simulation.
At startup, it creates and initializes all the agents and the environment.
Note that we will be doing a discrete-time simulation. At each step of
the simulation, the controller will request each agent to update itself
to a new state, based on the current environment. It will also make any
additional updates to the environment that are necessary.
User Interface
This would depend to a large extent on the particular system being
simulated. A good UI would let the user initialize the system and then
compute and display the state of the system after a specified number of
time steps. It might also let the user alter agents' parameters at run-time.
Simulation of Road Traffic
The system consists of moving cars on a network of roads, with traffic
lights at the intersections. Your program should show how the vehicles
move along the streets with time. The specifications below indicate the
minimum implementation required for the project. You are encouraged to
think of extensions and implement them, if time permits.
Environment
The environment consists of the map of roads on which the vehicles move,
along with position information of the vehicles and the states of the traffic
lights.
The Road Map
For simplicity, you may assume that the roads form a square grid. All roads
are two lane and two way - they run vertically (north-south) or horizontally
(east-west), as shown in the diagram below.
A simple roadmap. The black rectangles
represent intersections.
A street segment is the part of a road between two intersections, or
between an intersection to the edge of the road map. Exactly four street
segments meet at each intersection. You need not implement complex road
maps. A map similar to the image above, with a few vertical and horizontal
streets arranged in a uniform grid, will suffice.
Tiles
Since we are doing a discrete simulation, it makes it easier to think of
the lanes as being composed of discrete chunks, which we will refer to
as tiles. The idea is that each tile corresponds to a one car-length fragment
of the lane. At a given point in time, only one vehicle can occupy a tile.
Vehicles move one tile at a time. For simplicity, you may assume that all
street segments have the same number of tiles, set as a compile time parameter.
A street segment, composed of two lanes.
Each lane consists of five tiles.
Directed Graph Representation
Your program must represent the map as a linked directed graph
(though it is good to think of other alternatives) - this still leaves
you several choices regarding the graph. The graph will have have
two kinds of nodes: tiles and intersections. Edges indicate the direction
of movement of vehicles. There is an edge between an intersection and a
tile adjacent to it, in the direction of vehicle motion - intersection
to tile, or tile to intersection, depending on the lane the tile resides
in. There is an edge between two neighboring tiles in the same lane, in
the direction of vehicle movement. See the section on agents
for the details of how vehicles move.
[A pair
of diagrams illustrating the directed graph representation of the road
map is now available.]
[Directed graphs were just covered in lecture, and are discussed in
Weiss section 14.1. The recommended representation is being discussed
in the Accelerated section, though any of the directed graph representations
may be used, including adjacency matrix or adjacency lists.]
Agents
The "agents" in our traffic simulation are the vehicles on the roads and
the traffic lights at the intersections.
Traffic Lights
Traffic lights have a fixed position - there is a traffic light at each
intersection. At any point in time, a traffic light is in one of two modes:
| |
mode 0: |
|
green for vehicles facing North or South |
& |
red for vehicles facing in the other two directions |
| |
mode 1: |
|
green for vehicles facing East or West |
& |
red for vehicles facing in the other two directions |
For simplicity, you can assume that a traffic light cycles through these
two modes, spending an equal amount of time in each mode (say, three time
units each). Use separate compile time parameters for the durations
of each of these two modes, so that this can be changed easily.
Vehicles
Vehicles have a position in the road map at each point in time. Each vehicle
occupies one tile. In our simulation, vehicles do not spend any time in
the intersections - they just jump across, if the traffic light permits.
Legal moves
In each time interval, a vehicle may do one of the following:
-
It can remain in its current position if it has no other valid choices.
-
If it is not at an intersection, and if there is a vacant tile immediately
in front of it, it can move forward into the vacant tile.
-
If it is at an intersection (i.e., situated on a tile adjacent to an intersection
and facing the intersection) with a green light, it can jump to the first
"heading away from the intersection" tile of any of the other three segments
that touch the intersection, provided the jumped-to tile is vacant. No
U-turns are permitted. [A diagram
for this rule is now available.]
-
A vehicle that does not have a tile or intersection in front of it (i.e.,
a vehicle that's facing the edge of the map) is removed from the simulation.
[For additional optons on this topic, please see the add-ons
page.]
Querying the Environment
At a minimum, a vehicle must be able to obtain the following information
from the Environment:
-
Am I at an intersection ? If so,
-
Is the light red or green ?
-
Which of the three initial "heading away from the intersection" tiles of
the other segments that touch this intersection are vacant ?
[You may want to refer to the intersection
diagram.]
-
If I'm not at an intersection, is there a vacant tile in front of me ?
Since each moving agent (e.g.,
a car) will see only a limited set of information "around" it, you may
want to have a method which is responsible for determining which positions
are relevant (e.g., adjacent) and which fixed agents (traffic lights) need
to be accessed for their status.
In your implementation, please feel free to make more information available
to vehicles.
Kinds of vehicles
You must simulate at least the following two kinds of vehicles:
-
TCAT Bus
This always travels on a fixed, rectangular circuit. For example,
Thus, at any point in time, it knows the next tile it has to move into.
If that tile is not vacant, it will simply sit in its current position,
waiting for the tile to be vacated.
-
Randomized Vehicle
This vehicle's driver is out for a casual drive, with no particular
destination. Each time its turn to move arises, the vehicle determines
the set of tiles into which it can legally move and then randomly
selects one of them. The vehicle remains in its current position only
if it cannot legally move into any tile.
You are welcome to add other kinds of vehicles if you wish (and if time
permits). The above two categories are compulsory, however.
Simulation Control
This part of the program is responsible for creating of the roadmap and
agents at startup. The initial configuration of the system should be flexible,
but may be set at compile time - run time changes are an additional option.
Each "step" of the simulation corresponds to one unit of time. In each
time unit, the controller asks each agent to update itself, according to
the environment, by invoking the agent's "update yourself" / "take one
step" method. For a vehicle, updating itself would involve moving into
another tile, or remaining in the same position, as per the traffic rules
and
the vehicle type. For a traffic light, updating could result in a change
in signal, if it is time to change.
Round Robin Update
One naïve way to update the system is to update each agent in a fixed
order. So, if the system had five agents A1, A2, A3, A4, and A5 then we
could first update A1, then A2, and so on, updating A5 last. This is a
round robin update. For simplicity, you may implement a round robin update
in your project.
There is no conflict at an intersection if a northbound car wants
to turn right and a southbound car wants to turn left. Only one vehicle
moves at a time, and the next vehicle sees that change in state.
Updates with Cloned State (Optional)
There is one problem with round robin updates. Conceptually, the system
at time t is described by the state of all agents at time t.
The state of an agent at time t+1 is computed based on the state
of the agent itself, and state of the nearby agents at time t. The
round robin method may not update agents as realistically as one may want.
In the above example, agent A1 is updated based on the states of agents
at time t. But when we are updating agent A2, we can only access
the updated state of agent A1 - that is, the state of A1 at time t+1.
This may lead to a simulation that is not accurate or realistic - because
the order in which we update agents would affect the simulation.
To overcome this, we can first clone the state of all agents, and store
the cloned states at time t. The updating of each agent would be
done by reading the copy of the states at time t. Since all agents
have access to the state of the entire system at time t, the computation
of states at time t+1 is more realistic, and does not depend
on the order in which we update agents.
This approach will need an additional check that two vehicles do not
end up on the same tile. The easy way to do this is: after the
desired step is chosen
based on the world state at the previous time step t, the agent/vehicle
also peeks at the chosen tile at the current time step t + 1 to
be sure a vehicle has not just jumped there. A more sophisticated
approach is to subdivide each cycle into phases, with each phase
involving only non-conflicting actions (such as only left turns in one
phase, then a going straight phase, then right turns) - more info is
available on this by discussing with us.
For your project, you have a choice - you can implement the simpler
round robin updates, or you can implement updates with cloned states, whichever
suits you better.
User Interface
This part of the project may well involve the largest amount of programming.
You must have a graphical interface, that shows clearly the state of the
complete system at startup. The UI must let the user specify a positive
integer n, and then display the state of the system n units
of time later.
For the road traffic simulator, you must display the road map, showing
all the streets, intersections and tiles. Display the state of the traffic
lights and vehicle positions in a simple manner - you do not have to use
intricate pixmaps. The position of a vehicle could be shown by simply shading
the tile it occupies with a distinct color. Also, it would be ok to use
a simple color-coding scheme to indicate the state of the traffic lights
and the different kinds of vehicles.
[GUI will be covered in lecture and/or section. Those who'd like to
get a head start may want to take a look at the Creating
a GUI with JFC/Swing trail in sun's java
tutorial.]
Demos & Grading
< demo dates and times TBA >
The bulk of your final project grade will be determined at the final
demo, which will occur in compliance with university policy (probably sometime
before the official "final study break" or else during finals week). The
final demo will last approximately 30 minutes, and both partners
must attend.
At the final demo, we will first ask you to run your simulation as-is;
this
run may begin with any substantial initial configuration that you like.
Next, we will request that you make specific modifications to both your
hard-coded initial configuration and one or more of the compile-time constants
(e.g., the number of tiles per street segment). After doing so, you will
recompile and then run the modified application for us. It's consequently
imperative that you structure your code in a way that allows you to quickly
change things like: the number of streets on the map, the locations
of the vehicles in the initial configuration, etc. You must be able to
make such modifications by changing only a line or two of code. [The judicious
use of symbolic
constants will make your life significantly easier in this regard.]
Also be sure to read the Miscellaneous
notes and clarifications page and look thru the supplementary material
below.
When in doubt, please ask for clarification.
Appendices
-
Miscellaneous
notes and clarifications
-
Supplemental
material (hints, examples, ideas for extensions, etc.)