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 research projects:
• Parapatric speciation
• Hydrogen diffusion
• Market competition
• Descriptions of three more undergraduate research projects coming soon to a web page near you...
• Think-Tac-Toe
• Diffusion of Language
• KnotLogo
• CITIES: Procedural modeling of urban development
• ALIAS: Artificial Life in Artificial Societies
• GAs with dynamic breeding networks
• Critters! participatory simulation
• Evolving nonuniform cellular automata

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.

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.

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.)

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

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.)

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).

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.

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:

• teaching
• primary research
• activities
• tools
• curriculum vitae
• contact me