another comparison

[Claude Baumann]

We have compared the sampling and computing speed of NXT and RCX. NXT uses
standard firmware 1.03 and is programmed with the LabVIEW toolkit. RCX is
programmed with ULTIMATE ROBOLAB. Both bricks do the same thing: computing the
DFT on a small dataset of 128 points that are read from the legacy light-sensor
on a shaft encoder that is rotated with a legacy motor. ULTIMATE ROBOLAB keeps
the whole system running (managing sensors, sound, display, buttons,
IR-communication...) e.a. all the things that the standard firmware also is
doing; so there is no reduced funtionality and thus no tricky speed gain. Both
programs are absolutely comparable. But the RCX operates the sampling plus DFT
22.8 times faster than NXT! This is intriguing.

Would be nice to compare the speed features under other firmwares or programming
environments.

Beating the RCX is not that simple !

www.convict.lu/Jeunes/nxt_one/RFT_NXT_RCX.htm

[Brian Davis-3]

In lugnet.robotics, Claude Baumann wrote:

> the RCX (under the custom FW of Ultimate Robolab)
> operates the sampling plus DFT 22.8 times faster
> than NXT (under "standard" FW running a bytecode
> program written with the LV Toolbox)!

I'd love to make some other comparisions; actually, some of us have been trying
to figure out a good way to do this. Part of the problem is defineing specific
"goals" for a battery of tests. A DFT (while impressive), is propably not the
best example, at least partially because I don't think anybody has tried this
complexity under, say, NXT-G: the most complex math I've done are things like
square roots and inverse trig functions. What I think we need are:

1) Processor speed: something like your DFT comparision, but easier for folks
like me who are far less talented than that example under NXT-G. Something like
a hailstone number problem (also called the (3n+1) problem), or even easier
(just adding a number to itself 10,0000 times?)

2) Sensor readings: how fast can the FW+SW combination read from a sesnor 10,000
times or similar. Note there's a difference between taking a previously stored
value saved by the FW and getting current, fresh, up-to-date values.

3) For the NXT, a way to compare the speed of updating the LCD

4) Again for the NXT, a way to compare BT message speed (one-way and
bidirectional... they (will? may?) be different), and if we want, to compare
sending the same "information" RCX-to-RCX via IR. Again, what the message sgould
be is rather up for discussion: one-byte messages are the lowest common
denominator, but the fact that you can send more efficient multi-byte (text)
messages under BT should be taken into account too.

It's not a simple problem. As recent discussions have sometimes pointed out,
folks have very different viewpoints on what is or is not a good test, or what a
"good" comparision is... and if we want a speed comparison to be as useful as
possible to the community, it needs to be fairly generally agreed upon.

So, ideas from the group? Claude, you certainly have some, and I've mentioned
some above. We really need input here from end users who "know what they want",
and certainly from the SW and FW writers (those people are going to know how to
code something in those languages as well). Dick (RobotC, RCX "fast FW"), John
(NBC, NQC, NXC), Brian (LeJos?), Ralph (pbLua), and lots of others, anybody want
to put out some input here?

> Beating the RCX is not that simple!

Given the different processor speed, and instruction set, it *should* be...
well, in my own little world where I know next to nothing about HW, or
down-to-the-metal FW issues :-) Help!

--
Brian Davis

[Chris Phillips-3]

In lugnet.robotics, Brian Davis wrote:

> I'd love to make some other comparisions; actually, some of us have been trying
> to figure out a good way to do this. Part of the problem is defineing specific
> "goals" for a battery of tests.
>
> It's not a simple problem. As recent discussions have sometimes pointed out,
> folks have very different viewpoints on what is or is not a good test, or what a
> "good" comparision is... and if we want a speed comparison to be as useful as
> possible to the community, it needs to be fairly generally agreed upon.
>
> So, ideas from the group?

Perhaps a good benchmark would be to write a PID controller and measure the
number of control loop iterations per second that can be achieved under each
environment.  This incorporates sensor input with motor output, and uses a
moderate amount of computation in the middle.  It is also a very useful
"real-world" application in robotics.  (Unfortunately, any sensor-input
application is ultimately bounded by the maximum sampling rate of the sensors,
although I think both RCX and NXT use a ~2ms sampling rate.)

My gut tells me that the RCX (using BrickOS) would give the NXT (using anythng
available so far) a good run for its money, though...

[Dick Swan]

Chris Phillips wrote on Sunday, January 21, 2007 7:38 AM
"My gut tells me that the RCX (using BrickOS) would give the NXT (using
anything available so far) a good run for its money, though..."

Once you reach a certain base performance level, then it doesn't really
matter to most users what the actual real time performance is. NXT-G may
be relatively slow when compared to the emerging alternative programming
environments; it's certainly the case when it is compared with RobotC.
But NXT-G exceeds the base performance level so perhaps it doesn't
really matter.

Far more relevant is the choices made in the underlying
implementation/algorithms. I'll use your example of PID algorithms to
illustrate this principle. The relevant factors here include:

* How often is the PID loop updated?
* Are the PID factors properly tuned?
* Has the right "equation" / "definition" been chosen for the PID error
factor?

An observation of the NXT-G movement of two synched motors driving in a
straight line before stopping after a specified distance shows that it
achieves very reproducible results and does a great job of going
straight and stopping at the target. Most users are likely to be happy
with that. But it can be improved on! Looking at the "straight" line PID
results in detail you'll notice:

* A slight "oscillation" about the ideal line as the robot moves.
* There's a very slight (and reproducible) "curvature" to the line --
typically 0.1 to 0.25 inches for every 3 feet of travel.
* There's always overshoot at the end point. Followed by a correction to
move back to the target spot.

Analyzing the root cause of the above observations in more detail leads
to the following:

* PID loop is updated every 100 msec. A faster update cycle might reduce
the maximum error of the oscillations.
* There is only a PID used to adjust the synched motor speeds. A full
PID is not used to stop at the end-point; just a simple ramp down of the
speed as the end point is reached. Use of PID here (the "D" factor)
would allow stopping at the end point and avoid the overshoot.
* The PID error factor is to ensure that the speeds of the two motors
are synchronized. It is not to ensure that the robot travels in a
straight line! This is the cause of the curvature.

Addressing the above points, rather than execution speed improvement,
may yield the best improvements. For example, a better choice for the
error factor would be the deviation from the straight line movement --
which can be easily calculated from the motor encoders and a little
trigonometry.

The above performance is more than good enough to drive in a single
"straight" line. But one of my current interests is in super-accurate
dead reckoning -- i.e. lots of movements, turns, etc -- with accurate
recording of location. You need great accuracy in the individual
movements to minimize the accumulated error. I suspect the LegoBot Robot
from David Anderson (five years ago, Handyboard based, see
http://www.geology.smu.edu/~dpa-www/robo/lego/index.html) has
established a good benchmark; I've seen it randomly wander around a 10'
x 10' walled rectangle for five minutes and then consistently return to
within 2" of its original starting point. This is really impressive and
not something that I expect to see in a NXT-G program!

And this brings me back full-circle on the performance issue. Accurate
dead-reckoning needs trigonometry and transcendental functions (sqrt,
sin, cos, atan) with floating point numbers. Even though you can
implement these in NXT-G subroutines/blocks, my gut tells me the
performance won't be good enough. For this level of accuracy, maybe
NXT-G is not good enough.

And a practical example of dead reckoning movement is the annual FLL
tournament. Imagine a development environment that had a pre-built
library of dead reckoning routines -- e.g. give the robot a list of
coordinates/waypoints and it will move to each of them. This could
dramatically simplify the required programming. Some robots in the FIRST
tournament (the tournament with bigger robots for older kids) have been
using this technique for the last couple of years in the autonomous
operation section. I expect to see some dead reckoning solutions for FLL
next year!

And back to your original "gut" feel. BrickOS may give NXT-G "a good run
for its money" but I doubt if the same will be true of the faster
alternative text-based programming languages. See my recent post on
this.

Following up on your sampling rate question. "Standard" (i.e original)
firmware for RCX and NXT samples the sensor ports at 3 msec. But the NXT
motor encoders are interrupt driver and can support over 1,000 counts
per second. On the RCX, sampling speed in the Robolab firmware is now
customizable down to 0.5 msec so that you can get legacy rotation
sensors to reliably work at up to 1,400 counts per second. Unfortunately
in the NXT the analog sensor sampling rate is fixed at 3 msec and cannot
be changed since it is done in the slave AVR microprocessor.

[Claude Baumann]

In lugnet.robotics, Chris Phillips wrote:

> In lugnet.robotics, Brian Davis wrote:
>> I'd love to make some other comparisions; actually, some of us have been trying
>> to figure out a good way to do this. Part of the problem is defineing specific
>> "goals" for a battery of tests.
>>
>> It's not a simple problem. As recent discussions have sometimes pointed out,
>> folks have very different viewpoints on what is or is not a good test, or what a
>> "good" comparision is... and if we want a speed comparison to be as useful as
>> possible to the community, it needs to be fairly generally agreed upon.
>>
>> So, ideas from the group?
>
> Perhaps a good benchmark would be to write a PID controller and measure the
> number of control loop iterations per second that can be achieved under each
> environment.  This incorporates sensor input with motor output, and uses a
> moderate amount of computation in the middle.  It is also a very useful
> "real-world" application in robotics.  (Unfortunately, any sensor-input
> application is ultimately bounded by the maximum sampling rate of the sensors,
> although I think both RCX and NXT use a ~2ms sampling rate.)
>
> My gut tells me that the RCX (using BrickOS) would give the NXT (using anythng
> available so far) a good run for its money, though...

1. The DFT certainly may be considered as overkill for a toy robot kit. But I am
not sure that this forum considers the RCX or NXT only as toys. To say that NXT
or RCX are not made for this or that is like saying to the inventor of the
pencil that it is not thought for high arts, only for scribbling... and my best
puzzle is made of a pencil and a cord. OK, if we tell the pencil factory to
improve the quality, because we need sharp points in order to get a better
performence in bursting balloons, this would be absolutely crazy.

Now, what I want to say is that LEGO gave us the objects RCX and NXT, and we may
try out how to use them at their limits, how to extract the best performence,
how to create better robots than others. This is what FLL competitions and
comparable contests are for, aren't they? The history of the RCX told us, that
LEGO invented it on the base of MIT Papert's work. And Papert teaches us to
eagerly consider what he calls "bricolage", a kind of being creative with
things, using them unexpectedly. So, why not investigate the absolute limits of
the bricks.

2. Considering a ball, which is perhaps the most exciting object ever invented,
because you can make such diversity of things with it, you have to restrict
things, set up rules, if you want to compare human performence that use it in
soccer, basketball or baseball. FLL has trouble with fixing rules for their
contests: RCX-only, NXT-only, both allowed, software, firmware settings etc. And
those rules are essential for the fairness of the competitions. At least FLL
should know the possibilities what you can do with the devices.

3. I could have taken a simplier comparison, but the extreme performence ratio
appeared, because I wanted to do the DFT on NXT. (In fact, I was attracted by
the NXT display, in order to have small mobile scope for a special project I am
working on.) So, let's reduce the question to : "How fast can we do sensor-data
collection?" and "How fast can we replace a value in an array at a certain
index?" And I may argue that NXT, equipped with 2 microcontrollers should be
able to return better performence in those tasks compared to the RCX.

4. As to PID, a www.seattlerobotics.org/encoder/200108/using_a_pid.html Peeves
contest would be fine to find out, if NXT-Peeves can do better than RCX-Peeves.

[Juergen Stuber]

Hi Claude,

"Claude Baumann" <cbaumann@...> writes:
>
> We have compared the sampling and computing speed of NXT
> and RCX. NXT uses standard firmware 1.03 and is programmed
> with the LabVIEW toolkit. RCX is programmed with ULTIMATE
> ROBOLAB. Both bricks do the same thing: computing the DFT
> on a small dataset of 128 points that are read from the
> legacy light-sensor on a shaft encoder that is rotated
> with a legacy motor.

do you have the DFT algorithm in some programming language like Java or C?

I'm just guessing, but maybe it could also be useful for speech recognition?
Or maybe telling the cat from the dog?
(The sound sensor should be usable as a microphone.)


Cheers

Jürgen

--
Jürgen Stuber <juergen@...>
http://www.jstuber.net/
gnupg key fingerprint = 2767 CA3C 5680 58BA 9A91  23D9 BED6 9A7A AF9E 68B4

[Claude Baumann]

In lugnet.robotics, Juergen Stuber wrote:

> Hi Claude,
>
> "Claude Baumann" <cbaumann@...> writes:
>>
>> We have compared the sampling and computing speed of NXT
>> and RCX. NXT uses standard firmware 1.03 and is programmed
>> with the LabVIEW toolkit. RCX is programmed with ULTIMATE
>> ROBOLAB. Both bricks do the same thing: computing the DFT
>> on a small dataset of 128 points that are read from the
>> legacy light-sensor on a shaft encoder that is rotated
>> with a legacy motor.
>
> do you have the DFT algorithm in some programming language like Java or C?
>
> I'm just guessing, but maybe it could also be useful for speech recognition?
> Or maybe telling the cat from the dog?
> (The sound sensor should be usable as a microphone.)
>
>
> Cheers
>
> Jürgen

Hi Jürgen,

The document, where I develop the theory of the algorithm has some text-pseudo
code ( a mixture of C and PASCAL) that you easily can convert to anything. Since
the document is math stuff, I largely prefer the := notation for assignment.

Note that the RFT algorithm is a recursive interpretation of the DFT. This means
that essentially it can be used as a point-to-point algorithm. The good thing is
that with it you can very easily implement the DFT on any device, even very
restricted in memory. The second new idea in the algorithm is that sines and
cosines are not calculated, but are stored as scaled fix-point values in a
look-up table. The reflections behind are that the number of samples is fixed at
program start. Having a fix number of samples N, I show in the document that
only N different sine or cosine values may appear in the DFT calculations. By
consequence, an N-sized constant array may be used. Another quality of the
algorithm is that you don't loose samples. Normally you sample N points, then
you operate the DFT. During the calculations you won't update your sample array,
unless you use a switching algorithm, engaging more than one data array...
making the code complex.

Now, what are the speed limits. The LabVIEW toolkit example uses the RFT
traditionally only after having sampled N-values. The Ultimate version
calculates the new twiddle factors at each iteration. So, with Ultimate we can
do 5.2ms (even 3.4ms, if the code is optzimized) per sample. As you can see in
the comparison the actual NXT firmware and the toolkit compiler need some work
to improve the timing. Anyway, applying the RFT in a point-to-point manner won't
allow audio sampling. But you certainly can do it, if you sample N values and
then apply the algorithm. Through the look-up table the algorithm is faster than
normal DFT and much shorter than FFT.

-Claude

[Juergen Stuber]

Hi Claude,

"Claude Baumann" <cbaumann@...> writes:
> In lugnet.robotics, Juergen Stuber wrote:
>>
>> do you have the DFT algorithm in some programming language like Java or C?
>
> The document, where I develop the theory of the algorithm
> has some text-pseudo code ( a mixture of C and PASCAL)
> that you easily can convert to anything.

thanks, I found it at http://www.ultimaterobolab.com/pdfs/5_RFT.pdf .

And pseudocode is fine with me, Java or C were just meant as examples
for textual languages.

> Since the document is math stuff, I largely prefer the :=
> notation for assignment.

:-)

Best is to avoid assignment and modifiable state whenever possible.


Jürgen

--
Jürgen Stuber <juergen@...>
http://www.jstuber.net/
gnupg key fingerprint = 2767 CA3C 5680 58BA 9A91  23D9 BED6 9A7A AF9E 68B4

[Claude Baumann]

In lugnet.robotics, Juergen Stuber wrote:

> Hi Claude,
>
> "Claude Baumann" <cbaumann@...> writes:
>> In lugnet.robotics, Juergen Stuber wrote:
>>>
>>> do you have the DFT algorithm in some programming language like Java or C?
>>
>> The document, where I develop the theory of the algorithm
>> has some text-pseudo code ( a mixture of C and PASCAL)
>> that you easily can convert to anything.
>
> thanks, I found it at http://www.ultimaterobolab.com/pdfs/5_RFT.pdf .
>
> And pseudocode is fine with me, Java or C were just meant as examples
> for textual languages.
>
>> Since the document is math stuff, I largely prefer the :=
>> notation for assignment.
>
> :-)
>
> Best is to avoid assignment and modifiable state whenever possible.
>
>
> Jürgen

1. Indeed.

2. I got an email some time ago from a 16 year old student Korean student, Jimin
Sung,living in the US, who is making an autonomous underwater robot. I was so
amazed of what he was doing. He sent me his application of the RFT algorithm to
fsk-modulation detection. Though incomplete, I posted it to
http://www.convict.lu/Jeunes/ultimate_stuff/mfsk.pdf. If a gifted 16 year-old
boy can use it, any adult Mindstormer should be able to use it.

Claude

[Claude Baumann]

../snip

>>and modifiable state whenever possible.
>>
>>
>> Jürgen
>
> 1. Indeed.
>
> 2. I got an email some time ago from a 16 year old student Korean student, Jimin
> Sung,living in the US, who is making an autonomous underwater robot. I was so
> amazed of what he was doing. He sent me his application of the RFT algorithm to
> fsk-modulation detection. Though incomplete, I posted it to
> http://www.convict.lu/Jeunes/ultimate_stuff/mfsk.pdf. If a gifted 16 year-old
> boy can use it, any adult Mindstormer should be able to use it.
>
> Claude

Ah, I forgot, he is trying to do this with an ARM.

[Claude Baumann]

In lugnet.robotics, Claude Baumann wrote:

> We have compared the sampling and computing speed of NXT and RCX. NXT uses
> standard firmware 1.03 and is programmed with the LabVIEW toolkit. RCX is
> programmed with ULTIMATE ROBOLAB. Both bricks do the same thing: computing the
> DFT on a small dataset of 128 points that are read from the legacy light-sensor
> on a shaft encoder that is rotated with a legacy motor. ULTIMATE ROBOLAB keeps
> the whole system running (managing sensors, sound, display, buttons,
> IR-communication...) e.a. all the things that the standard firmware also is
> doing; so there is no reduced funtionality and thus no tricky speed gain. Both
> programs are absolutely comparable. But the RCX operates the sampling plus DFT
> 22.8 times faster than NXT! This is intriguing.
> Beating the RCX is not that simple !

Now the new LabVIEW NXT tookit 2.0 that includes firmware 1.26 drastically beets
the RCX performance ( http://zone.ni.com/devzone/cda/tut/p/id/4435 ).

We repeated the experiment and now the NXT runs the DFT much faster than the RCX
with more features: power-spectrum (needs floating point data) with graph on the
NXT display; life graphs on the PC. Please consult the new experiment:

http://www.convict.lu/htm/rob/RFT_second.htm

So, congrates to LEGO and NI for this excellent programming work.

( Btw legoengineering (Tufts CEEO) offers free download of fw 1.28:
http://legoengineering.com/library/doc_details/250-nxt-firmware-v128.html )

Claude