Jun 19, 2006

Thoughts on Complex Programs...

A recent comment asked what I thought the limits were on complex programs in the NXT-G language. The short answer is "I don't know (yet)", since I've not had the time to push it to the maximum in this way. Additionally it's hard to judge what's ment by "complex" here as well: How big? How much decision-making ability? How many things going on at once? It seems clear to me that NXT-G allows significantly more complex programs than the old RIS code. Not just in the choice of "blocks" availible, but in the ways these blocks can interact. With parallel tasks, wiring of values between blocks, and flexible loops and switch structures, the complexity can get much higher. So perhaps a better way to phrase the question is "what limits does a NXT-G program bump up against?" Keep in mind, I may be completely wrong on these issues - it's going to take a bunch of new Mindstorms users to really test these limits. That said...

Speed of the editor is a factor: as a program gets larger, the editor slows down, especially with deeply nested control structures like loops & switches. This has generally limited me to nesting only 4-5 levels deep, although I've gone as deep as 12. Note you can bypass the speed issue somewhat by using MyBlocks, so with proper structuring, this might not be the limiting factor.

Program size can be much larger than I'd like at times: the largest program I've written has 39 blocks, 6 loops, & 1 switch (named "Nesting7.rbt", this is the program that gives JennToo her territorial behavior): this is 2 Mb (!) on my hard drive, but compiles down to 23.5 kb in the NXT. Based on having about 106 kb free memory on the NXT, it would seem you could hold a program of about 200 blocks, loops, and switches. But, I'm sure some blocks are "bigger" than others, and probably getting that big a chunk of contiguous memory is tough, so... I suspect I practical upper limit is around 150 blocks, if there's little else on the NXT itself.

Procedural & representational complexity is pretty good: NXT-G allows three types of variables (integer, logical, and string), a file access system, and "advanced" (over RIS) blocks like compare a value to a range (does the value fall inside or outside a range), or switch on a string value. The lack of arrays is a real problem... but one that can be gotten around in a couple of ways. It lacks string operators (parsing of strings). I've not yet bumped into limits on the number of parallel sequences (tasks) or variables. The fact that you can define your own MyBlocks actually helps a lot here as well: for instance, NXT-G does not contain a Modulo block, so I wrote one, and it was easy and transparent to use (good for kids or adults, but perhaps especially for adults teaching kids). I've done this for negation, trig functions, arrays, etc.

Talking completely off-the-cuff here, I'd say NXT-G is comparable to Robolab, and I've seen some amazing things done in Robolab under what I'd say are tougher constraints. Personally, I suspect the program size may ultimately be the limiting factor: compiled NXT-G programs just seem really large given what I think might be possible at the firmware level. For FLL, I don't think this will be a problem at all (especially as downloading new programs can be done easily and wirelessly, without worrying about IR interferance).

For adults pushing the limits, size may be the factor. Taking a Tic-Tac-Toe playing RCX-based robot and duplicating it on the NXT-G system is going to be very difficult, I think (I've built RCX-based ones, but even there I used NQC; at least on the NXT, I don't have the variable limits thankfully).

Final footnote: this may not be the end state for NXT-G (LEGO released upgrades for the RIS firmware and software over time; hopefully they will do the same here), and there are already third-party offerings (NBC by John Hansen, ROBOT-C by Carnegie Mellon, a Java-based environment from others, etc.) that appear to unlock much more of the power in the platform. Already NBC has clearly shown that NBC NXT programs can be much smaller than their NXT-G counterparts, and John has already been developing for both the PC and Mac communities (thank you!). I've got no worries about having powerful options, only how long I will stay with the "official" NXT-G language. For the RCX, I used Robolab for about 2-3 months before I moved on to NQC... for the NXT, I've not yet begun to tap the potentials of NXT after at least that long. And that's good news.

--
Brian Davis

12 comments:

Jim Kelly said...

What I'm looking forward to is seeing how LEGO uses the "Web Downloads" category in the Custom Palette - what I think we'll start seeing is free downloads for functions that LEGO finds are useful - sine, cosine, modulo, etc... and the ability to share MyBlocks is going to be interesting, too - it may lead to some sort of voting or review for determining who has the best solution for a repeatable event that can be encapsulated inside a MyBlock.

So far, no word on how LEGO will use the "Web Downloads" category, but I keep hoping ...

Jim

Jeff said...

Speaking of sine, cosine, etc. How do you create NXT-G trig functions? Since trig functions produce decimal fractions, how do you express trig values as integers? (e.g. sine of pi over 4 equals 0.707106 to six decimal places. How is this expressed?) How are trig values calculated? By table lookup? power series? Can you post a picture of one of your trig programs in NXT-G?

byronczimmer said...

May 8th post by Brian "A MyBlock primer (with a side of math)" covered this in detail, sin() specifically.


Archive Link (about 55/60% o the way down)
or use this direct link to the comments part here. (but then you won't see the pictures)

WOW, I wish you could link to a specific post in the archives in this blog environment.

There were comments made a while ago about moving off of blogger -- are those sentiments still active?

Brian Davis said...

As byronczimmer mentioned, I covered some of this in a previous post. Since the NXT doesn't have floating point math, I just use integer math with the result multiplied by 100, or 1000, etc, to signify two or three places to the right of the decimal. As to how to calculate, I've implemented it using both tables as well as power series (somewhat ugly ones, due to the limitations of integer math).

I agree with Jim on the "Web Downloads" stuff as well - this may add a lot of interesting options for the future.

--
Brian Davis

Jeff said...

Thanks byronczimmer and brian davis for pointing me to the examples for doing math. I once worked on a project with a mathematician who developed some numerical algrothims for calculating trig functions. The algorithms converged very rapidly (four or five iterations) and would probably work using integer arithmitic. A factorial MyBlock would probably be necessary. Since the algorithms are based on power series (rather than table lookup), the need to check angle signs would be eliminated if radian angle measure can be used.

An interesting project would be to use triangulation to create an x-y map of the location of several objects. For example the sonar sensor could be used to determine the distance to an object. The robot could be programmed to turn ninty degrees, move a specified distance, and take another distance measurement. The angle to the object, relative to the new location, and the two distances would be sufficient to determine an x-y coordinate location, relative to the robot. The only limit to these sorts of programs would appear to be the program memory size of the NXT.

Incidentally, if you are willing to do a little navigating, a demo verison of LabView is avialable on the National Instruments web site. The LabView IDE can be used to develop such algorithms without the need of a NXT brick.

I'm really looking forward to seeing the software people develop with the NXT-G IDE. It should be pretty interesting!

Satish said...

I neverwor ked or atleast saw a Lego Mindstorm. But i believe, with the bluetooth feature in NXT, we can integrate a PDA with NXT and override whatever limits are present in NXT-G.

Brian Davis said...

Bluetooth will allow a lot of interesting solutions - like moving all the "intelligence" of a program off the NXT and into a desktop or laptop computer, using BT to drive the NXT to run motors, read sensors, etc. *BUT*, how does BT control the NXT? It's either got to be via direct commands (this is an availible option - it's how you use things like mobile phone to communicate with teh NXT), or from within NXT-G (at least until other environments come along).

The problem is there are some big drawbacks to this. First is not everybody has that option (a BT equiped PDA and the know-how to hack it), so solutions withing NXT-G are still really good to look for. Second, there's some real time issues with using BT this way. Queing up and sending a BT message, waiting while it's received, interepreted, and then waiting while a return message is qued up, send, and recieved, and then finally acted upon, takes *time*... and for a lot of tasks (line following being a cannonical example), you just don't have the time. By the time the PDA's response comes back, the robot has completely lost the line (I've seen RCX-based line-followers that run more than 1 m/s along a 3/4" black line (they could cross the line completely in about 20 ms). Third, you are still limited by the Bluetooth stack that is built into the NXT... and I'm not sure what limitations that presents as yet.

--
Brian Davis

Jeff said...

Question: Are recursive functions posible in NXT-G? In other words, can a MyBlock be self-referential? That is, can a MyBlock contain itself?

Brian Davis said...

No, it does not seem possible to make recursive MyBlocks. I'm not sure at this point if MyBlocks are the equivilent of in-line functions (duplicating code for eaqch use), limited subroutines (all calls share the same varaibles), or closer to "true" subroutines (each call generates its own varaible stack). I suspect they function as limited subroutines, but I've not tested it yet.

--
Brian Davis

jeff said...

Computation of Trig Functions

If a high degree of accuracy is not required, and memory space is
limited, then computation provides an alternative to table look up
methods. The following example illustrates this approach for the cosine function.

Given a processor allowing only 16 bit signed integer arithmetic, a fair approximation for os(x), scaled by a multiplier of 1000 is

cos(x) = 1000-(x^2)/7+(x/23)^4

where x is angle in degrees and "^" means exponentiation. For example,
a^4 = aaaa. (This formula is derived from the Taylor series for the cosine function.)

The above formula may be implemented by standard NXT arithmetic blocks
using something like the following algorithm

1. xsqr = x * x
2. xsqr = xsqr / 7
3. x_23 = x / 23
4. result = x_23
5. result = result * x_23
6. repeat step 5 twice (hint: loop twice)
7. result = result - xsqr
8. result = result + 1000

where "*" is multiplication,
"/" division
"-" subtraction
"+" addition

The table below shows the values calculated by the above formula versus the more accurate intrinsic software function.

angle formula software
percent error
0 1000 1000 0
5 997 996 0
10 986 985 0
15 968 966 0
20 943 940 0
25 912 906 1
30 873 866 1
35 826 819 1
40 773 766 1
45 712 707 0
50 659 643 2
55 584 574 1
60 502 500 0
65 413 423 1
70 381 342 4
75 278 259 2
80 167 174 1
85 49 87 4
90 -76 0 8

As you can see, the error tends to increase as we approach 90 degrees.
However if our application involves only mid-range angles, then the
above algorithm provides accuracy to about plus or minus 5%. Perhaps a
person with more mathematical background than I can find further
improvements of trig function computation?

jeff said...

You can see a block diagram of the cosine algorithm at

http://home.earthlink.net/~xaos69/cosine_approximation.html

The block diagram was done in LabView but should easily implemented in NXT-G.

Brian Davis said...

Good solution! Indeed, this is just the type of solution I tried to implement for things like cos(). But there are a few problems...

Since NXT-G deals with only integers, all the intermediate calculation values are also truncated. To minimize the problem with this, it helps to keep the intermediate results as large as possible without overflowing. So for instance, instead of (x/23)^4, it works better to calculate x^4/279841. For the same reason it's nice to scale the result by the biggest number reasonable.

Another thing that came up when I was doing this was what "best" means. Minimizing the maximum error? Minimizing the sum of the square of the errors at all angles (a least squares fit)? Making sure that the function is continuous over the range of interest? The "right" answer depends critically on what you need the function to do. For my purposes, I used a 4th order polynomial fit that was continuous throughout the range as well at the endpoints, and scaled up by 100,000:

100,000 * cos() =
100,000 - 13 x^2 + x^4 / 12379

Don't think it's the "best"... it's not. But there's a complex tradeoff between what you need it to do, and how you go about doing it, as well as the limits of the language (integer), processor (bits of precision before overflow), and how much accuracy you want and how long you want to take (use a 6th order polynomial if you like, but it'll take more time).

That was a really good analysis, by the way!

--
Brian Davis

Related Posts Plugin for WordPress, Blogger...