Histogram Filter for Robot Localization

Nataliya Boyko Yaroslav Hladun

department of artificial intelligence department of artificial intelligence
Lviv Polytechnic National University Lviv Polytechnic National University
Lviv, Ukraine Lviv, Ukraine
Nataliya.i.boyko@lpnu.ua yaroslav.hladun.knm.2018@lpnu.ua
https://orcid.org/0000-0002-6962-9363 https://orcid.org/ 0000-0001-9124-9124

Abstract— The paper describes localization methods. 1. Study of algorithms for localization of mobile robots.
The histogram filter algorithm is also described. The
results of the study of the histogram filter algorithm for 2. Implementation of a mobile robot localization
one-dimensional and two-dimensional space are presented. algorithm based on a histogram filter using the Python
The experimental application of the histogram filter programming language.
algorithm on a mobile robotic platform is analyzed. The 3. Study of the influence of the parameters of the
paper presents particle filter, histogram filter and Kalman implemented histogram filter on the quality of
filter. The results of experiments are given and the results localization.
are compared.
4. Research and analysis of the histogram filter for the
Keywords—machine learning; artificial intelligence; robotics; case of one-dimensional and two-dimensional space.
particle filter; histogram filter; Kalman filter
II. LITERATURE REVIEW
I. INTRODUCTION
The theoretical basis for writing this work were the works
Every year robotics develops more and more. New of foreign authors on the problems of automation and
approaches to solving problems of movement, localization, localization in robotics.
automation of robots are created. Many models achieve
considerable success in solving various problems. Many Robots are created so that they can replace humans in
technical complexes are created for military purposes: target difficult working conditions. For example, Google is
detection, its elimination. Firefighters are working; rescuers developing unmanned vehicle technology. This project is led
work, able to get people out of the water, from the rubble of by engineer Sebastian Fran (S. Thrun), a professor at Stanford
collapsed buildings. One of the many trends in robotics is the University. This car has traveled considerable distances with
transition from telecontrolled systems, which require constant minimal human involvement in its management [2]. Earlier, in
human participation to perform all the actions of the robot to 2005, Sebastian Fran's Stanley project team won the DARPA
autonomous systems, in which the operator only specifies the GrandChallenge [3].
ultimate and intermediate goals. This is convenient for alien
research, where a large signal delay does not allow for remote III. MATERIALS AND METHODS
control [1]. Localization and navigation are the two most important
The purpose of the research is to implement the tasks that mobile work performs. They need to know their
localization algorithm - histogram filter, its comparison with current position and how to get to the end point. These two
other filters, a detailed description of its advantages and tasks are closely related. If the robot, having outlined a
disadvantages. trajectory, does not know its exact initial position, it will face
certain difficulties when moving to the destination [6, 7, 17].
To date, the problem of robot autonomy [4, 5] is very This section discusses several navigation methods: with and
relevant. Autonomy requires the robot to perceive the without terrain maps. Navigation without a map (for example,
environment. Knowing the map of the area, the robot can the DistBug algorithm) is often used in a constantly changing
easily determine the location of objects in space. One of the environment or when the calculated path is subject to a single
difficulties arises when the robot has no idea of the terrain and pass and therefore does not necessarily have to be optimal. If
does not know its coordinates. In this case, he needs to make you have a map, you can use the Dijkstra algorithm or the A*
movements and at the same time create a map of the area, algorithm, which allows you to determine the shortest path
using various sensor devices and algorithms. The purpose of before the start of the robot. Navigation without a map is
this work is to implement a localization algorithm based on a carried out during the movement of the robot in direct
histogram filter to determine the location of a mobile interaction with its sensors. Map-based navigation algorithms
automated robot. are based on a nodal graph of distances, which must either be
To achieve this goal, the following tasks are solved:
provided in advance or built on the basis of environmental The graph is a uniform distribution. The line on the graph
analysis (for example, using a quadrant tree) [8]. defines the probability function, this state represents the
maximum uncertainty. Now suppose there are three landmarks
All the movements of the robot and the sensory - three doors that are similar to each other, and the robot can
measurements that it performs are to some extent prone to determine the presence or absence of a door in its current
noise. The purpose of probabilistic localization is the best position. If the robot feels that it is near the door, then the
possible assessment of the current position (configuration) of probability distribution will take a different form (Fig. 2 a).
the robot, based on previously obtained data and their
distribution functions. The final estimate will be nothing more
than the probability distribution, because the system is
characterized by internal uncertainty [9]. There is one big
problem with the method of probabilistic localization: since
the configuration space must be discrete, the position of the
robot can be specified only in discrete numbers. There is, a)
however, an easy way to overcome this limitation - to develop
a discrete representation based on the accuracy of sensor
readings and command execution. If, for example, their
accuracy does not exceed 1 cm, then you can express all the
distances through increments of 1 cm. Unfortunately, this
method significantly increases the number of measurements
and the number of discrete distances (each with its own b)
probability) [8, 17].
In contrast to probabilistic localization, the particle filter
allows the use of non-discrete configuration spaces. This
method is based on the following idea: the work is represented
as a set M of N particles. Each particle consists of a c)
configuration X robot and weight w  0,1 . Fig. 2. a) uniform probability distribution; b) probability distribution
provided that the robot sees the door; c) the listed probability
After executing the move command, the robot updates the distribution.
configurations of the xj particle. To do this, it makes the set М
by sampling from the values of the probability density Based on Fig. 2. it is seen that where the door is, the
probability of the location of the robot has become higher than
function p ( x d , x ) (it usually has the form of a Gaussian in a place where there is no door. Because the robot felt it was
j j
at the door, it made these places more likely and other places
distribution). After that, the robot assigns a new weight
less likely. The graph of this function is the probability
W = p( s x ) to the j-th particle and carries out the distribution after the event was executed. This probability is
j j called a posteriori. A priori is called the probability, which
normalization of weights so that their sum is equal to one. expresses the assumption of accounting for experimental data.
Finally, the robot re-samples to form a set of particles with the But it is possible that the sensors were wrong, and the robot
largest weight [9, 16]. inadvertently saw the door, where in fact it is not. One way or
another, the vertices of the graph function in Fig. 2 b show us
Consider a robot that is lost in space. The algorithm for the most possible location. The robot measurement is based on
localizing the histogram filter allows you to determine the
Bayes' theorem.
location of the robot quite accurately, for example, in
comparison with a GPS device whose error can reach ten Bayes' theorem allows us to determine any event under the
meters. For a histogram filter, the error will be about 2-10 cm. condition that a statistically interdependent event occurred.
Imagine that the robot is placed in one-dimensional space and The probability can be specified when new data is obtained.
has no idea where it is. An example of such a space is a long
narrow corridor, where it is possible to move only forward or
backward; lateral movement is impossible. Since the robot P ( B A) P ( A)
does not know its position in space, he believes that every P( A B) =  ()
point in this one-dimensional world with equal probability can P( B)
be its location. In fig. 1 on the graph on the y-axis presents the
probability of the location of the robot, the abscissa represents where P ( A) – a priori probability of the hypothesis;
all possible locations of the robot in this world.
P ( A B ) – the probability of the hypothesis under the
condition of the event;
P ( B A) – the probability of the event if the hypothesis is
Fig. 1. Uniform distribution of the probability of the location of the robot in true;
one-dimensional space
 P (B ) – probability of the event. measurements a robot makes, the better it locates itself. This is
the definition of Monte Carlo localization, which is also called
If the robot moves to the right for a certain distance, the a histogram filter.
probability of location shifts with it according to the
movement. This can be seen in Figure 3d. All vertices are also
shifted to the right.

a)

a)

b)

b)
c)

c)

d)

d)
Fig. 3. a) uniform probability distribution; b) probability distribution
provided that the robot sees the door; c) the listed probability
distribution after one measurement; d) the distribution of probability e)
after moving to the right for some distance.

However, due to the uncertainty in the movement of the

work, the probabilities of its position at the door decreased, f)
the peaks of the function became lower. This is due to the fact Fig. 4. a) uniform probability distribution; b) probability distribution
that the robot does not know exactly how far it has advanced, provided that the robot sees the door; c) the listed probability
the probability of the robot's location has become less distribution after one measurement; d) the distribution of probability
accurate. The process of moving these vertices to the right is after moving to the right for some distance; e) probability distribution,
technically called convolution. Now suppose that after provided that the robot sees the door; e) the final probability distribution
after two measurements and one movement.
moving, the robot again feels near the door, as before. We
multiply our probabilities, which were obtained before the When moving the robot, the distribution function is
second dimension (Fig. 3c) with the function in Fig. 3d. smoothed. Mathematically, such smoothing can be described
Unlike the first dimension, when the robot was in a state of by a convolution operation. Convolution is a mathematical
maximum uncertainty, the second dimension has some idea of operation that measures the overlap of two functions. If the
the location before the measurement by the robot. This two functions are not superimposed on each other, then their
preliminary information, together with the second convolution will be equal to zero. If they completely coincide,
measurement (when the robot sees the door again), are then their convolution will be equal to one. For the purposes
combined, and a new probability distribution is obtained, as of this paper, the first function is a measurement function, and
shown in Fig. 4e. There are a few minor performances on this the second is a function that describes motion. The result is a
chart and only one big maximum. He answers the second shifted probability distribution, shown in Fig. 3d. Formula (2)
door. This happened because, first, the robot saw the first is a convolution formula for the case of robot motion.
door. This indicates that he was at a door, but did not know
which one was close. Then the robot made a movement and
P ( x ) =  P ( x t − 1 )P ( x x ) 
saw another door. In two dimensions, the robot saw two doors. t
()
Therefore, the probability function should have a main peak i i i j
j
near where one might expect two doors in a row.
After two measurements, the robot is more confident in its
location than after one measurement. This means that the more
 TABLE III. COMPARISON OF DIFFERENT FILTRATION
t
where P ( x ) – the probability that at time t the robot is in METHODS IN THREE-DIMENSIONAL SPACE BY TIME AND RMS
i ERROR
position xi; n=10 n=100 n=1000 n=10000
t −1
P( x ) – the probability that at the time t-1 the robot is

15323ms
0.025 m

0.024 m

0.075 m
5345ms
i

43ms
KF -
in position xj;

P ( x x ) – the probability of being in cell xi provided

12564ms
0.077 m

0.075 m

0.054 m
4236ms
73ms
i j PF -
that the robot is in position xj the probability of the event if the
hypothesis is true.

0.024 m
889ms
This section describes the principle of operation of the HF - - -
histogram filter algorithm, which consists of two stages:
measurement and motion. The measurement step uses Bayes' The first and main conclusion that can be drawn from a
theorem. The motion stage uses a convolution operation. comparison of these basic localization algorithms is that the
These stages allow the work to change the probability histogram filter scales very strongly to dimension n. This
distribution, which describes its location on the map. means that it will not work properly in multidimensional
spaces, due to lack of memory and complexity of the
IV. EXPERIMENTS convolution operation.
First of all, before delving into the details of the The second conclusion can be made regarding accuracy.
complexity of the histogram filter algorithm, it is worth The histogram filter, despite being resource-intensive, is very
comparing it with the other two most popular and frequently accurate. Of all three filters, it has the best accuracy in three
used filters, such as the Kalman filter and the Particle Filter dimensional cases. This can be explained by the fact that at
(or Monte Carlo localization algorithm). It is worth comparing each step we keep the state of the weights of the whole map,
these three algorithms in different cases of dimensionality: which clearly helps us to more accurately assess the position
one-dimensional, two-dimensional and three-dimensional at each subsequent iteration.
cases.
After comparing the basic localization algorithms, the next
appropriate step will be to show the operation of the filter on a
TABLE I. COMPARISON OF DIFFERENT FILTRATION METHODS IN simple map. The layout of the football field was chosen as a
ONE-DIMENSIONAL SPACE BY TIME AND RMS ERROR
map (Fig. 5).
n=10 n=100 n=1000 n=10000
9m
0.0

0.0

0.0

0.0
ms

ms

ms
16

75

55

53

20

59

34

88

KF
m

m
7
s
0.037 m

0.064 m

0.045 m

0.069 m
171 ms

481ms
20 ms

59ms

PF
0.023 m

0.021 m

0.018 m

0.014 m
226 ms
122ms

774ms
17 ms

HF
Fig. 5. Discrete marking of the football field as a map

The red dot on the field shows the position of the sensor.
TABLE II. COMPARISON OF DIFFERENT FILTRATION This sensor sees only 9 cells below it (the parameter can be
METHODS IN TWO-DIMENSIONAL SPACE BY TIME AND RMS
ERROR adjusted). Using the keys w, s, a, d, the sensor can be moved
up, down, left, right. Thus, to perform the operation of moving
n=10 n=100 n=1000 n=10000 the histogram filter, so fix the position of the robot as in the
image and start moving it randomly. Let's look at the
0.035 m

0.075 m

0.024 m

0.053 m
634ms

assessment of the position of the robot after each movement

23ms

85ms

63ms

KF
(Fig. 6-9).
0.099 m

0.035 m

0.064 m

0.031 m
1247ms
64ms

67ms

23ms

PF
0.023 m

0.015 m
1002ms
35ms

HF - -

Fig. 6. Evaluation of the position of the sensor (yellow - more likely).

 As you can see, at one point the position of the sensor
converged at one point with a small vertical variance. This
was largely due to the fact that the sensor measured values that
had not been measured before and this helped to focus the
scales in one place. It will also be interesting to see the
behavior of the scales after the sensor starts measuring the
same type again. That is, when he will again see only green
cells for several iterations (Fig. 12).

Fig. 7. Estimation of the position of the sensor after one movement to the
right.

Fig. 12. Estimation of the position of the sensor after several movements to
the left

The histogram filter works in such a way that it increases

Fig. 8. Estimation of the position of the sensor after several movements to
the right.
the horizontal variance when moving to the left. As mentioned
in the previous sections, this is a special operation that is
performed due to inaccurate movement: that is, we can never
move an object exactly 5 centimeters, we will move it either a
little more or a little less.
It remains to explore the last question: how the complexity
of the algorithm depends on the size of the block that sees the
sensor (Fig. 13). In all previous experiments, this value was
constant: 3 to 3. Now we will change it and look at the time of
the algorithm.
Fig. 9. Evaluate the position of the sensor after a few more movements to the
right.

In Figure 9, the actual position of the sensor was already

near the central white circle. That is, before that the sensor
saw only a green cell and saw white for the first time. This
allowed us to assess his position very accurately. As you can
see, the largest scales are concentrated near the actual position
of the sensor. Let's continue to perform the movement
operation and look at the function of scales (Fig. 10-11).

Fig. 13. Dependence between time and kernel length

As can be seen from Figure 13, we have a linear

relationship between the length of the kernel and the time
Fig. 10. Evaluation of the sensor position after several movements up spent on the algorithm. It is also worth noting what can be
associated with the length of the kernel. It can be generalized
to the concept of the number of sensors. Obviously, the longer
the kernel, the more cells we see. Each cell can be considered
a separate sensor. Thus, we investigated that there is a linear
relationship between the number of sensors and time.

V. RESULTS
The first thing that can be learned from the comparison of
Fig. 11. Estimation of the position of the sensor after a few more movements the main localization algorithms is that the histogram filter is
up
very scalable to the dimension n. This means that it will not dimensional or two-dimensional space). This is due to the fact
work properly in multidimensional spaces, due to lack of that we hold the weight tensor at each iteration.
memory and complexity of the convolution operation. The
second conclusion can be made regarding accuracy. The Summarizing the advantages of the histogram filter, we
histogram filter, despite being resource-intensive, is very can say that this is a fairly accurate algorithm. Its range of use
accurate. Of all three filters, it has the best accuracy in three is not as wide as that of the particle filter, or the Kalman filter,
dimensional cases. This can be explained by the fact that at but in not very resource-intensive projects where the emphasis
each step we keep the state of the weights of the whole map, is on accuracy, the histogram filter is ideal.
which clearly helps us to more accurately assess the position
at each subsequent iteration. References
It is also worth discussing the specifics of the filter
histograms. While we were performing the movement [1] А. А. Мinin, Navigation and management of the mobile robot equipped
operation and the same data was constantly entering the with the laser rangefinder: the dissertation of the candidate of technical
sensors, the robot did not localize itself quite well. As soon as sciences 05.02.05, 2008, p.182.
we came across the new data, the Scales function immediately [2] S. Thrun, Google’s driverless car, 2011. [Electronic resource] – Access
mode:
"jumped" in some of the most plausible places. http://www.ted.com/talks/sebastian_thrun_google_s_driverless_car.
Next, if the scales are concentrated in one place, the [3] Stanford Racing team page, 2005. [Electronic resource] – Access mode:
movement will expand the range of possible positions of the http://cs.stanford.edu/group/roadrunner/stanley.html.
sensor. In other words, the variance will increase. The [4] А.А. Bolshakov, D.L. Lysychkyy, Mobile robot motion control //
Bulletin of AGTU. Ser.: Management, Computer Science and
parameter of how much the variance increases can be adjusted Informatics, № 1, 2011, pp. 12-18.
depending on how inaccurate the odometry data are. [5] Mobile robotics (Robot). Module 1. [Electronic resource] – Access
The linear dependence of time on the number of sensors mode: https://learn.open2study.com/mod/youtube/view.php?id=79916
(date 06.07.2015).
was also investigated. Thus, this shows that the filter
[6] J. Borenstein, H.R. Everett, L. Feng Borenstein, Sensors and methods
histogram algorithm is quite good at sense operations with a for mobile robot positioning // Prepared by the University of Michigan,
large number of sensors. This allows it to be used in complex 1996, p. 282.
systems. [7] R. Siegward, R. Nourbakhsh, Introduction to Autonomous Mobile
Robots // Cambridge MA: MIT Press, 2004, p. 321.
It should be noted that the histogram filter showed the best
[8] T. Broynl, Embedded robotic systems: design and application of mobile
accuracy compared to the particle filter and the Kalman filter. robots with embedded control systems, 2012, p. 520.
[9] H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki,
VI. CONCLUSIONS S. Thrun, Principles of Robot Motion: Theoty, Algorithms, and
Implementations, Cambridge MA – MIT Press, 2005, p. 603.
Investigating this problem, the purpose was to explore
[10] M. Arbib, A. Hanson, Depth and Detours: An Essay on Visually Guided
several key issues, in addition to the direct implementation of Behavior, Vision, Brain and Cooperative Computation, Cambridge MA.
the algorithm. First, we wanted to investigate why the – MIT Press, 1987.
histogram filter is used much less frequently than the Kalman [11] Y. Koren, J. Borenstein, Potential Field Methods and Their Inherent
filter and the particle filter. The answer to this question was Limitations for Mobile Robot Navigation, in: Proceedings of the IEEE
given by statistical evaluation of the complexity of the Conference on Robotics and Automation, Sacramento CA, 1991, pp.
algorithm. It practically does not work with strongly 1398-1404.
discretized and multidimensional spaces. And as in practice [12] J. Borenstein, H. Everett, L. Feng Navigating Mobile Robots: Senfors
and Techniques, Wellesley MA – AK Peters, 1998, p. 225.
the filter should be applied at least in three-dimensional space
[13] E. Puttkamer, E. Von, Autonome Mobile Roboter, Lecture notes, Univ.
(where two coordinates and rotation are taken into account), it Kaiserslautern, Fachbereich Informatik,2000.
at once cuts off a possibility of use of the histogram filter.
[14] V. Lumelsky, A. Stepanov, Dynamic Path Planning for a Mobile
The influence of the number of sensors on the time of Automation with Limited Information on the Environment in: IEEE
Transactions on Automatic Control, Vol. 31, 1986, pp. 1058- 1063.
iteration of the histogram filter is investigated in the work. The
[15] I. Kamon, E. Rivlin, Sensory-Based Motion Planning with Global Proofs
study showed that the dependence is linear. That is, the in: IEEE Transactions on Robotics and Automation, Vol. 13, 1997, pp.
number of sensors in the algorithm linearly affects the time. 814-822.
The implemented algorithm, namely its visualization [16] N. Boiko The issue of access sharing to data when building enterprise
information model in: IX International Scientific and Technical
shows how this filter works and how it specifies the position conference, Computer science and information technologies (CSIT
of the sensor. If the sensor sees only data of one type, it 2014), Lviv, Ukraine, 2014, pp. 23-24.
assumes that the robot is in all places where data of this type at [17] N.Boyko, V. Korkishko, B. Dohnyak, O. Vovk, Use of Neural Networks
the same time. But with the movement operation, the position in Q-Learning Algorithm, in: 32nd International Symposium on
of the object is constantly concretized and the object localizes Computer and Information Sciences, ISCIS 2018: Computer and
itself more precisely. Information Sciences, Poznan, Poland, September 20-21, 2018, pp 188-
195.
Another important advantage of filter histograms is the
ability to easily visualize the process (of course in one-