<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Percy Jaiswal on Medium]]></title>
        <description><![CDATA[Stories by Percy Jaiswal on Medium]]></description>
        <link>https://medium.com/@percy.jaiswal?source=rss-6173b8e69840------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*8C2meCn8xWNfsQCNol7cJg.jpeg</url>
            <title>Stories by Percy Jaiswal on Medium</title>
            <link>https://medium.com/@percy.jaiswal?source=rss-6173b8e69840------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 06:33:20 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@percy.jaiswal/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[V for Voltage!]]></title>
            <link>https://medium.com/hackernoon/v-for-voltage-b5fd8a63e0dd?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/b5fd8a63e0dd</guid>
            <category><![CDATA[electron]]></category>
            <category><![CDATA[electronics-engineering]]></category>
            <category><![CDATA[electronics]]></category>
            <category><![CDATA[electrical-engineering]]></category>
            <category><![CDATA[physics]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Thu, 27 Aug 2020 01:19:06 GMT</pubDate>
            <atom:updated>2020-08-27T01:19:06.917Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*XqDK15CaxkTnIwChJgZyRw.png" /><figcaption>Image created by author using Matplotlib</figcaption></figure><p>We always see voltage specifications mentioned almost on every electrical gadget. Whether it be some development board, mobile / tablet/laptop charging adapter down to every single IC which gets used in electronic circuitry. But do we really understand what exactly those voltage ratings are telling us? Today in this article, we will try to understand it’s meaning. Starting from the most basic element, an Atom, we will build our understanding intuitively to understand what does a voltage means conceptually. So let’s get started!</p><p><strong>The Atom</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bzKHoQmlpvP05BXTkeervA.gif" /><figcaption>Charged Particles in an Atom</figcaption></figure><p>Everything that you see around you is made of different kinds of elements. An element is defined as the substance which cannot be broken down further by chemical activity. And Atom is the smallest particle of an element. Each Atom consists of a nucleus that contains Neutrons, which does not contain any charge, and Protons which are positively charged. To balance these positively charged protons and to make an Atom electrically neutral there are negatively charged electrons revolving around this nucleus. And this is where we get first introduced to charged particles, a Proton — a positively charged particle and an Electron — a negatively charged particle.<br>So what happens when you take one of this charged particle and keep it in space?</p><p><strong>Electric Field and Electric Force<br></strong>As we saw in the above Atom structure, the negative and positive charges balance each other. Hypothetically speaking, if you removed a negative and a positive charge from the atom and kept them in space close to each other, they will start to attract and move toward each other. Similarly, if we keep two charges of the same polarity (either positive or negative) close to each other, they will start to repel each other. But how does this work exactly, there is no physical medium present between two charges, then how do they pull or push each other? This behavior is exactly the same as what we see when two magnets come close to each other. As we know, if we try to bring two magnetic south poles close to each other, they will exert a repelling force. And as in the case of electric charges, if we bring opposite magnetic poles close to each other, they will start to attract.<br>This phenomenon can be explained by the concept of the Electric field. It states that whenever you have an electric charge in space, it starts to radiate lines of electric fields in all directions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-a0ALcqYNjSFHtBdZ6Vc_g.gif" /><figcaption>A Charged Particle will radiate Electric Field</figcaption></figure><p>However, we cannot measure or experience this Electric Field directly. The only way to measure it or to know about its existence is by observing the force this Electrical Field will (let’s call our first charge as q1) exert if a second charge (call it q2) is brought in its proximity. q1 will either attract or repel q2, based on their polarities, and this is how we see the effect of q1’s Electric Field.</p><p>An obvious question that will come to your mind is that won’t q2 behave the same way and exert forces on q1? And you are exactly right, it will totally do that. So to make our understanding and visualizations easy, from now on, we will assume that q1 consists of many more number of charges (all of same polarity) than q2. Imagine this same as q1 being a much bigger magnet than q2. In such a case, the attracting or repelling force exerted by q2 on q1 will be very negligible and it will only be q2 which will either move towards or away from q1.</p><p>Now that we establish presence of the Electric field, we can start talking about Electric Force. Think about it like this, you can keep a magnet in your hand and carry it around all day and you will not feel any magnetic field or force coming out it. But as soon as some other magnetic material comes in the vicinity of the magnet in your hand, you will experience magnet exerting some kind of force on a new object. Whether the force will be attracting or repelling other object depends upon the polarity of both objects. Similarly, a single charge alone will not be exerting any force on anything. It’s only when a new charge is brought near its vicinity, will it start exerting Electric force on it. The direction of the force will depend on polarity of charges and its magnitude will depend on the distance between them. Going back to the magnet for the magnitude of the force, we know that as two magnets get close to each other, they start exerting more force. The same goes for electric charges too.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d3W8JuoW0KkT496mNCfGEA.gif" /><figcaption>q2 will experience Electric Force because of Electric Field generated by q1</figcaption></figure><p><strong>A little bit of Maths<br></strong>Without delving into maths too much, let’s try to mathematically relate Electric Force to Electric Field. As I said before, it’s difficult to directly measure how much Electric field is present, what we can measure however is how much Electric Force does a unit charge experiences when it comes in the vicinity of an Electric Field. And that is exactly how we calculate Electric Field.<br> Electric Field (E) is Electric Force (F) experienced per unit of charge<br> E = Electric Force / Total q2 charge — — — — (1)<br>Taking a small example. Let’s say you have a test charge of 3 Coulomb, and this test charge is experiencing an Electric Force of 6 Newton at a certain location. We can calculate Electric Field at this location as 6 Newton / 3 Coulomb = 2 Newton / Coulomb.</p><p>One point I will like to say about mathematical formulas, especially for my articles, is that you don’t need to memorize or remember them. But they help us see and cement the relationship between two quantities. E.g. we have been talking about q1 and q2, Electric Field and Electric Force between them so far. A mathematical formula binding them together acts as a good reference point to totally understand the relationship. One other thing I like math formulas is that we can verify the authenticity of any formula by verifying the units of different parameters used in the formula and whether left and right-hand side units are equal or not. I will show an example of what I mean by this a little later in this article.</p><p>Summarizing this section: We saw that electric charges radiate Electric Field in space and that Electric Field exerts an Electric Force on other charged particles.</p><p><strong>Electric Potential Energy and Voltage<br></strong>We saw in the previous section that we had some charge q1 (relatively bigger) emitting electric field and a test charge q2 was drifting into this region of Electric field generated by q1. And while q2 is drifting towards q1, it started experiencing an Electric Force. For q2 to keep moving towards q1 (or even just to maintain its position and avoid getting repelled away), q2 needs to perform some work. After all, if you ever want to get from one place to another, you need to do some work. If you want to move an object in your day to day life from one place to another, you have to perform some work to move it. And it is the same in the world of electronics too, for the charge q2 to move from position let’s say point A to point B, some work has to be done. And this work is measured by standard work formula, <br> Work = Force x Distance<br> = (Electric Field x charge) x Distance — — from (1)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*eOOCeeJl3rVrMchmafRYdw.gif" /><figcaption>Work (W) is performed on q2</figcaption></figure><p>Continuing our numerical example, let’s say our 3 Coulomb charge q2 was moved by a distance of 2 meters from point A to point B against the direction of Electric Field generated by q1. Taking Electric Field value of 2 Newton / Coulomb from the previous example, we can calculate total work required to move q2 from point A to point B as<br>Work (W)= (Electrical Field x Charge) X Distance<br> = (2 Newton / Coulomb x 3 Coulomb) x 2 meters<br> = 12 Newton meters</p><p>So the work that was required to move q2 (3 Coulomb) a distance of 2 meters was 12 Newton meters = 12 Joules. The definition of unit Joule is Newton meter. In other words, 1 Joule = 1 Newton meter. <br> One small thing to remember in any physics equation is that work = energy. Often I used to get confused when these two terms were used interchangeably, especially in different resources. But just remember, work is the same as energy and this is proved by the fact that both are measured by unit Joules.</p><p>To say the above statement in terms of energy we can say that the energy of q2 (it will be potential energy as it is stationary) at point B is 12 Joules higher than at point A. This is equivalent to saying that the potential energy of a rock at 5 meters of height is higher than its potential energy at ground level. This can be understood intuitively by two ways. 1st is to realize that you had to do some work (spent your energy) in getting this rock up to a height of 5 meters. And as we know that energy just gets converted to other forms, the work you have done in getting this rock to 5 meters of height has got converted into this new potential energy of the rock. Secondly, now that this rock is at a height of 5 meters, it has the potential to do some work or damage. If you drop it from this height, it’s potential energy can be used to perform some other work.<br>So without getting off the topic too much, we see that energy of q2 at point B is 12 Joules higher than it’s energy at point A.</p><p>Now, this is the most tricky part of this lesson. <strong>So what is Voltage?<br></strong>Recap: We know a charge emits electrical field, we understood that if some other charge comes in its vicinity, the charge q2 will experience an Electric Force F. We then saw that to move (or even to keep it at its place) against the direction of this electric Force F, we have to perform some work on q2, let’s say W Joules. And then we clarified that Work is equal to Energy.</p><p>Now the Voltage is nothing but work done per unit charge! In the above equation, we saw that 12 Joules of energy was required to move q2 from point A to point B (sorry for the repetition, but it’s very critical to understand the sequence). So as per our definition, the voltage difference between point B and point A is the work done per unit charge to move from point A to point B. If total work for 3 Coulomb (q2) charge was 12 Joules, we can get work done per unit charge by simply dividing W by q2. <br>Voltage V = Work (Energy) / Total Charge q2. — — — (2)</p><p>Continuing our numerical example and using above formula, we can say tat voltage difference between point A and point B is equal to 12 Joules / 3 Coulomb = 4 Joules / Coulomb = 4 Volts.</p><p>We can confirm the validity of above equation by looking at the units. We know the unit of Voltage is Volts, we see that all the time mentioned on all energy sources, whether it be our USB mobile chargers (5V) or clock battery cells (1.5V). The right-hand side of the above equation is Joules / Coulomb, which again is the definition of Volts (<a href="https://en.wikipedia.org/wiki/Volt">Wikipedia link</a>)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*kfrqmcfjXPQrahIXPbxH_w.jpeg" /><figcaption>Image Source Sparkfun</figcaption></figure><p><strong>Battery example<br></strong>This difference between Energy and Voltage will get more clear if we consider an example of a battery. We know that every battery has a positive and negative terminal. Let’s take an example of a 3.7V battery show in the picture. We see that the battery manufacturer is telling us that the Voltage difference at this battery terminal is 3.7V Volts and that it has 850 mAh (mili-Amp Hour) capacity. I will not bore you with more maths, but Joules in energy = mAh * Voltage, so this battery has 850mAh * 3.7V = 11,322 Joules of energy.<br>In other words, the manufacturer is telling you that he had to perform a work of 3.7 Volts of work to bring each charge from the negative terminal to the positive terminal of the battery. And he had to move 11,322 J / 3.7 V (using equation 2) = 3,060 number of such charges to provide 11,322 Joules or 850 mAh of energy in this battery.</p><p>And with that, it’s a wrap. Now you know what exactly those voltage ratings on all your charging adapters and batteries mean. So next time you read a voltage specification, remember that this is a note from the vendor telling you how much work he had to do <strong>per unit charge</strong> to move that unit charge from negative terminal of battery/adapter to its positive terminal!</p><p>Hope you have enjoyed reading this article, till next time….cheers!! :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b5fd8a63e0dd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/v-for-voltage-b5fd8a63e0dd">V for Voltage!</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Use Python to create Altium Database Library]]></title>
            <link>https://becominghuman.ai/use-python-to-create-altium-database-library-2b2af975f9af?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/2b2af975f9af</guid>
            <category><![CDATA[python]]></category>
            <category><![CDATA[altiumdesigner]]></category>
            <category><![CDATA[altium]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[selenium]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Mon, 27 Jul 2020 14:24:14 GMT</pubDate>
            <atom:updated>2020-07-27T14:24:14.978Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/680/1*t8_w0Z6buyUPld00fO6U4Q.jpeg" /></figure><p>A telltale story of how I created an Altium Database library for our company with the help of Python programming.</p><p><strong>How it started<br></strong>Recently I had started a couple of small projects in our company. And while I was designing schematic and PCBs in Altium, there was a thing that was bothering me. As in most of the projects, most of the components in my projects were getting reused from our existing design. However, in order to use those components, I was having to recall which projects might have used the part which I was needing for my project, open its Altium project, copy the schematic symbol and footprint for the component from existing project’s library files, copy them in my new project’s library file and finally link newly pasted schematic symbol to PCB footprint. This in itself was annoying, but there were couple more things which were bothering me.<br>For cookie-cutter parts like SMD resistor and capacitors, we would be using a generic schematic symbol in schematic and assign one of the standard footprints we had created for them and then update value and company and manufacturer part number details. This was also time-consuming and error-prone as sometimes I would miss updating some of the details.<br>And thirdly, while in the middle of my new projects, we found out that one of the footprints we were using for an existing project was a little incorrect. It was for an oscillator component and there was a chance that one of the alternate parts we were using would not fit into our footprint. For this, I basically had to do the reverse process of what I had described earlier. I had created a new footprint for my project and had to update the existing project’s PCB library.<br>All these things finally lead me to start exploring about creating a centralized library for all EEs in our company. Incidentally, at the same time, I came across a presentation from Robert Feranec at Altium live (you can watch it <a href="https://youtu.be/6oRSN_CvoWA">here</a>) in which he presented his survey about how libraries are maintained in different organizations. While there are lots of interesting things presented in the speech, the one thing which stood out to me was, as per Robert’s study, in almost all the companies it was always an initiative by one or two individual engineers which has led to the creation of centralized libraries. Someone starts by creating a library, presents it to the group and once the group and management see that it’s already in motion, then everyone starts using and contributing to it. And I knew it then and there itself that this is what was required for our company too. Something to get started with and then it will pick up the pace by itself. And hence, I decided to start creating an Altium component library for all the Electronic parts which were used by our company.</p><p><strong>Step 1: Get all Company level part numbers<br></strong>Most of the companies have their own part number system where the same parts (drop-in replacement to each other) are given just one company level part number. E.g. all 0402 1KOhms 0.1W, 5% resistor will have the same xxx company part number. Luckily for me, our company had an excel file containing all the company level part numbers that are used by engineering, and that was all I needed to get started.<br>Result: Got all company level part numbers in an excel file.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/241/1*mZltuGEmvKFlBcHUFNdh1g.png" /><figcaption>Example of (dummy) company level part numbers.</figcaption></figure><p><strong>Step 2: Get actual vendor details from company part numbers.<br></strong>Our company uses an Oracle system to store all documentation. My next challenge was to get the actual manufacturer name and part numbers from our Oracle system for every part. This is where I started using Python. I specifically used pyautogui and openpyxl libraries. I didn’t automate from A to Z, as this was just for my one-time personal use and it was easier to click one button to open the tool once rather than write 10 lines of Python code. So, I opened our Oracle tool and ran a few lines of codes that will automate mouse movement and clicks. Unfortunately, as I couldn’t show you screenshots of our tool, I created a small gif using powerpoint to show the steps involved in getting vendor details from the tool.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*kjHaSKLRNr8hTCfdk9L2kA.gif" /><figcaption>Example steps to get vendor details from company tool</figcaption></figure><p>Steps shown in the above gif can be coded in python with the help of pyautogui as will be explained below. But before we start to code, there is one thing which we need to know, and that is how to find the location of a particular element, like a button (Find Vendor details, Search and Close), text box, etc. on our PC screen. We can do that by just using a single line of code available in pyautogui, which is pyautogui.position(). Just place your mouse pointer on top of the button or text box whose location you want to find and run pyautogui.position() in your python terminal. For more information on how to use pyautogui, refer to their documentation <a href="https://pyautogui.readthedocs.io/en/latest/">here</a>.</p><h3>Trending AI Articles:</h3><blockquote><a href="https://becominghuman.ai/natural-language-generation-the-commercial-state-of-the-art-in-2020-3b671fa3ebc">1. Natural Language Generation:<br>The Commercial State of the Art in 2020</a></blockquote><blockquote><a href="https://becominghuman.ai/this-entire-article-was-written-by-open-ais-gpt2-adec829fe6bc">2. This Entire Article Was Written by Open AI’s GPT2</a></blockquote><blockquote><a href="https://becominghuman.ai/learning-to-classify-images-without-labels-43655a1cb4c7">3. Learning To Classify Images Without Labels</a></blockquote><blockquote><a href="https://becominghuman.ai/becoming-a-data-scientist-data-analyst-financial-analyst-and-research-analyst-d9ec01a9d11d">4. Becoming a Data Scientist, Data Analyst, Financial Analyst and Research Analyst</a></blockquote><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/99f09626fd6d176db4afdf55d0682e16/href">https://medium.com/media/99f09626fd6d176db4afdf55d0682e16/href</a></iframe><p>And there I had it, an excel file with all company part numbers with corresponding vendor details. Well, as you could have imagined, not all parts had valid vendor details, and many of the parts were actually just internal documents or some mechanical components. As with any <a href="http://becominghuman.ai/">data engineering</a> kind of job, I had to do clean up the data as we will see below.<br>Result: I had a file with the manufacturer name and part number updated against company part numbers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*qi7RR8TDP4933c0OhFhaUw.png" /></figure><p><strong>Step 3: Remove internal document parts<br></strong>Part numbers which were our internal documents (like row# 11 in the above screenshot) had our company’s part number itself in ‘Mfr Name’ field mentioned in the above step. So it was easy to filter them out. I just search for parts that had our company part number itself in vendor name and marked it with “Internal part / Document.” I used a script similar to that given below to get this result.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/39e6836cb19d8119f2e3c333c6c661df/href">https://medium.com/media/39e6836cb19d8119f2e3c333c6c661df/href</a></iframe><p>Result: Internal parts / Documents identified.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*ioZArbu25wXjDfl8_uUcgA.png" /></figure><p><strong>Step 4: Identify the component type.<br></strong>I wanted to organize our database according to the type of components. This would allow engineers to search for a component from the database using its type and value. So as the first step for that, I had to go through each vendor part number, search for the component in Digikey and mark its type. In order to use a web browser (and Digikey website), we will be using webdriver module from selenium library in Python. You can learn more about this library <a href="https://selenium-python.readthedocs.io/">here</a><br>The most important part in order to surf through a website using selenium is to find the ‘path’ of the element (again, like button, text box, etc.) on a webpage. It’s very much similar to how we had to find x, y location of button, etc. in the above section. There are multiple ways to find location/path of an element, one among them is to use something called ‘XPath’.<br>You can see the process of using XPath to find an element on a webpage in below couple of gifs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*gQ_8gpdvXd02MlvzneqXDA.gif" /><figcaption>XPath of Search Bar in Digikey</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*EpNIZnjp9RtoWcrXLJ8g_A.gif" /><figcaption>XPath of Search Button in Digikey</figcaption></figure><p>Coming to the coding part, first I go to Digikey, search for the ‘search’ bar using it’s XPath, paste the manufacturer part number from my Company_Database excel file, and press enter. After waiting for a couple of seconds to allow the page to load, I would extract the type of component from the following field in the Digikey page. While looking for the best way to find the type of component, I had decided it would be best for me to use the classification used by Digikey itself, rather than me trying to decipher it from the part description. After a few long stares at Digikey pages for various components, I observed that Digikey will identify a component in the hierarchy of three levels. The Below picture shows how a Capacitor, Resistor, Crystal, and a Diode will be categorized in Digikey.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/565/1*7XBxbz0RFStnvBRfwzu71g.png" /><figcaption>Digikey’s product classification example</figcaption></figure><p>Once I saw this, then it was easy, I again ran through all parts (this time excluding parts marked as “Internal parts / Documents” and copied the third entry in the above-shown product categorization.<br>Result: All components now have a ‘Component Type’ associated with them.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*Neue4GvpFmxxqBIaVvdLng.png" /></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/129cf4a29c32af1a3f40eb02366bb887/href">https://medium.com/media/129cf4a29c32af1a3f40eb02366bb887/href</a></iframe><p><strong>Step 5: Get one Key parameter for each component.<br></strong>After identifying the type of components, I wanted to know it’s principle value, like resistance for a resistor, capacitance for a capacitor, oscillating freq for the crystal, and so on and so forth. Again, this was an exercise in going through a few parts of each type and finding where can I find the value of its key parameter along with the footprint. Key-value and Footprint were the two parameters that I wanted to include in the database library to help to sort out the components. I first of all sorted the Company_Database excel file with “Component Type”, then manually decided which parameter I want to use for each type of component.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*dqmPAIvlEpsHByPBiLd_Bw.png" /><figcaption>Parameter Type identified for each component</figcaption></figure><p>Once I knew which parameter I want to get from Digikey for every type of component, I wrote the function shown below to get the respective value and Footprint for the components. As you can see in the below function, first we check what type of component it is. And then depending on the type of component, I take values from two of its parameters from Digikey using their XPath. Below are a couple of screenshots that show examples of where to get the value and footprint for Resistor and Capacitor type of components.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*aXvSGOAa2UgvF62mo1fMQw.png" /><figcaption>Resistance Value and Footprint for a Resistor</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*T_Sy6-heoR6aou1fcbC5pw.png" /><figcaption>Capacitance Value and Footprint for a Capacitor</figcaption></figure><p>With this, the majority of electronics components in our database got sorted out according to their type, value, and footprint. Whatever little were reaming, I updated their values and footprint manually. These components were one-off types like Buzzer, Cable Ferrite, displays, and so on.<br>Result: All valid part numbers have a type, value, and a footprint associated with it.</p><figure><a href="https://aijobsboard.com/?fbclid=IwAR0GcsLs8A6CFM-fynrZMM3sTgo_Zpbto2CjglJm0Dmi6otC6YWc7CDFpQk"><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dAlwXfVrtYspdCzmC8iADw.png" /></a><figcaption>Machine Learning Jobs</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*ucvOcRcUu-Aoggv3qC4ysQ.png" /><figcaption>Company parts with their value and footprint updated</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06fcbd683f396ccc9ffb5f79a499f0a3/href">https://medium.com/media/06fcbd683f396ccc9ffb5f79a499f0a3/href</a></iframe><p><strong>Step 6: Components Not Found in Digikey.<br></strong>After the above step, there were few components for which its type, and hence its value and footprint could not be obtained from the script. This was happening because of the following three scenarios.<br>a) Component not found in Digkey. In this case, it was obvious for it to be not categorized.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*xK7V2-lShXBbgLHDLbyjxQ.png" /></figure><p>b) In some cases, there was an exact manufacturer part number provided in our <a href="http://a tirinha nova esta no ar">database</a> and hence Digikey will directly take me to a single product page like this. As the location (XPath) of component’s type, value and footprint will be different in this kind of page than the ones shown in above steps, the script was not able to identify components which had a complete part number.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*inkbDPewOA99n8a7KO_olw.png" /></figure><p>c) Partial part number components, for which Digikey had multiple types of products with a same part number like shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*u_IV0uL3BgCCZ0GPdZN8QA.png" /></figure><p>Take note that categories ‘a’ and ‘c’ are different. In ‘a’ Digikey is sure that it doesn’t have any part matching our part number, whereas in ‘c’ it could find multiple options. As there were a relatively lesser number of components left combined in ‘a’, ‘b’, and ‘c’ categories, I decided to update details for them manually. For ‘a’ and ‘c’, the script would have been too much complicated for the scope of this project. And for ‘b’, there were just not enough components left. Even if there were 10 components of the same type with scenario ‘b’, I would have started writing function similar to the one in step 5. The only difference in this new function would be the XPath of the element from where I would be getting component details.</p><p><strong>Step 7: Company_Database Excel File Structure<br></strong>Before I get into the next section of getting Schematic Symbol and Footprint details for components from existing Altium projects. I would like to show all the columns I planned to have in the Company_Database excel file. These are slightly bit different from the example screenshot I have been sharing with you before. E.g. in my actual Company_Database excel file, I have columns for second manufacturer details along with Column G for ‘Owner’ of the part. I had derived this additional info from our internal repository tool.<br>They are not arranged in the best order, as I have seen that when I import this excel file in Altium, the columns would get rearranged and I would anyways need to arrange them in Altium. The second reason for why my columns were in such an order was because of the sequence in which I was populating this file. In step# 1 when I first got all company part numbers, they obviously got populated in Column A. In step# 2 where we got manufacture details from the internal database system, I was retrieving them in the order of categories entered in Column B to H.<br>Column A — Company Part Number<br>Column B — Manufacturer Name<br>Column C — Manufacturer Part Number<br>Column D — Manufacturer 2 Name<br>Column E — Manufacturer 2 Part Number<br>Column F — Company Description<br>Column G — Owner (Engineer who had created this company part number)<br>Column H — Date (G &amp; H were coming from internal database system. Thought no harm in having them)<br>Column I — Project (Will be updated in later steps)<br>Column J — Component Type (As updated by script in step 4)<br>Column K — Parameter Type (As updated by script in step 5)<br>Column L — Parameter Value (As updated by script in step 5)<br>Column M — Footprint (As updated by script in step 5)<br>Column N — Library Path (Altium Schematic Library path)<br>Column O — Library Ref (Altium Schematic Symbol Name)<br>Column P — Footprint Path (Altium Footprint Library path)<br>Column Q — Footprint Ref (Altium Footprint name)<br>Column R — Footprint Path 2 (Altium Footprint Library path if multiple footprint are available)<br>Column S — Footprint Ref 2 (Altium Footprint Name if multiple footprint are available)<br>Column T — Datasheet# 1 Link (Link to additional information like datasheet or app note)<br>Column U — Datasheet# 2 Link (Link to additional information like datasheet or app note)<br>Column V — Signal Integrity (For future use)<br>Column W — Simulation (For future use)<br>Column X — Created by (Engineer who created this Altium part)</p><p><strong>Step 8: Get footprints from existing Altium Projects.<br></strong>First, we were working on an internal repository tool, then with the Digikey website and now finally we get our hands on Altium Designer. After getting manufacturer details for all electrical parts used in our company, it was time to get Altium footprint for the components from the few projects we have already completed since we changed to Altium. As I said in the opening sections, right now in our Altium projects, we are using all sorts of libraries, like those created by individual engineers, or an integrated library, or library borrowed from other projects. To make the problem of getting a Schematic symbol and PCB footprint easier, I generated one Schematic and PCB library for each project. By doing this it would get easier for me to get a schematic symbol and footprint for each component. Instead of trying to find it from different libraries, I would have to search for it in only one project library.<br>Creating Schematic and Footprint libraries from the project is very easy in Altium. Just open up your Altium project — Open schematic page — go to the Design tab — Click on Make Schematic Library.<br>Similarly for PCB library, open PCB file — Go in Design — Click on “Make PCB Library”.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*hK0EnHAWAjgJD50ynFAHqg.png" /><figcaption>Generate Schematic and PCB Libraries for each project</figcaption></figure><p>After creating libraries, I generated BOM from Altium projects having the following fields — Company Part Number, LibRef (gives me names of the schematic symbol), and Footprint (gives me footprint name for Column Q).</p><p><strong>Step 8: Remove Duplicate Part Numbers from Project BoMs<br></strong>After getting BoM for each project, I vertically stacked them together as shown in the below example screenshot. I also added a couple of columns manually to each BoM having the name of the Schematic and Footprint library which I generated for each project in the above step. After stacking them together, I used Excel’s ‘Conditional Formatting’ tab to highlight duplicate parts to identify multiple instances of the same Company Part, and deleted them.<br>Result: Now I have a clean list of parts, organized by Company Part Numbers, for which I have Altium Schematic symbol and Footprints.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*qAyeomMPnV7ZFQiZU7M9hQ.png" /><figcaption>List of parts with Altium Schematic Symbol and PCB Footprint</figcaption></figure><p>I arranged my<a href="http://becominghuman.ai/"> database</a> folder as shown below. It had a simple folder structure. The reason for this is because while creating our Altium Database library, we need to provide the location address of the Schematic symbol and Footprint for each part. You will get more clear about it when we populate Columns N to S in our Company_Database excel file.<br> Database Folder<br>— (Folder) PcbLibraries<br> ````````— (Altium PCB Library) Project_1.PcbLib<br> ````````— (Altium PCB Library) Project_2.PcbLib<br> ````````— (Altium PCB Library) Project_3.PcbLib<br>— (Folder) SchLibraries<br> ````````— (Altium Schematic Library) Project_1.SchLib<br> ````````— (Altium Schematic Library) Project_2.SchLib<br> ````````— (Altium Schematic Library) Project_3.SchLib<br> — (Altium Datbase Library File) Company_Database<br> — (Ms Excel 97–2003 Worksheet) Company_Database</p><p>With a list of Altium parts created in step# 8, I wrote a simple function to execute the following steps.<br>a. Take Company Part Number form Altium Parts List.<br>b. Search for that part in the Company_Database excel file.<br>c. Update column I with column A from the Altium Parts List file for matched parts in the Company_Database excel file.<br>d. Update Columns O and Q by columns C and D from Altium Parts List — Name of Schematic Symbol and PCB Footprint respectively.<br>e. Update Column N with “SchLibraries\” + Column E from Altium Parts List. E.g. for parts matched from project 1, Column N in Company_Database will be updated as SchLibraries\ Project_1. SchLib. This will provide the complete address of the library where the Schematic symbol for this part is kept.<br>f. Update Column P with “PcbLibraries\” + Column F from Altium Parts List. E.g. for parts matched from project 2, Column P in Company_Database will be updated as PcbLibraries\ Project_2. PcbLib. This will provide the complete address of the library where the PCB Footprint for this part is kept<br>g. Update Column X with the name of the project from Column A of Altium Parts List.<br>Columns N &amp; O and Columns P &amp; Q provide Altium with complete address of the Schematic symbol and footprint for each component. We will see how we tell Altium that these are the columns from where it should take the addresses and names of symbol and footprint respectively in a later step.<br>But once we do that, columns N and P will provide Altium with a complete path to the library of the part. As you can see, this is a relative address with respect to the location where the Altium database library itself is stored. For e.g. on seeing SchLibraries\ Project_1. SchLib and PcbLibraries\ Project_1. PcbLib in Columns N and P, Altium will traverse through folders SchLibraries and PcbLibraries and access Project_1. SchLib and Project_1. PcbLib respectively. After that, it will use Columns O and Q to search for actual Schematic Symbol and corresponding Footprint for the part.<br> Result: In this step, we took our Altium parts list from step# 8 and updated Company_Database excel file with Schematic Symbol and Footprint details for the parts contained in Altium parts list.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*zbZDrXU_4dUnWkf0HeH21Q.png" /><figcaption>Database file updated with Altium Symbol and Footprint</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a21a2818dadeb8f14a95591413303701/href">https://medium.com/media/a21a2818dadeb8f14a95591413303701/href</a></iframe><p><strong>Step 10: Update Schematic Symbol and Footprint for <em>gelly bean</em> parts<br></strong>As you could imagine, in our Company_database excel file, there are tons of parts like Resistor, Capacitor, and Inductors in standard packages like 0402, 0603, 0805 respectively. These packages are standard throughout the industry and there is little risk in copying schematic symbols and footprints from one part with the same package to another. And that’s what we are going to do next. There is no need to write any function for this as this can be easily done in excel itself. In the Company_database file, I filtered Column J (Column G in screenshot examples), for e.g. to only show “Ceramic Capacitors”. Then sort Column M (Column J in screenshot examples) in the “A to Z” order. This will group all parts with the same package together. Now I just took the part which had Altium schematic symbol and footprint available, copied its Columns N to X, and pasted them in corresponding columns of the parts with the same package.<br>Repeat this for all components and packages you feel are compatible, like Resistors in 0402, 0603 and 0805 packages etc. and you are done with creating database file for your parts. <br>Pat yourself on the back 😊 as most of the hard work is done and now we just need to set up this newly created Company_database file as Altium library.</p><p><strong>Step 11: Create Altium Database library<br></strong>Create a new Altium database file by going to File » New » Library » Database Library from the main menu. On getting below dialog box, select “Microsoft Excel” in the dropdown box and select your “Company_database” excel file.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*n2DsnHH6FYa1ezdcCxEiEw.png" /><figcaption>Create new Altium Database Library file</figcaption></figure><p>If your MS-Office / Office 365 is a 32-bit version, you may get an error. Refer to this <a href="https://www.altium.com/documentation/altium-designer/using-database-libraries-with-32-bit-and-64-bit-altium-design-software-on-the-same-computer">link</a> to work around it. You can use “<a href="https://resources.altium.com/p/advanced-pcb-library-management">Advanced PCB Library Management</a>” article from Altium to know more about using the Database library in Altium.</p><p>With that, it’s a wrap. Hope you liked the article and can use it to make yours and your fellow EEs life easier by creating component library yourself for your company. Feel free to drop me a message in case you got any questions, suggestions, concerns …or even just to say Hi.</p><p>Till next time….cheers!!!! 😊</p><h3>Don’t forget to give us your 👏 !</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/780/0*2lvCls4yjxVMfZSR" /></figure><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fupscri.be%2F8f5f8b%3Fas_embed%3Dtrue&amp;dntp=1&amp;url=https%3A%2F%2Fupscri.be%2F8f5f8b&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=upscri" width="800" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/c43026df6fee7cdb1aab8aaf916125ea/href">https://medium.com/media/c43026df6fee7cdb1aab8aaf916125ea/href</a></iframe><figure><a href="https://becominghuman.ai/artificial-intelligence-communities-c305f28e674c"><img alt="" src="https://cdn-images-1.medium.com/max/255/1*2f7OqE2AJK1KSrhkmD9ZMw.png" /></a></figure><figure><a href="https://upscri.be/8f5f8b"><img alt="" src="https://cdn-images-1.medium.com/max/255/1*v-PpfkSWHbvlWWamSVHHWg.png" /></a></figure><figure><a href="https://becominghuman.ai/write-for-us-48270209de63"><img alt="" src="https://cdn-images-1.medium.com/max/255/1*Wt2auqISiEAOZxJ-I7brDQ.png" /></a></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2b2af975f9af" width="1" height="1" alt=""><hr><p><a href="https://becominghuman.ai/use-python-to-create-altium-database-library-2b2af975f9af">Use Python to create Altium Database Library</a> was originally published in <a href="https://becominghuman.ai/">Becoming Human: Artificial Intelligence Magazine</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone — Part II]]></title>
            <link>https://medium.com/data-science/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-part-ii-b0489dcb9c94?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0489dcb9c94</guid>
            <category><![CDATA[path-planning]]></category>
            <category><![CDATA[self-driving-cars]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[autonomous-vehicles]]></category>
            <category><![CDATA[drones]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Fri, 17 May 2019 22:43:41 GMT</pubDate>
            <atom:updated>2019-05-17T22:43:41.300Z</atom:updated>
            <content:encoded><![CDATA[<h3>Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone — Part II</h3><h4>In this part, we will build on theoretical base we learnt in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">part 1</a> and code the A* algorithm in Python.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*kbkkSd5qCFrIBZ1SGCDodA.jpeg" /></figure><ul><li><strong>Unity Simulator, Python Environment Installation and Starter Files<br></strong>Before beginning to code anything, we need to get our setup and tools installed. We begin this by downloading required Unity simulator that’s appropriate for your operating system from <a href="https://github.com/udacity/FCND-Simulator-Releases/releases">here</a>. Next, we get required Python libraries installed. I would encourage you to create a separate Python environment (in any IDE of your choice) so as to keep it clean and separate. Follow installation instructions from this github <a href="https://github.com/udacity/FCND-Term1-Starter-Kit">repo</a>. Finally, we download this github <a href="https://github.com/udacity/FCND-Motion-Planning">repo </a>to get our start files. Make sure you got your setup correct by checking if you are able to run instructions provided in Step# 4 of above provided github repo for starter files.</li><li><strong>Starter Code<br></strong> To begin with this project, we are provided with two scripts, motion_planning.py and planning_utils.py. Here you’ll also find a file called colliders.csv, which contains the 2.5D map of the simulator environment. A 2.5D map is nothing but a 2D map (x, y location) with additional ‘height’ information for the obstacle. We will explore this file little more once we begin coding.<br> The main function in motion_planning.py establishes a “Mavlink” connection with simulator and creates a ‘drone’ object of ‘MotionPlanning’ class. Motion Planning class contains lot of built in functions already prepared for us. It contains callback functions ‘local_position_callback’, ‘velocity_callback’, ‘state_callback’.</li></ul><pre>if __name__ == &quot;__main__&quot;:<br>    parser = argparse.ArgumentParser()<br>    parser.add_argument(&#39;--port&#39;, type=int, default=5760, help=&#39;Port number&#39;)<br>    parser.add_argument(&#39;--host&#39;, type=str, default=&#39;127.0.0.1&#39;, help=&quot;host address, i.e. &#39;127.0.0.1&#39;&quot;)<br>    args = parser.parse_args()</pre><pre>conn = MavlinkConnection(&#39;tcp:{0}:{1}&#39;.format(args.host, args.port), timeout=60)<br>    drone = MotionPlanning(conn)<br>    time.sleep(1)</pre><pre>drone.start()</pre><p>What are callback functions? A callback function is intended to be executed only when a particular event triggers it. For e.g., if you look at code line ‘self.register_callback(MsgID.LOCAL_POSITION, self.local_position_callback)’ what it is doing is registering MsgID.LOCAL_POSITION and self.local_position_callback as key-value pair in a python dictionary (implemented inside ‘self.register_callback’ function). Now whenever value in ‘MsgID.LOCAL_POSITION’ variable changes, it will trigger a call to ‘self.local_position_callback’ function. Hence it’s called a callback function. Because the function is not called during normal ‘sequential’ flow of program, but instead it gets called only when a particular event has happened, which is change in value of ‘MsgID.LOCAL_POSITION’ in this particular case.</p><pre>class MotionPlanning(Drone):</pre><pre>def __init__(self, connection):<br>        super().__init__(connection)</pre><pre>        self.target_position = np.array([0.0, 0.0, 0.0])<br>        self.waypoints = []<br>        self.in_mission = True<br>        self.check_state = {}</pre><pre>        # initial state<br>        self.flight_state = States.MANUAL</pre><pre>        # register all your callbacks here<br>        self.register_callback(MsgID.LOCAL_POSITION, self.local_position_callback)<br>        self.register_callback(MsgID.LOCAL_VELOCITY, self.velocity_callback)<br>        self.register_callback(MsgID.STATE, self.state_callback)</pre><p>This all callback functions form the core structure of overall program of flying drone. Various operations like take-off, landing, transitioning to waypoint following state, arming and disarming drone along with required callback functions are taken care of in this starter code. You can go over motion_planning.py file and understand this functions, but as the primary goal of this article is to explain the code for ‘plan_path’ function, we will not dwell too much on starter code. Once a drone has been armed, it has taken off successfully and transitioned into waypoint following state, we need to start sending it one waypoint at a time, which will be generated by our ‘plan_path’ function before drone even takes off.</p><p>Once we make sure our drone is armed (basically a system check to make sure all propellers and other systems are operating as per expectation), the first thing we done before taking off is prepare a valid path to follow. To begin simple, we plan to fly at constant height. We will also be keeping a ‘Safety_distance’ from obstacles in our map / world.</p><p>TARGET_ALTITUDE = 5<br>SAFETY_DISTANCE = 5</p><ul><li><strong>Creat_Grid<br></strong>In order to create a path, we need a map, and that is provided to us in ‘colliders.csv’ file. Opening the file, we can see that first row contains ‘lat0’ and ‘lon0’ values. These are home location or 0, 0, 0 for our map.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/408/1*X8w5FCLEBobf_VWCRCtkew.png" /></figure><p>Following lines read home latitude and longitude provided in 1st row of colliders.csv and set it as our home position.</p><pre># TODO: read lat0, lon0 from colliders into floating point values<br>        lat0_lon0 = pd.read_csv(&#39;colliders.csv&#39;, nrows = 1, header = None)<br>        lat0, lon0 = lat0_lon0.iloc[0,0], lat0_lon0.iloc[0,1]<br>        _, lat0 = lat0.split()<br>        _, lon0 = lon0.split()<br>        lat0 = np.float64(lat0)<br>        lon0 = np.float64(lon0)</pre><pre># TODO: set home position to (lat0, lon0, 0)<br>        self.set_home_position(lon0, lat0, 0)</pre><p>When then check our current global position and convert it into local position, which will be with respect to home position we set earlier. We then print our current local and global position along with global home position value.</p><pre># TODO: retrieve current global position <br># TODO: convert to current local position using global_to_local()<br>current_local_pos = global_to_local(self.global_position, self.global_home)<br>        <br># Me: checking current local position<br>print (&#39;current local position {0} and {1}&#39;.format(current_local_pos[0], current_local_pos[1]))<br>        <br>print(&#39;global home {0}, position {1}, local position {2}&#39;.format(self.global_home, self.global_position,<br>                                                                         self.local_position))</pre><p>Next we work on defining our map in grid format that we studied in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">part 1</a> of this series. We first read complete data from colliders.csv, and then pass that numpy array to function called ‘create_grid’.</p><pre># Read in obstacle map<br>data = np.loadtxt(&#39;colliders.csv&#39;, delimiter=&#39;,&#39;, dtype=&#39;Float64&#39;, skiprows=3)<br>        <br># Define a grid for a particular altitude and safety margin around obstacles<br>grid, north_offset, east_offset = create_grid(data, TARGET_ALTITUDE, SAFETY_DISTANCE)</pre><p>Before we understand how ‘create_grid’ will create our grid map, we need to understand the format in which data is provided in colliders.csv. If we look at the heading for each column (as shown in row2 of image2), we see that we are given 3 positional values of a point — its x, y and z coordinates, and 3 distance values. The x, y and z coordinates are coordinates of a center point for an obstacle and 3 distances are its width, length and height values. Actually they are half of height, width and length, as they are distance from center point to one side of obstacle. Below diagram explains how both center point and dimensions values for obstacles are provided.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/338/1*kZn4xB_zwCYzIJ61LF5Owg.png" /></figure><p>We will be creating maps similar to 2.5D structure explained in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">part 1</a>. In fact, we will be going one step further. We have already fixed the flying altitude for our drone with ‘TARGET_ALTITUDE’ variable. So while creating map, we will only include an obstacle in our map if its height (PozZ + 2 * halfSizeZ) is greater than ‘TARGET_ALTITUDE’. If height of the obstacle is less than ‘TARGET_ALTITUDE’ we will just assume it to be a free space as our drone can fly over it. This approach greatly reduces the space and processing complexity that our map needs.</p><p>With height parameter sorted out, we need to determine size of the map which we need to create. For this, we first determine the closest and furthest point from our origin in both X and Y direction. Consider X direction to be North and Y direction to be East, we can get value of closet and furthest point in both directions as follows:</p><pre># minimum and maximum north coordinates<br>north_min = np.floor(np.min(data[:, 0] - data[:, 3]))<br>north_max = np.ceil(np.max(data[:, 0] + data[:, 3]))</pre><pre># minimum and maximum east coordinates<br>east_min = np.floor(np.min(data[:, 1] - data[:, 4]))<br>east_max = np.ceil(np.max(data[:, 1] + data[:, 4]))</pre><pre># given the minimum and maximum coordinates we can<br># calculate the size of the grid.<br>north_size = int(np.ceil((north_max - north_min + 1)))<br>east_size = int(np.ceil((east_max - east_min + 1)))</pre><p>And finally we initialize our grid map as numpy zeros array</p><pre># Initialize an empty grid<br>grid = np.zeros((north_size, east_size))</pre><p>Next, we will iterate over each obstacle from our colliders.csv data, which we have already captured in variable ‘data’. We will first compare whether obstacle’s height is above ‘TARGET_ALTITUDE’, and if it is, then we will mark the area occupied by the obstacle + a safety distance we configured in variable ‘SAFETY_DISTANCE’ as 1 in our grid world. Finally, we return our grid world along with north_min and east_min values.</p><pre># Populate the grid with obstacles<br>    for i in range(data.shape[0]):<br>        north, east, alt, d_north, d_east, d_alt = data[i, :]<br>        if alt + d_alt + safety_distance &gt; drone_altitude:<br>            obstacle = [<br>                int(np.clip(north - d_north - safety_distance - north_min, 0, north_size-1)),<br>                int(np.clip(north + d_north + safety_distance - north_min, 0, north_size-1)),<br>                int(np.clip(east - d_east - safety_distance - east_min, 0, east_size-1)),<br>                int(np.clip(east + d_east + safety_distance - east_min, 0, east_size-1)),<br>            ]<br>            grid[obstacle[0]:obstacle[1]+1, obstacle[2]:obstacle[3]+1] = 1</pre><pre>return grid, int(north_min), int(east_min)</pre><p>A small caveat which we need to understand is, the obstacles in colliders and our current local location are with respect to global home, which we had configured in with help of lat0 and lon0 variables. Whereas, the grid world which we create in create_grid function has origin at first obstacle point. Remember how we had calculated north min &amp; max and east min &amp; max and then north and east size to create a grid. Well, because of that there is an offset between colliders &amp; our drone’s positional values and corresponding same position in our grid world. Following diagram will help us understand it better.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/490/1*4hEpFQujNiFl1zN-cj07Aw.png" /></figure><p>So every time we are trying to map a value from our drone’s positional sensor to grid world, we need to subtract north and east offset respectively. This offset value is nothing but north_min and east_min returned by create_grid function. We set our current position in grid_world as</p><pre># TODO: convert start position to current position rather than map center<br>grid_start = (int(current_local_pos[0] - north_offset), int(current_local_pos[1] - east_offset))</pre><p>Assign a goal location of our choice</p><pre># Take GPS co-ordinates as Grid goal -Me<br>grid_goal = (-122.396582, 37.795714, 0)<br>grid_goal = global_to_local(grid_goal, self.global_home)<br>grid_goal = (int(grid_goal[0] - north_offset), int(grid_goal[1] - east_offset))</pre><p>Print our start and goal location and off we go on our way to be A*!!</p><pre>print(&#39;Local Start and Goal: &#39;, grid_start, grid_goal)<br>path, _ = a_star(grid, heuristic, grid_start, grid_goal)</pre><ul><li><strong>A* in the city<br></strong> We pass the grid we just now created in above section, a heuristic function and our start and goal location as arguments to a_star function. Hopefully the concepts we had gained in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">part 1</a> of this series will help us understand code for this function better. In fact let’s revisit the list of steps we had gone through while understanding Breadth First Algorithm. Knowing which step of our algorithm is performed in which set of lines will help us understand below code block better. As stated in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">Part 1</a>, a A* algorithm adds ‘cost’ and ‘heuristic’ function on top of a BFS. So along with code for implementing below steps, it will include adding and accessing ‘cost’ and ‘heuristic’ functions too.<br> The backbone of a breadth-first search consists of these basic steps:<br> 1. Add a node/vertex from the grid to a queue of nodes to be “visited”.<br> 2. Visit the topmost node in the queue, and mark it as such.<br> 3. If that node has any neighbors, check to see if they have been “visited” or not.<br> 4. Add any neighboring nodes that still need to be “visited” to the queue.<br> 5. Remove current node we’ve visited from the queue.<br> We first declare few variables. We will be using a Priority Queue to store nodes we need to visit. A typical pattern for entries in priority queue is a tuple in the form: (priority_number, data). The lowest valued entries are retrieved first and as we will be using ‘cost to reach corresponding node’ value as ‘priority_number’, whenever we will ‘get’ (or pop) an element from this priority queue, we will get an element which has least ‘cost’ value. We start at our ‘start’ node.</li></ul><pre>path = []<br>    path_cost = 0<br>    queue = PriorityQueue()<br>    queue.put((0, start))<br>    visited = set(start)</pre><pre>branch = {}<br>found = False</pre><pre># Check till we have searched all nodes or have found our ‘goal’<br>while not queue.empty():<br>    item = queue.get() # Step2. Visit the topmost node in the queue<br>    current_cost = item[0]<br>    current_node = item[1]</pre><pre>    if current_node == goal:<br>      print(&#39;Found a path.&#39;)<br>      found = True<br>      break<br>    <br>    else:</pre><pre>#Step3. If that node has any neighbors, check to see if they have been “visited” or not.<br>      <br>      for a in valid_actions(grid, current_node):<br>        next_node = (current_node[0] + a.delta[0], current_node[1] + a.delta[1])<br>        new_cost = current_cost + a.cost + h(next_node, goal)</pre><pre>#Step4. Add any neighboring nodes that still need to be “visited” to the queue.<br>        if next_node not in visited:<br>          visited.add(next_node)<br>          queue.put((new_cost, next_node))</pre><pre>          branch[next_node] = (new_cost, current_node, a)</pre><p>As we saw in <a href="https://towardsdatascience.com/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">part 1</a>, whenever we reach a node in BFS algorithm, it is guaranteed to be the shortest path to that node from our ‘start’ location. So to keep track of path we are tracing, in a_star function, we will be maintaining a dictionary, for which ‘key’ will be the node we will be visiting next, and its value will be a tuple of current node, action to be taken from current node in order to reach next node and total cost to reach next node. This tuple (current node + action to take to reach next node) will represent the shortest path to reach next node coming from ‘start’ location.<br> Now once we find ‘goal’ location, we will trace back the route to ‘start’ location with the help of this ‘branch’ dictionary. We first copy the value of total cost to reach ‘goal’ location. Next, as we know that node present in ‘value’ of dictionary lies on the shortest path, we will build our ‘path’ list as -&gt; [goal, node present in value of branch[goal], …]. And we will keep tracing back our route till we find ‘start’ location, adding nodes to ‘path’ list.</p><pre>if found:<br>        # retrace steps<br>        n = goal<br>        path_cost = branch[n][0]<br>        path.append(goal)<br>        while branch[n][1] != start:<br>            path.append(branch[n][1])<br>            n = branch[n][1]<br>        path.append(branch[n][1])<br>    else:<br>        print(&#39;**********************&#39;)<br>        print(&#39;Failed to find a path!&#39;)<br>        print(&#39;**********************&#39;) <br>    return path[::-1], path_cost</pre><ul><li><strong>Helper Functions<br></strong><em>Path Pruning:</em> Once we have our path figured out, we will prune it by removing collinear points as explained in Collinearity Check section in Part 1. We take 3 consecutive points from our final path and check whether they lie on same line. We do this by calculating the area enclosed by selected 3 points. If it is very close to 0, we can assume that they lie on same line. We first convert a point in a 3 element (x-coordinate, y-coordinate, 1) to numpy array. We add this last element “1” so that we can arrange 3 vertices into a nice 3 x 3 matrix. After reshaping points in “points()” function, we create a matrix by concating them and then calculating the determinant of that matrix using a convenient np.linalg.det() function.<br><em>Valid Actions</em>: One function which was used by us in a_star is valid_actions (grid, current_node). This was used to carry out step# 3 of BFS algorithm, where we search for current node’s neighbours. We already have our action set (as explained in “Search space, Action set and Cost” section of Part1) and location of our current node. This function will return a subset of action set. It will check weather an action (i.e. moving up, down, left, right or diagonal) will lead us off grid or to an obstacle / No Fly zone node. And if that is the case, it will remove this action from list of valid actions feasible from current node.</li></ul><p>Coming back to motion_planning.py, once we get pruned path, take each point from it, convert it into waypoint in local frame coordinate (by adding north and east offsets) and send it to autopilot using self.send_waypoints() function. And with that, we have finished coding our path planning A* algorithm. So without further ado, lets fire up Udacity’s drone simulator and run our motion_planning.py python file. You can find all the source code in my github repo <a href="https://github.com/PercyJaiswal/FCND-Motion-Planning.git">here</a>. If everything runs smoothly, you should be able to see your drone fly from a user configured starting and goal location like shown in below gif.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*_ErzhG8YaQOGMzrpH01Wsw.gif" /></figure><p>Hope you have enjoyed reading couple of articles in this series and now have a good understanding of fundamentals of A*.</p><p>If you found this article useful, you know what to do next 😊 Till next time….cheers!!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*5wtinsb0QamDr88559Cy5g.gif" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0489dcb9c94" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-part-ii-b0489dcb9c94">Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone — Part II</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone]]></title>
            <link>https://medium.com/data-science/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d5b566fa1ae</guid>
            <category><![CDATA[self-driving-cars]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[drones]]></category>
            <category><![CDATA[autonomous-vehicles]]></category>
            <category><![CDATA[path-planning]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Tue, 30 Apr 2019 13:30:28 GMT</pubDate>
            <atom:updated>2019-04-30T13:30:28.821Z</atom:updated>
            <content:encoded><![CDATA[<h3>Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone</h3><h4>In this tutorial we will learn and code a very famous algorithm commonly used for path planning called A* (A — Star)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/806/1*TEA-BqY7xlaOBVtRR8_w-g.png" /></figure><ul><li><strong>Introduction</strong><br>We will be using an open source simulator provided by Udacity to make a drone fly from a start location to a goal. Planning is a one of the core capabilities of any autonomous vehicle. Before any autonomous vehicle can embark on a mission, it needs to have a plan, which is nothing but a series of actions that the vehicle must take in order to safely and efficiently move from some initial location to some goal location. To start with a planning problem, we need to have following — a) A set of all possible sets in which a vehicle can find itself (a map of the environment it needs to operate in) b) A start state and a goal state. c) Set of actions which will allow the vehicle to move from one state to next. And finally, d) — Cost of each possible action while transitioning from one state to another.</li><li><strong>Search space, Action set and Cost</strong><br> So what could be the simplest representation we can think of to represent a “search space”? Let’s consider a top-down two-dimensional view of the world. We can divide this world in small grids. Next, we need to incorporate obstacles into this representation. A common way to do this is to mark any grid cell that contains the obstacle as infeasible. The vehicle won’t be allowed to enter these cells. All the remaining grid cells are marked as free cells. To prepare a plan will mean to find out a path which will go through sequence of free grid cells from the start state to goal state.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*KUBcmO_vOvArYtOC5PwCzw.png" /><figcaption>Image 1</figcaption></figure><p>Next thing we need is an action set. We can consider actions that move the vehicle right, left, up, down and diagonal motions as our action space. For cost function, we can start simple by considering actions moving <em>right</em>, <em>left</em>, <em>up</em> and <em>down</em> as having a cost of 1. For diagonal motion, we can calculate that if lateral and vertical motion costs 1, then as per Pythagoras theorem, diagonal motion will cost square root of 2. Whenever we are making plans, we can add up this costs (to move from start to goal location) and use that to compare different plans.</p><ul><li><strong>Breadth First Search (BFS)<br></strong> Now that we have our grid world, we need to build a sequence of steps to travel from start state to goal state. So how do we build this plan? The process of actually searching by ‘breadth’ can be written down to a few steps, which we’ll continue to repeat again and again, until we have reached our goal.<br>The backbone of a breadth-first search consists of these basic steps:<br>1. Add a node/vertex from the grid to a queue of nodes to be “visited”.<br>2. Visit the topmost node in the queue, and mark it as such.<br>3. If that node has any neighbors, check to see if they have been “visited” or not.<br>4. Add any neighboring nodes that still need to be “visited” to the queue.<br>5. Remove current node we’ve visited from the queue.<br> <br>Let’s see these steps in action by searching for goal location from start position for map shown in above Image 1. We will be maintaining two ‘queues’ (called ‘queue’ and ‘visited’), one to track nodes which we need to visit, and second one to list down nodes which we have already visited. So starting at ‘start’ location, let’s put that in as first element in our queue. This is step 1 of BFS algorithm, moving to step 2, we will ‘visit’ ‘start’ node. The process of visiting a node effectively means that we’re noting that it exists, and also checking its neighbouring nodes. In this case, the neighboring nodes of ‘start’ are nodes A3, B4 and A5; so, we’ll add them to our queue. Once we’ve visited node ‘start’ and added its neighbors to the queue, we can dequeue node ‘start’, since we’ve done everything that we need to do with it. At this moment, our 2 queues will look like this:<br><em>queue -&gt; A3 — B4 — A5; Visited -&gt; Start<br></em>Taking next element from our First In First Out (FIFO) queue, we will visit node A3, check its neighbouring free nodes A2 and B3, add these neighbouring nodes in queue and move A3 from queue to ‘visited’. Our updated queues will look like this:<br><em>queue -&gt; B4 — A5 — A2 — B3; Visited -&gt; Start — A3<br></em>Taking one more example, next node in our FIFO queue is B4. Things get a bit interesting here. We see that B4 has nodes B3, ‘start’, C4 and B5 as its neighbours. We already have identified Obstacles and No Fly Zones in our map, so we will not consider C4 and B5. Moving on we can see ‘start’ node in our ‘visited’ list, so we will ignore it. Finally, we see that B3 is already present in queue, so we will ignore this node also, as it’s already included in our queue. And with this, we have checked all neighbouring nodes of B4. We will move it out of queue and insert it in ‘visited’ list. In this case of visiting B4, you can see how BFS algorithm was cleverly able to recognize the fact that ‘start’ node was previously visited and node B3 was already listed in queue. Updated queues will look like this:<br><em>queue -&gt; A5 — A2 — B3; Visited -&gt; Start — A3 — B4</em><br>Next we take A5 and repeat the same procedure. And we continue this process till we find our ‘goal’ location.<br>One very important feature of BFS algorithm is that it fits very nicely in cases where we want to find shortest distance of any node from our starting node. In fact, many BFS algorithms will keep track of every single node’s “parent” node. A parent node is the one who first discovered the node in question. Looking back at the iterations we have done above, let’s consider the case when we were ‘visiting’ A3. When we were at A3, we discovered that A2 and B3 are newly discovered nodes. Now while adding A2 and B3 in our queue, if we just keep a note of the fact that it was A3 which had helped us discovered A2 and B3 nodes, we will have a very convenient way of determining shortest distance to any node from ‘start’ node. If for example, our ‘goal’ was at A2, once we discover A2 (when we will be ‘visiting’ A3), we can note that A3 is its parent node. And then, tracing back through ‘visited’ list, we can find out that ‘start’ node would be ‘parent’ node for A3. And like this, we have found shortest path to A2 from ‘start’ like A2 &lt;- A3 &lt;- ‘start’. Although this might seem like a very simple example, I encourage you to perform this exercise for any node of your interest and find out for yourself that if you keep information about ‘parent’ node and trace it back through ‘visited’ list, you will always find the shortest path to that node from ‘start’. Needless to say this will hold good if you change your ‘start’ node to any other location.</li><li><strong>Heuristic</strong><br> Now that we have a map, our start and goal locations and a way to prepare a plan, we can start to add little bit of intelligence to our algorithm. Right now if you see in above Breadth First Search example, we are visiting nodes on a first come first serve basis. For example, if you prefer to look at right node first, every time we are at any node, the node to it’s right will get the priority in FIFO queue and we will always visit this ‘right’ node before other (left, up, down and diagonal ones), even if other nodes are closer to our goal location. This doesn’t seem like a very intelligent system. Given a map of the world we need to traverse, we can make a rough estimate of how far goal location is from all other nodes. There are couple of common ways to do this. One example is to take Euclidean distance (or in other words, the square root of the sum of the square of the x and y distances) from node we are visiting to goal location as a criterial to judge how wise it will be to visit this node.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/575/1*ymG5CTFOSxyhi6io_GXj-Q.png" /></figure><p>Another common method is to take Manhattan distance, which is just the sum of x an y distance remaining to get to the goal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*UzIJ--xwaPaxGWOzABzFRA.png" /></figure><p>Both these methods ignores obstacles and is going to be an underestimate, but it will tell you whether the node you are planning to visit is taking you towards your goal or going further away. Using this distance, we can prioritize the nodes we want to visit first. In above BFS section, we saw that we were selecting order of neighbouring nodes at random. But now we can use this distance information to ‘visit’ the node which is at shortest distance from our ‘goal’.</p><p>Theses distance estimates are what are known as Heuristics, and they help us in finding a solution to planning problem. As you can see, heuristics are not perfect — they ignore obstacles and difficulty / cost of tracing different paths and are always an underestimate.</p><p>So we got a cost function and a heuristic, let’s combine them next!</p><ul><li><strong>A*</strong><br> To give guidance to the search process, we have two functions which we can now use. We have the cost function of the sum of the action we have taken so far, let’s call it ‘G’ and we have our heuristic function ‘H’, which is representation of remaining cost (proportional to remaining distance in our case) to reach goal state. If we add these two quantities together, we get an estimate of the total cost of the plan from the start all the way to the goal, even though we don’t know exactly how to get all the way to the goal yet. Let’s go back to our example. We will begin at the start state and expand to all neighboring nodes to the right, up and down and we can add a label to each node with the total cost of action ‘G’. If you calculate total cost = cost + heuristic for all neighboring nodes, we can see that traveling to right or down has the lowest value of total cost, and that is the direction we will chose to go. This process of choosing a path which has lowest total cost in terms of the actual cost of the actions plus the heuristic from the last node in the plan is the famous algorithm known as<strong> A star.</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/1*zsbADReGqhCAwBv6l7eqZg.png" /></figure><ul><li><strong>Co-ordinate frames</strong><br> Upto this point, we been considering how to find a path from start state to goal state by connecting cells in a grid. But before finding a path to goal location, we first need to represent current position of our vehicle. We will use two different co-ordinates for representing our vehicle’s position. First frame is probably the one with which we are most familiar with, that is, using latitude and longitude to define position, which are known as geodetic frame. The geodetic frame is just a spherical coordinate system where the typical coordinates ‘r’, theta (θ) and phi (φ) are represented by altitude, longitude and latitude respectively. Instead of having ‘r’ = altitude to be 0 at centre, we set it to be 0 at surface of the earth.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/357/1*47Q6V73jBXoCgu1Oh4Ho8A.png" /></figure><p>A spherical system can be little difficult to actually do motion planning because its hard to compute distances using angular quantities. Hence we will convert them to more convenient local frame, called as Earth-centred Earth fixed (ECEF) frame. In ECEF, every point in space is represented as x, y and z. However, its more useful if this coordinate system has origin at surface of the earth. And with that we get our own local ECEF frame.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/305/1*fQcfbdzpKEU7EyXwRMnLZQ.png" /></figure><ul><li><strong>Collinearity Check</strong><br> Now that we have a plan output from our A* algorithm, we know how to reach goal location from our starting point. But if we send this plan, the sequence of grid cells to autopilot, what we are really asking the vehicle to do is to travel through a sequence of short goals. In the example we been working on, we would be telling the autopilot to go to goal location from our start location. What autopilot will do is it will start from current location, go one grid down and stop. Next we send next waypoint, which is to go one grid cell down again and stop. Next we send waypoint to go one grid cell right and stop and so and so forth. What we really want our vehicle to do is to go down, turn and travel all the way to the last grid cell which is our goal location.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*n9h4A8zSWIIImZzYjYdl_w.png" /></figure><p>The question then is how do we take this sequence of grid cells and turn it into waypoints? One method we can use is to take original list of grid cells and just take grid cells that are at beginning and end cell of any sequence of states that lie along a straight line. Let’s assume we have 3 points as shown below. If these 3 points line on a same line (they are collinear), then the area of the triangle defined by these three points is zero. If we point coordinates of these 3 points in a matrix form as shown below, then determinant of this matrix represents the area formed by these 3 points. If determinant of this matrix is 0, the area of triangle is 0 and these 3 points are collinear.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*8KNSkNfBmm8lcWuXZGde1A.png" /></figure><p>In next part of this blog, we will be taking the map of city of San Francisco along with methods we have learnt in this part and going to combine them to code a 3D motion planner algorithm. Stay tuned, If it sounds exciting to you!</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d5b566fa1ae" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/lets-be-a-learn-and-code-a-path-planning-algorithm-to-fly-a-drone-4d5b566fa1ae">Let’s be A* — Learn and Code a Path Planning algorithm to fly a Drone</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Generate Sports Rankings with Data Science]]></title>
            <link>https://medium.com/data-science/generate-sports-rankings-with-data-science-4dd1979571da?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/4dd1979571da</guid>
            <category><![CDATA[rankingfactor]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[sports]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[sports-science]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Thu, 04 Apr 2019 13:25:23 GMT</pubDate>
            <atom:updated>2019-04-04T13:25:23.697Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/735/1*GV_718jdiP5ENjOk4XOn6g.jpeg" /></figure><p>In this tutorial, we will go through one very popular algorithm used in generating rankings for sports teams. The method which we will be studying is called Colley Ratings.</p><p>Before going into depth, lets first understand why are these ranking systems required. Will a simple win-loss ratio not be enough? To answer this, let’s go through an example. Consider there is a tournament with 4 teams playing in it and following are the results, and final table of the tournament standings so far.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*2AIKG4LP9vYXVUZ5kVnAeA.png" /></figure><p>As you can see, Manchester United has won all of their 6 games and sit comfortably on top, Liverpool have lost all their games and lie on bottom of table. Arsenal and Chelsea share the spoil having been defeated by Man Utd in both rounds, defeating Liverpool in both rounds and then splitting the tie between themselves with Arsenal winning in 1st round and Chelsea returning the favour in reverse fixture.</p><p>Now imagine we begin 3rd round of fixtures and first couple of game’s results were as below.<br>Game 1: Arsenal defeat Manchester United<br>Game 2: Chelsea defeat Liverpool<br>With that, updated table will look like below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*VYDzwowt3VcstBJ8dSTFvA.png" /></figure><p>Now wait a minute, does Chelsea and Arsenal really deserve to get same rankings? Isn’t it pretty obvious that Arsenal has defeated Manchester United who were dominant team in the tournament so far, whereas Chelsea defeated Liverpool who had anyways lost all their games. Definitely Arsenal should get more credit and should be ranked higher than Chelsea. But how do we do that? If we are using just a simple win-loss ratio, there is no way to differentiate them. Further on if you are considering goal difference and such, consider that all games have been won by the score line of 2 goals to 1, again we have a deadlock. Then how should we take into account the fact Arsenal defeated a much stronger team than Chelsea did, and hence deserves a higher ranking. This is where ranking systems come into picture. As we will see, Colley rankings are able to understand the event of a strong team being defeated and adjust their rankings accordingly. So without further delay, let’s get started.</p><h4><strong>Colley Rankings</strong></h4><p>Mr. Wesley N. Colley suggested that instead of calculating rankings based on win-loss ratio like; ratings = [total wins] / [total games], ratings should be calculated based on following formula</p><p>Rating = [1 + total wins] / [2 + total games]. If you look at this formula, before start of any tournament, all teams will begin with a rating of 0.5, as both ‘total wins’ and ‘total games’ will be zero. Keep note of this point (the fact that all teams start with a rating of 0.5), it will come in handy later on. In fact, during all times, the average of all team’s ratings in Colley’s algorithm will always stay at 0.5.<br>We can write total-wins as shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/601/1*Y5EFIlSTjCV2hTcVNTwGYA.png" /></figure><p>Looking closely into ½ * [total-games] term for a single team, we can say that ½ * [total-games] = ½ * [1+1+1…1] where ‘1’ stands for a game played against each opponent. This in turn can be written as ½ * [total-games] = [1/2 + ½ + ½+..]. Now if you remember, as said before at the start, rating of all teams would be around 0.5 and hence average rating for all teams combined will also be 0.5. Considering this, we can say that [1/2 + ½ + ½ + ..] ~= [sum of opponent’s ratings]. With this, rewriting equation for total-wins.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*E8E323ZdZSJUn_zP5ceYNw.png" /></figure><p>Rewriting formula for ratings,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*gE3E0Mwzhox9z4xDbdfEfA.png" /></figure><p>Expanding total-wins and writing down rating for individual team, we can write as.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/315/1*dFSuVCEs5It9or-v32GMfg.png" /></figure><p>Where rᵢ, wᵢ, lᵢ, and ti represent rating, wins, loss and total game for the team of interest and ∑rj is sum of opponent’s ratings. This can be further rearranged as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*4B257vv6U7UVjl3BUgdOuQ.png" /></figure><p>Now, as with most of my other tutorials, let’s use a toy example to understand mathematical equations better. Consider a case of two teams. As stated above, before beginning, they both will have a rating of 0.5 each. Now let’s suppose they played one game against each other. Let rW and rL represent new ratings for winning and loosing team respectively. If you put tᵢ (which will be equal to 1) for both teams, and consider their wᵢ and lᵢ values, we will get following results from equation (A)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/260/1*wJQtZs5KlGlTQl-1onUJgg.png" /></figure><p>This represents a simple two variable linear system, which when solved gives us our new ratings as rw = 5/8 and rL = 3/8. For 2 teams, equation (A) resulted in two variable linear system, for N teams, it will result in N variable linear system. In programming world, whenever we want to solve N variable linear equations, we always write them in form of a matrix. So rewriting equation (A) in matrix form as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/114/1*pW171jL275UPaFHSy-kwvw.png" /></figure><p>Where <em>vector r</em> represents column-vector of all the ratings rᵢ and <em>vector b</em> is a column-vector of the right-hand-side of equation (A). The matrix C, defined as the <strong>Colley Matrix</strong>, is just slightly more complicated. Imagine having our four favorite English premier league teams as rows and columns of a 4x4 matrix, as shown in below picture</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/358/1*oixFrQA-hem8z9jWsX9t6g.png" /></figure><p>The diagonal elements in Colley matrix should be filled by number = (2 + total-games) for corresponding team. So 1st blue cell should have a value of 2 + number of games played by Manchester United. Similarly rest of cells to be filled for Chelsea, Arsenal and Liverpool games. The off diagonal elements, represented by green cell should have negative value of the number of games played between team represented by row and column for that cell. So for e.g. cell intersecting Man Utd row and Chelsea column should have a number equal to negative value of number of Man Utd vs Chelsea games. And like that we will fill rest of the cells in Colley matrix. Once we solve this N variable linear equation Cr = b, we will get vector value for ‘r’, which represents ratings for each individual team.</p><p>With this clear understanding of theoretical background, let’s go ahead and write a Python code to calculate Colley’s rankings for toy example introduced at the beginning of this article. Python code file, along with couple of supporting files can be found at my github repo <a href="https://github.com/PercyJaiswal/Colley_Rankings">here</a>.</p><p>Before beginning to code, let me explain structure of couple of supporting files, namely ‘scores’ and ‘teams’, both of which are in ‘comma separated value’ format. ‘teams’ file contains list of teams, alongside a ‘number’. This ‘number’ will be used to represent the team in ‘scores’ file. Following screenshot shows contents of ‘teams’ file.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/169/1*bZo3XWyYjnAvT0fcpEWChQ.png" /></figure><p>So from now on, whenever we want to represent Manchester United, we will represent them with number 1. Similarly for Chelsea, Arsenal and Liverpool, we will use numbers 2, 3, and 4 respectively while representing them in ‘scores’ file. Now let’s have a look at ‘score’s file with help of following screenshot.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/192/1*ZZTeDW9DwRIp9XB7EKk8cw.png" /></figure><p>Each row in ‘scores’ file corresponds to a game. I will explain it little later as to why is this file in such a particular order. Columns in ‘scores’ file represent =&gt; Column 1 = Number of days since 1/1/0000 when this particular game was played. Column 2 = today’s date. Column 3 = team 1 number. Column 4 = team 1 ‘home’ value (1 = home game, -1 = away game, 0 = neutral). Column 5 = team 1 score. Column 6 = team 2 number. Column 7 = team 2 ‘home’ value (1 = home game, -1 = away game, 0 = neutral). Column 8 = team 2 score.</p><p>As we will not be using Column 1, 2, 4 and 7 values in this exercise, I have put dummy numbers for them. Also, just for my convenience I have kept score (Column 5 for team 1 score and Column 8 for team 2 score) as mostly 2 and 1 each, as we will not be looking into scores either in this example. We will just use it to determine winner of each game.</p><p>Let’s take example of first row. Column 1 and 2 representing date of the game has dummy values of ‘1’ each. Column 3 has a value of ‘1’. Cross checking this with our ‘teams’ file, we can see that value of ‘1’ is used to represent Manchester United. Column 4 has ‘-1’, signifying that this game was away game for Manchester United. Col 5 has a value of ‘2’ meaning that 2 goals were scored by Manchester United. Col 6 value represent team 2 number, where number 2 means team 2 was Chelsea and this was a Manchester United vs Chelsea game. Col 7 has a value of ‘1’ meaning to say this was a home game for Chelsea and final column has a value of ‘1’ representing number of goals scored by Chelsea.</p><p>Finally, let’s start to code this algorithm. Coding Colley algorithm is relatively simple and fairly self explanatory. As with any Python file, we will import required packages, namely numpy and pandas in this case.</p><pre># Importing packages<br>import numpy as np<br>import pandas as pd</pre><p>Then we go and read ‘teams’ and ‘scores’ files.</p><pre># Reading &#39;teams&#39; and &#39;scores&#39; data<br>teams = pd.read_csv(&#39;teams.txt&#39;, header = None)<br>num_of_teams = len(teams.index)</pre><pre>data = pd.read_csv(&#39;scores.txt&#39;, header = None)</pre><p>We initialize Colley matrix and vector b with all 0 in required dimensions.</p><pre># Initializing Colley Matrix &#39;c&#39;and vector &#39;b&#39;<br>c = np.zeros([num_of_teams, num_of_teams])<br>b = np.zeros(num_of_teams)</pre><p>Then, iterating through ‘scores’ file line by line, we populate Colley matrix and vector ‘b’ depending on which teams are playing and winner of each game.</p><pre># Iterating through rows and populating Colley matrix values<br>for index, row in data.iterrows():<br>    t1 = row[2]<br>    t2 = row[5]<br>        <br>    c[(t1-1)][(t1-1)] = c[(t1-1)][(t1-1)] + 1 # Updating diagonal element<br>    c[(t2-1)][(t2-1)] = c[(t2-1)][(t2-1)] + 1 # Updating diagonal element<br>    c[(t1-1)][(t2-1)] = c[(t1-1)][(t2-1)] - 1 # Updating off - diagonal element<br>    c[(t2-1)][(t1-1)] = c[(t2-1)][(t1-1)] - 1 # Updating off - diagonal element<br>    <br>    # Updating vecotr b based on result of each game<br>    if row[4] &gt; row[7]:<br>        b[(t1-1)] += 1<br>        b[(t2-1)] -= 1<br>    elif row[4] &lt; row[7]:<br>        b[(t1-1)] -= 1<br>        b[(t2-1)] += 1</pre><p>Once that is done, we make the adjustment of adding 2 to diagonal elements of Colley matrix and dividing and adding 1 to each element of vector b, as per equation (A).</p><pre># Adding 2 to diagonal elements (total number of games) of Colley matrix<br>diag = c.diagonal() + 2<br>np.fill_diagonal(c, diag)</pre><pre># Dividing by 2 and adding one to vector b<br>for i, value in enumerate(b):<br>    b[i] = b[i] / 2<br>    b[i] += 1</pre><p>Afterwards we solve this N variable linear equation using numpy’s linalg.solve().</p><pre># Solving N variable linear equation<br>r = np.linalg.solve(c, b)</pre><p>Once we get result in ‘r’, we display top 4 teams by using argsort() method.</p><pre># Displaying ranking for top 4 teams<br>top_teams = r.argsort()[-4:][::-1]<br>for i in top_teams:<br>    print (str(r[i]) + &quot; &quot; + str(teams.iloc[i][1]))</pre><p>And with that, if you successfully downloaded the repo and ran this code, you should see following output.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/164/1*G49PETWnGkuzbHK536_h9Q.png" /></figure><p>Now, to check real strength of this algorithm, we will be adding two more games in our ‘scores’ files by inserting following lines.<br>Game 1: Arsenal defeat Manchester United =&gt; 1, 1, 1, -1, 1, 3, 1, 2<br>Game 2: Chelsea defeat Liverpool =&gt; 1, 1, 2, -1, 2, 4, 1, 1<br>Running Python file again after making above modifications in ‘scores’, you will get following result.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/236/1*LdzF_wh_5d0653ReN8KlxA.png" /></figure><p>As you can see, even though Arsenal and Chelsea have played, won and loss equal number of games, Colley algorithm was able to recognize the fact that Arsenal had defeated a stronger team in Manchester United compared to Liverpool who was defeated by Chelsea.</p><h3><strong>The In-Form Team</strong></h3><p>Coming back to the format of ‘scores’ files, let’s see how it is useful with one more use case. Consider there are 3 rounds in tournament with results shown in below image.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/602/1*eL5HxaQTOmMS5kJOPW0hwA.png" /></figure><p>Manchester United win all their games in round 1, Chelsea win all their games in round 2, and Arsenal in round 3. Although all 3 teams are tied on number of wins, any knowledgeable sports person will tell you that after winning all games in first round, Man Utd have fizzled out. Arsenal on the other hand are on a hot streak winning all their games in latest round of fixtures, and Chelsea lie in between. With this in mind, even though total points for Man Utd, Arsenal and Chelsea are same, a good ranking system should provide a provision to distinguish old performances against recent one.</p><p>To take this ‘momentum’ or ‘in-form’ factor into account, a new variable called ‘weight’ is introduced. With the help of a simple ‘if else’ conditional statements, we are giving different weightage to different games.</p><pre># Iterating through rows and populating Colley matrix values<br>for index, row in data.iterrows():<br>    t1 = row[2]<br>    t2 = row[5]<br>    <br>    if row[0] &lt;= 6: #For first round matches<br>        weight = 0.9<br>    elif row[0] &gt; 6 and row[0] &lt;=12: #For second round matches<br>        weight = 1.0<br>    else:<br>        weight = 1.1 #For third round matches<br>    <br>    c[(t1-1)][(t1-1)] = c[(t1-1)][(t1-1)] + 1 * weight # Updating diagonal element<br>    c[(t2-1)][(t2-1)] = c[(t2-1)][(t2-1)] + 1 * weight # Updating diagonal element<br>    c[(t1-1)][(t2-1)] = c[(t1-1)][(t2-1)] - 1 * weight # Updating off - diagonal element<br>    c[(t2-1)][(t1-1)] = c[(t2-1)][(t1-1)] - 1 * weight # Updating off - diagonal element<br>    <br>    # Updating vecotr b based on result of each game<br>    if row[4] &gt; row[7]:<br>        b[(t1-1)] += 1 * weight<br>        b[(t2-1)] -= 1 * weight<br>    elif row[4] &lt; row[7]:<br>        b[(t1-1)] -= 1 * weight<br>        b[(t2-1)] += 1 * weight</pre><p>As the tournament progress, less weightage is given to old games. Whereas latest round of fixtures are given higher weightage compared to previous two rounds. With above modification, if we again run our Colley algorithm, we will get following results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/248/1*YAXMBpB1G7MW70CHfvXCHg.png" /></figure><p>As expected, Arsenal having won all its games in latest fixtures are ranked first, whereas Man Utd are ranked third even though they share same points with Arsenal and Chelsea.</p><p>And with that, I will draw curtains on this article. Hope the sports fanatic and Data scientist in you was able to appreciate the beauty and simplicity of Colley’s method.</p><p>As usual, if you liked this post, Follow, Like, Retweet it on <a href="https://twitter.com/percyjaiswal">Twitter</a> or Claps, Likes here on Medium will act as encouragement for writing new posts as I continue my journey into Blogging world.</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4dd1979571da" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/generate-sports-rankings-with-data-science-4dd1979571da">Generate Sports Rankings with Data Science</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Manchester United vs Southampton — 2nd March 2019]]></title>
            <link>https://medium.com/sportsraid/manchester-united-vs-southampton-2nd-march-2019-da38a73bf0c?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/da38a73bf0c</guid>
            <category><![CDATA[soccer]]></category>
            <category><![CDATA[sports]]></category>
            <category><![CDATA[english-premier-league]]></category>
            <category><![CDATA[manchester-united]]></category>
            <category><![CDATA[football]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Sun, 03 Mar 2019 10:43:02 GMT</pubDate>
            <atom:updated>2019-03-13T14:02:07.809Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*Bz8-ZwcrWy36QGwqPIdt4Q.jpeg" /></figure><h3>Manchester United vs Southampton — 2nd March 2019</h3><p>5 Key Talking points from a match with fascinating goals!!</p><ol><li><strong>McTominay Maturing</strong></li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*FACuBOlwgVVzliuvE-edjQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*Yzpe4yBOYsd2OAYIBg-x7A.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*W5HjeF85E_qs1cZM10H14w.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*UJ1Gd6yUu5VQ312yoDDdWw.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*fg8QpYY8FzJeKyE6mrXkMw.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*onfLyso7GvSrCoIY_S5yCA.gif" /><figcaption><strong>Excellent Defensive Work from McTominay</strong></figcaption></figure><p>As per Opta’s player scoring McTominay won 1/1 tackles, 7/7 duels, 4/4 Aerial duels and 3/3 Interception. As a defensive midfielder, he had an almost perfect game, recovering or safeguarding ball whenever it was required.<br>Whether he is ready for PSG? We will find out real soon!</p><p>2. <strong>PSG should be afraid of Lukaku…very afraid!</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*7y4jRpfUHxLC4pIT0-1vYA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*1pMOI_xdyKH5lzRjBmxGow.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*9Dg5T-9-h-HCjBACg5mTQA.gif" /><figcaption><strong>Lethal Lukaku</strong></figcaption></figure><p>The best thing about Lukaku is that you don’t need to necessarily play well for him to score. He showed that under Mourinho and he is certainly showing how much more lethal he can be if provided with service under Ole. I had said previously that Lukaku’s contribution against Liverpool was unnoticed.</p><p>He always defends and even after playing out of position had given two best moments from entire game for either side; pass to Lingard and cross to Smalling. 4 goals in last 2 games speak for themselves. He provides excellent balance to width and pace offered by Rashford, Martial and co. and let’s not forget he is only 25!</p><p><strong>3. Pereira plays like a kid in the park and that’s not a bad thing.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*N5u3qTnjGUaUuHOU_ahwCQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*y9SGVatVTl5Msv2_NR0Eag.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*dZMUmCLVAnAI0GysP1ffSw.gif" /><figcaption><strong>Kid in Park Pereira</strong></figcaption></figure><p>Pereira is playing like a kid in the park. Throughout the game he was pressing intensely to win back ball, kept sprinting, winning balls and often times giving away possession too. And then he produces a moment of magic.</p><p>He has long way ahead in his development path, but with excellent role models like Matic and Herrera to look up to, Pereira can develop an enthralling pair of academy grown midfield duo with McTominay</p><p><strong>4. Young and Rashford had off days</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*48ULizJGxsT5El2sghzapQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*lzjxYWQ3SWFFhlP09k3Q4Q.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*ZuABUMrYnDFKGnq3WBHEgA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*fMtRqNV9BdsqO116KjlN4w.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*8tW3BeorQlbcXb1AVc2XVQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*1J8KP_F5MdCVT8AZAYLhXg.gif" /><figcaption><strong>Rashford (Top) and Young (Bottom) had off days</strong></figcaption></figure><p>Young didn’t do anything particularly wrong when he gave away the free kick which lead to 2nd goal. But even after keeping that aside, he had an off day. Defensively, he didn’t have a closed door and allowed few of the crosses to come in little too easily. But it was in attack where he was little bit of a let-down. Normally reliable to shoot in cross, today he was constantly looking to offload forwards on side channels without any success</p><p>Same for Rashford, just an off day. Gave away ball couple of times, was offside couple of times when he should have managed to stay onside. Didn’t add much in game after his beautiful skill in 2nd min to escape Vestergaard.</p><p>Rashford himself knew he could have done better in most of the plays and his anger with himself was.</p><p><strong>5. Sanchez injury was a blessing in disguise, Pogba needs to tidy up</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*bzpjr6uyn_ajFSkSj355Vg.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*o_MHmGzDtweciNCFbjdNJA.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*J93HRt-7k5gbMLqggDpQWQ.gif" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*MGaSfgnCQRB2ETNButcxtQ.gif" /><figcaption><strong>Untidy Pogba</strong></figcaption></figure><p>With Sanchez off pitch, united started to play more narrower and direct football. Original plan was to use width and pace on the side with Sanchez and Rashford. That tactic was also giving rewards, with width allowing open spaces in middle and was evident with chances created within opening few minutes. But with the changed shaped. United just became more direct as the game progressed.</p><p>Pogba has been brilliant recently, but a place where he can improve is contribute with small little things when he is having an off day. It’s okay if he couldn’t find killer passes every match day, but he should work on tidying up lose passes.</p><p>Don’t expect Pogba to do defensive work or positioning like Matic, but Southampton players were passing by Pogba with too much of ease.</p><p>As usual, if you liked my article, show your appreciation with likes and comments. You can also find me and my other articles on <a href="https://twitter.com/percyjaiswal">twitter</a>.</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=da38a73bf0c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/sportsraid/manchester-united-vs-southampton-2nd-march-2019-da38a73bf0c">Manchester United vs Southampton — 2nd March 2019</a> was originally published in <a href="https://medium.com/sportsraid">SportsRaid</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Defense Against Dark Arts —The Mirror of Erised]]></title>
            <link>https://medium.com/hackernoon/defense-against-dark-arts-the-mirror-of-erised-7d65fc6a333d?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d65fc6a333d</guid>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[privacy]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Sun, 23 Dec 2018 18:34:13 GMT</pubDate>
            <atom:updated>2018-12-23T18:34:13.047Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*R-mOEUvIP6HtUyXTDUHNMg.jpeg" /><figcaption>The Mirror of Erised from Harry Potter and the Sorcerer’s Stone</figcaption></figure><p>As in Harry Potter saga, we are surrounded by unknown Death Eaters (read Hackers) who are trying to attack poor Potter (read Client / Data) for one reason or another. Some time they want data (like Soccer’s stone or Prophecy in Order of Phoenix) or sometimes they just want to kill / corrupt Potter to fend off a threat / competition. In either case, we need to protect our Data and Deep Learning model from such kind of Dark Attacks.</p><p>A regular Deep Learning model is very prone to attacks as it usually collects huge amount of data in a centralized server where deep learning models are trained. This is called centralized learning as learning occurs on a central server. But with a technique called Federated Learning, instead of bringing data to model, we bring model to training data.</p><p>In this post, I will be walking you through a small step in Federated Learning by explaining you an example from <a href="https://github.com/OpenMined/PySyft">PySyft</a> library. In specific, we will see how an end client called ‘Bob’ can have its data used by a centralized server without ever actually having to share it. You will understand more as we walk through the example.</p><p>We will be using two Jupyter Notebooks for this tutorial. One for “Bob’ (Bob.ipynb) who will prepare its data, give reference to its data with which data (actually its pointer) can be used by centralized server and finally open a connection wherein it can receive requests by centralized server. On the other hand, centralized server will also be having a file (Model.ipynb) running on its end, which will first of all make connection with Bob’s socket, get pointers to actual data and finally run its algorithm using just the pointer variables.</p><p><strong>Bob.ipynb</strong></p><pre>##### Import files#############<br>import syft as sy<br>hook = sy.TorchHook() # Start a hook to make a connection</pre><pre>&quot;&quot;&quot;#########################<br>Give your hook a <strong>id</strong>: “Bob”<br><strong>Port Address</strong>: 3000<br><strong>is_pointer</strong>: Will update more about it<br><strong>is_client_worker</strong>:(bool, optional)** a boolean which determines                             whether this worker is associated with an end user client. If so,                             it assumes that the client will maintain control over when                             tensors/variables/models are instantiated or deleted as opposed to                             handling tensor/variable/model lifecycle internally<br><strong>verbose:</strong>(bool, optional)** A flag for whether or not to print events to stdout.<br>##########################&quot;&quot;&quot;</pre><pre>hook.local_worker = sy.SocketWorker(hook=hook,<br>                                   id=&quot;Bob&quot;,<br>                                   port=3000,<br>                                   is_pointer=False,<br>                                   is_client_worker=False,<br>                                   verbose=True)<br>sy.local_worker = hook.local_worker</pre><pre># create two sample Pytorch tensors for our demonstration<br>import torch<br>x = torch.FloatTensor([1, 2, 3, 4, 5])<br>y = torch.FloatTensor([1, 1, 1, 1, 1])</pre><p>Check list of object registered with bob, an easy way to verify that tensors we just now created are properly configured to Bob.</p><pre>hook.local_worker._objects</pre><p>Output:<br>{38610448342: [_LocalTensor — id:38610448342 owner:Bob],<br> 51021230807: [_LocalTensor — id:51021230807 owner:Bob]}</p><p>The result clearly shows that x and y tensors we created as local tensors and are owned by Bob.</p><pre># Set ID with which client can request for pointers for our tensors</pre><pre>x.set_id(&quot;#X&quot;)<br>y.set_id(&quot;#Y&quot;)</pre><pre># start listening to commands and wait for magic to happen!</pre><pre>hook.local_worker.listen()</pre><p><strong>Model.ipynb</strong></p><pre># Give yourself a name and port address<br>import syft as sy<br>hook = sy.TorchHook(local_worker = sy.SocketWorker(id=0, port=3001))</pre><pre># Connect with Bob<br>remote_client = sy.SocketWorker(hook=hook,<br>                               id=&quot;Bob&quot;,<br>                               port=3000,<br>                               is_pointer=True)<br>hook.local_worker.add_worker(remote_client)</pre><pre># Get pointer variables for actual data<br>x_set = remote_client.search([&quot;#X&quot;])<br>y_set = remote_client.search([&quot;#Y&quot;])</pre><p>If you tried to access either x_set or y_set, you will immediately see message like</p><p>[FloatTensor[_PointerTensor — id:22003035565 owner:0 loc:Bob id@loc:#Y]]</p><p>Meaning to say that y_set is “PointerTensor” (and not actual value of Y), you are owner of this pointer, but “location” of actual data is “Bob” and it’s ID is #Y</p><pre># Perform Tensor Operation on actual data using pointer variables</pre><pre>import torch<br>z = torch.add(x_set[0],y_set[0])<br>z</pre><p>Output:<br>FloatTensor[_PointerTensor — id:12443450818 owner:0 loc:Bob id@loc:30395812931]</p><p>Again, as in case when we tried to access y_set, when you try to access value of z, you will get above message</p><pre># To get actual value of z<br>z.get()</pre><p>When you are performing all this operations on Bob’s data, bob is getting notifications like “Received Command From: (‘127.0.0.1’, 54484)”<br>on its end whenever you are trying to access it data. Along with that, a log file will also get generated.</p><p>And that’s it. In this small example, we saw how PySyft was used to get pointer variable to Bob’s data, perform operations (run Deep Learning models) on it and get results. This is big step from Privacy’s standpoint, as never in this complete operation did anyone have access to actual data contents of Bob’s.</p><p>In hindsight, our program above was very much similar to <strong>Mirror of Erised</strong> from the first movie, as in <strong>it will give you what you desire…..as long as you don’t (mis)use it!</strong></p><p>So that’s it for now, if you managed to stay with me till so far, I encourage you to go to <a href="https://github.com/OpenMined/PySyft">PySyft</a> github page and start taking a deep dive into it. You can find complete code for both Jupyter notebooks at my github repo <a href="https://github.com/PercyJaiswal/PySyft">here</a>.</p><p>As usual, if you liked my article, show your appreciation with likes and comments. You can also find me and my other articles on <a href="https://twitter.com/percyjaiswal">twitter</a>.</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d65fc6a333d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hackernoon/defense-against-dark-arts-the-mirror-of-erised-7d65fc6a333d">Defense Against Dark Arts —The Mirror of Erised</a> was originally published in <a href="https://medium.com/hackernoon">HackerNoon.com</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Demystifying Drone Dynamics!]]></title>
            <link>https://medium.com/data-science/demystifying-drone-dynamics-ee98b1ba882f?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/ee98b1ba882f</guid>
            <category><![CDATA[physics]]></category>
            <category><![CDATA[drones]]></category>
            <category><![CDATA[autonomous-vehicles]]></category>
            <category><![CDATA[quadcopter]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Tue, 30 Oct 2018 13:39:40 GMT</pubDate>
            <atom:updated>2018-10-30T15:29:35.406Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1010/1*2BN14FarSCcO6VvZ7bOHKA.png" /><figcaption>Demystifying Drone Dynamics!</figcaption></figure><ol><li><strong>Components</strong><br> Although most of us are aware how a quadcopter / drone looks, a generic picture (It’s of a drone called Crazyflie from bitcraze) of drone is shown above. It consists of 4 motors, control circuitry in middle and Propellers mounted on its rotors. For reasons described in below section, 2 of the rotors rotate in clockwise (CW) direction and remaining 2 in counterclockwise (CCW). CW and CCW motors are placed next to each other to negate Moment (described in next section) generated by them. Propellers come in different configurations like CW or CCW rotating, Pusher or Tractor, with different radius, pitch etcetera.</li></ol><p><strong>2. Force and Moments</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*hqpGBYIiOXW5GZ9F6m9bfg.png" /><figcaption>Figure 2: Forces and Moments</figcaption></figure><p>Each rotating propeller produces two kind of forces. When a rotor rotates, it’s propeller produces upward thrust given by <em>F</em>=<em>K</em>_<em>f * ω² </em>(shown by forces F1, F2, F3 and F4 in Figure 2) where <em>ω </em>(omega) is rotation rate of rotor measured in radian / second. Constant K_<em>f</em> depends upon many factors like torque proportionality constant, back-EMF, Density of surrounding air, area swept by propeller etc. The values for K_<em>f</em>​ and <em>K_m</em> (mentioned below)​ are generally found empirically. We mount the motor and propeller on a load cell and measure the force and moment for different motor speeds. Refer “System Identification of the Crazyflie 2.0 Nano Quadrocopter” by Julian Forster for details regarding measurement of K_<em>f</em> and K_<em>m</em>.<br>Total upward thrust generated by all 4 propellers is given by summing all individual thrusts generated, for i= 1 to 4 its given by <br><strong>F_i = K_f * ω²</strong><em><br></em> Apart from upward force, a rotating propeller also generates an opposing rotating spin called Torque or Moment (shown by Moments M1, M2, M3 and M4 in Figure 2). For e.g. a rotor spinning in CW direction will produce a torque which causes the body of drone to spin in CCW direction. A demonstration of this effect can be seen <a href="https://www.youtube.com/watch?v=P3fM6VwXXFM">here</a>. This rotating torque is given by<em> </em><strong>M=K_<em>m </em>* ​ω²<br></strong> Moment generated by a motor is in opposite direction to its spinning, hence CW and CCW spinning motors generate opposite moments. And this is the reason why we have CW and CCW rotating motors so that in steady hover state, moments from 2 CW and 2 CCW rotating rotors negate each other out and drone doesn’t keeping spinning about its body axis (also called yaw).<br>Moments / Torques M1, M2, M3 and M4 are moments generated by individual motors. The overall Moment generated around drone’s z axis (Z_b in Figure 2) is given by summation of all 4 moments. Remember that CW and CCW moments will have opposite signs.<br><strong>moment_z = M1 + M2 + M3 + M4</strong>, again CW and CCW moments will have opposite signs and hence in ideal condition (or whenever we don’t want any Yaw (rotation around z axis) movement) <em>moment_z</em> will be close to 0.<br>Contrary to <em>moment_z</em>, overall moment / torque generated around x and y axis’s calculations are little different. Looking at Figure 2, we can see that motor 1 and 3 lie on x axis of drone. So they won’t contribute to any moment / torque around x axis. However we can see that difference in forces generated by motor 2 and 4 will cause drone’s body to tilt around it’s x axis and this is what constitutes overall moment / torque around x axis, which is given by<br><strong>moment _x = (F2 — F4) * L</strong>,<strong> </strong>where L is the distance from the axis of rotation of the rotors to the center of the quadrotor. By same logic,<br><strong>moment _y = (F3 — F1) * L.<br></strong> Summing it up, moment around all 3 axis can be denoted by below vector<br><strong><em>moment</em> = [moment_x, moment_y, moment_z]^T </strong>(^T for Transpose)</p><p><strong>3. Orientation and position</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/244/1*yCGg7KDarsZVgzWu-CR7Ng.png" /><figcaption>Figure 3: Orientation and position</figcaption></figure><p>A drone has positional as well as orientational attributes, meaning to say it can be any position (x, y, z coordinates) and can be making certain angles (theta (θ), phi (φ) and psi (ψ)) with respect to world / Inertial frame. Above figure shows theta (θ), phi (φ) and psi (ψ) more clearly.</p><p><strong>4. Moving in z and x &amp; y direction</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*4Bw1uDQZ6-a_y4UYJ0aOxA.png" /><figcaption>Figure 4: Moving in z and x &amp; y direction</figcaption></figure><p>Whenever a drone is stationary, it’s in alignment with World frame, meaning to say its Z axis is in same direction as World’s gravitational field. During such a case, if a drone wants to move upwards, it just needs to set proper propeller rotating speed and it can start moving in z direction according to equation <em>total generated force — gravity. </em>However, if it wants to move in x or y direction it first needs to orient itself (making required theta or phi angle). When that happens, total thrust generated by four propellers (F_thrust) has a component in z direction and in x/y direction as shown in above 2D figure. For above shown example, using basic trigonometry, we can find z and y directional force by following equation, where phi is angle made Drone’s body z axis with world Frame.<br> <strong><em>F_y </em>​= <em>F</em>_thrust * ​sin<em>ϕ<br></em> <em>F_z </em>​= <em>F</em>_thrust * ​cos<em>ϕ</em></strong></p><p><strong>5. World and Body frame</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/364/1*O1x8UDVWzgQT1LBuIIJj9g.png" /><figcaption>Figure 5: World and Body frame</figcaption></figure><p>To measure above stated theta, phi and psi angles, usually drone’s onboard IMU sensor is used. This sensor measures how fast drone’s body is rotating around its body frame and provides that angular velocity as its output. When processing this IMU outputs, we need to be careful and understand that angular velocities sent by it are not with respect to World frame, but are with respect to its Body Frame. Above diagram shown both this frames for reference.</p><p><strong>6. Rotation Matrix</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*IVB10XJOyuA51I5ICY3KgA.png" /><figcaption>Figure 6: Rotation Matrix</figcaption></figure><p>To convert coordinates from Body Frame to World Frame and vice versa, we use a 3x3 matrix called Rotation Matrix. That is, if V is a vector in the world coordinates and V’ is the same vector expressed in the body-fixed coordinates, then the following relations hold:<br>V’ = R * V and<br>V = R^T * V’ where R is Rotation Matrix and R^T is its transpose.<br>To understand this relation completely, let’s begin by understanding rotation in 2D. Let the vector V be rotated by an angle β to get the new vector V′. Let r=|V|. Then, we have the below relations:<br>vx = r*cosα and vy = r*sinα<br>v’x = r*cos(α+β) and v’y = r*sin(α+β). Expanding this, we get<br>v’x = r * (cosα * cosβ — sinα * sinβ) and v’y = r * (sinα * cosβ + cosα * sinβ)<br>v’x = vx * cosβ — vy * sinβ and v’y = vy * cosβ + vx * sinβ<br>This is exactly what we want because the desired point V’ is described in terms of the original point V and the actual angle β. For conclusion we can write this in matrix notation as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/296/1*AOgmarRZZR3cvXx0J3dAxg.png" /></figure><p>Going from 2D to 3D is relatively simple in Rotation Matrix’s case. In fact, the 2D matrix we just now derived can actual be thought of as an 3D rotation matrix for rotation around z axis. Hence, for a rotation around z-axis the Rotation Matrix would be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*0vB1R9LkZZdJwBbTBXnALA.png" /></figure><p>0, 0, 1 in values in last row and column indicate that z coordinates for rotated point (v’z) is same as original point’s z coordinate (vz). We will call this Z axis Rotation Matrix as Rz(β). Extrapolating same logic to rotations around x and y axis, we can get values for RX(β) and RY(β) as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/449/1*EV2koAiwFihdwrWFnniM9Q.png" /></figure><p>And final value for 3D motion Rotation Matrix will just be cross multiplication of above three Rotation Matrices.<br><strong>R = Rz(ψ) x Ry(θ) x Rx(φ)</strong>, where psi (ψ), phi (φ,) and theta (θ) are rotation around z, y, and x axis respectively.</p><p><strong>7. State Vector and its Derivative<br></strong> As our drone has 6 degrees of freedom, we usually track it by monitoring this six parameters along with their derivatives (how they are changing with time) to get an accurate estimate of drone’s position and velocity of movement. We do this by maintaining what is often called a state vector <strong>X = [x, y, z, φ, θ, ψ, x_dot, y_dot, z_dot, p, q, r]</strong> and its derivative <strong>X_dot= [x_dot, y_dot, z_dot, θ_dot, φ_dot, ψ_dot, x_doubledot, y_doubledot, z_doubledot, p_dot, q_dot, r_dot] </strong>where x, y and z are position of drone in World frame, x_dot, y _dot, and z_dot are positional / linear velocities in World Frame. φ, θ, ψ represent drone attitude / orientation in World frame whereas φ_dot, θ_dot, ψ_dot represents rate of change of this (Euler) angles. p, q, r are angular velocities in body frame whereas p_dot, q_dot and r_dot are its derivate (derivative = rate of change) aka angular acceleration in body frame. x_doubledot, y_doubledot, z_doubledot represents linear accelerations in World Frame.</p><p><strong>8. Linear Acceleration<br></strong> As briefed before, whenever propellers are moving, drone will start moving (accelerating) in x, y and z direction depending upon total thrust generated by it’s 4 propellers (represented by Ftotal in below equation) and drone’s orientation (represented by Rotation Matrix R). We know force = mass * acceleration. Ignoring Rotation Matrix R, if we just consider acceleration in z direction, it would be given by<br> Z_force = (mass * gravitational force) — (mass * Z_acceleration)<br> mass * Z_acceleration = mass * gravitational force — Z_force<br> And therefore <strong>Z_acceleration = gravitational force — Z_force / mass<br></strong> Extrapolating it to x and y direction and including Rotation Matrix (for reasons described in section 4 and 6), equation describing linear acceleration for a drone is given by below equation, where <em>m</em> is mass of drone and <em>g</em> is for gravitational force. Negative sign in F indicates that we are considering gravitational force to be in positive z direction.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*5kp9ZDdzqJsEuCrI3B5RyQ.png" /><figcaption>Linear Acceleration</figcaption></figure><p><strong>9. Angular acceleration<br></strong> Along with linear motion, owing to rotating propellers and its orientation, drone will also have some rotational motion. . While it is convenient to have the linear equations of motion in the inertial / world frame, the rotational equations of motion are useful to us in the body frame, so that we can express rotations about the center of the quadcopter instead of about our inertial center. As mentioned in section 4, we will use drone’s IMU to get its angular accelerations. Let’s consider output from IMU be p, q and r, representing rotational velocities around drone’s x, y and z body axis.<br>We derive the rotational equations of motion from Euler’s equations for rigid body dynamics. Expressed in vector form, Euler’s equations are written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/270/1*rFXCVHIbdU8ALf9CYJ-uyw.png" /><figcaption>Euler’s equations for rigid body dynamics</figcaption></figure><p>where ω = [p, q, r]^T is the angular velocity vector, I is the inertia matrix, and <em>moment</em> is a vector of external moment / torques developed in section 2. . Please don’t get confused with usage of ω (as angular velocity) in this section with it’s usage as propeller’s rotation rate. We will stick to usage of ω as rotation rate post this section. We can rewrite above equation as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/345/1*WaI6MT4m1FuXWO9B-uNyvg.png" /></figure><p>Replacing ω with [p, q, r]^T, expanding <em>moment </em>vector and reshuffling above equation we get angular accelerations in body frame as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*4NWo64BXe-bO5S5Xu2-bSg.png" /><figcaption>Angular Accelerations in Body Frame</figcaption></figure><p><strong>10. Rate of change of the Euler angles<br></strong> Although drone’s orientation is originally observed in Body frame, we need to convert them to World Frame. Again, we use rotation matrix as per below formula for this purpose. The derivation of this formula is little elongated and is provided in the Reference [6]</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*05rtPoLEAF6ez5vUrg-cSA.png" /><figcaption>Rate of Change of Euler Angles</figcaption></figure><p><strong>11. Recap<br></strong> So to recap what we have learnt so far<br>1. A quadcopter has 4 (2 CW and 2 CCW) rotating propellers<br>2. Each Propeller creates F =K_f * <em>ω</em>² force in direction perpendicular to its plane and Moment M = K_m * <em>ω</em>² around it’s perpendicular axis.<br>3. A drone can be in any x, y, z position and theta (θ), phi (φ) and psi (Ψ) orientation.<br>4. When a drone wants to move in z direction (in World Frame) it needs to generate appropriate force (total thrust divided by 4) on each propeller. When it wants to move in either x or y direction (again World Frame), it makes respecting theta / phi angle along with generating required force<br>5. When tracking drone’s motion, we need to handle data in World and Body Frames<br>6. To convert angular data from Body Frame to World Frame, a Rotational Matrix is used<br>7. To track drone’s movements, we keep track of its state vector X and its derivative X_dot<br>8. Rotating propellers generate linear accelerations in x, y and z direction as per equation shown in section 8<br>9. Rotating propellers generate angular accelerations around z, y and z axis in Body frame as per equation shown in section 9<br>10. We convert angular velocities in Body Frame to World Frame Euler angle velocities as per equation shown in section 10.</p><p><strong>12. References<br></strong>I don&#39;t want to just list down references, but instead would like to sincerely thank individual authors for their work, without which this article and the understanding which I have gained for drone dynamics would have been almost impossible.<br>1. System Identification of the Crazyflie 2.0 Nano Quadrocopter by Julian Forster — <a href="http://mikehamer.info/assets/papers/Crazyflie%20Modelling.pdf">http://mikehamer.info/assets/papers/Crazyflie%20Modelling.pdf</a><br>2. Trajectory Generation and Control for Quadrotors by Daniel Warren Mellinger — <a href="https://repository.upenn.edu/cgi/viewcontent.cgi?article=1705&amp;context=edissertations">https://repository.upenn.edu/cgi/viewcontent.cgi?article=1705&amp;context=edissertations</a><br>3. Quadcopter Dynamics, Simulation, and Control by Andrew Gibiansky — <a href="http://andrew.gibiansky.com/downloads/pdf/Quadcopter%20Dynamics,%20Simulation,%20and%20Control.pdf">http://andrew.gibiansky.com/downloads/pdf/Quadcopter%20Dynamics,%20Simulation,%20and%20Control.pdf</a><br>4. A short derivation to basic rotation around the x-, y- or z-axis — <a href="http://www.sunshine2k.de/articles/RotationDerivation.pdf">http://www.sunshine2k.de/articles/RotationDerivation.pdf</a><br>5. How do you derive the rotation matrices? — Quora — <a href="https://www.quora.com/How-do-you-derive-the-rotation-matrices">https://www.quora.com/How-do-you-derive-the-rotation-matrices</a><br>6. Representing Attitude: Euler Angles, Unit Quaternions, and Rotation Vectors by James Diebel — <a href="https://www.astro.rug.nl/software/kapteyn/_downloads/attitude.pdf">https://www.astro.rug.nl/software/kapteyn/_downloads/attitude.pdf</a></p><p>If you liked this post, Follow, Like, Retweet it on <a href="https://twitter.com/percyjaiswal">Twitter</a> or Claps, Likes here on Medium will act as encouragement for writing new posts as I continue my journey into Blogging world.</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ee98b1ba882f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/demystifying-drone-dynamics-ee98b1ba882f">Demystifying Drone Dynamics!</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sensor Fusion — Part 2: Kalman Filter Code]]></title>
            <link>https://medium.com/data-science/sensor-fusion-part-2-kalman-filter-code-78b82c63dcd?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/78b82c63dcd</guid>
            <category><![CDATA[autonomous-vehicles]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[kalman-filter]]></category>
            <category><![CDATA[machine-learning]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Fri, 24 Aug 2018 06:10:46 GMT</pubDate>
            <atom:updated>2018-11-03T05:02:50.379Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sKpJmj16sJwoAIkAlhkYgQ.jpeg" /></figure><p>In <a href="https://towardsdatascience.com/sensor-fusion-part-1-kalman-filter-basics-4692a653a74c">Part 1</a>, we left after deriving basic equations for a Kalman filter algorithm. Here they are stated again for easy reference.</p><p>A. Predict:<br> a. X = A * X + B * u<br> b. P = A * P * AT * Q<br>B. Measurement<br> a. Y = Z — H * X<br> b. K = ( P * HT ) / ( ( H * P * HT ) + R )<br>C. Update<br> a. X = X + K * Y<br> b. P = ( I — K * H ) * P</p><p>We will be coding above equation in this post, using sensor readings from a text file which is freely available at Udacity’s github handle. This text file (<em>obj_pose-laser-radar-synthetic-input.txt</em>) has sensor readings from Laser and Radar along with reading’s timestamp and ground truth values. Till this point, we have only covered basic Kalman filter algorithm, hence in this coding exercise we will only be using Laser readings from the above stated input file. Once we cover ‘Extended Kalman Filter’ in future post, we will start using Radar readings too. But with our current understanding of Kalman Filter equations, just using Laser readings will serve as a perfect example to cement our concept with help of coding.</p><p>Sensor readings captured in input text file are in below format.</p><p>For a row containing radar data, the columns are: sensor_type (R), rho_measured, phi_measured, rhodot_measured, timestamp, x_groundtruth, y_groundtruth, vx_groundtruth, vy_groundtruth, yaw_groundtruth, yawrate_groundtruth.</p><p>For a row containing lidar data, the columns are: sensor_type (L), x_measured, y_measured, timestamp, x_groundtruth, y_groundtruth, vx_groundtruth, vy_groundtruth, yaw_groundtruth, yawrate_groundtruth.</p><p>With all this information at our fingertip, let’s begin coding without any further delay . As with any Python file, let’s import all required libraries first</p><pre>#**************Importing Required Libraries*************<br>import numpy as np<br>import pandas as pd<br>from numpy.linalg import inv</pre><p>Next, read input text file containing sensor readings.</p><pre>#*************Declare Variables**************************<br>#Read Input File<br>measurements = pd.read_csv(&#39;obj_pose-laser-radar-synthetic-input.txt&#39;, header=None, delim_whitespace = True, skiprows=1)</pre><p>I have made ‘skiprows’ parameter as 1 because, when we begin implementing KF algorithm, we don’t have any prior knowledge about state of vehicle. In such cases usually we default our state to first reading from sensor output. And this is exactly what we will be doing. In below shown code, we will initialize our state <strong><em>X</em></strong> with reading from first row of input file. And as this reading has already been used, we simply skip it while reading input file. Along with initial values of state vector <strong><em>X</em></strong>, we will also use first <em>timestamp</em> from input file as our <strong><em>previous time</em></strong><em>. </em>As explained in previous post, we need current and previous timestamps to calculate <strong><em>delta_t</em></strong><em>.</em> Timestamps provided are in unit microseconds, which we will divide by 10⁶. This has two reasons, first, a smaller number is easier to maintain. Second, the velocity groundtruth readings (and hence velocity values in our code) are in units of <em>seconds.</em></p><pre># Manualy copy initial readings from first row of input file.<br>prv_time = 1477010443000000/1000000.0<br>x = np.array([<br>        [0.312242],<br>        [0.5803398],<br>        [0],<br>        [0]<br>        ])</pre><p>Next, we Initialize variables to store ground truth and RMSE values. RMSE (Root Mean Square Error) is used to judge performance of our algorithm against ground truth values.</p><pre>#Initialize variables to store ground truth and RMSE values<br>ground_truth = np.zeros([4, 1])<br>rmse = np.zeros([4, 1])</pre><p>We initialize matrix <strong><em>P</em></strong> and <strong><em>A</em></strong>. For details about structure of <strong><em>P</em></strong> and <strong><em>A</em></strong> matrices, refer to <a href="https://towardsdatascience.com/sensor-fusion-part-1-kalman-filter-basics-4692a653a74c">Part 1</a> where its explained in more depth. Basically matrix <strong><em>A</em></strong> is used to implement kinematics equations of distance, speed and time, and matrix <strong><em>P</em></strong> is State Covariance Matrix having variances in <em>x, y, vx</em> and <em>vy</em> as its diagonal elements. What this initial <strong><em>P</em></strong> values mean is that we have high confidence in our positional values (which makes sense as we have taken it from actual sensor readings), indicated by relatively low variance value, and low confidence in velocity values (which again makes sense as we have no idea about velocity), indicated by relatively large variance value.</p><pre>#Initialize matrices P and A<br>P = np.array([<br>        [1, 0, 0, 0],<br>        [0, 1, 0, 0],<br>        [0, 0, 1000, 0],<br>        [0, 0, 0, 1000]<br>        ])<br>A = np.array([<br>        [1.0, 0, 1.0, 0],<br>        [0, 1.0, 0, 1.0],<br>        [0, 0, 1.0, 0],<br>        [0, 0, 0, 1.0]<br>        ])</pre><p>Next we define <strong><em>H</em></strong> and <strong><em>I</em></strong> matrices, which, as I explained in last post, will be 4 x 2 and 4 x 4 matrices respectively. We define vector <strong><em>Z</em></strong>, which, as our Lidar readings will consist of 2 positional readings (x and y), will be a 2 x 1 vector.</p><pre>H = np.array([<br>        [1.0, 0, 0, 0],<br>        [0, 1.0, 0, 0]<br>        ])<br>I = np.identity(4)<br>z_lidar = np.zeros([2, 1])</pre><p>We define Measurement Covariance matrix <strong><em>R</em></strong>, which again, as per last post will be a 2 x 2 matrix. We will talk more about how to get values for <strong><em>R</em></strong> matrix and <strong><em>noise_ax</em></strong> and <strong><em>noise_ay</em></strong> in future articles.</p><pre>R = np.array([<br>        [0.0225, 0],<br>        [0, 0.0225]<br>        ])</pre><p>Next we define <strong><em>noise_ax</em></strong>, <strong><em>noise_ay</em></strong> and matrix <strong><em>Q</em></strong>.</p><pre>noise_ax = 5<br>noise_ay = 5<br>Q = np.zeros([4, 4])</pre><p>Let’s take few moments to understand them. If we revisit kinematics equations defined in 1st part of this series, you can see that there is an acceleration factor in positional and velocity terms. They have been rewritten here for ease.</p><ol><li>Px(t+1) = Px + delta_t * vx + 0.5 * ax * delta_t²</li><li>Py(t+1) = Py + delta_t * vy + 0.5 * ay * delta_t²</li><li>Vx(t+1) = Vx + ax * delta_t</li><li>Vy(t+1) = Vy + ay * delta_t</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/332/1*Yw3U9rHIonB5o44A0JVvkQ.png" /></figure><p>Since the acceleration is unknown we can add it to the noise component, and this random noise would be expressed analytically as the last terms in the equation derived above. So, we have a random acceleration vector <em>v</em> in this form, which is described by a zero mean and a covariance matrix <strong><em>Q.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/147/1*KGh-ppbBlYZH6K50MflbNQ.png" /></figure><p>The vector <strong><em>v</em></strong> can be decomposed into two components a 4 by 2 matrix G which does not contain random variables and a 2 by 1 matrix <em>a</em> which contains the random acceleration components:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/490/1*rwU2OtGKev_Tr4omTWpc5Q.png" /></figure><p>delta_t is calculated at each iteration of Kalman Filter, and as we don’t have any acceleration data, we define acceleration <strong><em>a</em></strong><em> </em>as random vector with zero mean and standard deviations noise_ax and noise_ay. Based on our noise vector we can define now the new covariance matrix Q. The covariance matrix is defined as the expectation value of the noise vector <em>v</em> times the noise vector <em>v</em> transpose. So let’s write this down:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*3kifoOgBrucWtjeheiUY7A.png" /></figure><p>To know more about ‘Expected Value’, watch <a href="https://youtu.be/j__Kredt7vY">this</a> video from Khan Academy. As G does not contain random variables, we can put it outside the expectation calculation</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/505/1*RKtmd49ZNF-yElMyeEwnnA.png" /></figure><p>ax and ay are assumed to be uncorrelated noise processes. This means that the covariance sigma_axy in Q is zero.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/393/1*MJ2t3C79ighIQeDx6ccY1Q.png" /></figure><p>So after combining everything in one matrix we obtain our 4 by 4 Q matrix:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*0m-n6cFW5BgopOr9L83VMw.png" /></figure><p>At each iteration of Kalman Filter, we will be calculating matrix Q as per above formula. With all our variables defined, let’s begin with iterating through sensor data and applying Kalman Filter on them. Running a for loop till length of measurements, reading measurement line, checking if it’s a Lidar (‘L’) reading.</p><pre>#**********************Iterate through main loop********************<br>#Begin iterating through sensor data<br>for i in range (len(measurements)):<br>    new_measurement = measurements.iloc[i, :].values<br>    if new_measurement[0] == &#39;L&#39;:</pre><p>Get timestamp from current reading, calculate change in time by comparing it with previous timestamp and then replace current timestamp as previous timestamp for next iteration.</p><pre>        #Calculate Timestamp and its power variables<br>        cur_time = new_measurement[3]/1000000.0<br>        dt = cur_time - prv_time<br>        prv_time = cur_time</pre><p>Calculate delta_t’s (‘dt’ in code) square, cube , and 4th power of delta_t which are required to calculate Q matrix.</p><pre>        dt_2 = dt * dt<br>        dt_3 = dt_2 * dt<br>        dt_4 = dt_3 * dt</pre><p>Updating matrix A with delta_t value. Delta_t will be multiplied by velocity to come up with positional values.</p><pre>        #Updating matrix A with dt value<br>        A[0][2] = dt<br>        A[1][3] = dt</pre><p>Updating Q matrix. If you look back at above derived equations for Q matrix, you can easil corelate below provided lines of code with that.</p><pre>        #Updating Q matrix<br>        Q[0][0] = dt_4/4*noise_ax<br>        Q[0][2] = dt_3/2*noise_ax<br>        Q[1][1] = dt_4/4*noise_ay<br>        Q[1][3] = dt_3/2*noise_ay<br>        Q[2][0] = dt_3/2*noise_ax<br>        Q[2][2] = dt_2*noise_ax<br>        Q[3][1] = dt_3/2*noise_ay<br>        Q[3][3] = dt_2*noise_ay</pre><pre>        #Updating sensor readings<br>        z_lidar[0][0] = new_measurement[1]<br>        z_lidar[1][0] = new_measurement[2]</pre><pre>        #Collecting ground truths<br>        ground_truth[0] = new_measurement[4]<br>        ground_truth[1] = new_measurement[5]<br>        ground_truth[2] = new_measurement[6]<br>        ground_truth[3] = new_measurement[7]</pre><p>And finally call Predict and Update functions.</p><pre>        predict()<br>        update(z_lidar)</pre><p>Now lets have a look at our predict() function which would very much similar to the following predict equations that we been using in this series. Not much to explain in the code section, its really just a direct replica of derived formulas.<br>A. Predict<br> a. X = A * X + B * u<br> b. P = A * P * AT * Q</p><pre>#**********************Define Functions*****************************<br>def predict():<br>    # Predict Step<br>    global x, P, Q<br>    x = np.matmul(A, x)<br>    At = np.transpose(A)<br>    P = np.add(np.matmul(A, np.matmul(P, At)), Q)</pre><p>Moving ahead to define update() function. We will be implementing both ‘measurement’ and ‘update’ steps in this function.<br>B. Measurement<br> a. Y = Z — H * X<br> b. K = ( P * HT ) / ( ( H * P * HT ) + R )<br>C. Update<br> a. X = X + K * Y<br> b. P = ( I — K * H ) * P</p><pre>def update(z):<br>    global x, P    <br>    # Measurement update step<br>    Y = np.subtract(z_lidar, np.matmul(H, x))<br>    Ht = np.transpose(H)<br>    S = np.add(np.matmul(H, np.matmul(P, Ht)), R)<br>    K = np.matmul(P, Ht)<br>    Si = inv(S)<br>    K = np.matmul(K, Si)<br>    <br>    # New state<br>    x = np.add(x, np.matmul(K, Y))<br>    P = np.matmul(np.subtract(I ,np.matmul(K, H)), P)</pre><p>…and with that, you have gone through complete code for a Kalman Filter algorithm. Even though it might look like a small step, this is the foundational algorithm for many of the advanced versions used for Sensor fusion technology. As stated earlier, all variants of Kalman Filter consists of same Predict, Measurement and Update states that we have defined in this series so far. The only difference in more advanced versions is the different kinematics and sensor equations they use. We will go through them too step by step in this series. But at this moment, lets have a high five for finishing our foundation step of a classic Kalman Filter Algorithm. You can find complete code along with input file at my github repo <a href="https://github.com/PercyJaiswal/Kalman_Filter">here</a>.</p><p>As usual, if you liked my article, show your appreciation with likes and comments. You can also find me and my other articles at <a href="https://twitter.com/percyjaiswal">twitter</a></p><p>Till next time, cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=78b82c63dcd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/sensor-fusion-part-2-kalman-filter-code-78b82c63dcd">Sensor Fusion — Part 2: Kalman Filter Code</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sensor Fusion — Part 1: Kalman Filter basics]]></title>
            <link>https://medium.com/data-science/sensor-fusion-part-1-kalman-filter-basics-4692a653a74c?source=rss-6173b8e69840------2</link>
            <guid isPermaLink="false">https://medium.com/p/4692a653a74c</guid>
            <category><![CDATA[autonomous-vehicles]]></category>
            <category><![CDATA[ai]]></category>
            <category><![CDATA[kalman-filter]]></category>
            <dc:creator><![CDATA[Percy Jaiswal]]></dc:creator>
            <pubDate>Sat, 11 Aug 2018 23:04:43 GMT</pubDate>
            <atom:updated>2018-08-11T23:04:43.039Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*sKpJmj16sJwoAIkAlhkYgQ.jpeg" /></figure><p>In this series, I will try to explain Kalman filter algorithm along with an implementation example of tracking a vehicle with help of multiple sensor inputs, often termed as Sensor Fusion.</p><p>Kalman filter in its most basic form consists of 3 steps. A) Predict — Based on previous knowledge of a vehicle position and kinematic equations, we predict what should be the position of vehicle after time t+1. B) Measurement — Get readings from sensor regarding position of vehicle and compare it with Prediction C) Update — Update our knowledge about position (or state) of vehicle based on our prediction and sensor readings. And that’s it. All variants of Kalman filter are just different variants of above 3 steps, depending upon different Kinematic equations you want to use and different kind of sensor reading which you want to incorporate in algorithm. But regardless of variants, all Kalman filter implementation consists of above mentioned 3 steps. So let’s analyze them using vehicle tracking example.</p><p>A. Predict</p><p>Using basic equations of velocity, distance and time, we know that if position of my vehicle at time <em>t</em> is at <em>x</em> location, then at time <em>t+1 </em>the vehicle will be at location x + ((t + 1) — t) * v, where v is velocity of vehicle. Digging in further, if we have acceleration value available with us, we can add it to above equation and update new position of vehicle to x + ((t + 1) — t) * v + 0.5 * a * ((t + 1) — t)2. Formalizing above equations, lets denote current state of vehicle, which consists of its current location and velocity as a vector x. So vector x will have 4 elements, namely px, py, vx, vy; representing position and velocity in x and y directions respectively.</p><p>In order to keep our example as simple as possible (but not simpler than it needs to be), we will be tracking vehicle in 2 dimensions, which is a fair estimate considering we don’t have flying cars yet 😊. The positional x and y distances are with respect to our vehicle’s own position. So if we say a vehicle is at position px and py, we mean that it is at a distance of px and py from our vehicle.</p><p>Moving on, let’ define velocity and acceleration as velocity and acceleration vectors having velocity and acceleration data in x and y direction respectively. We will denote change in time as delta_t. With this, our individual equations for tracking position and velocity becomes:</p><p>1. Px(t+1) = Px + delta_t * vx + 0.5 * ax * delta_t 2</p><p>2. Py(t+1) = Py + delta_t * vy + 0.5 * ay * delta_t 2</p><p>3. Vx(t+1) = Vx + ax * delta_t</p><p>4. Vy(t+1) = Vy + ay * delta_t</p><p>Without going into details, one thing we should understand is that performing matrix operation is much more computationally effective than solving individual equation. A simple justification being, if we consider above 4 equations, a controller (the actual microcontroller who will be performing operations in 1’s and 0’s) will need to perform following actions 4 times. i) Create a variable Px(t+ 1), ii). get value of Px iii). get value of delta_t iv). get value of vx v). get value of ax vi). perform mathematical operations vii). store result. All these operations will have to be performed one time each for each equation. To explain analogy better, let’s say your mom asks you to go to grocery and bring some Onions (being analogous to getting Px, vx, ax values from memory). Being the obedient child you are, you go immediately and bring it. She then asks you to cut them (analogous to mathematical operations), you do that, and then just when you were about to watch your Football game, she asks you to bring Tomatoes from store. Again, being the obedient child, you go back and bring tomatoes, gather all equipment (knives, cutting pad and a bowl to keep them), cut tomatoes and store it for her. And then she asks you to bring some fruits…and them some more. You get the gist here, suffice to say, you won’t be a happy kid that evening. Wouldn’t it have been sooooo much better if your mom had given you all the list of things to bring and instructed you to cut them before you start your tasks. Same goes for computers. (Must admit, I have been waiting to write the analogy 😊)</p><p>Coming back to 1s and 0s, lets convert our 4 individual equations into following matrix form. So now our 4 equation gets clubbed together and they look like this.</p><p>x_new = A * x + B * u where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MaQHT-LfjvssRgZlszejQg.png" /></figure><p>Taking first row from above matrix equation</p><p>px_new = [(1 * px) + (0 * py) + (delta_t * vx) + (0 * vy) ] + [ (0.5 * delta_t * delta_t * acceleration_x) + (0 * acceleration_y) ]</p><p>px_new = px + delta_t * vx + 0.5 * acceleration_x * delta_t 2</p><p>which is same as one we had come up with before converting individual equations to matrix form. Here matrix A and B are just matrices representing kinematic equations for position, velocity and acceleration.</p><p>Oh, but wait..uuhh…mom is asking ..to….go…bbaacck…to grocery (and she is apologetic about it this time)…so you snap back and say hey mom, I got this football game to see, I cant go right now. And mom says <em>so tell me (</em><strong><em>Predict</em></strong><em>) when can you go.</em> And you reply <em>I will go in </em><strong><em>about</em></strong><em> 2 hrs. </em>So what’s the interesting part about this conversation you ask…well it’s the “about” part. As you can sense, you are little bit uncertain about the time when you can go back. You know it will be in 2 hrs, but there is little bit of +- 10 (or 15 or pick a number) minutes of uncertainty you are not sure about. Maybe there is lot of extra time added in game, maybe game is getting boring (read it as your team is losing) and you decide not to wait till end, or maybe it was a great victory in a derby match and you want to wait and watch after match celebration and expert analysis.</p><p>This uncertainty factor holds true for computers too. A thought might have entered your mind saying, so what’s so great about Kalman filter, above mentioned kinematic equations been known for decade, we can use it in matrix form if you like it and start predicting. But as Benjamin Franklin said <em>there are only two things certain in life: death and taxes</em>. So when we are asking computer to predict the value of our new state of vehicle, we need to ask it about its uncertainty too. In Kalman filter language this uncertainty is represented as covariance matric. Lets denote our State Covariance Matrix as</p><p>P = [variance_px, 0, 0, 0],</p><p>[0, variance_py, 0, 0],</p><p>[0, 0, variance_vx, 0],</p><p>[0, 0, 0, variance_vy]</p><p>where variance_px, variance_py, variance_vx, variance_vy represent uncertainty in predicted x position, y position, x velocity and y velocity respectively. All the remaining 0 terms are to say that uncertainty in one value is independent of other value, meaning to say my <em>position x</em> uncertainty is nothing to do with my uncertainty in y direction. This need not be true in every case. In some case the variables you are tracking may actually depend on each other. But we will use the simplistic approach here and make other values as 0. This actually makes it a ‘variance’ matrix, but covariance is much more widely used term.</p><p>At the risk of making our equations a bit complex, I want to introduce Process Noise Covariance matrix Q. In any covariance matrix calculations (which is matrix P in our case), you can have a certain amount of noise which needs to be added into it to come up with a new predicted covariance in the estimation.</p><p>As Kalman filtering is a continuously iterative process, we need to keep predicting the state vector along with its covariance matrix every time we have a new reading from sensor, so that we can compare the predicted value (step a) with sensor value (step b) and update our information about the vehicle we are tracking (step c). We already have equations for updating state vector, and the equation to update covariance matrix is as given below. And with this we conclude our step a of predicting with following two equations.</p><p>State vector: x = A * x + B * u</p><p>Covariance matrix: P = A * P * AT * Q</p><p>B. Measurement</p><p>Now let’s say we receive a sensor reading for the position of the vehicle we are tracking. Actually the sequence of operation is, we trigger Kalman filter calculation only when we receive sensor readings. The sensor reading will usually have a timestamp associated with each reading. We read that timestamp, calculate difference between timestamp of last reading and this one. Perform prediction as per above explanation using delta_t = timestamp difference between two readings and then come to Measurement and update part for sensor input. Commonly use sensors like Lidar and Time of flight sensors will give you readings regarding position of a vehicle, but not its velocity. So our sensor reading will be of form vector z = [px, py]. As stated before, we need to compare this measurement value with the value predicted in step a. But looking at both vectors (predicted state vector x and measurement vector z), we see that both are of different order. Hence to convert state matrix to same size as z, we introduce matrix “H”. Getting into matrices basics, to convert a 4 x 1 ‘<em>x’</em> matrix to 2 x 1 ‘<em>z’</em> matrix (while keeping top two values as it is and removing velocity variables) we use a 2 x 4 matrix H. So the equation comparing predicted value with measurement becomes y = z — Hx, which gives us the difference between both values.</p><p>Well, in this step, we will also be calculating Kalman gain. This gain factor is basically used to decide final value for vehicle state, choosing an appropriate value between predicted and measurement one’s. We have already seen uncertainty in predicted value as State Covariance matrix P. The corresponding uncertainty matrix for measurement readings is Measurement Covariance matrix, denoted with letter R. Our state variable was having 4 variables (x, y position and velocity) so its covariance matrix was a 4 x 4 matrix. As stated before, lets consider that our sensor just gives us positional reading in x and y directions. In that case our Measurement Covariance Matrix will be of 2 x 2 shape as shown below.</p><p>R = [ [variance_in_pos_x_reading, 0]</p><p>[0, variance_in_pos_y_reading]</p><p>Obviously, while deciding on final value, we want to lean on more towards the value which has less uncertainty. In <em>Kalman gain</em> value, we compare uncertainty in predict and measurement methods by calculating percentage of uncertainty in predicted value to that of total uncertainty. In other words</p><p><strong>Kalman Gain = Uncertainty in predicted state / (Uncertainty in predicted state + Uncertainty in measurement readings).</strong> We know uncertainty in predicted state is matrix P and that in measured value is matrix R. But as you can see, both of them are of different size. Hence we use H matrix to convert P matrix to correct size. With that the Kalman Gain equation becomes =&gt;</p><p>K = ( P * HT ) / ( ( H * P * HT ) + R )</p><p>H Matrix required to calculate Kalman Gain with a 4 x 4 P Matrix and 2 x 2 R matrix will be as shown below</p><p>H = [ [1, 0, 0, 0],</p><p>[0, 1, 0, 0] ]</p><p>Again, the padding of H matrix around P matrix is only for matrix operation, please don’t let it scare you. Kalman gain is just a simple percentage formula.</p><p>Well, with precited value, measure value and Kalman gain values in hand, its time to move to update state, where we make final update to state vector x and its corresponding covariance matrix P.</p><p>C. Update</p><p>I can’t make this step complex even if I want to so I am just gonna give you equation for our final state vector -&gt; x = x + Ky. Imagine we are very confident in our predicted value, then our covariance P will have very small variance values. This in turn will make Kalman Gain ( which is <em>Uncertainity in predicted state / Uncertainity in predicted state + Uncertainity in measurement readings</em>.) a small number as final equation will be of form <em>small number / (small number + big number)</em>. In this case, if we consider final x equation, we take our predicted value and just add a small portion of it’s difference (that is, difference between predicted and measured values) to measured value. Because Kalman gain will be a small value as per above theory, equation of x will be of form; x = x + (small number * y)</p><p>As you can see, this will cause final x to lean more towards predicted value, which is in line with starting assumption we made that we have high confidence in predicted value compared to measured value. Similarly, the equation to update covariance matrix is P = (I-KH) P. Again, H matrix is used for matrix manipulations.</p><p>And with that we have all the tools required to implement a complete Kalman Filter with following equations</p><p>A. Predict:</p><p>a. X = A * X + B * u</p><p>b. P = A * P * AT * Q</p><p>B. Measurement</p><p>a. Y = Z — H * X</p><p>b. K = ( P * HT ) / ( ( H * P * HT ) + R )</p><p>C. Update</p><p>a. X = X + K * Y</p><p>b. P = ( I — K * H ) * P</p><p>Similar to my other articles, I wanted to add toy code for this post too, but it was getting quite a lengthy read. I would definitely be adding it in a subsequent part in this series which I plan to complete on Sensor Fusion using Kalman Filter.</p><p>As usual, if you liked my article, show your appreciation with likes and comments. You can also find me and my other articles on twitter</p><p>Till next time….cheers!!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4692a653a74c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/data-science/sensor-fusion-part-1-kalman-filter-basics-4692a653a74c">Sensor Fusion — Part 1: Kalman Filter basics</a> was originally published in <a href="https://medium.com/data-science">TDS Archive</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>