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
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
Comments
So far, no word on how LEGO will use the "Web Downloads" category, but I keep hoping ...
Jim
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?
I agree with Jim on the "Web Downloads" stuff as well - this may add a lot of interesting options for the future.
--
Brian Davis
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!
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
--
Brian Davis
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?
http://home.earthlink.net/~xaos69/cosine_approximation.html
The block diagram was done in LabView but should easily implemented in NXT-G.
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