State Estimation with Kalman Filter

State Estimation with Kalman Filter

Kalman Filter (aka linear quadratic estimation (LQE)) is an algorithm which can be used to estimate precise states of a moving object by feeding a series of noisy sensor inputs over time.

The Kalman Filter and its derivatives namely, “Extended Kalman Filter (EKF)” and “Unscented Kalman Filter” are highly reputed in the field of information processing. The most famous early use of the Kalman filter was in the Apollo navigation computer that took Neil Armstrong to the moon, and (most importantly) brought him back. Today, Kalman filters are at work in every satellite navigation device, every smart phone, and many computer games.

The Kalman filter requires a dynamic model of the system to predict next states of the system. The dynamic model can be motion laws or other equations that has ability to calculate the next state with use of correct coordinates.

Kalman Filter performs on two main operations. They are,

  • Estimating the next state of the machine
  • Correcting the estimated state with actual measurements

The following picture shows estimated location (after the correction) against measured location and the true location.

Modeling Kalman Filter

To model the scenario with Kalman filter, it requires to model two equations.

  1. Process model (State Equation)

  • xt is the state vector containing the terms of interest for the system (e.g., position, velocity, heading) at time t
  • ut is the vector containing any control inputs (steering angle, throttle setting, braking force)
  • Ft is the state transition matrix which applies the effect of each system state parameter at time t-1 on the system state at time t (e.g., the position and velocity at time t-1 both affect the position at time t)
  • Bt is the control input matrix which applies the effect of each control input parameter in the vector ut on the state vector (e.g., applies the effect of the throttle setting on the system velocity and position)
  • w(t) is the vector containing the process noise terms (unknown) for each parameter in the state vector. The process noise is assumed to be drawn from a zero mean multivariate normal distribution with covariance given by the covariance matrix Q(t ).

  1. Measurement model (measurement equation)

  • zt is the vector of measurements
  • Ht is the transformation matrix that maps the state vector parameters into the measurement domain
  • vt is the vector containing the measurement noise terms (known) for each observation in the measurement vector. Like the process noise, the measurement noise is assumed to be zero mean Gaussian white noise with covariance Rt.

For a simpler example let’s consider a scenario of a car, moving on X- axis with a constant acceleration (a). Suppose car emits its X coordinate periodically. But due to the measurement noises, the measurement can be vary from the actual location.

State vector contains the location and the velocity of the car over the X axis.

Using motion equations,

Now this is the state equation in matrix form using 1 and 2,

Suppose we are reading speed and the location and the speed with white measurement noises. This is the measurement model in matrix form.

With 3 and 4, we can estimate the states of the machine. If you are using a Kalman implementation library, it will do the rest of the calculation given 3 and 4 models. i.e Apache Commons Math Kalman Filter implementation.

Kalman Filter equations

Kalman Filter maintains the estimates of the state and the error covariance matrix of the state estimation.

Notations:

  • X(t|t) — Estimate of x(t) given measurements z(t) and z (t-1),….
  • X(t+1|t) — Estimate of x(t+1) given measurements z(t) and z (t-1),…
  • P(t|t) — Covariance of X(t) given z(t), z(t-1),…
  • P(t+1|t) — Covariance of X(t+1) given z(t), z(t-1),…

State Estimation

Known are x(t|t), u(t ), P(t|t) and the new measurement z(t+1).

Time Update

  1. State Prediction x(t +1|t )= F(t ) x(t|t) + G(t ) u(t )
  2. Measurement Prediction: z(t+1|t)= H(t)x(t+1|t )

Measurement Update

  1. Measurement Residual: w(t+1)= z(t+1) — z(t+1|t)
  2. Updated State Estimate: x(t+1|t+1)= x(t+1|t) +W(t+1)w(t+1)

Where W(t+1) is called Kalman Gain in state covariance estimation.

State covariance Estimation

  1. State prediction covariance: P(t +1|t ) = F(t)P(t|t )F(t )’+Q(t )
  2. Measurement prediction covariance: S(t +1) = H(t +1)P(t +1|t)H(t +1)’+R(t +1)
  3. Filter Gain: W(t +1) = P(t +1|t )H(t +1)’ S(t +1)-1
  4. Updated state covariance: P(t +1|t +1) = P(t +1|t ) — W(t +1)S(t +1)W(t +1)’

Hopefully, I’ll cover the implementation of a Kalman filter using Apache Math library in my next post!

Cheers!

Using Hg Mercurial behind a proxy

You might have faced to download gigabytes of repositories with Hg. In my case, a big portion of Mozilla repositories depends on it and wanted to download that huge repos from the university network. University bandwidths are mostly underused 😉

Hg uses hgrc file to load configurations. (Per repository) You can go to your repository, .hg/hgrc and add following with your configurations.

[http_proxy]
host = your.proxy.host:8000
passwd = password
user = username

In case you are using hg from a preloaded instance to clone repositories to another location, you can simply add your configurations as a prefix to your command.

hg --config http_proxy.host=[proxy_ip]:[proxy_port] --config http_proxy.user=[username] --config http_proxy.passwd=[password] push

Make sure if you have special characters(@,%,,.) in your username or password you use the suitable character representation for it. ie : use %40 instead of @ symbol. This will also help in finding special character representation.

Cheers!

 

IEEEXtreme – The Most Awaited Coding Competition

Xtreme

Register at IEEE UoM for Proctors

Visit IEEEUoM

IEEEXtreme is a global challenge in which teams of IEEE Student members, supported by an IEEE Student Branch, advised and proctored by an IEEE senior member, compete in a 24-hour time span against each other to solve a set of programming problems. The competition made its first appearance in 2007. The Institute of Electrical and Electronic Engineers (IEEE) is the pioneer behind organizing this colossal event.

[embedyt]https://www.youtube.com/watch?v=aNTAOCvfk0Y&width=400&height=250[/embedyt]

The Institute of Electrical and Electronic Engineers, which celebrates the 130th anniversary this year is the world’s largest professional organization for advancement of science and technology with around 400,000 IEEE members in over 160 countries around the world. It is the leading authority in many disciplines of engineering including Electronic Engineering, Electrical Engineering and Computer Science & Engineering. There are around 1900 IEEE student branches in 80 countries, across 5 continents in the world.

How Will It Happen..?

IEEEXtreme is organized globally by IEEE (Institute of Electrical and Electronic Engineers) supported by local student branches to host it within local universities.

IEEEXtreme in University of Moratuwa will be organized by IEEE Student Branch of University of Moratuwa within the university premises, gearing up everything including logistics, foods and beverages for coding students to take up challenges and hoist the flag of the university on the top of the ranking board.

The competition will start on 18th October at 05.30 am and end at 05.30 am on the following day, parallel to international event. Students will be given 15 – 20 toughest algorithmic questions issued periodically by the IEEEXtreme global committee. Students will submit the answers on the coding platform provided by IEEE.

IEEE student branch of University of Moratuwa has the responsibility of providing food and beverages and other needs of coding students to place the university on top of the rankings.

We are that close…

IEEE Student branch of University of Moratuwa have been the most consistent student branch of IEEEXtreme programming competition ever since the first time of its appearance in IEEEXtreme 3.0 – 2009 in which they became the global champions. Since then UoM has dominated the competition by producing top ranked teams in large numbers.

 

Year

Best performances

2009 Xtreme 3.0

Global champions

2010 Xtreme 4.0

Rank 11

2011 Xtreme 5.0

Rank 2

2012 Xtreme 6.0

Rank 3 (10 teams in top 100)

2013 Xtreme 7.0

Rank 12 (7 teams in top 100)

 

Apart from the results, IEEE Student Branch of University of Moratuwa is among the largest student branches in the world and the largest student branch in Sri Lanka, exceeding 400+ member base. Also, it is at the forefront of the student branches of largest number of IEEEXtreme participants.

The Grand Prize

The grand prize to the winning team from IEEE headquarters is a trip to any IEEE conference at anywhere in the world, that the team would like to participate in plus the ultimate glory.

From Previous Glory…

10424976_819098498124333_4243584617661961634_n

And we believe it’s time to bring the glory back to University of Moratuwa…

Wanna hear more..? Drop a mail to infoATieeeuomDOTnet

End of the SoC, but the passion remains the same

That was a great period to remember for a life time. Reading, Coding, again reading, refactoring, some annoying issues (things get really annoyed when you update the local repository during a bustage 😉 but still there was a lot of things to learn), getting reviews from experts..!!

I really enjoyed the SoC and hoping to continue contributing to internet giant Mozilla. There are few knits I still have to fix on patches and will be working on them in future as well. I got to know that fake server was something important to calendar so I will be focusing more into it and then fixing other proposed issues which were left behind due to sudden intrusion of the fake server.

Variations from the proposed deliverables as I decided with Mohit:

  • Week 3: Patch for schedule-calendar-transp
    Dropped since it requires some UI related changes
  • Week 4 – Week 6: Patch for If-Schedule-Tag and If-Schedule-Tag-Match
    Patch is done, needs to be made reviewable & handle edge cases
  • Week 6- Week 7: Patch for schedule-default-calendar-url
    No need to implement in lightning since this is more of a property that will allow clients to manage calendar collections for one user. More suited to a dedicated client for a particular server.
  • Week 7- Week 8: Patch for min/max date-time
    That is something related to the server, and is not returned in a PROPFIND request.
  • Week 8- Week 9: Patch for max-attendees per instance
    UI Changes required
  • Week 10 – Week 12: Unit tests for schedule-tag
    On track, this evolved into a major chunk of the project, with the fake server implementation and its design to support overriding, a rough working patch is completed, a more robust implementation in the works.
  • Week 12- Week 14: Mozmill tests for invitation scenarios
    This has been completed. Just some minor cleanup required with the packaged test thing.
  • Week 14- Week 15: Patch for schedule-force-send
    Needs UI change became less of a priority.

On the way, fake server became something that took a long time since it was a RFC implementation rather than a modification.

Throughout the GSoC period I received a great mentoring from Mohit, so herewith I’d like to give my gratitude to him for all the time he allocated and being cool throughout the period. Also, to Philipp for all the tech reviews. Without them I’d never caught up the complex things in the codebase.

Fun Facts :

Well, If you are going to contribute to Mozilla TB or Lightning by any chance lol, you should probably know these two abbreviations. You can’t find them in Google anyway.

m-c and c-c : I drove into trouble several times by hearing to update m-c and c-c. I was thinking that is something related to changset headers and hashes. well at last got to know, they weren’t. Those were the two folders named “mozilla-central” and “comm-central” in the repository.

PS: I searched in google for the term “c-c and m-c revisioning” and got the result “Women’s Choices Within Market Constraints: Re-Visioning” 😉

I will update the blog with my future works related to Lightning as well.

Cheers!

CodeExpertz | An online coding workshop for school students

CodeExpertz 1.0 was an online school programming competition held exclusively for the students of Sri Lankan schools.

Dare enough? Visit CodeExpertz at Codechef!

As the prime technological institution of Sri Lanka, we had taken the initial step to provide a platform for them to showcase their hidden talents and improve their skills in the field of computer programming. This was a new avenue for the students to get the exposure to the real world technology matters at a very young age which we at IEEE Student Branch of University of Moratuwa (IEEE SB UoM), consider as a great privilege. This was held on the 28th of September 2013 from 9.00 am to 6.00 pm at the University premises with the participation of more than 40 teams.

Question team - Lihini, Madawa and Me

The competition was created to

• Motivate school students to be technologically sound in solving real world problems, especially using computer programming

• To provide students an online competitive environment to investigate their talents in programming

• Give IEEE Student Members a challenge to embrace team work – an important skill to develop for career success

Students, who are currently studying in a school especially in Ordinary Level and Advanced Level classes and students just finished their advanced level examinations, were eligible to take part in this competition.

1379468_641075742593277_749355566_n

Organizing this type of a novel event required a lot of commitment, dedication and considerable attention towards many aspects. Student branch members were so passionate about working on a project which involved the development of the skills of students, the future of our country.

Prior to the competition, a series of workshops were conducted to provide the awareness about programming and the competition. These workshops were held in selected schools and institutions all over the country as well as at the University of Moratuwa premises. These were conducted by our high caliber undergraduates representing the technical committee of this event. All of them are members of the IEEE Student Branch of University of Moratuwa. We were able to witness the enthusiasm of the students towards this competition and we were more than happy to receive encouraging feedback regarding these workshops.

1237523_10201494525957127_1266790881_n

Me, the Sir. 😛

The standard of the knowledge level of the competitors were truly amazing and that made the competition more excited as the time passed. After an intense competition, the team ‘RCCoders’ from Royal College, Colombo won the championship while the team ‘The EE Crew’ from Nalanda College, Colombo and the team ‘Pulverizes’ from Rahula College, Matara became the 1st and 2nd runners up respectively. The team which won the first place comprised of following students; Chamath Palihawadana, Roshnal Lihinikadu and Sanila Vindula Jinendrasinghe. The award ceremony was held during the IEEE Day 2013.

1380275_641075732593278_205302464_n

This cutting-edge competition was praised by many people including the Principals, teachers and the students as well. They are eager to participate in these kinds of events each year and we are hoping to retain the momentum till this year’s competition. This unique experience had made most of them realized about their hidden skills which they can improve in the future. We were extremely glad to partnership with Dialog IdeaMart and we had Digit.lk as the online media partner who supported us in hosting our event throughout the entire procedure of the competition.

Digit.lk was our online media sponsor. Dig-It!

 

AT commands and Interfacing a PIC microcontroller with a GSM module

AT commands are a list of commands that you can use to communicate with any kind of a mobile phone or a GSM module serially. First you have to identify the GSM module and it’s own AT commands list first. In a case that you don’t have a GSM module, you can use a basic mobile phone connected to the pc as a gsm module. (note it’s not working stand alone, always with the PC)

After connecting the mobile/GSM module to the PC via serial or USB try to communicate with it with using a hyper terminal(win XP) or Putty client(any OS). Download putty from here. 

http://www.youtube.com/watch?v=Nvf_QBez8w0

Same way find the serial port of the GSM module and try to communicate.

There are various at commands to select sms mode, dial a number, Bluetooth(mobiles with bluetooth), access sim memory and all operations.

Ex: ATD 0711234567;

//dials the number

ATH

Hang the phone

Note : if you are using a mobile phone, there’s a big possibility of it’s not supporting the text mode but the PDU mode.  To check the format it supports, type AT+CMGF=? in the terminal. If the device returns “0” it supports only the pdu mode. That implies you can’t send a text as it’s but need to convert into PDU format.

If it returns 1 or 0,1 it says it supports text mode and both respectively.

Interfacing with the IC

After you are done with your mobile/gsm module and understand the AT commands, use ISIS to simulate the circuit.

AT commands can be issued to the device via HSEROUT/TX pin of the IC. And will be received by the RX pin of the device. (Module or the phone. If it’s a micro usb phone, u don’t need to worry about the TX,RX of the device)

To output a command to the device using hardware serial port of the PIC,

hserout [“ATD 711234567;”,13,10];

//13 : carriage return , 10: new line character

Home Automation with Android | University Level 1 Project

This project was carried out during level 1 of our university life. – Gained an A+ too 🙂

We were totally new to Android, micro-controller programming and I didn’t know the ABC of AT commands at all. At times the project was seemed unachievable. All we knew at the beginning was, we need to control some electronic components with a mobile phone. We went through all type of connection establishing protocols we could done using a mobile phone to the micro controller. We went through bluetooth, internet but couldn’t see a way to receive the message from the micro-controller.

Finally found AT commands that allows to control a mobile with serial communication.

We used a PIC 16f877A at the receiving end along with a mobile phone. Micro-controller was programmed to issue AT commands and used my computer running with a ISIS program as an interrogator to the mobile phone.  Capture

Then we moved to a GSM module which could be directly connected with the PIC.

Once the GSM module received a SMS, the PIC reads it using AT commands and it could take the defined action for the particular message.

Next…
AT commands