View unanswered posts | View active topics It is currently Mon Sep 16, 2019 2:09 am






Reply to topic  [ 8 posts ] 
Kalman Filter for nxt? 
Author Message
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Kalman Filter for nxt?
hi, has anyone already seen or written a Kalman Filter for NXT?

http://rsbweb.nih.gov/ij/plugins/kalman.html

http://robotics.stanford.edu/~ang/paper ... ations.pdf

http://www.youtube.com/watch?v=M-QUkgk3HyE

:programmer:

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Fri Sep 05, 2008 6:37 am
Profile
Expert
User avatar

Joined: Fri Nov 09, 2007 4:51 am
Posts: 121
Location: Hungary, Europe
Post Re: Kalman Filter for nxt?
I am planning one but first I have to blow the dust from my NXT.

It is not about Kalman filter for NXT -- it is about Kalman filter in general.

That is the key point: you have to prepare a considerably correct model of your system, maybe simulate the model (just to see if it matches the reality) then fill in the matrices needed for Kalman filter, optionally test your filter in simulation and then build your robot to amuse professionals (most of audience will not appreciate the Kalman filter).


Thu Sep 11, 2008 12:29 pm
Profile
Rookie

Joined: Wed Jan 07, 2009 7:27 pm
Posts: 5
Post Re: Kalman Filter for nxt?
elemes wrote:
That is the key point: you have to prepare a considerably correct model of your system, maybe simulate the model (just to see if it matches the reality) then fill in the matrices needed for Kalman filter, optionally test your filter in simulation and then build your robot to amuse professionals (most of audience will not appreciate the Kalman filter).


Not true! This only holds for Second Order Kalman filters :wink:, which can handle Non-Linear Filtering. Even then, if your Markov behaves in a Linear fashion then a Second Order Kalman will show little difference. A control system for a helicopter would almost certianly have to be a Second Order KF, due to the Non-Linearity of controlling something in 3D space. The model for such a controller would filter random changes to orientation and acceleration revealing exactly how the human controller is trying to fly the helicopter.

http://www.techsystemsembedded.com/Kalman.html , here's a link to a Matlab FOKF and SOKF example. I used this to learn how to use these filters, since 90% of the PDF's I read we're far too academic for my understanding, and I do better with examples anyways.

Quote:
...amuse professionals (most of audience will not appreciate the Kalman filter).


Corrupt 50% of the Ultrasonic Sensor readings on a wall-following robot, and show them the difference the filter can make. Unless the audience isn't into robotics, they'd be sure to appreciate it. :D


Wed Jan 14, 2009 5:04 pm
Profile
Expert
User avatar

Joined: Fri Nov 09, 2007 4:51 am
Posts: 121
Location: Hungary, Europe
Post Re: Kalman Filter for nxt?
Yes, you are right. I am continuously keeping in mind my own robot plans (actually, final goal is a balancing robot that is capable to estimate the weight put on its top, based on the answer to balancing movements) and the mechanical model of it is quite complex. At present.

Image


Thu Jan 15, 2009 11:51 am
Profile
Rookie

Joined: Wed Jan 07, 2009 7:27 pm
Posts: 5
Post Re: Kalman Filter for nxt?
I can see how you'd have to fuse sensor data to estimate the weight and balance accordingly. I'd love to make a balancing robot but I'm still grappling with the first order KF's. The real problem with the KF's is that there's no set in stone equation, you have to derive the equations, thats what I think a lot of confusion comes from with these. I was never able to find a tutorial that showed how to derive the equations properly, mostly I looked at the source code for about 20 filters to derive the general structure, if someone found/wrote a tutorial like that it'd open this up to more people.


Mon Jan 19, 2009 12:11 pm
Profile
Rookie

Joined: Sat Feb 14, 2009 10:42 am
Posts: 4
Post Re: Kalman Filter for nxt?
I'm also interested in a good Kalman tutorial (in general). I may write one - as soon as I figure it out!

Here are two sites using NXT Both have some background info, as well
http://www.convict.lu/Jeunes/RoboticsIntro.htm
http://naba.blogspot.com/2008/07/kalman ... s-nxt.html

This is one of the better general sites:
http://www.cs.unc.edu/~welch/kalman/

Wikipedia has some good info and links as well. Nothing on NXT, but there are some links to parallax propeller implementations
http://en.wikipedia.org/wiki/Kalman_filter

Finally, this professor implemented a particle filter on the NXT, which is a related algorithm to the Kalman (he also has info on the mindsensors NXT cam)
http://www.itee.uq.edu.au/~wyeth/NXT/

Good luck!
Roy


Sat Feb 14, 2009 3:38 pm
Profile
Expert
User avatar

Joined: Mon Oct 06, 2008 6:30 pm
Posts: 176
Location: Netherlands
Post Re: Kalman Filter for nxt?
Hi,

I thought I might share my experience with a Kalman filter and a compass sensor. This is the situaton. I have a robot like the tribot with a compass mounted to it. I want to implement odometry (and slam, but that's another topic).
The compass readings are not trustworthy so I thought to combine dead reckoning and compass readings to get a best estimate of the robots heading.

On this forum I read about Kalman filters (thanks for the links guys) and I went to try it out. I did a lot of reading but these articles always go into the technique and only seldom into the concepts. So here is what I made out the be the concept. I'll use heading as an example. There are different ways to find out what you're heading might be. Some are direct, like the compass. It gives you a heading without having to know anything about the history of the robot. Some are indirect, like dead reckoning. For this you'll have to know the previous position of you're robot and it's behaviour since then. The Kalman filter combines the results of direct method(s) and indirect method(s) to a best estimate. It then uses this estimate as input for the indirect measurements the next time it is used. This is why it is called recursive, you don't have to use recursive algorithms to implement it.

To build a Kalman filter you'll have to know two things about your robot. First thing concerns indirect methods. You'll have to know how to calculate the current position from the last known position and the input from your indirect sensors. In my case I had to calculate the change in heading from the motor sensors and add this to the previous heading. This is what in a previous post is referred to as the equations and in my case it took a little trigonometry. The second thing to find out is the amount of variation there is between real life and what you have measured (or calculated). If the filter knows how much it can trust each of your results it can combine these results to a best guess. (It also knows how good this guess is and it uses that information the next time it is used). In my case I had no idea how much variation there was in the compass sensor and in the odometry. I thought I could find that out later.

I first built the filter in excel ignoring the model, I just gave two values as input. This made me understand the filter. The spreadsheet is available upon request. Then I made the equations for the dead reckoning. Then I combined the two using some guessed variation. Now I have a robot that can give me three different headings,form the compass, the dead reckoning and the filter. To my surprise the results of the dead reckoning were superiour to the results of the filter. The results from the compass were the worst. First I thought it must be wronge assumptions regarding the variances, so I tried different values. It didn't help. But then I found out the real reason. It is in the nature of the magnetic field.

As there always is some iron in a building the magnetic field will be disturbed. And it won't be random. The speaker in the corner of your room attracts any compass needle. So the error is biased to one direction. The Kalman filter on the other hand assumes the error of each of the input values to be random (normally distributed). The error in a sensor might be normally distributed but there is still the deviation in the magnetic field that isn't. So the Kalman filter isn't of much use in this case.

So this is were I'm right now. If I want to continue on this track I'll have to compensate for the deviation in the magnetic field. In theory it could be done assuming it is constant (with some random error) at any given position. But it would be a lot of work. I could also add another sensor. I still don't know.

BTW, my robot can make some nice visuals for each of the three results. But for now I'll call it a day.

_________________
My most recent blog: A grain of sugar


Fri Mar 06, 2009 7:50 pm
Profile WWW
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Kalman Filter for nxt?
hi,
I'm really curious how the Calman actually works, and your spreadsheet maybe could help me a lot. Is it to be downloaded somewhere, or could you send it attached to an email?

BTW: As you may have read, the compass sensor values had been a problem also to Gordon Wyeth who's written another Filter system based on the statistical/stochastical Monte Carlo Method ("Particle Filter") http://www.itee.uq.edu.au/~wyeth/NXT. Those values had been so unreliable, that he completely gave it up trying to use it for navigation:
Gordon Wyeth wrote:
If I mapped magnetic field, I could probably add it in, but there's no straightforward way to use it for localisation.
So, there is nothing wrong with the compass per se, but there are well known limitations with using the compass for navigation indoors.


EDIT:

a problem using the Kalman Filter for compass sensor values is that the Kalman Filter uses just a linear processing model with normally (standard) distributed measurement errors. The magnetic fileld indoors, anyway, is supposed not to be normally distributed, so it's likely that non-linear filters will be needed. Maybe you speak a little German, that's what you can read in the German Wikipedia on this subject:

Wikipedia wrote:
Sequenzielle Monte-Carlo-Methode http://de.wikipedia.org/wiki/Sequenziel ... lo-Methode
Für den Fall eines linearen Prozessmodells und unter Annahme normalverteilter Störgrößen und Messfehler wurde 1961 das kontinuierliche Kalman-Filter von Kalman und Bucy eingeführt, um den wahrscheinlichsten Zustand rekursiv aus den vorhergehenden Schätzungen und den erhaltenen Messwerten zu bestimmen. Im Falle, dass das Prozessmodell wesentlich nichtlinear ist oder die Störeinflüsse nicht als normalverteilt angenommen werden können, kann nicht von einer Normalverteilung des zu schätzenden Zustandes ausgegangen werden. Es muss weiter u.a. in Betracht gezogen werden, dass die Wahrscheinlichkeitsdichte mehrere Maxima aufweist, d.h. die gemachten Beobachtungen zu mehreren inneren Zuständen kompatibel sind. Ein gitterbasierter Ansatz zur Lösung dieses erweiterten Problems besteht in der Transformation der Systemdynamik in eine Dynamik der Wahrscheinlichkeitsdichte auf dem Zustandsraum (s. Stochastische Differentialgleichung). Die Lösung der dabei entstehenden partiellen Differentialgleichungen mittels Finite-Elemente-Methoden ist im Allgemeinen recht aufwendig.


maybe you find this interesting, too: http://www.cs.cmu.edu/~minerva/tech/mosaic.html

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Sat Mar 07, 2009 9:13 am
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 8 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.