FYP Progress up to Recess

Recently I was largely occupied by projects and labs from other modules, therefore the progress for FYP is not as fast as previous a few weeks.

I found the following articles useful and summarized them as below.

 

Simultaneous Localization and Mapping for Forest Harvesters

This article is based on a forest harvester application that is done in Finland. The environment is extremely similar to the Out-door project that Jinqiang is doing (I guess).

The main sensor for this mentioned project is laser scanner. They made use of a graph data structure to store the measured information and run multiple data association algorithms against the obtained data on batch basis.

They also brought up a few interesting points in the article:

1.    They claimed that the image beacons does not help in the data association problem. The season is simply that trees in forests looks alike. They claimed that this is extremely true in well-maintained forests.

2.    The proposed the idea (not realized though) that measuring the absolute angle would help in the data association problem.

a.    I think magnetometer would help in geometry based data association, if the sensor was able to produce measurements of absolute direction with reasonable accuracy.

b.    I am not sure whether the motors from the helicopter would interfere with the magnetometer.

3.    They are using GPS in their project. Since their tests are also carried out in forests, is it the case that GPS data is actually available in forests.

 

Towards Lazy Data Association in SLAM

This paper took a second look at a basic assumption that most maximum likelihood data association algorithm adopts, which is all pervious decisions made were correct.

 Data Association

        In this proposed approach, author maintained a tree-like log-likelihood data structure. Each time a new data association decision is made, all frontier are re-examined to see whether modifying one of the pervious decision would result in greater likelihood. If so, the upper level to the modified leaf would also be checked recursively, until a maximum is obtained. In the process, all log-likelihood data are maintained in the tree data structure for later use.

 SLAM

        The SLAM part of this algorithm is similar to the Sparse Information Filter SLAM. All measurements are finally translated in to soft constrains and the mapping task becomes an optimization problem.

 Computation considerations

        If this idea is implemented on feature bases, the memory and computation usage would be very expensive. Therefore, I don’t think this method would be able to run on-board.

        The lazy nature also make this approach hard to meet real-time requirement. Whenever a modification of previous data association is made, the search might be substantial. Therefore the computation time variance from frame to frame is large. In such case it’s easy to hit scheduling deadline, if run in real-time.

In short, the advantage of this method is the modification solved the root of brittleness for data association problem, which is the assumption that previous decisions are always right.

The disadvantage of this approach is that, the lazy nature of the tree search and the large amount of computation for inverting information matrix make this approach hard to implement for real-time.

FYP progress for week 3 & 4

Overview

For the past two weeks, the main focus was on trying to understand the various approach in solving SLAM problem.
The book borrowed from Jinqiang turned out to be extremely useful!

Literature summary:

Particle Filter Based Robust Simultaneous Localization and Map Building for Mobile Robots
This article discribed an approach to detact and fix gound robot kidnap problem in real-time SLAM.
Basically, the author was monitering the residule from odometry readings. When it is likely that fault has occured. The particles are mutated in order to retrack the position of the robot.
The artile is short and does not contain much details.

Noval approach to nonlinear/non-Gaussian batesian state estimation
This article discribes the math and thought behind particle filter and proved particle filter performs better than EKF in certain cases, where it's nonlinear or non-Gaussian.

A Method for Registration of 3-D shapes

This paper discribes in detail the ICP algorithm, however, I have not get the time to finish this paper, before I find the book below is much better.

Probabilistic Robotics

Chapter 5 robot motion

This chapter dealt with motion model of robot. Two approach was given in the book, one was based on controll input, the other was based on odomery.
However, I felt that the two approach given in the book was mainly meant for ground robot, however both could be related to our case.

• The odometry model could be related to the optical flow model, whic is being developed by Wang Fei.
• The control model for a UAV is way more complex than the one for ground vechicle. In order to make the model usable for 2-D SLAM, we have to find a way to approximate the 3-D motion into 2-D. It might also be a problem that the heading of UAV might not be the direction that the UAV is actually propagation. Extensive research in UAV control and modelling need to be done in order to obtain a control-based motion model.

Chpter 6 Robot Perception (measurement model)

This chapter introduced a few types of measurement model that could be used for laser sensor.
In my point of view, establishing an accurate measurement model is criticle for the rest of the task. (especially after seeing Bo Xuan's work).
The model introduced in the book could be summarized as follows:

• Beam model for Range finders is a model that could be justified with rigour and tuned systematically. In the model, there are 4 factors that could contribute to a measurement reading, each of which can be represented by a probability distribution. They are:
• hit: the intended measurement with a narrow gaussian distribution
• short: obstruct by unintented object
• max: max reading returned, due to lighting condition, color of object, reflection etc.
• random: other factor contrbute to a false reading
• The wrights of these four factors and their intrinsic parameters could be tuned.
• The shortcomes of this approach are:
• Expensive computation involved
• Dependency amoung beems, which are assumed to be independent
• Lack of smoothness (trouble caused by objects like table leg, chair etc.)

• Likelihood Fields for Rnage finder is a model only deal with the end point of the measurements(except for the max readings). This method calculate the position of the end point w.r.t. global map using translation matrixes and adjust the probability of encountering an obstacle at the end point. This approach deals with 3 out of 4 factors in the Beam Model
• hit
• max
• random
• The disadvantages of this approaches are:
• It does not model dynamically moving objects (short category)
• The algorithem does not deel with problem of going through obstacles
• It does not takes into account the matching of free space
• While comparing to Beam model, this approach does better in smoothness

• Correlation-based measurement model is not really a measurement model. It's more a method that matches two local maps and produce parameters like distances between maps.
• The advantage of map mapping is that it considers white spaces in the map. But the dis advantage of this approach are there is no physical explanation behind and there is no noise charicteristic of the sensor.

• Feature-Based measurement Model is what Bo Xuan has done (more or less). It has to do feature extraction first before the data could be processed to yield measurements. Being at a higher level, features extracted are way lower in number. Therefore, the computational cost for this approach is much lower.
• The main challenge in feature-based measruement model lies in data association steps. We have to find a way to extract a signature of every feature, so that it could be checked to confirm the association of data. In order to do this, Lidar alone will not be enough.

Chapter 7 Mobile Robot Localization: Markov and Gaussian

This chapter introduced, in detail, two similar approach (EKF and UKF) to realize localization task.
Both EKF and UKF assumes a gaussian distribution for measurement noise. Their differece lies in the different ways to linearize the measurement/ motion model. UKF usually produce better result at the cost of more computation power.
The main draw back of both approaches are that they were subject to global registration and kidnap problems.
Author also briefly mentioned another approach- multi hypothesis tracking algotrithm (MHT), which I think is the most promissing amoung the gaussian filter approaches. It is more robust, while still seems practicle to be implemented in real time.

Chapter 8 Mobile Robot localization: Grid and Monte Carlo

This chapter introduced mainly two approach to achieve the localization problem, and they are grid (histogram filter) and Monte Carlo.
They are similar in a sence that they both try to represent the probability distribution by having a sample of states.
However, Monte Carlo is more efficient as compare to Grid based approach, especially after adopting the KLD-sampling approach.
As compare to Gaussian filter based algorithms, these two approaches solved the global registration and kidnapped problem at the cost of heavier computation. But, if implemented properly, the Monte Corlo approach seems promising to be run in real-time.

Goals for now

Following should be done before CA1:

• Finish the SLAM related chapters in the book
• Look back into the papers that has been found and categorize them according to as the book suggested
• Try finding some more articles through the references in the book

FYP Progress for Week 1 & 2

Overview

For the past two week, the main focus has been trying to understand the literature's received from seniors, Wang Fei and Cui Jinqiang.
I have also downloaded and installed MatLab on my PC and labtop, so that whne I finish reading, I could getting started with the Matlab codes.

 Classification of Literature

The literature's can be roughly classified into following topics:

• Localisation
• Feature based localisation
• Feature extraction
• Cartesian coordinate based
• Sensor coordinate based
• Transformation estimation
• Point based localisation
• ICP algorithm
• MbICP Algorithm
• IDC algorithm
• SLAM
• EKF SLAM
• Fast-EKF SLAM

Literature Summaries

Simultaneous Localisation and Mapping with extended Kalman Filter

This article introduced the steps of implementing a EKF-SLAM algorithm after processing the raw scanning data.
In the article, how to extract feature, and how to estimate the position of the UAV are not mentioned.

An Introduction to Kalman Filter (Find through Library E-resources)

As I had never came across the term EKF. I searched for this article so that I know how Kalman Filter and Extended Kalmen Filter came about.
This article explained in detail, how KF and EKF are obtained mathematically and illustrated what should be done, in updating an estimation after each set of data in obtained from measurement.

Stochastic models, estimations, and control <chap 1-3> (Borrowed from Library)

I browsed thought the first a few chapters of this book mainly to familiarise myself to matrixes.
I never came across Matric-Representation of linear systems and Correlation matrixes. I need to get a taste of what are the meanings of these matrixes.

High-speed laser localisation for mobile robots (Find through Library e-resources)

This paper presented a localisations method based on both sensor's coordinates and Cartesian coordinates. The algorithm is termed "HAYAI".
The proposed algorithm made use of linear filters, which could be easily implemented by Matrix multiplications. As a result, it achieved good computational speed with reasonable accuracy.

Feature-based laser scan matching for accurate and high speed mobile robot localisation

This paper aimed to improve on the accuracy of HAYAI algorithm by refining the feature extraction part of the HAYAI algorithm.
Author Incorporated the covariance into the computation, which makes the process slower but more rigorous.
The line extraction and corner extraction algorithm has been improved to expect better accuracies.

Metric-Based Scan Matching Algorithms for Mobile Robot Displacement Estimation

This paper introduced the MbICP algorithm.
The introduced algorithm tried to solve for displacement and rotation at the same time. After taking approximation, the expression is simplified into second order equations, for which the extreme value can be easily obtained. The same was applied again for point -to-line transformation.
Author claims this method has significantly better result, as compare to tranditional ICP methods
.

Efficient Variants of the ICP algorithm [have not understood fully, in progress]

I am still working on this paper.
This is a review type of paper, therefore, I need to dig through some of the reference list before I could understand what all the comparisons are talking about.

GSoC 2012 update

The review of the app has been successful!

It's available at OI Shopping List in App Store

GSOoC 2012 Week 10 report

This week, the primary focus has been to complete the store-wise price calculation related features.

A subtotal display is added to the ListContentTableViewController. Store filter is also implemented and added to the application.

Functionality of both feature are similar to the android version.

The subtotal calculation sums the product of unit price and quantity of all unchecked items. And updates the sum when the user load the list, modifies the list or check/ uncheck the items.

The Store filter enables user to display items with price information available within a certain store. The app would load all the stores that are related to the displayed list. After one is selected by the user, those items that has price information related to the selected store would be displayed, others would be hided.

Screen shots of both feature have been attached below.

 

These two screen shot shows the button to filter and the action sheet popping up after clicking filter button.

These two screen shot below shows selecting store filter and filtered list display.

After completing the store-wise price calculation, I feel that the feature could be improve as below:

Now, list owns stores. In other words, when we create a new list, we have to input the price information from scratch. Which can be a thing that users do not want. If we could change it around, and makes Item owns the stores. That could be potentially better. For example, I buy potato chips on Wednesday and recorded down it is $3.00. If I add potato chips to the Friday shopping list, it would be good to have the $3.00 information in the list automatically, then “forget” about it and ask users for it again.

Of course, this would add complexity to the algorithms. Other potential problem could be that a long list of prices and stores might be associated with a item, and the database might be messy and difficult to clean up.

I could now, focus on cloud synchronization solely. Hope it could be done soon!

GSoC Week9 Report

First of all, I am glad that I have passed the mid-term evaluation. Now, I have got more thrust to move on with the project, complete the price feature, optimize the interface and incorporate the cloud sync feature into the app.

This week, the mean focus is still on store-wise price calculation. It has been pointed out that the bug in android has been fixed and after updating my source version, I am able to run the android version smoothly. There I finally got the full picture of the app.

There was an discrepancy between my previous understanding of store-wise price calculation and the one that Android is using now. My understanding was, store would be primarily associated with items, since that is the thought that most people have in real-live. While in the Android app, stores were associated with list. This makes the implementation easier. I took the second approach after considering the two. Firstly because it is more manageable; secondly because of the consistency crossing different platforms.

After clearing the mis-understanding of how it is done. I continued with my implementation.

The data-model has to be slightly adjusted, as follow:

the list_id is a to-one type of relationship

each store is “tied” to a list, removing the list would remove the store.

Then I went on to realize the interface, The challenge was, I have to use a customized a table cell with textfield in it. The approach I took was to subclass the text field, and add a property “store name” to each of the textfield. So that when user modifies the price, I would always know it is the price in WHICH store that is being modified.

 

The store-wise price menu is in the edit entry detail menu, a screen shot is attached below.

GSoC Week8 Report

The primary focus of this week has been:

Implement the price calculation.

However, this feature is not, yet, ready for running. Thus, there was no code uploaded this week. 

The working code for this week will be uploaded as soon as I finish up the remaining parts, latest by the next week.

The main challenge of this task is to implement the store-wise price calculation.

There is a bug in the Android version of the app, there was no ready algorithm for this purpose. It's more like writing something brand new rather than fit something to a different platform.

The task can be brought down roughly, as follows:

 

Core Data

Responsible for creating and managing the relationship between contains, items, prices and stores. 

Fetches and Calculations

when a list is displayed, the subtotal of the times will also be displayed at the bottom of the list.

Interfaces

Interface must be improved to accommodate the price feature and store-wise price calculation.

Potential problems are:

When a price is created, it must be associated with a store, if we intend to calculate the price base on store. However, this creates tedious input process, as the user has to input information about a store before he can do something with the price.

Therefore, it would be a challenge to present the UI in a neat and concise manner.