Improving runtime efficiency of simultaneous localization and mapping techniques

When the word "robot" is enounced, it is commonly understood that it is a humanlike machine with its arms, legs, head and body. But, there are lots of different types of robot mechanisms used in industrial sectors, planetary explorations, education and military. For example; a robot in an automobile factory looks like a human arm which is attached to a fixed joint. These machines are designed to carry out the tasks like painting and welding. They do their job recursively in a predefined manner by humans. On the other hand, a machine discovering a planet may looks like a vehicle. Because of unpredictable environments and conditions, these robots should decide how they carry out their tasks on their own. These tasks may be going to somewhere with specific coordinates from current location or . It is hard even to go from one place to another without getting lost and hitting the objects. In order to manage this change of location mission, a robot should first understand how the environment looks like and where it is in this environment. Without foreknowledge of the surroundings and coordinates of current position, estimating the robot pose and generating the map of environment is called as simultaneous localization and mapping (SLAM). SLAM also known as concurrent mapping and localization (CML) is a very hard problem for robots due to the noisy measurements, unpredictable conditions, wheel or foot slippage, presence of moving objects around and estimation errors. Additionally, the amount of the data collected by measurement devices may cause a huge computational cost for processors of the robot. For example; a laser range finder with 360 degree field of view can collect a great number of data. This huge data causes the methods which constructs grid map to slow down. Likewise, a system using camera should process lots of data. In order to reduce the computational cost of SLAM algorithms, one can either increase the number of collected data or improving the process of SLAM techniques. Most of the researhers are focused on solving the problems above using probabilistic methods. In literature, there are two common SLAM technique called as EKF-SLAM and FastSLAM. The EKF-SLAM is easily applicable approach while the FastSLAM is computationally efficient technique. These two methods are landmark based and use kalman filter. Landmarks are distinct points of some objects such as doors, walls or several geometric objects. Using landmarks decrease the operation time when compared to the SLAM methods which construct grid maps. EKF-SLAM has a significant drawback by comparison with FastSLAM. When the number of landmarks reaches to a high value, EKF-SLAM gets slow drastically. This is caused by a procedure in EKF-SLAM which is called as data association. Data association is a process of matching currently sensed landmark with the one in the estimated map. All the elements in the map are associated with each other. Therefore, when a new landmark is detected, the map grows exponentially and this structure gets the algorithm slower. As a solution for the exponential growth in EKF-SLAM, FastSLAM offers a very innovative approach. It combines the particle filter and extended Kalman filter by separating pose estimation and landmark estimation. While EKF-SLAM is interested in calculating only current pose of the robot which is called as online SLAM, FastSLAM is interested in calculating the path of the robot which is called as full SLAM. With the knowledge of the whole poses of the robot, FastSLAM estimates the landmarks individually. This means that all landmarks are associated with only robot pose. When the robot detects a new landmark, mean and covariance of the landmark are added for all particles that causes a linear growth in the map. Considering the exponential growth in EKF-SLAM, FastSLAM brings an important innovation to map management. However FastSLAM is very efficient approach, it also gets slower if the number of estimated landmarks are gigantic. Because, in such a case, FastSLAM faces the numerous operation in data association step. In order to decrease the computational cost of the data association, several approaches are proposed. The most effective method limits the number of landmarks to ones only in the range of the measurement device. This method provides a very good computational efficiency for SLAM techniques, especially for the particle filter based ones. However, if the scan range of the measurement device attached to the robot is extensive, the number of landmarks that are considered in data association process is high again. Also in some situations such as a landmark is out of the range of the sensor, this approach may fail. In this thesis, a novel technique that eliminates unnecessary operations in data association process is proposed. Briefly; when a new landmark is detected by measurement device, it is compared with the landmarks only in a small circular area. Other landmarks in the map and outside the circular area are automatically skipped. Center of this circular area is estimated by using the sensor measurement. Therefore, no matter how big the number of landmarks, the computational cost in data association step remains almost same as the beginning. In order to see the success of the proposed method, simulations are performed in different environments that were created by a simulation program called as Gazebo. Different SLAM algoritms are also tested in simulation environments in order to understand how much the new approach is faster than other aproaches. Additionally, these tests are done in real laboratory environments. Before testing the new SLAM technique and others, some arrangements were made. The sensor which is used for the collection of 2D data from environment, produces noisy data. This noisy data makes the landmark extraction very difficult. For this reason, a smoothing filter was implemented on the noisy data. For the sake of simplicity, the mean filter was prefered. After smoothing the laser data, landmark extraction became easier. Another arrangement was made for the landmark extraction and identification. The curvature function method which simplifies the identification of the landmarks was implemented on the sensor data. After tuning all the parameters of the SLAM algorithms, the robot operated 30 times for two different environments and three different SLAM methods. When the simulation results were analized, it was understood that proposed method estimates the robot pose and landmarks map almost at the same accuracy compared with other methods. Afterwards, the runtime values of the three methods were compared. It was clearly seen that the proposed method improves the runtime efficiency of actual SLAM methods. The results of the real world experiments also reveal the improvement of the new approach. In recent years, the sensor technology has improved a lot. They can scan very wide range of field and collect a huge data. Therefore, it is contemplated to implement the new SLAM method on the systems with sensors of different quality so that how the approach is effective. Similarly, the new technique can be implemented to the different SLAM algorithms to see its suitability.