Genetic Algorithm PID fitness assessment

Post your NXJ projects, project ideas, etc here!

Moderators: 99jonathan, roger, imaqine

Genetic Algorithm PID fitness assessment

Postby steveiswicked » Mon Oct 03, 2011 10:36 pm

Hello, I have a self balancing robot based on a stripped down version of Steven Witzand's code. The values for the PID loop and loop delay work well enough but they were chosen using the WAG method through trial and error. It occurred to me that I'd never know if these values were the most stable and efficient ones to use. So I coded a genetic algorithm to shuffle, mutate and test all the combinations of PID weightings. The mutations couldn't be too radical otherwise the robot would fall. For the fitness assessment I figured that the PID loop attributes that showed the least power variance over time were the best.

One problem I had to contend with is that all the extra maths the robot has to do impacts its balancing performance, but it seemed to work and the robot started to become less jittery through each generation of PID loop attributes. But it became apparent that the improved robot stability was an illusion and if the robot was nudged it performed much worse than before. It seems that, while the robot is just standing still, by using the least power variance test the P&I weightings for the PID loop wither away through lack of use. So I need either a better way of testing or a way of giving the robot a controlled nudge to keep it tough.

Can anyone give me any tips on determining the optimal values for a PID loop?
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby Aswin » Tue Oct 04, 2011 7:23 am

steveiswicked wrote:For the fitness assessment I figured that the PID loop attributes that showed the least power variance over time were the best.

Cool!
How much generations did it take to find a good value, and how many scenario's per iteration?

I think that you tune your PID for least power consumption and not necessarily for stability. You could try to use the sum of the squares of the error (P=value) / time as an incidation of success. The lower the better. It doesn´t use variance as math which might take less math. Also if you want it to react well on nudges you could apply controlled nudges while training.

It is very understandable to make only small mutations, otherwise you´ll have the risk that the robot falls over. But there is a downside to this. You´ll find an optimum that is close to your starting parameters, this is called the local minimum. But there could be a better optimum that is not close to the starting position that you can't find with small mutations. You'll find an example of this on my blog. This also explains how a genetic algorithm works.
My NXT blog: http://nxttime.wordpress.com/
Aswin
leJOS Team Member
 
Posts: 197
Joined: Tue Apr 26, 2011 9:18 pm
Location: Netherlands

Re: Genetic Algorithm PID fitness assessment

Postby gloomyandy » Tue Oct 04, 2011 9:20 am

Sounds interesting. But I think you are correct that you need to add some sort of impulse response into the system to test it for stability in this case as well as in the relatively stable case. This is a well known issue with PID controllers. Adjusting the values to maintain a stable system (with only very small error terms) often means that you end up with large values for some of the parameters. These large values work well when dealing with small errors (because the error is corrected quickly), but when a large error is introduced quickly into the system the result is oscillation. One possible way to test this may be to inject a motor movement into the system from time to time to force it to move out of the stable position, and then see how well the controller recovers from this. Doing things that way may enable more repeatable test case rather than simply nudging the robot)...

Andy

PS When you have it all working be sure to post your code, as I know that balancing robots are one of the most popular projects...
User avatar
gloomyandy
leJOS Team Member
 
Posts: 3901
Joined: Fri Sep 28, 2007 2:06 pm
Location: UK

Re: Genetic Algorithm PID fitness assessment

Postby steveiswicked » Fri Nov 11, 2011 12:23 am

Hello Andy and Aswin,

Thanks for your help. I simplified the fitness assessment to be simply the average of the absolute power values applied to the motors over 500 iterations of the PID loop and added a "nudge" by applying an additional fixed power value to the wheels every 50 iterations. I save the best PID values while it tests each permutation from the GA. The robot falls a lot at first but when I reset, it starts with the "best" PID gains from the previous cycle even if the whole cycle was not completed. I'm pleased to say that it seems to work and after about 6 incomplete cycles it can withstand all the nudges and continue to balance indefinitely, eventually the PID gains no longer change significantly.

The factor that has the biggest impact is the loop delay in the PID loop. The robot has to evolve for several cycles before it is stable enough to risk mutating this value so I've been doing it by hand, making it smaller and re-evolving the PID values. For each reduced loop delay the PID Gains are also smaller, but the robot eventually gets too frisky to use the gains from the previous cycle.

When I take the Genetic Algorithm Test & Save thread out, the PID Gain values are probably no longer optimum, but they are much more stable than I've been able to work out through trial and error. :D
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby Aswin » Fri Nov 11, 2011 2:53 pm

Nice job,

The loop delay problem comes from the fact that the I and D factors are time dependend. When you take this into account your PID controller will no longer be sensitive to loop delay factor.

I guess your code now looks like this
Code: Select all
I=I+error;
D= (error-lastError);

Try to change this into something like this
Code: Select all
I=I+error * dt;
D= (error-lastError)/dt;


Dt is the time elapsed since the last iteration. The P is not time dependend.
My NXT blog: http://nxttime.wordpress.com/
Aswin
leJOS Team Member
 
Posts: 197
Joined: Tue Apr 26, 2011 9:18 pm
Location: Netherlands

Re: Genetic Algorithm PID fitness assessment

Postby steveiswicked » Fri Nov 11, 2011 6:17 pm

Thanks, I'll give that a try!
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby steveiswicked » Sun Nov 13, 2011 7:12 pm

Hello Aswin,

Thanks for your very perceptive advice about dt. If I'd realised I had this flaw in my PID loop I might never have explored Genetic Algorithms at all! I'm glad that I have though, I can see that when I train my robot on carpet and on a hard flat surface it settles on noticeably different values. I am curious to know why. It might be worthwhile giving it the ability to recalibrate on the fly. Best thing though, is that I can re-introduce behavioural threads without it going crazy.
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby gloomyandy » Sun Nov 13, 2011 7:21 pm

Hi,
This sounds pretty good to me. I'd love to take a look at the code and perhaps give it a try. Would you mind posting it or providing a download location?

All the best

Andy
User avatar
gloomyandy
leJOS Team Member
 
Posts: 3901
Joined: Fri Sep 28, 2007 2:06 pm
Location: UK

Re: Genetic Algorithm PID fitness assessment

Postby Aswin » Sun Nov 13, 2011 11:48 pm

Count me in
My NXT blog: http://nxttime.wordpress.com/
Aswin
leJOS Team Member
 
Posts: 197
Joined: Tue Apr 26, 2011 9:18 pm
Location: Netherlands

Re: Genetic Algorithm PID fitness assessment

Postby steveiswicked » Mon Nov 14, 2011 10:22 pm

I don't seem to be able to add attachments here so I put it in Google docs

https://docs.google.com/open?id=0Bwtv1av5PMUDM2RkYTM1NjktNGE4NS00ZDkwLWJhNWQtOWM4NGNiZjc5ZjY2

the Slugz class holds the chromosomes for the PID loop
the Colony class handles the breeding when in learning mode and saving/loading of new Slugz chromosomes
SlugBalancer is the balancing thread, which I start before Bluetooth
You might guess that I started on this a long time ago, so some recent Lejos innovations haven't been adopted
Slugzway is the main program, much of the code is based on Gelway, apologies and regards to SJWitzand

Forgive my code for being scruffy, I've never produced code for public consumption.
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby gloomyandy » Mon Nov 14, 2011 11:11 pm

Thanks, I've grabbed a copy of the code but not had chance to look at it yet...

If you have the time I'd really appreciated a few notes on the process you used to optimize the PID values (unless the code already contains the details of how to do that)... Basically how do you run the program?

Thanks again...

Andy

PS What size wheels did you use?
User avatar
gloomyandy
leJOS Team Member
 
Posts: 3901
Joined: Fri Sep 28, 2007 2:06 pm
Location: UK

Re: Genetic Algorithm PID fitness assessment

Postby steveiswicked » Wed Nov 16, 2011 12:25 am

The main program is Slugzwaywhich starts three threads
SlugBalancer
BlueToothReader
and an Arbitrator, the only Behaviour implemented in the Arbitrator is GELwayDriver

GELwayDriver class allows remote steering of Robot through Bluetooth commands

The SlugBalancer class
Calibrates the Gyro (while the robot is held upright)
Instantiates a Colony of Slugz
Takes gyro sensor readings
Implements the PID Loop for controlling the motors
Records data for assessing PID loop performance/fitness
Compensates for Gyro drift (a bit dodgy that)
Moderates inputs from Gelway driver

The Slugz class is where the parameters of a PID loop are kept, these params are used as chromosomes in the Colony's Genetic Algorithm. The Slugz class has a method to mutate the Slugz' chromosomes by randomly modifying the parameters within a controlled threshhold.
The Colony class is an array of Slugz objects and a thread that periodically breeds and mutates the Slugz within the colony.

Initially the Colony needs a base set of working PID Loop parameters for the very first mother Slugz. It gets these from a file in the brick called "default.slg"
If the file "default.slg" does not exist the Colony class will create one using a set of specified defaults.
In order to create the remaining slugz in the colony it needs a father slugz so it mutates a copy of the first Slugz and then populates the colony with every permutation of the chromosomes from these slugs
so if the initial contained.
P1 I1 D1 L1 Where P I and D are proportional, integrated, derived gains, and L is the loop delay

P2 I2 D2 L2 would be mutated values of the above
The colony contains 16 slugz
P1 I1 D1 L1
P1 I1 D1 L2
P1 I1 D2 L1 etc
...
P2 I2 D2 L2
this method I call breedSlugz.
All the slugz in the colony, except the mother, are then randomly mutated a little bit

When the Colony is in learnMode (set by boolean) it runs a thread that by cycling through the Slugz in the colony, periodically changes the PID Loop parameters supplied to the SlugBalancer class.
The Colony can also tell the SlugBalancer class to give itself a periodic kick so the the PID gains get exercised. The SlugBalancer also monitors the power that has been supplied to the wheels while balancing. (My logic is that an elegantly standing robot should not need to use much power, it seems to work, though Aswin suggests I might use the proportional error value to better effect, I've yet to try this)
The Colony will write the parameters of the best performing Slugz object to "default.slg" so that they can be used as the mother parameters the next time the robot starts.
If the colony makes it through all 16 permutations it will start again using the best performing slugz as the new mother.

There's a separate program ShowSlugLoad that allows the user to display the default.slg file on the brick.

Once the robot is trained the Colony can be taken out of learnMode and the have kicks turned off. The robot remains stable.

The other classes control the motors and pass various parameters between the threads.

I developed my robot with size 81.6 wheels. But I've just retrained it with size 56 wheels and didn't have to change the code.
steveiswicked
New User
 
Posts: 19
Joined: Sun Feb 06, 2011 11:22 pm

Re: Genetic Algorithm PID fitness assessment

Postby Aswin » Wed Nov 16, 2011 7:20 am

Hi,

I think your idea to use the power level of the motors is as good as mine to use the integral of absolute P values. But have you taken loop time into account (I do not have access to your code at the moment)? I think that three times a power level of x for 5 msec should be just as "fit" as one time a power level of x during 15 msec.

I suggest that you not take a single mother, being the fittest of your permutations. Instead you could use the best 4 or 8 permutations as mothers. Each would breed 4 or 2 offspring. This will have two effects. First, you won't loose a good scenario due to a a random event too easily. Second, a potentially good scenario has some change to evolve into the best scenario without being discarded to soon.
My NXT blog: http://nxttime.wordpress.com/
Aswin
leJOS Team Member
 
Posts: 197
Joined: Tue Apr 26, 2011 9:18 pm
Location: Netherlands


Return to NXJ Projects

Who is online

Users browsing this forum: No registered users and 2 guests

more stuff