An absolute sense of place

[Webbot]

If I have a robot, with wheel encoders, that runs around then, theoretically, I can calculate where the robot is relative to its starting point. ie its starting point is the origin and it has a position vector for the current position (x,y) relative to that point, and a direction vector indicating its current direction of travel. The x,y axes will be arbitrary. OK: thats just the problem - so lets not worry about encoder cumulative errors, choice of x,y axes etc. Just take it as read that the robot knows where it is in relation to its start point. Lets assume this robot is happy just running around, creating a map of its environment, avoiding stuff, maze solving, eating cheese and being a thoroughly excellent robot.

Next I place (ie switch on) another similar robot but at a completely different start point and pointing in another direction. This robot is also happy just running around doing the same stuff.

The only difference is that their starting points (ie the map origin of 0,0) is in a different place and that their initial x,y axes are different. This could be fixed by a translation (to share the same origin) and a rotation (to share the same x,y axes). Then both of their maps are identical and they can co-operate by sharing their map data.

So lets assume that all of the above is 'true and makes sense' - does to me but then I'm only human!!

So my question is: since each robot only has a sense of position according to its start point then how do they exchange 'enough' data in order for them to zero their start points in to the same position. I know there are various hardware systems out there that use beacons (either placed on the floor or screwed into the ceiling) - but my wife would go beserk if I wired out the house in this way!! Fine if you've got robots running around a warehouse. Also its not very portable.

I think the solution can be simplified to a degree: in that we dont care about the absolute physical localtion of the robots - we only care about their location relative to each other and relative to a common, if arbitrary, start point.

Here are some of my thoughts....

You could have very low intensity IR transceivers on each robot so that once they first get into close contact then they can share their info. ie they both know whey they are relative to their own start points and their direction of travel relative to their own initial x-y axes. They also know that they are very close to each other. So if you sub-divide floor space into 6 inch squares then you could say that they are both in the same square (you could adjust this by knowing the radius of each robot base to be more exact). Therefore one of the robots could re-adjust his origin, and initial x-y axes, to be in sync with the other robot. Now they have a common map of the world relative to a shared origin.

I don't think that RF, Bluetooth etc will help because, as I see it, you need to have really low power transmitters so that communications only happen when they share a common point.

When you first switch on a new robot then its primary goal could be to chase any other moving targets - so that it can then get in sync with the 'robot pack'. Once in sync then the robots could collaborate, via a master laptop link if necessary, to share their common view of the world. Divide and conquer !!!

Can anyone else think of another easy way for two robots to agree an origin and x/y axes for their map data WITHOUT requiring ANY external devices.

[cosminprund]

Here's my idea.

I'll first start with each robot. Since the robot wants to make a nice map of it's environment I assume it would have the minimum required mapping capabilities: (a) It would have a way of finding it's own position relative to it's starting point and (b) it would be capable of determine the position of foreign objects relative to it's current position: both distance and angle! Problem "a" is probably easier to solve since it's a known problem (maze-solving robots have the solution to this problem). Problem (b) might need a bit more imagination to solve. I imagine an range finding sensor rotated by an motor with an encoder (the way the RADAR works on ships). While a crude, squarish map can be built without knowing angles, the angles are necessary once two robots meet!

Let's have a meeting between two robots, A and B. Let's talk from robot A's perspective: It just met an other robot (robot B). It would need to know it actually met an other robot and not some piece of furniture: RFID tags? Robot A would know it's own position (say it's at (acx, acy) - "c" from current, "a" from robot A). Robot B also knows it's own position, and since it's capable of mapping it's environment it knows robot A's position: From B's perspective robot A is at coordinates (bax, bay) - "a" from A's coordinates ). Robot B first sends robot A what it assumes to be robot A's position (bax, bay). Then it sends what robot B assumes to be the angle it saw robot A at. Then robot B starts sending every other feature it has on it's map, in it's own coordinates. Robot A would then use the common reference point (it's own position in it's own coordinates and in robot B's coordinates) to translate the coordinate system and then the angle to rotate it back to it's own coordinate system.

Of course, once errors start creeping in things get allot more interesting. I'd make the robots rank each place found on the map with a number: this way the robots would be capable of identifying fixed objects (like walls or corners). Then I'd have the robots go to known fixed objects once in a while to recalibrate the coordinate system. Next I'd try to find an algorithm for identifying certain features on the maps of different robots (ex: clearly identify two opposing walls on the map made by robot A and the map made by robot B; At the time of data transfer from robot A to robot B I might use those two walls to scale the map! maybe not all robot wheels are the same size)

[Dscrimager]

I would think that you could use the dead-reckoning to get into some proximity and then use some sort of beacon and sensor arrangement on each bot.
Like this: http://www.pololu.com/catalog/product/701
I was considering it to allow my big bot to find homebase and recharge...

[Webbot]

@cosmiprund - I think we are talking about the same kind of 'software' to exchange position/direction vectors. Thanks for your thoughts. But my main concern is the circuitry that the 2 robots would use to establish a comms link once they are in proximity.

@Dscrimager - the Pololu beacon is a possibility - but at approx $30 per robot seems like overkill.

I think a simpler IR kinda circuit could work. So I might look at using a traiditional 'line following' kind of set up of transmitter/receiver for the comms.

[Ro-Bot-X]

You should look for the Panasonic IR sensor (PNA4602M for example) or the TSOP4838 IR sensor. They work on a specific frequency as IR remote control receivers. It is easy to set up transmitter-reciever pairs, you need a IR LED and this sensor. There are libraries for RC5 signals used for TV remote controllers. This is the setup I have used with all my microcontrollers to communicate to each other and IR remote control.

Here are some links:
http://www.atmel.com/dyn/resources/prod_documents/doc1473.pdf
http://avr-mcu.dxp.pl/rc5+remote+control+infrared+assembly.html

And code for sender and receiver in Arduino:
http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1176098434/6#6

[Webbot]

Thanks - I'll look into that. You could save me a load of time reading datasheets by answering this.....

Assume that more than one robot gets close to Robot A - so that they all start swapping info with robot A. Is there anything to help get round the interference between robot B->A, C->A, D->A etc. Bearing in mind that robot A may actually be any random robot. Or is that just down to the data in the packet?

[Soeren]

Hi,

Assume that more than one robot gets close to Robot A - so that they all start swapping info with robot A. Is there anything to help get round the interference between robot B->A, C->A, D->A etc. Bearing in mind that robot A may actually be any random robot. Or is that just down to the data in the packet?

That's a software problem - You might wanna read up on the protocol for Token Ring networks and use a similar but simplified approach.

[Webbot]

Thats what I expected. Just didn't know if PNA4602M could help with that as well. No point re-inventing the wheel - we all know its an oval right?

[Ro-Bot-X]

I was thinking of using this method of communication for a robotic ant farm. Each robot would have it's own address and not be allowed to speak until a certain code was transmited like you would do on a walkie talkie saying "over". So each robot would receive the transmision and look for it's address. If it his, process the data. If it's not, then look for "over" then speak.

[Admin]

I remember seeing an amazing video of three robots, each using slam, running around a maze individually. They constantly communicate the map to each other, and using statistical probability and crazy fast processors they eventually manage to link their maps up.

I think I saw it on the CMU robot videos.

But for a bot with a puny microcontroller . . . I'd say just go with the Pololu beacon . . .

[Webbot]

I'm not convinced that the Pololou beacon is the answer to my problem.

Coz there are two problems:

1. Problem 1 is that they need to find each other.... Robot B has to find Robot A and move very close to it. So if they both have a robot base of radius R, and they are touching each other, then we can assume they are both in the same square if the square size is less than 2*R (yes - I know that is very rough and in-accurate). Note the Pololu beacon may help to steer towards each other but since they have no sense of distance - just a compass direction: N/S/W/E - then they dont help to decide if the robots are in 'very close' proximity. Since it works over 15 feet then we just know they are within 15 feet of each other (it could be anywhere between 0 and 15 feet) and we dont know the exact angle (its approximated as N/S/W/E).  Hence my original comment about a very low power transceiver so that a contact is only made when they are in close proximity.

2. Once in 'very close proximity' we can assume that their current points are roughly the same and so shift their map origins to be the same. Equally we can apply rotation to make the axes the same. BUT we can only do this if one Robot (say Robot A) asks the other (Robot B) about its initial start point and starting orientation respective to the current location. So, in simple terms. they have to have 'a little chat' to share info to get in sync with each other. Again: the beacon doesn't help.


So the beacon helps them find each other but doesn't:
a) let them know when they are VERY close to each other
b) let them swap info so that they can get in sync


So we need something else as well. Either: a low power transceiver we can use to have that 'little chat' which can only happen when they are very close or a version of the beacon that also gives a value of 'distance'.

[Admin]

then they dont help to decide if the robots are in 'very close' proximity. Since it works over 15 feet then we just know they are within 15 feet of each other (it could be anywhere between 0 and 15 feet) and we dont know the exact angle (its approximated as N/S/W/E).

After using the Pololu beacon to get close and identify the other robot, aim a sharp IR in the direction of the beacon. By rotating the robot and reading both the beacon and sharp IR values, you can get a pretty good idea on the relative angles of each robot. I'm not quite sure what accuracy you want though.

Putting brightly colored LEDs on each robot (different color per side) and giving them video cameras would be the slightly more complicated/expensive way.

a low power transceiver we can use to have that 'little chat' which can only happen when they are very close or a version of the beacon that also gives a value of 'distance'.

My IR transceiver that I custom made had a range of about 10 feet when its aimed in the right direction. Cost me like $100 after adding up the PCB, parts, shipping, and mistakes I made. I recommend getting some cheap wireless transceivers instead.