Introduction

The robot localization problem is a fundamental and well studied problem in robotics research. Several algorithms are used to estimate pose on the known map and cope with errors, that arise due to inaccuracy of robot sensors and effectors. Their performance depends heavily on quality of robot's equipment: the more precise (and usually more expensive) sensors, the better results of localization procedure.

This work deals with localization algorithm based on particle filter with small miniature low-cost E-puck robot. Information from cheap VGA camera and eight infrared sensors are used to correct estimation of the robot's pose. To achieve better results, several landmarks are put into the environment. We assume, that robot knows the map of the environment in advance (distribution of obstacles and walls in the environment and position of the landmarks). We do not consider the more difficult simultaneous localization and mapping (SLAM) problem in this work (the case, when robot does not know it's own position in advance and does not have the map of the environment available).

E-puck is a widely used robot for scientific and educational purposes -it is open-source and low-cost. Despite its cheapness and limited sensor system, localization can be successfully implemented, as will be shown in this article. We are not aware of any published results of localization algorithms with E-puck robot. The survey of localization methods can be found in [1]. 2 Introducing E-puck robot 1) is a mobile robot with a diameter of 70 mm and a weight of 50 g. The robot is supported by two lateral wheels that can rotate in both directions and two rigid pivots in the front and in the back. The sensory system employs eight "active infrared light" sensors distributed around the body, six on one side and two on other side. In "passive mode", they measure the amount of infrared light in the environment, which is roughly proportional to the amount of visible light. In "active mode" these sensors emit a ray of infrared light and measure the amount of reflected light. The closer they are to a surface (the e-puck sensors can detect a white paper at a maximum distance of approximately 8 cm), the higher is the amount of infrared light measured. Unfortunately, because of their imprecision and characteristics (see Figure 2), they can be used as bumpers only. As can be seen, they provide high resolution only within few millimeters. They are very sensitive to the obstacle surface, as well. Besides infrared sensors, robot is equipped with low-cost VGA camera. The camera and image processing will be described in the following section.

E-puck ([2, 3], Figure

Two stepper motors support the movement of the robot. A stepper motor is an electromechanical device which converts electrical pulses into discrete mechanical movements. It can divide a full rotation into a 1000 steps, the maximum speed corresponds to about a rotation every second.

Dead reckoning

Dead reckoning ( [4], derived originally from deduced reckoning) is the process of estimating robot's current position based upon a previously determined position. For shorter trajectories, position can be estimated using shaft encoders and precise stepper motors.

E-puck is equipped with a differential drive (Figure 3) -a simplest method to control robot. For a differential drive robot the position of the robot can be estimated by looking at the difference in the encoder values ∆s R and ∆s L . By estimating the position of the robot, we mean the computation of tuple x, y, Θ as a function of previous position (x OLD , y OLD , Θ OLD ) and encoder values (∆s R and ∆s L ).

  x y θ   =   x OLD y OLD θ OLD   +   ∆x ∆y ∆θ   (1) ∆θ = ∆s R − ∆s L L (2) ∆s = ∆s R + ∆s L 2 (3)∆y = ∆s.sin(θ + ∆θ 2 )(5)

The major drawback of this procedure is error accumulation. At each step (each time you take an encoder measurement), the position update will involve some error. This error accumulates over time and therefore renders accurate tracking over large distances impossible (see Figure 4). Tiny differences in wheel diameter will result in important errors after a few meters, if they are not properly taken into account.

Image processing

The robot has a low-cost VGA camera with resolution of 480x640 pixels. Unfortunately, the Bluetooth connection supports only a transmission of 2028 colored pixel. For this reason a resolution of 52x39 pixels maximizes the Bluetooth connection and keeps a 4:3 ratio. This is the resolution we have used in our experiments (see Figure 4). Another drawback of the camera is that it is very sensitive to the light conditions.

Despite these limitations, camera can be used to detect objects or landmarks. However, the information about distance to the landmark extracted from the camera is not reliable (due to the noise), and we do not use it in following section.

Landmarks are objects of rectangular shape of size 5x5 cm and three different colors -red, green and blue. We implemented image processing subsystem, that detects relative position of the landmark from the robot. Following steps are included:

-Gaussian filter is used to reduce camera noise ( Output from the image processing is the relative position and color of the detected landmarks (for example -I see red landmark by angle 15 degrees).

Particle filter localization

As shown previously (Figure 4), pose estimation based on dead reckoning is possible for short distances only. For longer trajectories, more clever methods are needed. These methods are based either on Kalman filter [8] (or some of its variants) or particle filter (PF) [9].

The PF possesses three basic steps -state prediction, observation integration and resampling. It works with quantity p(x t ) -the probability, that robots is located at the position x t in time t. In the case of PF, the probability distribution is represented by the set of particles. Such a representation is approximate, but can represent much broader space of distributions that, for example, Gaussians, as it is nonparametric.

Each particle x

[m] t is a hypothesis, where the robot can be at time t. We have used M particles in our experiment. The input of the algorithm is the set of particles X t , most recent control command u t and the most recent sensor measurements z t .

State prediction based on odometry.

The first step is the computation of temporary particle set X from X t . It is created by applying odometry model p(

x t |u t , x t−1 ) to each parti- cle x [m] t from X t .

Correction step -Observation integration

The next step is the computation of importance factor w

[m] t . It is the probability of the measurement z t under particle x

[m] t , given by w

[m] t = p(z t |x [m] t ).

Two types of measurements were considered:

-Measurement coming from distance sensors Distance sensor (one averaged value for front, left, right and back direction) were used as bumpers only. In case of any contradiction between real state and hypothesis, importance factor was decreased correspondingly. -Measurement obtained from image processing Output from image processing was compared with expected position of the landmarks. In case of any contradiction (colors and relative angle of landmarks were checked), importance factor was decreased. The bigger mismatch, the smaller importance factor was assigned to the hypothesis.

Re-sampling

The last step incorporates so-called importance sampling. The algorithm draws with replacement M particles from temporary set X and creates new particle set X t+1 . The probability of drawing each particles is given by its importance weight. This principle is called survival of the fittest in AI ( [10]).

Experiments

Experiments were carried out in an arena of size 1x0.75 meters. Three landmarks (red, blue and green, one of each color) were placed into the arena, as shown on the figure 8. Robot was controlled by commands sent from computer, values from sensors were sent back to computer by using Bluetooth. Execution of each command took 64 milliseconds. The experiment started by putting robot into the arena and randomly distributing 2000 particles. After several steps, the PF algorithm relocated the particles into real location of the robot. The robot was able to localize itself. The convergence of the algorithm depends on the fact, if robot is moving near the wall or in the middle of the arena. The impact of infrared sensors was obvious. Algorithms were verified in the simulator( [11]) and in reality, as well. The video demonstration can be found at ( [12]).

The localization algorithm was able to cope with even bigger areas, up to the size of three meters. However, we had to add more landmarks to simplify the localization process. Localization algorithm showed satisfiable performance, relocating hypothesis near real robot pose.

Localization and pose estimation is an opening gate towards more sophisticated robotics experiments. As we have shown, the localization process can be carried out even with low-cost robot. Experiments were executed both in simulation and real environment.

A lot of work remains to be done. The experiments in this work considered static environment only. Addition of another robot will make the problem much more difficult.

As we have mentioned already, there are certain areas in the environment, where convergence of the localization algorithm is very fast -in corners or near walls. Sensor fusion is the process of combining sensory data from disparate sources such that the resulting information is in some sense better than would be possible when these sources were used individually. We are dealing with sensor fusion of infrared sensors and input from camera.

As a future work, we would like to implement path planning, that takes into account performance of the localization algorithm. Suggested path (generated by path planning algorithm) should be safe (the chance to get lost should be small) and short. Multi-criterial path planning will be based on dynamic programming ( [13]). The idea is to learn areas with high loss probability from experience.