Skip to content

Development

Jump to bottom Edit New page
sofian edited this page Feb 16, 2013 · 16 revisions

Agent-based systems

List: http://www.swarm.org/index.php/Tools_for_Agent-Based_Modelling

Swarm library

Main objects:

  • Agent = model / set of rules/responses to stimuli
  • Swarm = group of agents + schedule
  • Eg. "a swarm could be a collection of 15 coyotes, 50 rabbits, a garden with carrots, and a simple schedule: the rabbits eating the carrots and hiding and the coyotes eating the rabbits")
  • A swarm can be an agent
  • An environment is just an agent "The core of a Swarm simulation is the modeled world itself. In the simplest case, a model consists of one swarm inhabited by a group of agents and a schedule of activity for those agents."

Similar project: JAS Java clone of Swarm (User guide PDF) Since JAS is written in Java it was easier to look it up. However there doesn't seem to be any explicit class Agent or Swarm so it's hard to know how this works.

MASON

  • http://cs.gmu.edu/~eclab/projects/mason/

  • Language: Java

  • Licence: Gnu LGPL

  • Contains very nice examples and tutorials (you can try them directly on the website)

  • Main (agent) objects contain a step(SimState) method:

  • So the step() method doesn't just return an action to be implemented by the environment (world): it directly affects the environment

CppAgent

http://code.google.com/p/cppagent/

This library would be very close to what we are looking for in Qualia but it hasn't really been implemented (there are 4 files in the repo...).

This quote from the main page is interesting:

"In this context, an agent is a software component which:

  • processes and manipulates data streams,
  • is autonomous, in that it requires no interaction from users or other agents,
  • is entirely decoupled from other system components,
  • has no interface (black-box view),
  • operates in an independent thread of execution."

This page explains how a robotic system can be implemented with several agents interacting: http://code.google.com/p/cppagent/wiki/SampleRoboticsApplication

Genetic algorithms

There are mainly two ways to employ GAs in art:

  1. As more creative / random ways of creating experiences (eg. DNA-designed music)
  2. As an optimization tool for agents (which is the actual reason why GAs were designed for)

So if we implement such a library we should better separate it in two parts:

  1. A set of tools to design:
    • genotypes (bitcoded genes)
    • DNA manipulation (mutations, crossovers, etc)
    • phenotypes resulting from genes (including parameters and possibly programs ie. GP)
  2. Genetic Algorithm agents and environments

Notice that part (1) can (and should if possible) be independent of Qualia

Basic principles

From this nice tutorial on GAs

Encoding

  • Solutions are encoded as binary strings
    • Genes: a gene represents some data (eg. color of eyes) eg. Gene 1: (10101000) Gene 2: (01110100)
    • Chromosome: a chromosome is an array of genes eg. (10101000) (01110100)
  • Types of encoding:
    • Binary encoding: most popular
    • Value encoding:
      • every chromosome is a sequence of values (eg. integer, chars, floats)
      • sometimes necessary to design specific kinds of crossovers/mutation operators
    • Permutation encoding:
      • Chromosome = string of numbers representing a position
      • eg. for travelling salesman problem
    • Tree encoding:
      • Chromosome = tree of objects
      • Useful for encoding computer programs
      • NOTE: Could be used in combination with Behavior Trees (???)

Operators

Three operators

  • Reproduction (or selection)
  • Crossover (or recombination)
  • Mutation

Reproduction (or selection)

  • Selection of the "fittest" individuals to be used for recombination
  • Selection = extract a subset of chromosomes based on a fitness function
  • Selection approaches : roulette wheel, Boltzmann, Tournament, Rank, Steady state

Crossover (or recombination)

  • One-point crossover (easiest way)
    • Take two parents
      • Parent 1: 11010110
      • Parent 2: 00100011
    • Select a random point in the chromosome
      • Parent 1: 11010|110
      • Parent 2: 00100|011
    • Interchange their DNA at that point to create two offsprings
      • Offsp. 1: 11010|011
      • Offsp. 2: 00100|110
  • Two point:
    • Take two parents
      • Parent 1: 11010110
      • Parent 2: 00100011
    • Select two random points in the chromosome
      • Parent 1: 11|010|110
      • Parent 2: 00|100|011
    • Interchange their DNA at that point to create two offsprings
      • Offsp. 1: 11|100|110
      • Offsp. 2: 00|010|011
  • Uniform
    • Selects each gene (bit) randomly according to a mix factor/probability.
    • Eg. if the mixing factor is 0.5 half the genes of offspring 1 will come from parent 1 and the other half from parent 2 (offspring 2 gets the other half)
  • Arithmetic (for numeric genes ie. int or float)
    • Offspring1 = a x Parent1 + (1-a) x Parent2
    • Offspring2 = (1-a) x Parent1 + a x Parent2
    • a in [0..1]
  • Heuristic
    • Offspring1 = BestParent + r x (BestParent - WorstParent)
    • Offspring2 = BestParent
    • r in [0..1]
    • has some specific issues (may result in out of range genes)

Mutation

  • Happens after a crossover is performed
  • Happens according to a probability (generally low eg. 0.01)
  • Flip Bit
    • Most simple
    • Inverts the value of the chosen gene
  • Other mutation operators: Boundary, Non-uniform, Uniform, Gaussian

Genetic Programming

GP is a category of GA where programs (instead of just parameters) are evolved. I'm not sure we should use this in Qualia but it's worth looking at.

Tutorial on GP

Software libraries:

  • TinyGP Java implementation Very small (but also very basic, only allows math operation nodes +-/*)
  • Lil-GP lil-gp is a generic 'C' genetic programming tool
  • RoboGP Inspired by Lil-GP
  • SmallGP A lean Genetic Programming System for Symbolic Regression
  • BEAGLE Puppy Very small (8 include files + 3 source files!) and very comprehensive, would be a perfect candidate on which to base ourselves for GP / tree implementation

Behavior Trees

Presentation/tutorials

Existing libraries/code

Memory management

Add a custom footer
Add a custom sidebar
Clone this wiki locally