A Navigation Quandry (advice needed)

[jpwalters]

Hello everyone, this is my first topic here, and before getting into my question I just wanted to say thank you to Admin and the many posters who's advice I have been reading here for months.  You guys are great, keep it up!

So here's my question, and it's sort of complicated so bear with me.  A group I'm working with at school has a set of tasks we have to accomplish with a robot, and one of these tasks involves navigating an 8' x 8' course.  We're having some debate regarding what would be the best way to navigate this course, and so I wanted to get some advice.  To keep things as simple as possible here, I won't go into too many details about the other stuff.  We need to be able to autonomously navigate to each corner of the course as well as return to the center of the course at least once during the run.  The corners have to be visited in a specific (yet changing with each run) order, and we need to get within about a foot of the corner to accomplish what we need to do.  The course is mostly white, so there is no way to use line following or any other kind of path-finding algorithms to navigate the course.

The course we will perform these tasks on is also set up with a single, side-emitting LED sitting eight inches above each corner, as well as an LED hanging eight inches above the center of the course, and each LED is pulsing at a frequency from about 10 kHz to 100 kHz, with each corner set at a specific frequency.  So, one option for navigation would obviously be to use these LEDs in order for the robot to locate the corner.  If it can detect the frequency of the LED, it will know which corner that LED is located at, or it can navigate to the center of the course using the center LED.  Another option we have discussed is to use some kind of 2D mapping, such as the Admin described in his wavefront tutorial.  In this case, the course would be entirely mapped to memory, and the robot would essentially navigate the course based on a predefined path saved in memory, meaning there wouldn't really be any kind of outside stimulus affecting navigation.

There are obvious issues with each.  Using the LEDs seems like a good idea, but the problem is that we're having trouble figuring exactly how to use these LEDs to tell the robot where it needs to go.  What kind of sensor do you use for that?  It has to be something that can detect differing frequencies in the range of several kHz, and it has to be sensitive enough to detect the LED from 8' away, and that can ideally tell how far away the LED actually is.  On the other hand, using a predefined map for navigation means we're taking some big risks, such as wheel slippage or other things that might cause the robot to travel on an actual path that's different from what we want.

I know it's a lot to ask for, but can anyone give some advice on what might be the best method, and how specifically we can go about accomplishing that method?  I'm sure we can figure something out eventually, but you guys offer a wealth of knowledge, and it would be careless of us not to explore every option.  Again, thank you for all of your help.  If there's anything that needs to be clarified regarding my question, please let me know and I'll provide whatever information I can.

[Soeren]

Hi,

Are the LED's infrared or...?

[jpwalters]

They are white light, side emitting LEDs.  These, to be exact.  The different corner lights will be pulsing at 10 kHz, 20 kHz, 40 kHz, 60 kHz, and 80 kHz.

[Soeren]

Hi,

Too bad really, but I'd still go aiming for the LEDs.

If the corner LEDs are mounted in the same height mounting a phototransistor in a long(ish) light tight (matte black inside) tube to exclude daylight/artificial light some, eventually with a small lens to focus the light onto the phototransistor.

To decode which corner you're looking at, either use tone detectors directly or clean up the signal and count the pulses in eg. 10 ms (should give you 100, 200, 400, 600 and 800 pulses during that interval).
The number counted should be accepted if inside eg. +/- 10% (or 20%), so 90 to 110 (80 to 120) pulses would be the 10 kHz beacon.

Relying on dead reckoning will be prone to too many errors, even given the small area IMO.

[jpwalters]

Do you think the phototransistor will be sensitive/fast enough to actually count the individual pulses at that frequency?  If so, how exactly would you implement this in code (we're using the Axon)?  Also, could you explain the tone detector you mentioned?  I haven't heard of that before.  Thanks, I really appreciate it.

Also, I agree about the "dead-reckoning" method.  We're already seeing issues with our robot even being able to travel in a perfect straight line, and being able to navigate an entire course this way could prove to be almost impossible.  Using the LEDs is certainly the best option in my opinion, it's just figuring out exactly how that's posing a problem.

[Ro-Bot-X]

So you are navigating a maze like course, right? Then why not use both methods? Have the map stored in memory to find the shortest way to each corner, use the LEDs to identify the corners on the map and you also need distace or proximity sensors to keep you from bumping in the walls. A compass may prove helpfull to make course corrections if the robot does not turn or drive straight.

Depending on the size of the wall openings and corridors and the size of the robot, you may look at the way mouse robots navigate their way out of the maze driving so fast and not touching the walls. Some of them are small and able to go diagonaly instead of zig-zagging. They just use encoders and distance sensors to build the map of the maze so in the second run they use the shortest path to exit the maze (or get to the center).

Some time ago I competed in maze contest and used a left side wall following strategy, using distance sensors to keep away from the walls and I even built a mechanical version that was using a wheel feeler to follow the wall.

These are ideas that you may look into, try to get the ones that are easier for you and faster, because in the end the fastest robot will win!

[jpwalters]

See, this is the catch though, it really isn't a maze like course.  It's completely open.  If it were a maze, it'd actually make things much easier.  This is an 8' x 8' course that has no walls whatsoever (including the edges of the course, which we are not allowed to cross despite there being no barrier there), and there are no lines either, at least not any that could assist us in navigation.  Here, this might make things more clear:

The colored squares in the middle and the numbers at the four corners are painted onto the surface of the course... otherwise, everything else is white and completely flat.  The little dots on each corner represent the LEDS pulsing at different frequencies to indicate a specific corner, which sit eight inches above the surface of the course.  So as you can see, the only real features that can be used to navigate consistently are the lights.

[jpwalters]

One thought I just had.  Is it possible that enough IR light could be coming off of these lights that we could use an IR Sensor to detect the frequency modulation?  The only reason I ask is that I'm worried that a photoresistor/phototransistor might not have a fast enough response to be able to detect the faster frequencies such as 80kHz.

It's really frustrating, as I can't find any kind of sensor that will accomplish this kind of task, which makes me wonder why they chose this method for navigation for the competition.  There must be some way to do it though.

[Ro-Bot-X]

This is odd...

How about using 4 sensors on top of the robot on a turret looking directly at the 4 pulsing LEDs at start? You just have to position the turret so all sensors see the LEDs. Then while turning, rotate the turret so it faces the LEDs all the time. Perhaps use a stepper for the turret.

I know light bulbs emit IR but not sure about white LEDs. You have to read their data sheet. All IR sensors have a photodiode or phototransistor as the receiver, but then the signal is filtered, demodulated, etc. on some IR sensors. So, a photodiode should work with pulsing light. Just make sure to install it in a tube, like Soeren advised.

[jpwalters]

Hmm, yeah, from what I've been reading tonight a photodiode seems to be the best bet in terms of response time.  Some good suggestions here, I'll take them all into consideration, as well as any others that people may have.

Assuming that I use Soeren's method, can anyone recommend a good way to interface the sensor with the Axon microcontroller?  From what I understand, the output from the sensor will be a sinusoidal-ish analog signal (depending on how fast the response time is), and so the idea would be to count how many pulses we get over a given amount of time.  Is there a function that already exists to do this, or will we need to write our own?  And if so, any suggestions on how to do that?

Sorry for all the questions, but I really appreciate your input and advice everyone.

[gordon.cooke]

Do you know for certain that the corner markers are white LEDs?  Loking at the data sheets on the LED you gave, the white LED has a significant spike between 425nm and 450nm.  Problem is most photodiodes and such arent very sensative in that range.

Perhaps you could get a narrow band pass filter that only allows 425-450nm through and blocks everything else.  Then use a photodiode behind it to look for the bright spot.  High end would be one from Omega Optical (XB73) for about $140 or Newport (10BPF10-440) for $130.

A much cheaper option is gel filters that are used in theater lighting.  They arent as precise as science ones. You can get a large sheet for $5 or so.  Quick look at the spectra- suggest Roscolux #R381 Baldassari Blue  (you could also try some other filters or maybe two filters together).  Realize that only a percentage of all light will get through the filter.  About half of the light at the 440nm peak will get through.  Since most detectors arent super sensative in this range you may need to amp the signal.  

Im sure there will be noise and you will have to tinker a bit.  But the concept is to basically make your bot blind to anything except the portion of the spectrum that the beacon is highly intense at.  A little experimentation and youshould be able to threshold the LED from the ambient (especially since most indoor light is rather orange).  If you find out that the LEDs arent white but are colored, you could use a similar aproach with different filters if you cant find a detector that only works in that range.

[jpwalters]

Yeah, they're definitely white.  That's a pretty interesting idea actually, and one I hadn't thought of.  I'll definitely look into that, thanks!

Edit - Would something like this be sort of what you're talking about?

[jpwalters]

For anyone interested, a quick update:

Yesterday, we did some tests concerning the ability of photocells to detect the pulsing LED light.  We basically used a Breadboard interfaced with an NI Elvis and Labview Virtual Instrumentation software to produce the square-wave pulse for the LEDs at several frequencies, and to monitor the response of the photocells.  Unfortunately, we did not have a photodiode to test, but we did have have a few photoresistors.  With the photoresistor right up next to the pulsing LED, we actually obtained surprisingly good results, despite the slower response time.  Even at frequencies as high as 80 kHz (the highest we'll need to detect), we got a very solid and clear 80 kHz response from the photoresistor on the oscilloscope, even though it was only at around 20 mV.

The bad news is that, at distances more than a few inches, we pretty much completely lost the signal.  Even turning off all other ambient light in the room, including the computer monitors and covering up other panel LEDs, we still couldn't get any kind of reading whatsoever from the photocell.  So, my question is, can anyone recommend any kind of photodetector (either photoresistor, photodiode, whatever) than can detect such an LED from several feet away?  I can still use the filtering method to filter out all the other ambient light, or use a high-pass filter so that only high frequency pulses are get through to the input pin of the microcontroller, but I don't know if either of those methods will solve the problem of detecting a light so far away.

Any suggestions?

[CALEB]

MAN I WISH WE COULD FIGURE OUT HOW TO USE THE LEDS!! If anyone knows of a sensor out there that can just be be bought or built  please let us know.We are running out of time .

[Admin]

jpwalters, photoresistors are horrible for transmitting data due to a slow transitioning.

You want to use IR LEDs. However with that alone you'd only get a few inches or feet.

As such you need to modulate it. Basically you PWM the LED as some frequency, typically 48kHz.

Then your receiver has a low/high pass filter that only accepts 48kHz signals.

Basically how a TV remote and a Sharp IR works.

[jpwalters]

If only we could do that, I would be thrilled.  Unfortunately, the LEDs I linked to above are set in stone as the ones they will be using at the competition, so if we use the LEDs for navigation, it has to be those.

I think we may have to do something else though.  I've racked my brain with this issue and can't seem to find any kind of workable solution so far.  Thanks for the advice though still, we appreciate it.