2D Mapping Suggested Beacons?

[Ratfink]

I've been tasked as part of a current project to create 2D mapping for a Autonomous Vehicle which has the capability of Object Recognition with use a rotating camera.

 We currently are able to isolate and recognise information such as a right and left turn from a sign what we need is to be able to map the positions of these signs in a 2D grid and come up with a way of avoiding obstacles in the way.

The obvious problem that arises from this is how to work out the position of the car in relation to this map when it moves. I literally have no more Input/Output pins left apart from some PWM pins and luckily still have a full selection of ADC pins available. (Currently using DSP chip F2812 EzDSP starter kit).

i could place 4 beacons in the corner of the room i wish to map but as i require constant information as to the position of these beacons in relation to the car to accurately note where the car is within the 2D map.

Any suggestions as to what can be used as beacons and what sensors would be required to keep track of the position of the beacons in relation to the vehicle? 
 

[Admin]

Ok so what you ask for is a little complicated, but there are many ways to go about this.

First, a few questions.

What precision do you need? You robot will always have error - its just a question of how much is acceptable. More error allowed, the easier it is to program the robot.

How big is the playing field? Beacons suck at far distances . . .

Have you considered using encoders? Yeap, analog pins can read digital signals . . .

What about using Sharp IR to gauge distance from an object? That tutorial will explain how I generated a 2D map using just a sharp IR.

If your camera uses signs in the path, then by knowing the size of the sign a-priori your robot can calculate it's exact position with relation to that sign. Its sorta like stereo vision, except you only need one camera since you know the pixel to size ratio beforehand. Since you already have the camera working, this is the method I would recommend.

If you choose to use beacons, a very easy way is to make three beacons out of a bunch of LEDs: blue, green, and red. Then you put a simple analog color sensor on your robot to tell which beacon you are looking at. But it may not work depending on the position accuracy you require . . .

[dunk]

hi Ratfink,
so you are working on a project somewhat similar to my own.
so i decided early on, after doing a load of reading on stereo vision and pattern recognition that there are less processor intensive ways of sensing a robot's environment with a camera.

if you decide to go for beacons i have had some success making beacons for computer vision projects.
i made my beacons from LEDs (the brighter the better). you want to make the LEDs flash at a known rate.
you then want to take 2 pictures from your camera, timed so that exactly half a beacon cycle has passed.
this way you will get 2 pictures which are identical except in one the beacon will be lit. in the other the beacon will be dark.
subtract one image from the other and you will be left with only the beacon in the diff of the 2 pictures.

i had a working prototype for my latest bot. the beacon will be on it's battery charger. (i say "had". it's currently dismantled and will not be put into use until my bot becomes a little more complete.)
there are actually 2 LEDs, a known distance appart and a known height above the ground.
once i have created a diff of the 2 pictures i apply some maths to find the center of the 2 blobs of colour to get 2 points on the screen.
i can then apply some more maths to work out how far away each LED is using the height it appears at in the picture. (as the LEDs are mounted 1 meter higher than the camera, far away LEDs will appear low down in the picture. near LEDs will appear high up.)
now my bot knows how far away each of the 2 LEDs are, it can work out not only how far away the battery charger is and which direction relative to the bot, but also what direction the bot is approaching the charger from.

localisation from a single beacon.
neat hu?

dunk.

[Ratfink]

I will attempt to use the Sharp Distance sensor 40cm - 300 cm to build a 2D map using the technique you described in combination with the encoder.

The distances im working with is basically a large room the robot is a small radio controlled type robot

Heres some pictures by the team that built it last year we've basically inherited it and been asked to come up with a new idea and we've decided to build a autonomous navigation robot which will use a rotating camera for object recognition. It will basically consist of a few large signs pointing right and left directions with some obstacles placed randomly around the room and attempt to simulate obstacle avoidance and recognition by doing turns based on the signs it sees.

http://www.informatics.manchester.ac.uk/~mcai2lk2/index.html

As for size of room as i said its a large room i've not got exact dimensions but 30m square if not bigger the size of the signs are also going to be quite huge about 50cm squared to help with our object recognition.

What im planning to do is build a 2D map with positions of these signs create some sort of navigation algorithm that approaches the signs interprets the direction its pointing while avoiding obstacles. So the accuracy is not going to have to be great it just needs to show that it can approach the rough position of the sign and make a turn to the direction its pointing whilst avoiding obstacles along the way.

The problem i can see with the encoder is the accumulated error of the position of the car hence the beacons im not sure if the colour ones can be used to give an accuracy of say 10-20 cm for the size of the obstacle course im trying to plan. The kind of thing im thinking of using is ultrasonic sensors for each beacon which will emit at certain frequencies and having a reciever on the car which will be able to track its position within the beacon. I can forsee however alot of interference problems with this type of combination.

So im looking for a beacon which will emit something constantly and the car can sense the distance between the beacons and itself and work out its rough location while its moving.

The LED idea i have already thought of and could easily implemented the only problem i forsee is that the camera would have to be able to see the LED beacons constantly to be able to track its relative position to the beacons.

Im looking for a way of tracking the cars position with beacons without having to point something in the direction of beacons.

Any ideas for beacons/sensor combination would be gladly appreciated.

[hgordon]

Can you use color shapes or color combinations for your markers ?   

You probably already have some color blob processing algorithms available, and you could use the combination of different colors or color + shape to create your landmarks.  You'll need to experiment with color segmentation routines in various lighting conditions, but it sounds like you are operating in a controlled environment, so this should be manageable.

If you had some additional digital inputs, I'd suggest using an array of 4 IR detectors such as Vishay TSOP 1738 to get 360-degree coverage (1 bit per beacon).  Each detector has a 180-degree field of view, so the overlap of fields will give you some directional sense.  The TSAL 6200 IR emitters have quite a good range (10-20 meters), and you could modulate the different emitters with a different bit pattern in order to discriminate between beacons.

[Ratfink]

Some questions about the suggested beacon would they not interfere with each other or the Sharp distance sensor?

Im assuming your suggesting i use a detector which rotates and the angle at which the beacon is detected use the information as triangulation to work out the distance between the detector and each beacon and finally work out the position of the car with these relative distances?

[Admin]

Some questions about the suggested beacon would they not interfere with each other or the Sharp distance sensor?

to my knowledge, the only thing that can interfere with a sharp IR sensor is another sharp IR sensor positioned badly . . . if your beacon LED's use visible light (green, blue, red, etc), its impossible for them to interfere with the IR spectrum

oh, and make sure you get the diffused light LEDs cause the clear ones are highly directional.

[hgordon]

This won't give you distance, but it will give you rough orientation.  You don't need to rotate the detectors - they can be fixed, and you can use the fact that the field-of-view overlaps between the detectors to figure out in which quadrant a beacon is located.  So for example, if a beacon is straight ahead, the signal might only appear in the front-facing detector, but if it's 45-degrees to the right, it will appear in the front and the right detectors.  Also, you could rotate the robot to search for beacons.

As regards interference, the Vishay sensors have a 38kHz (with the 1738) filter, so you want to modulate the beacon at 38kHz with a bit pattern that uniquely identifies each beacon.  You would put a random delay between each burst of bits so it's not a continuous transmission.  I don't know about the Sharp range finders - perhaps the beacon would interfere, but since it's not continuous, you should be able to filter it out.  Actually, you might have better results by combining IR beacons and ultrasonic rangers.

Some questions about the suggested beacon would they not interfere with each other or the Sharp distance sensor?

Im assuming your suggesting i use a detector which rotates and the angle at which the beacon is detected use the information as triangulation to work out the distance between the detector and each beacon and finally work out the position of the car with these relative distances?

[Ratfink]

Im quite keen on the following idea:

http://www.restena.lu/convict/Jeunes/beacon.htm

although im assuming that at the distance im looking at 20m-30m the inaccuracy would be even greater and the transmitter/reciever would be even more expensive.

I have a budget of roughly $400 or 200 pounds since im from UK

My university normally gets their components from:
http://uk.farnell.com
rswww.com/

I really like the idea in the link but im assuming a encoder would be better to use due to the greater inaccuracy of a 20m range beacon network.

Anyone have an idea of anything that would work similar to above with better results 10cm-15cm inaccuracy is fine with me within a 30m^2 area of space.

[Admin]

if you have the camera already working, i still think you should just use only the camera. if you have a sign of known shape and size, you can easily calculate the robots exact position with respect to that sign. if you put simple colored leds around the room, the camera can tell which beacon it is looking at.

another beacon idea i have, and will probably build sooner or later, is a robot that does triangulation using not the timing of sound, but the amplitude of sound.

for example, close your eyes. now someone sneaks up to you and yells. now can you point to this person accurately without seeing him? yes, and this is because one ear hears the sound louder than the other ear, allowing you to discern the location of the person yelling. all you need is a single loud beacon (it could be ultrasonic so it wont annoy people), two microphones, and a sound absorbing object between the microphones (humans use a thick skull).

after all, running a high accuracy timer that can measure the speed of sound from three separate beacons is a huge waste of processing power . . . two simple ADC is so much simpler . . .

but again, i still say stick with your working camera . . .

[Ratfink]

grey level camera could just use number of LED's i guess only i would need alot of them or stop the car and keep rotating camera to look for beacons.

Only reason i try and stay away from the LED idea is that this was done by last years team to track a leading car with two LED's to work out its relative distance and we are currently being discouraged from using it.

Videos shown here:
http://www.informatics.manchester.ac.uk/~mcai2lk2/multimedia.html

[hgordon]

I likewise agree that the camera should be your primary sensor, and in addition to using visual cues as suggested by Admin, you can use a single camera as a rangefinder by adding a laser, as shown here -

    http://www.pages.drexel.edu/~twd25/webcam_laser_ranger.html
and
    http://www.seattlerobotics.org/encoder/200110/vision.htm

[Ratfink]

Thank you hgordon i've seen that link before but you've just reminded me how i can use this along with the 2D mapping method shown on this site