Thursday, June 1, 2017

A gentle guide to start Extended Kalman Filter project

updated on 2017-6-18

I am moving very fast in term 2 and just finished all the projects in 3 weeks. In retrospect, uWebSocketIO is very necessary because all the projects have data IO with the simulator. And it’s a lot of fun watching the animation when you get the codes right.
Note: The reviewer will use the original “CMakeLists.txt” to judge your code. Although I recommend Clion IDE to facilitate debugging, make another copy for submission and make sure the following command works:
mkdir build && cd build
cmake .. && make
./mpc   # run it

This first project is overwhelming for C++ beginners wading from the Python world, where a lot of low-level implementation details have been hidden by the Python interpreter. The reasons why we use C++ in the self-driving car are:
  1. C++ is much faster in running. The codes are already compiled beforehand.
  2. C++ is more reliable. C++ is statically typed so the machine knows exactly how much memory should be allocated for each variable. And C++ has full-fledged object-oriented support so it is much easier to handle a large project.
  3. C++ is more closed to the hardware. It is the first language for “Internet of things” devices. A particular example is that the electrical engineering students write C++ codes in mbed for ARM Cortex chip/microcontroller.
Now we get our mind in C++. For this EKF project, the major goal is to implement Kalman Matrix (using Eigen library). On 2017.5.3, Udacity introduced the simulator, which makes the result visually appealing, but may frustrate beginners due to the complicated setup of the uWebSocketIO.
In this blog, I will guide you through the basics by 3 steps. You can jump into step 3 to see how uWS is setup for Mac.
I use Macbook Pro OS X El Capitan (10.11.6). My C++ IDE is Clion (1 year free for a student). I recommend use Clion because each project folder is very clean: your source codes, a “CMakeLists.txt” and a “cmake-build-debug”folder (where you put the input.txt). I use CMake 3.7.2 and C++ 11.
You may need to spend a little time to understand how “CMakeLists.txt” works. Udacity provides such file for each project for term 2. If you use Clion, you only need to make a little changes and everything works like a charm.

1. practice Kalman Matrices locally

Practice locally to clear any blindspot.
Lesson 5.6 (Kalman Matrices 1D) is a good starting point. Learn how to use Eigen libraries and how matrix/vector works. There are 2 ways to include Eigen libraries depending on where you store them. Details see my note.
Lesson 5.12 (laser measurement 2D) is a mini-version of the EKF project. This is the best place to get familiar with the algorithm flow and how to link different source file together. My learning notes are here.

2. EKF without uWS

Download starter code from Udacity.
Create a copy. Compare two “main.cpp” files from lesson 5.12 and the starter code, delete everything about uWS. It will be easy if you already run 5.12 codes locally. There’s no trick in my “CMakeLists.txt” :
cmake_minimum_required(VERSION 3.7)
project(kf_p1) # kf_p1 is a project name I choose
add_executable(kf_p1 main.cpp kalman_filter.cpp FusionEKF.cpp tools.cpp)
Now you’re ready to dive into EKF project. Without the distraction of uWS, you can actually code and debug much more efficiently.
For example, you will encounter Assertion failed: (aLhs.rows() == aRhs.rows() && aLhs.cols() == aRhs.cols()), function CwiseBinaryOp,.... In other words, the dimensions of two related matrices are not aligned. The bad thing is that the compiler doesn’t tell you where the error happens. So you have to set some break points or use cout here and there to localize the error. You can do it more efficiently with a direct ifstream than json stream via uWS.

3. use uWebSocketIO

My workable “CMakeList.txt” looks like this:
cmake_minimum_required(VERSION 3.7)
add_executable(kf_p1 main.cpp kalman_filter.cpp FusionEKF.cpp tools.cpp)
target_link_libraries(kf_p1 z ssl uv uWS)
Ideally, every include files should be in /usr/local/include and every lib files should be in /usr/local/lib. But brew install organize things differently and put them in /usr/local/Cellar/ by name and version.
To walk you through the setup, I will divide it into 2 steps.

1. install dependencies

The tricky thing is that uWS is built on 3 libraries (ssl, zlib, libuv). These 3 libraries can be easily installed by brew install openssl zlib libuv.
As you see in the “CMakeList.txt”, these 3 libraries all have a folder called “lib”. But uWS doesn’t have such thing because it is built on others. There may be also some environment dependencies so you will have to build it yourself in step 2.
For a similar reason, there is no brew install for uWs. You have to download it directly from its official github. However, the started code seems not compatible with the latest version 0.14 and will cause “onMessage” issue. So it is recommended to use version 0.13.

2. make uWS library

Udacity has provided a walk-through video and file to do this. I am trying to fill the knowledge gap from my experience:
brew install openssl libuv cmake
git clone 
cd uWebSockets
git checkout e94b6e1  # all files restored to v0.13
patch CMakeLists.txt < ../cmakepatch.txt  # revise "CMakeLists.txt" from "cmakepath.txt" in upper level folder
mkdir build  # create a new folder
export PKG_CONFIG_PATH=/usr/local/Cellar/openssl/1.0.2k/lib/pkgconfig # modify yours, check by "brew list openssl"
cd build
cmake ..   # produce a "Makefile" and a file folder
make    # use "Makefile" to compile sources into library
sudo make install # copy files to "/usr/local/..."
cd ..
cd ..
sudo rm -r uWebSockets
Several confusing things in the above:
  1. “patch” command. “cmakepatch.txt” is provided by Udacity, and “CMakelists.txt” is provided by uWS. So make sure these 2 files are in the right place. Tricky thing is the latest UWebSockets only provides Makefile but no CMakelist.txt
  2. What “cmakepatch.txt” does is to add command that will install libuWS.dylib to /usr/local/lib and copy a batch of .h files to /usr/local/include
  3. I never get through cmake .. and make by following Udacity’s guide. I always get errors related to “openssl” and can’t figure out why. Thanks to Ian Zhang for providing the Makefile. It is based on the latest official uWS Makefile and adds one more line:”CPP_EXPERIMENTAL := -DUSE_MICRO_UV”. I use this file then everything works like a charm!
  4. The last command is to remove the whole “uWebSockets” because it is not needed anymore. All the useful things have been copied to /usr/local/…

Final words

Despite I spend almost 2 days dealing with various tricky errors, it is worth the effort to get installed. I hope this guide can help you save some time and dive into the essentials.