MAPS - Problem Statement/Previous Attempts

Problem Statement

We need to determine the position of a robot. The robot is initially at some position (x0, y0) at time t0. The robot moves for awhile and at time t1, we want to know where it is.

Previous Attempts

There are three classical ways to solve this problem. Mapping involves a robot detecting its local environment and reacting accordingly. There are several ways to do mapping.

Sonar mapping involves emitting a sonar signal from the robot and using it to determine the shape of the room and the objects it contains. By examining the robots position relative to these objects the robots position can be determined. Sonar mapping requires a complex algorithm to interpret the sonar responses compared to other forms of positioning, and is subject to a lot of noise.

There are two common ways to do what is called RF mapping:

Amplitude-based RF mapping involves setting up several base stations (one implementation runs of the signals emitted by wireless LAN hubs) and using the amplitude of the signal received to determine the distance from the base station. Each point in space has a locally unique set of amplitudes from the base stations, and these sets can be used to determine the robot's position (the set have at least three members to triangulate). One problem with amplitude-based RF mapping is that it requires extensive training of the RF system to map the area accurately before the robot can be deployed. It is also very prone to error due to amplitude noise (if someone walks in front of the antenna, for example). This system is convenient in that it can operate off of existing signals. It also separates the receivers from the transmitters and makes the robot only responsible for receiving, a much less power intensive operation.

A similar technique is tag-based RF mapping, which involves setting up "tags" around a room. The robot sends out a pulse, and the tags respond with their ID numbers. By knowing which tags respond and the relative amplitude of each of these tags' responses, some position information can be extracted. This system has a few problems. One is that the tags respond at psuedo-random times and in random order, and it is very possible for two responses to overlap. Also, the robot has to transmit and receive signals, and so the design is fairly complex. Finally, the tags' transmissions are quite weak since they are battery operated and optimized for size. One big advantage of this system is that an arbitrary number of tags can be used.

The most obvious yet most implementationally challenging method of positioning is computer vision. Needless to say, this technology is still in its infancy due to the extremely complex AI needed.

Dead Reckoning is a third method for determining position. Dead Reckoning is the measurement of the position of a robot based on how far it has moved. This is the most basic way to determine the position of a robot.

The most common implementation of dead reckoning involves measuring the rotation of a robot's wheel. One could do this by counting spokes as they pass by a sensor, etc. This method is prone to cumulative error due to slip in the robot's wheels.

Another method involves cross-correlation of pictures of the floor beneath the robot. Multiple photos are taken of the floor in rapid succession. The photos are cross-correlated to see the distance between them. Indoors there is usually a pattern to the carpeting or tiling of the floor which can cause false cross-correlation results. Outdoors the ground is usually too uneven to be usable.