To: alife@cognet.ucla.edu Subject: Alife Digest Volume #061 Alife Digest, Number 061 Monday, August 26th 1991 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~ Artificial Life Distribution List ~ ~ ~ ~ All submissions for distribution to: alife@cognet.ucla.edu ~ ~ All list subscriber additions, deletions, or administrative details to: ~ ~ alife-request@cognet.ucla.edu ~ ~ All software, tech reports to Alife depository through ~ ~ anonymous ftp at polaris.cognet.ucla.edu in ~ftp/pub/alife ~ ~ ~ ~ List maintainers: Liane Gabora and Rob Collins ~ ~ Artificial Life Research Group, UCLA ~ ~ ~ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Today's Topics: UCLA Apology Alife-relevant Highlights of the GA Conference Request for help with GA SEX A new journal SIGGRAPH '91 from an ALife perspective ---------------------------------------------------------------------- Date: Mon, 26 Aug 91 13:18:43 PDT From: David Jefferson Subject: UCLA Apology Dear friends and fellow A/Lifers, As you know, we have been having trouble with our network and mailing list software since bringing the A/Life Digest to UCLA. Some of you have received Digests with expanded headers, messages sent to alife-request, as well as extra copies of some messages. We wish to apologize for the widespread inconvenience caused by these problems. To make matters worse, while attempting to fix the problems we made the mistake of sending out several messages from the account of the moderator, Liane Gabora, in such a way that they appeared to originate with her. In fact, they were sent by our staff, and Liane is not responsible for them. Once again, we apologize for the errors. We continue to have full confidence in Liane Gabora as the moderator of this Digest. We are confident now that we have all of our technical problems straightened out, and we expect that the A/Life Digest will run smoothly from now on. Nonetheless, should any non-routine problem concerning the Digest arise in the future, please do not hesitate to contact us. Sincerely, David Jefferson, Computer Science, UCLA jefferson@cs.ucla.edu Charles Taylor, Biology, UCLA taylor@cognet.ucla.edu ------------------------------ Subject: Alife-relevant Highlights of the GA Conference Date: Thu, 01 Aug 91 12:43:32 PDT From: todd%galadriel@Forsythe.Stanford.EDU The Artificial Life and Genetic Algorithms/Evolutionary Approaches workshop at the Fourth International Conference on Genetic Algorithms (ICGA91) in San Diego, CA, last month was a great success, with over a hundred people in attendance, and ten speakers crammed into two and a half hours. Along with the frequent mention of themes of adaptive agents and artificial life throughout the plenary addresses and other talks at the conference, enthusiasm at this workshop was a strong indication that ALife research and problems are becoming one of the central threads of the field of genetic algorithms. Peter Todd (todd@psych.stanford.edu) and Geoffrey Miller (geoffrey@psych.stanford.edu) of the Stanford University Psychology Department organized the workshop around short talks on current research, each of which addressed a more general issue in the discussion of GA-based ALife research. Peter began by stressing the importance of making our research aims clear: whether we are creating ALife applications (adaptive robots, VR pets, etc.), modeling biological phenomena, or exploring the more general realm adaptive agency (looking at interactions of adaptive processes abstracted from the particulars of carbon-based biochemistry, performing what John Holland described as gedanken- experiments which lead to further investigations), and whether we wish to frame our work in an educational context. (To this list Michael Littman later added "having fun," also very valid.) Once our goals have been specified, we can begin to consider how GA's and evolutionary modeling can fit into our research program. Geoffrey proceeded to lay out a theoretical framework of general issues and questions to consider in evolutionizing artificial life. Among these were the place of GAs and evolutionary methods as the stage-setters for ALife, emphasizing their non-teleological, emergent fitness-function uses--letting "evolution take care of its own," rather than pre-specifying the goals and behaviors of an ALife system by hand; the importance of observation, exploration, and experimentation in this realm, not being afraid to perform careful experiments and test hypotheses, and need to develop theoretical analysis tools to aid in these activities; the question of what exactly should be evolved, at how many levels: just behavioral mechanisms, or sensory and motor systems as well at the lower end, and social and communication systems higher up?; the importance of genotype to phenotype development schemes, and increased scalability of our methods to larger and larger problems; the crucial role of social interactions and co-evolving groups in creating dynamic emergent adaptive landscapes; the possibilities for allowing smooth evolved phylogenies through scaling up environmental, behavioral, and physiological complexity; and the place of GA researchers as possible mediators between the worlds of evolutionary biology and artificial life. The speakers throughout the rest of the workshop addressed various of these issues through their own research. Michael Littman (mlittman@breeze.bellcore.com) from Bellcore presented a summary of recent work simulating the evolution of learning. He covered papers by Hinton & Nowlan (1987), Maynard Smith (1987), Belew (1990), Fontanari & Meir (1990, Complex Systems), Ackley & Littman (1990), Todd & Miller (1990), and Littman & Ackley (1991, ICGA) (note: all of the papers listed without sources are referenced in the short ALife/GA bibliography distributed at the workshop--see details at the end of this message). His main message was that individual adaptation (learning) can improve genetic adaptation (GA/evolution) by making it more robust against the perils of difficult search spaces, sexual recombination, mutation, and certain types of environmental noise and environmental change, as the listed papers demonstrate. John Koza (koza@sunburn.stanford.edu) from Stanford next presented his work evolving what he called a subsumption-type architecture (a la Rod Brooks) in a Lisp program to control a simulated mobile robot whose task is to use radar cues to circumnavigate a room and collect "points pellets". His evolutionary programming method for evolving Lisp expressions yielded compact programs capable of performing this feat, and which he said would generalize to other room configurations; much discussion was generated on this point. Hiroaki Kitano (hiroaki@a.nl.cs.cmu.edu) from NEC and CMU spoke on his work evolving neural network architectures via a developmental scheme employing L-system rewrite grammar rules. Such architectures can be much more regular than those generated purely by GA-type evolution, and he presented data showing that they evolve more quickly and generalize better to larger network sizes, using smaller chromosome lengths. Rob Collins pointed out that this could be due to the smaller phenotype range that such restrictured chromosomes can code for, a possible advantage of this method. Kazuhiro Matsuo (matsuo@sutra.syslab.iias.flab.fujitsu.co.jp) from Fujitsu presented a summary of his paper on evolving a cooperative society in his "Game World," where spatially-distributed individuals play iterated games (like the Prisoner's Dilemma) with their neighbors and strategies are chosen which maximize the cooperativity score of the society as a whole. In this setup, he found that different selection rules would lead to different dynamics of rule-propagation throughout the population, some societies settling to Tit-for-Tat, others oscillating between defection, "skepticism," and cooperation. Inman Harvey (inmanh@cogs.sussex.ac.uk) from Sussex addressed the problem of scaling ALife systems upwards in complexity, by means of gradual increases in genotype length. Problems with crossover between genotypes of widely varying lengths furthermore suggest keeping these lengths nearly equal in a given population, he said (though David Ackley reported he'd had some success wihtout this restriction). His results, supported by a simulation extending Kauffman's NK model, are to be applied to any instance of open-ended (and species-based) evolution. Stewart Wilson (wilson@cmns.think.com) from the Rowland Institute for Science emphasized the importance of considering the structure of the environment, in addition to the structure of the individual creature, in simulations of ALife. One of the ways to represent the environment is as a finite-state machine which takes as inputs a creature's behavior, and produces as outputs new states of the environment and often new sensory vectors corresponding to the creature's relation to it. Stewart presented the beginnings of a classification scheme for environment types which should help to clarify the adaptive tasks facing (real and artificial) creatures in different niches. Rob Collins (rjc@cs.ucla.edu) from UCLA argued for the importance of considering the great store of knowledge and theory that has been developed by theoretical biologists when addressing similar topics in ALife research. While the majority of mathematical biology work has been concerned with asymptotic behavior--what happens as evolutionary time goes to infinity--and GA work has mostly stuck to much more short-term effects, both fields still have a lot to offer to each other, and very interesting work may take place at the interface--medium-term evolution--between the two. Finally, Jonathan Schull (j_schull@acc.haverford.edu) from Haverford emphasized the importance throughout our work of using the right evolutionary metaphors. If we only consider the simple hill-climbing metaphor of evolution, we will come up with models limited by that picture, and miss most of the interesting things going on--which come about because of the *interaction* of different adaptive processes. Jon proposed that the behavior of entire species themselves may be a much more appropriate image upon which to model our studies of the intelligent actions of adaptive agents. In addition, Miller and Todd distributed a short, selective bibliography of some of the relevant work in evolution, psychology, artificial life, and genetic algorithms; much of the research described at the workshop is represented. This bibliography is available electronically by sending a request to either geoffrey@psych.stanford.edu or todd@psych.stanford.edu; and while this bibliography is not being explicitly maintained and expanded, suggestions for relevant further references may appear in future versions. Thanks to all who attended and participated in this workshop, and made it such a success--keep up the good work evolutionizing ALife, and bringing the important and interesting questions of this field to the forefront of the GA world-- Peter Todd ANNOUNCEMENT: Peter Todd and Geoffrey Millers' Alife/GA Bibliography will be sent out in the next volume of the Artificial Life Digest. ------------------------------ Date: Fri, 19 Jul 91 11:12:56 PDT From: cdavis%sunstroke@sdsu.edu (Craig Davis) Subject: Request for help with GA SEX I have written a program that uses Genetic Algorithms to compete an asexual species with a sexual one. The sexual species can have assortative or random mating. I need some one to check this program for me. It is written in Microsoft BASIC for the Mac. If the program is a proper mimic of a natural population, two concepts are predicted. Assortative mating is a very powerful reason for having sex. Sexual reproduction can deal with a very high level of mutation. The source program is ready for email. ------------------------------ Date: Fri, 2 Aug 91 15:30:48 +0200 From: meyer%FRULM63.BITNET@mvs.oac.ucla.edu(Jean-Arcady MEYER) Subject: A new journal ============================= Call for papers ============================== A D A P T I V E B E H A V I O R An international journal devoted to experimental and theoretical research on adaptive behavior in animals and in autonomous artificial systems, with emphasis on mechanisms, organizational principles, and architectures that can be expressed in computational, physical, or mathematical models. Broadly, behavior is adaptive if it deals successfully with changed circumstances. The adapting entities may be individuals or populations, over short or long time scales. The journal will publish articles, reviews, and short communications that treat the following topics, among others, from the perspective of adaptive behavior. Perception and motor control Ontogeny, learning and evolution Motivation and emotion Action selection and behavioral sequences Internal world models and cognitive processes Architectures, organizational principles, and functional approaches Collective behavior Characterization of environments Among its scientific objectives, the Journal aims to emphasize an approach complementary to traditional AI, in which basic abilities that allow animals to survive, or robots to perform their mission in unpredictable environments, will be studied in preference to more elaborated and human-specific abilities. The Journal also aims to investigate which new insights into intelligence or cognition can be achieved by explicitly taking into account the environmental feedback --mediated by behavior--that an animal or a robot receives, instead of studying components of intelligence in isolation. The journal will be published quarterly, beginning with the Summer issue of 1992. EDITOR-IN-CHIEF Jean-Arcady Meyer (Ecole Normale Superieure, France) email: meyer@wotan.ens.fr meyer@frulm63.bitnet tel: (1) 43 29 12 25 ext 3623 fax: (1) 43 29 70 85 ASSOCIATE EDITORS Randall Beer (Case Western Reserve Univ., USA) Lashon Booker (MITRE Corp., USA) Jean-Louis Deneubourg (Univ. of Bruxelles, Belgium) Janet Halperin (Univ. of Toronto, Canada) Pattie Maes (MIT Media Lab., USA) Herbert Roitblat (Univ. of Hawaii, USA) Ronald Williams (Northeastern University, USA) Stewart Wilson (The Rowland Institute for Science, USA). EDITORIAL BOARD David Ackley (Belcore, USA) Michael Arbib (Univ. South. California, USA) Andrew Barto (Univ. of Massachusetts, USA) Richard Belew (Univ. of California, USA) Rodney Brooks (MIT AI Lab., USA) Patrick Colgan (Canadian Museum of Nature, Canada) Holk Cruse (Univ. Bielefeld, Germany) Daniel Dennett (Tufts Univ., USA) Jorg-Peter Ewert (Univ. Kassel, Germany) Nicolas Franceschini (Univ. Marseille, France) David Goldberg (Univ. of Illinois, USA) John Greffenstette (Naval Research Lab., USA) Patrick Greussay (Univ. Paris 8, France) Stephen Grossberg (Center for Adaptive Systems, USA) John Holland (Univ. Michigan, USA) Keith Holyoak (Univ. California, USA) Christopher Langton (Los Alamos National Lab., USA) David McFarland (Univ. of Oxford, UK) Thomas Miller (Univ. of New Hampshire, USA) Norman Packard (Univ. of Illinois, USA) Tim Smithers (Edinburgh Univ., UK) Luc Steels (VUB AI Lab., Belgium) Richard Sutton (GTE Labs., USA) Frederick Toates (The Open University, UK) David Waltz (Thinking Machines Corp., USA) To be published, an article should report substantive new results that significantly advance understanding of adaptive behavior. Critical reviews of existing work will also be considered. Contributions will originate from a range of disciplines including robotics, artificial intelligence, connectionism, classifier systems and genetic algorithms, psychology and cognitive science, behavioral ecology, and ethology among others. Ideally, an article will suggest implications for both natural and artificial systems. Authors should aim to make their results, and the results' significance, clear and understandable to the Journal's multi- disciplinary readership. Very general, speculative, or narrowly specialized papers, papers with substantially incomplete conceptual, experimental, or computational results, or papers irrelevant to the subject of adaptive behavior may be returned to authors without formal review. Submissions should be sent to: Dr. Jean-Arcady Meyer, Editor Adaptive Behavior Groupe de BioInformatique Ecole Normale Superieure 46 rue d'Ulm 75230 Paris Cedex05 FRANCE Please send five (5) copies of all materials. Manuscripts must be in English, with American spelling preferred. Please briefly define terms that may not be familiar outside your specialty. Avoid jargon and non-standard abbreviations. Make every attempt to employ technical terms that are already in use before making up new ones. The following guidelines should be adhered to, or papers may be returned for reformatting prior to review. Double-space all materials. Manuscripts should be typed (or laser printed) on 8 1/2 x 11 inch or A4 paper, one side only, with one-inch margins all around. Every page should be numbered in the upper right hand corner starting with the title page. Manuscript length should not normally exceed the equivalent of twenty journal pages. The title page (page 1) should have: - the paper's title, preferably not too long - the names, affiliations, and complete addresses of the authors, including electronic mail addresses if available - a daytime telephone number for the author with whom the editors should correspond. The second page should contain an abstract of 200 words or less, a list of six or fewer key words, and a shortened title for use as a running head. Begin the text of the article on page 3. Aid the reader by dividing the text into logical sections and subsections. Footnotes may be used sparingly. Follow the text with acknowledgements on a separate page. Begin the reference list on a new page following the acknowledgements page. References and citations should conform to the APA Publication Manual except: (1) do not cite page numbers of any book; (2) use the same format for unpublished references as for published ones. Please carefully check citations and references to be sure thay are correct and consistent. Note that the names of all authors of a publication should be given in the reference list and the first time it is cited in the text; after that "et al." may be used in citations. If a publication has 3 or more authors, "et al." may also be used in the first citation unless ambiguity would result. Include figures and tables at the end of the manuscript. Number them consecutively using Arabic numerals. Include a brief title above each table and a caption below each figure. Indicate in the text an approximate position for each figure and table. Besides graphical material, figures consisting of high quality black and white photographs are acceptable. Submit only clear reproductions of artwork. Authors should retain original artwork until the final version of the manuscript has been accepted. No page charges will be levied. Authors may order reprints when corrected proofs are returned. For subscription information, please contact: MIT Press Journals Circulation Department 55 Hayward Street Cambridge, Ma 02142 tel: 617-253-2889 fax: 617-258-6779 ------------------------------ Date: Wed, 7 Aug 1991 20:46-0700 From: Craig W. Reynolds Subject: SIGGRAPH '91 from an ALife perspective ACM's SIGGRAPH held its 18th International Conference on Computer Graphics and Interactive Techniques from July 28th to August 2nd in Las Vegas, Nevada. SIGGRAPH is a huge and diverse event that includes a technical conference, a film festival, an art show, a commercial exhibition, courses, panels, and workshops. I haven't heard an official figure for this year's conference, but SIGGRAPH usually attracts about 30,000 participants. Here is a report on a few aspects of SIGGRAPH '91 that may be of interest to the ALife community. One obvious area of overlap was a paper (Artificial Evolution for Computer Graphics) and video (Primordial Dance) by Karl Sims of Thinking Machines Corporation. Karl is well known in both the computer animation and ALife communities. In this work, he has demonstrated how to use concepts from Genetic Algorithms, and particularly Dawkins' Blind Watchmaker, to do aesthetically directed search over the vast multi-dimensional control space of certain graphic systems. In one instance he used a variation on Dawkins technique to select several species of graftal plants for the forest scenes in "Panspermia". The other example was to use a combination of the Blind Watchmaker and Koza's technique (GA on Lisp code) to evolve programs that created exotic images. There were two papers on reaction-diffusion systems. One by Greg Turk (Generating Textures on Arbitrary Surfaces Using Reaction-Diffusion) and one by Andy Witkin and Mike Kass (Reaction-Diffusion Textures). These were both based on the original 1952 work by Alan Turing (The Chemical Basis of Morphogenesis) which sought to model the source of certain patterns seen on plants and animals. (EG: the patterns on zebras and leopards.) Witkin and Kass also produced an animation showing natural transitions between various reaction-diffusion systems. In Chris Langton's opening remarks at ALife II, he discussed a hierarchy of abstractions useful in categorizing Artificial Life research. At the bottom were simulations of pre-biotic chemical systems, at the top was the simulation of macroscopic behavior of "artificial creatures". There is a strong overlap between this kind of behavioral modeling in ALife and the trend in computer animation toward higher-level specification of action in more abstract terms. Specification of computer animation was originally done in terms of pure geometry (kinematics), then later with physically based models (dynamics), and now is starting to incorporate goal driven behavior simulation. In one of the Courses (Motion Synthesis, Planning and Control) several of the speakers (Michael Cohen and Gary Ridsdale of the University of Utah, and Jean-Claude Latombe of the Stanford Robotics Lab) talked about issues related to ALife-like behavioral control of autonomous agents. Ridsdale also mentioned using genetic algorithm to train a neural net to control a physically based model of a skilled task: serving in the game of handball. Two robotics researchers, Marc Raibert of MIT and Jessica Hodgins of IBM, gave a paper (Animation of Dynamic Legged Locomotion) based on their work with dynamically balanced robots and extending to somewhat more fanciful animated creatures. In their animation (On The Run) a real robot on a treadmill is daydreaming about running untethered out in the countryside. The motion is all created by a dynamic physically based model which is driven by high level behavioral goals. The finished film was fun, but in his talk Raibert showed hilarious out-takes of the "unvarnished truth" where the modeling didn't quite work as intended. Probably the most unique event of SIGGRAPH '91 was Loren Carpenter's Audience Participation piece presented during the Electronic Theater. Each person in the audience was given a wand with a red side and a green side. The colored retro-reflective material was scanned in by video cameras at the back of the auditorium, frame-grabbed and processed, and used to drive a video display that was projected on the big screen, all in real time. In its standby mode the system created a map of the auditorium, with enough resolution to show each seat, indicating whether the person in that seat was holding up the red or green (or neither) side of their wand. It was described as "being a pixel in a huge raster scan display". Various games were played with this setup, from simple voting and "stadium flash card" type displays, to a round of massively parallel Pong. The Pong game was stunning because of how quickly the 5000 "autonomous agents" in the audience learned to cooperate and regulate their aggregate behavior. The way it worked was that each side of the auditorium controlled one of the Pong paddles, red moved the paddles up and green moved it down. In order to move the paddle to the correct position, just the right number of people had to signal with the appropriate color. Too many or too few and the paddle would overshoot or undershoot its mark. The final exercise was massively parallel control of a flight simulator. We crashed. - Craig Reynolds (with help from: Andy Kopra, Pattie Maes, Karl Sims, and Steve Strassmann) ------------------------------ End of ALife Digest *******************