OpenSim
This page contains the working Google Summer of Code proposal for OpenSim. OpenSim is intended as a system dynamics model editor and a general simulation engine.
Contents
Introduction
System dynamics (SD) is a method to enhance learning in complex systems. It allows us to study and manage complex systems that involve feedback loops and time delays, systems that are inherently non-linear. For a decent introduction to the subject, the System Dynamics Society [1] and Wikipedia[2] both have good overviews. It is used around the world, frequently in majority world countries, for planning among other applications. At a basic level you have to specify the mathematical equations for how different parts of your system work and interact. The same problems can be solved by writing code in a programming language (I had a course taught in Fortran a year ago...), but in SD the modeling is customarily done using a visual model editor where you can define causal relationships, stocks and flows graphically. This lowers the barriers to learning by removing all of the non-modeling aspects of programming models like memory management, file IO, syntax, etc. Don Hopkins started a thread on the mailing list a year ago on this subject, many of the ideas presented there have been incorporated here. In the SD field today there are several commercial offerings [3][4][5] but no open-source solutions. In addition, the commercial solutions are expensive (usually > $500 dollars per single academic license) and many haven't seen a redesign of their user-interfaces since the turn of the millennium.
Differences from eToys and Turtle Art
There are currently two activities that provide some kind of visual programming on the XO, Turtle Art and Etoys. Turtle Art provides a snap-together visual programming environment which can draw colorful art. Etoys provides an environment to easily define rules to control user created objects and run them. Both serve their role, but do not fill the niche that SD modeling can offer. The Wikipedia [6] site has some examples of how SD models generally look - they show the behavior of a system described by equations, rarely are if/else statements used. Both Turtle Art and eToys are very good at describing agents, but are not as expressive at SD for describing the behavior of systems. The three have all have their place on the XO, and there are great possibilities of integrating a SD approach and Turtle art in the future.
Deliverables
I started work this January, 2008 on an open-source SD model editor and simulation engine as the core of my Master's thesis at UiB. I would like to adapt and expand the work I've done on this for the XO. I am proposing:
- A system dynamics modeling activity that can be used to edit, design and run system dynamics models.
- A simulation engine with basic GIS integration.
- Port Metropolis to use our simulation engine for its core city logic, and integrate the ability to visually edit these models. Depending on community support, this could be put off to focus more on the model editor and simulation engine.
Proposal Details
SD Model Editor
The models created could look similar to the following mockup. Modeling would be a collaborative activity, several people could work on editing a model at once.
Simulation engine
I have started one and have it turning models specified in an XML file into valid Python code. By the summer it will be packaged as a shared library with the ability to edit models, execute them in a JIT environment (provided by LLVM libraries), and provide the data and results to applications. For the XO I would like to expand this to be able to access and operate on geospatial GIS data, as well as the execution of Turtle Art models. Using geospatial data could take either the form of supporting basic operations for things like land use change, or the more complicated step of porting and communicating with a GIS application, like GRASS. You can check out some of my progress so far here.
Integration with GIS
Geospatial data comes in many flavors, the biggest distinction being between raster and vector data. If you're not familiar with it, check out the Wikipedia entry on the subject. Fortunately, there are excellent open source libraries for opening and abstractly accessing the contents of maps - GDAL for raster data and OGR for vector data.
The first step towards fully integrating GIS into a simulation engine is to implement map algebra, overlay and scalar operations. Map algebra is generally the ability to do arithmetic operations on map operands, for example:
per_capita_income_map = spatial_income_map / population_map
Overlay operations are similar, but generally refer to the boolean operations. As you can probably guess by now, scalar operations are of the general form:
relative_elevation_map = city_DEM - 702
where one operand is a map and the other is a real or integer value. It is possible, and likely you would want to combine several of these operation types in a single equation:
future_city_population = city_limits_mask | (area_population_map + .07 * area_population_map)
We can accomplish this by looping through all of the values in the raster map, or all of the features in a layer of a vector dataset. This is pretty simple, but the last example can be implemented as:
for (int i=0; i < map_size; ++i)
{
future_city_population[i] = city_limits_mask[i] | (area_population_map[i] + .07 * area_population_map[i])
}
We need all of the raster maps to be of the same size, and the vector maps to have the same number of , which is a common requirement. We also assume that by this point all the maps have the same reference information, or at least that the user was told their metadata says they are maps of different areas. Of course, the actual implementation is a little more complicated as we will be working through GDAL and OGR drivers, but it is not fundamentally different.
What will be really neat is to have the simulation engine discover the operand types from variable definitions instead of from explicit castings or assumptions in the equations. I suppose I am suggesting a dynamically typed engine. For example:
average_per_capita_income = income * population
Initially income and population could be defined as constants or equations of their own, and average_per_capita_income would be computed as a real value. If you then found a map of either income or population, or both, average_per_capita_income would then be computed as a map. While type information would only be stored for constant real values and variables importing maps, once a model was loaded and equations parsed a GUI could query the simulation engine as to the current types of variables, so that users would know.
Once this is done, the more interesting aspect of integrating GIS into a simulation engine is to be able to rules and models for how individual cells (or features) will behave, and I would hope to work on this after the interface, simulation engine and GIS integration, and Micropolis integration are either completed or well enough along. There is a commercial software offering that does this, Simile (see the example here). In our Sugar front-end I am confident we can give it a more intuitive look and feel, and we shouldn't have a big problem with the implementation. The biggest issues will be defining operations and safety checks for when cells examine their neighbors contents, and probably defining some helper operations that can return commonly requested information instead of having to create the functions in each cell model you make, for things like testing if the cell is one of the X cells with the highest value.
Geospatial simulation optimizations
Geospatial simulations are be notoriously computationally expensive - when before you were calculating the value of each variable per timestep, now you are doing the each calculation N times (N being rows*columns for raster data and the number of features for vector data) per timestep. This could be a real power drain on the XO. Since these simulations will be running on the simulation engine based on the LLVM JIT, we will be able to perform various compiler optimizations (LLVM supports all the optimizations GCC can do, and more!) on the simulation before we JIT compile it, ensuring that it will run as efficiently as possible on the XO. When the time comes I would love some help with profiling, as I don't (yet!) have any experience with it.
Micropolis
The models could be edited in the above mentioned model editor, maybe the editor could be implemented as a GTK+ widget that could be created right in the Micropolis UI. Turtle Art could be used to define agents like bulldozers, etc, as Don Hopkins has suggested. Time permitting, the SD and Turtle Art editors could be integrated. As Homunq mentioned, this would (at least initially) miss a lot of the core processing done in Micropolis, like graph analysis and agents. I would hope the legwork involved in integrating the simulation engine with Micropolis, along with the work done to integrate GIS into the simulation engine will make the future addition of these additional 'features' easier than they were before. For example, if you can define models for how individual cells in a map behave and interact with adjacent cells, abstracting this a but further to support agents isn't a giant leap.
Availability
I am currently attending courses for my Masters at the University of Bergen in Norway, but will be living in Westchester, NY over the summer (a 45-minute train ride from NYC), and can commit to working a good eight hours per day on the project. Courses end the 30th of May, and I will be back in the US about a week later, available for 10 weeks of solid work on this.
About Me
Please check out my user page for information about me: Bobbypowers 11:50, 23 March 2008 (EDT)
Links
http://www.systemdynamics.org/
http://en.wikipedia.org/wiki/System_dynamics
http://www.millenniuminstitute.net/
http://lists.laptop.org/pipermail/sugar/2007-March/001829.html
http://www.vensim.com/
http://www.powersim.com/
http://www.iseesystems.com/
http://www.futuresalon.org/2004/11/will_wright_kic.html
http://www.donhopkins.com/drupal/node/142
