Wolfram Science

Alastair Hewitt: An Alternative Approach to Anticipative Reinforcement Learning

This was another decision-based talk using NKS, and I found this one just as interesting as the last. Hewitt studied a relatively simple but fascinating model of decision making based on choices between binary states with memory about which decisions led to which states. He had a very large number of of quantities he was using to describing the the behavior of the system, including predicatbility, desirability, and entropy.

The elementary system was a 2D CA with 2 choices, (turn left and no action), and 1 indicator with two states (right direction and wrong direction.) The agent must learn what to do when feedback indicates it is headed in the wrong direction based on past behavior, but with no indication of what moving toward the direction would be. Hewitt presented some state transition diagrams where the agent would determine the correct direction very quickly, but he quickly threw a wrench in the works by giving himself the ability to change the target point in real time.

He showed an interactive graphic of the agent seeking its target. The agent would head off in a direction more or less toward the target, but frequently get stuck in "orbits" once it had passed it on one side. I found it very amusing that the agent would get stuck in these orbits for some number of cycles and then finally get "frustrated" when it received enough negative feedback for each of its actions, and strike off in a random direction which would usually cause it to hit the target a few steps later.

Then he showed multiple agents where some of the agents were other agents targets. Their behaviors were reminiscent of bees milling around a hive, or as one of the audience members eloquently phrased it, "dating."

Hewitt ended with some graphics of distributions of various features of the agents' behavior.

Samuel Chen: Achieve Computer Vision with 2D CA--An Introduction

Perception and Analysis lecture series

Samuel Chen from Harvard University discusses computer vision techniques with 2D CA

Samuel uses 2D CA as a direct filter on visual images, and identified a class of 2D CA with 5 neighbors and radius 1 that can identify horizontal, vertical and diagonal, 45-degree lines. This class is divided into types that perform particular operations: they highlight vertical or horizontal lines only, or only diagonal lines. Other types multiply (think "thicken") horizontal or diagonal lines  in various ways. Additionally, various effects on other diagonal lines and small curved lines segments were cataloged.

One immediate application for the filters identified is to help differentiate between signal and noise in a time series of images, for example.

Thomas Speller: From Aesthetically Appealing Chinese Lattices to Routing or Circuitry Systems

Engineering and Design lecture series

Thomas Speller of MIT describes a cataloging system created with shape grammars and 2D CAs

Thomas discussed how system architecture limited both by current processes, by budget and time, and by the typical fact that stakeholders in a project aren't aware of their true requirements until part of the designed system has been built.

Shape grammars are based on Chomksy's transformational grammar, which generate a language of one-dimensional strings. Thomas describes a generative algorithm in stages, that transform shape grammars into a CA system. Thomas used shape grammars to develop a catalog of Chinese Lattices and ancient Greek Meanders. The shape grammar defines shapes, markers and initial conditions, and a 2D CA is used to generate one quadrant of the lattice, since the full lattice can be produced from this through symmetric reflections.

While the rule system had over 4 million possible outcomes, only about 20% met the specifications of being a valid lattice, and in fact after a uniqueness test, there turned out to only be 20 unique lattice structures.

Thomas described an application of this system to the routing of pipes for in-floor radiative heating. The crucial requirement here is that it must provide uniform heat and be the most cost-effective to install. The system was extended with a more complex neighborhood and more rules, and each room or "zone" in an installation can be solved as a separate module with limited connectivity to the other modules, and the modules can then be joined into a complete installation plan. The solution space can be further filters to meet efficiency conditions, such as preference for the longest possible runs of straight pipes or other requirements.

Loe Feijs: Reinventing Electronics in NKS

Engineering and Design lecture series

Loe Feijs of the Technical University of Eindhoven describes his work simulating electronic circuits with CA rules.

Loe explores the expressive power of CAs as an alternate basis for electrical engineering. As his first goal, he has designed several CA systems that attempt to emulate an RC phase-shift oscillator, with the assumption that if this is possible, more complex circuits will also be possible.

In his first attempt, each cell is assigned a voltage value. Rules define a diffusion and flow of voltage. This system was then extended to 2D with a graphical grid-based circuit specification (made using MS Paint!) and appropriate 2D rules. This system was successful at modeling a simple resistive system like a voltage divider. However, problems arose when trying to add a model for capacitor plates.

His second attempt utilized block CAs, and like the first used special colors to position the ground plane and input-level voltage, as well as to overlay voltmeters and ammeters. This method was again successful in modeling voltage dividers, and could also model capacitor plates using a special, larger rule. However, this model failed when trying to model FETs, but was instead able to model beam-deflection transistors, also known as vacuum tubes. This allowed the successful modeling of a phase-shift oscillator.

Vallorie Peridier: Basic Schemes for Reversible Cellular Automata

Engineering and Design lecture series

Vallorie Peridier discusses the utility of reversible CA rules in engineering

Vallorie described reversible CA rules, and their application in the research of inverse problems. Often, for example, a series of measurements of temperature data on a device or structure need to be used to make a qualitative determination about a system. Inverse problems using CA have the advantage that a bi-directional search may be possible, whereas the conventional approach dictates that the system state is re-estimated and then computed forward.

One particular application of this idea is in the inspection of wafers during integrated-circuit manufacturing, examining the light scattered by the wafer surface as a measure of physical quality. Since optical metrology is a 2D-problem, it requires the use of 2D reversible rules. Vallorie showed two ways to construct reversible 2D rules, the Fredkin construction and the block-transformation, "Margolus-neighborhood" scheme.

Vallorie also developed extensions to other block structures, and in particular hexagonal lattices. Her work next will involve working out an inverse solution methodology on a more simple problem than light scattering.

Margaret Eppstein: Predicting Naturalization versus Invasion using Stochastic CA Models

Natural Sciences lecture series

Margaret Eppstein of the University of Vermont discusses invasion vs. naturalization in plant models

Margaret talked about what makes plants invasive. Several ideas already exist to explain some of the phenomena: the enemy release hypothesis, evolution of increased competitive ability, the biotic resistance hypothesis and propagule pressure. Models include both positive feedback effects, like pollinators and the presence of symbionts, and negative feedback effects like predators and pathogens. A characteristic like soil chemistry can be both a positive and negative feedback effect.

However, the standard Lotka-Volterra models typically used fail to account for frequency-dependent feedback effects, as well as typically making the assumption of a mean field, meaning that the use of space is ignored.

Margaret has developed a new model that incorporates propagule pressure, and both frequency dependent and independent effects, as well as spatial scale. Her results show that it's important to consider space when modeling whether an exotic species can establish when invading a new environment, as well as both frequency-dependent and independent interactions. This is then modeled as a stochastic CA with a configurable cell neighborhood.

This new model may be a practical way to assess the invasive potential of new species, or to estimate range limits of invasive species.

Emmanuel Sapin: "On Discovering Gliders and Glider Guns with Evolutionary Algorithms"

Sapin's project was to find universal CAs with the game of life. He had many interesting example configurations where he was using so-called gliders and glider guns to model streams of information. He would configure the initial states with glider guns whose paths intersected. Gliders that collided would be annihilated, which in some cases would create gaps that would allow other gliders to pass through a stream. Sapin claimed that these systems represented AND logic gates. One could easily imagine universal computation being done by certain configurations of these glider guns.

Sapin also has some interesting tools for creating conditions in his Game of Life. With a contextual menu, he could create a field of random obstacles and set up some glider guns to fire against them and interact.

Thomas Speller: "A Study within the Nanosystem Architecture Domain: Self-Assembly of Graphene"

Thomas Speller discussed a combination of shape grammars and cellular automata.  Shape grammars are apparently specifications of 2- or 3-dimensional forms, and are commonly used used in architectural schools. I wasn't familiar with the concept of shape grammars, but they appear to be a natural way to symbolically specify shapes.

He is interested in a domain study of graphene, a common structure in all biotic systems and many inanimate ones, which is becoming a popular subject of study among condensed matter physicists. He was generating shape grammars for graphene by using cellular automata to model the possible transitions between states.

He showed comparisons of different the results from different CAs pre-selected to model different physics processes, and showed that in each one, graphene-like structures were created. The difficulty in translating these processes to reality appears to be limiting the number of atoms that combine into separate aggregations before bonding with each other.

Yuriy Gulak "Algebraic properties of elementary cellular automata"

Yuriy explores the idea to replace conventional CA rule with algebraic operation by grouping pairs of cells (Pedersen 1992, Moore 1997). Then, the ECA evolution can be computed bu groupoid multiplications of neighboring elements.

Generally, the complexity of computation of evolution is N^2. Can one do better?  Yes, under certain conditions. Namely, there are certain "shortcut" identities.  One can empirically search for these identties, but can they be derived?

A "basis" is a set of identities from which all other identities follow (these are like axioms). "Finitely based" groupoids have finite basis. 4-element groupoids are not necessarity finitely based: some "true" identities cannot be derived from other lower-degree identities. There is a recursive algorithm that would determine if groupoid is finitely based (is there?)

Here, Yuriy is making a hint on a connection between incompressibility and non-finitely-based groupoids. In particular, the fact that 6 is the least order of semigroup without a finite basis for identities vs. NKS book, page 887. Traditional math is based on a finite number of axioms, and to develop complexity, one needs(?) non-finitely-based systems. The less identities are there, the more interesting is
the structure.

Pretty cool, I would say. It would be interesting to see how those identities appear in the numerously drawn CA evolution pictures. Something like longer-term rules?

Robert Barbour, 2D Four-Color Cellular Automaton

Robert made a presentation about a 2-dimensional CA -Langton's Ant- with space filling capabilities.  His CA rule generates one single active updating site - updating happens in a very local manner. The behavior reminds me of a 2D Turing machine. Andrew Bragdon did work on space-filling 2D Turing machines at the 2005 NKS Summer School:

Andrew Bragdon, NKS SS 2005

Robert showed some nice visual analysis of how often cells in the 2D grid get visited.

Here are three integer sequences that related to his work:

A102358

A102369