DPRG
DPRG List  



[DPRG] Hello from sawtooth

Subject: [DPRG] Hello from sawtooth
From: Francisco Jose Ayala ze at neuroblast.net
Date: Wed Nov 26 10:54:33 CST 2008

Jacob,

The interface between the sensor reading and motor control code and  
our brains is actually pretty simple, and not much different from the  
interface with a PID controller.

Every neural cluster has a variable (i.e. a terminal node) called X0,  
which is for data input.  We read the sensors in the usual way, and  
then set X0 to that value.  So that part of the code is pretty much as  
simple this:

	X0 = sensor[n];

We then let the brain chew on those inputs with a command that looks  
like this:

	fireBrain();

Finally, there is another variable called Y0, which is for data  
output, and which is set by the brain itself.  We read that variable,  
and interpret it as follows:

         if( Y0 < 0 )
         {
             m1 = motorMax + (motorMax * Y0)/100;
             m2 = motorMax;
         }
         else
         {
             m1 = motorMax;
             m2 = motorMax - (motorMax * Y0)/100;
         }
         set_motors( m1, m2 );

The primary goal of evolution is to minimize the distance between the  
robot and the center of the line.  There are other secondary goals,  
such as minimizing control jitters (from which our robot suffered at  
Roborama).  The neat thing about a sufficiently versatile evolutionary  
system is that you get what you ask for.  If you select for the  
elimination of control jitters, they'll eventually go away.  We can  
select for just about anything that is physically possible.

Cheers,
Jose'
	

On Nov 26, 2008, at 10:05 AM, JS wrote:

> 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.  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, 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.  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/a73a4f94/attachment.html

More information about the DPRG mailing list