Autonomous Multirobot Excavation for Lunar Applications Jekanthan Thangavelautham Kenneth Law School of Earth and Space Exploration David Schaeffer and Associates Arizona State University Markham, ON, Canada 781 E Terrace Mall, Tempe, AZ 85287 7 [email protected] 1 0 2 Terence Fu Nader Abu El Samid University of Toronto MDA Space Missions n a 4925 Dufferin Street, Toronto, Ontario, Canada M3H 5T6 9445 Airport Road J Brampton, ON, Canada L6S 4J3 6 ] Alexander D.S. Smith O University of Toronto R 4925 Dufferin Street, Toronto, Ontario, Canada M3H 5T6 . [email protected] s c [ Gabriele M.T. D’Eleuterio 1 University of Toronto v 4925 Dufferin Street, Toronto, Ontario, Canada M3H 5T6 7 [email protected] 5 6 1 0 Abstract . 1 0 7 1 In this paper, a control approach called Artificial Neural Tissue (ANT) is applied to mul- : tirobot excavation for lunar base preparation tasks including clearing landing pads and v i burying of habitat modules. We show for the first time, a team of autonomous robots exca- X vating a terrain to match a given 3D blueprint. Constructing mounds around landing pads r willprovidephysicalshieldingfromdebrisduringlaunch/landing. Buryingahumanhabitat a modules under 0.5 m of lunar regolith is expected to provide both radiation shielding and maintain temperatures of -25 oC. This minimizes base life-support complexity and reduces launch mass. ANT is compelling for a lunar mission because it doesn’t require a team of astronauts for excavation and it requires minimal supervision. The robot teams are shown to autonomously interpret blueprints, excavate and prepare sites for a lunar base. Because little pre-programmed knowledge is provided, the controllers discover creative techniques. ANTevolvestechniquessuchasslot-dozingthatwouldotherwiserequireexcavationexperts. This is critical in making an excavation mission feasible when it is prohibitively expensive to send astronauts. The controllers evolve elaborate negotiation behaviors to work in close quarters. These and other techniques such as concurrent evolution of the controller and team size are shown to tackle problem of antagonism, when too many robots interfere re- ducing the overall efficiency or worse, resulting in gridlock. While many challenges remain with this technology our work shows a compelling pathway for field testing this approach. 1 Introduction Socialinsectssuchasacolonyofantsexcavatinganetworkoftunnelsorswarmsoftermitesbuildingtowering cathedral mounds with internal heating and cooling shafts (Bristow and Holt, 1997) show the potential of multi-agentsystemsinbuildingrobuststructures. Thesesocialinsects,withoutanycentralizedcoordination produce emergent collective behaviors used to build these robust structures. Multiple individuals working in a decentralized manner offers some inherent advantages, including fault tolerance, parallelism, reliability, scalability and simplicity in robot design (Cao et al., 1997). Using this bio-inspiredmethod, teams of autonomous robots can construct key elements of a human habitat on the moon (Figure 1). They can work continuously in harsh environments making them very productive, are fault tolerant to the failure of individual robots and are scalable depending on the task complexity and schedule. Robots do not require life-support infrastructure that would otherwise be required for a team of astronaut workers. Furthermore, robots may be required for certain tasks due to concerns of health and safety of the astronauts. Combining these factors, our studies show use of teams of autonomous robots insteadofastronautscanreducelaunchcostby50%(AbuElSamidetal.,2008)forlunarbaseconstruction. This can free ground operators from constantly tending to the multirobot team. In this architecture it will be possible for operators on the ground to have total oversight over the activities of the robot team and intervene and recover from mishaps or unexpected events. Constructingmoundsaroundlandingpadswillprovidephysicalshieldingfromdebrisduringlaunch/landing. Burying a human habitat modules that under 0.5 m of lunar regolith is expected to provide both radiation shielding and maintain comfortable temperatures of -25 oC (based Apollo 17 manual excavation experi- ments)(Heiken et al., 1991). Figure 1: Artist Impression of a Lunar Base and Mining Facility (courtesy NASA). Earth-based teleoperation systems have been proposed for control of robots on the moon (Lee and Spong, 2006). SuchsystemshavebeendemonstratedsuccessfullywiththeLunakhod1and2rovermissions;however latency (time delay) induced prolonged fatigue was a concern for the Lunakhod missions. Latency induced operatorfatigueisstillaconcernwhencoordinatingactionswithteamsofrobotsoverextendedtime(Miller and Machulis, 2005). Advancements have been made coordination and control of multiple robots using teleoperation (Lu et al., 2015; Khademian and Hashtrudi-Zaad, 2011). However these techniques have yet to be tested for spacecraft or robots at the Moon. The proposed ANT architecture allows ground control oversight and frees ground operators from mundane taskswhilereservingallbutthemostdelicateandmissioncriticaltasksforhumaninterventionthusreducing thechanceoffatigueandhumanerror. Thesefactorsmakeanautonomousroboticsystemwithteleoperation capability more appealing than teleoperation alone. This approach permits having a base deployed and operationalintimeforastronautstoarrivefromEarth. Majorapproachestodevelopingautonomouscontrol systems utilize human knowledge, machine learning techniques or a combination of both. Humanknowledge-basedcontrolstrategiesrelyonhumaninputintheformofad-hoccontrolrules, physical model based planners, task-specific assumptions, and human knowledge (Bernard et al., 1999; Xidias et al., 2016). In many tasks that use multiple robots, it is often unclear of how best to plan the task, organize the group and determine the best interaction behaviors to complete the task. In lunar and planetary environments, task-specific assumptions may not be valid in-situ. The surface properties and material may vary from crater to crater. One or more robots may be disabled unexpectedly or need to perform tasks that have not been envisioned during mission planning and modeling stages. These factors make an adaptive, decentralized controls approach to reorganize and control a group of robots more appealing. Anovel, roboticlearningcontrolsapproachispresentedherethataddressesthesechallenges. Thisapproach requires much less human knowledge than conventional approaches. The controllers are homogenous (i.e., a single controller is replicated for use on each robot), decentralized and make use of local sensor data. Hardwareimplementationsofthesystemutilizeasharedresourcesuchasanoverheadcameraforlocalization or TriDAR for 3D mapping and hence the system is not truly decentralized but the system can be made decentralized by utilizing multiple shared resource. The approach learns to solve tasks through a process of trial and error and is given a global objective function, a generic set of basis behaviors, sensory input and a simplified training environment without detailed physical models of the system. The proposed approach requires an accurate localization system. This is possible by mounting cameras and lighting on a tower over the work area. Other options include use of radio beacons that are located from the main landing craft or structure. These two approaches can enable rover localization without requiring a Lunar GPS system. This approach called the Artificial Neural Tissue (ANT) (Thangavelautham and D’Eleuterio, 2005; Thangavelautham, 2008) combines a standard neural network with a novel coarse-coding mechanism in- spired by the work of Albus and Hinton (Albus, 1971; Hinton, 1981). In ANT, coarse coding is used to perform regulatory control of networks (Thangavelautham and D’Eleuterio, 2005; Thangavelautham, 2008; Thangavelautham and D’Eleuterio, 2012). The process occurs through simulated chemical diffusion (Garthwaite et al., 1988; Montague et al., 1991) and enables segmentation of a network, through activation and inhibition of neuronal groups. This allows for modules of neurons to be added, removed and rewired during training facilitating self-organized task decomposition and task-allocation (Thangavelautham and D’Eleuterio, 2012). This method is shown to solve the sign-following task found to be intractable with conventional fixed and variable topology neural network architectures (Thangavelautham and D’Eleuterio, 2005; Thangavelautham and D’Eleuterio, 2012). HerethecapabilitiesofANTareshownformultirobotexcavation(Thangavelauthametal.,2008;Thangave- lautham et al., 2009), a difficult task, with a large, high-dimensional task space. Learning to solve the excavation task, enables the robots to build berms, landing pads and excavate holes for burying the lunar habitat modules. The excavation task combines features of a typical foraging, grazing or cleaning task with ability to plan, interpret blueprints and perform coordinated excavation. Since little pre-programmed knowledgeisgiven, ANTmaydiscovercreativesolutionsproducingcontrollersthatcaninterpretexcavation blueprints, can successfully avoid obstacles, perform layered digging, leveling and avoid burying or trapping other robots. These innovative behaviors are discovered during training and are similar to behaviors used by social insects to perform group coordination. Inthisworkexpandedfrom(Thangavelauthametal.,2008),ANTisfoundtoevolvesuperiorsolutionstothe excavation task in fewer genetic evaluations than hand-coded and conventional neural networks solutions. The ANT solutions are found to be scalable and can be applied to unforseen real world scenarios where one or more robots may become disabled or unavailable. Hand-coded solutions are found to work in single robot scenarios and show poor performance, and robustness for increased number of robots thus lacking adaptivity. The required cooperative behaviors for all but the simplest of tasks are unintuitive and pose difficulty for humans programmers. Conventional neural networks can do better than hand coded solutions but require an experimenter manually decompose a complex task, determine a suitable network topology and activation function to make training tractable. ANT requires even less experimenter input and is useful for multirobot excavation tasks, where there is limited domain knowledge available. The controllers can generalize (interpolate) from limited training scenarios to handle unforseen situations. ANT through a process of coarse-coding can segment high dimensional tasks space more efficiently, performing automated task decomposition and simultaneously finding the required controller network topology, selecting optimal numberofrobotsandcoordinationbehaviorstocompletethetask. Neuronalactivityandbehavioralanalysis of the controllers suggests solutions emerge through a process of trial and error discovery, fine tuning and incremental assembly of ‘building-block’ behaviors to solve tasks. Using this approach we show the feasibility of using multirobot excavation for site preparations tasks. The approach shows improved performance and scalability than conventional neural networks and hand coded solutions. Thisfacilitatesfindingcreativebehaviorsthatarenotspecifiedorencouragedbyanexperimenter. These creative behaviors verified in hardware include correctly interpreting blueprints, performing layered digging, obstacle avoidance and rocking behaviors to avoid getting stuck. This approach is shown to pro- duce controllers that have improved scalability compared to conventional neural networks and hand-coded solutions. Furthermore, ANT can simultaneously evolve the desired controller and select for optimal num- ber of robots for the task. This approach is shown as a possible solution to the problem of antagonism in decentralized multirobot control. The evolved solutions have been analyzed in simulation and the best solutions have been ported onto real robots. Hardware experiments were performed on 3 different robotic platforms, including in the laboratory and under controlled field conditions. These experiments were used to validate individuals behaviors seen in simulation to verifying the overall excavation performance of the controllers. Laboratory hardware experi- ments and controlled field experiments produced promising results that show a promising pathway towards full implementation and demonstration in the field. This article is organized as follows. Section 2 presents related work. Section 3 presents the Artificial Neural Tissue approach. Section 4 presents the excavation task used to demonstrate ANT’s capabilities. This is followed by results and discussion in Section 5 and proof-of-concept experiments in Section 6. 2 Related Work Previousworkinautonomousexcavation(Stentzetal.,1998)hasbeenlimitedtoasinglerobotandseparate loading/unloading vehicles. Digging is performed using hand coded scripts that simplify repetitive excava- tion/truck loading cycles. These controllers are used to position and unload an excavator bucket relative to a dump truck using a suite of sensors onboard the vehicles. Thesescriptsaredevelopedwithinputfromanexperthumanoperatorandmodelvehiclespecificlimitations suchasloadhandlingcapacityandlatency. Thesesystemsincorporateadaptivecoarseandrefinedplannersto sequencediggingoperations(RoweandStentz,1997). Otherworksusedcoarseandrefinedplannercontaining a neural network approach to learn soil conditions and excavator capabilities during operation (Cannon and Singh,1999). Suchsystemsarecomparableinefficiencytohumanoperators. Otherapproachesaredevotedto modelingkinematicsand/ordynamicsoftheexcavationvehiclesandsimulatingtheirperformance(Dunbabin and Corke, 2006). These techniques are designed for specific vehicle platforms and do not include scripts for every possible scenario in the task space thus requiring close monitoring and intervention by a human operator. This makes the approach unsuitable for fully autonomous operation of multiple robots on the moon. Control systems such as LUCIE are more sophisticated and incorporate long-term planning (Bradley and Seward, 1998). Apart from identifying and automating excavation cycles, the system incorporates a whole sequence of intermediate goals that need to be achieved to complete a trench digging task. However, the system lacks autonomy because the task is decomposed and prioritized by a human operator. Other techniques closely mimic insect in there ability to build road ways and ramps using amorphous construction. A laboratory robot is used to heat, melt and deposit foam to produce a ramp and other complex structures (Napp and Nagpal, 2012). More recent work by Halbach et al. (Halbach et al., 2013) have performed simulations of multiple robots to perform excavation on Mars. The intent is to setup a permanent human base and utilize Martian resources for construction and in-situ resource utilization. The work has focused on human assisted high level planning required to locate a base and key facilities and the process of resource extraction. Human assistance is utilized in planning the high level tasks and giving execution orders to the multiple robots. It is presumed human astronauts are already located on Mars and can perform tele-operation on site (from a safe distance). Recent work by (Skonieczny and Wettergreen, 2016) have show bucket wheels to be the most effective excavation platform for low gravity on the Moon. As will be shown later, our results also show bucket wheels to be most efficient for excavation. The construction of a human habitat on the moon will require multiple excavation robots working towards a given goal. Collective robotics is well suited because it incorporates multiple autonomous robots that work cooperatively towards a global goal. Some collective robotic controllers mimic mechanisms used by social insects to perform group coordination. These include the use of self-organization, templates and stigmergy. Self-organization describes how macroscopic behavior emerge solely from numerous interactions among lower level components of the system that use only local information (Bonabeau et al., 1997) and is the basis for the bio-inspired control approach presented here. Templates are environmental features perceptible to individuals within the collective (Bonabeau et al., 1999). In robotic applications, template- based approaches include use of light fields to direct the creation of linear (Stewart and Russell, 2003) and circular walls (Wawerla et al., 2002) and planar annulus structures (Wilson et al., 2004). Spatiotemporally varying templates (e.g., adjusting or moving a light gradient over time) have been used to produce more complex structures (Stewart and Russell, 2004). Stigmergyisaformofindirectcommunicationmediatedthroughtheenvironment(Grass´e,1959). Stigmergy has been used extensively in collective-robotic construction, including blind bulldozing (Parker et al., 2003), box pushing (Matari´c et al., 1995), heap formation (Beckers et al., 1994) and tiling pattern formation (Thangavelautham et al., 2003). However conventional collective robotics control approaches have two limitations. First, they rely on either user-defined deterministic “if-then” rules or on stochastic behaviors. It is difficult to design controllers by hand with cooperation in mind, as we show later in the paper, because there exists no formalisms to predict or control the global behaviors that will result from local interactions. Designing successful controllers by hand can devolve into a process of trial and error. The second limitation is that these approaches can suffer from an emergent feature called antago- nism (Chantemargue et al., 1996) when multiple agents trying to perform the same task interfere with one another, reducing the overall efficiency of the group or worse, result in gridlock. This limits scalability of the solution to number of robots and size of the task area. Because the approach presented here is evolutionary in nature, it “learns” to exploit the mechanisms de- scribed earlier to find creative solutions to a task. As with other evolutionary algorithms, the approach is stochasticandcannotguaranteeasolutioninfinitetime. However,aswillbepresentedlater,thecontrollers converge to solution with a probability of 93% at the optimal training settings. The presented method is able to mitigate the effects of antagonism, which is difficult to do with conventional approaches due to lack of domain knowledge of a task at hand. Ameansofreducingtheeffortrequiredindesigningcontrollersbyhandistoencodecontrollersasbehavioral look-uptablesandallowageneticalgorithmtoevolvethetableentries. Thisapproachisusedtosolveaheap formation task in (Barfoot and D’Eleuterio, 1999) and a 2×2 tiling formation task in (Thangavelautham et al., 2003). A limitation with look-up tables is that they have poor sensor scalability, as the size of the look-up table is exponential in the number of inputs. Look-up tables also have poor generalization. Neural network controllers perform better generalization since they effectively encode a compressed representation of the table. Neural networks have been successfully applied on multirobot systems and have been used to build walls, corridors, and briar patches (Crabbe and Dyer, 1999) and for tasks that require communication and coordination (Trianni and Dorigo, 2006). Neural network controllers have been also been used to solve 3×3 tiling task (Thangavelautham and T., 2004). Going from the 2×2 to the 3×3 tiling formation task, results in a search space of 10145 to 101300 respectively. Thisverylargeincreaseinsearchspacepreventsalookuptablefromfindingasuitablesolution. However because a neural network can generalize better it finds a desired solution. In standard neural networks, communication between neurons is modeled as synaptic connection (wires) that enable electrical signalling. Other fixed topology networks such as Gasnet model both electrical and chemical signalling between neurons (Husbands, 1998). However, when using fixed-topology networks, the size of the network must be specified ahead of time. Choosing the wrong topology may lead to a network that is difficult to train or is intractable (Jacobs et al., 1991; Thangavelautham and D’Eleuterio, 2005). Variable length neural network methodologies such as NEAT (NeuroEvolution of Augmenting Topologies) show the potential advantage of evolving both the neuron weights and topology concurrently (Stanley and Miikkulainen, 2002). It is argued that growing the network incrementally through (‘complexification’) helps minimize the dimensional search space and thus improve evolutionary performance (Stanley and Miikku- lainen,2002). Thisrequiresstartingwithasmalltopologyandgrowingitincrementallythroughevolutionary training which can be slow. TheANTframeworkpresentedhereisabio-inspiredapproachthatsimultaneouslyaddressesboththeprob- lems in designing rule-based systems by hand and the limitations inherent in previous fixed and variable topology neural networks. Unlike previous models like Gasnet (Husbands, 1998), chemical communica- tion within ANT enables it to dynamically add, remove and modify modules of neurons through coarse coding. This facilitates segmentation of the search space to perform self-organized task decomposition (ThangavelauthamandD’Eleuterio, 2012). Thisalsoprovidesgoodscalabilityandgeneralizationofsensory input (Thangavelautham and D’Eleuterio, 2005). ANT is more flexible than NEAT. It can be initialized with a large number of neurons without the need for incremental ‘complexification’ (Thangavelautham and D’Eleuterio, 2012). As will be shown later, ANT does not rely on detailed task-specific knowledge or detailed physical models of the system. It evolves controllers to optimize a user-specified global objective (fitness) function. The evolutionary selection process is able to discover for itself and exploit templates, stigmergy and mitigate the effects of antagonism. 3 Artificial Neural Tissue ANT(ThangavelauthamandD’Eleuterio,2005;Thangavelautham,2008;ThangavelauthamandD’Eleuterio, 2012) is a neural networks approach trained using evolutionary algorithms. ANT is applied in this paper as the controller for the robot exacavator(s). It consists of a developmental program encoded into an artificial genome composed of a set of genes to construct a three-dimensional artificial neural tissue. Inspired by neurobiology, ANT models chemical communication in addition to electrical communication along axons. Some neurons release chemicals that travel by diffusion and are read by other neurons, in essence serving as a ‘wireless’ communication system to complement the ‘wired’ one. This chemical communication scheme is used to dynamically activate and inhibit network of neurons. The tissue consists of two types of neural units, decision neurons andmotor-control neurons, orsimplymotorneurons. Assumearandomlygenerated set of motor neurons in a tissue connected by wires (Figure 2a). Chances are most of these neurons will produce incoherent/noisy output, while a few may produce desired functions. If the signal from all of these neurons are summed, then these “noisy” neurons would drown out the output signal (Figure 2b) due to spatial crosstalk (Jacobs et al., 1991). Figure 2: In a randomly generated tissue, most motor neurons would produce spurious/incoherent output (a) that would ‘drown out’ signals from a few desired motor neurons due to spatial crosstalk (Jacobs et al., 1991) (b). This can make training intractable for difficult tasks. Neurotransmitter (chemicals) emitted by decision neurons (c) selectively activate networks of desired motor neurons in shaded regions (i) and (ii) by coarse-coding overlapping diffusion fields as shown (d). This inhibits noisy motor neurons and eliminates spatial crosstalk (e). Within ANT, decision neurons emit chemicals that diffuse omnidirectionally shown shaded (Figure 2d). Coarse coding is a distributed representation that uses multiple overlapping coarse fields to encode a finer field (Albus, 1971; Hinton, 1981). By coarse-coding multiple overlapping diffusion fields, the desired motor neurons can be selected and spurious motor neurons inhibited. With multiple overlapping diffusion fields (Figure 2d) shown in shaded region (ii), there is redundancy and when one decision neuron is modified (i.e. due to a deleterious mutation) the desired motor neurons are still selected. In the following section, the computational mechanisms within the tissue is described first, followed by description of how the tissue is created. 3.1 Motor Neurons Motor neuron, N occupies the position λ=(l,m,n)∈Z3 (Figure 3) and is arranged in a lattice structure. λ Dependingontheactivationfunctionsused,thestates ∈Softheneuroniseitherbinary,i.e.,S ={0,1} λ bin or can be real, S =[0,1] or S =[−1,1]. p r Figure 3: Synaptic connections between ANT motor neurons from layer l+1 to l. Each motor neuron N receives input from neurons N where κ ∈⇑(λ), the nominal input set. These λ κ nominal inputs are the 3×3 neurons centered one layer below N ; in other terms, ⇑(λ) = {(i,j,k)|i = λ l−1,l,l+1; j =m−1,m,m+1; k =n−1}. The sensor data are represented by the activation (state) of the sensor input neurons N ,i = 1...m, αi summarized as A = {s ,s ...s }. The network output is represented by the activation (state) of the α1 α2 αm output neurons N ,j = 1...n, summarized as Ω = {s ,s ,s ...s }, where q = 1...b specifies the ωj ω11 ω12 ω23 ωbn output behavior. Each output neuron commands one behavior of the robot. (In the case of a robot, a typical behavior may be to move forward a given distance. This may require the coordinated action of several actuators. Alternatively, the behavior may be more primitive such as augmenting the current of a given actuator.) If sωq = 1, output neuron ωj votes to activate behavior q; if sωq = 0, it does not. Since j j multiple neurons can have access to a behavior, an arbitration scheme is imposed to ensure the controller is deterministic where p(q)=(cid:80)n γ(s ,q)s /n and n =(cid:80)n γ(s ,q) is the number of output neurons j=1 ωi ωi q q j=1 ωi j j j connected to output behavior q where γ(s ,q) is evaluated as follows: ωi j (cid:26) 1, if i=q γ(s ,q)= (1) ωij 0, otherwise andresultinginbehaviorq beingactivatedifp(q)≥0.5. Oncethebehaviorsareactivatedtheyareexecuted in a a priori sequence. 3.2 The Decision Neuron Decision neurons occupy nodes in the lattice as established by their genetic parameters (Figure 4). These neurons excite into operation or inhibit the motor control neurons (shown as spheres) by excreting an activation chemical. Once a motor control neuron is excited into operation, the computation outlined in (3) is performed. Figure 4: Coarse coding regulation being performed by two decision neurons (shown as squares) that diffuse a chemical, in turn activating a motor neuron column located at the center (right). Each decision neuron can be in one of two states, diffuse a neurotransmitter chemical or remain dormant. The state of a decision neuron T , s , is binary and determined by one of the activation functions (see µ µ Section 3.3). The inputs to T are all the input sensor neurons N ; i.e., s = ψ (s ...s ) where σ = (cid:80) vµs /(cid:80) s and vµµare the weights. The decision neuronαis dormaµnt if sµ =α10 andαrmeleases a µ α α α α α α µ neurotransmitter chemical of uniform concentration c over a prescribed field of influence if s =1. µ µ The decision neuron’s field of influence is taken to be a rectangular box extending ±dr, where r =1,2,3,..., µ fromµinthethreeperpendiculardirections. Thesethreedimensionsalongwithµandc ,theconcentration µ level of the virtual chemical emitted by T , are encoded in the genome. µ Motor control neurons within the highest chemical concentration field are excited into operation by the decision neurons, while all others remain dormant. Owing to the coarse coding effect, the sums used in the weighted input of (2) are over only the set ⇑(λ)⊆⇑(λ) of active inputs to N . Likewise the output of ANT λ is Ω⊆Ω. 3.3 Activation Function Each neuron, motor and decision uses a modular activation function. This allows selection among four possible threshold functions of the weighted input σ. The use of two threshold parameters allows for a single neuron to compute the XOR function, in addition to the AND and OR functions. For this activation function, (cid:26) 0, ifσ ≥θ ψ (σ) = 1 down 1, otherwise (cid:26) 0, ifσ ≤θ ψ (σ) = 2 up 1, otherwise (2) (cid:26) 0, min(θ ,θ )≤σ <max(θ ,θ ) ψ (σ) = 1 2 1 2 ditch 1, otherwise (cid:26) 0, σ ≤min(θ ,θ ) or σ >max(θ ,θ ) ψ (σ) = 1 2 1 2 mound 1, otherwise where θ ,θ are threshold parameters and θ ,θ ∈ R. The weighted input σ for neuron N is nominally 1 2 1 2 λ λ taken as (cid:80) wκs κ∈⇑(λ) λ κ σ = (3) λ (cid:80) s κ∈⇑(λ) κ with the proviso that σ = 0 if the numerator and denominator are zero. Also, wκ ∈ R is the weight λ connecting N to N . These threshold functions are summarized as κ λ ψ = (1 − k )[(1 − k )ψ + k ψ ] + k [(1 − k )ψ + k ψ ] (4) 1 2 down 2 up 1 2 ditch 2 mound wherek1,k2∈0,1. Theactivationfunctionisthusencodedinthegenomebyk ,k thethresholdparameters 1 2 θ and θ . 1 2 3.4 Evolution and Development A population of artificial neural tissues are evolved in an artificial Darwinian manner. The ‘genome’ for a tissue contains a ‘gene’ for each cell with a specifier D used to distinguish between motor control neuron, decision neuron and tissue. A constructor protein (an autonomous program) interprets the information encoded in the gene (Figure 5) and translates this into a cell descriptor protein. The gene ‘activation’ parameterisabinaryflagresidentinallthecellgenesandisusedtoeitherexpressorrepressthecontentsof thegene. Whenrepressed,adescriptorproteinofthegenecontentisnotcreated. Otherwise,theconstructor protein ‘grows’ a cell. Each cell position is specified in reference to a seed-parent address. A cell-death flag determineswhetherthecellcommitssuicideafterbeinggrown. Onceagain,thisfeatureinthegenomehelps in the evolutionary process with a cell committing suicide still occupying a volume in the lattice although it is dormant. Evolution can decide to reinstate the cell by merely toggling a bit through mutation. In turn mutation (manipulation of gene parameters with a uniform random distribution) to the growth program results in new cells being formed through cell division. The rate of mutation occurring on the growth program is specified for each tissue and is dependent on the cell replication probability parameter T . This probability parameter is used to determine whether a new cell is inserted. Cell division requires r Figure 5: ANT gene map showing tissue, motor neuron and decision neuron genes. a parent cell (selected with highest replication probability relative to the rest of the cells within the tissue) and copying m% of the original cell contents to a daughter cell (where m is determined based on uniform random distribution). This models a gene duplication process with the first m% being a redundant copy of an existing gene and the remaining contents being malformed in which a daughter gene adopts some functions from its parent. The tissue gene specifies parameters that govern the overall description of the tissue. This includes “neuron replication probability”, a parameter that govern the probability additional cell genes are created through mutation and the “Neuron Replication Ratio”, that determines the ratio of decision neuron genes to motor neurons genes in the tissue. The “Cell Type” of each new cell is determined based on the ratio of motor controlneuronstodecisionneurons,aparameterspecifiedinthetissuegene. Thenewneuroncanbelocated in one of six neighboring locations (top, bottom, north, south, east, west) chosen at random and sharing a common side with the parent and not occupied by another neuron. Furthermore a seed address is specified, that identifies the seed cell gene which will be used to construct the first cell in the tissue. 3.5 Crossover and Mutation Within ANT, the genome is modular, with each gene defining each neuron’s characteristics. Crossover is the exchange of genes between two parents to form a child. Before crossover, a parent affinity parameter, (cid:36) ∈ {0,1} is chosen at random for each child genome. The affinity parameter is used to establish if each child genome has closer ‘affinity’ to one of its parents (either parent A or parent B). Thus if (cid:36) =0 then the genomehascloser‘affinity’toparentAand(cid:36) =1ifithasaffinitywithparentB. Eachneuronhasaunique position λ=(l,m,n) and a crossover is performed by drawing a plane (with a normal vector parallel to the x or y-axis) separating the tissue. Cell genes on the parent genome located on the side of the plane closer to theoriginiscopieddirectlyontothechildgenomewiththeassociated‘affinity’parameterandtheremaining genesareexchangedbetweentheparentsbasedona‘compatibilitycriterion’(Figure6). Crossoveroperation does not result in arbitrary separation and exchange of gene contents. The ‘compatibility criterion’ imposes the following condition, that the gene for neuron N from parent A λ1 and N from parent B could be exchanged if λ = λ , i.e., have the same position after development and λ2 1 2 only when both genes are expressed or repressed during development. Thus child 1 with (cid:36) = 0 (affinity to parent A) assumes the gene for BN and child 2 with (cid:36) = 1 (affinity to parent B) assumes AN . If the λ2 λ1 compatibility criterion is not met, then no exchange occurs, and thus AN is passed onto child 1 and BN λ1 λ2