Wolfram Science

Adrian German: A Space of Solutions for the Easter Egg Problem

Adrian German presented some ideas toward a solution to the so-called "Easter Egg problem" where one has a field with randomly placed Easter Eggs. One wants to unleash a collection of near-sighted agents to path around the field and collect the easter eggs in the shortest amount of time. The question is, "Is there any algorithm that beats random searching. German was convinced that there was and presented the first part of his algorithm. It involved creating rule patterns that the agents would attempt to match to their surroundings with a default case of action if no patterns matched. German only got as far as showing the templates that cause the agent to spiral outward in a path that fills all space before his time ran out.

I am especially eager for German to find an algorithm more efficient than random search, since this is apparently what my Roomba employs to clean the living room and its algorithm is incredibly inefficient. The Roomba crosses its own path many times in its attempt to collect all the "easter eggs" on the living room floor. Here's hoping that German finds results that are employed by the iRobot corporation in their wonderful products.

Wendy Cox: Paradoxical Appropriations

Engineering and Design lecture series

Wendy Cox of Norwich University discusses architecture and NKS

Wendy describes the paradoxes present between architecture and nature, and how their presence led her to connect architecture with NKS. She showed several examples of interactive and dynamic buildings and structures, as well as many pieces of art that illustrated the points of her discussion.

Since architecture typically serves to create a particular solution for a particular problem, one application of NKS is to produce more general models that can be modified to suit a particular problem. Wendy described her work designing NKS branching structures, which on one scale could produce meshes to serve as the facade of a building, and at another scale even as the layout of a city.

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.

Brian Moulton: Recent Developments in Materials Science: NKS and the Design of New Materials

Natural Sciences lecture series

Brian Moulton of Brown University discusses Crystal Engineering with NKS

As a crystallographer, Brian is interested in crystal growth and structure, and has observed that in certain cases, many types of crystal lattices could form, and yet do not. Curious as to what other forms might be possible, Brian applied NKS techniques to attempt to model crystal growth.

At last year's NKS Summer School, Brian and Stephen Wolfram did a live experiment in an attempt to find new structures in 2D lattices, starting with a seed lattice, using "T"-shaped molecular pieces. This required a refinement step to connect loose legs of the "T" shape. At the time, this method failed to produce the desired results.

Brian then attempted a new method, starting with a seed cluster of molecules, and then substituted more clusters onto the branched ends of the cluster. This led a model of a new type of substance, porous coordination polymer gels, which includes composite materials, xerogels and aerogels with interesting properties. Once the solvent is evaporated from the xerogel, its structure collapses into a film. Depending on the structure of the polymer, the resulting material can be stiff or flexible, or have other useful properties.

Distance Transforms. Cellular Automata on Directed Acyclic Networks. Richard Scott, CDx Laboratories

Distance transforms represent distances between pixel values. The implementation uses the built-in Mathematica function CellularAutomaton with a pure function to propagate differences between neighbours values during its evolution. It is claimed that arbitrary acyclic graphs can be generated this way by choosing particular neighbourhood kernels. The fixed points reached this way does not depend on the update order of the evaluations Examples for totalistic rules are discussed by showing direct visualizations of distances and the corresponding results of running the distance transform. Then selection among different kernels according to the least significant digit is shown to generate approximations of circular shapes which depend on the rules governing selection among the distance transform kernels. Then rotation symmetric kernels are used with the same rule to generate animations which shows a rich variety of interesting spiderweb and spiral patterns featuring dendrtic structures. Hexagonal and snowflake patterns are generated by particular distance transform kernels featuring alternations of neighbor positions and reflections of kernels. Some of the results look like models of diffusions or fluid dynamics. An optimized implementation runs in n*Log n which was discussed in more detail in the NKS forum.

A new DNA encoding technology with application in signal processing of Mechanical Engineering Systems. Considering Cellular Automata and A New Kind of Science in Engineering Science by Quan-Fang Wang, Chinese University of Hong Kong

A kind of "DNA" of signal processing is constructed by a particular construction of encodings which helps to understand mechanical systems. This encoding methodology is related to cellular automata. A twin shuffle language is constructed by complementing the letters of the alphabet used to describe states of a system. This idea is used to encode time series of signals which are transformed by a corresponding twin shuffle language. The resulting encoding is related to binary cellular automaton states.Higher order integration of the evolution steps is achieved by taking differences and finding cellular automaton rules which emulate the differences as iterations of CAs. The approach is demonstrated by examples comparing random initial conditions for CAs with random signal data. Similar comparsisons study emulations of signals generated by formulas involving trigonometric functions, exponentials and special functions. Various plots illustrate particular patterns at various resolutions.

Thomas H. Speller, "Use of Shape Grammar to Derive Cellular Automata Rule Patterns"

Posted by Richard Phillips.

Thomas was an NKS Summer School participant. He said the experience was foundational for his research.

Thomas described a somewhat complicated system (although I may have misunderstood) for using Shape Grammar's - which are basically sets of rules for describing shapes in a generative way.

He addressed System Architecture, Generating a Solution Space, the CA rule space, and he gave examples.

He said a goal is wanting to look a variety of designs rather than just a few.

His approach involves quite alot of details and I didn't follow the details of this model.

The first example was a brick bridge structure.

He described many of the details of the rules, and how to turn the Shape Grammar into a cellular automaton rule.

He showed many examples of system architectures developed for the bridge application. This involves multiple stages.

A final example, of an historic Roman aquaduct, showed how you can look at an existing structure from the point of view of shape grammars.

Some concluding points included the attempt to capture a style of design, and the usefulness of having modular configurations.

Rafal Kicinger, "Generative Design in Civil Engineering Using Cellular Automata"

Posted by Richard Phillips.

The theme was Generative Design and how Rafal applied it to civil engineering applications.

Design representations were discussed. How generative designs differ from the traditional approach. In traditional design there is effectively a complete description of the design.
But in generative design there is no complete description but a core initial design and a generative process.

Designs are grown!

His goal is not just finding new design, but optimal designs. So he needs a fitness measure. He uses both evolutionary search and exhaustive search.

His first example was building structures, coming out of this NKS Summer School 2003 project.

Next he showed an example of traffic control system design in urban areas. One point is that you might only have local information to feed into the control method.

Rafal developed a tool called Emergent Designer to do these things, with many nice features.

For building design he did exhaustive search of the Elementary CAs. And also evolved 1D rules. For traffic control he used evolutionary algorithms on the larger 2D rule spaces. He covered a bunch of details of the experiments.

During the results section he showed some of the best designs. It's quite time intensive to get them. Compared randomly generated designs to CA generated designs, which was interesting.

A broad claim was made that for the building structures problem the cellular automata tended to make better than random designs. Certainly they seemed to have less variance if I understood the graph correctly. Also that generative designs were 6-20% better than traditional representations, and that they were qualitatively different.

He said that they are optimized well by evolutionary algorithms.

In the Q&A Rafal made the point that optimizing the CA rule and initial conditions using the genetic algorithm was better than optimizing the raw building description, since it was a small rule space that maintained (by definition) more order.