Forrest Stonedahl

Projects...

“We build too many walls and not enough bridges.”

Isaac Newton

Beyond my primary research, I have been involved in a variety of projects that bridge computer science with other disciplines. These include urban development/land use, linguistics, economics, materials science, evolutionary biology, artificial life, and learning science/education.

Page Outline:












Selected student advisee projects:

Parapatric speciation

I advised undergraduate Murphy scholar Greg McGlynn on a evolutionary botany project that created a basic model of parapatric speciation. In parapatric speciation, there is partial overlap between the zones of two diverging populations (as opposed to allopatric speciation, where the two populations are geographically isolated -- e.g. islands like Madagascar). Parapatric speciation may occur by diverging pollination periods, stemming from varying regional environmental pressures.


Parapatric speciation model



Hydrogen diffusion model

I also advised computer science undergraduate Daniel Kim, working in collaboration with Wenhao Sun, an undergraduate materials science major, on a project modeling the diffusion of hydrogen in lattices. Specifically, the model simulates hydrogen desorption from solid state hydrides, which are hydrogen storage materials that absorb or release hydrogen depending on pressure and temperature conditions.

Of particular interest is the rate at which hydrogen is released from the metal, as these types of hydrogen-storing materials have application in the development of fuel cells. Both a 2D and a 3D version of this model were developed -- see images at right.


2D and 3D agent-based models of hydrogen diffusion

Market competition

Bertrand Ottino-Löffler is another student that I worked extensively with on an agent-based modeling project. We followed up on Hotelling's early and influential work on stability and competition in economic markets, by extending the product-space to two dimensions and allowing multiple firms to compete for consumer market. Firms use a greedy heuristic to make decisions about price and position in the product space, while consumers use a balance of price and product preferences to choose which store to patronize. In this work, we discovered interesting emergent patterns about firms pairing off and engaging in local price wars. (Manuscript in preparation.)



ABM of market competition


Think-Tac-Toe

Think-Tac-Toe is a logic puzzle reminiscent of Minesweeper that Dr. Susa Stonedahl and I developed for our middle school math problem solving group. Certain puzzle dimensions make the puzzle uniquely solvable, while others do not. We presented a proof characterizing the conditions that guarantee puzzle solution uniqueness at the 2011 summer MAA meeting (MathFest).

Visit our Think-Tac-Toe Website

MathFest 2011 materials: Handout   Abstract   Presentation

Think-Tac-Toe puzzle example


Diffusion of Language

This project, which is joint work with linguistics professors at Northwestern and U.C.L.A., investigates how language change can occur within a population, even when there is no global bias in favor of the change.

Using agent-based simulation, we demonstrate a theoretical model for how language cascades can occur, using a combination of a heterogeneous population with a social network structure for language interaction. We also identify several interesting phase transitions between different regimes in the model's parameter space. (This paper is currently in preparation.)

Visualization of a language cascade through a social network


KnotLogo

KnotLogo is a constructionist learning environment that I designed. Following in the tradition of the original Logo language, which used a turtle to teach kids about geometry and computer programming, KnotLogo uses snakes to teach kids about knot theory, 3D geometry, and computer programming. The video below gives a flavor of KnotLogo.

An additional feature, in keeping with the constructionist philosophy of creating personally meaningful artifacts, is that students can export their knots to a VRML file format which can then be printed on a 3D printer. (See images at right).




ZCorp 3D printer




Printed 3D objects:
knots from KnotLogo and misc. shapes from NetLogo


Procedural modeling of cities

The CITIES project employed agent-based modeling for the procedural generation of realistic urban landscapes, similar to how L-systems (and related techniques) can be used to generate detailed and realistic foliage. In a 2D simulation, virtual construction workers, developers, and residents combine to create life-like transportation networks, land usage maps, and population densities. The resulting city plan could then be vectorized and rendered in 3D. Additional simulations addressing auxiliary aspects of urban modeling were also developed. For more information, see the project website.

A simulated city layout, with transportation network, zoning, population density, etc.


ALIAS: Artificial Life in Artificial Societies

Some of my research falls in the area of artificial life, and I have grouped several relevant (though separate) projects together under this heading.

GAs with dynamic breeding networks

This project was done in collaboration with Bill Rand, and it involved restricting which individuals in the population of a genetic algorithm can breed with one another, by specifying breeding networks. We also allowed for the possibility of the breeding network changing over time (i.e., dynamic networks).

We also experimented with low-density networks, to see how few links could be used while still maintaining an effective search process. Several interesting findings came out of this project: 1) the genetic algorithm's performance is robust, even at quite fairly low connection densities, 2) random linking is preferable over spatial linking for low-density networks, and 3) dynamic linking is more robust than static linking for low density networks (see demo videos at right).

What is additionally interesting about this project is that the same simulation can be interpreted as a model of information diffusion in social networks. That is, ideas can spread from person to person, with people making modifications to those ideas (mutations), or combining several good ideas from their friends (crossover). Thus, it can be construed as an abstract model of collective problem solving capabilities given limited communication channels.

This project is further described in this paper, presented at the ALAMAS+ALAg Workshop at AAMAS '08.


Critters! participatory simulation

In another project, I built a simple web-based artificial life simulator, akin to a virtual Petri dish game. Human players could log in, and design a species which would be placed in the world, and compete with other species for virtual resources. Players could choose between carnivorous and herbivorous creatures, and choose various movement and reproductive strategies. Successful species would multiply, while unsuccessful species would go extinct. Sometimes relatively stable ecosystems could form, whereas other times domination could cycle between species in a fashion reminiscent of rock-paper-scissors games. Screenshot at right.


Evolving nonuniform cellular automata

One more project (in collaboration with Bill Rand) that touches on artificial life involves the evolution of non-uniform cellular automata rules (using a genetic algorithm). Specifically, we were trying to evolve rules that would solve the majority classification problem. That is, the whole lattice should converge to 1s if the initial density of 1s is less than half, and it should converge to all 0s otherwise. It has been proven that no perfect rules exist for uniform cellular automata, but we were interested in investigating what leverage might be gained by using a heterogeneous rules throughout the lattice.

A few interesting results can be found in this poster and abstract (presented at the GECCO 2007 conference).



Quick Links:


Genetic algorithm with a static spatial breeding network. Warmer colors indicate higher fitness. (Fails to find optimal solution.)

Genetic algorithm with a dynamic spatial breeding network. (Finds optimal solution.)



Critters! online participatory a-life simulation [more info here]


Time-space diagram for a set of evolved nonuniform cellular automata rules