Projects

Localization is the task of estimating the robot location and has been identified as one of the key problems in robotics. The localization problem can be roughly divided into two variants: In the first variant the robots can estimate their location by sensing their surroundings and comparing it with information they possess about the environment, while in the second variant, the robots have no such capabilities. Instead, every robot knows its initial location and updates its location estimation.

In this project we are focusing on the second variant. In the second variant of the localization problem it is assumed that, initially, every robot knows its location and uses audometry in order to track it (dead-reckoning). However, due to noisy sensor readings, in time, the estimation diverges from the robot real location. When a group of robots perform localization, the localization error can be reduced by sharing information between them.

The goal is not to derive hard lower or upper bounds, but rather to characterize the robots expected behavior and in particular, to predict the expected localization error.

The solution is based on the paper “Multi-A(ge)nt Graph Patrolling and Partitioning” by Yotam Elor and Alfred M. Bruckstein. The agents perform dynamic partitioning of the graph into sub-graphs, while each agent patrols its own sub-graph. Balanced graph partition is achieved over time due to “gas filled balloon” behavior – each agent applies pressure on the border vertices of its sub-graph. The agent that is applying the higher pressure (the agent that is controlling a smaller area) can conquer the vertex on the other side, and will do so with a certain probability.

In this project we have implemented the Balloon DFS algorithm in Java programming language, which allowed us to run, check and research the algorithm.

The robot can charge the color by lighting it with UV Leds. After being charged, the Phosphorescent color emits green light which can be sensed by the robot’s camera. Using these markings, the robot is able to perform the coverage algorithm of Gabrieli and Rimon[1] and cover the floor optimally.

HARDWARE

The algorithm is implemented on Lego Mindstorm. Therefore, our inputs from the enviroment and movement capabilities are limited to the following:

Light Sensor – providing us with an integer number, indicating amount of light sensed.
Odometer – a unit that measures rotation cycles.
Engines.
Mini light-bulb system.
As described in the document (link below) we build our robots using the above items, and a “brain” system (the Mindstorm RCX unit) programmed in C. The robot vision system is based on a rotating light sensor, and mini light bulb system, trackable by other robots.

THE ALGORITHM

Limited to the above inputs, we are able to map the space around the robot into slices, and measure light in each slice. However, we are not able to get a good estimation of the distance between two robots. Therefore, our algorithm can not be strongly based on distances between robots.

We summarize the algorithm here according to our understanding of the birds consideration, with the limitations mentioned above. The robot scans his inviroment and finds the closest robot to follow. However, in order to create and maintain the V formation, the robot examines the location of this robot.

• The first area, very close to the robot, and in a small angle in front of it (Image 2) is the dangerous zone, and simply moving forward might result in collision. The robot tries to avoid having another robot there, by turning away from it and slowing down.
• The second area, not in immediate course to collision is the view blocked zone, and having a robot there should be avoided. This is done by speeding up a bit.
• The third area, at approximately 45 degrees from the robot’s front is the good zone, and having a robot there helps improve aerodynamic efficiency and does not block the view. Maintaining this possition is wanted.
• The fourth area, mostly at the sides and hardly in front of the robot is the unhelpful zone. Having a robot there does not helps improve aerodynamic efficiency and therefore the robot should slow down to let his friend enter his good zone.

LEGO IMPLEMENTATION

Image 3 – Robot FlockThe algorithm is finally implemented using the Lego Mindstorm set. It required some tuning but eventually we came out with fine results.

THE PROBLEM

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.

THE SOLUTION
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.

CONCLUSIONS

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.