Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved

Indoors Mapping Using MARS

Indoors Mapping Using MARS

Improvement of Mapping by Odometry using MARS

Carried out by Ken Fox and Tomer Altman.
Guided by Noam Gordon and Ronen Keidar.
Supervised by Prof. Alfred M. Bruckstein.

The main objective of this project is to improve the accuracy of the odometry by averaging the estimated locations available from two robots when these two are close to each other.
A simulation system was built in order to test and estimate the performances of different suggested algorithms and a Lego based robotic system was built in order to execute and prove the practicality of the MARS solution.


Odometry means calculating the distance a certain object has tarveled by calculating the umber of revolutions its left and right wheels had turend. In theory, these calculation can be perfect, given the speed of the wheels at all times. However, in practice, noise is introduced, and not limited to the following:

Sensor inaccuracies. Even if the movement is perfrect, the sensor might give a reading which is slightly different or even quantised, introducing mixed noise.
Free revolutions of the wheels, when a wheel revolves without its exact movement applied to the surface. For example when the surface is when an agent collides with an obstacle without stopping.
Friction can cause a wheel to not revolve but rather drag along while the other is pulling the agent forward, for example when the agent is performing a rotation without the use of a differential.

World Model

The model chosen here is base
d on a version of random walk, since it has been proven to be one of the best methods of covering an unknown area. The robots use two wheels with independant speeds. Movements where the speed of both wheels is the same (possibly reversed) are the most stable, since there's no use of a differential. Specifically, the model in this project is split between movement in straight lines and rotation around the center of the robot. These are done by setting the wheels to the same speed for straight line and reversed for rotation. The robots choose a random speed for each of these stages, therefore a random walk is resulted. The robots' theoretical positions and headings can be calculated.

Robots' View of the World

The robots aquire their view on the world from the odometers on each of the two wheels. The robots calculate their approximate position and heading using the same formula as used above. To simulate the errors occuring in real life situations, the error was added as random noise to the odometers' readings, relative their speed. This is because it is more likely to have errors at high speed movement.


Error Reduction Algorithm

It is wanted that by communication between the robots, a better of view of the world can be achieved for each robot. For this algorithm, we assume a large number of robots and collisions and that the error is randomly distributed, without bias. For this kind of noise a good solution is averaging of the world view between the robots. Naturally, when the number of agents and the working is relatively small, such error reduction method cannot be expected to produce good results. More specifically, when two robots collide, they exchange their views of the world, and the angle at which they have collided. Each robot then uses this information to calculate their position and heading, from the other robot's point of view. The robots then average these values with their view.



In this project, we have shown in theory that using a smart algorithm can help reduce errors, when the number of participating agents is large enough. It was learnt that in practice, certain assumptions are still required for the algorithm to show its improvements to the original problem.
following this project several routes of progress can be made, improvements to this project and other projects which can emerge from the ideas discussed:

The averaging algorithm can be improved to consider values which are very different than the current less than values close to the current values. This can reduce the problem where one very wrong robot might spoil the values for all others.
A "trust" meter can be established where the robots trust their values less as time passes and trust them more after averaging with another robot, especially if the other robot's values are close to ours. This trust is used to weigh the averaging.
A different secondary problem can be introduced. A system where the robots want to perform a synchronized task, while measuring their movements using odometry. For example giving each robot a destination to reach, averaging their views of the worlds as they move, until they reach the destination. To inscrease the accuracy, several random-walking robots can be used to update robots standing in wrong locations.


Project Report: Indoors Mapping Using MARS Project Report