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.

Introduction

"The greatest constant of modern time is change." - John Sterman

System dynamics deals with how things change over time. It is a way to augment our understanding of the world around us particularly suited for studying the dynamic, non-linear systems all around us. The Limits To Growth model, which caused more public reaction than any other computer model, came out of MIT's system dynamics lab. 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, but is also particularly suited to childhood education. Jay Forrester, the founder of system dynamics had this to say in 1997:

• System Dynamics uses computer simulation models to reveal how known structures and policies often produce unexpected and troublesome behavior. The computer models are constructed from descriptive information that is usually already known. Such information relates to who is striving to do what, the information that each person has available, time delays in taking aciton, and what individuals will do under a variety of pressures. the Same approach carries over to nonhuman systems in nature and physical change.
• In the more successful schools, system dynamics is combined with a classroom reorganization we call "learner-centered learning." Such a project-oriented approach goes by various names in other proposals for K-12 education, but is especially powerful when combined with system dynamics. Learner-centered learning focuses on solving substantial problems. Teachers are no longer lecturers, no longer the source of all wisdom, not even necessarily authority figures. ... Students address projects with real world significance for which they have not been given the necessary background and techniques. They start by facing the challenge of learning what they need to know in order to accomplish the project ... In its full development, system dynamics is a profession with the scope of science, education, law, engineering, or medicine. On the other hand, it is becoming clear that teachers in ordinary K--12 schools can make enough progress in two or three years to achieve major improvements in students' thinking, self reliance, and enthusiasm for learning. - System Dynamics and K-12 Teachers

Its a bit of a lengthy quote (that I had to transcribe, so any grammatical errors are likely mine), but I think it captures quite well the need to bring SD to the XO. There is a demand, there are potential lesson plans ready to be adapted, and it integrates so well with constructivist principles.

Basics and Other Approaches

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 eventually be a collaborative activity, several people could work on editing a model at once and models would be saved in the Journal as usual. I've been spending my time recently on actively developing the simulation engine, so while I have many ideas for the Editor, I'm wide open to suggestions.

At a minimum, models would look somewhat like the above example (probably without the bounding box and title like that). There would be a pallet where users could click to add stocks (like population), flows (the thick lines in and out of stocks), variables, and influence (the blue arrows, showing where variables and stocks are referenced). There are two big things that I would like to see for equation editing: tokens for referencing other variables and something like interactive latex formatting for the equation field. With something like the tokens you can use in Cocoa on OSX (NSTokenView), it would ease the problem of typing in long variable names, they could be autocompleted or dragged in, and only valid identifiers would show up as tokens. This could be created as a subclass of GtkEntry or GtkEntryCompletion. As for the interactive equation formatting, I'm envisioning something like what is available in Grapher, again on OSX. These two pieces of eye candy aren't core functionality, and will be worked on after the rest of the editor is complete and as bug free as possible.

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. I have a preliminary example of some optimizations on my wiki.

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. For GSoC, I would like to get Micropolis to use the simulation engine for some of its easier models and calculations, a working proof of concept I can expand upon in the fall.

Micropolis Details

This work will probably fall outside the scope of GSoC, but I think its useful to see some of the applications and future directions of the project. As mentioned, I'm going to use GDAL to interact with raster maps. It will be really cool to convert Micropolis to use GDAL's RasterBand datatype to represent the data on map layers. Since GDAL can read and write almost any kind of file used to store raster GIS data (and they have another library for Vector data too), you could import maps from outside of Micropolis to create a city on. Teachers could create and students could import a set of maps containing the local elevation, water features, land cover types, even current roads, population and zoning information where its available as the basis of a new city. From there they could play Micropolis as usual and manage and change their city as they wish, and it would be that much more personal and powerful! The set of maps that is used by Micropolis could be stored and loaded as a GDALDataset by quickly throwing together our own GDAL driver (or using an existing raster standard).

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.

Beginning Timeline Notes

• Now - May 26 - Continue work on the simulation engine in my free time. In roughly this order I think I can complete by the end of may: JIT compilation, implementation of RK2 integration, output to SQLite and CSV, live model editing, and creating 'libsim' as a dynamic library. This will leave me with a great place to start integrating GIS into the engine.
• April 14 - May 26 - Talk with mentors to hammer down specifics of GIS integration, Sugar specific features and model editor design. Getting the design stuff nailed down before the summer will leave me with more time to code things up and squish bugs out. I'll also read and grok the OLPC_Human_Interface_Guidelines HIG
• May 26 - around June 10 - Class at my university doesn't finish until the 30th of May, and I don't arrive back in the US until around the 10th or 11th of June, so during this time I won't be able to work full time (on average I would say 2-3 hours per weekday).
• Starting June 11 - Full time GSoC work
  • weeks 1-4 - work on integrating GIS, 3 weeks for implementation and one week for bug testing.
  • weeks 5-8 - work on Sugar interface. I'm aiming to have a simple GTK+ app by the beginning of the summer, of which I can reuse most of the drawing code. This will give me a month to sugarize and implement OLPC specific features (collaborate, etc)
  • weeks 9-10 - hack Micropolis to use our simulation engine for some core functions, provide the groundwork to do more (ideas above)

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