Multitasking Robots

[krich]

Now that I've read up on robotics quite a bit, I understand that even the most simple task can be somewhat processor intensive.  It usually requires preprogrammed delays to read sensors properly, thus reducing the sample rate of sensors, thus reducing the distance in which the robot can travel over time without overrunning sensor responsiveness.  I can't help but think that there must be a better way.

All the programs I've seen run in pretty much a linear fashion.  In very simple terms, while you are reading your sensors, you can't move, while you move, you can't read your sensors.  All this happens at fairly high speed, so a human may never observe any ill effects.  However, when  you've got to do some heavy duty sensor work (multiple sonars or Ir sensors, 2D mapping, or 3D mapping), then things start slowing down because all the delays start adding up.  So, I ask myself...can these processors do simple multitasking?  I've used multithreading on Linux to speed up an app I developed by over 1000%.  It was amazing.  I'm hoping something similar is possible on my little ATmega8 (or bigger if need be).

In a previous post, a few months ago, Ro-Bot-X mentioned AVRx

You may want to take a look at AVRx, a Real Time Multitasking Kernel for AVR micros, by Larry Barello.
Here is the link:
http://www.barello.net/avrx/index.htm

Looks really good.  I envision a multitasked robot to have many, many threads.  One thread for each sensor, one for each motor or servo, one for handling calculations based on input from sensor and motor threads, and a master thread handling idle time and thread priority.  In this scenario, the motors could be going while waiting for the echos from the last sonar reading to dissipate before taking another reading, etc.  I suspect the sensor and motor responsiveness would see a significant gain in responsiveness.

Has anyone gone down this road with AVRx or FreeRTOS?  Does it help responsiveness as much as I'm theorizing?  What about multiple MCU's?    How do they talk between each other?  SPI?

Why?  If I'm going to build a cat chasing robot, its going to need to be both fast and nimble.   

[Steve Joblin]

Parallax has seemed to take the first major step forward with the Propeller chip that they designed from scratch to be truely multi-processing.  You can read all about it and "Spin" (the programming language) here --> http://www.parallax.com/propeller/index.asp

[JesseWelling]

Maybe learning more about Operating Systems would help you out.
Try freertos.org it's the easiest embedded operating system I have found to get started on.

[dcole07]

Processors can only look at one bit at a time. bits become bytes, become KB, MB, GB, TB... so that's a lot of work. The problem can be solved by having multiple processors, but then you have to deal with process order. Sometime information goes in ABC, then comes out CAB. This is why current multi-processors don't share single programs amount more than one processors. This is due to time delay when switching from high (1) to low (0) and low (0) to high (1).

When the price of processors goes down or something, we may have a processor for each task, until then you would have to pay something like $1,000 for each processor.

[krich]

Not sure I'm following you dcole07.

All I know is that there are a lot of delays programmed into the simple robot code that I've reviewed.  It seems to me that the processor could be doing something a bit more useful during those delays than incrementing a counter 4 million times.  This would be achieved by a multitasking RTOS which could switch between tasks based on task priority and activity.

Has anyone here built a robot using AvrX or FreeRTOS?  What were the noticable performance gains, if any?

[bens]

I have a small amount of experience with FreeRTOS and it seems quite nice, though it does add overhead (both flash and RAM) to your programs.  I personally feel that there's a middle ground between a real-time OS and loop delays that is in general better for many robotics applications.  For example, you could fairly easily use timer interrupts to time your sensor delays so that your processor can go off and do other things in the interim.   Tie your sensors to interrupts so that you handle them as sensor events occur rather than having to sit around idling the processor while waiting for them.

If your choice is loop delays or RTOS, you'll obviously see significant performance gains if you go with the RTOS.  In general, though, I think RTOS will always be slightly lower performance than the best custom, interrupt-based program you could write just because of the overhead associated with the RTOS.  Of course as your program grows more complex, there comes a point where the RTOS becomes the much simpler solution.

[JesseWelling]

I use FreeRTOS on my robot. I find that even using the OS I've barely reached 50% processor load on my ATmega128. This is due to the event driven nature of the code. I'm using it to control two channels of drive motors (differential drive with 4 motors but one signal per right or left half) with PI control from two quadrature encoders, a scanning servo with 3 IR range finders that have analog output, a gyro and 2d accelerometer both  analog, and a sonar that outputs distance in serial, and it is relaying information to a small computer on board through serial and taking commands by I2C, and providing emergency stop based on the IR and Sonar distances.

Writing my own scheduler for the PI control and Servo Scanner alone would not be very fun, and rather pointless because I'm not going to come up with a better solution unless I want to sink all my time in it instead of the AI. That's just my take.

The OS is around 19k depending on how you compile it.

[JonHylands]

Using a RTOS is nice in some ways, but for smaller chips it adds too much overhead. You can structure your program like a finite state machine, and thus completely avoid any delays.

My mini-sumo Seeker 2 uses an FSM for its behavior. The main loop looks like this:

Code: [Select]

do {
endTime = millisecondClockValue + CYCLE_TIME;
heartbeatExecute ();
edgeTest ();
rangeFinderGet ();
nearIrDetect ();
fsmExecute ();
do {} while (millisecondClockValue < endTime);}
while (TRUE);

CYCLE_TIME is 10, so the main loop runs at 100 Hz. millisecondClockValue is a 32 bit integer that is incremented once every millisecond by a hardware timer interrupt.

- Jon

[Admin]

Be careful to not get stuck in that 'software can fix everything' mode . . . (apologies to the programmers out there, a mechanical engineer is on his soap box )

Your robot can only go as fast as your sensors . . . sonar can only pulse a few times per second due to the laws of physics, rangefinders need a finite amount of time to scan, etc. On every robot I have ever made, my speed limitation was the physics of the sensor and not my processing speed.

Consider other ways to boost speed, such as using multiple sensors to scan faster, etc. Or dedicated processors for each sensor (the CMUcam has a dedicated processor built in, for example).

There are also other techniques to speed up your program, such as reducing accuracy to increase speed. Who cares if your robot can locate a target within .01% accuracy when 10% will also work. For example, I can scan at .1 degree increments with my rangefinder for a 10s scan, or do 1 degree increments for a 1s scan. So what if I'm .9 degrees off? Saving 9s is a huge deal! Basically determine your maximum acceptable error and take it.

Then other obvious stuff like avoid floats, long ints, etc. Use lookup tables for complex math . . .

Jons method of a FSM is by far the fastest.

I take an algebraic fuzzy logic approach which uses basic algebra, gives good between state transition, and is 'good enough' for what I want. It typically requires 10%+ error, but for the speed gain it works really well.

[krich]

Thanks for the input guys.  If you've read any of my other posts, I'm obviously I'm not at a point where any RTOS will help me yet.  I've got much larger issues, like learning all this dang electronics stuff.   

My programming experience is in back-end systems and some threading.  I've never written a program that actually affects the physical world, and thus have never been constrained to the laws of physics (as Admin has so astutely reminded us).  Its definitely not as easy as it seems, at first.  Just read my recent post on simple servo control.     On second thought, don't read it...the answer to my question was embarrassingly simple.   

[paulstreats]

aswell as making your own operating kernel multitasking system, you should also look at the possibility of multiple controllers.

have 1 mcu for sensors, 1 for moving etc...

when you think of the problem in object programming terms such as java objects, 1 mcu = 1 object with input / output pins.(javabeans was explained to me as operating like an interlinked mcu system when it was in its early days)

you could develope a small operating system for a basic robot with 1 mcu but eventually you are going to need many mcu's, even people that use laptops on robots will eventually need more than 1 system once they start pushing for object recognition etc (theyll eventually want a seperate system to do facial recognition or the whole thing would start operating too slow).

[krich]

What methods are there for multiple MCUs to communicate?  I've read the tutorial on I2C.  Are there others?

[paulstreats]

you could try connecting them through uart rx/tx pins direct most mcus have them built in now

[JonHylands]

I've done a number of robots with multiple microcontrollers, and there are definitely pitfalls to avoid. It sounds like a nice way of doing things, but the communications between them is definitely much more of an issue than it sounds.

The problem is one of timing. Many sensors require very precise timing, and being interrupted in the middle of measuring stuff can throw it off enough to be useless. Some of the newer microcontrollers, with more memory and faster clock speed can do a better job of it, because they can handle the communication on interrupts in hardware, and thus the bus communication doesn't overwhelm the processor enough to throw off the sensor processing.

- Jon

[dunk]

so my recent efforts have all used multiple microcontrollers communicating over an i2c bus.
one of the early mistakes i made was to try and have each microcontroller initiate communication on the bus.
this caused all sorts of timing issues.

a far more successful strategy i have found is to have a master node control all communication.
this master node polls the other nodes for incoming data and controls outgoing data.
in this way you can be sure only one controller is trying to access the bus at a time and it minimises the chances of a microcontroller having to pause a program while it waits for the bus to be free.

i do allow exceptions to this rule for inputs that need to be acted upon quickly, for example i allow the node monitoring bump sensors to interrupt the motor controller node if a collision occurs.

dunk.

[Ro-Bot-X]

How is the Lego firmware able to hadle up to 10 tasks running in parallel? Isn't it possible to make a firmware like that for avr micros?

[paulstreats]

The problem is one of timing. Many sensors require very precise timing, and being interrupted in the middle of measuring stuff can throw it off enough to be useless.

I usually dont interrupt and ask for sensor data, i would probably get 1 mcu to read the sensor, then transmit the data to another master node then read the sensor again so everything is done without needing prompting.

[Admin]

Probably not very efficient/elegant, but my method is to have the sensor mcu spit out data non-stop, and my control mcu will only read it when it needs it. This was my method with the CMUcam on my old PIC boards . . .

[Ro-Bot-X]

I have once experimented with multi microcontroller comunication, but used separate I/O lines for each and serin - serout commands (yes, in basic). The sensors mcu sends data every loop pass and generate an interrupt on the main mcu that would read the data, decide what to do and send commands out to the motors mcu.

[Steel_monkey]

Why don`t you use something faster intead of all this multiple MCU systems? ARM7 is reasonably cheap and fast today- 70 MHz, 4-10$, many pins, 6 communication ports (2 USART, 2 SPI, I2C, SSP), not big consumption (40mA). The only thing is that lead distance is little ( 0,5 mm), so home PCB making is a challange. I hav already bought one (LPC2102), and going to make experiments with it this winter holidays. Also, if you need more speed, you always can use CPLDs.  If ypu can affors Sharp IR, why don`t you use something siutable for it?

[maverick monk]

or you could hack a old laptop... thin of the power that a 400mhz processor has compared to these little avr controlers.

[Steel_monkey]

It consumes to much for fast little robot. You need acid cells from UPS to feed it. Palm PC is better choise, but it lack of simple communication interfaces (like RS232 for example).

[paulstreats]

A fast processor running many different processes will eventually run slow.
How would you interface say a sharp ir distance finder with the limited ports?
If you interface it through a usb to serial to mcu (for pin control) then you are also losing time through communications protocols.

[HDL_CinC_Dragon]

Eh you could probably blue tooth the crap out of the thing but that would probably be a tad slow hooking up that many things to it... just a thought

[JonHylands]

A fast processor running many different processes will eventually run slow.
How would you interface say a sharp ir distance finder with the limited ports?
If you interface it through a usb to serial to mcu (for pin control) then you are also losing time through communications protocols.

A properly done complex system is a combination of high level processors for doing the complex stuff, and low level processors for interfacing to hardware.

I'll use BrainBot as an example, since I built it and am familiar with these aspects of it. For high level work we've got a PC, which is connected to the robot over a wifi link. Onboard the robot is a gumstix, which acts as an interface between the wifi connection and the Bioloid bus. The bus is the interesting part of the equation - it allows you to hang a large number of smart devices (sensors and actuators) together, and provides a pretty decent communications protocol to go along with it. On the tracked version of BrainBot, we've got around 14 servo devices on the bus, along with a six-axis IMU, a couple pressure sensor interface boards (for the gripper touch sensors), and a motor drive board.

I could plug in half a dozen Sharp GP2D12 analog IR rangefinders into the motor drive board without changing a single thing about the hardware and software on the embedded side, and that information would become available on the PC with a tiny change to what it asks for. Having a small amount of latency is not a bad thing - the sensors themselves have a large amount of latency, only updating their state every 40 ms or so.

Anyways, it is doable, but it takes a lot of planning and development work to get there...

- Jon

[Rebelgium]

A fast processor running many different processes will eventually run slow.
How would you interface say a sharp ir distance finder with the limited ports?
If you interface it through a usb to serial to mcu (for pin control) then you are also losing time through communications protocols.

A properly done complex system is a combination of high level processors for doing the complex stuff, and low level processors for interfacing to hardware.

I'll use BrainBot as an example, since I built it and am familiar with these aspects of it. For high level work we've got a PC, which is connected to the robot over a wifi link. Onboard the robot is a gumstix, which acts as an interface between the wifi connection and the Bioloid bus. The bus is the interesting part of the equation - it allows you to hang a large number of smart devices (sensors and actuators) together, and provides a pretty decent communications protocol to go along with it. On the tracked version of BrainBot, we've got around 14 servo devices on the bus, along with a six-axis IMU, a couple pressure sensor interface boards (for the gripper touch sensors), and a motor drive board.

I could plug in half a dozen Sharp GP2D12 analog IR rangefinders into the motor drive board without changing a single thing about the hardware and software on the embedded side, and that information would become available on the PC with a tiny change to what it asks for. Having a small amount of latency is not a bad thing - the sensors themselves have a large amount of latency, only updating their state every 40 ms or so.

Anyways, it is doable, but it takes a lot of planning and development work to get there...

- Jon

Very interesting Jon.
I searched SoR for more info about your Brainbot, but to my surprise the only topic that came up with searching "Brainbot" was this one!
I found the site via google, and it's really interesting.


Everyone, visit http://www.bioloid.info/tiki/tiki-index.php?page=BrainEngineering+BrainBot
If you want to learn more.

[HDL_CinC_Dragon]

heh he kinda looks like the "Brain" character from the game Quake II lol

[JonHylands]

There's a lot of information on my blog about it as well...

http://www.huv.com/blog

- Jon