|
AI - The art and science of making computers do interesting things that are not in their nature.
Update to last month's "Regular expressions in Prolog";
The University of Bath Replicating Rapid-Prototyper;
FlockBots: Open source swarm robots;
Open source Java AI software;
What is planning?;
Final part of the evolutionary art feature
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.
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.
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.
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.
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.
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.
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.
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.
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
href="http://reprap.blogspot.com/">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.
href="http://staff.bath.ac.uk/ensab/">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.
www.wohlersassociates.com/Wohlers-Talk.html -
Sceptical blog entry about RepRap by
Terry Wohlers of the Wohlers rapid prototyping and manufacturing
consultancy. Search for
A Self-Replicating 3D Printer?.
href="http://staff.bath.ac.uk/ensab/replicator/other.html">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.
href="http://keithlynch.net/april1/fhf.html">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
href="http://www.keithlynch.net/index.html">www.keithlynch.net/index.html.
href="http://features.linuxtoday.com/news_story.php3?ltsn=1999-06-22-005-05-NW-LF">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."
href="http://www.accelerando.org/_static/accelerando.html">www.accelerando.org/_static/accelerando.html -
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.
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.
Here's something I came across on
robots.net:
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.
cs.gmu.edu/~eclab/projects/robots/flockbots/pmwiki.php -
FlockBots project page.
hardware.slashdot.org/article.pl?sid=05/07/06/0155213 -
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?
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.
www.manageability.org/blog/stuff/rule_engines/view -
Open Source Rule Engines Written In
Java by Carlos Perez. His home page is
at
href="http://www.manageability.org/">www.manageability.org/.
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.
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/AITopics/html/planning.html -
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.
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.
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 http://www.evopedia.com .]
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.
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! <click> Another one! Beautiful! <click> And this
one, astounding! <click> Oh, marvellous! <click> Miraculous! <click>
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.
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.
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.
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.
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.
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 Amlcar 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 Amlcar 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.
www.generation5.org/content/1999/biles.asp -
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.
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.
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.
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.
|
