DPRG
DPRG List  



[DPRG] Hello from sawtooth

Subject: [DPRG] Hello from sawtooth
From: JS angryscientist at gmail.com
Date: Wed Nov 26 10:05:27 CST 2008

Jose,

Very interesting, thanks for the info. Now I wont kid you I am certainly not
a math whiz by any means, and really this bot was my first foray into
robotics beyond blinking LEDs on a breadboard. I'm a network engineer and
have a small background in perl, regular expressions, shell scripting, etc,
but nothing like C really. So ive been teaching myself using an arduino and
I know how we ended up getting the job done in our code, and ive read quite
a bit on how other people have done line following and its all relatively
similar, the better ones seem to be using PID. I guess what im curious to
know is where does this algorithm fit into the sensor reading code, and the
motor control code? Is the goal of the evolution to make the bot execute the
line faster each time, or just more to observe various mutations?

On Wed, Nov 26, 2008 at 9:20 AM, Francisco Jose Ayala <ze at neuroblast.net>wrote:

>
>
> Hi im Jacob and I was the other guy on the sawtooth team. I got an email
> from the list forwarded to me regarding the two 3pi's using AI and I have a
> few questions for those two gentlement:
>
>
> Hi, Jacob.  Thanks for your interest.
>
>
> 1. I'm curious to know what the output code actually looks like;
>
>
> Each genome in our genetic system consists of a series of parse trees,
> which look something like this<http://upload.wikimedia.org/wikipedia/commons/7/77/Genetic_Program_Tree.png>.
>  Each parse tree encodes a mathematical expression representing the
> processing of a single neuron.  Connections between neurons can be encoded
> as special kinds of nodes within the tree.
>
> Here is a sample tree from one of our recent genomes:
>
> ((((Y0 NEG ) NUL ) MAX (((X2 SY0 ) - (N5 STP Y0)) MOD ((D2 + (R0 STP (D9 +
> R1))) SY0 ))) THR (((X0 * (Y0 MOD N14)) MAX ((R0 + N12) SR0 )) * ((D6 NEG )
> % ((Y0 SR1 ) MIN (D14 % X1)))))
>
> A genome encodes a cluster of neurons.  Multiple instantiations of this
> cluster can be combined like legos to form a brain.  For example, to spawn
> the brains for the 3pi<http://www.neuroblast.net/images/20081121pop17gen690hiBrn5.jpg>,
> which has five reflectance sensors, we join together five neural clusters,
> one for each input.
>
> Parse trees are used in the genetic algorithm subfield called genetic
> programming <http://en.wikipedia.org/wiki/Genetic_programming>.  Many
> other methods are available for genetically encoding evolvable mathematical
> expressions.  The great advantage of using parse trees is the process by
> which they are mutated...
>
>
> 2. Where in the code (what portions) are the changes being made as a result
> of this process,
>
>
> There are two general types of mutation to a parse tree.
>
> Point mutations simply change one node to a different kind of node.  For
> example, (5 + 3) can become (5 + 7), or (5 * 3).
>
> Crossover mutations swap branches between two trees.  For example, ((5 + 3)
> * 2) can combine with (1 - (7 * 8)) to produce ((5 + 3) * (7 * 8)) and (1 -
> 2).
>
> Another type of crossover mutation swaps entire sections of one genome
> (comprising many trees) with entire sections of another genome.
>
>
> 3. and what kinds of things within the code are being changed?
>
>
> Any kind of internal node can mutate to any other kind of internal node,
> and any terminal node can mutate to any other kind of terminal node; and any
> pairs of branches can be swapped between any two trees.
>
> I mentioned that parse trees have a big advantage regarding mutation, and
> it is this:  all mutations, whether point or cross-over, will result in new
> trees that are guaranteed to be syntactically valid.  That is, there are no
> "nonsense" mutations.
>
>
> 4. Does the code have some measure of success so that it knows which traits
> are more desirable for the next iteration?
>
>
> No, success (i.e. fitness) is measured externally.  In the case of our
> line-following brains, success is measured simply as proximity to the center
> of the line.  The brains know the current values of the sensors, so they
> know where they are relative to the line, so in that sense they know how
> well they are doing, but they do not know what their fitness scores are.
>
> Mutations are completely random, so the brains have no way of choosing
> which traits to pass on to the next generation.
>
>
> Nice to meet everyone and look forward to competing again.
>
>
> Ditto!
>
> Cheers,
> Jose'
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.dprg.org/pipermail/dprglist/attachments/20081126/daf4301b/attachment.html

More information about the DPRG mailing list