Applications of the Kalman Filter Algorithm to Robot Localisation - Lab Report Example

?Robot Lab report Introduction: Mechanics and Electronics play a vital role in our day to day life. The invention of mechanical/electronic devices have changed our traditional way of life tremendously, that the amount of human labor has been reduced to a great extent. These devices are so intelligently and efficiently developed that it can automate most of the human-can-do functions making our daily labor so easy and comfortable. Robots are one such invention that uses the principles of mechanics and electronics and are designed to automate a repeated group of tasks so as to minimize or replace human labor. To define more precisely, Robot is “a device that automatically performs complicated often repetitive tasks” (merriam-webster). The task is instructed to the robot in the form of programs using any programming language. Robot can either be guided using a remote control or can be made completely automatic by pre-defining the directions in the program thereby replacing the complete human interventions. One such application of automated robots would be in industries where these robots handle tasks like cutting, welding, packing and moving to the correct destinations and so on, thereby increasing productivity, safety and profitability. Though the initial cost of purchasing a robot is comparatively higher, the advantages they offer simply overwhelms them. As a part of our Robot study course, we have designed and programmed one such automated robot using Lego NXT, a programmable robotics kit from Lego. Lego NXT comes with a brick shaped device called NXT Intelligent Brick which forms the brain of the robot. This device can be thought of an intelligent micro computer that can be programmable with many compatible programming languages. It can operate with up to four sensors and up to three motors. It also comes with an in-built LCD display and necessary buttons to navigate the user interfaces using hierarchical menus and a speaker to play sound files. Simple programs can be developed using this menus and more complicated programs can be downloaded through USB or Bluetooth. Though it can be programmed with many compatible languages, we have chosen Lejos, a high level open source language based on Java, for programming the device. A step by step procedure on how we have developed the robot is summarized below: Sensor Calibration: “A sensor (also called detector) is a device that measures a physical quantity and converts it into a signal which can be read by an observer or by an instrument” (Wikipedia). Sensor is like an eye for the Robot, without which they are actually blind. A robot uses sensors for detecting what is happening around them so that they can respond or react to varying circumstances. In our design, we have used a simple ultrasonic sensor. This ultrasonic sensor is attached to the Lego NXT brick and series of measurement were taken in order to calibrate the sensor. The various factors involved in sensor calibration include sensitivity- the smallest change in input that will be detectable in the output, range- the minimum and maximum distances it a can measure, precision- the degree of reproducibility of a measurement i.e if the same value were measured a multiple of times, and good sensor would output exactly the same value every time, resolution- the smallest detectable incremental change of input parameter that can be measured in the output signal, accuracy- the maximum difference between the actual value (which can be measured by a ruler) and the indicated value at the output of the sensor, linearity- an expression of the extent to which the actual measured curve of a sensor departs from the ideal straight line and Hysteresis- the measure of capability of the sensor to follow the changes of the input parameter regardless of which direction the change is made. The measurement for each factor is recorded and the device is calibrated. Odometry and Dead Reckoning: Now that we have calibrated the sensor for the robot to recognize when to respond, the next step is to help the robot know where it is, in other words how far it has travelled since the starting point. Odometry is the term used to estimate the position of the robot with reference to the starting position. It uses the information about the rotation of wheels during motion, to calculate the change in position over time. Once it knows the number of rotations the wheel has made and circumference of the wheel, computes the distance travelled. Dead reckoning is “the process of calculating the current position by using a previously determined position, or fix, and advancing that position based upon known or estimated speeds over elapsed time, and course” (Wikepedia). In other words, dead reckoning works out the current position based upon a previously fixed position and moving that position based upon known speed, time that has elapsed, and the direction. Car Pilot is the class used to allow the DriveTime class to run both the odomerty method and the dead reckoning method. Running these methods would give how far the robot moved away from its original starting point. Maze Solving and Path Finding: The next step is to feed the robot with a pre-defined route also called a maze and program it to find the correct path to reach the right destination. Here, we need to consider the robot as a three headed-dog because a maze walking robot needs to be able to "see" walls ahead, to the left and to the right so that it knows whether it has reached a junction or a dead end. The method followed here is Wall-following, which is a simple maze algorithm we might have learned as a child. All we do to solve a maze using this algorithm is keep your left hand on the left wall (or your right hand on the right wall) and just follow it along until you exit the maze. It's easy to see that this algorithm always works if the maze you're in has an entrance and an exit on its border. We have used the left hand rule, where the robot solves the path by following the wall to its left. An EOPD (Electro Optical Proximity Detector) sensor is used to detect its left side wall. On the programming end, Lejos comes with a special class that supports EOPD sensors; we have used the methods in the EOPD class to implement the wall following method. The movement of the robot is controlled by using the LegacyPilot class of robotics navigation package of the lejos which contains methods to move the robot forward, backward, rotate by any given angle and also to move in a circular path. The identification of the robot on how it should be move or what direction it has to take is controlled by the Behavior interface of lejos subsumption package. This holds the methods for recognizing the behavior as a forward or backward or a turn and dictates how it should respond under each condition. Control Theory and the PID: “Control theory is an interdisciplinary branch of engineering and mathematics that deals with the behavior of dynamical systems” (Wikepedia). The main goal of implementing the control theory is to stabilize the system so that it does not oscillate from its actual behavior. The concept of control theory is used here for balancing the robot in case of robot falling backward or forward during its motion. We have used a PID controller as a part of the control system for the Robot. PID stands for Proportional-Integral-Derivative, which actually refers to the three terms, which on proper tuning can offer the desired dynamics. The three terms can be summed up as: P – Proportional control. The output varies based on how far you are from your target. I – Integral control. The output varies based on how long it’s taking you to get to your target. D – Derivative control. The output varies based on the change in the error. Greater change is greater response, good for dampening spikes and jumps. (Krass, Matt) If u(t) denotes the control signal sent to the system, y(t), the measured output and r(t), the desired output, and tracking error e(t) = r(t) ? y(t), a PID controller has the general form (Wikipedia) On the programming face, in order to make the robot stand on two wheels, balancing by powering the wheels forwards or backwards, we have used the Segway class of the lejos, which . The parameters Kp Ki and Kd are first initialized. The deviation or the error in robot movement is recognized by the deviation in the angle from vertical. The required speed is calculated based upon the error value using the above function. If the robot is found to be falling backward, it is made to move forward with calculated speed depending upon the error value and if it is found falling forward, it is made to move backward in a similar fashion and finally stop in a balance position. After balancing, the robot is free to continue as per the pre-defined route. Kalman Filter and their use in Localization: One of the key concepts involved in designing automation robot is localization, which talks about the ability of the robot to find its current location at any point of time throughout its journey. A well designed robot should be able to localize itself very precisely in order to avoid any difficulties in proceeding further. In order to do this, a robot should be fed with some sort of calculations which would help them find their location as accurate as possible. As discussed in odometry section, we can use the wheel encoders to find the relative position from the starting point. This is the frequent method of localization; however this is not practically feasible as the robot may slip during motion or smack with any object while on the move. One such approach would be to combine this locomotion data with the measurements from the sensor so as to provide the robot with absolute and relative measurements which would give them a quantity of thought about its driving actions and the environment around, which would in turn help them find where they are in terms of X and Y co-ordinates and the orientation. What makes this difficult is the existence of uncertainty in both the driving and the sensing of the robot. The uncertain information needs to be combined in an optimal way. The Kalman Filter is a technique from estimation theory that combines the information of different uncertain sources to obtain the values of variables of interest together with the uncertainty in these. (Negenborn, Rudy) In our design, we have used Kalman filter algorithm for localization. This algorithm is so effective that it not only combines information from different sources but also at different times. It updates the robot with the exact location along with orientation as the robot moves. Important factors to be considered in kalman filter are: The Kalman Filter algorithm assumes that all noise is white (has equal energy at all frequencies) and has amplitude which can be modelled as a Gaussian (or Normal) distribution. The Gaussian distribution has two important parameters: The mean (the average size of the noise). All noise considered has zero mean. The variance (the square root of variance is the standard deviation which is the average size of the noise away from the mean). A probability distribution with a higher variance has a higher overall level of noise. Another fundamental part of the theory of the Kalman Filter is the covariance matrix. The covariance matrix of a state variable vector V with zero mean is defined as the expected value of a vector multiplied by its transpose E(VV'). One Kalman Filter parameter we will come across is P, the error covariance matrix. When we talk about error we mean the difference between the actual state variables and the estimated state variables. P is generally used as an estimate of the uncertainty, that is, the larger P is the more uncertainty there is in the estimate of the state variables. The square root of the diagonal elements of P give the standard deviation of the error in the state variables. (Freeston, Leonie). In the programming end, Kalmanfilter utility of the lejos simulates the actual kalman filter algorithm. The state of the system is considered to be the wall and the control data is the velocity, which is chosen randomly every second. The measurement data is the ultrasonic sensor range reading to the wall. The Kalman filter predicts the robot position from its velocity and updates the prediction from the range reading. The program first calculates the locomotion data from the wheel diameter and the distance between the wheels. Then it reads the information from the ultrasonic sensor. Initial matrix for each parameter (position, velocity, measurement, ultrasonic noise factor, movement noise factor) is defined. Pilot is created with the information about the wheel and data and Kalman filter is created with the matrix defined above and set to the initial state using the covariance. The program is made to iterate for different random values of velocity, each times updating the filter with the measurement and control information depending upon the range value from the sensor. Conclusion: The design of this simple robot has helped us to utilize the entire knowledge we acquired from our robot lab sessions. Starting with a simple kit and a sensor, we have learnt the techniques involved in sensor calibration, and basic localization using odometry and dead reckoning. Though we initially understood that odometry helps the robot to localize them, later we found that there can be many errors involved in this method. With the implementation of Kalman filters, we have achieved a complete solution for robot localization. In the maze solving and path finding process, we have learnt to program the robot to use the left hand left wall method to solve the maze, and implemented three-headed dog realization to identify dead ends. Implementation of control theory using PID controllers have stabilized our Robot to a great extent that it can balance itself with its two wheels efficiently even when it is about to slip forward/backward. However, we consider this project as our first step toward Robot design; we have a plan to research and study further to create more complex automation Robots. Source Cited Merriam-webster, www.merriam-webster.com, Definition of Robot, web, n. p, n. d, 18-Dec- 2011. Wikepedia, www.wikepedia.com, Definition of Dead Reckoning, Equations for control Theory, web, n. p, n. d, 18-Dec-2011. Krass, Matt, http://www.team358.org, PID Control Theory, web, April 10th, 2006, 19-Dec-2011. Negenborn, Ruby, w ww.negenborn.net, Robot Localization and Kalman Filters, web, August 26, 2003, 18-Dec-2011. Freeston, Leonie, www8.cs.umu.se, Applications of the Kalman Filter Algorithm to Robot Localisation and World Modelling, web, 2002, 19-Dec-2011 Read More