# How can my robot find its position in any given map without GPS, including when the initial point is not given?

Consider this map

The Contest arena shown in figure 1 consists of two sub arenas, both the sides are identical to each other and their scientists and safe zone locations are similar.

Each sub arena has 3 different colored rooms and a fourth shared room. Each robot will be placed at identical start locations, respective to their arena. These locations will be random and anywhere on the map.

Each room (other than the shared room) will have two entry and exit gates. Both of these gates will be open at all times. The robot can enter and exit from any gate it chooses.

• Can you give us more details on the competition - is it goal based, as in do you have to tell the robot to go to a certain space and they time how long it takes to get there? Or is performance based on how quickly it can figure out where it is? May 7 '16 at 12:30

Determining your location when you have a map but not your starting location is a job for a particle filter.

Here's an animation of a particle filter in use. The black boxes are walls, the green turtle is the robot, the red marks are possible locations, and the grey circle is the center point of all the estimates. As the robot moves, the possible locations become more tightly grouped until there is no more ambiguity.

The idea is that by moving around the space and measuring the distance to walls around you (or by bumping into them), you can get a better sense of where you "might be".

For example: in the map you showed, imagine that your robot moves forward by 4 spaces but does not hit a wall. There are only a few spots on the map where this is possible, so now you know you must be in one of those places. The actual movement doesn't matter, but as you build up your knowledge of where the walls are (and where you don't find walls), some moves will be more useful in determining your location than others. And eventually, you'll have roughly 100% confidence in your location.

I would say that you have 2 main possibilities:

• You base your computation on the IMU (Inertial Measurement Unit) of your robot. Usually from those you can basically have an acceleration, then you need to integrate it 2 times to get the position and therefore the displacement in meters.

• You base your computation on simple encoders. Encoders are sensors which convert the angular position or motion of a shaft to an analog or digital code. From this, if you know the radius of the wheel (which you should assume constant, if the wheel does not change over time) you will know the displacement in meters associated to the displacement read by the encoder.

I hope this helped you.

• While these methods do allow the estimation of the pose relative to the starting position, they cannot find the absolute position on the map and I think that's what the question is about. Apr 29 '16 at 9:50
• Yeah. I understood he had the coordinates of the starting point in the 'world-frame' Apr 29 '16 at 10:15
• Second option involves the use of dead-reckoning, which is susceptible to accumulative error over distance travelled. Could be dodgy if the robot hits something and the wheels slip. May 7 '16 at 12:21