Automatic Programming of Agents via Multi-type,Self-Adaptive Genetic Programming Lee Spector, Hampshire [email protected], http://hampshire.edu/lspectorAssistance by Jon KleinOverviewApproach and Critical ElementsTechnologies:Push, PushGP, Pushpop, Breve, SwarmEvolveRecent Results:Emergence of collective/multicellular organizationEnvironmental/genetic stability and adaptationPush/Breve integration v. 0.1Demo:SwarmEvolve 1.5Next StepsApproach & Critical ElementsDesign Approach: Self-adaptive, multi-type geneticprogramming for automated or semi-automated agent design.Critical Elements: Autonomy, coordination, adaptation,control, evolution.Problems: Can agents be automatically generated forcomplex, dynamic environments? Can agents evolve tobecome more adaptable to changing environments?Metrics: Wait time, event response delay, agent lifetime,code parsimony/diversity, evolutionary computational effort,task completion.Toolkit: Push programming language for evolved agentprograms, PushGP genetic programming system, Pushpopautoconstructive evolution system.The Push Programming Language forEvolutionary ComputationGoal: Scale up GP/agents techniques for human-competitiveperformance in complex, dynamic environments.Evolve agents that may use:• multiple data types• subroutines (any architecture)• recursion• evolved control structures• evolved evolutionary mechanismsPush supports all of this using simple, mostly standard GPtechniques.Stack-based language with one stack per type; types includeinteger, float, Boolean, code, child, type, name.PushGPEvolves Push programsusing (mostly) standard GP.Multiple types handled withoutsyntactic constraints.Evolves modules andcontrol structures automatically.Autoconstructive Evolution: PushpopIndividuals make their own children.The machinery of reproductionand diversification (and thereby themachinery of evolution) evolves.Radical self-adaptation.Breve: a 3D Environment for the Simulationof Decentralized Systems and Artificial LifeWritten by Jon Klein, http://www.spiderland.org/breveSimplifies the rapid construction of complex 3D simulations.Object-oriented scripting language with rich pre-defined classhierarchy.OpenGL 3D graphics with lighting, shadows, and reflection.Rigid body simulation, collision detection/response,articulated body simulation.Runge-Kutta 4th order integrator or Runge-Kutta-Fehlmanintegrator with adaptive step-size control.Breve Swarmby Jon Klein, after Craig Reynoldsacceleration =p1*[away from crowding others vector]+p2*[towards world center vector]+p3*[average neighbor velocity vector]+p4*[towards neighbor center vector]+p5*[random vector]SwarmEvolveOn-Line evolution of goal-directed swarmsMultiple speciesp6*[away from crowding other species vector]Randomly moving energy sources:p7*[towards closest energy source vector].Energy costs:• Colliding with one another• Being outnumbered (by species) in neighborhood• Giving birth• Surviving (per simulation cycle)Upon death (energy = 0), parameters replacedwith mutated version of fittest of speciesFitness metric = age * energySwarmEvolve 1.5• Food consumption/growth• Birth near mothers• Corpses• Food sensor, inverse square signal strength• GUI controls and metrics• Feeders redesigned, increased in number• OEF correspondence increasing[view movie]Emergence of collective/multicellularorganizationObserved behavior: a cloud of agents hovers around anenergy source. Only the central agents feed, while the othersare continually dying and being reborn.Can be viewed as a form of emergent collective organizationor multicellularity.Facilitated by “birth at death location” implementation.To appear in proceedings of Beyond Fitness: VisualisingEvolution, a workshop at ALife 8.[view movie]Environmental/GeneticStability and AdaptationFood supply as a function of environmental stability andmutation rate: MUTATION low med highSTABILITY low 54% 17% 18% med 43% 12% 10% high 55% 14% 12%Preliminary data (2 runs/condition) averaged over first 10,000time steps of each run.[Demo: SwarmEvolve 1.5]Next StepsEnhance complexity/realism/OEF integration.Species-specific controls and metrics.Structured feeder behavior; agent-responsive.Leverage Push/Breve integration for evolution of arbitraryagent control programs and group (species) distinctions.Integrate MIT/BBN elementary adaptive modules.Provide “evolution” components for Taskable Agent SoftwareKit.New IdeasMulti-Type, Self-Adaptive Genetic Programming for Complex ApplicationsHampshire College: Lee SpectorImpact Schedulehttp://www...ftp://ftp..."<H1>...3.1415...[x1,y1],...(a, b, ...)0100101...http://www...ftp://ftp..."<H1>...3.1415...[x1,y1],...(a, b, ...)0100101...0100101..."<H1>...3.1415...0100101...http://www...3.1415...(a, b, ...)ftp://ftp..."<H1>...3.1415...[x1,y1],...(a, b, ...)0100101...((a b)(c d)...((a b)(c d)...((a b)(c d)...((a b)(c d)...((a b)(c d)...3.1415...ftp://ftp...http://www..."<H1>...3.1415...(a, b, ...)0100101...0100101..."<H1>...3.1415...0100101...3.1415...(a, b, ...)((a b)(c d)...((a b)(c d)... ftp://ftp...λλλλλλλλλλλλλλλλλλλλλλλλ!!!!(1, 2, ...)(1, 2, ...)• Richly heterogeneous data can be flexibly integrated in programs produced by stack-based genetic programming.• Explicit code manipulation allows for automatic emergence of modules and evolved program architecture.• Self-adaptive construction of evolutionary mechanisms enhances fit to problem environments.• Evolved agents for heterogeneous, dynamic environments.• Broader range of applications for automatic programming technologies.• Automatic programming with less configuration by users.Feb 01Feb 02Feb 03Feb 04Port new GP systems to Beowulf clusterBenchmarkingIntegration with agent environmentsAnalysis of evolved agentsAlternative