Localisation through supervised learning
Lagriffoul Fabien
January 11, 2005
20 credits
Umeå University
Department of Computing Science
SE-901 87 UMEÅ
SWEDEN
Abstract
This thesis describes an odometry method based on supervised learning. Sensory data is collected from the robot’s shaft encoders and position data from a ceiling camera. This data is then used for training a Feed Forward Neural Network. An appropriate representation of this data, that leads to better learning, is discussed. The system is then extended with additional sensory input, independent of the wheels. Experimentation shows that, properly trained with such additional sensory information, the system performs better than classical odometry, especially in situations where the wheels are slipping.
Contents
I. Introduction 5
1. Odometry and robotics 5
2. Approach taken in the present thesis 5
3. Thesis outline 6
II. Odometry basics 7
1. Odometry sensing 7
2. Systematic error 8
3. Non systematic error 9
4. Improving odometry with additional sensory input 9
5. What is different in the presented approach ? 10
III. Experimental set up 12
1. The robot 12
2. Software 12
3. The arena 13
4. The supervisor 14
5. What data is needed ? 15
IV. Extracting position data from the video camera 16
1. The Khepera’s hat 16
2. Video processing 17
3. Space warping 19
4. Accuracy 20
V. Neural networks basics 23
1. Which kind of neural net ? 23
2. Description of a Multi Layer Neural Network 24
3. Mean-squared error, training, epoch 25
4. Overfitting / Generalisation 25
5. Consistency of data 27
VI. Preliminary experiments with neural nets 28
1. Classical odometry with Khepera 28
2. Experiment 1 29
3. Further tests 32
4. Importance of uniform distribution in the training set 32
5. Experiment 2 : a new representation of data 35
6. Results 38
7. Post analysis of the mappings 39
8. Conclusion 41
VII. Experiments with the physical robot 43
1. The synchronisation problem 43
2. A new representation of data (2) 45
3. Results 46
4. conclusions 50
VIII. An additional input 51
1. K213 vision turret 51
2. Can a range-finder make odometry ? 52
3. method 54
4. Results 56
5. Experiment with slippage 61
IX. Conclusion and future work 65
X. Appendix 66
1. Forward kinematics 66
2. Experiment with different training sets 68
XI. References 70
I. Introduction
1. Odometry and robotics
Odometry is the general ability for any system to know its own position. It is therefore an issue of primary importance in autonomous mobile robotics. Although it’s not always necessary to know the robot’s position to reach a certain goal, it’s useful in many applications such as path following and map building.
The basic idea of odometry is to retrieve information from different sensors and process it to estimate the position of the robot. The classical example is to determine how much the wheels have turned thanks to shaft encoders, and then to combine these values with geometrical features of the vehicle (distance between wheels, diameter) to determine the movement. This basic approach provides good results in indoor environments, but becomes inaccurate in real world applications, because of irregularities of the ground and slippage of the wheels. The common approach to overcome these limitations consists in building a model of the error, and correcting the odometry using maximum likelihood (see e.g. [Chong Kleeman]).
2. Approach taken in the present thesis
In this thesis, the features of the vehicle are not assumed to be known. Instead, the approach is to find the relationship between the sensor values and the movement of the robot. This relationship can be found without any prior knowledge about the geometry of the vehicle, by supervised learning techniques. This learning will be achieved by training a neural network with data collected in real navigation situations.
This method has two major advantages. The first one is simplicity. Indeed, no complicated model of the robot is needed, whether it has two wheels or six legs, the principle remains the same. The second advantage is robustness : information from many different sensors can be combined in the neural net, so that if one of them is ineffective or noisy, the system still gives good results. The drawback of the method is that the performance of the neural network depends highly on how it is trained. There is no well defined method for this; it is more a matter of empirical rules and experimentation.
3. Thesis outline
Chapter II describes the current odometry techniques from the sensor level to the algorithmic level. It addresses also the limitations of odometry and the current methods used to overcome them. Then it shows in what the approach taken in this thesis sets apart from existing techniques.
Chapter III describes the experimental setup : hardware, software, and equipment used to conduct this work.
Chapter IV focuses on a tool of primary importance for the work, since it is used as a supervisor for all the real experiments : the video camera. Video processing and accuracy are discussed.
Chapter V gives an overall view of artificial neural networks. The aim is to make the reader understand which kind of neural network is suitable for this application, and to introduce the concepts that are useful for evaluating and improving such a system.
Chapter VI presents a first experiment conducted with the Khepera simulator. The goal was to get familiar with the neural networks before experimentating with the real robot. This first try has resulted in useful hints that saved time in the later experiments.
Chapter VII describes the experiments with the real robot, and shows how the “real world” constrains are handled.
Chapter VIII describes the extension of the system with an additional sensor. The results are presented and compared to classical odometry in normal and sliding situations (using the simulator).
Chapter IX gives the conclusion.
Chapter X gives the mathematical basis of classical odometry, and the detailed setup of experiments conducted in Chapter VI.
II. Odometry basics
This chapter aims at presenting the basics of odometry, and showing the most common sources of error in odometry systems. It. It also presents methods that improve odometry by using additional sensor information, and shows in what respect the approach taken in this thesis is different.
1. Odometry sensing
In its basic form, odometry uses information from wheels rotation only, it is then called “dead reckoning”. The most common technique to retrieve the rotation of the wheels is to use optical incremental encoders :
Figure II.1 - The optical incremental encoder
The disc is coupled to the wheels or directly to the motor. Counting the resulting pulses enables to calculate the rotation of the wheels. The user manual of the Khepera (robot used in this thesis, see section III.1) explains :
“Every wheel is moved by a DC motor coupled with the wheel through a 25:1
reduction gear. An incremental encoder is placed on the motor axis and gives 24 pulses
per revolution of the motor. This allows a resolution of 600 pulses per revolution of the
wheel that corresponds to 12 pulses per millimetre of path of the robot.”
This means that for each pulse counted, the wheel moves by 1/12 ≈ 0.08 mm. From this value and from the geometric features of the robot, one can derive equations that tells how the robot moves. Those equations, known as forward kinematics equations are then different for each kind of robot. The forward kinematics equations of the Khepera robot are given in appendix 1.
2. Systematic error
The systematic error in the basic form of odometry is mainly caused by imperfections in the construction of the robot. The problem with this kind of errors is that they accumulate constantly along the path the trajectory of the robot. The origin of these error is however well identified [Borenstein & Feng, 1996] :
· Unequal wheel diameters
· Average of both wheel diameters differs from nominal diameter
· Misalignment of wheels
· Uncertainty about the effective wheelbase (due to bad wheel contact with the floor)
· Limited encoder resolution, Limited encoder sampling rate
These errors are easy to model and can be corrected by Borenstein’ s method UMBmark ([Borenstein & Feng, 1994]). It consists of making the robot move along a certain path, and measuring the difference between the theoretical arrival point and the actual arrival position of the robot. The error measured, combined with the model, enables calculation of two calibration factors (one for the diameter of the wheels and one for the wheelbase), that can directly be added in the odometry algorithm. The idea is illustrated in figure II.2.
figure II.2 – The test path
3. Non systematic error
Non systematic error is due to unpredictable interactions between the robot and its environment ([Borenstein & Feng, 1996]) :
· Travel over uneven floors
· Travel over unexpected objects on the floor
· Wheel-slippage due to slippery floors, over-acceleration, fast turning (skidding), external forces (interaction with external bodies), non-point wheel contact with the floor
Contrary to systematic errors, non-systematic errors are not reproducible, and it is thus impossible to correct them by a calibration method. The most common approach is then to make a statistical model of the error, and reduce this error by using additional sensors. There are almost as many methods as there are sensors. For instance, [Schroeter et. Al, 2003] use orientation information from patterns on the floor to correct the heading of the robot, [Nagatani et. Al.] use optical flow information.
4. Improving odometry with additional sensory input
When systematic errors have been corrected, the only way to further improve the accuracy of odometry is to use additional sensors to enhance information from the shaft encoders. The problem is to fuse information from different sources of information i.e. given two different measurement, how to determine which one is the more reliable, and to what extent. This dilemma is addressed by considering that each sensor reading contains noise, thus the values can be statistically characterized by their mean (μ) and variance (s) as shown in Figure II.3.
Figure II.3 – Model of error
There are many methods to fuse information from different sensors : Maximum Likelihood Estimation [Nagatani et. al], Kalman Filter [Hakyoung et. Al.], Neural Network [Colla et. Al.] are common techniques. [Moshe et. Al.] present a review of these techniques.
The sensors used for additional inputs can be grouped in two categories, depending on if they get information relative to an internal frame of reference (Proprioceptive sensors) or relative to the robot itself (Exteroceptive sensors) :
Examples of proprioceptive sensors
- GPS
- Accelerometer
- Gyroscope
- Inclinometer
- Compass
Examples of exteroceptive sensors
- Range Finders (Infrared, Laser)
- Radar (US, Radio waves)
- Camera (Stereo Vision, Optical flow)
Information from the wheel encoders can also be fused with higher level information e.g. Landmarks, Beacons, or Maps. This kind of information is generally a rough estimate of the location; these methods are thus rather a way to “recalibrate” odometry at known places [Palamas et. Al.] in order to reset the accumulated drift.
5. What is different in the presented approach ?
First, the presented approach doesn’t use any mechanical model of the robot or of the error. Instead. the systematic and non-systematic errors are modelled by the neural network during learning.
Second, it also differs in the way additional sensory data is handled. Other methods (see section II.4) first calculate separately odometry information from different sensors. Those different estimations are then combined using some method (see Figure II.4). In this thesis, both calculation of odometry and fusion are performed at the same time in the neural network (Figure II.5).
Figure II.4 – Odometry calculation is done before fusion
Figure II.5 – Odometry calculation and fusion are done at the same time
III. Experimental set up
1. The robot
Figure III.1 - The Khepera robot
For all experiments, a Khepera robot was used. It is a two-wheeled robot endowed with all the necessary sensors to achieve navigation. For my purpose, only the shaft encoders are used. The first idea was to use the Vision Turret (a simple camera mounted on top of the Khepera) in combination with the shaft encoders but this idea was abandoned after some time (see VIII.1)). The robot is connected to a PC via a serial connection, which allows reading the sensors values and send the navigation commands at the rate of 30 Hz (This rate becomes only 13 Hz when the Vision Turret is used).
2. Software
All the software parts are implemented with MATLAB. The programming language is easy to work with and a number of powerful tools are available, such as :
· Neural network toolbox
· Image processing toolbox
· A Khepera simulator : Kiks ([Nilsson, 2001])
These tools motivated the choice of MATLAB as developing platform, because they cover exactly the needs for this thesis. Implementing a neural network and its learning algorithms in C language is not simple, but MATLAB do it in one line of code. A Khepera simulator isn’t a real Khepera, but it enables to save time in many cases. Having those tools gathered in the same software fairly simplifies the implementation.
3. The arena
Figure III.2 – The arena
The Khepera moves in a 50 x 80 cm arena. The walls are covered with black and white stripes in order to enable a good quality of the pictures taken by the camera. This arena provides also a flat floor suitable for the Khepera’s small wheels (The Khepera is definitively an indoor robot).