#LyX 1.1 created this file. For more info see http://www.lyx.org/ \lyxformat 2.16 \textclass thesis2 \begin_preamble %\usepackage[nolot,nolof,ps-eh,fm-eh]{brandeis} \usepackage{cite} \usepackage{fancyheadings} \usepackage{setspace} \usepackage{wrapfig} \usepackage{lrfigs} \doublespace %\newcommand{\sechead}[1]{\markright{\MakeUppercase{\thesection.{#1}}}} \renewcommand{\MakeUppercase}[1]{\textbf{\small #1}} \geometry{reset,verbose,twoside,dvips, letterpaper,rmargin=1.4in,tmargin=2in,bmargin=0.5in, lmargin=1.1in} \end_preamble \language default \inputencoding latin1 \fontscheme pslatex \graphics default \paperfontsize 12 \spacing single \papersize letterpaper \paperpackage a4 \use_geometry 1 \use_amsmath 1 \paperorientation portrait \topmargin 2in \bottommargin 0.5in \secnumdepth 2 \tocdepth 2 \paragraph_separation indent \defskip medskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 2 \paperpagestyle default \layout Comment Two-Sided, doublespace version \layout 01 Title Evolution of Complexity in Real-World Domains \layout 02 Author Pablo Funes \layout 03 Dept Computer Science \layout 04 Advisor Jordan B. Pollack \layout 05 May Degree 2001 \layout 06 OtherMembers Martin Cohn, Dept. of Computer Science \layout 06 OtherMembers Timothy J. Hickey, Dept. of Computer Science \layout 06 OtherMembers Dario Floreano, ISR, École Polytechnique Fédérale de Lausanne \layout 07 *Copyright \layout Standard \added_space_top bigskip \added_space_bottom bigskip \pagebreak_top \align right \SpecialChar ~ \layout Standard \align right \emph on in memoriam \layout Standard \align right Everé Santiago Funes (1913-2000) \layout LaTeX \backslash clearblank \layout 09 *Acknowledgments \SpecialChar ~ \layout 09 *Acknowledgments \series bold Elizabeth Sklar \series default collaborated on the work on coevolving behavior with live creatures (chapter \begin_inset LatexCommand \ref{chapter.tron} \end_inset ). \layout 09 *Acknowledgments \series bold Hugues Juillé \series default collaborated with the Tron GP architecture (section \begin_inset LatexCommand \ref{sec.trongp} \end_inset ) and the novelty engine (section \begin_inset LatexCommand \ref{sec.noveltyengine} \end_inset ). \layout 09 *Acknowledgments \added_space_bottom bigskip \series bold Louis Lapat \series default collaborated on EvoCAD (section \begin_inset LatexCommand \ref{sec.evocad} \end_inset ). \layout 09 *Acknowledgments Thanks to Jordan Pollack for the continuing support and for being there when it really matters. \layout 09 *Acknowledgments Thanks to Betsy Sklar, my true American friend. And to Richard Watson for the love and the focus on the real science. Also to all the people who contributed in one way or another, in no particular order: José Castaño, Adriana Villella, Edwin De Jong, Barry Werger, Ofer Melnik, Isabel Ennes, Sevan Ficici, Myrna Fox, Miguel Schneider, Maja Mataric, Martin Cohn, Aroldo Kaplan, Otilia Vainstok. \layout 09 *Acknowledgments And mainly to my family and friends, among them: María Argüello, Santiago Funes, Soledad Funes, Carmen Argüello, María Josefa González, Faustino Jorge, Martín Levenson, Inés Armendariz, Enrique Pujals, Carlos Brody, Ernesto Dal Bo, Martín Galli, Marcelo Oglietti. \layout 10 Abstract \latex latex \backslash begin{doublespace} \layout 10 Abstract Artificial Life research brings together methods from Artificial Intelligence (AI), philosophy and biology, studying the problem of evolution of complexity from what we might call a constructive point of view, trying to replicate adaptive phenomena using computers and robots. \layout 10 Abstract Here we wish to shed new light on the issue by showing how computer-simulated evolutionary learning methods are capable of discovering complex emergent properties in complex domains. Our stance is that in AI the most interesting results come from the interaction between learning algorithms and real domains, leading to discovery of emergent properties, rather than from the algorithms themselves. \layout 10 Abstract The theory of natural selection postulates that generate-test-regenerate dynamics, exemplified by life on earth, when coupled with the kinds of environments found in the natural world, have lead to the appearance of complex forms. But artificial evolution methods, based on this hypothesis, have only begun to be put in contact with real-world environments. \layout 10 Abstract In the present thesis we explore two aspects of real-world environments as they interact with an evolutionary algorithm. In our first experimental domain (chapter \begin_inset LatexCommand \ref{chapter.lego} \end_inset ) we show how structures can be evolved under gravitational and geometrical constraints, employing simulated physics. Structures evolve that exploit features of the interaction between brick-based structures and the physics of gravitational forces. \layout 10 Abstract In a second experimental domain (chapter \begin_inset LatexCommand \ref{chapter.tron} \end_inset ) we study how a virtual world gives rise to co-adaptation between human and agent species. In this case we look at the competitive interaction between two adaptive species. The purely reactive nature of artificial agents in this domain implies that the high level features observed cannot be explicit in the genotype but rather, they emerge from the interaction between genetic information and a changing domain. \layout 10 Abstract Emergent properties, not obvious from the lower level description, amount to what we humans call complexity, but the idea stands on concepts which resist formalization --- such as difficulty or complicatedness. We show how simulated evolution, exploring reality, finds features of this kind which are preserved by selection, leading to complex forms and behaviors. But it does so without creating new levels of abstraction --- thus the question of evolution of modularity remains open. \layout 10 Abstract \latex latex \backslash end{doublespace} \layout Standard \layout LaTeX \backslash begin{doublespace} \layout Chapter Introduction \layout Section Artificial Life and Evolution of Complexity \layout Subsection How does complex organization arise? \layout Comment Finer observations often reveal unexpected detail and interrelations that are difficult to apprehend. Synthesis are often found which collapse a large set of previously unexplained, unorganized observations into a structured framework. \layout Comment Complex organization appears everywhere we look at. \layout Standard The present state of the universe lies somewhere between two extremes of uniformity: perfect order, or zero entropy, which might have happened at the beginning of time ( \emph on big bang \emph default ), and total disorder, infinite entropy, which could be its final destiny ( \emph on heat death \emph default ). Somehow from these homogeneous extremes, diversity arises in the form of galaxies, planets, heavy atoms, life. \layout Standard Analogous scenarios of emergence of organization exist within the scope of different sciences ( \emph on e.g. \emph default formation of ecological niches, of human language, of macromolecules, of the genetic code, etc.). The study of \emph on evolution of complexity \emph default bears on these disciplines and aims at understanding the general features of such phenomena of \begin_inset Quotes eld \end_inset complexification \begin_inset Quotes erd \end_inset : what is complexity, and what kinds of processes lead to it? \begin_inset LatexCommand \cite{keirsey99,heylighen99} \end_inset . \layout Comment Often the interactions at a lower level of organization (e.g. subatomic particles) result in higher levels with \emph on \emph default aggregate rules of their own (e.g. formation of molecules) \layout Standard Biology in particular strives to explain the evolution of complex life forms starting from a random ``primitive soup''. Darwin's theory of natural selection is the fundamental theory that explains the changing characteristics of life in our planet, but contemporary Darwinism is far from complete, having only begun to address questions such as specializa tion, diversification and complexification. \layout Standard Some theories of natural evolution argue that complexity is nothing but statistical error \begin_inset LatexCommand \cite{gould96} \end_inset , whereas others propose that increasing complexity is a necessary consequence of evolution \begin_inset LatexCommand \cite{simon62,heylighen89} \end_inset . The point of view of \emph on universal Darwinism \emph default \begin_inset LatexCommand \cite{dawkins83} \end_inset is that the same characteristics of life on earth that make it susceptible to evolutionary change by natural selection, can also be found on other systems, which themselves undergo evolutionary change. Plotkin \begin_inset LatexCommand \cite{plotkin94} \end_inset proposes the \emph on g-t-r heuristics \begin_float footnote \layout Standard An extension of the \begin_inset Quotes eld \end_inset generate-and-test \begin_inset Quotes erd \end_inset concept \begin_inset LatexCommand \cite{minsky86} \end_inset , with the additional token of iterated generation ( \emph on regeneration \emph default ) based on the previous ones. \end_float as the fundamental characteristic of evolutionary process. Three \emph on phases \emph default are involved: \layout Enumerate \series bold \emph on g \emph default \series default --- Generation of variants \layout Enumerate \series bold \emph on t \series default \emph default --- Test and selection \layout Enumerate \series bold \emph on r \series default \emph default --- Regeneration of variants, based on the previous ones \layout Standard Some examples of systems subject to this kind of g-t-r dynamics are: life on earth, the mammal immune system (random mutation and selection of antigens), brain development (selection of neurons and synapses) and human language (selection of words and grammars) \begin_inset LatexCommand \cite{plotkin94,cziko95} \end_inset . \layout Subsection Measuring Complexity \layout Standard One of the problems with studying the mechanisms and history of complex systems is the lack of a working definition of \emph on complexity \emph default . We have intuitive notions that often lead to contradictions. There have been numerous attempts to define the complexity of a given system or phenomenon, usually by means of a \emph on complexity measure \emph default --- a numerical scale to compare the complexity of different problems, but all of them fall short of expectations. \layout Comment In general we conclude that an abstract definition of complexity should integrate some of the following elements \begin_inset LatexCommand \cite{edmonds99} \end_inset : \layout Standard The notion of Algorithmic Information Content (AIC) is a keystone in the problem. The AIC or \emph on Kolmogorov complexity \emph default of a binary string is defined as the length of the shortest program for a Universal Turing Machine (UTM) whose output is the given string \begin_inset LatexCommand \cite{solomonoff64,kolmogorov65,chaitin66} \end_inset . \layout Standard Intuitively, the simplest strings can be generated with a few instructions, e.g. \begin_inset Quotes eld \end_inset a string of 100 zeros \begin_inset Quotes erd \end_inset ; whereas the highly complex ones require a program slightly longer than the string itself, e.g. \begin_inset Quotes eld \end_inset the string 0010111100101110000010100001000111100110 \begin_inset Quotes erd \end_inset . However, the minimal program depends on the encoding or ``programming language' ' chosen; the difference between two different encodings being bound by a constant. Moreover, AIC is uncomputable. Shannon's entropy \begin_inset LatexCommand \cite{shannon48} \end_inset is a closely related measure (it is an upper bound to AIC \begin_inset LatexCommand \cite{kolmogorov83,vyugin99} \end_inset ). \layout Standard Further research on the matter of complexity measures stems from the notion that the most difficult, the most interesting systems are not necessarily those most complex according to algorithmic complexity and related measures. Just as there is no organization in a universe with infinite entropy, there is little to be understood, or compressed, on maximally complex strings in the Kolmogorov sense. The quest for mathematical definitions of complexity whose maximums lie somewhere between zero and maximal AIC \begin_inset LatexCommand \cite{bennet85,koppel87,grassberger90,gellmann96} \end_inset has yet to produce satisfactory results. Bruce Edmonds' recent PhD thesis on the measurement of complexity \begin_inset LatexCommand \cite{edmonds99} \end_inset concludes that none of the measures that have been proposed so far manages to capture the problem, but points out several important elements: \layout Enumerate Complexity depends on the observer. \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default The complexity of natural phenomena \emph on per se \emph default can not be defined in a useful manner, because natural phenomena have infinite detail. Thus one cannot define the absolute or inherent complexity of \begin_inset Quotes eld \end_inset earth \begin_inset Quotes erd \end_inset for example. Only when observations are made, as produced by an acquisition model, is when the question of complexity becomes relevant: after the observer's model is incorporated. \end_deeper \layout Enumerate \begin_inset Quotes eld \end_inset Emergent \begin_inset Quotes erd \end_inset levels of complexity \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default Often the interactions at a lower level of organization (e.g. subatomic particles) result in higher levels with \emph on \emph default aggregate rules of their own ( \emph on e.g \emph default . formation of molecules). A defining characteristic of complexity is a hierarchy of description levels, where the characteristics of a superior level \emph on emerge \emph default from those below it. The condition of emergence is relative to the observer; emergent properties are those that come from unexpected, aggregate interactions between components of the system. \layout Standard A mathematical system is a good example. The set of axioms determines the whole system, but demonstrable statements receive different names like ``lemma'', ``property'', ``corollary'' or ``theorem'' depending on their relative role within the corpus. ``Theorem'' is reserved for those that are difficult to proof and constitute foundations for new branches of the theory --- they are ``emergent'' properties. \layout Standard A theorem simplifies a group of phenomena and creates a higher lever language. This type of re-definition of languages is typical of the way we do science. As Toulmin puts it, \begin_inset Quotes eld \end_inset The heart of all major discoveries in the physical sciences is the discovery of novel methods of representation, and so of fresh techniques by which inferences can be drawn \begin_inset Quotes erd \end_inset \begin_inset LatexCommand \cite[p. 34]{toulmin53} \end_inset . \end_deeper \layout Enumerate Modularization with Interdependencies \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default Complex systems are partially decomposable, their modules dependent on each other. In this sense, Edmonds concludes that among the most satisfactory measures of complexity is the \emph on \begin_inset LatexCommand \label{page.cyclomatic} \end_inset cyclomatic number \emph default \begin_inset LatexCommand \cite[p. 107]{edmonds99} \end_inset \begin_inset LatexCommand \cite{Temperley81} \end_inset , which is the number of independent closed loops on a minimal graph. \newline The cyclomatic number measures the complexity of an expression, represented as a tree. Expressions with either all identical nodes or with all different nodes are the extremes in an ``entropy'' scale, for they are either trivial or impossible to compress. The more complex ones in the cyclomatic sense are those whose branches are different, yet some subtrees are reused across branches. Such a graph can be reduced (fig. \begin_inset LatexCommand \ref{fig.cyclonum} \end_inset ) so that reused subexpressions appear only once. Doing so reveals a network of entangled cross-references. The count of loops in the reduced graph is the cyclomatic number of the expression. \begin_float fig \end_deeper \layout Standard \align center \begin_inset Figure size 208 140 file cyclonum.eps width 4 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Cyclomatic complexity]{ \latex default \begin_inset LatexCommand \label{fig.cyclonum} \end_inset Cyclomatic complexity of expressions: (a) and (b) have cyclomatic number zero (no irreducible loops), although (a) is completely reducible and (b) completely irreducible. (c) has cyclomatic number one, because of the reuse of node C. \latex latex } \end_float \layout Subsection Artificial Life \layout Standard Artificial Life (ALife) is a growing field that brings together research from several areas. Its subject is defined loosely as the study of ``life as it could be'' \begin_inset LatexCommand \cite{langton89} \end_inset as opposed to ``life as it is'' --- which is the the subject of biology. \layout Standard Work in ALife includes robots that emulate animal behaviors, agents that survive in virtual worlds, artificial evolution, reinforcement learning, autonomous robotics and so on. There is a continuing debate on this field regarding what the definition, methods and goals of Artificial Life are. \layout Standard We propose that one of the fundamental goals of ALife research is to be a \series bold constructive \series default approach to the problem of emergence of complexity. Not satisfied with a global description which describes the process through abstract elements, ALife should consider the question settled only when those elements have been formalized up to the point where they can be laid down in the form of a computer program and shown to work by running it. \layout Comment If in fact the mechanisms of evolution, as universal Darwinism argues, can be described in general terms; and they are found repeatedly in the phenomenolo gical world, leading to the self organization and complexification of systems, then it should be possible to replicate the process in formal systems subject to those rules. \layout Standard Whereas evolutionary biology looks at the fossil record and tries to describe the evolution of life as a result of the g-t-r dynamics, Artificial Life research should aim at writing g-t-r programs that show how in fact artificial agents increase in complexity through the process, thus proving that natural complexity can be generated by this formal process. \layout Subsection Our Stance \layout Standard The goal of this thesis is to show how the dynamics of computer-simulated evolution can lead to the emergence of complex properties, when combined with a suitable environment. We propose that one way to do this is to put evolutionary algorithms in contact with the real world, precisely because it was in this context that natural evolution led to the sophisticated entities conforming the biosphere. \layout Standard Even though the characteristics that define \begin_inset Quotes eld \end_inset suitable environment \begin_inset Quotes erd \end_inset for evolution are unknown, we should be able to verify the theoretical predictions of the evolutionary hypothesis by placing artificial agents in the same kinds of contexts that produce complex natural agents. \layout Standard The difficulty of measuring complexity makes it hard to study an evolutionary system acting on a purely symbolic domain, such as the \emph on Tierra \emph default experiments \begin_inset LatexCommand \cite{ray92,ray94} \end_inset . Evolving real-world agents instead makes it easier to recognize solutions to difficult problems which are familiar to us, and at the same time creates an applied discipline, dealing with real problems. \layout Standard We are deliberately staying away from a discussion about the different flavors of evolutionary algorithms (Genetic Algorithms, Genetic Programming, Multi-obje ctive optimization and so on): all of them capture the fundamental ideas of the g-t-r model. Our aim is to reproduce the dynamics of natural evolution of complexity by \emph on situating \emph default artificial evolution within complex, reality-based domains. We are driven by the intuition that the most interesting results in our field have come not from great sophistication in the algorithm, but rather from the dynamics between g-t-r and interesting environments. Exciting results using coevolution \begin_inset LatexCommand \cite{hillis91,tesauro92,pollack98,sims94} \end_inset for example, suggest that the landscape created by another adaptive unit is richer than a fixed fitness function. \layout Standard Previous work in Artificial Life has already shown promising examples of evolving in real worlds. Here we implement two new approaches: the first one is evolving morphology under simulated physical laws, with simulated elements that are compliant to those found in reality, so as to make the results buildable. The second approach is to employ the concept of virtual reality to bring living animals into contact with simulated agents, in order to evolve situated agents whose domain, albeit simulated, contains natural life forms. \layout Comment Coevolution \layout Comment Coevolution leads to increasing complexity \layout Comment Sorting Networks (Hillis), Backgammon (Tesauro & Pollack), Checkers (Fogel), etc. \layout Comment Virtual Creatures (Sims) \layout Section Interfacing an evolving agent with the Real World \layout Standard Efforts to interface an adaptive agent with reality have created several subfields which study the problem from different perspectives. \layout Subsection Evolutionary Robotics \layout Standard The field of Evolutionary Robotics (ER) starts with a fixed robot platform which has a computer brain connected to sensors and effectors. Different control programs or ``brains'' are tested by downloading them into the robot and evaluating its performance, either in the real robot or a simulated version \begin_inset LatexCommand \cite{floreano94,floreano98,cliff93,husbands:92,jakobi95} \end_inset . \layout Standard Among the difficulties ER faces are, \layout Itemize The robot is bounded by its physicality \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default Evolution is limited by the pace and physicality of the robot. Making copies of a hardware robot is costly because they are not mass-produced. Also, the pace of time cannot be sped up. \layout Comment Simulating the robot is an alternative, but constructing such simulators is costly and creates the so-called \emph on reality gap \emph default : the differences between simulation and reality can lead to solutions which are not correct when transferred to reality. \end_deeper \layout Itemize Design is costly \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default The robot itself is designed by human engineers who engage in a costly process of designing, building, testing and repairing the robot. Commercial robots are available for research on a limited basis. \end_deeper \layout Itemize Robotic Platform is fixed \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default With a robot ``body'' whose morphology can not change, ER is limited to evolving control programs for the fixed platform. This represents a strong limitation, as we argue below, when compared to biological evolution where all behaviors are supported by morphology. \end_deeper \layout Subsection Reconfigurable Hardware \layout Standard Reconfigurable hardware is a new field that evolves the hardware configurations of reconfigurable chips (FPGAs). The idea that an evolutionary algorithm can generate and test hundreds of hardware configurations very quickly is powerful and has produced exciting results \begin_inset LatexCommand \cite{thompson95,thompson98} \end_inset . \layout Standard So far this type of work is limited to chips and thus can not be used to generate life-like creatures. The problems dealt with by evolved FPGA chips are electrical problems such as frequency filters, and occasionally brains to control robotic behaviors. \layout Standard Interest is growing on the design of \emph on self-reconfigurable robots \emph default that can change morphology under program control \begin_inset LatexCommand \cite{fukuda90,yim95,kotay98,kawauchi99,yim00} \end_inset . This is a promising field that holds the exciting perspective of putting together features of both the reconfigurable hardware and evolutionary morphology fields. \layout Subsection Virtual Worlds \layout Standard Virtual worlds are simulated environments with internal rules inspired at least in part by real physics laws. This type of environment has been fruitful for ALife research, for it allows quick implementation of reality-inspired behavior that can be visualized as computer animations \begin_inset LatexCommand \cite{sims94,sims94a,reynolds94,miller94,komosinski99} \end_inset . \layout Standard The surreal beauty of some artificial agents in virtual worlds has had a profound impact in the field, most famously Karl Sims' \emph on virtual creatures \emph default , made of rectangular prisms, evolved life-like behaviors and motion under a careful physical simulation (fig. \begin_inset LatexCommand \ref{fig.sims} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 416 346 file graph/sims3.eps width 3 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[``Virtual Creatures \latex default '' \latex latex by K. Sims]{ \emph on \latex default \begin_inset LatexCommand \label{fig.sims} \end_inset \emph default \begin_inset Quotes eld \end_inset Virtual Creatures \begin_inset Quotes erd \end_inset \emph on \emph default by K. Sims \begin_inset LatexCommand \cite{sims94} \end_inset have evolved morphology and behaviors. They behave according to some physical laws (inertia, action-reaction) but lack other reality constraints: blocks can overlap each other, movements are not generated by motors, etc. \latex latex } \end_float \layout Subsection Simulated Reality \layout Standard Simulating reality puts together Evolutionary Robotics and Virtual Worlds: at the same time one is dealing with the full complexity of physical reality, while not bounded by the laws of conservation of matter or the fixed pace of time. However, writing a full-fledged simulator is an impossibility, for reality has endless detail. \layout Standard A heated discussion separates pro- and anti- simulation ALife research; the detractors of simulations \begin_inset LatexCommand \cite{mataric96,thompson95} \end_inset argue that reality simply cannot be imitated, and that virtual agents adapted to simulated reality will evolve slower than real-time, fail to be transferable , or both. Advocates of simulation claim that by simulating only some aspects of reality one can evolve and transfer \begin_inset LatexCommand \cite{jakobi95,jakobi:97b} \end_inset . \layout Section Summary: Contributions of this Thesis \layout Standard Here we investigate the \emph on reality effect, \emph default of which previous works in the field (Sims' virtual creatures, Thompson's FPGA's) are examples: evolution interacting with reality discovers emergent properties of its domain, builds complexity and creates original solutions, resembling what happens in natural evolution. \layout Standard We investigate two complementary scenarios (a simulation that brings a computer brain out into the real world, and a video game which brings a multitude of natural brains into a virtual world) with two experimental environments: \layout Enumerate Evolution of structures made of toy bricks (chapter \begin_inset LatexCommand \ref{chapter.lego} \end_inset ). These are the main points discussed: \begin_deeper \layout Itemize Evolutionary morphology is a promising new domain for ALife. \layout Itemize Adaptive designs can be evolved that are buildable and behave as predicted. \layout Itemize Principles of architectural and natural design such as cantilevering, counterbal ancing, branching and symmetry are (re)discovered by evolution. \layout Itemize Recombination between partial solutions and change of use ( \emph on exaptation) \emph default are mechanisms that create novelty and lead to the emergence of hierarchical levels of organization. \layout Itemize Originality results from an artificial design method that is not based upon pre-defined rules for task decomposition. \layout Itemize The potential for expanding human expertise is shown with an application --- EvoCAD, a system where human and computer have active, creative roles. \end_deeper \layout Enumerate Evolution of artificial players for a video-game (chapter \begin_inset LatexCommand \ref{chapter.tron} \end_inset ). Main issues are: \begin_deeper \layout Itemize Evolution against live humans can be done with a hybrid evolutionary scheme that combines agent-agent games with human-agent games. \layout Itemize The Internet has the potential of creating niches for mixed agent/human interactions that host phenomena of mutual adaptation. \layout Itemize Basic as well as complex navigation behaviors are developed as survival strategies. \layout Itemize Coevolving in the real world is stronger than coevolving in an agent-only domain, which in turn is stronger than evolving against a fixed training set. \layout Itemize Statistical methods are employed in order to analyze the results. \layout Itemize Agents adapted to complex environments can exhibit elaborate behaviors using a simple reactive architecture. \layout Itemize Human learning arises and can be studied from the interactions with an adaptive agent. \layout Itemize An evolving population acts as one emergent intelligence, in an automated version of a \emph on mixture of experts \emph default architecture. \end_deeper \layout Standard We conclude with a discussion on AI and the role of discovery and of interaction between learning algorithms, people and physical reality in the light of these results (chapter \begin_inset LatexCommand \ref{chapter.conclusions} \end_inset ). \layout Standard Altogether, we are elaborating on a new perspective of Artificial Life, conceived as one of the pieces on the question of evolution of complexity. The evolutionary paradigm explains complexification up to a certain point at least, but also shows that we are still far from a complete understanding of this phenomenon. \layout Chapter \begin_inset LatexCommand \label{chapter.lego} \end_inset Evolution of Adaptive Morphology \layout Section Introduction and Related Work \layout Standard This chapter describes our work in evolution of buildable structural designs. Designs evolve by means of interaction with reality, mediated by a simulation that knows about the properties of their modular components: commercial off-the-shelf building blocks. \layout Standard This is the first example of reality-constrained \emph on evolutionary morphology \emph default : entities that evolve under space and gravitational constraints imposed by the physical world, but are free to organize in any way. We do not consider movement; our aim is to show how complete structural organization, a fundamental concept for ALife, may begin to be addressed. \layout Standard The resulting artifacts, induced by various manually specified fitness functions , are built and shown to behave correctly in the real world. They are not based in building heuristics or rules such as a human would use. We show how these artifacts are founded upon emergent rules discovered and exploited by the dynamic interaction of recombination and selection under reality constraints. \layout Standard Weak search methods such as simulated evolution have great potential for exploring spaces of designs and artifacts beyond the limits of what people usually do. \color red \color default We present a prototype CAD tool that incorporates evolution as a creative component that creates new designs in collaboration with a human user. \layout Standard Parts of this research have been reported on the following publications: \begin_inset LatexCommand \cite{funespollack97,funespollack98,funespollack99,ices2000,legosim,pollack99nasa,funesaid00} \end_inset . \layout Subsection Adaptive Morphology \layout Standard Morphology is a fundamental means of adaptation in life forms. Shape determines function and behavior, from the molecular level, where the shape of a protein determines its enzymatic activity, to the organism level, where plants and animals adapt to specific niches by morphological changes, up to the collective level where organisms modify the environment to adapt it to their own needs. \layout Standard In order to evolve adaptive physical structures we imitate nature by introducing a genetic coding that allows for both local modifications, with global effects (i.e. enlarging one component has only a local effect but may also result in shifting an entire subpart of the structure) and recombination, which spreads useful subparts of different sizes. \layout Standard Even though the plasticity of life forms is far superior to a limited computer model such as ours, we are still able to see how the dynamic ``evolutionary game'' among a genetically-regulated family of organisms whose fitness comes from interaction with a complex environment, results in evolution of complexity and diversity leading to higher levels of organization. \layout Subsection ALife and Morphology \layout Comment \color red There are three basic kinds of experimental models utilized in ALife research: \layout Comment \color red Abstract Models \begin_inset LatexCommand \cite{fontana92,ray92,ray94,watson99a} \end_inset are used to model abstract questions such as evolutionary dynamics and optimization. The idea of morphology, if present, is not linked to reality. \layout Comment \color red Robotic Models ( \begin_inset LatexCommand \cite{floreano94,floreano98a,lund95,cliff93} \end_inset ) permit the study of complexities arising from real world. Here morphology is fixed, a robotic contraption pre-designed by a human engineer. \layout Comment \color red Virtual Worlds ( \begin_inset LatexCommand \cite{sims94,sims94a,reynolds94,miller94,komosinski99} \end_inset ) utilize 2 or 3-dimensional coordinates and notions of physics to bypass the problems of robotic models while retaining interesting aspects of the physical world. Here morphology is often adaptive, but as the simulation is reality inspired, but not reality based, so are its results. \layout Standard A deep chasm separates Artificial Life work that uses robotics models \begin_inset LatexCommand \cite{floreano94,floreano98a,lund95,cliff93} \end_inset from the one in virtual worlds \begin_inset LatexCommand \cite{sims94,sims94a,reynolds94,miller94,komosinski99} \end_inset . Robots today lack plasticity in their design; they need to be built by hand, molded using expensive methods. The number of generations and the number of configurations tested is several orders of magnitude smaller than those that can be reached with simulated environments. Evolutionary Robotics does not address morphology, although the idea was around from the beginning \begin_inset LatexCommand \cite{cliff92} \end_inset . Experiments generally focus on evolving behaviors within a fixed morphology --- a robotic ``platform''. Occasionally we see shape variables, but limited to a few parameters, such as wheel diameter or sensor orientation \begin_inset LatexCommand \cite{cliff97,lee96,lund97b} \end_inset . \layout Standard Evolution in Virtual Worlds on the other hand, is often morphological \begin_inset LatexCommand \cite{sims94,komosinski99} \end_inset . Virtual worlds are constrained neither by the fixed \begin_inset Quotes eld \end_inset speed \begin_inset Quotes erd \end_inset of real time, nor by physical laws such as conservation of mass. The drawback is in the level of detail and the complexity of reality: simulatin g \emph on everything \emph default would require an infinite amount of computation. \layout Standard The Evolution of Buildable Structures project aims at bridging the reality gap between virtual worlds and robotics by evolving agents in simulation under adequate constraints, and then transferring the results, constructing the ``reality equivalent'' of the agent. \layout Standard Lego \begin_float footnote \layout Standard Lego is a registered trademark of the Lego group. \end_float bricks are popular construction blocks, commonly used for educational, recreation and research purposes. We chose these commercially available bricks because they have proven to be adequate for so many uses, suggesting that they have an appropriate combination of size, tightness, resistance, modularity and price. These characteristics led us to expect to be able to evolve interesting, complex structures that can be built, used and recycled. \layout Subsection \emph on Nouvelle \emph default AI \layout Standard One important contribution of the \emph on nouvelle AI \emph default revolution in the eighties was to deconstruct the traditional notion of reasoning in isolation. Brooks \begin_inset LatexCommand \cite{brooks86,brooks91} \end_inset fought against the division of cognition in layers (perception -- recognition -- planning -- execution -- actuation) and instead proposed the notions of reactivity and situatedness: the phenomenon we call intelligence stems from a tight coupling between sensing and actuation. \layout Standard In the same spirit of doing without layered approaches, we reject the notion of parameterizing the functional parts of a robotic artifact. The different parts of a body --- torso, extremities, head --- are not interesting if we establish them manually. By giving the evolutionary code full access to the substrate, the search procedure does without conventional human biases, discovering its own ways to decompose the problem --- which are not necessarily those that human engineers would come up with. \layout Standard Human cognition, as pointed out by Harvey \begin_inset LatexCommand \cite{harvey97} \end_inset lacks the ability to design complex systems as a whole. Instead, we usually proceed by complexity reduction (the \begin_inset Quotes eld \end_inset divide and conquer \begin_inset Quotes erd \end_inset method). This is why the classic AI work took the layered approach that Brooks rejected so strongly. Perhaps the greatest strength of ALife methods such as artificial evolution is their ability to develop the organization and subparts together as a whole. \layout Subsection Artificial Design \layout Standard The science of design usually conceives of AI as a set of tools for structuring the process, or planning, or optimizing \begin_inset LatexCommand \cite{chapman93,park00,bezerra00} \end_inset . Rarely does the computer explore a space of designs, and in doing so, it is generally following a set of precise rules, so the machine is doing little else than repeating a series of mechanical steps, faster than a human could. Creativity is usually considered to lay outside the realm of what computers can do. \layout Standard Evolutionary Design (ED), the creation of designs by computers using evolutionar y methods \begin_inset LatexCommand \cite{bentley99} \end_inset is a new research area with an enormous potential. Examples of ED work are evolution of abstract shapes \begin_inset LatexCommand \cite{bentley96} \end_inset or optimization of one part or component \begin_inset LatexCommand \cite{chapman93,shoenauer96} \end_inset . The present work is different, for we are proposing to let the evolutionary process take care of the entire design process by means of recombination of available components and interaction with a physics simulation. \layout Standard Inasmuch as Artificial Intelligence is an elusive concept--- it seems that every new challenge that computers solve, becomes non-intelligent by definition \begin_float footnote \layout Standard AI is ``the study of how to make computers do things which, at the moment, people do better'' \begin_inset LatexCommand \cite[p. 3]{rich91} \end_inset \end_float , so is ``artificial creativity''. We claim that the present work is in fact a form of artificial creativity, albeit restricted, whose designs are unexpected, surprising, amusing --- and they work. \layout Comment \color red The observation can be made, however, that evolution of a creature's controlling brain is just one part of the problem of artificial evolution of life a creature that adapts to an environment needs an adequate body to inhabit. The body and brains of a robot should evolve together to constitute an adaptive organism. This is the case in natural life forms where new actions require new capabiliti es in the body along with the corresponding new brain functions to execute them. \layout Section \begin_inset LatexCommand \label{section.simulation} \end_inset Simulating Bricks Structures \layout Standard This section discusses our approach to the simulation of structures made of weakly joined bricks. \layout Subsection Background \layout Standard Two kinds of simulation, Finite Elements from engineering and Qualitative Physics from computer science, have inspired our simulator of Lego brick structures. \layout Standard Finite Element Modeling (FEM) is a structural mechanics technique for discretizi ng an object in order to analyze its behavior in the presence of stresses and holds \begin_inset LatexCommand \cite{zienk97} \end_inset . The principle is to construct a network or \begin_inset Quotes eld \end_inset mesh \begin_inset Quotes erd \end_inset to model the piece as a discrete network and have the nodes communicate with their neighbors in order to cancel out all forces. \layout Standard Qualitative Physics (QP) is a subfield of AI which deals with mechanical and physical knowledge representation. It starts with a logical representation of a mechanism, such as a heat pump \begin_inset LatexCommand \cite{forbus84} \end_inset or a string \begin_inset LatexCommand \cite{gardin89} \end_inset , and produces simulations, or envisionments, of the future behavior of the mechanism. \layout Standard QP simulations have not been used for evolutionary design, but they express an idea of great potential for reality-grounded evolution: not all aspects of the world need to be simulated to their fullest detail. Sometimes one can create an approximate model using \emph on ad hoc \emph default qualitative rules instead of the more complex equations of Newtonian physics. \layout Subsection \begin_inset LatexCommand \label{section.ntp} \end_inset Lego Bricks \layout Standard The resistance of the plastic material (ABS - acrylonitrile butadiene styrene) of Lego bricks far surpasses the force necessary to either join two of them together or break their unions. This makes it possible to conceive a model that ignores the resistance of the material and evaluates the stress forces over a group of bricks only at their union areas. If a Lego structure fails, it will generally do so at the joints, but the actual bricks will not be damaged. \layout Standard This characteristic of bricks structures makes their discretization for modeling an obvious step. Instead of imposing an artificial mesh for simulation purposes only (as FEM does), these structures are already made of relatively large discrete units. A first simplification is thus to ignore the physical characteristics of the bricks and study only those of their unions. \layout Standard Our second simplification is to ignore bending effects. In standard structural analysis, the effects of stress are observed as deformation of the original shape of a body. Here strain deformations are ignored altogether. \layout Subsection Joints in two dimensions \layout Standard We began considering two-dimensional structures, assuming that all the bricks are of width 1, assembled in a plane. A fulcrum effect, which is the angular torque exerted over two joined bricks, constitutes the principal cause for the breakage of a stressed structure of Lego bricks. We designed our model around this idea, describing the system of static forces inside a complex structure of Lego bricks as a network of rotational joints located at each union between brick pairs and subject to loads (fig. \begin_inset LatexCommand \ref{fig.network1} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 357 222 file lego/graph/fulcrum3.eps width 3 60.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Fulcrum effect]{ \latex default \begin_inset LatexCommand \label{fig.fulcrum} \end_inset \emph on Fulcrum effect \emph default : a \begin_inset Formula \( 2\times 1 \) \end_inset union resists more than twice the load of a \begin_inset Formula \( 1\times 1 \) \end_inset because the second knob is farther away from the axis of rotation. \latex latex } \end_float \begin_float tab \layout Standard \added_space_top 0.3cm \added_space_bottom 0.3cm \align center \LyXTable multicol5 8 2 0 0 -1 -1 -1 -1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Joint size ( \begin_inset Formula \( \omega \) \end_inset ) \newline Approximate torque capacity ( \begin_inset Formula \( \kappa _{\omega } \) \end_inset ) \newline knobs \newline N-m \begin_inset Formula \( \times 10^{-3} \) \end_inset \newline 1 \newline 12.7 \newline 2 \newline 61.5 \newline 3 \newline 109.8 \newline 4 \newline 192.7 \newline 5 \newline 345.0 \newline 6 \newline 424.0 \layout Standard \latex latex \backslash caption[Estimated torque capacities of the basic types of joints]{ \latex default \begin_inset LatexCommand \label{table.jointsizes} \end_inset Estimated minimal torque capacities of the basic types of joints. Note: these values correct the ones on \begin_inset LatexCommand \cite[table 1]{funespollack98} \end_inset . \latex latex } \end_float \layout Standard Bricks joined by just one knob resist only a small amount of torque; bigger unions are stronger. The resistance of the joint depends on the number of knobs involved. We measured the minimum amount of stress that different linear ( \begin_inset Formula \( 1\times 1 \) \end_inset , \begin_inset Formula \( 2\times 1 \) \end_inset , \begin_inset Formula \( 3\times 1 \) \end_inset , etc.) unions of brick pairs support (table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset ). \layout Standard From a structure formed by a combination of bricks, our model builds a network with joints of different capacities, according to the table. Each idealized joint is placed at the center of the area of contact between every pair of bricks. A margin of safety, set to 20% in our experiments, is discounted from the resistances of all joints in the structure, to ensure robustness in the model's predictions. \layout Standard All forces acting in the structure have to be in equilibrium for it to be static. Each brick generates, by its weight, a gravitational force acting downwards. There may be other forces generated by external loads. \layout Standard Each force has a site of application in one brick --- each brick's weight is a force applied to itself; external forces also \begin_inset Quotes eld \end_inset enter \begin_inset Quotes erd \end_inset the structure through one brick --- and has to be canceled by one or more reaction forces for that brick to be stable. Reaction forces can come from any of the joints that connect it to neighbor bricks. But the brick exerting a reaction force becomes unstable and has to be stabilized in turn by a reaction from a third brick. The load seems to \begin_inset Quotes eld \end_inset flow \begin_inset Quotes erd \end_inset from one brick to the other. Thus by the action-reaction principle, a load is propagated through the network until finally absorbed by a fixed body, the \begin_inset Quotes eld \end_inset ground \begin_inset Quotes erd \end_inset . \begin_float fig \layout Standard \align center \begin_inset Figure size 565 452 file lego/graph/bridsce2.eps width 3 95.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Model of a 2D Lego structure]{ \latex default \begin_inset LatexCommand \label{fig.network1} \end_inset Model of a 2D Lego structure showing the brick outlines (rectangles), centers of mass (circles), joints (diagonal lines, with axis located at the star), and ``ground'' where the structure is attached (shaded area). The thickness of the joint's lines is proportional to the strength of the joint. A distribution of forces was calculated: highly stressed joints are shown in light color, whereas those more relaxed are darker. Note that the \emph on x \emph default and \emph on y \emph default axis are in different scales. \latex latex } \end_float \layout Standard The principle of propagation of forces described, combined with the limitations imposed to each individual joint, generates a set of equations (section \begin_inset LatexCommand \ref{sec.ntpequations} \end_inset ). A solution means that there is a way to distribute all the forces along the structure. This is the principle of our simulator: \emph on as long as there is a way to distribute the weights among the network of bricks such that no joint is stressed beyond its maximum capacity, the structure will not break. \layout Subsection From 2- to 3-dimensional joints \layout Standard In two dimensions, all brick unions can be described with one integer quantity --- the number of knobs that join two bricks. Table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset gives all the information needed to describe 2D brick joints. In the three dimensional case, brick unions are \emph on n \emph default -by- \emph on m \emph default rectangles. Two \begin_inset Formula \( 2\times 4 \) \end_inset bricks for example can be stuck together in 8 different types of joints: \begin_inset Formula \( 1\times 1 \) \end_inset , \begin_inset Formula \( 1\times 2 \) \end_inset , \begin_inset Formula \( 1\times 3 \) \end_inset , \begin_inset Formula \( 1\times 4 \) \end_inset , \begin_inset Formula \( 2\times 1 \) \end_inset , \begin_inset Formula \( 2\times 3 \) \end_inset , \begin_inset Formula \( 2\times 4 \) \end_inset . \layout Standard We know already, from the 2D case, how \begin_inset Formula \( n\times 1 \) \end_inset unions respond to forces acting along the \emph on x \emph default axis alone. A \begin_inset Formula \( 2\times 1 \) \end_inset union supports more than double the torque admitted by a \begin_inset Formula \( 1\times 1 \) \end_inset , the reason being that the brick itself acts as a fulcrum (fig. \begin_inset LatexCommand \ref{fig.fulcrum} \end_inset ). The distance from the border to the first knob is shorter than the distance to the second knob, resulting in a lower multiplication of the force for the second knob. This fulcrum effect does not happen when the force is orthogonal to the line of knobs. A \begin_inset Formula \( 1\times 2 \) \end_inset union can be considered as two \begin_inset Formula \( 1\times 1 \) \end_inset unions, or as one joint with double the strength of a \begin_inset Formula \( 1\times 1 \) \end_inset (fig. \begin_inset LatexCommand \ref{fig.3djoint} \end_inset ). \layout Standard In other words, when torque is applied along a sequence of stuck knobs, the fulcrum effect will expand the resistance of the joint beyond linearity (as in table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset ). But when the torque arm is perpendicular instead, knob actions are independent and expansion is just linear. \begin_float fig \layout Standard \align center \begin_inset Figure size 416 235 file lego/graph/brickab2.eps width 3 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Two-dimensional brick joint]{ \latex default \begin_inset LatexCommand \label{fig.3djoint} \end_inset Two-dimensional brick joint. Bricks A and B overlap in a \begin_inset Formula \( 4\times 2 \) \end_inset joint J. Along \emph on x \emph default the joint is a double \begin_inset Formula \( 4\times 1 \) \end_inset joint. Along the \emph on y \emph default axis it is a quadruple \begin_inset Formula \( 2\times 1 \) \end_inset -joint. \latex latex } \end_float \layout Standard We thus state the following \emph on dimensional independence assumption \emph default : Two bricks united by \begin_inset Formula \( n\times m \) \end_inset \emph on \emph default overlapping knobs will form a joint \emph on \emph default with a capacity \emph on \begin_inset Formula \( K_{x} \) \end_inset \emph default along the \emph on \begin_inset Formula \( x \) \end_inset \emph default axis equal to \emph on m \emph default times the capacity of one \emph on n \emph default -joint and \emph on \begin_inset Formula \( K_{y} \) \end_inset \emph default along the \emph on y \emph default axis equal to \emph on n \emph default times the capacity of an \emph on m \emph default -joint. \layout Standard To test the resistance of a composite joint to any spatial force \emph on f \emph default we separate it into its two components, \emph on \begin_inset Formula \( f_{x} \) \end_inset \emph default on the \emph on xz \emph default plane and \emph on \begin_inset Formula \( f_{y} \) \end_inset \emph default on the \emph on yz \emph default plane. These components induce two torques \emph on \begin_inset Formula \( \tau _{x} \) \end_inset , \emph default \begin_inset Formula \( \tau _{y} \) \end_inset . To break the joint either \begin_inset Formula \( \tau _{x} \) \end_inset \emph on \emph default must be larger than \emph on \begin_inset Formula \( K_{x} \) \end_inset \emph default or \begin_inset Formula \( \tau _{y} \) \end_inset larger than \emph on \begin_inset Formula \( K_{y} \) \end_inset . \layout Standard If the dimensional independence hypothesis was not true, a force exerted along one axis could weaken or strengthen the resistance in the orthogonal dimension, but our measurements suggest that the presence of stress along one axis does not modify the resistance along the other. It is probably the case that the rectangular shape of the joint actually makes it stronger for diagonal forces, implying that dimensional independence is a conservative assumption. In any case, separating the components of the force has been a sufficient approximation for the scope of our experiments. \layout Subsection \begin_inset LatexCommand \label{sec.networksoftorquepropagation} \end_inset Networks of Torque Propagation \layout Standard \begin_float fig \layout Standard \align center \begin_inset Figure size 565 539 file lego/graph/fig1b.eps width 3 95.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[3D Lego structure]{ \emph on \latex default \begin_inset LatexCommand \label{fig.tableskeleton} \end_inset \emph default 3D Lego structure generated by our evolutionary process. The underlying physical model is shown. \latex latex } \end_float Our model for a 2D structure of bricks generates a network, called a Network of Torque Propagation (NTP) consisting of \emph on nodes \emph default , \emph on joints \emph default and \emph on loads. \layout Itemize Each \emph on node \emph default represents a brick and its located at the brick's center of mass (circles in our figures). \layout Itemize An additional node represents the ground. \layout Itemize Each pair of locked bricks gives raise to a \emph on joint \emph default . The joint has an origin node, a destination node, an axis of rotation (located at the center of the area of contact between the bricks) and a maximum torque capacity (depending on the number of knobs involved). Joints are represented by lines in our figures, their axis of rotation by stars. \layout Itemize \emph on Loads \emph default represent the forces acting on the network. Each has magnitude, direction, point of application, and entry node. For each brick, a force corresponding to its weight originates at the center of mass, is applied at the corresponding node, and points downwards. External forces may have any direction and their point of application is not necessarily the center of the brick. \layout Standard Each force, either the weight of one of the bricks or an external load, has to be absorbed by the joints in the structure and transmitted to the ground. The magnitude of the torque exerted by each joint \emph on j \emph default must lie in the interval [- \emph on K \begin_inset Formula \( _{j} \) \end_inset , K \begin_inset Formula \( _{j} \) \end_inset \emph default ], where \emph on K \begin_inset Formula \( _{j} \) \end_inset \emph default represents its maximum capacity as deduced from table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset . \layout Standard By separating each 3D joint into two orthogonal and independent 2D joints, which receive the \emph on x \emph default and \emph on y \emph default components of each force, we can project an entire 3D network model of a brick structure into two orthogonal planes, \emph on xz \emph default and \emph on yz \emph default , generating two 2D NTP's that can be solved separately (figs. \begin_inset LatexCommand \ref{fig.tableskeleton} \end_inset and \begin_inset LatexCommand \ref{fig.tableprojections} \end_inset ). Thus the problem of solving a 3D network is reduced to that of solving 2D networks. \begin_float fig \layout Standard \align center \latex latex \begin_inset Figure size 279 288 file lego/graph/fig1c.eps width 3 47.00 flags 11 \end_inset \backslash hfill \begin_inset Figure size 279 288 file lego/graph/fig1d.eps width 3 47.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[2D projections of a 3D structure]{ \latex default \begin_inset LatexCommand \label{fig.tableprojections} \end_inset Projecting the 3D structure of fig. \begin_inset LatexCommand \ref{fig.tableskeleton} \end_inset to the \emph on xz \emph default and \emph on yz \emph default planes, two 2D networks are obtained that can be solved independently. \latex latex } \end_float \layout Subsection \begin_inset LatexCommand \label{sec.ntpequations} \end_inset NTP Equations \layout Standard From our initial idea that forces propagate along a structure producing stresses in the form of torques, we have built an NTP, a network that has all the information needed to compute the possible paths along which the loads could \begin_inset Quotes eld \end_inset flow \begin_inset Quotes erd \end_inset and the torques they would generate along the way. \layout Standard For each force \emph on F \emph default we consider the network of all the joints in the structure as a flow network that will transmit it to the ground. Each joint \emph on j \emph default can support a certain fraction \begin_inset Formula \( \alpha \) \end_inset of such a force, given by the formula \layout Standard \begin_inset Formula \begin{equation} \label{eq.flow} \alpha _{j,F}=\max \left\{ 1,\left| \frac{K_{j}}{\delta (j,F)||F||}\right| \right\} \end{equation} \end_inset \layout Standard where \emph on \begin_inset Formula \( K_{j} \) \end_inset \emph default is the maximum capacity of the joint, \begin_inset Formula \( \delta (j,F) \) \end_inset \emph on \emph default the distance between the line generated by the force vector and the joint, and \begin_inset Formula \( ||F|| \) \end_inset \emph on \emph default the magnitude of the force. Thus if the torque generated is less than the joint maximum \begin_inset Formula \( K \) \end_inset , then \begin_inset Formula \( \alpha =1 \) \end_inset (the joint fully supports \begin_inset Formula \( F \) \end_inset ); otherwise \begin_inset Formula \( \alpha \) \end_inset is \emph on K \emph default divided by the torque. The arm of the torque \begin_inset Formula \( \delta (j,F) \) \end_inset can have a positive or negative sign depending on whether it acts clockwise or counterclockwise. \layout Standard If one given force \emph on \begin_inset Formula \( F \) \end_inset \emph default is fixed and each joint on the graph is labeled with the corresponding \begin_inset Formula \( \alpha _{j,F} \) \end_inset according to eq. \begin_inset LatexCommand \ref{eq.flow} \end_inset , a network flow problem (NFP) \begin_inset LatexCommand \cite{cormen} \end_inset is obtained where the \emph on source \emph default is the node to which the force is applied and the \emph on sink \emph default is the ground. Each joint links two nodes in the network and has a capacity equal to \begin_inset Formula \( \alpha \) \end_inset \begin_inset Formula \( _{j,F} \) \end_inset . A net flow \begin_inset Formula \( |\phi _{F}|=1 \) \end_inset represents a valid distribution of the force \emph on F \emph default throughout the structure: \begin_inset Formula \( F \) \end_inset can be supported by the structure if there is a solution to the NFP with a net flow of 1. \layout Standard With more than one force, a solution for the entire network can be described as a set \begin_inset Formula \( \{\phi _{F}\} \) \end_inset of flows, one for each force, all valued one. But as multiple forces acting on one joint are added, the capacity constraint needs to be enforced globally instead of locally, that is, the combined torques must be equal to or less than the capacity of the joint: \begin_inset Formula \begin{equation} \label{eq.multiflow} \left| \sum _{F}\phi _{F}(j)\delta (j,F)\left\Vert F\right\Vert \right| \leq K_{j} \end{equation} \end_inset \layout Standard This problem is not solvable by standard NFP algorithms, due to the multiplicity of the flow (one flow per force) and the magnification of magnitudes due to the torque arm \begin_inset Formula \( \delta \) \end_inset (so the capacity of a joint is different for each load). Equation \begin_inset LatexCommand \ref{eq.multiflow} \end_inset is equivalent to a \emph on multicommodity network flow problem \emph default \begin_inset LatexCommand \cite[ch. 17]{ahuja93} \end_inset . \layout Subsection \begin_inset LatexCommand \label{sec.solvers} \end_inset NTP Algorithms \layout Standard Whereas the standard maximum network flow problem (single commodity) has well known polynomial-time solutions \begin_inset LatexCommand \cite{cormen} \end_inset , multicommodity problems are much harder, and fall into the general category of linear programming. There is a fair amount of research on the multicommodity problem \begin_inset LatexCommand \cite{grigoriadis95,ali80,iusem95,leighton95} \end_inset but the algorithms, based on Linear Programming, are exponential on the worst case. \layout Subsubsection Greedy Solver \layout Standard Our initial approach for solving NTP problems was a greedy algorithm: Forces are analyzed one at a time. The push-relabel algorithm \emph on PRF \emph default by Cherkassky and Goldberg \begin_inset LatexCommand \cite{cherkassky97} \end_inset is used to find a valid flow. Once a flow has been found it is fixed, and a remaining capacity for each joint (eq. \begin_inset LatexCommand \ref{eq.greedy} \end_inset ) is computed that will produce a reduced network that must support the next force. A maximum flow is found for the second force with respect to the reduced network and so on for all forces. \begin_inset Formula \begin{equation} \label{eq.greedy} K_{j}'=K_{j}-\phi _{F}(j)\delta (j,F)||F|| \end{equation} \end_inset \layout Standard This simple algorithm misses solutions, yet is quick, and thus we preferred it for time reasons to the more sophisticated solvers. With the greedy model, some solutions might be missed; but the ones found are good --- so the structures evolve within the space of \emph on provable \emph default solutions, that is, those for which a greedy solution is found. This algorithm was particularly useful in the crane cases (sections \begin_inset LatexCommand \ref{sec.firstexperiments} \end_inset , \begin_inset LatexCommand \ref{sec.triangle} \end_inset ), where there is one special force, several orders of magnitude larger than the others. All experiments detailed here use this approach, except for the tree experiment (section \begin_inset LatexCommand \ref{sec.tree} \end_inset ) and EvoCAD ( \begin_inset LatexCommand \ref{sec.evocad} \end_inset ), which employ the \begin_inset Quotes eld \end_inset embedded solver \begin_inset Quotes erd \end_inset explained below. \layout Subsubsection Multicommodity Solver \layout Standard A second version of our Lego structure simulator incorporated a state-of-the-art multicommodity algorithm, by Castro and Nabona \begin_inset LatexCommand \cite{castroNabona96} \end_inset . A special case of Linear Programming, these solvers have exponential order in the worst case, although with some luck they are faster on practical cases. We found this algorithm to be slower than the greedy version by a factor of 10 or more. The gain in accuracy did not compensate the loss in speed. \layout Subsubsection Embedded Solver \layout Standard A third approach to the NTP problem was to incorporate the network flow into the representation of the structure. Thus structures and solutions evolve together: instead of using a network flow algorithm to find a flow, the flow is uniquely encoded in the genetic code of the structure, and is allowed to evolve along with it. \layout Standard With a few modifications we extended the genotype to represent not only the position of the bricks, but also a unique flow for each force into a sink. With this, a structure can evolve along with the flows that represent a solution to the NTP problem. \layout Standard As seen in the previous sections, a set \begin_inset Formula \( \{\phi _{F}\} \) \end_inset of flows, one for each force, determines the total torque demanded from each joint in the structure (eq. \begin_inset LatexCommand \ref{eq.multiflow} \end_inset ). With the embedded solver, the evolutionary algorithm searches both the space of structure layouts and the space of flows at the same time. If the torques generated by the distribution of forces specified by the genotype exceed the joints' capacities, the structure is considered invalid. \layout Standard Our representation for bricks structures (see section \begin_inset LatexCommand \ref{sec.evolvinglego} \end_inset ) is a tree graph whose nodes represent bricks. All descendants of a node are bricks which are physically in contact with the parent. In a structure there may be multiple paths from a brick to the ground, but genetically, there is a unique branch from each brick to the root. The root node is always a brick that rests on the ground, so all paths that follow the tree structure terminate on the ground. The following extensions to the genotype allowed us to evolve a structure along with the solution to the NTP problem: \layout Enumerate Load flows only from descendant to ancestor \begin_deeper \layout Standard Loads flow only down from descendants to parents. This defines the positive or negative sign of \begin_inset Formula \( \phi _{F}(j) \) \end_inset for each joint and force. For the previous algorithms we had an undirected graph. Now the graph is strictly directed: for each brick pair \begin_inset Formula \( a,b \) \end_inset either joint \begin_inset Formula \( j(a,b) \) \end_inset exists or \begin_inset Formula \( j(b,a) \) \end_inset , but not both. \end_deeper \layout Enumerate Multiple trees rooted at grounds \begin_deeper \layout Standard \latex latex \backslash nopagebreak \latex default Instead of only one root, there can be multiple roots now situated at the grounds of the problem. Each load now has at least one possible path to flow to a sink, although it may or may not violate the joint's constraints. \end_deeper \layout Enumerate \begin_inset Quotes eld \end_inset Adoptive \begin_inset Quotes erd \end_inset parents may also bear weight \begin_deeper \layout Standard When two bricks happen to be physically linked, but neither of them is a descendant of the other, the first one \begin_float footnote \end_deeper \layout Standard The tree is traversed in depth-first order. The descendants of a node are represented as a list, which determines the order of expansion, so there is a well-defined order in which bricks are laid down. \end_float will become an \begin_inset Quotes eld \end_inset adoptive \begin_inset Quotes erd \end_inset parent, so the joint created flows from the lower-order brick to the higher-ord er. \layout Enumerate Flow determined by joint size and weight vector. \begin_deeper \layout Standard A weight parameter \begin_inset Formula \( w_{j} \) \end_inset was added to the representation of the joints. When a joint is created, \begin_inset Formula \( w_{j} \) \end_inset is initialized to 1, but then it may change by random mutation or by recombinat ion. The flow \begin_inset Formula \( \phi _{F}(j) \) \end_inset for each force and joint is determined by the joint size (number of knobs) and the flow weight, as follows: \layout Standard Let \begin_inset Formula \( x \) \end_inset be a brick in the path of force \begin_inset Formula \( F \) \end_inset . The flow of \begin_inset Formula \( F \) \end_inset into \begin_inset Formula \( x \) \end_inset must equal its flow out of \begin_inset Formula \( x, \) \end_inset thus \begin_inset Formula \begin{equation} \label{eq.fx} F_{x}=\sum _{a}\phi _{F}(a,x)=\sum _{b}\phi _{F}(x,b) \end{equation} \end_inset \layout Standard The outgoing flow is uniquely determined by \begin_inset Formula \( F_{x} \) \end_inset and the proportion \begin_inset Formula \( \lambda (x,b) \) \end_inset that goes to each parent \begin_inset Formula \( b \) \end_inset of \begin_inset Formula \( x \) \end_inset (either \begin_inset Quotes eld \end_inset adoptive \begin_inset Quotes erd \end_inset or \begin_inset Quotes eld \end_inset original \begin_inset Quotes erd \end_inset ). \layout Standard For each brick \begin_inset Formula \( b \) \end_inset that is a parent of \begin_inset Formula \( x \) \end_inset , let \begin_inset Formula \( \omega (x,b) \) \end_inset be the size (in knobs) of the joint \begin_inset Formula \( j(x,b) \) \end_inset and \begin_inset Formula \( w(x,b) \) \end_inset the encoded weight of the joint. Let \begin_inset Formula \( \Omega =\sum _{j(x,b)}\omega (x,b) \) \end_inset and \begin_inset Formula \( W=\sum _{j(x,b)}w(x,b) \) \end_inset . For each joint now we define the proportion of total flow that follows each outgoing path as: \begin_inset Formula \begin{equation} \label{eq.lambdaxb} \lambda (x,b)=\frac{\omega (x,b)w(x,b)}{\Omega W} \end{equation} \end_inset which defines the behavior of all flows going through x: \begin_inset Formula \begin{equation} \label{eq.phifxb} \phi _{F}(x,b)=F_{x}\lambda (x,b) \end{equation} \end_inset \layout Standard With this configuration, the flow of a force through brick \begin_inset Formula \( x \) \end_inset is by default proportional to the size of the joint --- stronger joints are asked to support proportionally more weight. But the genotype encodes weights \begin_inset Formula \( w(x,b) \) \end_inset for each joint so the flow of the force can be redistributed. \end_deeper \layout Enumerate Additional Mutations \begin_deeper \layout Standard Two mutation operators were added to allow the structures to explore the space of possible flows: \layout Enumerate Jump: A brick and its subtree of descendants is cut off from the original parent and becomes a descendant of one of its \begin_inset Quotes eld \end_inset adoptive \begin_inset Quotes erd \end_inset parents. This does not change the positions of any brick, but the directions of flow may change as bricks which were ancestors become descendants. \layout Enumerate Redistribute Weight: A random joint's weight \begin_inset Formula \( w_{j} \) \end_inset is multiplied by a random number between zero and one resulting in a change of flow magnitudes. \end_deeper \layout Standard This genotype extension was used for the tree experiments (section \begin_inset LatexCommand \ref{sec.tree} \end_inset ) and for EvoCAD (section \begin_inset LatexCommand \ref{sec.evocad} \end_inset ). It does without any network problem solver and thus is much faster (by ten-fold, approximately) at the cost of failing to approve many valid structure s. In all, there was a speed benefit but \emph on changes of function \emph default were unlikely to happen (see section \begin_inset LatexCommand \ref{sec.exaptations} \end_inset ), meaning that some of the richness of the dynamics between evolving agent and complex environment was lost when we embedded more of the environment inside the agent. \layout Subsection A Step-By-Step Example \layout Standard In this section we build the NTP model for a sample brick structure in detail. \begin_float fig \layout Standard \align center \begin_inset Figure size 416 138 file lego/ex1.eps width 3 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Sample structure]{ \latex default \begin_inset LatexCommand \label{fig.ex1} \end_inset Sample structure with four bricks \begin_inset Formula \( b_{1},\ldots ,b_{4} \) \end_inset and a ground. \latex latex } \end_float We study a simple structure with four bricks and a ground (fig. \begin_inset LatexCommand \ref{fig.ex1} \end_inset ). \layout Standard In order to build the physical model, first we find the center of mass of all bricks (circles) and the center of the areas of contact between bricks (crosses), as shown on fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset . Each brick generates a force ( \begin_inset Formula \( F_{1},\ldots ,F_{4} \) \end_inset ) and each area of contact, a joint ( \begin_inset Formula \( j_{1},\ldots ,j_{5} \) \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 476 220 file lego/ex2.eps width 3 80.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Sample structure with loads and joints]{ \latex default \begin_inset LatexCommand \label{fig.ex2} \end_inset Loads and joints have been identified on the structure of fig. \begin_inset LatexCommand \ref{fig.ex1} \end_inset . \latex latex } \end_float Adding an axis of reference, lists of loads (forces) and joints are generated (tables \begin_inset LatexCommand \ref{table.ex2a} \end_inset and \begin_inset LatexCommand \ref{table.ex2b} \end_inset ). For the sake of simplicity the \emph on x \emph default and \emph on y \emph default axis are in \begin_inset Quotes eld \end_inset Lego units \begin_inset Quotes erd \end_inset : the width of a Lego unit is lw = 8 mm and the height, lh = 9.6 mm. \begin_float tab \layout Standard \align center \LyXTable multicol5 5 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" n \newline position \newline direction \newline source \newline magnitude \newline \begin_inset Formula \( F_{1} \) \end_inset \newline (4,4.5) \newline (0,-1) \newline \begin_inset Formula \( b_{1} \) \end_inset \newline \begin_inset Formula \( 6\: \beta \) \end_inset G \newline \begin_inset Formula \( F_{2} \) \end_inset \newline (7,3.5) \newline (0,-1) \newline \begin_inset Formula \( b_{2} \) \end_inset \newline \begin_inset Formula \( 4\: \beta \) \end_inset G \newline \begin_inset Formula \( F_{3} \) \end_inset \newline (10,4.5) \newline (0,-1) \newline \begin_inset Formula \( b_{3} \) \end_inset \newline \begin_inset Formula \( 4\: \beta \) \end_inset G \newline \begin_inset Formula \( F_{4} \) \end_inset \newline (13,3.5) \newline (0,-1) \newline \begin_inset Formula \( b_{4} \) \end_inset \newline \begin_inset Formula \( 2\: \beta \) \end_inset G \layout Standard \latex latex \backslash caption[Forces generated by sample Lego structure]{ \latex default \begin_inset LatexCommand \label{table.ex2a} \end_inset Loads obtained from fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset . \begin_inset Formula \( \beta \) \end_inset = weight of a Lego brick unit (0.4 g). G = gravitational constant. \latex latex } \end_float \begin_float tab \layout Standard \align center \LyXTable multicol5 6 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" n \newline nodes \newline position \newline knobs \newline max. torque \begin_inset Formula \( K \) \end_inset \newline \begin_inset Formula \( j_{1} \) \end_inset \newline \begin_inset Formula \( (b_{1},b_{2}) \) \end_inset \newline (6,4) \newline 2 \newline \begin_inset Formula \( \kappa _{2} \) \end_inset \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( (b_{2},b_{3}) \) \end_inset \newline (8,4) \newline 2 \newline \begin_inset Formula \( \kappa _{2} \) \end_inset \newline \begin_inset Formula \( j_{3} \) \end_inset \newline \begin_inset Formula \( (b_{2},G) \) \end_inset \newline (8,3) \newline 1 \newline \begin_inset Formula \( \kappa _{1} \) \end_inset \newline \begin_inset Formula \( j_{4} \) \end_inset \newline \begin_inset Formula \( (b_{3},b_{4}) \) \end_inset \newline (12.5,4) \newline 1 \newline \begin_inset Formula \( \kappa _{1} \) \end_inset \newline \begin_inset Formula \( j_{5} \) \end_inset \newline \begin_inset Formula \( (b_{4},G) \) \end_inset \newline (12.5,3) \newline 1 \newline \begin_inset Formula \( \kappa _{1} \) \end_inset \layout Standard \latex latex \backslash caption[Joints generated by sample Lego structure]{ \latex default \begin_inset LatexCommand \label{table.ex2b} \end_inset Joints generated from fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset . The torque resistances \begin_inset Formula \( \kappa _{1} \) \end_inset , \begin_inset Formula \( \kappa _{2} \) \end_inset are listed on table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset . \latex latex } \end_float \layout Standard From the layout we generate a graph that represents the connectivity of the structure (fig. \begin_inset LatexCommand \ref{fig.ex3} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 386 153 file lego/ex3.eps width 3 65.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.ex3} \end_inset Graph generated by the structure of fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset . \end_float Bricks and ground generate nodes on the graph and joints generate edges. \layout Standard We consider initially what the situation is for the first load alone ( \begin_inset Formula \( F_{1} \) \end_inset ). This force is originated by the mass of brick number one, and so it points downwards, its magnitude being equal to the weight of a Lego brick of width six ( \begin_inset Formula \( =6\: \beta \text {G} \) \end_inset , where \begin_inset Formula \( \beta \) \end_inset = 0.4 g is the per-unit weight of our Lego bricks, and G the earth's gravitation al constant). According to equation \begin_inset LatexCommand \ref{eq.flow} \end_inset , the capacity of each joint with respect to this particular load is the magnitude of the load, multiplied by the torque's arm and divided by the capacity of the joint (table \begin_inset LatexCommand \ref{table.ex3} \end_inset ). The value of the sign is 1 if the rotation is clockwise and -1 if counterclockw ise. \begin_float tab \layout Standard \align center \LyXTable multicol5 6 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Joint \newline Force \newline arm length ( \begin_inset Formula \( \delta ) \) \end_inset \newline relative capacity ( \begin_inset Formula \( \alpha ) \) \end_inset \newline sign \newline \begin_inset Formula \( j_{1} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 2 lw \newline \begin_inset Formula \( \frac{\kappa _{2}}{2\cdot 6\: \text {lw}\beta \text {G}} \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 4 lw \newline \begin_inset Formula \( \frac{\kappa _{2}}{4\cdot 6\: \text {lw}\beta \text {G}} \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{3} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 4.5 lw \newline \begin_inset Formula \( \frac{\kappa _{1}}{4.5\cdot 6\: \text {lw}\beta \text {G}} \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{4} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 8.5 lw \newline \begin_inset Formula \( \frac{\kappa _{1}}{8.5\cdot 6\: \text {lw}\beta \text {G}} \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{5} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 8.5 lw \newline \begin_inset Formula \( \frac{\kappa _{1}}{8.5\cdot 6\: \text {lw}\beta \text {G}} \) \end_inset \newline -1 \layout Standard \latex latex \backslash caption[Capacities of network generated by sample structure]{ \latex default \begin_inset LatexCommand \label{table.ex3} \end_inset Capacities of the example network with respect to load \begin_inset Formula \( F_{1} \) \end_inset . Each joint can support a fraction of the load equal to the torque capacity of the joint divided by the torque exerted by that particular force at that joint, which in turn is the arm length multiplied by the magnitude of the force. lw = width of a Lego brick = 0.8 mm. \latex latex } \end_float \layout Standard With the true values \begin_float footnote \layout Standard According to table \begin_inset LatexCommand \ref{table.jointsizes} \end_inset , and assuming \begin_inset Formula \( \text {G}=9.8m/s^{2} \) \end_inset , the values of \begin_inset Formula \( \kappa _{1},\ldots ,\kappa _{6} \) \end_inset are respectively: 405, 1960, 3500, 6144, 11000 and 13520 \begin_inset Formula \( \text {lw}\beta \text {G} \) \end_inset . \end_float for \begin_inset Formula \( \kappa _{1} \) \end_inset and \begin_inset Formula \( \kappa _{2} \) \end_inset , the capacities of all joints in the example are far greater than the light forces generated by this small structure. To illustrate distribution of force we use fictitious values for the constants. Assuming \begin_inset Formula \( \kappa _{1}=20\: \text {lw}\beta \text {G} \) \end_inset and \begin_inset Formula \( \kappa _{2}=45\: \text {lw}\beta \text {G} \) \end_inset , the capacities of joints \begin_inset Formula \( j_{1},\ldots ,j_{5} \) \end_inset relative to load \begin_inset Formula \( F_{1} \) \end_inset are respectively 1, 1, \begin_inset Formula \( \frac{20}{27} \) \end_inset , \begin_inset Formula \( \frac{20}{51} \) \end_inset and \begin_inset Formula \( \frac{20}{51} \) \end_inset , leading to the network flow problem (and solution) on fig. \begin_inset LatexCommand \ref{fig.ex4} \end_inset . Each edge was labelled with the capacity and (parenthesized) a solution. \begin_float fig \layout Standard \align center \begin_inset Figure size 416 151 file lego/ex4.eps width 3 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Network flow problem generated by sample structure]{ \latex default \begin_inset LatexCommand \label{fig.ex4} \end_inset Network flow problem generated by the weight of brick \begin_inset Formula \( b_{1} \) \end_inset on the sample structure of fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset , assuming \begin_inset Formula \( \kappa _{1}=20 \) \end_inset and \begin_inset Formula \( \kappa _{2}=45\: \text {lw}\beta \text {G} \) \end_inset . The source is \begin_inset Formula \( b_{1} \) \end_inset and the sink \begin_inset Formula \( G \) \end_inset . Each node is labelled with a capacity, and (in parenthesis) a valid flow is shown: \begin_inset Formula \( \phi _{1}(1,2)=1 \) \end_inset , \begin_inset Formula \( \phi _{1}(2,3)=0.3 \) \end_inset , \begin_inset Formula \( \phi _{1}(3,4)=0.3 \) \end_inset , \begin_inset Formula \( \phi _{1}(4,G)=0.3, \) \end_inset \begin_inset Formula \( \phi _{1}(2,G)=0.7 \) \end_inset . \latex latex } \end_float \layout Standard The solution to this flow problem could have been obtained by a maximum flow algorithm. A greedy solver would reduce now the network, computing a \begin_inset Quotes eld \end_inset remaining capacity \begin_inset Quotes erd \end_inset for each joint (table \begin_inset LatexCommand \ref{table.ex4a} \end_inset \begin_float tab \layout Standard \align center \LyXTable multicol5 6 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Joint \newline Force \newline Flow \begin_inset Formula \( \phi _{F_{1}}(j) \) \end_inset \newline torque ( \begin_inset Formula \( \text {lw}\beta \text {G} \) \end_inset ) \newline residual capacity(*) \newline \begin_inset Formula \( j_{1} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 1.0 \newline \begin_inset Formula \( -1.0\cdot 2\cdot 6 \) \end_inset \newline \begin_inset Formula \( [-33,57] \) \end_inset \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 0.3 \newline \begin_inset Formula \( -0.3\cdot 4\cdot 6 \) \end_inset \newline \begin_inset Formula \( [-37.8,52.2 \) \end_inset ] \newline \begin_inset Formula \( j_{3} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 0.7 \newline \begin_inset Formula \( -0.7\cdot 4.5\cdot 6 \) \end_inset \newline \begin_inset Formula \( [-1.1,38.9] \) \end_inset \newline \begin_inset Formula \( j_{4} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 0.3 \newline \begin_inset Formula \( -0.3\cdot 8.5\cdot 6 \) \end_inset \newline \begin_inset Formula \( [-4.7,35.3] \) \end_inset \newline \begin_inset Formula \( j_{5} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 0.3 \newline \begin_inset Formula \( -0.3\cdot 8.5\cdot 6 \) \end_inset \newline \begin_inset Formula \( [-4.7,35.3] \) \end_inset \layout Standard \latex latex \backslash caption[Greedy solver: residual capacities]{ \latex default \begin_inset LatexCommand \label{table.ex4a} \end_inset Greedy solver: Residual joint capacities for the sample structure, after force \begin_inset Formula \( F_{1} \) \end_inset has been distributed according to fig. \begin_inset LatexCommand \ref{fig.ex4} \end_inset . (*) Assuming \begin_inset Formula \( \kappa _{2}=45, \) \end_inset \begin_inset Formula \( \kappa _{1}=20 \) \end_inset . \latex latex } \end_float ). The stress on joint \begin_inset Formula \( j_{2} \) \end_inset for example, is equal to \begin_inset Formula \( -0.3\cdot 4\cdot 6\: \text {lw}\beta \text {G} \) \end_inset (counterclockwise). If the initial capacity of \begin_inset Formula \( j_{2} \) \end_inset was \begin_inset Formula \( [-\kappa _{2},\kappa _{2}]=[-45,45] \) \end_inset , the reduced capacity (according to eq. \begin_inset LatexCommand \ref{eq.greedy} \end_inset ) would be \begin_inset Formula \( [-37.8,52.2] \) \end_inset . So when a flow network for \begin_inset Formula \( F_{2} \) \end_inset is generated, the reduced capacities of joints are used, incorporating the effects of the previous load. (table \begin_inset LatexCommand \ref{table.ex4} \end_inset \begin_float tab \layout Standard \align center \LyXTable multicol5 7 6 0 0 -1 -1 -1 -1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" joint \newline force \newline arm length \newline magnitude \newline sign \newline capacity (w.r.t. \begin_inset Formula \( F_{2} \) \end_inset ) \newline \newline \newline (lw) \newline ( \begin_inset Formula \( \text {lw}\beta \text {G} \) \end_inset ) \newline \newline (see table \begin_inset LatexCommand \ref{fig.ex4} \end_inset ) \newline \begin_inset Formula \( j_{1} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 1 \newline 4 \newline 1 \newline 1 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 1 \newline 4 \newline -1 \newline 1 \newline \begin_inset Formula \( j_{3} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 1.5 \newline 6 \newline -1 \newline \begin_inset Formula \( \frac{1.1}{6} \) \end_inset \newline \begin_inset Formula \( j_{4} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 5.5 \newline 22 \newline -1 \newline \begin_inset Formula \( \frac{4.7}{22} \) \end_inset \newline \begin_inset Formula \( j_{5} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 5.5 \newline 22 \newline -1 \newline \begin_inset Formula \( \frac{4.7}{22} \) \end_inset \layout Standard \latex latex \backslash caption[Joint capacities for second force]{ \latex default \begin_inset LatexCommand \label{table.ex4} \end_inset Greedy solver: capacities of the joints in the sample structure, with respect to force \begin_inset Formula \( F_{2} \) \end_inset , after the loads resulting from \begin_inset Formula \( F_{1} \) \end_inset have been subtracted. \latex latex } \end_float and figure \begin_inset LatexCommand \ref{fig.ex5} \end_inset ). In this example, there is no solution, so in fact the structure could not be proved stable. \begin_float fig \layout Standard \align center \begin_inset Figure size 416 165 file lego/ex5.eps width 3 70.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.ex5} \end_inset Greedy solver: NFP problem for the second force. \end_float \layout Standard For the multicommodity solver, all forces are considered simultaneously. The capacities of each joint become boundary conditions on a multicommodity network flow problem. For example, we can write down the equation for joint number two by generating a table of all forces and their relative weights for this particular joint (table \begin_inset LatexCommand \ref{table.ex5} \end_inset \begin_float tab \layout Standard \align center \LyXTable multicol5 5 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" joint \newline force \newline arm length (lw) \newline magnitude ( \begin_inset Formula \( \text {lw}\beta \text {G} \) \end_inset ) \newline sign \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{1} \) \end_inset \newline 4 \newline \begin_inset Formula \( 6\cdot 4 \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{2} \) \end_inset \newline 1 \newline \begin_inset Formula \( 4\cdot 1 \) \end_inset \newline -1 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{3} \) \end_inset \newline 2 \newline \begin_inset Formula \( 6\cdot 2 \) \end_inset \newline 1 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( F_{4} \) \end_inset \newline 5 \newline \begin_inset Formula \( 2\cdot 5 \) \end_inset \newline 1 \layout Standard \latex latex \backslash caption[Relative weights of forces on sample structure]{ \latex default \begin_inset LatexCommand \label{table.ex5} \end_inset Relative weights of the forces from fig. \begin_inset LatexCommand \ref{fig.ex2} \end_inset as they act on joint number two. \latex latex } \end_float ).According to the table, and per equation \begin_inset LatexCommand \ref{eq.multiflow} \end_inset , if \begin_inset Formula \( \phi _{1},\ldots ,\phi _{4} \) \end_inset are the flow functions of forces \begin_inset Formula \( F_{1},\ldots ,F_{4} \) \end_inset , the boundary condition for joint two is: \begin_inset Formula \begin{equation} \label{eq.example} \left| -24\: \phi _{1}(2,3)-4\: \phi _{2}(2,3)+12\: \phi _{3}(3,2)+10\: \phi _{4}(3,2)\right| \leq \kappa _{2} \end{equation} \end_inset \layout Standard a solution to this problem is a set of four flows \begin_inset Formula \( \phi _{1},\ldots \phi _{4} \) \end_inset , each one transporting a magnitude of one from the origin of each force ( \begin_inset Formula \( F_{i} \) \end_inset originates at \begin_inset Formula \( b_{i} \) \end_inset in our example) into the sink G, that also satisfies five boundary equations, analogous to eq. \begin_inset LatexCommand \ref{eq.example} \end_inset , one per joint. A multicommodity flow algorithm searches the space of all possible flows, using linear programming techniques, looking for such a solution. \layout Standard Finally, using the embedded solver would mean that the genotype pre-specifies a unique direction of flow, and a weight for all joints, as in table \begin_inset LatexCommand \ref{table.ex6} \end_inset \begin_float tab \layout Standard \align center \LyXTable multicol5 6 5 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" joint \newline direction \newline weight ( \begin_inset Formula \( w \) \end_inset ) \newline knobs ( \begin_inset Formula \( \omega \) \end_inset ) \newline \begin_inset Formula \( \omega w \) \end_inset \newline \begin_inset Formula \( j_{1} \) \end_inset \newline \begin_inset Formula \( b_{1}\rightarrow b_{2} \) \end_inset \newline 1 \newline 2 \newline 2 \newline \begin_inset Formula \( j_{2} \) \end_inset \newline \begin_inset Formula \( b_{3}\rightarrow b_{2} \) \end_inset \newline 1.5 \newline 2 \newline 3 \newline \begin_inset Formula \( j_{3} \) \end_inset \newline \begin_inset Formula \( b_{2}\rightarrow G \) \end_inset \newline 0.75 \newline 1 \newline 0.75 \newline \begin_inset Formula \( j_{4} \) \end_inset \newline \begin_inset Formula \( b_{3}\rightarrow b_{4} \) \end_inset \newline 1 \newline 1 \newline 1 \newline \begin_inset Formula \( j_{5} \) \end_inset \newline \begin_inset Formula \( b_{4}\rightarrow G \) \end_inset \newline 2 \newline 1 \newline 2 \layout Standard \latex latex \backslash caption[Embedded solver: the genotype specifies direction of flow and and weight]{ \latex default \begin_inset LatexCommand \label{table.ex6} \end_inset Embedded solver: the genotype specifies direction of flow and a random weight for each joint. Together with the number of knobs of in the joint, these specify the percentage of flow in each direction. In this example, brick \begin_inset Formula \( b_{3} \) \end_inset has two outgoing joints, to bricks \begin_inset Formula \( b_{2} \) \end_inset and \begin_inset Formula \( b_{4} \) \end_inset , with \begin_inset Formula \( \omega w \) \end_inset values of 3 and 1, respectively. This means that 75% of any loads going through \begin_inset Formula \( b_{3} \) \end_inset will pass on to \begin_inset Formula \( b_{2} \) \end_inset and the remaining 25% will rest on \begin_inset Formula \( b_{4} \) \end_inset . \latex latex } \end_float for example. Figure \begin_inset LatexCommand \ref{fig.ex6} \end_inset \begin_float fig \layout Standard \align center \begin_inset Figure size 416 165 file lego/ex6.eps width 3 70.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.ex6} \end_inset DAG determined by the genotype of a structure using the embedded solver approach. \end_float shows the resulting DAG which determines all four flows (table \begin_inset LatexCommand \ref{table.ex7} \end_inset ) \begin_float tab \layout Standard \align center \LyXTable multicol5 5 2 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" flow \newline value \newline \begin_inset Formula \( \phi _{1} \) \end_inset \newline \begin_inset Formula \( b_{1}\rightarrow b_{2}\rightarrow G \) \end_inset \newline \begin_inset Formula \( \phi _{2} \) \end_inset \newline \begin_inset Formula \( b_{2}\rightarrow G \) \end_inset \newline \begin_inset Formula \( \phi _{3} \) \end_inset \newline \begin_inset Formula \( \frac{3}{4}b_{3}\rightarrow b_{2}\rightarrow G+\frac{1}{4}b_{3}\rightarrow b_{4}\rightarrow G \) \end_inset \newline \begin_inset Formula \( \phi _{4} \) \end_inset \newline \begin_inset Formula \( b_{4}\rightarrow G \) \end_inset \layout Caption \begin_inset LatexCommand \label{table.ex7} \end_inset Flows generated by the embedded solution. \end_float and thus the total torque for all the joints. Whereas in the greedy example we had the weight \begin_inset Formula \( F_{1} \) \end_inset of brick \begin_inset Formula \( b_{1} \) \end_inset flowing in part via \begin_inset Formula \( b_{2}\rightarrow G \) \end_inset (30%) and in part via \begin_inset Formula \( b_{2}\rightarrow b_{3}\rightarrow b_{4}\rightarrow G \) \end_inset (70%), in this embedded solver example, the only route allowed for the genotype is \begin_inset Formula \( F_{1} \) \end_inset is via \begin_inset Formula \( b_{2}\rightarrow G \) \end_inset . Again, with the values for \begin_inset Formula \( \kappa _{1} \) \end_inset , \begin_inset Formula \( \kappa _{2} \) \end_inset used in this example, the weight on joint \begin_inset Formula \( j_{3} \) \end_inset is excessive so the structure is not stable. \layout Section \begin_inset LatexCommand \label{sec.evolvinglego} \end_inset Evolving Brick structures \layout Standard Our representation to evolve Lego structures borrows the tree mutation and crossover operators from genetic programming (GP) \begin_inset LatexCommand \cite{koza90} \end_inset . We implemented tree representations of 2D and 3D Lego structures. Each node of the tree represents a brick and has a size parameter, indicating the size of the brick, and a list of descendants, which are new bricks physically attached to the parent. Each descendant node has positional parameters that specify the position of the new brick relative to the parent. \layout Subsection Coding for 2D and 3D structures \layout Standard In the first, 2D version of this work \begin_inset LatexCommand \cite{funespollack97} \end_inset , each brick node had a size type parameter (4, 6, 8, 10, 12 or 16, correspondin g to the Lego bricks of size \begin_inset Formula \( 1\times 4 \) \end_inset through \begin_inset Formula \( 1\times 16 \) \end_inset ) and four potential descendants, each one representing a new brick linked at one of its four corners (lower left, lower right, upper right, upper left). Each non-nil descendant had a `joint size' parameter indicating the number of overlapping knobs in the union. \begin_float fig \layout Standard \align center \begin_inset Figure size 416 112 file lego/graph/enco2d.eps width 3 70.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.2drep} \end_inset Example of 2D genetic encoding of bricks (eq. \begin_inset LatexCommand \ref{25867} \end_inset ). \end_float \layout Standard Fig. \begin_inset LatexCommand \ref{fig.2drep} \end_inset represents a 10-brick with its 4 joint sites labeled 0, 1, 2, 3, that is linked to a 6-brick by two overlapping knobs. The corresponding tree could be written in Lisp-like notation as \begin_inset Formula \begin{equation} \label{25867} \text {(10\, nil\, (2\, (6\, nil\, nil\, nil))\, nil\, nil)} \end{equation} \end_inset \layout Standard For 3D structures we added more size types to incorporate bricks other than \emph on \begin_inset Formula \( 1\times n \) \end_inset \emph default (the table experiment in section \begin_inset LatexCommand \ref{sec.table} \end_inset had sizes \begin_inset Formula \( 1\times 2 \) \end_inset , \begin_inset Formula \( 1\times 4 \) \end_inset , \begin_inset Formula \( 1\times 6 \) \end_inset , \begin_inset Formula \( 1\times 10 \) \end_inset , \begin_inset Formula \( 1\times 12 \) \end_inset , \begin_inset Formula \( 1\times 16 \) \end_inset , \begin_inset Formula \( 2\times 2 \) \end_inset and \begin_inset Formula \( 2\times 4 \) \end_inset ), and used a list of descendants, each one representing a new brick to be plugged into the parent. Each descendant brick has 3 parameters: The \emph on (x, y, z) \emph default coordinates of the new brick (relative to its parent, so for a descendant of an \emph on \begin_inset Formula \( n\times m \) \end_inset \emph default brick, \begin_inset Formula \( 0\leq xy \) \end_inset . \begin_float tab \layout Standard \added_space_top 0.3cm \added_space_bottom 0.3cm \align center \LyXTable multicol5 14 2 0 0 -1 -1 -1 -1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 8 1 1 "" "" 8 0 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Bricks \newline {4,6,8,10,12,16} \newline Max Bricks \newline 127 \newline Base \newline (0,-1)--(-16,-1) \newline \emph on x \emph default Range \newline (-50,22) \newline \emph on y \emph default Range \newline (-1,40) \newline \emph on xy \emph default Restriction \newline \emph on y \emph default > \emph on -x \emph default \newline Fixed Bricks \newline 6 at (6,0) \newline \newline 4 at (12,0) \newline \newline 4 at (12,1) \newline \newline 4 at (12,2) \newline \newline 4 at (12,3) \newline Fitness \newline \begin_inset Formula \( 1+(-x)\alpha \) \end_inset \newline \newline \emph on x \emph default = position of the tip \newline \newline \begin_inset Formula \( \alpha \) \end_inset = fraction of 250g supported \layout Caption \begin_inset LatexCommand \label{crane.setup} \end_inset Setup of the diagonal crane arm experiment. \end_float \layout Standard We observed a curious phenomenon about the way a triangular solution appeared. Soon the crane evolved a counterbalance, located at the top, to act against the massive external load. This counterbalance took the shape of a bar going back from the tip of the crane --- where the load is located, with a pile of bricks at the other end to act against the weight. This counter-weight could not be too heavy, for the crane is required to support its own weight before adding the external load (fig. \begin_inset LatexCommand \ref{fig.triangles} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 297 253 file lego/triangle1.eps width 3 50.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 297 253 file lego/triangle2.eps width 3 50.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 297 252 file lego/triangle3.eps width 3 50.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.triangles} \end_inset Three stages on the evolution of the diagonal crane arm: counterbalance, closer to triangle, closed triangle. \end_float \layout Standard With the tendency to reuse useful parts that had already been observed in the long bridge experiment, the counterbalance at the tip, with its \begin_inset Quotes eld \end_inset J \begin_inset Quotes erd \end_inset shape, reappeared at a lower position, creating an arm counterbalanced at two points. The fact that these two counterbalances ended up connecting to each other and touching down at the base was a fortuitous event that created a new stronger synthesis: a triangular shape which supports more weight than the original counterbalancing bar, by tensioning the vertical column. At the same time the triangle supports all this counterbalancing apparatus (by compression) when the crane is not lifting a load. This is a change of use, as discussed in section \begin_inset LatexCommand \ref{sec.exaptations} \end_inset , only in a much larger scale. \layout Section Optimization \layout Standard A comment that we often receive is that our final structures are not optimized: they contain redundant bricks that do not serve any apparent purpose. Of course, these irregularities are useful during the search process. Since we are not rewarding nor punishing for the number of bricks used, the evolutionary search freely generates variations with different numbers of bricks. All of them are potentially useful in the process of finding new combinations with higher fitness. \layout Standard In a new run of the diagonal crane arm experiment, we added a little reward for lightness, inversely proportional to the number of bricks, but three orders of magnitude smaller than the raw fitness function. Fig. \begin_inset LatexCommand \ref{fig.optimization} \end_inset shows two solutions for a crane arm the same length (a fitness value of 24). The structure on the right has a bigger premium, so we will prefer it. \layout Standard Since we are willing to sacrifice everything else for the length of the arm, the fitness weight of the `simplicity' factor has to be very small compared with the raw fitness measure (arm length). Among cranes of the same size and resistance, however, we prefer those with a smaller number of bricks. The evolutionary process is not biased against heavier versions of the crane; it just detects the simpler ones. In the example shown in fig. \begin_inset LatexCommand \ref{fig.optimization} \end_inset , fitness values of 24.0029 and 24.0040 have nearly identical chances of being selected in a fitness proportional selection scheme. But among otherwise identical cranes, the premium for implies that the cleanest one makes the final cut. \begin_float fig \layout Standard \align center \begin_inset Figure size 267 218 file lego/graph/opt1.eps width 3 45.00 flags 11 \end_inset \SpecialChar ~ \begin_inset Figure size 267 218 file lego/graph/opt2.eps width 3 45.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Optimization]{ \latex default \begin_inset LatexCommand \label{fig.optimization} \end_inset Optimization: Among several structures found with a raw fitness of 24, a small premium in the fitness function allows us to choose the one that uses less bricks (right). The tall vertical column (on the optimized version) cannot be eliminated because it acts as a counterbalance for the load that will be placed at the left tip of the crane. \latex latex } \end_float \layout Section \begin_inset LatexCommand \label{sec.tree} \end_inset Symmetry, Branching, Modularity: Lego Tree \layout Standard The \emph on tree \emph default experiment was designed to test out whether some characteristics of natural trees (branching, symmetry) could evolve as a consequence of the environment. The design of a tree in nature is a product of conflicting objectives: maximizing the exposure to light while keeping internal stability. \layout Standard The experimental design for the tree has a narrow attachment base: Only three knobs. This provides very little sustentation for cantilevering, so the structure will have to be balanced to reach out. A ``light'' resource, coming from directions up, left and right, has one value per column or row. Light is ``absorbed \begin_inset Quotes erd \end_inset by the first brick it touches --- and the fitness points given are equal to the distance from the absorption point to the \emph on x \emph default or \emph on y \emph default axis. The highest fitness would be a structure reaching out to completely cover the left, right and top borders (see fig. \begin_inset LatexCommand \ref{fig.treesetup} \end_inset and table \begin_inset LatexCommand \ref{table.tree.setup} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 416 281 file lego/treescheme.eps width 3 70.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.treesetup} \end_inset Tree experiment \end_float \layout Standard There were no symmetry-oriented operators in our experiments, as could be, for example a ``reverse'' recombination operator that switched the orientation of a subpart. This means that symmetry is not encouraged by representational biases. Instead, the problem setup requires balancing the total weight of both sides. The tree did evolve, however, with a central symmetry with branches reaching out, by evolving the same type of solution separately on both sides. \layout Standard The general layout of the evolved tree has several similarities with that of a real tree: there is a (somewhat twisted) trunk, with branches that become thinner as they reach out, and ``leaves'', bulky formations that maximize the surface at the end of the branch. \begin_float tab \layout Standard \added_space_top 0.3cm \added_space_bottom 0.3cm \align center \LyXTable multicol5 11 2 0 0 -1 -1 -1 -1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 8 1 1 "" "" 8 0 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Bricks \newline {1,2,4,6,8,10,12,16} \newline Max Bricks \newline 127 \newline Base \newline (0,-1)--(2,-1) \newline \emph on x \emph default Range \newline (-50,52) \newline \emph on y \emph default Range \newline (0,45) \newline Fitness \newline \begin_inset Formula \( f_{L}+f_{R}+f_{T} \) \end_inset \newline \newline where \newline \newline \begin_inset Formula \( f_{L}=\sum ^{45}_{j=0}\max \left( 0,-\min \{x:(x,j)\in S\}\right) \) \end_inset \newline \newline \begin_inset Formula \( f_{R}=\sum ^{45}_{j=0}\max \left( 0,\max \{x:(x,j)\in S\}\right) \) \end_inset \newline \newline \begin_inset Formula \( f_{T}=\sum ^{52}_{i=-50}\max \left( 0,\max \{y:(i,y)\in S\}\right) \) \end_inset \newline \newline \begin_inset Formula \( S \) \end_inset = structure \layout Caption \begin_inset LatexCommand \label{table.tree.setup} \end_inset Setup of the tree experiment. \end_float \layout Standard The tree is, among all our experiments, the one that most clearly illustrates the emergence of nested levels of organization, key indicator of what we call complex organization \layout Itemize Level zero: individual bricks. \layout Itemize Level 1: diagonal stacks and horizontal stacks of long bricks (on the branches), stacks of small bricks (at the tips), \layout Itemize Level 2: trunk, U shaped branches, T structure at the top. \layout Itemize Level 3: two tridents on top of each other, and a roof. \layout Itemize Level 4: the entire structure. \begin_float fig \layout Standard \align center \begin_inset Figure size 446 375 file lego/tree6a.eps width 3 75.00 flags 11 \end_inset \newline \begin_inset Figure size 446 328 file tree1.eps width 3 75.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.tree} \end_inset Evolved Tree (internal model and built structure) \end_float \layout Subsection Recombination Example \layout Standard An interesting observation that illustrates the role of mutations is that the observed organization we have called \begin_inset Quotes eld \end_inset level 3 \begin_inset Quotes erd \end_inset occurred as a result of one single crossover operation. In this lucky event (fig. \begin_inset LatexCommand \ref{fig.treexover} \end_inset ), the bottom half part was reused to create also the top half part, discarding all the previous evolution of a top half that did not create a branching structure. \layout Standard The \begin_inset Quotes eld \end_inset branches \begin_inset Quotes erd \end_inset organization proved to be evolutionarily more robust than the \begin_inset Quotes eld \end_inset fork \begin_inset Quotes erd \end_inset organization found initially, as it survived until the end of the run. The reuse of subparts and submodules is fundamental to generate these type of discrete transition. \begin_float fig \layout Standard \align center \begin_inset Figure size 279 237 file lego/graph/legodad.eps width 3 47.00 flags 11 \end_inset \latex latex \backslash hfill \latex default \begin_inset Figure size 279 237 file lego/graph/legomom.eps width 3 47.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 357 304 file lego/graph/legoson.eps width 3 60.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Recombination]{ \latex default \begin_inset LatexCommand \label{fig.treexover} \end_inset \emph on Recombination \emph default . An interesting example of a recombination at the highest level, that creates a recursive structure. The two parents (top) are close relatives, very similar. The root parent (top left) got the crossover point in the trunk of the structure; bricks colored white were discarded by the operation. The secondary parent (top right) had its insertion point at the root. The resulting structure is shown at the bottom. Besides the bricks lost by the root parent's replacement of a subtree, other bricks were lost during the development process: the secondary parent lost all its top bricks (colored white) because they became out-of-bounds, and the central-left branch of the root parent lost three bricks because the maximum bricks limit (127) was reached. The final version of the tree (fig. \begin_inset LatexCommand \ref{fig.tree} \end_inset ) evolved from this individual. \latex latex } \end_float \layout Section \begin_inset LatexCommand \label{sec.evocad} \end_inset Discovery is creativity: EvoCAD \layout Standard Today's commercial CAD systems may add a mechanical simulator to the usual 3D manipulation tools \begin_float footnote \layout Standard PTC's Pro/Engineer software, whose CAD tool can generate output for the mechanical simulator, Pro/Mechanica, is an example. \end_float . But the new field of Evolutionary Design (ED) \begin_inset LatexCommand \cite{bentley99} \end_inset has the potential to add a third leg to computer-aided design: A creative role. Not only designs can be drawn (as in CAD), or drawn and simulated (as in CAD+simulation), but also designed by the computer following guidelines given by the operator. Thus we envision future Evolutionary CAD systems, ``EvoCADs.'' \layout Standard An EvoCAD system has the human designer in the main role: the designer has an idea or concept for a required object. Some of the requirements can be added to the 3D canvas, creating evolutionary targets that an ED engine uses for evolving a possible design. The output of this evolutionary engine can be modified, tested and re-evolved as many times as desired (figure \begin_inset LatexCommand \ref{fig.evocad} \end_inset ). \layout Standard To demonstrate our conception of EvoCAD, we have built a mini-CAD system to design 2D Lego structures. This Lego EvoCAD allows the user to manipulate Lego structures, and test their gravitational resistance using the same structural simulator we have been using to do ED with Lego bricks. It also interfaces to an evolutionary algorithm that combines user-defined goals with simulation to evolve candidate solutions for the design problems. The results of evolution are sent back to the CAD front-end to allow for further re-design until a satisfactory solution is obtained. \begin_float fig \layout Standard \align center \begin_inset Figure size 476 328 file applet/ecad.eps width 3 80.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[A conceptual EvoCAD system]{ \latex default \begin_inset LatexCommand \label{fig.evocad} \end_inset A conceptual EvoCAD system has two ``creative minds'', the human designer and the ED software. The human designer is in control, and calls upon the remaining elements as tools. A problem description language (PDL) allows CAD, evolutionary and simulation components to communicate with each other (bold arrows). \latex latex } \end_float \layout Subsection Evolutionary Algorithm \layout Standard Instead of initializing the population with a single brick, as in previous experiments, here we want the current design to be used as a starting point. \layout Standard To begin an evolutionary run, a starting structure is received by the ED engine, consisting of one or more bricks, and needs to be ``reverse-compiled'' into a genetic representation in order to seed the population. \layout Standard Mutation and crossover operators are applied iteratively to grow and evolve a population of structures. The simulator is run on each new structure to test for stability and load support, and compute a fitness value. Evolution stops when all objectives are satisfied or when a timeout occurs. \layout Subsection Brick Problem Description Language \layout Standard We designed a Brick Problem Description Language (BPDL), as an interface between the evolutionary algorithm, simulator, and the CAD front-end. When the user clicks the ``evolve'' button, a BPDL description is sent over the Internet to an evolution server which evolves a solution for the problem. The result of the evolution is sent back to the CAD using the same language. The simulator receives BPDL-encoded structures for testing, both from the CAD (when the human wants to test a structure) and from the evolutionary engine, which tests every mutated or recombined structure \begin_float tab \layout Standard \align center \LyXTable multicol5 11 3 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 8 1 0 "" "" 8 1 1 "" "" 2 0 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 2 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 2 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Object type \newline Parameters \newline Comments \newline brick \newline x, y, size \newline Bricks will compose the initial seed of \newline \newline \newline the evolving population. \newline fixed brick \newline x, y, size \newline Bricks that are not modifiable by evolution. \newline ground \newline x, y, size \newline At least one needed. \newline \newline \newline One or more grounds support the structure. \newline load \newline x, y, magnitude \newline Loads that must be supported by the structure. \newline target point \newline x, y \newline Points that must be touched by the structure. \newline restriction \newline x, y \newline Points that are unusable. \newline canvas limits \newline min x, max x, \newline Describes canvas size to evolutionary engine, \newline \newline min y, max y \newline establishing boundaries for the simulator. \layout Standard \latex latex \backslash caption[Brick problem description language (BPDL)]{ \latex default Brick problem description language (BPDL) symbols are used to send problems and solutions between evolving engine, CAD screen and simulator \latex latex } \end_float . \layout Subsection Target Points and Target Loads \layout Standard The goals for the ED engine are deduced from user-defined \emph on Restrictions \emph default , \emph on Target Points \emph default and \emph on Target Loads \emph default . A structure will be fully satisfactory if it touches all the target points and target load points, whereas avoiding all the restricted points, and supports all the specified loads at each target load point. \begin_float fig \layout Standard \align center \begin_inset Figure size 595 375 file applet/fourpics.eps width 3 100.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Sample working session with the EvoCAD program]{ \latex default \begin_inset LatexCommand \label{fig.evocadsession} \end_inset Sample working session with the EvoCAD program: (a) The user has defined two grounds and several evolutionary hints: restrictions (x), target (dot) and load (arrow). An initial brick was laid down. (b) Evolution designed a structure that fulfills all requirements. (c) The user made cosmetic corrections (d) The structure has been built with Lego bricks. \latex latex } \end_float \layout Subsection Fitness Function \layout Standard All previous experiments used handwritten fitness functions to guide the search For EvoCAD we need instead to compute a generic fitness value for any BPDL structure. Although optimized fitness functions will require further study, the fitness of a structure S has been defined as: \begin_inset Formula \begin{equation} \label{equ.evocad} \sum _{t\in \text {targets}}\frac{1}{1+d(S,t)}+\sum _{l\in \text {loads}}\frac{1}{1+d(S,l)}+\sum _{\begin{array}{c} l\in \text {loads}\\ d(S,l)=0 \end{array}}\text {supp}(S,l) \end{equation} \end_inset \layout Standard (where \emph on d \emph default computes the distance between a point and the nearest brick in the structure, and \emph on supp \emph default uses the simulator to compute the fraction of a certain load that the structure supports) \layout Subsection Results \layout Standard Our Lego EvoCAD system (figure \begin_inset LatexCommand \ref{fig.evocadsession} \end_inset ) demonstrates how a new kind of application could employ ED techniques to let the computer not only be a canvas and a simulation tool, but also create its own designs following the users' specifications. Our system allows human and computer to create a design collaboratively, greatly reducing the human effort needed to craft and optimize a design. \layout Section \begin_inset LatexCommand \label{sec.legodiscussion} \end_inset Discussion \layout Subsection Modeling and the Reality Gap \layout Standard The properties of bricks are variable. Differences in construction, age, dirt, temperature, humidity and other unpredictable factors produce seemingly random variations when their behavior is measured. These factors had to be considered in order to have buildable results. We have accounted for this problem using a safety margin: our model assigns 20% less resistance to all the joints involved. \layout Standard The simplistic simulator described is far from modeling physics to its full detail, yet any model for modular structures, no matter how accurate, has to compensate for the random variability in the generic properties of the average brick, using similar methods. The value of 20% was set intuitively and may require further study, especially as our structures scale up in size and complexity. \layout Standard Engineers have been using safety margins for a long time, to deal with all the factors that cannot be calculated ahead of time. In ALife, evolutionary roboticists have found unpredictabilities when attemptin g to simulate the environment for a real robot \begin_inset LatexCommand \cite{jakobi95,mataric96} \end_inset . One simple technique used in ER is to add random noise to the simulated sensors in order to generate robust behaviors suitable to be transferred to the real world. \layout Standard Noise and safety margins are variations on a fundamental principle of conservati veness. The so-called ``reality gap'', which is the difference between the model and the final artifact, does not mean that modeling is useless. But it must be taken into account in order to achieve successful transfer from simulation to reality. ALife research has addressed the reality gap problem in different ways, such as: \layout Itemize Using safety margins, as exemplified by the present work. \layout Itemize Evolving directly in reality, as in evolution in FPGA's \begin_inset LatexCommand \cite{thompson95} \end_inset or robot behaviors \begin_inset LatexCommand \cite{floreano94} \end_inset . \layout Itemize Evolving adaptable entities, as proposed by Di Paolo \begin_inset LatexCommand \cite{dipaolo00} \end_inset . \layout Itemize Use a hybrid model, first evolving in simulation, then transfer to reality to do a final round of adaptation, has been proposed by our group \begin_inset LatexCommand \cite{ices2000} \end_inset and implemented (for a game) in the two-layer evolutionary architecture of Tron (chapter \begin_inset LatexCommand \ref{chapter.tron} \end_inset ). \layout Standard We agree with Jakobi \begin_inset LatexCommand \cite{jakobi94,jakobi:97b} \end_inset in going for simulation at the right level, aiming at the aspects of reality that insure robust, transferable behaviors. We also think that the method of simulated evolution has inherent advantages in lieu of the reality gap problem: the dynamics of reproduction and selection subject to mutation lead evolving populations to explore fuzzy regions --- clouds within the solution space. \layout Standard Those organisms that, when mutated, are likely to be successful, have a reproductive advantage: their offspring is more likely to survive. This means that inasmuch as genotypical and phenotypical variation are linked, evolved solutions will have a tendency to being robust, in the sense that small variations in their constitution will not incapacitate them (more likely, they give rise to successful mutants). If this phenomenon is true, then solutions obtained by evolution implement ``by default'' a conservative principle based on kinship. This is an open research question. \layout Subsection Modular and Reconfigurable Robotics \layout Standard In our 1998 article \begin_inset LatexCommand \cite{funespollack98} \end_inset we proposed that this type of technique should be applied in ER to evolve the body and brain of a robot simultaneously. We thought that the modular approach should fit well with the research in modular robots, such as proposed by Yim \begin_inset LatexCommand \cite{yim95} \end_inset or Pamecha \begin_inset LatexCommand \cite{pamecha96} \end_inset . \layout Standard However, the first realization of fully coevolved body and behavior came two years later with Lipson and Pollack's crawlers \begin_inset LatexCommand \cite{lipson00} \end_inset . Instead of a modular parts approach, they use a continuously deformable architecture, employing a rapid-prototyping machine to build the evolved components on-the-fly (fig. \begin_inset LatexCommand \ref{fig.golem} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 416 290 file golem/arrow_halfres2.eps width 3 70.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Walking robot evolved by Lipson and Pollack]{ \latex default \begin_inset LatexCommand \label{fig.golem} \end_inset Walking robot evolved by Lipson and Pollack builds further on our paradigm of evolution of structure under buildability constraints, adding movement and control. \latex latex } \end_float \layout Subsection Movement Planning as Evolution? \layout Standard Evolutionary algorithms solve a problem by maintaining a population of variant partial solutions and applying recombination operators to them. Those operators can be considered valid, or available operations in a space of configurations. Our brick structures algorithms are solving problems of spatial arrangement, subject to buildability restrictions, starting from a known initial configurati on and advancing, one step at a time, by legal transformations. The simulation enforces that each step is physically correct. \layout Standard The implication is that the succession of genetic transformations that yield to a final stage can be considered a plan. Problems of planning for spatial arrangement are classic in AI \begin_inset LatexCommand \cite{fahlman74} \end_inset . One plausible future application of structural evolutionary algorithms is to adapt the recombination operations to reflect valid reconfigurations of a modular metamorphic robot. Problems of robot locomotion for example could be solved by evolving a plan for the desired final configuration from the starting one. \layout Standard We ran an exploratory experiment which evolves an imaginary amoeba-like creature made of Lego bricks (fig. \begin_inset LatexCommand \ref{fig.amoeba} \end_inset ). Once a goal state is obtained, the ``family tree'' from the initial to final configurations represents a sequence of valid transformations. \begin_float fig \layout Standard \align center \begin_inset Figure size 476 391 file crawlfig.eps width 3 80.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Evolution as Planning]{ \latex default \begin_inset LatexCommand \label{fig.amoeba} \end_inset An imaginary Lego creature evolves a plan to locomote between islands by expanding and contracting its body in \begin_inset Quotes eld \end_inset amoeba \begin_inset Quotes erd \end_inset fashion. Each step involves adding, deleting or sliding a limb, as induced by mutations. Recombination works as macro operator. \latex latex } \end_float \layout Standard The mutation operations are interpreted as the \begin_inset Quotes eld \end_inset valid actions \begin_inset Quotes erd \end_inset of the creature (i.e., extending, retracting or displacing limbs) and recombinati ons amount to macro operators, chaining a sequence of actions. \layout Subsection Cellular and Modularity-Sensitive Representations \layout Standard The problem of neural network representations for evolution of recurrent networks is similar to our problem of encoding brick structures. From early naive representations the concept of `developmental' or `cellular' grammatical encodings emerged \begin_inset LatexCommand \cite{belew90,kitano90,gruau92} \end_inset . They increase the efficiency of the GA by reducing the search space, eliminatin g redundancies and meaningless codes, and providing meaningful recombination operators. \layout Standard There is a developmental stage in our experiments, because the genotype builds a phenotype by laying down bricks one at at time, and fails whenever the position indicated is invalid, either because a previous brick is occupying that position already, is out of bounds, or the maximum numbers of bricks has been reached (see eqs. \begin_inset LatexCommand \ref{eq.invalid} \end_inset , \begin_inset LatexCommand \ref{eq.prunned} \end_inset and fig. \begin_inset LatexCommand \ref{fig.treexover} \end_inset ). Each failed brick results in the deletion of a subtree. \layout Standard An interesting alternative, never tested, would have been to delete illegal bricks from the phenotype but not the genotype, thus allowing for ghost limbs that could reappear later on. In any case, our representation has no means to represent subroutines or iterations other than interchanging genetic material via recombination. \layout Standard There have been studies of modularity in recurrent neural net representations \begin_inset LatexCommand \cite{gruau93,angeline94} \end_inset , aiming to improve the GA with automatic creation of libraries of reusable subcomponents. Structural representations should ultimately aim at the same objective: Finding useful complex blocks and incorporating them in the making of large structures with inherent modularities. Recent work by Hornby, et. al \begin_inset LatexCommand \cite{Hornby01} \end_inset utilizes an L-system generative representation to evolve walking virtual creatures. \layout Subsection Surprise in Design \layout Standard Instead of devising an expert system with rules about how to divide a task into subtasks, and how to carry along with each of those, a system like ours relies on more basic assumptions. The rules of physics, unlike the rules of design, are not an artificial creation, and this leads to original designs, because the evolutionary algorithm explores \emph on design space \emph default in ways which are not so strongly pre-determined by our culture. \layout Standard This is the reason why our evolved structures have an alien look, which prompted Ronald and Sipper to observe that they exemplify \begin_inset Quotes eld \end_inset surprising surprise, where we are totally and utterly taken aback \begin_inset Quotes erd \end_inset \begin_inset LatexCommand \cite[p. 525]{ronald00} \end_inset . According to them, these Lego artifacts lack the familiar look that helps us trust and use a structure produced by classic engineering. However, we see their comments as a strong encouragement, for among the most ambitious goals of AI is that of expanding the human mind by introducing new ways of thinking. We believe that useful inventions, no matter how weird they might look in the beginning, are eventually incorporated into the culture if they are useful. Just as today we trust our lives to an airplane (which at first glance seems utterly incapable of flight), tomorrow we may walk over bridges designed by ALife. \layout Subsection Conclusions \layout Standard In machine learning and artificial evolution systems, the more interesting results, such as Sims' creatures or expert Backgammon players, are due more to elements of the learning environment than to any sophistication in the learning algorithm itself \begin_inset LatexCommand \cite{tesauro95,pollackblair96} \end_inset . By keeping inductive biases and \emph on ad hoc \emph default ingredients to a minimum, we have demonstrated that interesting real-world behavior can come from a simple virtual model of physics and a basic adaptive algorithm. \layout Standard The use of modular building elements with predictable --- within an error margin --- properties allows evolutionary algorithms to manipulate physical entities in simulation in ways similar to what we have seen, for example, in the case of robot control software. The bits in our artificial chromosomes are not limited to codifying just bits; they are capable of representing the building blocks of an entire physical structure. \layout Standard We believe to have only scratched the surface of what is achievable. Combined with suitable simulators, the recombination of modular components guided by an artificial selection algorithm is a powerful framework capable of designing complete architectures ready to be built and used, discovering and exploiting complex properties of the substrate which are not identical to those explored by human engineers and designers. \layout Chapter \begin_inset LatexCommand \label{chapter.tron} \end_inset Coevolving Behavior with Live Creatures \layout Section Introduction \layout Standard In the 1966 movie classic \emph on Fantastic Voyage \emph default \begin_inset LatexCommand \cite{fantasticvoyage} \end_inset , a group of humans were shrunk and inserted inside a human body to cure a disease. Sixteen years later, \emph on Tron \emph default \begin_inset LatexCommand \cite{tron82} \end_inset shrunk film heroes into a new fantastic domain: \emph on the world inside the computer. \emph default This new pop icon sprang up from the massive impact that the 8-bit microprocess or had in our culture, bringing us personal computers and an explosion of arcade video games. \layout Standard Virtual worlds as studied by Artificial Life are inhabited by creatures that reproduce, learn and evolve --- with varying degrees of physical realism --- without human participation. For the virtual worlds of video games, instead, humans are invited but the emphasis is on the visual appeal: artificial opponents are present but they rely on access to the internal variables of the game more than artificial adaptation --- they are not artificial life beings. \layout Comment The need for credible dynamical action, however, means that true physical simulation is increasingly important, and those agents become more robot-like. \layout Standard Robots interact with physical reality and live creatures: they are \emph on embodied. \emph default But robotics research is difficult because the real world brings with it limitations of space, budget, engineering and speed. A video-game instead, is a simulated world where human intelligence can meet artificial adaptation, through the \emph on immersive \emph default experience of virtual reality. \layout Standard Here we posit that the science of Artificial Life should employ the metaphors of virtual realities and video games to attain knowledge about adaptive behavior, putting artificial agents in contact with live creatures, by introducing them into a simulated world. Virtual worlds could enable ALife researchers to study how artificial and natural intelligence coevolve, adapting to each other. Moreover, with the revolution of the Internet, these worlds can reach thousands of human subjects and artificial learning can arise from the combined contribut ions of many individuals. \layout Standard We present the first work that evolves agents by having them play against humans. The recreational nature of a simple video game attracts people and creates a niche for mutual adaptation between people and agents, providing the substrate for the first experience in learning a game through the massive training by thousands of human subjects. \layout Standard The physical features of our model are limited to the simulation of a two-dimens ional space with walls; but they are sufficient to observe the emergence of navigational behaviors such as wall following and obstacle avoidance. \layout Comment We have taken a dual inspiration from Walt Disney's Tron: the \emph on light cycles \emph default game we use as a model, and the idea that fascinating things may happen when the hero challenges the autonomous creatures created by the \begin_inset Quotes eld \end_inset Master Control Program \begin_inset Quotes erd \end_inset . \layout Standard Parts of this research have been reported on the following publications: \begin_inset LatexCommand \cite{funesetal98,funessab98,funessab00,sklar99} \end_inset . \layout Section Background and Related Work \layout Subsection Coevolution \layout Standard In nature, organisms and species coexist in an ecosystem; each species has its own place or \emph on niche \emph default in the system. The environment contains a limited number and amount of resources, and the various species must compete for access to those resources. Through these interactions, species grow and change, each influencing the others' evolutionary development. This process of reciprocal adaptation is known as coevolution. \layout Standard In evolutionary computation, the term ``coevolution'' has been used to describe any iterated adaptation involving ``arms races'', either between learning species or between a learner and its learning environment. Examples of coevolutionary learning include the pioneering work by Hillis on sorting networks \begin_inset LatexCommand \cite{hillis91} \end_inset , Backgammon learning \begin_inset LatexCommand \cite{tesauro92, pollackblair96, pollackblair97} \end_inset , predator/prey games \begin_inset LatexCommand \cite{reynolds94, miller94, miller96} \end_inset and spatial distribution problems \begin_inset LatexCommand \cite{juille96,juille96b} \end_inset . The present work extends the coevolution paradigm to include the case where the changing environment results from the adaptive behavior of a heterogeneous population of human beings. \layout Comment In its most general sense, any moving target situation, where the fitness of an individual changes with external factors, is considered a form of coevolution. \layout Subsection Too Many Fitness Evaluations \layout Standard The need to evaluate the fitness of a large number of individuals is a critical factor that restricts the range of application of GA's. In many domains, a computer can do these evaluations very fast; but in others, the time spent by this process may render the GA solution impractical. Examples of the latter case include a computer playing a game with people and trying to learn from experience or a robot attempting to complete a task in the physical world. \layout Standard Robots that are reliable enough can run repeated trials of the same experiment over a long time in order to learn using evolutionary computation techniques. Floreano and Mondada \begin_inset LatexCommand \cite{floreano94,floreano96} \end_inset run their robots for several days in order to evolve controllers for basic tasks. Most evolutionary roboticists have preferred to rely on computer simulations to provide them with faster evaluations, but the crafting of appropriate simulators is also very difficult \begin_inset LatexCommand \cite{mataric96} \end_inset . \layout Standard Evolution through interaction with humans faces similar difficulties. ``Blind watchmaker'' systems, where the user ranks every generation manually, have been successfully used to evolve shapes \begin_inset LatexCommand \cite{dawkins87,sims91} \end_inset ; even with the extreme limitations imposed by the need to evaluate each individual manually (minimal population sizes, small number of generations) those results prove the great potential of evolution in a human-generated landscape. \layout Standard But with a human in the loop, it is impossible to attain the large numbers of generations and evaluations employed in evolutionary experiments. Humans --- unlike robots --- get tired of repetitive tasks. Moreover, humans act irregularly; they may react differently each time when faced with the same situation more than once. If users provide fitness evaluations, adaptive software would need to be able to filter out such sources of ``noise'' provided naturally by human users. \layout Standard We believe that the Internet, with millions of human users, could be fertile ground for the evolution of interactive adaptive software. Instead of relying on a few selected testers, the whole community of users together constitutes a viable gauge of fitness for an evolutionary algorithm that is searching to optimize its behavior. \layout Comment The problem of generalization \layout Comment Given that it is an arduous task to evaluate fitness for multitudes of individua ls, one might ask: is it possible to limit the search to just a few? The problem of lack of generalization or lack of transfer to a more general environment defeats this idea. The fact that an algorithm performs well in a certain group of test cases does not usually mean that it will generalize to a wider range of situations. \layout Comment Neural networks are thought to have generalization capabilities \begin_inset LatexCommand \cite{wolpert90,darwen96} \end_inset , successfully inducing, for example, a good Backgammon player from a set of suggested moves \begin_inset LatexCommand \cite{tesauro90} \end_inset . Supporters of the Genetic Programming (GP) paradigm \begin_inset LatexCommand \cite{koza92} \end_inset suggest that this may be the case for GP as well \begin_inset LatexCommand \cite{rosca96} \end_inset . In \latex latex \begin_inset LatexCommand \cite{juille96b} \end_inset \latex default , \latex latex Juill \backslash 'e \latex default and Pollack argue that the dynamics of coevolutionary fitness help to get ``perspicacious'' solutions to a problem of recognizing 194 points arranged in a spiral pattern. The GP function they obtain indeed defines two roughly spiral surfaces that continue outside the boundary of the original test points. \layout Subsection Learning to Play Games \layout Comment Game playing is a classical problem domain for Machine Learning, where important results have been obtained on learning from human trainers \begin_inset LatexCommand \cite{samuel59,samuel67,epstein94} \end_inset , and encyclopedias of games \begin_inset LatexCommand \cite{tesauro89} \end_inset , as well as learning through self-play \begin_inset LatexCommand \cite{tesauro95,pollack98,fogel00} \end_inset . Artificial players obtained by these methods, however, often fail against human players, who can quickly adapt to them. Ever since Samuel's early experiments with checkers \begin_inset LatexCommand \cite{samuel59} \end_inset , we have hoped that the computer would be able to make good use of experience, improving its skills by learning from its mistakes and successes. \layout Comment Tron is the first game learning system that continuously adapts to a large population of humans. Playing a real time video game against people on the Internet, our artificial opponent has improved from a mediocre starting player to become a top 5% competitor. This player is actually composed of an evolving population of ``robots'' (i.e., software agents), each one embodying a different strategy. Learning is driven by selection and reproduction of these agents based on their success against humanity. We show that learning occurred in humans as well, resulting in a feedback loop of increased challenges. We posit that the continued interaction between human learner and machine learner has created a ``virtual niche'' for reciprocal adaptation, where natural and artificial intelligences coevolve. \layout Subsubsection Self-Play or Play against People? \layout Standard A machine that learns by playing games may acquire knowledge either from external expertise (playing with a human or human-programmed trainer), or by engaging in \emph on self-play \emph default . \layout Comment \color red In his work with the game of Backgammon, Tesauro began collecting samples from human games to provide a fitness measure for training neural networks \begin_inset LatexCommand \cite{tesauro90} \end_inset . Later, he abandoned this methodology and used introspective \emph on self-play \emph default \begin_inset LatexCommand \cite{tesauro95} \end_inset . Of the earlier approach, he argued that ``building human expertise into an evaluation function [...] has been found to be an extraordinarily difficult undertaking'' (p. 59). \layout Standard Tesauro \begin_inset LatexCommand \cite{tesauro92} \end_inset was able to obtain strong Backgammon players, having one neural network play itself and adjusting the weights with a variant of Sutton's TD algorithm \begin_inset LatexCommand \cite{sutton88} \end_inset . Although it worked for Backgammon, self-play has failed on other domains. Our group obtained similar results to those of Tesauro using hill-climbing, a much simpler algorithm \begin_inset LatexCommand \cite{pollack98} \end_inset . This demonstrated that elements unique to Backgammon, more than the TD method, enable learning to succeed. Self-play remains an attractive idea because no external experience is required. In most cases, however, the learning agent explores a narrow portion of the problem domain and fails to generalize to the game as humans perceive it. \layout Standard Attaining knowledge from human experience has proven to be difficult as well. Today's algorithms would require millions of games, hence rendering training against a live human impossible in practice. Programmed trainers have also led to the exploration of an insufficient subset of the game space: Tesauro \begin_inset LatexCommand \cite{tesauro90} \end_inset tried to learn Backgammon using human knowledge through a database of human expert examples, but self-play yielded better results. Angeline and Pollack \begin_inset LatexCommand \cite{angelinepollack93} \end_inset showed how a genetic program that learned to play tic-tac-toe against several fixed heuristic players was outperformed by the winner in a self-playing population. Most of today's expert computer players are programmed by humans; some employ no learning at all \begin_inset LatexCommand \cite{newborn96} \end_inset and some use it during a final stage to fine-tune a few internal parameters \begin_inset LatexCommand \cite{baxteretal98} \end_inset . A recent exception is Fogel's checkers player \begin_inset LatexCommand \cite{fogel00} \end_inset , which achieved a ``Class A'' rating by coevolutionary self-play alone. \layout Comment Learning to play a game by self-play involves a problem of generalization, or ``transfer'' as well. The fitness landscape (even in the coevolutionary case, where the ``landscape'' is redefined in every generation) might be an insufficient sample of the larger problem defined by the whole game and the way humans approach it. While learning Backgammon \begin_inset LatexCommand \cite{tesauro95, pollackblair96} \end_inset is a success for coevolution, the same approach has failed in most other cases. \layout Standard Real-time, interactive games (e.g. video games) have distinctive features that differentiate them from board games. Koza \begin_inset LatexCommand \cite{koza92} \end_inset and others \begin_inset LatexCommand \cite{rosca96} \end_inset evolved players for the game of Pacman. There has been important research in pursuer-evader games \begin_inset LatexCommand \cite{reynolds94,miller94,miller96} \end_inset as well as contests in simulated physics environments \begin_inset LatexCommand \cite{sims94} \end_inset . But these games do not have human participants, as their environments are either provided by the game itself, or emerge from coevolutionary interactions inside a population of agents. \layout Subsection Intelligence on the Web \layout Subsubsection \begin_inset LatexCommand \label{niche} \end_inset A space where agents can thrive and evolve \layout Standard It has been suggested that intelligence should be present on Internet sites in the form of intelligent agents. According to this hypothesis, such environments will contain software agents that interact with human users and adapt according to the behavior displayed in those interactions \begin_inset LatexCommand \cite{lieberman97} \end_inset . \layout Standard With Tron we are exploring the hypothesis that one of the forms in which this idea may be realized is through the presence of species of agents evolving through their interactions with the rest of the web. From this perspective, the Internet is seen as a complex environment with virtual niches inhabited by adaptive agents. \layout Standard Here we propose that learning complex behaviors can be achieved in a coevolution ary environment where one population consists of the human users of an interacti ve software tool and the ``opposing'' population is artificial, generated by a coevolutionary learning engine. A niche must be created in order for the arms race phenomenon to take place, requiring that: \layout Enumerate A sufficiently large number of potential human users must exist. \layout Enumerate The artificial population must provide a useful environment for the human users, even when --- in the early stages --- many instances perform poorly. \layout Enumerate An evaluation of the performance of the artificial population must be measurable from its interaction with the human users. \layout Standard The experimental learning environment we created for the game Tron met these requirements. First, the game is played in a Java applet window on our web site. As Tron was being launched, Java was a new thing and there was a great interest on any applications, particularly games. So by advertising our site in Java games lists we were able to attract visitors. Second, our earlier experiments with Tron had shown us that, by self-play, we could produce players that were not entirely uninteresting when faced by humans. And third, each round of Tron results in a performance measure: a win, a loss or (rarely) a tie. \layout Comment In our case, the bi-adaptive relationship between human users and artificial agents could be considered a form of mutualism \begin_inset LatexCommand \cite{gilbert75} \end_inset , as both humans and agents participating have their own goals and adaptation strategies. Both being adaptive species, this relationship between software agents and human users implies coadaptation of both species. \layout Comment From the point of view of the learning agent species, the human environment is very noisy and adapts very fast. The evolutionary process finds its way through this noise as the better agents are being selected, slowly but surely. The motivations in this case are very simple, as rewards come from the fitness function we programmed. \layout Comment People have reasons for participating that are much more complex. Fun, curiosity, competition against an unfamiliar intelligence, and competition against each other to appear in the `ranking' page are among them. The evolutionary properties of the animat population create a changing artificial environment that makes people come back searching for a renewed challenge. \layout Section Experimental Model \layout Subsection \color black Tron Light Cycles \layout Standard Tron is a popular video game that has been implemented in arcades and PC's with different rule variations. \color black It is based upon a segment of the movie \emph on Tron \emph default \begin_inset LatexCommand \cite{tron82} \end_inset \emph on , \emph default where the characters rode \emph on Light Cycles \emph default , \color default futuristic motorcycles that leave a solid trail behind them (fig. \begin_inset LatexCommand \ref{light cyles} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 357 342 file sab98/graph/lgtccl1.eps width 3 60.00 flags 11 \end_inset \layout Caption \emph on \begin_inset LatexCommand \label{light cyles} \end_inset Light Cycles. \emph default Still from the movie \emph on Tron. \end_float \layout Standard The Tron-Light Cycles game is a contest between opponents who move at constant, identical speeds, erecting walls wherever they pass and turning only at right angles. As the game advances, the 2D game arena progressively fills with walls and eventually one opponent crashes, losing the game. \layout Standard Tron requires quick reactions and spatial-topological reasoning at the same time. In our version, the two players (one human, one agent) start in the middle region of the screen, moving in the same direction. The edges are not considered ``walls''; players move past them and reappear on the opposite side, thus creating a toroidal game arena. The size of the arena is 256 \begin_inset Formula \( \times \) \end_inset 256 pixels. \layout Standard Fig. \begin_inset LatexCommand \ref{applet} \end_inset shows the Java version of our Tron game, running inside an Internet browser application. A Java agent is constrained by the Java Virtual Machine of the browser, an environment very limited in speed and resources. At the time when our experiment was conceived, Java was a new technology and only small, simple programs would run reliably on commercial web browsers. The minimalistic memory, CPU and graphics requirements of Tron made it an ideal choice for the experiment. \begin_float fig \layout Standard \align center \begin_inset Figure size 382 547 file sab00/graph/avoider6.eps height 3 65.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[The Tron page]{ \latex default \begin_inset LatexCommand \label{applet} \end_inset The Tron page: Tron runs as an applet inside an Internet browser. Arrows have been added to indicate direction of movement, and dotted lines to show the sensors of an artificial agent. \latex latex } \end_float \layout Subsubsection Initial Experiment \layout Standard In exploratory experiments \begin_inset LatexCommand \cite{funes96} \end_inset , we used a Genetic Algorithm to learn the weights of a perceptron network that played Tron. We found that simple agents played interestingly, but also that coevolution may not always lead to robust strategies. \emph on Collusion \emph default \begin_inset LatexCommand \cite{pollackblair97} \end_inset was likely to appear in the form of ``live and let live'' strategies such as the one shown in figure \begin_inset LatexCommand \ref{collusion} \end_inset , where agents avoid confrontation and \begin_inset Quotes eld \end_inset agree \begin_inset Quotes erd \end_inset to tie, splitting the point. \begin_float fig \layout Standard \align center \begin_inset Figure size 357 357 file sab98/graph/square.eps width 3 60.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Live and let live]{ \latex default \begin_inset LatexCommand \label{collusion} \end_inset Live and let live: Two artificial Tron players make tight spirals in order to stay as far from the opponent as possible. This form of collusion is a frequent suboptimal equilibrium that complicates artificial learning through self-play. \latex latex } \end_float \layout Subsection System Architecture \layout Standard Tron is implemented as a client/sever application with three main components (fig. \begin_inset LatexCommand \ref{foreback} \end_inset ), \layout Itemize \emph on Java Front End \emph default . A Java applet that runs on web browsers, playing Tron between a human and an agent. \layout Itemize \emph on Main (Foreground) Server. \emph default An Internet web server and SQL database that hosts a population of Tron agents, evolving it against humanity. This server records all games played, computes fitness and decides which agents live and die. \layout Itemize \emph on Novelty (Background) Engine. \emph default An application that evolves Tron agents by self-play. It sends new agents to the Foreground Server whenever they are needed, and receives veteran champions to be used as fitness measures and/or seeds for a new population. \begin_float fig \layout Standard \align center \begin_inset Figure size 535 214 file sab00/graph/scheme4.eps width 3 90.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Scheme of information flow]{ \latex default \begin_inset LatexCommand \label{foreback} \end_inset Scheme of information flow. Agents travel to users' computers to play games. Those with poorest performances are eliminated. A novelty engine creates new players. The better ones are added to the population, filling the empty slots. \latex latex } \end_float \layout Subsection \begin_inset LatexCommand \label{sec.trongp} \end_inset Tron Agents \layout Standard Tron agents perceive the world through sensors that evaluate the distance in pixels from the current position to the nearest obstacle in eight relative directions: front, back, left, right, front left, front right, back left and back right. Every sensor returns a maximum value of 1 for an immediate obstacle, a lower number for an obstacle further away, and 0 when there are no walls in sight (figs. \begin_inset LatexCommand \ref{fig.8sensors} \end_inset and \begin_inset LatexCommand \ref{applet} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 238 326 file graph/sensors.eps width 3 40.00 flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{fig.8sensors} \end_inset A Tron agent perceives the environment through eight distance sensors. \end_float \layout Standard Each agent or ``robot'' is a small program, representing one Tron strategy, coded as a Genetic Programming (GP) s-expression \begin_inset LatexCommand \cite{koza92} \end_inset , with terminals {A, B, \begin_inset Formula \( \ldots \) \end_inset , H (the eight sensors) and \begin_inset Formula \( \Re \) \end_inset (random constants between 0 and 1)}, functions {+, -, * (arithmetic operations) ,% (safe division), IFLTE (if\SpecialChar ~ less\SpecialChar ~ or\SpecialChar ~ equal-then-else), RIGHT (turn right) and LEFT (turn left)}, maximum depth of 7 and maximum size of 512 tokens. An agent reads its sensors and evaluates its s-expression every third time step: if a RIGHT or LEFT function is output, the agent makes the corresponding turn; otherwise, it will keep going straight. \layout Standard The simple sensory capabilities imply that an agent's view of the game is quite restricted: the position of the opponent is unknown, and so is the complete view of the game situation. \layout Standard Tron agents have no state variables, so the behavior of the agent is purely reactive, based solely on 7 distance sensors \begin_float footnote \layout Standard Sensor \begin_inset Quotes eld \end_inset E \begin_inset Quotes erd \end_inset , which point backwards, sees the agent's own trace as an immediate obstacle, so it always returns 1.0. \end_float . Whereas humans may base their game decisions on topological considerations (e.g. ``is this region open or closed?'' \emph on ) \emph default , or follow plans, the complexities of a robot's behavior must emerge from the interaction with the opponent along the game. \layout Subsection \color black Java Applet \layout Standard When a visitor opens the Tron web page \begin_float footnote \layout Standard \color blue http://www.demo.cs.brandeis.edu/tron \end_float , her browser loads and starts a Java applet. The applet (fig. \begin_inset LatexCommand \ref{applet} \end_inset ) receives the GP code for an agent from our web server and uses it to play one game with the human user. The human moves by pressing the arrow keys and the agent, by evaluating its s-expression. When the game ends, the applet reports the result (win or loss) to the server, and receives a new agent for the next game. This cycle continues until the human stops playing. \layout Standard Our Java Tron application consists of three modules: the \emph on Arena \emph default updates players position and direction, and their traces, updating the display; the \emph on Human Player \emph default module listens to keystrokes and changes the Human's orientation accordingly; a \emph on GP Player \emph default module computes sensor values and feeds them to a GP interpreter that evaluates an agent's s-expression. This module contacts the server over the web, receiving GP code and sending back game results. \layout Subsection Evolving Agents: The Tron Server \layout Standard The Tron system maintains a population of 100 ``live'' agents on the foreground server. For each game, an agent is drawn at random from it. The game results are stored in a database. A generation lasts until all 100 agents have played a minimum number of games: new agents play at least 10 games, while veterans from previous generations play only 5 games. \layout Standard With a proportion of 90 veteran agents and 10 rookies on the population, a generation consists of approximately 450 games by veterans and 100 by novices, thus untested agents play about 18% of all games \emph on . \layout Standard When all agents have completed their minimum number of games, the current generation finishes: agents are sorted by fitness; the worst 10 are eliminated and replaced by 10 fresh ones, supplied by a the \emph on novelty engine \emph default . A new generation begins (fig. \begin_inset LatexCommand \ref{foreback} \end_inset ). \layout Subsubsection \begin_inset LatexCommand \label{sec.pseudofore} \end_inset Pseudocode of the foreground Tron server \layout LaTeX { \backslash onehalfspacing \layout Enumerate \family typewriter \size small Start with an agent population \begin_inset Formula \( A \) \end_inset of 100 robots. \layout Enumerate \family typewriter \size small For each \begin_inset Formula \( a\in A \) \end_inset let \begin_inset Formula \( c_{a}=0 \) \end_inset \layout Enumerate \family typewriter \size small (Loop) \newline While \begin_inset Formula \( \min \{c_{a},a\in A\}<10 \) \end_inset , wait for events: \begin_deeper \begin_deeper \layout Enumerate \family typewriter \size small On event that a Java applet requests a game over the Internet, \newline Select an agent \begin_inset Formula \( a\in A \) \end_inset with probability \begin_inset Formula \[ P(a)=\frac{w(a)}{\sum w(x),x\in A},\, w(a)=\max \{1,10-c_{a}\}\] \end_inset and send it to the applet. \layout Enumerate \family typewriter \size small On event that an applet reports the results of a game between human \begin_inset Formula \( h \) \end_inset and agent \begin_inset Formula \( a \) \end_inset , \newline Save in database: \newline Game result (win, tie, or lose); human id, agent id, time stamp, and list of moves. \newline If \begin_inset Formula \( a\in A \) \end_inset then let \begin_inset Formula \( c_{a}=c_{a}+1 \) \end_inset \end_deeper \end_deeper \layout Enumerate \family typewriter \size small \begin_inset LatexCommand \label{sort.fit} \end_inset Sort \begin_inset Formula \( A \) \end_inset according to fitness, \begin_inset Formula \( A=a_{1},\ldots ,a_{100}, \) \end_inset and let \begin_inset Formula \( V=a_{1},\ldots ,a_{90} \) \end_inset \layout Enumerate \family typewriter \size small Fetch 10 new agents from novelty engine and call them \begin_inset Formula \( R \) \end_inset \layout Enumerate \family typewriter \size small For each \begin_inset Formula \( a\in V \) \end_inset let \begin_inset Formula \( c_{a}=5. \) \end_inset \newline For each \begin_inset Formula \( a\in R \) \end_inset let \begin_inset Formula \( c_{a}=0 \) \end_inset \newline Let \begin_inset Formula \( A=V\cup R \) \end_inset \layout Enumerate \family typewriter \size small Go to (Loop) \layout LaTeX } \layout Subsection Fitness Function \layout Standard Defining an appropriate fitness measure to rank our agents has proven difficult. In principle we defined a variant of fitness sharing \begin_inset LatexCommand \cite{beasleyetal93} \end_inset by giving points for doing better than average against a human player, and negative points for doing worse than average. The fitness of agent \emph on a \emph default was defined as: \begin_inset Formula \begin{equation} \label{fitness} F(a)=\sum _{\{h:p(h,a)>0\}}\left( \frac{s(h,a)}{p(h,a)}-\frac{s(h)}{p(h)}\right) \left( 1-e^{\frac{p(h)}{10}}\right) \end{equation} \end_inset \layout Standard where \emph on s \emph default ( \emph on h,a \emph default ) is the number of games lost minus the number of games won ( \emph on score) \emph default by a human opponent \emph on h \emph default against \emph on a \emph default ; \emph on p \emph default ( \emph on h,a \emph default ) is the total number of games between the two; \emph on s \emph default ( \emph on h \emph default ) is the total score of \emph on h \emph default ; and \emph on p \emph default ( \emph on h) \emph default is the number of games that \emph on h \emph default has played. All games played are counted, not just those that belong to the current generation. The factor \begin_inset Formula \( \left( 1-e^{\frac{p(h)}{10}}\right) \) \end_inset is a confidence measure that devalues the average scores obtained against humans who have played only a small number of games. \layout Standard A second part of the experiment assayed a new definition of fitness, based on our statistical analysis of players' strengths. This problem is discussed in detail in section \begin_inset LatexCommand \ref{sec.aftermath} \end_inset . \layout Subsection \begin_inset LatexCommand \label{sec.noveltyengine} \end_inset Novelty Engine \layout Standard Evolutionary algorithms create new entities and evaluate their fitness, introducing variations on the existing population through the use of crossover \emph on \emph default and \emph on \emph default mutation operators. Such recombinations often yield uninteresting individuals, identical to or worse than their parents. Typically, evaluations are rapid and unfit children are quickly filtered out. However, in our case, this approach would be wasteful since evaluation is obtained from a sparse resource --- precious interactions between agents and humans. \layout Standard The Tron architecture uses a separate \emph on novelty engine \emph default as the source of new individuals. This module coevolves a population of 1000 agents by playing them against each other. The best robots are chosen to be incorporated into the main population. Even though self-play does not provide enough information to know which strategies will perform best against people, this method is much better than blind recombination for creating interesting new agents. \layout Standard The novelty engine is a continuously running generational GA with 50% elitism. Every agent in the population plays against a training set \emph on T \emph default of \begin_inset Formula \( t=25 \) \end_inset robots. Fitness is evaluated, and the bottom half of the population is replaced by random mating with crossover of the best half. The fitness function is defined as follows: \begin_inset Formula \begin{equation} \label{nov.fit} F_{T}(a)=\sum _{\{a'\in T:pt(a,a')>0\}}\frac{pt(a,a')}{l(a')} \end{equation} \end_inset \layout Standard where \emph on T \emph default is the training set, \emph on pt \emph default ( \emph on a, a' \emph default ) = {0 if \emph on a \emph default loses against \emph on a' \emph default , 0.5 if they tie and 1 if \emph on a \emph default wins} and \emph on l \emph default ( \emph on a' \emph default ) is the number of games lost by \emph on a' \emph default . Thus we give more points for defeating good players than bad players. \layout Standard The training set consists of two parts. There are \begin_inset Formula \( f \) \end_inset fixed members which come from the foreground process. The remaining \begin_inset Formula \( t-f \) \end_inset members of the training set are replaced each generation with a fitness sharing criteria. The new training set \emph on T' \emph default is initialized to the empty set and then new members are added one at a time, choosing the highest according to the following shared fitness function: \begin_inset Formula \begin{equation} \label{training.set} F_{T,T'}(a)=\sum _{a'\in T}\frac{pt(a,a')}{(1+\sum _{a''\in T}pt(a'',a)} \end{equation} \end_inset \layout Standard This selection function, adapted from Rosin \begin_inset LatexCommand \cite{rosin97} \end_inset , decreases the relevance of a case that has already been ``covered'', that is, when there is already a player in the training set that beats it. \layout Standard At the end of a generation, the bottom half of the population is dropped, and so is the (changing) part of the training set. 500 new agents are created by (uniform) random mating (crossover), with a mutation rate of 0.04 (a parent's subexpression has a 4% chance of being replaced by a random new expression instead). \layout Subsubsection Feedback from Main Population to Novelty Engine \layout Standard With the main population/novelty engine setup, the idle time --- while the system is patiently waiting for human games to come in \begin_float footnote \layout Standard Averaging 100 thousand games per year (0.2 per minute), the pace of human-agent interaction is between 3 and 4 orders of magnitude slower than our C code, capable of playing about 1000 games per minute. \end_float --- is devoted to the fabrication of the best opponents we can come up with. \layout Standard It is expected that an evolutionary algorithm should increase the quality of the new entities with every each generation. If there was no feedback from the front end back to the novelty engine, the latter would remain oblivious to the information being collected by the selective process acting on the foreground. We have proposed and implemented two ways for surviving agents to come back and reproduce in the novelty engine. \layout Enumerate \emph on Using them as trainers. \emph default A reasonable setting for coevolving Tron agents by self-play alone would have \begin_inset Formula \( f=0. \) \end_inset By setting \begin_inset Formula \( f=15 \) \end_inset , some of the champions-against-people come back to the novelty engine to act as trainers. The hope is that, by transference, new agents are favored which are themselves good against people. \layout Enumerate \emph on Reintroducing them in the population. \emph default Successful agents can be simply reintroduced in the population to let them compete with the other coevolving robots and reproduce, provided they are successful against their peers. \layout Subsubsection \begin_inset LatexCommand \label{novelty.parameters} \end_inset Tunable Parameters \layout Standard The novelty engine has three parameters that have changed at different points in the experiment. \layout Itemize MAXGEN. Every time the foreground server ends a generation, it fetches ten new rookies, the current champions-vs.-robots, to become part of the main population. To avoid the effects of convergence, which could lead to the same agents being sent repeatedly, the background population is restarted every once in a while. The novelty engine checks the number of generations \emph on g \emph default that the present population has been evolving for. If \emph on g \emph default > MAXGEN, then the present population is killed and evolution starts with a fresh random population. \layout Itemize \emph on f \emph default . When the novelty engine restarts, it fetches \emph on f \emph default new agents from the foreground that become the fixed part of the training set. \layout Itemize SEED. This is a boolean parameter. Upon restart of the coevolutionary run, either 1000 new random agents are created or, if SEED is true, the current 100 champions-against-people are reintroduced along with 900 random ones --- the foreground population is used as a seed for the background. \layout Subsubsection Pseudocode of the Novelty Engine \layout LaTeX { \backslash onehalfspacing \layout Enumerate \family typewriter \size small (Reset) \newline Create a population \begin_inset Formula \( P=\{p_{1},\ldots ,p_{1000}\} \) \end_inset of random robots \newline and a random training set \begin_inset Formula \( T_{2} \) \end_inset of \begin_inset Formula \( t-f \) \end_inset agents. \layout Enumerate \family typewriter \size small (Seed) \newline If option SEED is true, \begin_deeper \layout Enumerate \family typewriter \size small fetch 100 best from main population \layout Enumerate \family typewriter \size small replace \begin_inset Formula \( \{p_{901},\ldots ,p_{1000}\} \) \end_inset with them \end_deeper \layout Enumerate \family typewriter \size small (Refetch) \newline Fetch \begin_inset Formula \( f \) \end_inset best agents from the main server \newline and call this group \begin_inset Formula \( T_{1} \) \end_inset \layout Enumerate \family typewriter \size small Let \begin_inset Formula \( g=0 \) \end_inset \layout Enumerate \family typewriter \size small Repeat forever \begin_deeper \layout Enumerate \family typewriter \size small Let \begin_inset Formula \( T=T_{1}\cup T_{2} \) \end_inset \layout Enumerate \family typewriter \size small Play each \begin_inset Formula \( a\in P \) \end_inset against each \begin_inset Formula \( a'\in T \) \end_inset \layout Enumerate \family typewriter \size small Sort \begin_inset Formula \( P=\{p_{1},\ldots ,p_{1000}\} \) \end_inset according to eq. ( \begin_inset LatexCommand \ref{nov.fit} \end_inset ) \layout Enumerate \family typewriter \size small For \begin_inset Formula \( i=1 \) \end_inset to \begin_inset Formula \( 500 \) \end_inset \newline Select random \begin_inset Formula \( a_{1},\, a_{2}\in \{p_{1},\ldots ,p_{500}\} \) \end_inset and \newline replace \begin_inset Formula \( p_{i+500} \) \end_inset with a random crossover of \begin_inset Formula \( a_{1} \) \end_inset and \begin_inset Formula \( a_{2} \) \end_inset \layout Enumerate \family typewriter \size small Let \begin_inset Formula \( T'=\varnothing \) \end_inset , then for \begin_inset Formula \( i=1 \) \end_inset to \begin_inset Formula \( t-f \) \end_inset \newline add a new agent to \begin_inset Formula \( T' \) \end_inset by eq. ( \begin_inset LatexCommand \ref{training.set} \end_inset ). \newline Let \begin_inset Formula \( T_{2}=T' \) \end_inset \layout Enumerate \family typewriter \size small Let \begin_inset Formula \( g=g+1 \) \end_inset \layout Enumerate \family typewriter \size small If the main population has finished a new generation, then \begin_deeper \layout Enumerate \family typewriter \size small Send \begin_inset Formula \( \{p_{1},\ldots ,p_{10}\} \) \end_inset to main population as next group of rookies \layout Enumerate \family typewriter \size small If \begin_inset Formula \( g>\text {MAXGEN} \) \end_inset then go to (Reset) else goto (Refetch) \end_deeper \end_deeper \layout LaTeX } \layout Section \begin_inset LatexCommand \label{sec.results} \end_inset Results \layout Standard Our server has been operational since September 1997; we have collected the results of all games between agents and humans; the system is still running. The results presented in this section are based on the first 525 days of data (204,093 games). A total 4037 human players and 3512 agent players have participated, each of them having faced just some of all potential opponents (fig. \begin_inset LatexCommand \ref{f.whowhom} \end_inset ). The ``aftermath'' section ( \begin_inset LatexCommand \ref{sec.aftermath} \end_inset ) discusses a new configuration of the system and the results obtained with it. \begin_float fig \layout Standard \align center \begin_inset Figure size 577 432 file sab00/graph/ts2f10.eps width 3 97.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Who has played whom]{ \latex default \begin_inset LatexCommand \label{f.whowhom} \end_inset Who has played whom: A dot marks every human-robot pair who have played each other at least once. Both populations are sorted by the date of their first appearance. The long vertical lines correspond to robots that have been part of the population for a long time, and thus have played against most newcomers. \latex latex } \end_float \layout Subsection \color black \begin_inset LatexCommand \label{sec.winrate} \end_inset Win Rate (WR) \layout Standard An intuitive performance measure is the \emph on win rate \emph default (WR), which is the fraction of games that the artificial players win; \begin_inset Formula \begin{equation} \label{eq.WR} \text {WR}=\frac{\text {games\, won}}{\text {games\, played}} \end{equation} \end_inset \layout Standard The average win rate over the total number of games played is 0.55, meaning that 55% of all games completed resulted in agent victories. \layout Standard The WR has been changing over time (fig. \begin_inset LatexCommand \ref{f.winrate} \end_inset ), in an oscillating fashion. This noisy behavior is a natural phenomenon in a coevolutionary environment, and occurs here more noticeably since one of the evolving populations consists of random human players. Each of the 4037 persons sampled here has a different level of expertise and has played a different number of games (another variable factor is the speed of the game on the user's machine, which may have a slower pace when the Java environment is too slow \begin_float footnote \layout Standard Our Java Tron uses a millisecond sleep instruction to pace the game, but different implementations of the Java Virtual Engine, on different browsers, seem to interpret it with dissimilar accuracies. The effect is more noticeable on machines with slow CPUs and old browsers. \end_float ). \begin_float fig \layout Standard \align center \begin_inset Figure size 416 328 file newfit/ts2f09.eps width 3 70.00 flags 3 \end_inset \layout Standard \latex latex \backslash caption[Evolution of the win rate]{ \latex default \begin_inset LatexCommand \label{f.winrate} \end_inset Evolution of the win rate: \emph on \emph default WR sampled in groups of 1000 games. \latex latex } \end_float \layout Standard There is a visible trend toward improvement. Whereas at the beginning of our experiment, the Tron system won about 30% of its games, by the end of the period it wins about 80% of its games. This is a strong indication of the improvement of the system's performance. \layout Standard An increasing WR could be hiding other phenomena besides improvement in the quality of game of the Tron system. Humans could be playing worse now than before, for example, for whatever the reasons; or novices could be dominating the human population and playing the bulk of games. In the next section we describe a statistical technique that yields a much finer measure, avoiding the pitfalls of WR. \layout Subsection \begin_inset LatexCommand \label{sec.joe90} \end_inset Statistical Relative Strength (RS) \layout Standard To further analyze performance and learning within the Tron system, we employ a paired-comparisons maximum likelihood model. \layout Standard Paired comparisons models are statistical methods that estimate the relative strengths or preferences of a group of participants. The ``Elo ratings \begin_inset Quotes erd \end_inset for Chess, conceived by A. Elo \begin_inset LatexCommand \cite{elo86} \end_inset are one example of such method. Chess poses some problems akin to ours, as one would like to ask, say, ``was Capablanca better than Fisher?'' Even if the two players did play each other, one might not have been at the peak of his abilities at the time. All the information from opponents they played in common, and how well they performed, should be put together. We have followed the maximum likelihood approach described by Joe \begin_inset LatexCommand \cite{joe90} \end_inset , applied by the author to the Chess problem among others. \layout Standard Elo's model --- used today for many other games, including the so-called ``game ladders'' --- assigns a low ranking to a novice, who can slowly climb up as she wins games against other ranked players. Maximum likelihood statistics such as Joe's are better suited to our problem because they compute the most feasible ranking for all players, without presuming that young ones are bad. \layout Subsubsection Paired Comparisons Analysis \layout Standard The goal of paired comparison statistics is to deduce a ranking from an uneven matrix of observed results, from which the contestants can be sorted from best to worst. In the knowledge that crushing all the complexities of the situation into just one number is a large simplification, one wishes to have the best one-dimensional explanation of the data. \layout Standard Each game between two players ( \emph on P \begin_inset Formula \( _{i} \) \end_inset , P \begin_inset Formula \( _{j} \) \end_inset \emph default ) can be thought of as a random experiment where there is a probability \emph on p \begin_inset Formula \( _{ij} \) \end_inset \emph default that \emph on P \begin_inset Formula \( _{i} \) \end_inset \emph default will win. Games actually observed are thus instances of a binomial distribution experimen t: Any sample of \emph on n \emph default games between \emph on \begin_inset Formula \( P_{i} \) \end_inset \emph default and \emph on P \begin_inset Formula \( _{j} \) \end_inset \emph default occurs with a probability of \begin_inset Formula \begin{equation} \label{eq.Psample} P(\text {sample})=p_{ij}^{w_{ij}}(1-p_{ij})^{n-w_{ij}} \end{equation} \end_inset \layout Standard where \emph on w \begin_inset Formula \( _{ij} \) \end_inset \emph default is the number of wins by player \emph on P \begin_inset Formula \( _{i} \) \end_inset \emph default . \layout Standard We wish to assign a \emph on relative strength \emph default (RS) parameter \begin_inset Formula \( \lambda _{i} \) \end_inset to each of the players involved in a tournament, where \begin_inset Formula \( \lambda _{i}>\lambda _{j} \) \end_inset implies that player \emph on P \begin_inset Formula \( _{i} \) \end_inset \emph default is better than player \emph on P \emph default \begin_inset Formula \( _{j} \) \end_inset . \layout Standard A probability function \begin_inset Formula \( F \) \end_inset such that \begin_inset Formula \( F(0)=0.5 \) \end_inset and \begin_inset Formula \( F(x)=1-F(-x) \) \end_inset (for all \begin_inset Formula \( x\in \Re \) \end_inset ) is chosen arbitrarily; following \begin_inset LatexCommand \cite{joe90} \end_inset we use the logistic function \begin_inset Formula \begin{equation} \label{eq.logistic} F(x)=\frac{1}{1+e^{-x}} \end{equation} \end_inset \layout Standard The model describes the probabilities \emph on p \begin_inset Formula \( _{ij} \) \end_inset \emph default as a function of the RS parameter \begin_inset Formula \( \lambda _{i} \) \end_inset for each player: \begin_inset Formula \begin{equation} \label{40073} p_{ij}=F(\lambda _{i}-\lambda _{j}) \end{equation} \end_inset so the outcome of a game is a probabilistic function of the difference between both opponent's strengths. The conditions imposed on \begin_inset Formula \( F \) \end_inset imply that players with equal strength are estimated to be equally likely to win or lose, and that the probability of \begin_inset Formula \( P_{i} \) \end_inset winning is equal to that of \begin_inset Formula \( P_{j} \) \end_inset losing. \layout Standard The observed data is a long sequence of games between opponent pairs, each one a either a win or a loss. According to eq. \begin_inset LatexCommand \ref{40073} \end_inset , the probability of that particular sequence was \begin_inset Formula \begin{equation} \label{26586} P=\prod _{i,j}F(\lambda _{i}-\lambda _{j})^{w_{ij}}\left( 1-F(\lambda _{i}-\lambda _{j})\right) ^{n_{ij}-w_{ij}} \end{equation} \end_inset \layout Standard for any choice of \begin_inset Formula \( \lambda \) \end_inset \begin_inset Formula \( _{i} \) \end_inset 's.The set of \begin_inset Formula \( \lambda \) \end_inset \begin_inset Formula \( _{i} \) \end_inset 's that best explains the observations is thus the one that maximizes this probability. The well known method of maximum likelihood can be applied to find the maximum for eq. \begin_inset LatexCommand \ref{26586} \end_inset , generating a large set of implicit simultaneous equations on \begin_inset Formula \( \lambda _{1},\ldots \lambda _{M} \) \end_inset that are solved by the Newton-Raphson algorithm. \layout Standard An important consideration is, the \begin_inset Formula \( \lambda \) \end_inset \begin_inset Formula \( _{i} \) \end_inset 's are not the true indeterminates, for the equations involve only paired differences, \begin_inset Formula \( \lambda _{i}-\lambda _{j} \) \end_inset . One point has to be chosen arbitrarily to be the zero of the RS scale. \layout Standard A similar method permits assigning a rating to the performance of any smaller sample of observations (one player for example): fixing all the \begin_inset Formula \( \lambda \) \end_inset \begin_inset Formula \( _{i} \) \end_inset 's on equation ( \begin_inset LatexCommand \ref{26586} \end_inset ), except one, we obtain \begin_inset Formula \begin{equation} \label{55060} \text {wins}=\sum _{i}F(\lambda -\lambda _{i}) \end{equation} \end_inset \layout Standard where \begin_inset Formula \( \lambda \) \end_inset is the only unknown --- all the other values are known. The single indeterminate can be found with identical procedure. \layout Standard A player's history of games is a vector \begin_inset Formula \( (x_{1},\ldots \, x_{N}) \) \end_inset of win/loss results, obtained against opponents with known RS's \begin_inset Formula \( \lambda _{i_{1}},\ldots ,\lambda _{i_{N}} \) \end_inset , respectively. Eq. ( \begin_inset LatexCommand \ref{55060} \end_inset ) can be solved iteratively, using a ``sliding window'' of size \emph on \begin_inset Formula \( n= REAR_RIGHT turn left \layout LyX-Code \family sans else if LEFT < RIGHT turn right \layout LyX-Code \family sans else turn left \layout LaTeX } \layout Standard This robot will always go straight, unless there is an obstacle in front of it closer than 8% of the size of the arena. At this point, it will turn right or left. The use of the REAR_RIGHT sensor is confusing, and its is difficult to infer from the code the actual behavior of this expression, as complex variations arise from its interactions with the Tron environment. \layout Standard When inserted in a Tron arena, the agent shows an interesting behavior. It will avoid obstacles, get out of dead ends and do tight turns to maximize space when in a confined space (fig. \begin_inset LatexCommand \ref{fig.510006} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 267 263 file sab98/graph/510006e1.eps width 3 45.00 flags 11 \end_inset \SpecialChar ~ \begin_inset Figure size 267 265 file sab98/graph/510006a1.eps width 3 45.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Sample games of robot 510006]{ \latex default \begin_inset LatexCommand \label{fig.510006} \end_inset Sample games of robot 510006 (black) vs. a human opponent (grey). It quickly beats a novice player (left). It fights against an expert player, making tight turns when confined in a small space (right). \latex latex } \end_float \layout Standard The basic strategy of going straight all the time, then turning at the last minute, is one of the obvious solutions for reasonable Tron agents, given the established architecture. But robots can do much better than this: Today R. 510006 ranks at no. 2740 among 5977 robots, which means that 45% of the strategies found are better than its own. \layout Subsection An Advanced Agent \layout Standard We now take a more detailed look at one of the top agents. R. 5210008 is at the time of this analysis, the top rated agent with an experience of more than 400 games; it has played 528 games and is the tenth ranked robot among those with 100 or more games played. \layout Standard \begin_float fig \layout Standard \latex latex { \backslash singlespace \family sans \size small \latex default ( IFLTE _G ( - ( - _A ( - ( IFLTE _C ( + _A ( IFLTE _E ( - ( - _F _A ) ( - _E ( - _C _G ) ) ) _A _D ) ) _C _D ) ( - ( IFLTE ( - ( + ( + _C ( - ( * _C ( - ( - _E _H ) _C ) ) _A ) ) _A ) ( - _F ( - ( + _G _A ) _H ) ) ) ( - _B ( + ( * _H _E ) _F ) ) ( - _C _A ) ( IFLTE _G ( - ( - _C ( IFLTE _G _A _F _F ) ) _C ) ( % ( IFLTE _A ( + _B _D ) ( - _C _C ) ( RIGHT_TURN ) ) _H ) ( IFLTE ( + ( IFLTE _E _C _C _D ) ( IFLTE ( IFLTE ( - _A _C ) ( IFLTE ( IFLTE ( - _C ( - _F _A ) ) _D _A ( IFLTE _G _C _F _C ) ) _E ( + ( - _C _H ) _E ) ( RIGHT_TURN ) ) _A _D ) _A ( - _F ( - _C ( - _C ( + 0.06349 _A ) ) ) ) ( RIGHT_TURN ) ) ) ( - _A ( + ( * _F _B ) _G ) ) _A _A ) ) ) ( - _E ( - _A ( - _F ( - _C ( - _C ( + 0.06349 _F ) ) ) ) ) ) ) ) ) ( - ( IFLTE _G _D ( IFLTE ( - _E ( - _E _A ) ) ( IFLTE ( - ( + ( + ( + _C ( - ( * _C ( + _C _F ) ) _H ) ) ( - ( * _E ( - ( - _E _H ) _C ) ) _A ) ) ( IFLTE ( IFLTE ( * ( - _E ( - _A _C ) ) _C ) ( - _A ( + ( + ( - _C 0.06349 ) _B ) _C ) ) _E _C ) ( * _F _C ) _F _A ) ) ( - _F ( - _C _H ) ) ) ( - _B ( + ( * _H _E ) _F ) ) ( - _C _A ) ( IFLTE _A ( - ( - ( - ( * ( + ( - ( - _H _D ) 0.06349 ) _C ) _A ) ( IFLTE _A ( IFLTE ( IFLTE ( - _C _A ) _D ( - ( - _D _A ) _D ) ( IFLTE _G _C _A _F ) ) ( + ( IFLTE _E _B _C _A ) _G ) _A ( RIGHT_TURN ) ) _G _H ) ) ( IFLTE _G _H _F _F ) ) _C ) ( % ( IFLTE _A ( + _B _A ) ( - _C _C ) ( RIGHT_TURN ) ) _H ) ( IFLTE ( + ( IFLTE _E _C _C _D ) ( IFLTE ( IFLTE ( - _A _C ) ( IFLTE ( IFLTE ( - _C ( - _F _A ) ) _D _A ( IFLTE _G _C ( + ( % _D _A ) ( LEFT_TURN ) ) _C ) ) ( + ( - _H ( - _A _C ) ) _A ) ( + ( - _C 0.06349 ) _E ) ( RIGHT_TURN ) ) _A _D ) _A ( - _F ( - _C _C ) ) ( RIGHT_TURN ) ) ) ( IFLTE _D ( - ( + ( - ( + _G _D ) _A ) _D ) _E ) _B ( - _A _A ) ) _C ( * _A ( * _H _E ) ) ) ) ) _B _E ) ( IFLTE ( + ( IFLTE _E _C _A _D ) _G ) _C _C _H ) ) ( IFLTE _F ( - _C _G ) ( IFLTE _G _C _F _F ) _A ) ) ) ( - ( * ( * ( - ( * _C ( - _C ( IFLTE ( - ( - _F _A ) ( * _F ( IFLTE _G _C _D _A ) ) ) ( * _D ( IFLTE _G _C ( + ( LEFT_TURN ) ( LEFT_TURN ) ) ( * _B ( RIGHT_TURN ) ) ) ) _F _A ) ) ) ( * _C _G ) ) ( IFLTE ( * ( IFLTE ( - _A ( - _F ( - _C ( - _C ( * _B _E ) ) ) ) ) _E _B _C ) ( IFLTE _H _C ( + ( LEFT_TURN ) _F ) _A ) ) _C _E _B ) ) _G ) _D ) ( + _F ( IFLTE _E _C _A _D ) ) ) \latex latex } \layout Caption \begin_inset LatexCommand \label{fig.5210008} \end_inset The code (s-expression) of agent 5210008. \end_float The s-expression of this agent has 449 tokens (see fig. \begin_inset LatexCommand \ref{fig.5210008} \end_inset ). But even the cyclomatic number of this expression is 283: a very complex formula indeed. Software complexity measures \begin_inset LatexCommand \cite{mccabe76} \end_inset suggest that cyclomatic numbers higher than 10 should be \begin_inset Quotes eld \end_inset avoided \begin_inset Quotes erd \end_inset because they make a program difficult to understand. The cyclomatic number fails to capture some of the inherent complexity of the formula, such as the widespread use of templates such as \family sans \series bold (- C _ ) \family default \series default and \family sans \series bold (IFLTE G _ _ _ ) \family default \series default . \layout Standard With its difficult structure, we were not able to manually de-compile the expression into pseudocode to try and follow the logic. The beginning of such pseudocode would be: \layout LaTeX { \backslash onehalfspacing \layout LyX-Code \family sans if (LEFT + RIGHT + RIGHT * (1 - RIGHT - FRONT_LEFT)) > (FRONT_RIGHT - FRONT) \layout LyX-Code \family sans then \begin_deeper \layout LyX-Code \family sans If FRONT< 1 - FRONT_LEFT \layout LyX-Code \family sans Then \begin_deeper \layout LyX-Code \family sans x = FRONT - RIGHT \end_deeper \layout LyX-Code \family sans else \begin_deeper \layout LyX-Code \family sans x = REAR_RIGHT; \end_deeper \layout LyX-Code \family sans if x > FRONT turn right \layout LyX-Code \family sans else y = FRONT \end_deeper \layout LyX-Code \family sans else \begin_deeper \layout LyX-Code \family sans y = RIGHT - FRONT; \end_deeper \layout LyX-Code \family sans if LEFT < REAR_RIGHT \layout LyX-Code \family sans then \begin_deeper \layout LyX-Code \family sans [...] \end_deeper \layout LaTeX } \layout Standard The first inequality involves 4 different sensors in a complex relationship, including a confusing multiplication and is already difficult to understand; it may generate a right turn or not, in which case the evaluation continues. And this is just the first expression of a long program, which would take several pages of pseudocode. Instead we have manually looked at several games from our historic records --- to see how the agent behaves in the game environment. \layout Standard So the next section, which talks about emergent behaviors in general, takes most of its examples from this player. We found out that it is capable of producing a surprising assortment of different behaviors including a different opening move for each game, cutting off the opponent , open box ``traps'' , driving around the edges and so on (figs. \begin_inset LatexCommand \ref{b.open} \end_inset , \begin_inset LatexCommand \ref{b.cutoff} \end_inset , \begin_inset LatexCommand \ref{b.trap} \end_inset , \begin_inset LatexCommand \ref{b.emerg} \end_inset and \begin_inset LatexCommand \ref{b.edge} \end_inset ). \layout Subsection Emergent Behaviors \layout Standard Tron agents, by their architecture, are purely reactive entities --- there is no state at all, no history or even access to the current position of the adversary. All behaviors are thus emergent, in the sense that they appear only as a result of the changing environment. \layout Standard The architecture of Tron was designed in 1997, when many researchers in the adaptive behavior community were proposing basic \emph on reactive \emph default agents whose complex behavior relied more on the complexities of the environmen t than on complex reasoning and planning \begin_inset LatexCommand \cite{brooks:91a} \end_inset . Consequently, Tron agents were deprived of any planning capability; they have no internal state, their sensory inputs are very restricted and all the complex behaviors that we observe are the result of their situatedness: Tron agents behave in complex ways as a results of their being adapted to a complex environment over a long evolutionary process. \layout Standard Placed on a fixed environment, a Tron agent would have a constant behavior, either right or left turn, or straight. This of course, never happens: even in the absence of an opponent, a Tron agent is constantly moving, generating a trail that immediately becomes part of the environment; such changes will be perceived and thus different actions begin to occur as a result of the re-evaluation of the agent's control expression. \layout Standard Among the information sent back by the Tron Java applets, and stored in our server's database, is the full trace of game. All turns are recorded, so we can re-enact and study the games that took place between humans and agents. \layout Standard From this record we have selected a few snapshots that showcase Tron agents performing different high-level behaviors during their games with humans. Every snapshot is labelled with the time \begin_float footnote \layout Standard In UNIX-style time units (number of seconds after 0:00 01/01/1970). \end_float at which the game finished, the id number of the human opponent and the robot's id number. An asterisk marks the losing player (or both in the case of a tie). \layout Standard The trace of the robot player is a black line, the human a grey line. \layout Paragraph Spiral inwards \layout Standard Tracing a box and then spiraling inwards is a commonplace defensive behavior (fig. \begin_inset LatexCommand \ref{b.spiral} \end_inset ). Once the box is marked, the opponent cannot get in; a spiral-in then exploits this gained territory optimally. \begin_float fig \layout Standard \align center \begin_inset Figure size 297 310 file behavior/spiralin.eps width 3 50.00 flags 15 \end_inset \layout Standard \latex latex \backslash caption[Spiral inwards]{ \emph on \latex default \begin_inset LatexCommand \label{b.spiral} \end_inset Spiral Inwards. \emph default A spiral inwards is a good solution to make the most out of a closed space (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Live and let live \layout Standard Sometimes two players avoid each other, staying away from confrontation, for as long as possible. Two commonplace occurrences in agent-vs-agent coevolutionary scenarios are loops across the vertical dimension, as seen on fig. \begin_inset LatexCommand \ref{b.live} \end_inset (left). Another strategy that attempts to stay away from the opponent is to spiral outwards from the starting position (fig. \begin_inset LatexCommand \ref{b.live} \end_inset , right). \layout Standard We think that this phenomenon occurs as a form of cooperation between coevolving agents: agents that agree on this behavior split the point with each other, engaging in a form of cooperation: any deviation from this behavior would be retaliated against. Figure \begin_inset LatexCommand \ref{collusion} \end_inset depicts two robots that persist on their behavior until they crash simultaneous ly, thus producing a tied game. \layout Standard We were surprised to observe humans engaging in the same type of strategy. In these two examples we see the human imitating the agent's behavior --- albeit imperfectly. On the first example, H. 457 died first; but on the second, H. 259 successfully broke the pattern, and R. 370002 lost the match. \begin_float fig \layout Standard \align center \begin_inset Figure size 291 304 file behavior/live1.eps width 3 49.00 flags 11 \end_inset \begin_inset Figure size 291 304 file behavior/live2.eps width 3 49.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Live and let live]{ \emph on \latex default \begin_inset LatexCommand \label{b.live} \end_inset Live and Let Live. \emph default In both these games, human and agent agree on a common strategy to avoid confrontation. This often occurs as a form of emergent collusion in coevolutionary games, yet it's surprising to observe it occur between human and agent (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Staircasing \layout Standard Only orthogonal movement is defined by the rules of Tron. One can move in a horizontal or vertical direction, never diagonal. But Tron agents often simulate a diagonal, by quickly alternating left and right turns. It may be a bit disconcerting for the human but, by itself, is not enough to be a good player (fig. \begin_inset LatexCommand \ref{b.stair} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 309 323 file behavior/staircrash.eps width 3 52.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Too much staircasing]{ \emph on \latex default \begin_inset LatexCommand \label{b.stair} \end_inset Too much staircasing. \emph default Agent 280003 seems to know about staircasing and little else (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Opening moves \layout Standard The first few seconds of a match set up the type of game that will be played. A player has the option to try and stay away from its opponent, or go after him; to stay close to the starting position or mark territory away from it. In any case, performing the same opening moves in every game seems like a bad idea, for opponents would be able to adapt to it. Performing a different opening move every time is difficult to accomplish for deterministic agents that start every game from the same configuration. Figure \begin_inset LatexCommand \ref{b.open} \end_inset , however, shows a series of games played by R. 5210008 (only the first 300 steps of every game). All these games have different initial moves. \begin_float fig \layout Standard \align center \begin_inset Figure size 190 198 file behavior/open1.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open2.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open3.eps width 3 32.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 190 198 file behavior/open4.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open5.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open6.eps width 3 32.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 190 198 file behavior/open7.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open8.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 198 file behavior/open9.eps width 3 32.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Changing Behavior]{ \emph on \latex default \begin_inset LatexCommand \label{b.open} \end_inset Changing Behavior. \emph default Agent 5210008 showcases here its variety of opening moves (black=agent, gray=human). \latex latex } \end_float \layout Paragraph The cutoff maneuver \layout Standard A common move among humans is the ``cutoff'': If you and your opponent are running parallel to each other, but you are ahead, cut him off and try to beat his reaction. One wouldn't expect to see an agent perform the cutoff --- they don't know where you are! Figure \begin_inset LatexCommand \ref{b.cutoff} \end_inset however, depicts R. 5210008 performing what looks like a typical cutoff. \layout Standard \begin_float fig \layout Standard \align center \begin_inset Figure size 145 151 file behavior/cutoff1.eps width 4 49.00 flags 11 \end_inset \begin_inset Figure size 145 151 file behavior/cutoff2.eps width 4 49.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Cutoff]{ \emph on \latex default \begin_inset LatexCommand \label{b.cutoff} \end_inset Cutoff. R. \emph default 5210008 is seen here performing the \begin_inset Quotes eld \end_inset cutoff \begin_inset Quotes erd \end_inset maneuver. Human and agent find themselves running parallel (left), but the agent is ahead, so it makes a sharp right turn, cutting off the human (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Topological games \layout Standard During the game depicted on fig. \begin_inset LatexCommand \ref{b.trap} \end_inset , agent 5210008 created a box with a small opening. This box spans across the screen boundary, so it is not easy to perceive for a human player. When the opponent finds himself in the box, it may be difficult to go back and find the narrow exit. \begin_float fig \layout Standard \align center \begin_inset Figure size 145 151 file behavior/trap1b.eps width 4 49.00 flags 11 \end_inset \begin_inset Figure size 145 151 file behavior/trap2b.eps width 4 49.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Trapped]{ \emph on \latex default \begin_inset LatexCommand \label{b.trap} \end_inset Trapped \emph default . R. 5210008 created a box at the edge of the screen, with a small opening, and its opponent fell inside it. After visiting the trap once, H. 8323 goes up (left), ultimately landing in the trap again. Eventually the human is boxed in and commits suicide (right). \latex latex } \end_float \layout Paragraph Combined behaviors \layout Standard Fig. \begin_inset LatexCommand \ref{b.emerg} \end_inset shows an agent combining different behaviors: wandering, wall following, obstacle avoidance, space-filling turns, to win a game. \begin_float fig \layout Standard \align center \begin_inset Figure size 145 151 file behavior/wan1.eps width 4 49.00 flags 11 \end_inset \begin_inset Figure size 145 151 file behavior/wan2.eps width 4 49.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Emergent behaviors]{ \emph on \latex default \begin_inset LatexCommand \label{b.emerg} \end_inset Emergent Behaviors \emph default R. 5210008 displays different emergent behaviors in this match. In the first part of the game it uses a combination of wandering and obstacle avoidance strategies, cutting off the arena in small spaces (left). As the game progresses, a combination of tight turns and wall following help make the most out of a more confined situation (right) (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Edging \layout Standard Running along the edges of the screen is a strategy that easily creates confusion in humans. A human player approaching the edge often finds it difficult to quickly look at the other edge to plan ahead for what is going after emerging on the other side. A wall along it is difficult to see. Agents on the other hand, are immune to this strategy --- the border of the screen is invisible to them; their sensors have no perception of borders, they don't really exist, being an artifact of how the display was encoded for visual human input (fig. \begin_inset LatexCommand \ref{b.edge} \end_inset ). \begin_float fig \layout Standard \align center \begin_inset Figure size 309 323 file behavior/edg.eps width 3 52.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Edging and staircasing]{ \latex default \begin_inset LatexCommand \label{b.edge} \end_inset \emph on Edging \emph default \emph on and Staircasing \emph default . Here R. 5210008 shows the use of staircasing to produce a diagonal displacement in a domain where only horizontal and vertical movements were originally defined. Creating walls along the edges of the screen, as in this game, allows Tron agents to exploit one human handicap: humans have trouble understanding the toroidal topology where edges are connected. In this game the human attempted to go across the border and crashed the wall that the agent had built (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Space Filling \layout Standard It often happens that an end game is reached where both opponents are confined in a space, isolated from the opponent. At this point the optimal strategy becomes filling the space as densely as possible, hoping for the other opponent to crash sooner. Any good Tron player should master this technique. The game depicted on fig. \begin_inset LatexCommand \ref{b.spacfil} \end_inset shows human and agent in a match of endurance. \begin_float fig \layout Standard \align center \begin_inset Figure size 309 323 file behavior/spacfil.eps width 3 52.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Space filling]{ \emph on \latex default \begin_inset LatexCommand \label{b.spacfil} \end_inset Space Filling. \emph default R. 5470006 and Human 5074 engage in a space-filling endurance contest. The difference between their perceptual modes is visible: The human is allowed tighter turns, yet its finger ability is limited. The agent cannot measure with precision the space remaining, so sometimes recurs to spiraling in, then out as in the upper right region. In the end the human fails to enter a narrow passage and loses (black=agent, gray=human). \latex latex } \end_float \layout Paragraph Unforced errors \layout Standard Even the highest ranked Tron agents seem to make an occasional mistake, crashing against themselves in a silly manner for example (fig. \begin_inset LatexCommand \ref{b.error} \end_inset ). People do the same, even the best player makes an occasional mistake. \begin_float fig \layout Standard \align center \begin_inset Figure size 297 310 file behavior/error.eps width 3 50.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Error]{ \emph on \latex default \begin_inset LatexCommand \label{b.error} \end_inset Error. \emph default R. 5470006, one of the all-time best Tron agents, loses here in a stupid manner, crashing itself. Even though this is a highly evolved agent capable of winning against most human opponents, it still makes occasional mistakes (black=agent, gray=human). \latex latex } \end_float \layout Subsubsection Behavior or Imagination? \layout Standard Are these behaviors really occurring as we described them? Some cases, such as spiraling, are quite obvious, but others like the \emph on cutoff \emph default and the \emph on trap \emph default might be more in the imagination of the observer. After all, a Tron agent cannot decide that the time is ripe for a cutoff maneuver without knowing the position of the other player. Nor it has memory to decide: \begin_inset Quotes eld \end_inset I am in the process of doing a spiral, so turn in the same direction again \begin_inset Quotes erd \end_inset . \layout Standard On the other hand, it might be the case that the cutoff is \begin_inset Quotes eld \end_inset definable \begin_inset Quotes erd \end_inset for an agent in different terms than ours. As long as there is a certain environmental condition (in terms of sensory inputs) that is correlated with the right moment to do a cutoff, agents likely to turn in the correct direction in those circumstances might have an evolutionary advantage, so in the end we see agents \begin_inset Quotes eld \end_inset doing it \begin_inset Quotes erd \end_inset with increasing frequency. \layout Standard Ethologists warn us \begin_inset LatexCommand \cite[p. 105]{plotkin94} \end_inset that an animal's action is called \emph on behavior \emph default only when performed in order to improve its chances of survival or reproduction --- because it has been selected for, that is. The present section just shows a group of snapshots to illustrate the types of actions that Tron agents are performing. In the next one we go further, testing for correlations between behaviors, evolutionary time, and fitness. \layout Subsection Quantitative Analysis of Behaviors \layout Standard Emergent behaviors are difficult to quantify: how could we measure ``wandering'' ? In this section we examine some behaviors that we were able to define with simple formulas, allowing us to count their occurrences quickly by using regular expressions. \begin_float tab \layout Standard \align center \LyXTable multicol5 13 2 0 0 -1 -1 -1 -1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Behavior \newline Expression \newline Tight Turn \newline \begin_inset Formula \( U<6 \) \end_inset \newline Spiral \newline \begin_inset Formula \( U^{3} \) \end_inset \newline Staircase \newline \begin_inset Formula \( S^{3} \) \end_inset \newline Zig-zag \newline \begin_inset Formula \( USU \) \end_inset \newline Loop \newline \begin_inset Formula \( (\{U|S]\}>150)(S<14) \) \end_inset \newline Diagonal \newline \begin_inset Formula \( (S<15)^{3} \) \end_inset \newline Zig-zag Fill \newline \begin_inset Formula \( (U<6)S(U<6) \) \end_inset \newline Turns \newline \emph on turns \emph default \newline Asymmetry \newline \begin_inset Formula \( \left| \frac{\text {\em {left\, turns}}-\text {\em {right\, turns}}}{\text {\em {turns}}}\right| \) \end_inset \newline Edge Crossing \newline \emph on distance to edge = 0 \emph default \newline Edging \newline \emph on distance to edge \begin_inset Formula \( \leq \) \end_inset 10 \emph default and \emph on parallel to edge \emph default \newline Spiral In & Out \newline \begin_inset Formula \( U^{3}SU^{3} \) \end_inset \layout Caption \begin_inset LatexCommand \label{table.behaviors} \end_inset Definitions of Behaviors \end_float \layout Standard \added_space_bottom bigskip Two consecutive turns of a Tron player can be either in the same direction (left-left or right-right) or in opposite directions (right-left or left-right). The former are \emph on U \emph default moves, and the latter \emph on S \emph default moves. The \emph on size \emph default of the move is the number of pixels advanced between the two turns. Most of the different behaviors we quantified are formally defined by a regular expression on the sequence of turns thus defined (table \begin_inset LatexCommand \ref{table.correlations} \end_inset ). \layout Standard \noindent \latex latex \backslash itemleft{ \begin_inset Figure size 72 72 file graph/b01.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 1 \series bold \emph default . \series default \emph on Tight Turns \emph default \SpecialChar ~ \SpecialChar ~ A tight turn is defined as two consecutive turns to the same side, within 6 steps of each other ( \begin_inset Formula \( U<6 \) \end_inset ). The icon depicts a player doing 8 tight U turns. \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \emph on \begin_inset Figure size 72 72 file graph/b02.eps width 2 1.00 flags 11 \end_inset \emph default }{ \emph on \latex default 2. Spirals\SpecialChar ~ \SpecialChar ~ \emph default \latex latex \latex default A spiral can be outwards or inwards; it is characterized as making four turns in the same direction. \latex latex } \layout Standard \noindent \latex latex \backslash itemleft{ \emph on \latex default \begin_inset Figure size 72 72 file graph/b03.eps width 2 1.00 flags 11 \end_inset \emph default \latex latex }{ \emph on \latex default 3. Staircase\SpecialChar ~ \SpecialChar ~ \emph default A staircase is defined as 4 consecutive alternating turns. \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \begin_inset Figure size 72 72 file graph/b04.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 4. Zig-zag\SpecialChar ~ \SpecialChar ~ \emph default A player is \begin_inset Quotes eld \end_inset zig-zagging \begin_inset Quotes erd \end_inset when alternating left-left then right-right turns. \latex latex } \layout Standard \noindent \latex latex \backslash itemleft{ \begin_inset Figure size 72 72 file graph/b05.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 5. Looping\SpecialChar ~ \SpecialChar ~ \emph default A player ``loops'' around the torus when she goes straight for more than 150 steps, then makes a quick `S' turn (less than 14 steps) to make a second pass parallel to the first one (fig. \begin_inset LatexCommand \ref{b.live} \end_inset left). \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \begin_inset Figure size 72 72 file graph/b06.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 6. Diagonal\SpecialChar ~ \SpecialChar ~ \emph default A diagonal move is a tight staircase, all turns within 15 steps of each other (fig. \begin_inset LatexCommand \ref{b.stair} \end_inset ). \latex latex } \layout Standard \noindent \latex latex \backslash itemleft{ \begin_inset Figure size 72 72 file graph/b07.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 7. Zig-zag filling\SpecialChar ~ \SpecialChar ~ \emph default This behavior is a combination of zig-zag and tight turns; a succession of 2 opposite tight U turns. It is a useful strategy to fill up the space tightly. The human player on fig. \begin_inset LatexCommand \ref{b.spacfil} \end_inset spent most of the match executing this behavior. \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \begin_inset Figure size 72 72 file graph/b08.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 8. Turns\SpecialChar ~ \SpecialChar ~ \emph default Some players go straight for a long time, others are turning all the time. This feature could also be called ``nervousness''. \latex latex } \layout Standard \noindent \latex latex \backslash itemleft{ \begin_inset Figure size 72 72 file graph/b09.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 9. Asymmetry\SpecialChar ~ \SpecialChar ~ \emph default Some players prefer to do mostly left turns or right turns; others have a 50%-50% balance. According to the definition on table \begin_inset LatexCommand \ref{table.behaviors} \end_inset , an asymmetry equal to one means all turns have been made to the same side, and a zero asymmetry means an equal number of turns to both sides. The icon depicts a player making seven right turns but just one left turn (6/8 asymmetry = 0.75). \layout Standard \noindent \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \begin_inset Figure size 72 72 file graph/b10.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 10. Edge Crossing\SpecialChar ~ \SpecialChar ~ \emph default Each time a player crosses the edge of the screen, to reappear on the opposite side. Agents do this without noticing, since they have no perception of the arena having edges; they just see a continuous topology. Humans need to learn to mentally connect the opposite borders of the screen. The icon depicts a player going across the edge five times. \latex latex } \layout Standard \noindent \latex latex \backslash itemleft{ \begin_inset Figure size 72 72 file graph/b11.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 11. Edging\SpecialChar ~ \SpecialChar ~ \emph default Each step a player runs parallel to the edge of the screen within 10 pixels of it (see fig. \begin_inset LatexCommand \ref{b.edge} \end_inset ). \latex latex } \layout Standard \noindent \latex latex \backslash itemright{ \begin_inset Figure size 72 72 file graph/b12.eps width 2 1.00 flags 11 \end_inset }{ \emph on \latex default 12. Spiral in and Out\SpecialChar ~ \SpecialChar ~ \emph default We have observed that one of the ways Tron agents may use to gain a space and exploit it, is a spiral that goes in first, then out. This player can spiral in loosely, then go backwards, spiraling out. The pure spiral behavior often ends in a crash (fig. \begin_inset LatexCommand \ref{b.spiral} \end_inset ) but after spiraling in, then out, the player is still alive. The agent of fig. \begin_inset LatexCommand \ref{b.spacfil} \end_inset used this strategy at the upper right corner of the arena. We have defined it as four consecutive turns to one side (spiral) followed by four turns to the opposite side (opposite spiral). \latex latex } \layout Standard \added_space_top bigskip The first question we wish to quantify is: Are any of these simple behaviors being favored or disfavored by evolution? Is our system consistently relying on any of them? The first group of results, fig. \begin_inset LatexCommand \ref{beh.time} \end_inset , shows the frequency of behaviors along the history of the system. We grouped all games in bins of 1000, and counted the occurrences of each of the 12 patterns, divided by the number of steps. So each behavior is quantified as the ``propensity'' of the Tron system to engage in it (except for \emph on asymmetry \emph default which is a per-turn ratio, not per-step). \begin_float fig \layout Standard \added_space_top 0.3cm \align center \begin_inset Figure size 190 157 file aftermath2/winfeat01.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 160 file aftermath2/winfeat02.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 152 file aftermath2/winfeat03.eps width 3 32.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 190 157 file aftermath2/winfeat04.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 160 file aftermath2/winfeat05.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 152 file aftermath2/winfeat06.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 157 file aftermath2/winfeat07.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 152 file aftermath2/winfeat08.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 154 file aftermath2/winfeat09.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 157 file aftermath2/winfeat10.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 154 file aftermath2/winfeat11.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 157 file aftermath2/winfeat12.eps width 3 32.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Behaviors vs. time]{ \emph on \latex default \begin_inset LatexCommand \label{beh.time} \end_inset Behaviors vs. Time \emph default . U turns, spirals, staircasing, zigzag, loop, diagonal, zigzag-fill, turns, asymmetry, edge crossing, edge following, spiral in, then out. Games were sampled in groups of 1000 and average events of each behavior, per game step, plotted on the vertical axis. \latex latex } \end_float \layout Standard The behaviors that occur with increased frequency along time are tight turns, zig-zags, filling zig-zags, edge following and spiral-in-out. Decreasing in frequency are spiraling and asymmetry. The others do not show a clear tendency. This confirms some of our intuitions, such as filling spaces and edging being favored by evolution. Spiraling on the other hand, is surprisingly disfavored. We must conclude that spiraling is a bad idea in general, albeit a necessary tool for a behavior that is a specialization of spiral --- spiral-in-then-out, which is favored by evolution. \layout Standard The next question is, are these behaviors associated with a robot's measured strength? Do some behaviors occur more or less often in stronger robots? The associations should not be much different from those defined by time, since performance is being selected across the time dimension. To observe this, we have selected all robots whose accumulated games are at least 10000 steps, and measured their behavioral frequency. On fig. \begin_inset LatexCommand \ref{beh.both} \end_inset we have marked one point per robot; the \emph on x \emph default coordinate being the strength, the \emph on y \emph default coordinate the behavioral frequency. The result is a cloud of points, quite disperse in all cases. This means that none of these behaviors implies, by itself, that an agent is strong or weak. Quite the opposite, for each behavior one can usually find both good and bad players who perform it either often or rarely. \begin_float fig \layout Standard \added_space_top 0.3cm \align center \begin_inset Figure size 190 160 file aftermath2/ufeat01.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 160 file aftermath2/ufeat02.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 157 file aftermath2/ufeat03.eps width 3 32.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 190 163 file aftermath2/ufeat04.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 160 file aftermath2/ufeat05.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 157 file aftermath2/ufeat06.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 163 file aftermath2/ufeat07.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 157 file aftermath2/ufeat08.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 159 file aftermath2/ufeat09.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 159 file aftermath2/ufeat10.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 157 file aftermath2/ufeat11.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 163 file aftermath2/ufeat12.eps width 3 32.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Behaviors vs. performance]{ \emph on \latex default \begin_inset LatexCommand \label{beh.robots} \end_inset Behaviors vs. Performance: \emph default U turns, spirals, staircasing, zigzag, loop, diagonal, zigzag-fill, turns, asymmetry, edge crossing, edge following, spiral in, then out. Horizontal axis: robot RS; vertical axis: average events per game step. Every robot is plotted as one point. The broken line is a histogram showing mean occurrences along 6 intervals on the RS range. Error bars mark the standard error of the mean. \latex latex } \end_float \layout Standard The clouds of points do show some accumulation regions though, so we also divided the RS axis in six segments and calculated the mean and its standard error. We confirm with this that, on average, better robots are doing more tight turns, zig-zags, filling zig-zags and spirals in/out but less spirals --- and tend to have symmetrical behaviors and follow the edges of the screen. \layout Subsection Differences Between Human and Agent Behaviors \layout Standard In this section we analyze the differences between agent and human behavior, according to the 12 \begin_inset Quotes eld \end_inset quantifiable \begin_inset Quotes erd \end_inset behaviors described on the previous section. Figure \begin_inset LatexCommand \ref{beh.both} \end_inset shows the results. The graphs in this figure repeat the curves for robot behavior frequency vs. performance (same as in \begin_inset LatexCommand \ref{beh.robots} \end_inset ), adding the curves for the human case. \begin_float fig \layout Standard \added_space_top 0.3cm \align center \begin_inset Figure size 190 165 file aftermath2/bothf01.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 156 file aftermath2/bothf02.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 156 file aftermath2/bothf03.eps width 3 32.00 flags 11 \end_inset \layout Standard \align center \begin_inset Figure size 190 160 file aftermath2/bothf04.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 165 file aftermath2/bothf05.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 156 file aftermath2/bothf06.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 165 file aftermath2/bothf07.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 158 file aftermath2/bothf08.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 163 file aftermath2/bothf09.eps width 3 32.00 flags 11 \end_inset \layout Standard \added_space_bottom 0.3cm \align center \begin_inset Figure size 190 161 file aftermath2/bothf10.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 166 file aftermath2/bothf11.eps width 3 32.00 flags 11 \end_inset \begin_inset Figure size 190 167 file aftermath2/bothf12.eps width 3 32.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[Agent vs. Human Behaviors]{ \emph on \latex default \begin_inset LatexCommand \label{beh.both} \end_inset Agent & Humans behavior frequencies vs. strength: \emph default There are significant behavioral differences between agent (thin lines) and human (thick lines) behaviors, according to our 12 test cases. Horizontal axis: RS; vertical axis: average events per game step. Error bars indicate the standard error of the mean. The first and last bins are wider, to compensate for the sparsity of players at both ends of the performance scale. \latex latex } \end_float . \layout Standard Table \begin_inset LatexCommand \ref{table.correlations} \end_inset summarizes these results, comparing four categories: novice agents, advanced agents, novice humans and advanced humans. \begin_float tab \layout Standard \align center \LyXTable multicol5 16 7 0 0 -1 -1 -1 -1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 1 8 1 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 1 8 1 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 1 8 0 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 1 8 0 0 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 1 8 0 1 0 0 0 "" "" 2 8 1 0 0 0 0 "" "" 1 8 0 1 0 0 0 "" "" 2 8 0 1 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" \emph on from \emph default \newline Novice \newline Advanced \newline Novice \newline \newline Agent \newline Agent \newline Human \newline \emph on to \emph default \newline Advanced \newline Novice \newline Advanced \newline Novice \newline Advanced \newline Advanced \newline \newline Agent \newline Human \newline Human \newline Human \newline tight turns \newline \series bold + \series default \newline - \newline = \newline - \newline - \newline \series bold + \series default \newline spiral \newline \series bold - \series default \newline - \newline - \newline - \newline = \newline \series bold = \series default \newline staircase \newline \series bold = \series default \newline - \newline - \newline - \newline - \newline \series bold = \series default \newline zigzag \newline \series bold + \series default \newline = \newline + \newline - \newline - \newline \series bold + \series default \newline loop \newline \series bold + \series default \newline = \newline - \newline - \newline - \newline \series bold = \series default \newline diagonal \newline \series bold = \series default \newline - \newline - \newline - \newline - \newline \series bold = \series default \newline zigzag fill \newline \series bold = \series default \newline = \newline + \newline - \newline = \newline \series bold + \series default \newline turns \newline \series bold = \series default \newline - \newline - \newline - \newline - \newline \series bold = \series default \newline asymmetry \newline \series bold - \series default \newline - \newline - \newline = \newline = \newline \series bold = \series default \newline edge crossing \newline \series bold = \series default \newline - \newline - \newline - \newline - \newline \series bold + \series default \newline edge following \newline \series bold + \series default \newline - \newline = \newline - \newline - \newline \series bold = \series default \newline spiral in&out \newline \series bold + \series default \newline = \newline - \newline - \newline - \newline \series bold = \layout Standard \latex latex \backslash caption[Correlations between humans, agents and behaviors]{ \emph on \latex default \begin_inset LatexCommand \label{table.correlations} \end_inset Correlations between humans, agents and behaviors \emph default . Each column represents a pair of categories. The \begin_inset Quotes eld \end_inset = \begin_inset Quotes erd \end_inset symbol means that there is no big difference between both categories on the respective behavior, whereas \begin_inset Quotes eld \end_inset + \begin_inset Quotes erd \end_inset means that the second group has an increased value with respect to the second (and ``-'' the opposite). The first and last columns compare novices with advanced players, amongst agents and humans respectively. Tight turns for example, increase with level of play for both agents and humans (+); a novice agent doing about as many of them as an advanced human. Asymmetry is negatively correlated with quality (for robots) but uncorrelated for humans. \latex latex } \latex default \end_float \layout Standard These are the differences for each individual behavior: \layout Description \pextra_type 3 \pextra_widthp 35 Tight\SpecialChar ~ turns \series bold \series default Agents develop the capacity for doing tight turns early on. Due to their error-free sensors, they can perform this type of maneuver very efficiently. The more advanced the agent, the more frequent the behavior becomes. \begin_deeper \layout Standard For humans, doing closed turns with exact precision requires training. As with agents, there is a strong correlation between frequency of tight turns and performance. A top human, on average, performs tight turns as often as a beginner agent. \end_deeper \layout Description Spiral Although it does happen sometimes (see fig. \begin_inset LatexCommand \ref{b.live} \end_inset ), this is not a frequent behavior for people. The inwards spiral amounts to creating a confined space and entering it, something that human biases warn us against. The outwards spiral also seems pointless, it is a passive behavior that neither attacks nor runs away from the attacker. \begin_deeper \layout Standard The opposite is true for agents. Robots develop this strategy in the beginning of robot-robot coevolution scenarios, when most other strategies are random (hence suicidal). Sometimes a whole population may fall into a \emph on mediocre stable-state \emph default \begin_inset LatexCommand \cite{pollackblair96} \end_inset characterized by most agents doing spirals. The spiral is probably the simplest non-suicidal behavior in terms of GP code. \layout Standard A search for the shortest robots ever produced by the novelty engine (table \begin_inset LatexCommand \ref{table.shortagents} \end_inset ) reveals two minimal behaviors which use just 5 tokens. One of them, R230007 does a classic tight spiral, and the other, R. 90001, a more loose spiral. \begin_float tab \end_deeper \layout Standard \added_space_top 0.3cm \added_space_bottom 0.3cm \align center \LyXTable multicol5 11 3 0 0 -1 -1 -1 -1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 8 1 0 "" "" 8 1 0 "" "" 8 1 1 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" 0 8 1 0 0 0 0 "" "" Agent Id. \newline Len \newline Code \newline 230007 \newline 5 \newline (IFLTE 0.88889 _C _C (LEFT_TURN)) \newline 230009 \newline 5 \newline (IFLTE 0.88889 _C _C (LEFT_TURN)) \newline 230010 \newline 5 \newline (IFLTE 0.88889 _C _C (LEFT_TURN)) \newline 90001 \newline 5 \newline (IFLTE _D _C (LEFT_TURN) _D) \newline 90002 \newline 5 \newline (IFLTE _D _C (LEFT_TURN) _D) \newline 510003 \newline 7 \newline (* _H (IFLTE _A 0.90476 _H (RIGHT_TURN))) \newline 50008 \newline 9 \newline (* _H (IFLTE _A 0.90476 _H (RIGHT_TURN))) \newline 60001 \newline 9 \newline (IFLTE _B _F (IFLTE _C _H (LEFT_TURN) 0.11111) _F) \newline 60002 \newline 9 \newline (IFLTE _B _F (IFLTE _C _H (LEFT_TURN) 0.11111) _F) \newline 60003 \newline 9 \newline (IFLTE _B _F (IFLTE _C _H (LEFT_TURN) 0.11111) 0.12698) \layout Standard \latex latex \backslash caption[Shortest Agents]{ \latex default \begin_inset LatexCommand \label{table.shortagents} \end_inset The shortest agents produced by the novelty engine have 5 tokens each. Agents 230007, 230009 and 230010 do a tight spiral. 90001 and 90002, a wide spiral (fig. \begin_inset LatexCommand \ref{fig.simplestagent} \end_inset ). 510003 does something different: it goes straight until it reaches an obstacle. 60001-60003 do a sort of \begin_inset Quotes eld \end_inset Tit-for-tat \begin_inset Quotes erd \end_inset ; they spiral while the other player is also spiraling, but break the pattern when the other player does so. \latex latex } \end_float The code for R. 230007 is: \begin_deeper \layout Quote \added_space_top defskip \noindent \pextra_type 2 \pextra_alignment 1 \pextra_widthp 100 \family sans (IFLTE 0.88889 _C _C (LEFT_TURN)) \layout Standard \pextra_type 2 \pextra_alignment 0 \pextra_widthp 100 which translates as:In the end, humans get out of mazes for the exact same reason. \layout LyX-Code \family sans if LEFT < 0.8888 then go straight else turn left \layout Standard so this robot executes a left turn whenever there are no obstacles to the left. This minimal code results in an basic wall following that produces a tight spiral as depicted on fig. \begin_inset LatexCommand \ref{fig.simplestagent} \end_inset (top). When the robot is running along its own wall, built by the previous lap, the left sensor perceives the obstacle and the agent goes straight. But as soon as the corner is reached, the space suddenly opens to the left and the agent turns. \layout Standard As evolution progresses, agents \begin_inset Quotes eld \end_inset unlearn \begin_inset Quotes erd \end_inset to do spirals, finding better strategies. The behavior frequency diminishes sharply for more advanced agents, approaching the human average rate: In the best robots, spiraling has been almost completel y abandoned. \begin_float fig \end_deeper \layout Standard \align center \begin_inset Figure size 267 267 file graph/r230007a.eps width 3 45.00 flags 15 \end_inset \begin_inset Figure size 267 268 file graph/r230007b.eps width 3 45.00 flags 15 \end_inset \layout Standard \align center \begin_inset Figure size 267 265 file graph/r90001.eps width 3 45.00 flags 15 \end_inset \layout Standard \latex latex \backslash caption[Simplest Agents]{ \emph on \latex default \begin_inset LatexCommand \label{fig.simplestagent} \end_inset Simplest Agent. \emph default Sample games of the simplest agents according to code size (table \begin_inset LatexCommand \ref{table.shortagents} \end_inset ). R. 230007 and R. 90001 are 5 tokens long. Agent 230007 does a tight spiral by means of a simple wall following, oblivious to what its opponent is doing (top left). This agent can sometimes break the spiral when it finds an obstacle (top right), by \begin_inset Quotes eld \end_inset following \begin_inset Quotes erd \end_inset the wall of an obstacle. The spiral of agent 90001 (bottom), created by comparing the left and rear-left sensors, is a Fibonacci spiral (the length of each segment equals the sum of the previous two). \latex latex } \end_float \layout Description Staircase Together with its tight version, the \series bold diagonal \series default , staircasing is a characteristic behavior that strongly differentiates human and robotic playing styles. Agents perform a diagonal on 1% of their total game time on average, whereas the rate for humans is much lower, close to 0.05%. \begin_deeper \layout Standard A human's attention typically shifts between two modes: it either focuses on a narrow region around the present position, in order to perform precise maneuvers and turns, or spreads over a wider region, analyzing the different parts of the arena in an effort to plan the next move. \layout Standard A move such as the staircase can be performed only in the narrow attention mode. When one switches to the second, \begin_inset Quotes eld \end_inset big picture \begin_inset Quotes erd \end_inset mode of attention, turns stop completely. So humans in general will not perform continuous turns for long periods of time. \layout Standard Agents, on the other hand, lack attention characteristics altogether, so they can afford to be constantly turning without confusing or delaying their sensors readings or analysis. \end_deeper \layout Description Zigzag/Zigzag\SpecialChar ~ fill This is a behavior that shares similar frequency profiles for both species. Zigzagging is an important ability for the endgame, so its frequency increases with expertise on agents as well as on humans. The sample game shown on figure \begin_inset LatexCommand \ref{b.spacfil} \end_inset illustrates how both species resort to zigzagging in similar situations. \begin_deeper \layout Standard The \begin_inset Quotes eld \end_inset filling \begin_inset Quotes erd \end_inset zigzag serves the purpose of making the most out of a confined space and amounts to about half of all zig-zags, in humans and robots alike. The frequency of filling zig-zag, for humans as well as agents, is an order of magnitude larger for expert players as compared to novices. \end_deeper \layout Description Loop Looping, together with spiraling and tight zigzagging, is a space-filling strategy (fig. \begin_inset LatexCommand \ref{b.live} \end_inset , left). The correlations of looping and strength are unique, though: both humans and agents seem to increase looping with expertise, but only up to a certain point. In the end, the most expert players, humans or robots alike, have abandoned this behavior, frequencies falling down to beginners' levels. \layout Description Turns Another behavior that strongly differentiates humans and agents: agents are much more \begin_inset Quotes eld \end_inset nervous \begin_inset Quotes erd \end_inset , they make turns more frequently. Robots turn once every 33 steps on average, whereas humans do so only once every 80 steps. Again we think that this difference is related to human attention modes, as in the staircase above. \layout Description Asymmetry Humans rarely depict any strong preference for turning to either side, whereas this is a typical characteristic of unsophisticated robots. \begin_deeper \layout Standard The reasons for asymmetric behavior on robots are similar to those explained for spiraling above: early on coevolutionary runs, a useful turn is discovered and exploited. The code will spread along the population and everybody will start performing the same type of turn. Later on, more advanced turning patterns are discovered that involve left as well as right turns. \layout Standard In the end, the best agent strategies have perfectly balanced frequencies of left and right turns: levels of asymmetry are near-zero for advanced robots, and for humans of all levels. \end_deeper \layout Description Edge\SpecialChar ~ Crossing \series bold \series default Unsurprisingly, robots cross the edges of the screen more often than humans. Robots do not perceive edges in any direct manner, so they move across without a problem. \begin_deeper \layout Standard Agents go across edges once every 300 game steps (approximately), whereas the human frequency is closer to one crossing every 500 game steps (a random walk would go across an edge every 256 steps). \end_deeper \layout Description Edge\SpecialChar ~ Following Another differentiating behavior, robots move close and parallel to the edges of the visible screen (at a distance of 10 or less, see fig. \begin_inset LatexCommand \ref{b.edge} \end_inset ) more often than humans. Also, the percentage of game time they spend doing this, increases with the expertise of the agent. \begin_deeper \layout Standard A random walk would move along the edges 7.8% of the time. This is about the frequency for novice robots, but expert ones `edge' about 12% of the time. Human rates stay between 2.5% and 5%, increasing slightly for experts. \layout Standard Even though agents do not perceive edges --- and thus are incapable of defining ``edging'' explicitly --- the better ones do it more often than random. Thus, albeit indirectly defined, agents seem to have found a way to exploit a human weakness. \layout Standard For humans, being close to an edge is perceived as dangerous: something might come up unexpectedly from the other side, so humans stay away from edges more often than not. \end_deeper \layout Description Spiral\SpecialChar ~ In\SpecialChar ~ &\SpecialChar ~ Out A behavior that occurs only amongst advanced robots. Difficult for humans, because it needs very precise navigation, robots discovered it at some point and now is a resource strongly correlated with better performance. \layout Standard \added_space_top bigskip Altogether, we have found that the set of behaviors we have been analyzing has provided us with interesting measures of robot and human evolution and learning. Some of them are typical of the \begin_inset Quotes eld \end_inset robot \begin_inset Quotes erd \end_inset species: more tight turns, more crossings of the screen's edges, diagonals produced by quickly alternating turns. \layout Standard Zigzag is a unique problem in that it seems about equally important, and equally difficult for agents and humans alike. Zigzagging is fundamental for split endgames, when both players are trying to save space, waiting for the other to make a mistake. \layout Standard Some behaviors occur mostly at specific levels of expertise: Spiraling and asymmetry are typical of novice agents, whereas in-out spirals and edge following are characteristic behaviors of advanced agents. Among humans, tight turns and edge crossings are common tools of expert players. \layout Standard None of these behaviors had more frequency on humans than robots. Perhaps our choice of 12 sample behaviors was biased by our observations of how agents behave, rather than humans. But it is also interesting to reflect on the fact that human behavior is more complex, more changing, so it is difficult to find fixed patterns that occur very often. Several behaviors have much larger frequencies amongst agents than humans: staircase, edge following, and frequency of turns. \layout Standard This last characteristic, lower human frequency of turns, we conjecture is related to a fundamental difference on the way that agents and humans approach the game. Agents are reactive, they read their sensors and act immediately. Humans switch between different attention modes: they exploit safe situations, where they can go straight for a while without interruptions, to look at the opponent's behavior, examine remote areas of the board, study the current topology of the game situation, and make plans for the future. Even though strategically it makes no difference, a human would rarely do a diagonal, quickly pressing the left and right keys while his/her attention is analyzing remote areas of the screen. A person can perform a diagonal with equal efficiency than a robot, but at the cost of concentrating all attention on the narrowest area, maintaining a precise coordination of turns and trajectory. \layout Subsection Maze Navigation \layout Standard There is no problem solving in nature, just adaptation. A frog, evolutionary biologists may argue, is not \begin_inset Quotes eld \end_inset a solution to the problem of being a frog \begin_inset Quotes erd \end_inset , and it is not appropriate to say for example that it has solved the problem of jumping, or \begin_inset Quotes eld \end_inset being green \begin_inset Quotes erd \end_inset . In the same vein, none of the behaviors we have observed among Tron agents have evolved deliberately, but rather as a consequence of the fight for survival. \layout Standard Tron agents perform known basic robotics behaviors, such as obstacle avoidance or wall following, not because they have solved those problems, but rather as a consequence of evolving for survival. \layout Standard Figure \begin_inset LatexCommand \ref{fig.maze} \end_inset shows a Tron agent that has been inserted on a maze. This agent visits some of the various passages, backtracks, then finally finds the exit and leaves. Approximately one every 10 evolved agents is able to find the exit to this particular maze. But the reason they do so is a need for survival, for there was never any payoff to do it. \layout Standard The fact that the agent actually leaves the maze through the exit is particularl y interesting. Why leave? Humans observing this behavior might interpret that there is a will to escape, a need for freedom; but on a deeper sense these are just consequences, \emph on as all animal behaviors are, \emph default of their being adapted to a competitive environment. \begin_float fig \layout Standard \align center \begin_inset Figure size 357 354 file graph/m2r4150000.eps width 3 60.00 flags 11 \end_inset \layout Standard \latex latex \backslash caption[A Tron agent navigates out of a maze]{ \latex default \begin_inset LatexCommand \label{fig.maze} \end_inset A Tron agent navigates out of a maze. It uses its own traced movements to explore until it finds the exit. There was never a purpose or explicit fitness reward for navigating mazes; instead, this agent behaves in this way as a result of its adaptation to the environment of Tron. The agent leaves the maze through the exit only because it has evolved to avoid confined spaces. \latex latex } \end_float \layout Section Discussion \layout Subsection Adapting to the Real Problem \layout Standard We use a state-of-the art evolutionary algorithm, continuously being trained by self-play, as our novelty engine; but the players generated have a broad RS distribution: some of them are very good against humans and others are very bad. In all, even with feedback from the human results (by using champions as trainers, or later, by allowing champions to reproduce) the average RS of the robots produced is below the performance of Tron as a whole (section \begin_inset LatexCommand \ref{sec.control} \end_inset ). \layout Standard A Tron playing system relying solely on self-play would not be able to improve beyond this rate. \emph on It was the power of selection coming from interaction with a live human population that drove the system up to an expert level. \layout Subsection Evolution as Mixture of Experts \layout Standard As perceived by an individual user, our virtual Tron plays differently every time, as agents are switched before each game. Simultaneously, due to the evolutionary process, the overall level of play increases. This heterogeneous behavior is part of the success; the strength of an individual strategy is valid only \emph on given the collective behavior of all other agents --- \emph default if the same strategy were used over and over, humans would quickly adapt and the artificial opponent would appear boring and repetitive. This amounts to a \emph on mixture of experts \emph default architecture \begin_inset LatexCommand \cite{jacobs91b} \end_inset , but here the mixture is a consequence of evolution, of agents exploiting different niches created by their opponents. No single strategy can dominate, as long as there are humans who learn to respond to it, bringing down its fitness, making the way for new ones to take its place. \layout Standard An interesting question for further study is to look for those emergent niches: is it possible that some agents may have adapted to specific subsets of humans? It is conceivable for example, that some agents are better against people with certain styles --- novices for example, or aggressive players. \layout Subsection Human-Machine Coevolution \layout Standard The word \emph on coevolution \emph default is used in computer science literature to describe relative fitness situations, where an individual's value depends upon the population itself. But the present work is the first example, to the best of our knowledge, of coevolution between an agent and an animal species. Agents are selected, through the fitness rules coded into the system, based only on their interaction with humans. \layout Comment Red Queen \layout Standard With Tron we are proposing a new paradigm for evolutionary computation: creating niches where agents and humans interact, leading to the evolution of the agent species. There are two main difficulties introduced when one attempts this type of coevolution against real people: \layout Itemize Interactions with humans are a sparse resource. \layout Itemize Opponents are random and known tournament techniques for coevolution become infeasible. \layout Standard The first problem is common to all applications that wish to learn from a real, or even simulated, environment: interactions are slow and costly. We address this problem by nesting an extra loop of coevolution: while the system is waiting for human opponents, it runs many generations of agent-agent coevolution. \layout Standard The second problem led us to develop a new evaluation strategy, based on the paired comparisons statistics. With it we were able to successfully select the best strategies, pushing the system to the level of a top 3% human. \layout Standard The differences between self evaluation and human evaluation, studied in section \begin_inset LatexCommand \ref{sec.control} \end_inset , indicate, on the one hand, that evolving Tron agents by playing each other was not sufficient, as the top agents are usually not so special against people. But on the other, some of them are good, so expertise against other robots and expertise against people are not independent variables either. \layout Standard We think that this is the general case: evolutionary computation is useful in domains that are not entirely unlearnable; at the same time, there is no substitute for the real experience: simulation can never be perfect. \layout Standard We have also been able to show here, how most humans --- at least those who stay for a while --- learn from their interaction with the system; some of them quite significantly. Even though the system was not designed as a training environment for people, but rather simply as an artificial opponent, the implications for human education are exciting: evolutionary techniques provide us with a tool for building adaptive environments, capable of challenging humans with increased efficiency by interacting with a large group of people. \layout Subsection Human Motivations \layout Standard The dynamics of the human population are complicated. New players arrive at a steady pace, but at the same time many veterans keep coming back (fig. \begin_inset LatexCommand \ref{f.composition} \end_inset ), resulting in a relatively stable experience distribution. The median is 87 games, meaning that half of the games are played by users with a previous experience of 87 or more matches (25% with 387 or more). \layout Standard The uniquely adaptive quality of the Tron web site is one of the reasons for such enthusiasm. One of our visitors described it in an eloquent e-mail message: \layout Quote ``I can actually see that the best robots now are better than the best robots of yesterday. (Specifically, all of a sudden when I logged in at 7PM yesterday, I could swear that there were sentient beings behind some of the robots)'' \begin_float footnote \layout Standard M. Jacobs, 1998. \end_float . \layout Comment Internet Niches \layout Comment Human-agent interactions on the grand scale of the Internet may be fertile ground for evolutionary software, but the situations must be mutually beneficia l. In the present case, humans receive renewed challenge through the changing strategies of the Tron system, which in turn uses those precious bits of information to evaluate its agents. The system opened up a ``virtual niche'' for agents and humans to inhabit. \layout Chapter \begin_inset LatexCommand \label{chapter.conclusions} \end_inset Conclusions \layout Section Discovery in AI \layout Standard Intelligence defined as symbolic reasoning was the foundation of the first works in AI: playing chess, solving logic problems, following formal rules, were thought to epitomize intelligent behavior. Reasoning capacity was traditionally considered to be the difference between intelligent Man and unintelligent animal. \layout Standard Doug Lenat \emph on \emph default claimed that his \emph on Automated Mathematician \emph default (AM) program \begin_inset LatexCommand \cite{lenat77} \end_inset , seeded with 115 elementary set theory concepts, was able to \begin_inset Quotes eld \end_inset discover \begin_inset Quotes erd \end_inset natural numbers and formulate interesting concepts in basic number theory such as addition, multiplication, etc.; even prime numbers. Lenat thought that the fundamental rule of intelligence, namely \emph on heuristic search \emph default , had been found. The follow-up project, EURISKO, would discover a domain's heuristics by itself, thus enabling discovery in any field. To discover mathematics for example, one should be able to run EURISKO with the initial axioms, and the program would eventually find both the subject's heuristics and facts, each one reinforcing the other. Lenat's hopes failed, though, and EURISKO did not live up to its expectations \begin_inset LatexCommand \cite{lenat84} \end_inset . From this and other failures, AI shifted focus, over the ensuing decades, towards programmed expertise rather than discovery. \layout Standard By showing how evolutionary entities find and exploit emergent properties of reality, we go back to Lenat's idea of AI as discovery. From the human perspective, complex is what is not obvious, what is entangled and difficult; emergent properties are the complex ones, those that need intelligence to be discovered and assimilated. With a growing understanding of what complexity and emergence are, and how they are generated, Artificial Life methods bring a new perspective on discovery as adaptation. \layout Standard The goal of AI should not be to program situated agents, but to make them adaptive. Manually coding the program with all the information an organism needs becomes infeasible because it is too much --- and because of the Red Queen problem: by the time we finish, the environment has changed. The code for a complete real agent, a horse for example, may well be impossible to write. Even if we knew how to, a team of programmers could not debug so many interdepe ndent lines of code \begin_inset LatexCommand \cite{pollack99nasa} \end_inset . But an adaptive agent, as natural evolution shows, is capable of doing so. \layout Section From Discovery to Abstraction \layout Standard ALife is founded upon a different paradigm than classic AI: it considers human intelligence as a small part logic, and a large part interaction with the habitat --- embodiment. Evolutionary methods have shown the potential to develop artificial entities adapted to complex habitats and discover their rules. This is, however, only part of the problem, because it is not known how to abstract those found rules and incorporate them into the agent as modules, as new words in the language. \layout Standard Here we have shown that recombination plays a fundamental role, acting as a simple way of finding and reusing higher-level descriptions and subsolutions. One of the reasons why agents can find and exploit emergent rules on their domains is that there is a partial reduction of complexity coming from the crossover operator, which replicates useful components at random. The question for the future is: how can these emergent rules be assimilated by the agent? ALife has only started to look at this problem, sometimes referred to as the \emph on modularity \emph default problem \begin_inset LatexCommand \cite{angeline94,juille96b} \end_inset . \layout Standard The bulk of evidence coming from ALife work, including the one described here, supports the g-t-r hypothesis of Universal Darwinism: it is plausible that selection and recombination, in the scope of a challenging environment, can lead to increasing levels of complexity. But it also shows that this is still a crude model of evolution. Two big questions remain: \layout Itemize How are discoveries assimilated into higher level descriptions? \begin_deeper \layout Standard Take the genome of mammals as an example. It is organized to protect a core part of the genotype, while encouraging mutation on regulation factors. The result is a basic template that allows the exploration of morphology without changing the basic components \begin_inset LatexCommand \cite{carroll00} \end_inset . Horizontal gene transfer, which leads to inter-species recombinations, has been controlled by sexual reproduction, to make it happen only within the species. Thus not only emergent complex components have been found, such as organs, but they have been incorporated into the representation, and the language of mutation and recombination itself has been reformulated. \end_deeper \layout Itemize How can evolution be described and studied at the level of whole systems instead of agent-environment interaction? \begin_deeper \layout Standard Coevolution (as a subfield of evolutionary computation) has obtained interesting results that could be pointing in the right general direction. These experiments do not have a drastic agent/environment distinction. Instead, the environment is the result of the collective behavior of the population. This configuration, when successful, creates a continuous challenge at the right level, leading to agents that climb the ladder of complexity. Coevolution thus breaks the first mold, that of a changing agent in a rigid environment. But real evolution involves simultaneous co-adaptation throughout all levels of organization, from the individual gene to the symbiotic association of species. \end_deeper \layout Standard Expanded views of evolution, both from biology \begin_inset LatexCommand \cite{maynardsmith97,lewontin00,margulis93} \end_inset and ALife \begin_inset LatexCommand \cite{watson00} \end_inset that look at collective evaluations, symbiosis and cooperations effects, and \begin_inset Quotes eld \end_inset evolution of evolvability \begin_inset Quotes erd \end_inset \begin_inset LatexCommand \cite{dawkins96,carroll00} \end_inset point towards the more general understanding of natural and artificial evolution that is necessary to address these problems. \layout Section The Humans in the Loop \layout Standard With the reciprocal learning environments presented in this thesis, we have described new ways to exploit the enormous potential of feedback loops between human intelligence and evolutionary methods. The \begin_inset Quotes eld \end_inset blind watchmaker \begin_inset Quotes erd \end_inset algorithms \begin_inset LatexCommand \cite{dawkins87,sims91} \end_inset , and TD-Leaf's induction of the relative values of chess figures from games against humans \begin_inset LatexCommand \cite{baxteretal98} \end_inset were previous indications of this potential. \layout Standard \begin_inset LatexCommand \label{disc.creativity} \end_inset EvoCAD (section \begin_inset LatexCommand \ref{sec.evocad} \end_inset ) shows how a design tool can employ AI to generate creative solutions for engineering problems. Researchers in design usually reject the concept of artificial creativity, yet the diverse characteristics of computer and human problem-solving lead to solutions that are radically different. If our experiments can be described as generating surprise and innovation \begin_inset LatexCommand \cite{ronald00} \end_inset then the goal of artificial creativity might not be impossible, after all. \layout Standard In EvoCAD, human and machine take turns in trying to bring a design closer to a final goal. But Tron puts human and machine in a collaboration of a larger scale. \layout Comment We see great promise in software evolving while being used by a large number of people. \layout Standard The cooperative effect of large groups of humans working together on the Internet is known, but Tron is the first example of an adaptive system that harvests voluntary contributions of intelligence from its users. The technique also induced learning in humans, suggesting that the coevolutiona ry dynamics can produce new kinds of educational and entertainment environments through coadaptation between machines and humans. Sklar and Pollack \begin_inset LatexCommand \cite{sklar00} \end_inset have begun an effort to create educational environments for people based on the type of mutually adaptive challenge first demonstrated by Tron. \layout Standard The Internet is a new kind of environment where people and software interact in an unprecedented scale. Thus the potential for a new kind of intelligent software that --- as exemplifi ed by our Tron domain --- thrives on the niches of a virtual ecology that mixes natural and artificial life forms. \layout Section The Reality Effect \layout Standard We have described in detail some of the solutions encountered by our test domains: the appearance of nested levels of complexity in Lego structures, the reuse and adaptation of components, the emergence of basic navigation behaviors such as wall-following, spiraling, maze navigation and space filling, amongst Tron agents. \layout Standard The Brooksian idea that an agent's complexity sometimes comes from the environme nt more than the agent itself is supported by the evidence of Tron robots: these stateless agents have no internal means for storing plans or previous decisions, yet were shown (section \begin_inset LatexCommand \ref{sec.emergentbehaviors} \end_inset ) to reliably evolve behaviors involving choreographed sequences of moves. \layout Comment Applications and the Future \layout Standard By adapting to the real problem, rather than a metaphor or an incomplete simulation, the applied aspect of evolutionary methods comes to life, which could lead to a variety of applications. \layout Standard Fully Automated Design, the idea of computers designing complete, functional artifacts, based on constraints and goals defined externally, was shown here with Lego structures. Lipson and Pollack extended this idea by showing how a static motion simulator can be used to coevolve morphology and brain of walking creatures \begin_inset LatexCommand \cite{lipson00} \end_inset . Automated design is central to evolutionary robotics, for brains need bodies to inhabit, as well as evolutionary design, which needs to break the mold of pre-imposed problem decomposition, and play more freely with components and goals. \layout Standard Together with work by other researchers such as Sims and Thompson our thesis deals with what we have called \emph on the reality effect \emph default : when evolution interacts with a large, complex environment like those typically generated by the world around us, complex solutions appear that exploit emergent properties of the domain in surprising new ways. \layout LaTeX \backslash singlespace \layout Standard \begin_inset LatexCommand \BibTeX[thesis]{pablo} \end_inset \layout LaTeX \backslash end{doublespace} \the_end