Introduction

I have been feeling cynical this week. In its 22nd October issue, New Scientist reported two pieces of news. One was that phone companies are trying to make phone calls sound dreadful. You may say they don't have to try. However, these aren't normal calls; they're voice-over-internet. The companies are using programs written by an outfit named Narus to hunt down and de-prioritise or even kill voice data packets on their internet lines; by doing so, they hope to inconvenience voice-over-internet callers and drive them back to paid calls.

It seems a shame not to spend the brainpower on something more widely beneficial; but at least the result is merely inconvenient. But New Scientist also reported that Roche, holders of the patent on Tamiflu, had until that week refused to let anyone else make this now famous antiviral, even though it will take them over a year to fulfil the orders they already have. I earnestly hope I'll never need to experience for myself how effective Tamiflu is against whichever human-infective bird flu may eventually evolve. But if I do, I shall wish commercial practice had permitted there to be enough for me to try. So, such news items in mind, I decided to concentrate this month's issue on altruism. As well as the final part of my evolutionary art feature, I have two small pieces on assorted open-source AI programs; but my main feature concerns a man who wants to give us open-source hardware. A self-copying rapid prototyper. With all its specs and software under the Gnu Public Licence. On the Web. Oh, and he hopes it will allow open-source drug development too.

Perl Style Regular Expressions in Prolog

A reader, whose mail I'm afaid I must have deleted while sweeping out the night's offerings of mortgage-reduction loans and penis-enlargement creams, wrote to say that the title of last month's Perl Style Regular Expressions in Prolog feature was misleading. Perl goes way beyond standard regular expressions, with extensions such as back-references in the pattern, and even Perl code. However, the course notes from Robert Cameron about which I wrote and from which I took my title, do not deal with these extensions. So they won't tell you how to write a full Perl RE matcher in Prolog, complete with interpreter for interpolated code; but they are still a nice example of Prolog, DCGs, and recursively-defined semantics.

Links

www.cs.sfu.ca/people/Faculty/cameron/Teaching/384/99-3/regexp-plg.html - Perl Style Regular Expressions in Prolog, by Robert Cameron, Simon Fraser University.

perl.plover.com/NPC/ - Perl Regular Expression Matching is NP-Hard, by Mark-Jason Dominus. How allowing one special feature - back-references - in regular expressions means that matching can no longer be done in polynomial time, but becomes NP-hard.

perl.plover.com/Regex/article.html - How Regexes Work, by Mark-Jason Dominus. Nice tutorial on how to implement Perl's RE matching using pennies on circles - or finite automata, as he explains in How to Talk Like a Computer Scientist at perl.plover.com/Regex/sidebar.html. Perl code for his matcher is available; the article is an excellent intro both to RE's and finite automata.

RepRap: Replicating Rapid-Prototypers and the Free Hardware Foundation

The Cessna and the parrot

What's the difference between a Cessna and a parrot? The Cessna costs an awful lot more than the parrot. But since the parrot is an incomparably more subtle and beautiful flying machine than the Cessna, why is it so much cheaper? There's only one reason: parrots can reproduce; aeroplanes can't.

By answering this question, posted to the Open source whatchamacallits thread on the Rapid Prototyping mailing list, Adrian Bowyer explains the motivation behind RepRap, his Replicating Rapid-Prototyper project being carried out at Bath University's Centre for Biomimetic and Natural Technologies and Innovative Manufacturing Research Centre.

A rapid prototyper is, in essence, a 3D printer: a machine that converts a CAD design to a working object. Bowyer aims to build a rapid prototyper that can copy itself, and also make a range of useful household and other objects from suitable designs. And moreover, he intends to place the design, with its accompanying all software and documentation, on the Web under the GNU General Public Licence - the GPL - so that anyone else may build a rapid prototyper too.

A useful virus as big as a fridge

To avoid misunderstanding, I need to say that RepRap's rapid prototyper will copy its components and those of other objects (with some exceptions listed below) but not assemble them. Humans are good at putting together complicated objects from parts - even if, as Bowyer says in his page on the background to RepRap, we grumble at assembling flat-pack furniture - so letting a person do the assembly simplifies the project while still producing something of huge economic benefit. In the biological world, viruses self-copy but don't self-assemble, while most other living things do both. So RepRap is about making a useful virus that's as big as a fridge.

No more unrefillable-printer-cartridge scams

Bowyer goes on to explain that it doesn't matter how much the first RepRap prototyper costs, because the second will cost only as much as its raw materials and its assembly. And so will all subsequent machines. Thus anyone who acquires one machine will be able to have any number they need. People of modest means will be able to own them, and to let their friends have copies. They will be able to make themselves a new flute, a new digital camera, or just a new comb by downloading the necessary CAD designs from the Web. Printer manufacturers keep the price of cartridges artificially high by building in chips that prevent refilling; but this and similar business strategies will not cripple RepRap's objectives, because one will simply change designs to remove such prohibitions before feeding them to the prototyper. Or not design them in in the first place.

Extruded plastics and Wood's-metal wiring

All this is Utopian, but what are the technical details? I am no expert on these technologies, but it seems that there are various different kinds of rapid prototyper - there's a list at the University of Utah Rapid Prototyping Home Page. The kind selected for RepRap is a Fused Deposition Modelling or FDM machine. These extrude a thin thread of molten plastic from a moveable head to build up a shape layer by layer. Several different kinds of plastic can be used in FDM machines: they don't warp or shrink, are tough enough to withstand further machining, and in general, are suitable for making high-precision real-world engineering components. Some examples can be seen on the Web pages of Stratasys, who manufactured the FDM machine used by RepRap.

There are some things the prototyper is not expected to make. These are: self-tapping steel screws; brass bushes; lubricating grease; standard chips such as microcontrollers and optical sensors; a standard plug-in low-voltage power brick; and stepper motors. These are easily and cheaply available, and not trying to fabricate them is a good compromise between what's ultimately desirable and what's possible now. When you fabricate an object, you'll order what you need of these components, copy the rest from the object's CAD design, and assemble the result. If necessary, as it will be when fabricating another replicator, you'll also download any firmware the new object needs.

Although the above list reduces the need to work metal, it doesn't eliminate it. One must be able to make wiring, for example. Working out how to do this was in fact the first stage of the RepRap project, and is described in the report Rapid Prototyped Electronic Circuits. In essence, the researchers fabricated grooves in the plastic and then in a separate process, filled them with the low-melting-point alloy known as Wood's Metal or (since it is actually an alloy) Wood's Alloy. (When I used to read old chemistry books, this substance was recommended for making joke teaspoons that melted in hot tea, though I suspect such experiments would now be banned under health and safety legislation.)

Incidentally, the report says that this way of forming circuitry was inspired by a 1940's attempt to produce cheap radios. In 1944, engineer John Sargrove designed an automatic radio production line which started with a slab of Bakelite moulded with a pattern of grooves and depressions on each side. When these were filled with molten zinc, they formed the wiring and - it seems - some of the radio's passive components. The production line was extremely efficient, but investors feared such automation would threaten people's livelihoods, so the project never got proper funding.

Reprap and AI

Work on RepRap is continuing, in part to render the circuitry-forming technique more reliable and to integrate it with FDM. There's a lot of other research too, some of which can be seen in the RepRap blog. At this stage, software must be RepRap's least pressing worry, materials and machining being much more important. But what is the relevance to AI, if any?

First, the Rapid Prototyped Electronic Circuits report mentions that to test their circuit-forming technology, the researchers made a simple robot. This was a complete success, fulfilling 100% of its specification. So eventually, we shall need control software for RepRap-fabricated robots.

RepRep uses software to control fabrication, but there seems no particular need for AI there. Perhaps it might one day be useful for controlling robots that can assemble the fabricated components - remember that RepRep is a copier, not an assembler. AI could also become important in creating CAD designs. And, as a posting by Brock Hinzmann on the Rapid Prototyping list says:

New tools will be needed to search through the crummy stuff to get to the good stuff. And tools will be needed to search through all the free tools. I heard a talk yesterday on the use of the Semantic Web that suggested we need a Bayesian Web on top of that, in order to deal with all the uncertainty. In some ways funny, but in some ways true.

RepRap invites offers of help from researchers the world over - this is an open-source project and anyone can contribute. Follow the Want to help? link on the RepRap navigation bar.

Links

reprap.org/ - RepRap home page. It's a framed site, with links on the left hand navigation bar. These include project documents, amongst them a one-page executive summary. There is a project blog at reprap.blogspot.com/, with pictures, videos, and day to day progress reports on such things as control software, printer heads, and sources for raw materials.

staff.bath.ac.uk/ensab/ - Adrian Bowyer.

www.bath.ac.uk/mech-eng/biomimetics - Bath University Centre for Biomimetic and Natural Technologies.

www.bath.ac.uk/imrc/mechengineering/mecheng_home.htm - Bath University Innovative Manufacturing Research Centre.

news.scotsman.com/scitech.cfm?id=301722005 - Prepare yourself for rise of the machines by Kevin Hurley. The Scotsman's popular science feature about RepRap, March 2005.

rapid.lpt.fi/archives/rp-ml-current/0498.html - Discussion about RepRap on the Open source whatchamacallits thread of the Rapid Prototyping mailing list. This URL points to Adrian Bowyer's posting comparing a Cessna to a parrot; the list's home page is at rapid.lpt.fi/rp-ml/. Bowyer's posting about open-source drug development is at rapid.lpt.fi/archives/rp-ml-current/0480.html.

http://wohlersassociates.com/blog/ - Sceptical blog entry about RepRap by Terry Wohlers of the Wohlers rapid prototyping and manufacturing consultancy. Search for A Self-Replicating 3D Printer?.

staff.bath.ac.uk/ensab/replicator/other.html - RepRap's links to other universal constructor and rapid prototyping resources.

www.cc.utah.edu/~asn8200/rapid.html - Rapid Prototyping Home Page, University of Utah.

www.stratasys.com/INTL/index.html - Stratasys, manufacturers of the FDM used by RepRap.

www.molecularassembler.com/index.htm - The Molecular Assembler Website, by Robert A. Freitas Jr. This links to the top-level page www.molecularassembler.com/KSRM.htm for the online version of the book Kinematic Self-Replicating Machines by Freitas and Ralph C. Merkle. Despite the site's name, the book does deal with macroscale replicators.

keithlynch.net/april1/fhf.html - Keith Lynch's spoof posting from "Richard N. Stollmin", offering a new Vax-11/780 compatible computer, FREE from Project Knu. Perhaps this is the first mention of a Free Hardware Foundation: "The Free Hardware Foundation opposes the tyranny of hardware manufacturers not allowing everyone to have one of their machines for free." Other humorous pieces are linked from Lynch's page www.keithlynch.net/index.html.

features.linuxtoday.com/news_story.php3?ltsn=1999-06-22-005-05-NW-LF - Richard Stallman - On "Free Hardware", an interview in Linux Today, 1999. "Freedom to copy software is an important right because it is easy now - any computer user can do it. Freedom to copy hardware is not as important, because copying hardware is hard to do."

Charles Stross's Accelerando future histories, envisaging a Free Hardware Foundation that's very close to RepRap's ideals.

rapid.lpt.fi/archives/rp-ml-current/0475.html - Business models for a Free Hardware Foundation, a posting on the Rapid Prototyping list.

The Death of Science

Elspeth takes a swallow of beer. "Perhaps there's no such thing as good old-fashioned curiosity-motivated inquiry any more, but there's still plenty of good science being done.

Darlajane B. says, "I don't disagree with your ideals, Dr Faber, but to me, people like you are very much a relict species, like the coelacanth. You exist in a marginal environment. Always you must struggle for funds, scraps of endowments, sponsorship, and always you must work harder for less and less, because the world cannot any longer afford such work. The nineteenth-century culture of science's Golden Age, which flourished only when ideas could be exchanged freel, was destroyed when scientists became obsessed with making money, and so also with secrecy, because to make a profit they must hide their ideas from their rivals. All the best researchers left the universities to make obscene amounts of money from their little area of speciality in government research facilities and the public sector, and in short order scientific culture consumed itself because there was no one left to generate the basic unprofitable work on which the high-flyers depended. It was like an ecosystem that removes its primary producers."

From the novel White Devils, by Paul McAuley, 2004.

Open Source Swarm Robots: FlockBots

Here's something I came across on robotsnet: FlockBots. This news page reports a Slashdot posting which in turn reports the FlockBots project from the Evolutionary Computation Laboratory at George Mason University:

They're trying to pack as much functionality as possible into a roughly $800, 7" mobile swarmbot, and publish the design and software as a free and open spec. So far their design includes a wireless 200MHz Gumstix linux computer, a camera, range and bump sensors, wheel encoders, a can gripper, and lots more.

According to the project page, FlockBots are being used for research in: ant foraging via digital pheromones or movable beacons; cooperative target observation; herding; collective map building; and dynamic changes in ad-hoc networking topology.

Links

cs.gmu.edu/~eclab/projects/robots/flockbots/pmwiki.php - FlockBots project page.

https://hardware.slashdot.org/story/05/07/06/0155213/open-design-for-800-swarm-robots - The Slashdot posting about FlockBots. There are some interesting points to be found hiding amongst the chat about military applications of FlockBots and their (un)desirability. "Sv-Manowar" (Interesting equipment choice posting) writes about the flexibility of the Acroname Brainstem microcontroller used with the tiny Gumstix. "Anonymous Coward" (Sea Swarm posting) announces work on an underwater version, the biggest problem being inter-bot communication. And "kai.chan" (Deterrent in the Field of Robotics posting) writes about how progress is crippled by lack of standards in hardware, mechanics, and software. Perhaps a candidate for the ultra-portable Pyro software I wrote about in September?

Open Source Java Programs: Expert Systems, Planners, Probabilistic Reasoners, and More

Here's yet more open source, this time from Manageability, Carlos Perez's blog on the manageability of complex software systems. In his Open Source Rule Engines Written In Java, he links to a huge range of expert systems, inference engines, and other software. It includes the JShop2 hierarchical planner, InfoSapient for fuzzy-logic business rules, the Drools rules engine based on the efficient Rete algorithm for rule-matching, and a variety of Semantic Web and RDF tools. Links at the bottom of his list point to open source agent systems, open source probabilistic reasoners, and more. I don't like Java (I find it inelegant and verbose, with objects being a poor substitute for code-reuse via proper modularisation, as well as a poor way to model almost anything); but for those who do, Carlos has amassed a wealth of useful software.

Links

Open Source Rule Engines Written In Java by Carlos Perez..

What is Planning?

I mentioned planners above. Many readers will know what I mean by the word; but for those new to the topic, here are some links.

"Planning" originally meant searching for a path in a state space: that is, finding a sequence of operators that transforms the current state of the world into a desired goal state. Somewhat later, as Robert St. Amant and R. Michael Young point out in their AI Planning Resources on the Web, the kind of search changed: no longer search through a space of states, but search through a space of partial plans. More recently still, the focus has changed again, to planning as constraint satisfaction. There are and have been an assortment of other approaches: for example planning as theorem proving and planning via case-based reasoning. As Subbarao Kambhampati shows in AAAI-2000 Planning Tutorial, it is possible to unify many of these approaches.

Links

www.csc.ncsu.edu/faculty/stamant/papers/links-01-1.pdf - AI Planning Resources on the Web, by Robert St. Amant and R. Michael Young. A concise 2½-page account of planning and where to read about its history and current practice. Probably written in 2000 or 2001.

www.csc.ncsu.edu/faculty/stamant/planning-resources.html - AI Planning Resources, by Robert St. Amant. A list of planners and where they were developed. Last updated in 2003.

www.cs.berkeley.edu/~russell/ai.html#planning - The "planning" section of AI on the Web, by Stuart Russell and Peter Norvig. The other sections are also well worth a visit.

www.cs.umd.edu/projects/planning/ - University of Maryland page on automated planning. Includes pointers to planning domains (environments in which planners can be tested) and - via a link to www.cs.umd.edu/projects/planning/domains.html - the International Planning Competitions.

www.aaai.org - AAAI page on Planning and Scheduling.

rakaposhi.eas.asu.edu/planning-tutorial/ - AAAI-2000 Planning Tutorial by Subbarao Kambhampati, Arizona State. These detailed slides, linked from the AAAI page above, show how far planning has come in the past 50 years, and how the different approaches can be unified.

The Star Maker Evolves a Musical Cosmos

Many of [the Star Maker's] early universes were non-spatial, though none the less physical. And of these non-spatial universes not a few were of the 'musical' type, in which space was strangely represented by a dimension corresponding to musical pitch, and capacious with myriads of tonal differences. The creatures appeared to one another as complex patterns and rhythms of tonal characters. They could move their tonal bodies in the dimension of pitch, and sometimes in other dimensions, humanly inconceivable. A creature's body was a more or less constant tonal pattern, with much the same degree of flexibility and minor changefulness as a human body. Also, it could traverse other living bodies in the pitch dimension much as wave-trains on a pond may cross one another. But though these beings could glide through one another, they could also grapple, and damage one another's tonal tissues. Some, indeed, lived by devouring others; for the more complex needed to integrate into their own vital patterns the simpler patterns that exfoliated throughout the cosmos directly from the creative power of the Star Maker. The intelligent creatures could mnanipulate for their own ends elements wrenched from the fixed tonal environment, thus constructing artifacts of tonal pattern. Some of these served as tools for the more efficient persuit of 'agricultural' activities, by which they enhanced the abundance of their natural food. Universes of this non-spatial kind, though incomparably simpler and more meagre than our own cosmos, were rich enough to produce societies capable not only of 'agriculture' but of 'handicrafts', and even a kind of pure art that combined the characteristics of song and dance and verse. Philosophy, generally rather Pythagorean, appeared for the first time in a cosmos of this 'musical' kind.

From Olaf Stapledon's novel Star Maker, 1937.

Evolutionary Art

Propagation of the prettiest

Last month, I introduced evolutionary art with Evopedia, the self-evolving encyclopaedia. To recap - Evopedia generates initial pages on various topics using Markov techniques to recombine text it finds on the Web. From these, it breeds new generations of page, using mutation and crossover to create them, and Web traffic analysis to rate their fitness.

[A note added as I check the newsletter before sending it out: Evopedia no longer exists. I just got a "not found" message when I tried.]

I'm not sure how useful this traffic analysis is. Evopedia makes clear that it isn't a normal encyclopedia, so readers certainly won't return again and again to the most informative pages as they might in a Wiki. Aren't they more likely to return instead to the most bizarre? That said, traffic analysis ought to work with evolutionary music; if this is worth listening to at all, then counting downloads of evolved tunes posted on the Web should be a good fitness estimator, as friends and colleagues hurry to copy tunes recommended by their mates.

Instead of estimating Web usage as a proxy for human appreciation, why not ask the user directly? There are many programs for evolving visual art that do so. For example, the Alphabet Synthesis Machine, a Java program runnable as an applet. You set the general style of the letters to be evolved by drawing a shape on a blank canvas. This, plus an assortment of control parameters, determines the Machine's fitness function. Set the parameters and launch the evolution, and the applet will generate you a collection of letters from an alien alphabet.

Other interactive art generators are Michael Gold's Using Genetic Algorithms to Generate Evolutionary Art in C# and .NET and Laurence Ashmore's An Investigation Into Evolutionary Art Using Cartesian Genetic Programming, written in Java. Most elaborate and interesting is surely Thomas Jourdan's Kandid, with which I ended last month. This program is written in Java, and you can run it over the Web via the Java WEB Start interface. This is slow, but it's worth persevering. With a variety of image-generating functions to evolve, the ability to save evolved images, and a genome editor you can use during a run, Kandid is a splendid introduction to genetic algorithms.

The Eliza effect in interactive art

You probably know of Eliza, the interactive psychotherapist created by Joseph Weizenbaum. In his book Computer Power and Human Reason, Weizenbaum tells how his secretary kept sitting at a terminal and telling it her troubles even though she knew it was just a program. This worried Weizenbaum and seems to be one reason he wrote the book. I was reminded of this by an interview with Carlo Zanni in the magazine of the Montreal Centre Art Contemporaine:

I'm not sure why today's digital artists are so drawn to aleatoric uses of randomness. Probably there are a lot of different reasons; I certainly find a use for it from time to time. But I'm a little skeptical of artists who endorse an uncritical attitude towards its results. Last May, I saw a very well-known web artist give a talk at a conference called "User_Mode" at the Tate in London. He showed a piece of generative Flash art, in which everytime he clicked the mouse, he got another random arrangement of flower pictures. He was totally transfixed by his own artwork's generativity and kept clicking his mouse over and over, saying "Another one! Magnificent! Another one! Beautiful! And this one, astounding! Oh, marvellous! Miraculous! Dude, I could do this all day!" I was nauseated. His flower collages were good, but they were all equally good and he failed to see that this made them all equally bad as well. It's one thing to endorse the beauty of unexpected outcomes, but we must confront the fact that our algorithms are capable of coldness and ugliness, too, or we will never learn anything.

Aesthetic measure

So far, I've talked about measuring an artwork's fitness by estimating its popularity and by asking the user directly. Another possibility would be to code an explicit fitness function. However, this means coding a measure of aesthetic quality, and we're a long way from being able to do so.

People have tried. One of these was the famous algebraist George Birkhoff, who wrote about his work in his book Aesthetic Measure, published in 1933. There's a good account in the Science News Online feature A Measure of Beauty by Ivars Peterson. In essence, Birkhoff said that an object's beauty increases as its orderliness increases and its complexity decreases. He supported this by examining aesthetic responses to polygons of varying shape and complexity, but also considered paintings, poetry, and the most pleasing design for movie screens.

A more recent attempt is Jürgen Schmidhuber's paper Low Complexity Art, in which he uses Kolmogorov complexity theory to reach a similar conclusion. There are some nice "low complexity" drawings; one of these reminds me of Beardsley.

Evolving the audience

I sometimes wish, when surrounded in the cinema by rustling sweet packets and crunching crisps, that the audience around me was better evolved. That's not what I mean here, however. Lacking a way to code a fitness function for aesthetic quality, let's try learning one. And since evolutionary computing is one possible learning method, let's use that.

Such a system is Bruce Jacobs's music program Variations. His bottom line is:

I want to write more music than I have time to write. To this end, I've represented my personal composition methodology in a set of algorithms which my computer uses to write music for me. Since I do not have time to listen to everything the system creates (not all of it is good), I also developed a set of filters that "listen" to the music and grade it.

Variations has three modules: Composer, Ear, and Arranger. Ear embodies a musical fitness function, and was itself evolved by presenting to it samples of music, Jacobs's ratings of these being its own measure of fitness. Ear's "chromosomes", which Jacobs explains with musical scores in his paper Composing With Genetic Algorithms, code for valid pitch transitions, i.e. the musical distance between one chord and the next. They are built out of smaller units which code for chords, i.e. notes played simultaneously.

Once Variations has evolved an Ear, it evolves a Composer. This module takes musical motifs - short themes or sequences of notes that will recur, with variation, throughout the music - and creates variations on them which it then glues together to make an entire musical phrase.

Composer has data structures that tell it how to create these variations. These are its chromosomes. It is initialised with randomly-generated chromosomes, and then breeds successively better ones by using Ear to rate its output. The end result is a Composer that can create musical phrases acceptable to Ear and hence to Jacobs.

The Variations program is now ready to begin composing, which it does simply by running Composer and feeding the resulting phrases to the third module, Arranger, which arranges them into a complete musical composition.

Jacobs claims, in Algorithmic Composition As a Model of Creativity that this structure models the way he composes music. Not the "divine inspiration" brand of creativity, but the legwork we have to slog through when inspiration fails us:

There are two distinct types of creativity: the flash out of the blue (inspiration? genius?), and the process of incremental revisions (hard work). Not only are we years away from modeling the former, we do not even begin to understand it. The latter is algorithmic in nature and has been modeled in many systems both musical and non-musical.

Pavarotti and the ants

In a paper reminiscent of my Star Maker excerpt above, Living Melodies: Coevolution of Sonic Communication, Palle Dahlstedt and Mats G. Nordahl of Chalmers University of Technology describe a world of creatures that evolve to sing to one another. The authors' want to use these songs as musical raw material: as they put it, "a fundamental goal of artistic expression is to create meaningful structures that one cannot immediately envision, to avoid repeating worn formulae and tedious mannerisms". In doing so, they have devised an interesting and unusual evolutionary setup.

Dahlstedt and Nordahl's creatures live in a two-dimensional grid. Each creature occupies one cell at a time, and can walk in any of the eight possible directions from it. Each creature has two sets of genes. One set determines its walking, foraging, and singing behaviour; the other the songs it likes listening to. To drive evolution, restrictions are put on the creatures' reproduction - two creatures can mate only if they are next to one another, have sufficient energy, are over a certain age, and have exercised recently. This selects for fit individuals, and the "over a certain age" stipulation means they must already have managed to survive for a reasonable time.

The authors cause evolution to link the two sets of genes within a creature, and the creatures considered as a community, by also requiring that to mate, creatures must be happy. In this universe, this means that each prospective parent must recently have heard a song that it likes. This drives co-evolution, with the result that:

We have constructed a world of interacting artificial creatures that generate interesting and musically useful sonic structures. In this world, the main feature is not so much that the individual creatures develop interesting sounds. It is more about listening to the process of evolution of simple creatures working together, triggering each other, and playing a small part each. The process is more like creating a singing ant colony than trying to create a Pavarotti ant.

Genetic jazz - every day, on WDYN

I have just found a radio station that plays AI-generated music every day. Go to Dynamic Recording Studio's Al Biles page, and you will see that the page is topped with a transmitter-mast logo and the words "WDYN Radio - An Independent Radio Station that plays Gen Jam Every Day". Then scroll down, and you read "If you think jazz musicians are born and not bred, you should listen to GenJam".

Someone must have waited for ages to apply that sentence, because GenJam is indeed bred. It's another genetic algorithm, this time developed to play jazz solos. "As a CD, GenJam is an eclectic mix of straight up jazz with bits of latin, funk, even new age thrown in. As computer software, GenJam is a genetic algorithm that learns to play jazz solos under the guidance of its creator and mentor, Al Biles". Yes, you can buy GenJam's CD.

On his home page, Biles says that GenJam can listen to him play solo and improvise a "smart echo", anywhere from a beat to a measure behind. And it can "trade fours", the jazzman's term for a kind of musical conversation where musicians in a combo take turns to play four bar solos. These aren't independent - instead, each is related in some way to what has gone before. GenJam is able to work fast enough to keep up with the humans around it in such musical exchanges.

Biles's page carries a lot of technical information about GenJam, in the form of links to papers and other publications. He also maintains an evolutionary music page. This is definitely worth following up: he distinguishes toy- from non-toy programs, and can be more careful in separating out the different aspects of musical composition than can a non-musician.

Finally, unlike most evolutionary music researchers, Biles's page also carries a list of gig dates, tours, and booking details. As Jeff Spivak, Staff Music Critic of the Rochester Democrat and Chronicle wrote in a review:

Al Biles has created the perfect backing band: one that doesn't drink, smoke or whine about long bus rides to the gig.

Links

These links continue the list I gave at the end of last month's feature.

Evolving visual art

alphabet.tmema.org/ - Alphabet Synthesis Machine, by Golan Levin with Jonathan Feinberg and Cassidy Curtis.

acg.media.mit.edu/people/pcho/thesis/pchothesis.pdf - Computational Models for Expressive Dimensional Typography, by Peter Sungil Cho, MIT, 1997. An assortment of typographical art forms, and a demonstration of why typography is complicated to represent.

www.c-sharpcorner.com/Code/2003/Oct/GAArt.asp -* Using Genetic Algorithms to Generate Evolutionary Art in C# and .NET*, by Michael Gold.

www.emoware.org/evolutionary_art.asp - An Investigation Into Evolutionary Art Using Cartesian Genetic Programming, by Laurence Ashmore.

kandid.sourceforge.net/index.html - The Kandid genetic art program, written by Thomas Jourdan.

www.hybridsociety.net/pdf_files/model_proposal.pdf - Model Proposal for a Constructed Artist, by Penousal Machado and Amílcar Cardoso, University of Coimbra. Describes a prototype art generator using fractal image compression, genetic algorithms, and neural nets trained on existing artwork to evaluate the results.

eden.dei.uc.pt/~machado/research/pdf/aisb2002.pdf - Giving Colour to Images, by Penousal Machado, André Dias, Nuno Duarte, and Amílcar Cardoso, Coimbra.

eden.dei.uc.pt/~machado/NEvAr/ - Web site for NEvAr (Neuro Evolutionary Art), an evolutionary artist developed by Machado and colleagues which uses genetic programming. Includes an image gallery, pages where you can see sample genomes (genetic program trees) and try genetic crossover and mutation, and links to papers. Some information seems only to be available via the right-pointing arrows at the bottom of the pages, so don't ignore these.

www.cosc.brocku.ca/~bross/research/ - Links to Brian Ross's work on evolving procedural textures.

www.josos.org/index/030-writings/artandsex.pdf - Why Artworks Should Have Sex, by Simon de Bakker.

Evolving music

www.ee.umd.edu/~blj/algorithmic_composition/ - VARIATIONS: Algorithmic Composition for Acoustic Instruments, by Bruce Jacobs, 1994 onwards. Links to Jacob's papers, to Perl source for his program, and to audio files and musical scores demonstrating the output.

www.davidschoenberger.net/joy/career/research/MusicalCompositionWithGeneticAlgorithms.pdf - Genetic Algorithms for Musical Composition with Coherency Through Genotype, by Joy Schoenberger, 2002. Slides for a graduate project based on Variations. C++ code, and music samples, available from www.davidschoenberger.net/joy/career/research.html.

www.design.chalmers.se/projects/art_and_interactivity/living-melodies/LMpaper.html - Living Melodies: Coevolution of Sonic Communication, by Palle Dahlstedt and Mats G. Nordahl of Chalmers University of Technology, 2000.

http://www.it.rit.edu/~jab/GenJam.html - Al Biles's GenJam page. History, technical info, and publications on GenJam and evolutionary music in general. Also gig dates, ordering details for GenJam's CD, and booking info for the Virtual Quintet.

www.it.rit.edu/~jab/Spevak.html - Review of GenJam by Jeff Spivak, Staff Music Critic of Rochester's Democrat and Chronicle, 1996.

Interview with Al Biles for Generation5, 1998.

www.dynrec.com/biles1.html - The Al Biles and GenJam page at Dynamic Recording.

www.pawfal.org/index.php?page=LsystemComposition - Pawfal ("poor artists working for a living") page about using Lindenmayer systems (also known as L-Systems) for generating music. An L-System is a set of production rules forming a grammar for a language, used to generate a string rather than parsing one. By interpreting this string as graphics commands, we can draw plant-like patterns: L-Systems were devised to model the development of simple multicellular organisms such as algae, as the links in the following section will show. The work described here, however, interprets strings to musical scores, and uses genetic algorithms to evolve the L-Systems.

www.it.rit.edu/~jab/EvoMusic/EvoMusBib.html - Al Biles's evolutionary music resources. Recommended: non-musicians usually underestimate the complexity of music and the information required to represent it.

L-Systems

www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html - A brief intro intro to L-Systems, by Gabriela Ochoa. See also also the Wiki article at en.wikipedia.org/wiki/L-system.

algorithmicbotany.org/ - Much more on L-Systems, at the site for the University of Calgary Algorithmic Botany group led by Przemyslaw Prusinkiewicz. The site includes info about the Virtual Laboratory for simulating plant development.

Evolutionary computing

www.red3d.com/cwr/evolve.html - Evolutionary Computation and its application to art and design. Craig Reynolds's links. There's lots of interesting stuff, including Renolds's own work - for example Evolution of Corridor Following Behavior in a Noisy World - but the page hasn't been updated since 2002. Favourites of mine remain Karl Sims's wonderful virtual creatures.

surf.de.uu.net/encore/ - ENCORE Evolutionary Computation Archive, by Jörg Heitkötter: "a huge amount of information and very funny."

www.geneticprogramming.com/ - Directory for information about Genetic Programming, Artificial Intelligence, Genetic Algorithms, Evolutionary Computation and robotics, by Jaime Fernandez. Includes conferences, researchers, journals, software, papers and more.

www.technologyreview.com/articles/05/02/issue/feature_algorithms.0.asp - Unnatural Selection, By Sam Williams for Technology Review, 2005. A nice popular-science feature on evolutionary computation, including Koza's work and Searchspace's programs for detecting fraud via analysis of financial data.

www.genetic-programming.org/ - John Koza's genetic programming site, which also links to some non-GP stuff. "Genetic programming is an automated method for creating a working computer program from a high-level problem statement of a problem. Genetic programming starts from a high-level statement of .what needs to be done. and automatically creates a computer program to solve the problem. There are now 36 instances where genetic programming has automatically produced a result that is competitive with human performance, including 15 instances where genetic programming has created an entity that either infringes or duplicates the functionality of a previously patented 20th-century invention, 6 instances where genetic programming has done the same with respect to a 21st-centry invention, and 2 instances where genetic programming has created a patentable new invention."

www.genetic-programming.com/johnkoza.html - Koza's home page, including a list of his books and accompanying videos with summaries of their main points. His fourth book, 2003, is challengingly titled Genetic Programming IV: Routine Human-Competitive Machine Intelligence. "Genetic programming now routinely delivers high-return human-competitive machine intelligence."

www.genetic-programming.org/gpftpsite.html - Some genetic programming software. Last updated 2003.

www.genetic-programming.com/sevendiffs.html - Koza's list of seven differences between genetic programming and other AI techniques.

evonet.lri.fr/evoweb/news_events/news_features/article.php?id=15 - Genetic pragmatism - an exclusive interview with John Koza, on EvoWeb, funded by the EU IST programme. "Back in the early sixties, when the University of Michigan offered the world's only BA course in Computer Science, one of the first undergraduates that John Holland taught was a young man who went on to set up a company that built computer systems for state lotteries and printed instant lottery tickets. For a time it looked at if John Koza's only claim to fame would be the invention of the scratch card."

www.idsia.ch/~juergen/gp.html - Jürgen Schmidhuber on pre-Koza work on program evolution and genetic programming. "Genetic Programming (GP) is a special instance of the broader and older field of Program Evolution. GP was apparently invented by Nichael Cramer in 1985."

www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/surveyRN76.pdf - Genetic Programming - Computers using "Natural Selection" to generate programs, by William Langdon and Adil Qureshi. A good survey and explanation of genetic programming up to about 1994.

www.cs.bham.ac.uk/~wbl/biblio/gp-bibliography.html - Genetic programming bibliography maintained by William Langdon, Steven Gustafson, and John Koza.

jasss.soc.surrey.ac.uk/2/1/review1.html - The Uses of Genetic Programming in Social Simulation: A Review of Five Books, by Bruce Edmonds Centre for Policy Modelling, Manchester Metropolitan University. A useful explanation of genetic programming, with reviews including those of Koza's Genetic Programming and Genetic Programming II. Edmonds focusses on social simulation, obviously, but the page is worth reading by those working in other fields: note for example the warning in Section 3.2.1 against using genetic programming as a stand in for a learning process regardless of whether its characteristics are appropriate.

www.doc.ic.ac.uk/~sgc/teaching/v231/lecture17.html - Lecture 17 Genetic Programming. An introduction to genetic programming by Simon Colton, with a useful 7-point list showing how to characterise a genetic program.

Aesthetic measure

www.sciencenews.org/articles/20040522/mathtrek.asp - A Measure of Beauty, by Ivars Peterson for Science News Online, 2004.

www.idsia.ch/~juergen/locoart/locoart.html - Low Complexity Art, by Jürgen Schmidhuber, 1997. See www.idsia.ch/~juergen/locoart/node12.html for some low complexity drawings.

The Eliza effect in interactive art

www.gslis.utexas.edu/~palmquis/courses/reviews/amy.htm - One of several reviews of Computer Power and Human Reason which tells the story of Weizenbaum's secretary.

www.atariarchives.org/bcc2/showpage.php?page=298 - Detailed reviews of Computer Power and Human Reason for Creative Computing, by John Lees, John McCarthy, and Peter Kugel.

www.flong.com/writings/interviews/interview_ciac.html - Interview with Carlo Zanni for CIAC Magazine by Golan Levin, June 2004.

Do Stuff Because It's Wonderful

Pete touched spex knobs and leaned forward. "What you got there?"

"Dead robots. They ate our foamchocks, right out of the ceiling. They eat anything. I killed the ones that tried to break into camp." Katrinko stroked at a midair menu, then handed Pete a fiber lead for his spex. "Check this footage I took."

Katrinko had been keeping watch with the gelcams, picking out passing robots in the glow of their engine heat. She'd documented them on infrared, saving and editing the clearest live-action footage. "These little ones with the ball-shaped feet, I call them keets," she narrated, as the captured frames cascaded across Pete's spex-clad gaze. "They're small, but they're really fast, and all over the place. I had to kill three of them. This one with the sharp spiral nose is a drillet. Those are a pair of dubits. The dubits always travel in pairs. This big thing here, that looks like a spilled dessert with big eyes and a ball on a chain, I call that one a lurchen. Because of the way it moves, see? It's sure a lot faster than it looks."

Pete stared at the dissected robots, a cooling mass of nerve-netting, batteries, veiny armor plates, and gelatin. "Why do they look so crazy?"

"'Cause they grew all by themselves. Nobody ever designed them. ... Let's say you want to make a can-opener. Well, you could study other people's can-openers and try to improve the design. Or else you could just set up a giant high-powered virtuality with a bunch of virtual cans inside it. Then you make some can-opener simulations, that are basically blobs of goo. They're simulated goo, but they're also programs, and those programs trade data and evolve. Whenever they pierce a can, you reward them by making more copies of them. You're running, like, a million generations of a million different possible can-openers, all day every day, in a simulated space."

The concept was not entirely alien to Pete. "Yeah, I've heard the rumors. It was one of those stunts like Artificial Intelligence. It might look really good on paper, but you can't ever get it to work in real life."

"Yeah. But let's imagine you're into economic warfare and you figure out how to do this. Finally, you evolve this super weird, super can-opener that no human being could ever have invented. Something that no human being could even imagine. Because it grew like a mushroom in an entire alternate physics. But you have all the specs for its shape and proportions, right there in the supercomputer. So to make one inside the real world, you just print it out like a photograph. And it works! It runs! See? Instant cheap consumer goods."

Pete thought it over. "So you're saying the Sphere people got that idea to work, and these robots here were built that way?"

"Pete, I just can't figure any other way this could have happened. These machines are just too alien. They had to come from some totally nonhuman, autonomous process. Even the best Japanese engineers can't design a jelly robot made out of fuzz and rope that can move like a caterpillar. There's not enough money in the world to pay human brains to think that out."

But who the heck would take the trouble to create a giant hole in the ground that's full of robots. I mean, why?"

Katrinko shrugged. "I guess it's just the Sphere, man. They still do stuff just because it's wonderful."

From Bruce Sterling's novelette Taklamakan, published in* Asimov's* for October/November 1998, also in his collection A Good Old-Fashioned Future and in The Year's Best Science Fiction, Sixteenth Annual Collection, edited by Gardner Dozois.

Links

www.brandeis.edu/news/golem.html - Science Catches up to Science Fiction: Brandeis DEMO Lab moves the world closer to robot evolution, from Brandeis University News, August 30th 2000. Includes a quote from Sterling: "The thing they're doing in that lab is really close to the central gimmick of my Hugo-Award-winning story 'Taklamakan' (1998). That story [just] came out, and here they are trying to ship product already!".

blog.wired.com/sterling/ - Sterling's blog, with some excellent photos.

uyghur.50megs.com/photo.html - The Uyghur Photo Site with images of the real Taklamakan.

Until next month.