Sunday, March 25, 2018

Update To AHRS with Mag!

Since my previous post on AHRS types, I have made some additional changes to the three systems.  Specifically, I have added the magnetometer data as an update to the yaw in each system.  My technique for adding the mag in each system was derived from this paper by Sebastian Madgwick.

The idea is that the Earth's magnetic field can be described as having a components in a single horizontal axis and a single vertical axis.  By rotating these components inversely, by our quaternion, we can directly compare our results to the measured magnetic field vector.  This was especially helpful because it simplified the equation for R in the EKF and UKF, because I could directly use square of the rms-noise of the magnetometer sensors as the diagonals of the matrix.

The toughest part of this problem was deriving each of the equations for Madgwick, the EKF and the UKF.  I would post it my work, but it is extremely tedious.  However, the results are very good and you can see that it clearly improved the yaw from the previous post in all three cases.

This was an extremely exciting result for me to see, because I worked very hard on the solutions.  The one area that I need to work on is when to provide updates to the EKF and UKF.  Currently, I use an accelerometer threshold, just to make sure there is no movement.  However, this causes the system to be very sensitive to slight movements.  Preferably, I would like to make a more robust system for performing updates.  That's all for now!

Tuesday, March 20, 2018

Testing Some AHRS Algorithms

 https://github.com/team401/Vision-Tutorials/wiki/Yaw-and-Pitch
In recent weeks, I have spent some time brushing up on as many types of Attitude and Heading Reference Systems (AHRS) as I can.  I wanted to code them, and compare them in a meaningful way and eventually implement them on an Arduino.  My initial goal has been to work with three types: The Madgwick Filter, an Extended Kalman Filter and an Unscented Kalman Filter.  As of right now, I have each of them working and am able to play back a few different types of csv datasets.  All of my code is on my github.

I should note that I collected data from my phone, which is a Google Pixel, that holds a BMI160 IMU sensor with a 3 axis accelerometer, 3 axis gyroscope, 3 axis magnetometer, a barometer and a temperature sensor.  I am sampling the data using an app called HyperIMU (available on the Google Play Store).  As of right now, I have only integrated the gyroscope and the accelerometer and am working on the magnetometer updates.

All of my implementations are very simple models, that do not yet introduce the gyroscope bias as parameter in the filter.  This will be added later, because it complicates the model.  My states are the quaternion values: w, x, y, z and all operations are done in quaternion space in order to avoid the singularity when the pitch is at 90 degrees.

The Madgwick Filter is based on this paper by Sebastian Madgwick.  Remarkably, it is a very new algorithm, but has been widely used across many systems.  The idea of this filter is to incorporate updates to the classic gyroscope integration via an optimization assumption.  The initial update is to correct for drift in the pitch and roll directions by taking advantage of the direction of gravity from the accelerometers.  Essentially, the algorithm forms an objective function between the gravitational vector rotated into the frame of the sensor and the acceleration vector in the frame of the sensor.  The idea is that at all times, the acceleration is an approximation of the gravity, even though there may be some acceleration due to movement and noise.  The optimization is solved with a gradient descent solution and is therefore, always attempting to correct any drift originating from the gyroscope in the gravity related directions.

Here is an image of the results of the Madgwick filter when applied to my phone spinning along the three axes.  This is particular run is using the recommended beta gain value from the paper, however, I have found that setting it to between 0.04 and 0.2, allows it to converge faster and more accurately.
As you can see in the image, the prediction of roll, pitch and yaw works well. In the roll and pitch directions, you can see that the filter is slowly converging back to 0 degrees.  If I increase the beta value, I can speed up that convergence, but it comes at the cost of factoring in any acceleration that is not due to gravity.  To see the divergence, I decided to compare residual between the estimate and the measurement.  What is interesting to see is what happens when we have actual movement of the phone and how it causes divergence in the filter values.

The Extended Kalman Filter

The EKF is the standard equation for most estimation problems and it fits well for the AHRS, as well.  Essentially, the EKF is a typical Kalman filter that linearizes the prediction and update equations in order to estimate the uncertainty of each of the states.  The uncertainty is used to weight measurement updates in order to shrink the overall error of the system.  When the sensor is moving with extra acceleration, the gravity updates are far more damaging than they are in the Madgwick filter.  In order to mitigate this problem, I decided to only apply updates when the change in acceleration along all three axes is less than a threshold. This way, we know that the phone is stationary during this period.  In the future, I will work on a more robust way to find allowable update times.

Here is the results of the EKF.  The Euler plot shows fast convergence back to 0 degrees in the pitch and roll after rotations.  We can see a bit more noise in the solution than Madgwick Filter, but faster convergance.  This is probably because the linearized function does not approximate the uncertainty distribution as well.
I have only plotted the residuals when I have done updates.  As you can see, the residual is zero mean and has a nice error distribution after the updates.  This means that the filter is doing its job.

The Unscented Kalman Filter

The UKF was a curious addition to this batch of algorithms.  Typically, a UKF is used if there is an unclear distribution function.  It works by creating a distribution from a few "Sigma Points", which are projections of the system states with a fraction of the noise added back in.  This creates a pseudo space that approximates the distribution of the uncertainty of each state.

This image was very helpful in my understanding of the UKF.  Basically, a proportion of the standard deviation of the uncertainty is added to each state and then either projected forward in time by the state transition matrix or rotated to the measurement frame.
 https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/10-Unscented-Kalman-Filter.ipynb
Here are the results of the UKF.  Again, we are seeing good results in terms of convergence back to zero after large movements in pitch and roll.  We also see that we have somewhat Gaussian Error in the residual.

Here are the histograms of the Roll and Pitch error.  Both are very Gaussian and has almost exactly the same amount of mean and error as the EKF.

Now that I have this done, I have a few other things that I want to do to improve my results.  These things include:
• Yaw correction via Magnetometer
• Gyroscope bias correction, also with the Magnetometer and possibly the Temperature Sensor
• Process and Measurement noise improvement via adaptive EKF
• Implementation in C for realtime estimation on Arduino

Thursday, February 15, 2018

Update On RNN's for Predicting Crypto Prices

 This is a Recurrent Neural Network diagram from here

Sporadically, I have been working on this little project to both learn more about recurrent neural networks and build something useful to predict future cryptocurrency prices.  As I talked about before, I have been looking into ways of predicting the price on a rolling basis.  As of right now, I am predicting the next day's price from a history of 6 days before.  Let's take a look at what I did.

Recurrent Neural Networks are a good choice for this type of timeseries because they can incorporate new values and keep track of history in order to make new predictions.  I am using Keras to create the network and here is how I built it:

```lookback=6
model = Sequential()
batch_size = 1
model.compile(loss='mse', optimizer='rmsprop', metrics=['mae'])```

As you can see, I used 4 Long-Short Term Memory blocks and a lookback of 6 days.  I used "rmsprop" as my optimizer because it is essentially a more advanced gradient descent method which is usually fine for regression tasks.  The Loss Metric chosen was Mean Square Error, which is the classic loss function for regression problems.  I am also keeping track of Mean Absolute Error, just to confirm the results.

The data in this example consists of BTC/USD daily closes from January 2016 to February 2018.  This is the plot of that data.
Before training, I scale the data between 0 and 0.9 to account for higher prices in the future, with a Min-Max Scaler from Sci-kit Learn.  In the future, I may try dividing by 1 million instead, to better account for future prices (I don't see it hitting 1 million any time soon, but it could in the future).   Then I split the data into training and testing datasets with a 67% training split.  During the train, I also check a 20% validation set, just to watch how each iteration of the model performs.  I have plotted these values during the train.  This allows me to see at what point the model begins to over-train. We can see this by looking at the point at which the validation loss (MSE) significantly diverges from the training loss.  This is an image of that plot, with the validation loss filtered to discard noise:

In this example, I have trained to 1000 iterations.  It is kind of tough to see the divergence, but it happens around 125 iterations.  I am curious if I were to leave it training for 10,000 iterations, whether there might be a more clear divergence point.  Anyway, if we train to about 125 iterations, we get a result that looks like the one below.  The green line is the prediction of trained data and the red line is the prediction of the untrained portion of the data.  Although the result is clearly worse, I am pretty happy with how well it did.

The results are as follows:
- On Trained data the RMSE is 44.67
- On Test data the RMSE is 1342.08

The question is, how can I improve this result?  My initial thoughts are to experiment with different look-back values, and possibly more LSTM blocks.  However, I suspect that the most practical way to improve the result is to also add in open's, high's and low's as features as well.  This may vastly improve the model because it will be able to see momentum and other patterns at each timestep.  This where I will focus next.

Tuesday, February 13, 2018

Some Computer Vision For Kicks

Over the past few weeks, I have been working on a few different projects to broaden my skills and learn about some new technologies.  One area that I have been jumping into is computer vision.  Recently, I have been working my way through the book "OpenCV with Python Blueprints".  Some of the projects I have done so far include building a Cartoonizer and some Feature Matching.  Let me show you!

This is me just after finishing the Cartoonizer.  As you can see, the program cartoonizes live video and shows the result in real-time.  The process involves:
- Applying a bilateral filter in order to smooth flat areas while keeping edges sharp
- Converting the original to grayscale
- Applying a median blur to reduce image noise
- Using an adaptive threshold to detect edges
- Combining the color image with the edge mask

The result is really great!

Another project I just completed is the Feature Matching project.  The idea here is to find robust features of an image, match them in another image and find the transform that converts between the two images.

Here is an examples of what that looks like in practice.  On the left, is the still image that I took from my computer and on the right is a live image of the scene.  The red lines show where the feature in the first frame is located in the second frame. This seemed to work pretty well for very similar scenes, but had some trouble when I changed the scene significantly.  However, it is not unexpected that it would fail on different scenes, because the features are not very similar at all.

Here is how I did it:
- First I used SURF (Speeded-Up Robust Features) to find some distinctive keypoints.
- Then, I used FLANN (Fast Library for Approximate Nearest Neighbors) to check whether the other frame has similar keypoints and then match them.
- Then, using outlier rejection, I was able to pare down the number of features to only the good ones.
-  Finally, using a perspective transform, I was able to warp the second image so that it matched the first (not shown here).

I am currently in the middle of the 3D scene reconstruction project.  This something I have been meaning to do for a long time and I am currently really enjoying working on it.

Tuesday, January 30, 2018

Cryptocurrency Analysis

It's been a while since I last posted, because I was working hard over at Navisens.  After about 3 years, I am now back on the market looking for a new position.  In the meantime, I have started working on another project that has fascinated me for a while.

For about a year now, I have been looking into and trading cryptocurrencies.  I find the whole market exciting to follow and very lucrative (if you do it right).  This is where my new project comes in.   I am building a tool for querying historical cryptocurrency price data in order to analyze and use it for making future price predictions.  My current progress is located on my Github.

To get started, I have built a simple api that uses the phenomenal ccxt api to query from tons of exchanges to build up data. Then, once I have a significant amount of data, I will test some machine learning algorithms on that data.

Here are some questions that I am starting to think about:

- How is one cryptocurrency related to another?  Can I use the data from one crypto to train a classifier/regressor for predicting a different crypto?

- What type of Machine Learning algorithms will work best on this time-series data? Neural Networks? Recurrent Neural Networks?  Decision Trees? Bayesian Estimators?

- What features should I use as inputs to the ML algorithms?  Do I need scaling? (probably)  How many features will be sufficient?

- What should I predict? A new price (regressor)? Whether it will go up or down (classifier)?

As I start to look at these problems more carefully, I will continue to write about the conclusions that I come to.  If you have questions or thoughts, I would love to hear them! Feel free to comment on this post or send me an email!

Wednesday, April 15, 2015

A Kalman Filter for a Robot Car

This past week, I have spent quite a bit of time working on a simulator for a two-wheel differential drive robot.  The idea was to use simulated encoder and range finder data and an Extended Kalman filter to determine the location of a robot.  My implementation is written in Python and hosted here.

The system is modeled as having two inputs - The left and right wheel speeds.  The robot is externally given control inputs, but they are unknown to the Kalman filter.  The only inputs to the Kalman filter system are the encoder values and the range finder values and a set of known landmarks (this is to simulate mapping or some other landmark detection).  The encoder inputs are Vl and Vr.  From these values, we can surmise the average velocity V, and the rotational velocity w of the robot.
V = (Vl + Vr)/2
w = (Vr - Vl)/L, where L = length between wheels
We can then use the image below to determine the simple version of the equations of motion of the robot.
 An image of a differential drive robot.
From this system, we can surmise that the equations of motion, in discrete form, are:
x(k+1) = x(k) + V(k)*Cos(theta(k))*dt
y(k+1) = y(k) + V(k)*Sin(theta(k))*dt
theta(k+1) = theta(k)  + w(k)*dt
This means that we can assign the system states to be X, Y and Theta.  Because the system model above is ideal, we also need to add in a Gaussian noise value for each state. Now the system looks like this:
x(k+1) = x(k) + (V(k) + Nv) *Cos(theta(k))*dt
y(k+1) = y(k) + (V(k) + Nv) *Sin(theta(k))*dt
theta(k+1) = theta(k)  + (w(k) + Nw)*dt
The Kalman filter has two steps. The prediction step, and the update step.  The prediction step uses the system model, previous state values and control inputs (in this case, encoder values) to create a prediction (a priori) of the new states of the system.  It also creates an estimate covariance matrix, that is essentially a mathematical way to determine how much you trust the sensor values and the prediction.  The matrices needed for the calculation of the prediction step are the A, G, Q and P matrices.  A is the Jacobian, with respect to the system states, for the model shown above.  G is the Jacobian with respect to the noise values.  Q is a matrix built up by the covariances of the process noise.   The prediction step equations are:
X^(k+1) = f (X(k), U(k)) , where f (X(k), U(k)) is the original system model
P^(k+1) = A*P(k)*transpose(A) + G*Q*transpose(G)
The update step (a posteriori) is a bit more complicated.  The idea is to use a separate sensor (or multiple) to improve the quality of the prediction.  In this case, we will use a range finder to find landmarks and use those landmarks to determine where we should be and correct the position.  Of course, the range finder is not a perfect sensor and has Gaussian noise too.  This will be included in our calculations.  There are 4 parts of the update step.  The first is to calculate the difference in the measured values (from the range finder) and the predicted values from the previous step.  The h matrix, or measurement matrix, puts the states from the last step into the same space as the measurement values.  Then, we also need to calculate the Kalman gain.  This gain is a matrix that tells us how much we want to use the new measurement to update the prediction.  It is calculated using the sensor covariance matrix, the estimate covariance matrix and the Jacobian of the h matrix, H.  Using the residual and the Kalman Gain, we update the state prediction.  Finally, we updated the covariance matrix, using the Kalman Gain and H matrix.  The actual formulas are laid out below.
Y = Z - h(X(k))
K = P^(k+1)*H*(H*P^(k+1)*transpose(H) + R)^-1
X(k+1) = X^(k+1) + K*Y
P(k+1) = (I - K*H)*P^(k+1)
In order to make the landmark detection work, the x and y positions of the landmarks were augmented to the states matrix. X.  By adding those values, the Kalman Filter became an EKF and many other matrices had to be changed, as well.   The reason for doing this, is to keep track of the landmarks and allow them to make changes to the prediction, only if they are seen.  In my case, they are always seen, but in an real-world scenario, the range finder might not be able to see all of the landmarks or misses them.

Here are some results of my work.  A typical run can be seen below.  In this image, the actual position of the robot is in blue, the initial prediction is in green and the final prediction (after landmark detection with 20 landmarks) is in red.  The robot tracks the random path very well over 2 minutes, with a time step of 0.1 seconds.
The error between the actual and updated paths for this run can be seen below.  There was an average RMS error of 3.45 units over the course of the path.  What is neat, is that the Kalman Filter seems to correct itself when there is a lot of error. If odometry was the only sensor used, the error would grow much faster, and it would not correct itself.

Tuesday, April 7, 2015

The Lidar-Lite Ranging Sensor

Currently, I am working with the new PulsedLight Lidar-Lite range sensor, a small Laser emitter/receiver that can measure distance in one direction.  It is a terrific sensor that I bought for only \$89 on-line.  A typical Lidar sensor is usually in the hundreds or even thousands of dollars, so this is quite a bargain, and something that the at-home maker can afford.  Not only is it cheap, it als has terrific accuracy and works with both PWM and I2C.

As of right now, I am writing a couple of libraries in Python and C++ to interface with the Lidar-Lite via I2C.  My work is currently posted here. Most of my experimentation has been using a Raspberry Pi with Rasbian Wheezy.  The idea is to make these libraries portable and then use them on a Robot Operating System (ROS) project, down the road.  Once the library is finished, I will post a quick tutorial on how to use it.   PusledLight also has a great repository of Arduino sketches for use the Lidar-Lite here.  I have tried them out and they work great.  Check it out!

Friday, March 13, 2015

3d Printer Reviews

One of the great perks of my job at Visa Labs is that I get to use 3d printers every day.  In my office, we have 4 printers that I have used extensively.  This post is a review of my experiences with these printers.

Flashforge Creator (\$977)
5 Stars

The Flashforge Creator is the first printer we received and has proven to be the most reliable, fastest, easiest to repair and simplest to use printer of them all.  The Creator is one of the many printers to be based off of the original Markerbot Replicator.  It can use the same firmware as the Makerbots and even the same software (Makerbot Desktop, which works well).  It is also open-source, so it is very easy to find information, replace parts, and use open source software like Slic3r or replicatorG.  It can also print most materials with relative ease and had dual extruders which was great for multi-color prints.  The print quality at 0.2 mm layer height is fairly good for an inexpensive printer.

The only downside that I saw with the Creator was that there would often be lifting off of the build plate due to uneven heat on the surface.  Making large parts can be difficult because the build space is rather small and often there will be some problem like filament getting stuck or the material not sticking to itself.  Most of these problems are easy enough to fix with software or with creative solutions.  By far this printer exceeded my expectations and I would highly recommend it to beginners and advanced users alike.

Solidoodle 4 (\$599)
4 Stars
The Solidoodle 4 is another quality printer on the lower price range end of the spectrum.  I particularly liked the enclosed build area and overall build quality of the printer.  It was simple to fix any problems and had a great filament spool holder and feeding hole covered in rubber.  There were never any filament feeding problems at all, which is great because pretty much every other printer gets jammed all the time.  It also prints both ABS and PLA, which was good.

The downsides that I found with this printer included the software (Repetier Host) and the warped build plate.  First, the software was very odd compared to other software out there.  It gives you lots of control and can manually move the printhead which was nice.  However, it was non-intuitive to use and had alignment issues.  If you pressed the Home button multiple times, the printer would home each axis to different places.  It also caused the printer to not print the object in the same place that you wanted it to be printed.  This was frustrating, but even more so was the fact that the build plate that came with the printer was completely warped.   Because there are only three adjustments screws under the plate, it was not possible to manually un-warp the plate, so we could only print small objects in the area that was not warped.  Besides these small problems, we got very good quality prints at 0.2 mm layer height.

Makerbot Replicator 5th Generation (\$2899)
3 Stars

Makerbot is probably the most well-known 3d printer company around, but I was not so impressed with the 5th Generation Replicator.  There were a few positives that I found.  First, the Makerbot Desktop software is very good (although it takes some time to learn how to customize it).  It is very simple to use and can create an SD card x3g  g-code file for other printers as well.  I also liked the beautiful navigation screen and control wheel.  It made it easy to do things like align and level the build plate.  The build quality at 0.2 mm was mediocre and had a lot of bumpy edges, but certainly wasn't awful.

The negatives, however, were numerous.  First off, you could only print PLA because the build plate was not heated.  For an almost \$3000 printer, that is pretty pathetic.  I also hated the new "Smart Extruder".  If by smart, they meant, gets jammed all the time, they did a great job.  Also, the blue tape they give you is absolutely useless.  From my experience, PLA does not stick to that stuff at all.  Also, the fact that the material is hidden inside the machine is awful, especially because the shape of the Makerbot spools are not the same as anyone elses.  If you want to use a 3rd party material, you have to make your own spool holder and hope that it works.  Lastly, I even had alignment issues with the onboard software.  The system thought the build area started in the middle and aligning it caused the print head to start bouncing off the wall repeatedly.  It was awful.

Having said all of this, I would love to try out the Replicator 2, because I have heard much better things.  But consider me unimpressed by this Replicator.

CubeX Trio (\$3295)
1 Star

I have to say that I was most excited to try the CubeX Trio because of its specs.  Huge build space, three extruders, great motors, high accuracy and so on.  Boy, was I way off.  This thing is a piece of junk.  It seems like it is very well built, looks nice and has a seemingly great print head with fans.  And the two full prints that I managed to make, came out pretty well. These are the only nice things I can say about this machine.

Here are the problems I faced using this printer.  The software is horrible.  It is hard to use, has basically no ability customize anything and worst of all, you cannot connect it to the printer.  This means that you have to get everything right with the design and then put that design on the provided USB stick and plug it into the printer.  There is a growing group of people who have switched over to Kisslicer (open source) and use a post-processor to convert the g-code to the .brb format that the printer reads.  This was not simple to figure out and took me a very long time.  Kisslicer, I will say, is a good program with a lot of functionality.  The next problem is that the folks over at CubeX tried to do WAY too much with the onboard software.  The leveling and alignment process is all in software, so inevitably there are problems with mechanical heights versus software heights.  Now the company says that this printer can be used with PLA or ABS.  If you use ABS, you should use the included glue stick because the build plate is not heated.  Again, this is ridiculous for a three thousand dollar printer, but I digress.  This glue is like superglue, especially with the plastic build surface.  After finishing (or not finishing) any print, it would take me an hour or more to remove the print from the surface.  This is absurd and frankly intolerable.  But the worst part of this printer was the printing experience.  The printer would heat up, start extruding into the waste bin, then do about ten movements around the build area for some reason.  Then it would start to print, but it would print so slowly, that it was impossible to print fist sized object in less than 24 hours.  I tried to adjust the speed with Kisslicer, but to no avail.  Then came the extruder jamming problem.  It seemed that every single print I ever did with the CubeX, the extruder got jammed.  The worst part about the printer getting jammed was that the onboard software did not give you an option to pause the print and change the filament.  IT JUST CANCELLED THE PRINT!  So, again and again, I would waste hours on a seemingly good print only to have it fail in the middle and ruin my day.  There were countless more problems with this printer, but these were the most pronounced. I would recommend no one ever buy a CubeX printer.

Tuesday, March 3, 2015

The Wandboard and It's Mysteries

The Wandboard
For a while, at work, I was building up embedded systems for our team to use as development platforms.  One board, in particular was the Wandboard.  It is an ARM development platform built on the Freescale IMX6.  Although, I had a lot of trouble with this board, I was able to learn quite a bit about embedded OS's.

The Wandboard has a many choices of Operating Systems and the website features a few standard images.  My goal was to use Linux and our flavor of choice was usually Ubuntu.  Trying out the Ubuntu image, provided by the Wandboard people, we found that it was generally fine, but it ran graphics remarkably slowly.  Many other people had found the same thing.  Also, any updates to the system caused crashes.  This was no good.  So instead, I began looking for alternatives.

One alternative that I spent a very long time on was Robert Nelson's eewiki post about compiling Linux for the Wandboard from scratch.  This allows you more customization and you can learn about how an OS is built up.  After doing this procedure, many problems occurred, including no screen (which was fixed with uBoot args), update failures (from wrong repos), X11 failures (due to graphics drivers not being compatible after updates), and so on.  This was frustrating.

Next, I tried Yocto.  At first, I didn't quite understand what Yocto was, but after using it, I became familiar.  Yocto is a custom archlinux setup that is built on a development machine with all of the possible packages that you need for the system.  It is meant for production environments where the system setup just needs to be flashed to the device and never touched again.  This wasn't really what I was looking for, but I tried it anyway.  Boy, does it need some work,  First of all, building a correct system could take months.  Using bitbake (the graphical package selection tool), the system would fail after many packages.  The system is cool because it goes out and downloads the necessary files (based on package requirement files), compiles them for your particular system and then installs them into the image.  However, there are so many opportunities to fail, that it takes forever to get to the end of a setup.  I was able to finish a few setups and they worked just OK.  In the future, I would try to plan out exactly what packages and dependencies I need and go from there.

Lastly, I tried some other images from the Wandboard Wiki.  Again, these worked pretty well, but always, I ran into some problem with display, graphics and other things.  One big area of concern to me, is that I could never find an image that allowed the Wifi to work and the graphics acceleration to work at the same time.  There were images that had one or the other, or you could download the drivers for the wifi (BRCM29), but never both.  This just shows that Wandboard needs some serious work.

Later, I was able to get a UDOO Quad, which is essentially the same hardware, and I put one of their stock images on it and it worked perfectly.  Honestly, I was amazed that Wandboard's are so popular because they are a trainwreck to use.

Monday, April 7, 2014

Particle Swarm Optimization

Since my last post, I have spent a lot of time learning about biologically inspired optimization techniques.  Some commonly used biological machine learning methods include genetic algorithms and neural networks.  However, I decided to dive a little bit deeper and try out a few newer algorithms.  The two algorithms I have been working with are called Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO).  In this post I will talk about PSO.

Particle Swarm Optimization
 This is a representation of Particle Swarm Optimization.  The solution that is found for a particle is swayed by the global best and the individual particle's best solutions.  http://www.sciencepubco.com/index.php/JACST/article/view/84

PSO is a stochastic technique that is based on the way that swarms move towards a goal.  Each particle is a potential solution (or bee in a swarm) and it moves in some direction with a velocity.  The velocity is determined by a combination of the individual particle's best solution, the global swarm's best solution and an inertia weight.  First developed by Kennedy and Eberhart in 1995, each particle is updated with the equations shown below:

 http://web.ist.utl.pt/gdgp/VA/pso.htm
The interesting equation above is the velocity update.  Essentially, the new velocity for particle i is the addition of the previous velocity for that particle times the inertia weight (a function of how many iterations we have performed), the randomly weighted difference between the particle and the particle best and the randomly weighted difference between the particle and the global best.  randomly uniform weighting of the differences is a way of introducing unpredictability into the equation so that the system does not get stuck at a local minimum.  The position update just adds the new velocity to the previous position.

The algorithm for performing these actions is fairly straight-forward as well.  The idea is to update each particle and determine if that particle has a better fitness value than it has ever had before, and then determine if it has a better fitness than the swarm's best fitness.  This way, each particle has the equivalent of a unique mind as well as the swarm mind.  Below is the algorithm specifics:

1. A set of N particles are created such that each particle contains random values in the set.
2. It is determined whether each particle is its best case, if it is, particle i's best is this particle.
3. It is determined whether the best particle is the swarms best case, if it is, the swarm best is this particle.
4. Each particle's velocity and position are updated simultaneously with the new particle and swarm bests.
5. If the global best meets the termination condition or the max iterations are reached, stop.  Else, go back to step 2 and repeat.
Using this algorithm, I was able to solve the N-queens problem.  My implementation can be found here, as a new Seeker in the Do-Anything-Machine.  In the N-queens problem, each particle is an array of rows containing a number that corresponds to a column for the position of each queen.  (For an explanation of the N-queens problem, see the previous post).  The fitness function is simply the number of queens that are on the same horizontals, verticals and diagonals of the chess board.  If the fitness of a particle is zero, the solution is correct.

One issue that I have noticed is that it can usually find a local minimum of the system, but does not always find a global minimum.  My solution was to repeat the algorithm multiple times, until the system met the fitness requirement.

Feel free to let me know what you think of my work in the comments.  I am happy to provide links and help to those who are interested.

Monday, March 24, 2014

The Do-Anything-Machine and the Hopfield Neural Network

Machine learning has become a new fascination for me in the past few months.  I have delved into the complicated world of solving problems with neural nets, genetic algorithms and clustering techniques.  Recently, I started work on the Do-Anything-Machine, a project started by Eric Neuman to build an artificial intelligence for solving any type of problem.  This is clearly a huge task, so it has been open-sourced.  To get involved, I have developed this method of solving the N-Queens problem.

The problem states that there are a number of ways to place N number of Queens onto a chess board with NxN squares, such that none of the queens can capture each other.  One way of solving this problem is by using a Hopfield Neural Network configuration.  A Hopfield net is a single-layer network in which all of the neurons are connected.  In our case, each neuron represents a square on the board, so there are N x N neurons.  Each neuron connection is weighted in a way that all of diagonal, horizontal and vertical squares from the initial square are added into that neuron, and the rest are weighted with zero.   The inputs are a random binary array, where each value in the array is an input into one of the neurons.  The output is also a binary array, with each value being an output from one of the neurons.
 This is an example of a Hopfield network with 6 neurons. (http://www.nnwj.de/hopfield-net.html)
The general method has two parts:
- The Internal process
- The External process

The internal process is an asynchronous method of changing the output of each neuron.
1. A random neuron is picked
2. The input potential of the neuron is calculated by summing the values of all of the horizontal, vertical, and diagonal queens from that square
3. This gives a value that is fed through a sigmoid function
4. The resulting output is then fed back as an input
5. The process repeats

The External process is performed after N x N iterations of the internal process.
1. The internal process is performed N x N times so that the inputs have a chance to evenly distribute
2. The energy (or cost function) of the entire board is calculated
3. If after 3 External iterations, the change in energy is zero, then the system has stabilized, and you have reached local minima
4. If it has not stabilized, then repeat the external process

Due to the amount of randomness, the system converges in anywhere from 3-25 external iterations.  The code for the initial implementation is here.  Please check it out and join in on the project!

Monday, August 12, 2013

Autonomous Quadricopter for Forest Fire Detection

I just recently finished my Master's Degree at Rochester Institute of Technology.  My final project was to design a control system for a Quadricopter that would be able to track forest fires as they spread.  All of the code is at https://github.com/Sanderi44/AR-Drone-Fire-Detection.  Here is the description from the paper:
"An autonomous control mechanism for tracking forest fires was designed with the use of an inexpensive, commercially available quadcopter.  The Parrot AR Drone 2.0 was chosen for this project because of its large open source programming community and many on-board sensors, including two cameras.  Image processing was performed on the video stream sent from the drone’s frontal, high definition video camera.  A few different fire detection algorithms were used with to make sense of the video data.  Then, after processing the video, object detection was performed to find the location of the fire.  Finally, the drone was told to move according to the location of the fire."
Below is the final presentation:

Wednesday, July 31, 2013

RIT Tigerbug Paper

I haven't written much about the Tigerbug project in a while, but I wanted to share the paper that our team wrote.  Please take a look and give any feedback that you have in the comments below.  I am very interested in what people have to say about the project!

Monday, July 22, 2013

Learning to Learn

I have always loved learning.  Sure, I haven't always made that point obvious, but in fact, it is true.  So as I depart the world of education for the excitement of the "real world", I can't help but reminisce about my glorious college days at Penn State and RIT.  But now, I am moving on; entering the unknown with nothing but the knowledge and skills I have acquired in 17 years of schooling.  From what I have heard from friends and read on the internet, I am as unprepared today as I was on the day I began school all those years ago.  But I disagree.  I have completed so many projects, homeworks and exams, spent countless hours researching, studying and taking notes. It has to count for something.  But what?  What do they count for?  I think the answer is that they have taught me how to work hard.  Sure everyone "works hard" once or twice in their life.  But at school, especially in my year at RIT, I have pushed myself to places I never thought I could go, almost daily.  I think my real education was in how to focus and complete a task to perfection.  At the end of the day, I am very proud of the work I have done.

Wednesday, July 17, 2013

The Sentience Stack

A good friend of mine, Eric Neuman, has proposed a roadmap to a living, motivated, creative, sentient being built entirely with Artificial Intelligence and computers.  The best part about the project is that it is open source (meaning github)!  The project is just beginning, but really seems to have legs.  Here is a more apt description of the project:

via simpleactually:
Artificial intelligence sounds awesome, doesn’t it? Machines that can solve problems on their own or answer questions for us would represent an enormous leap forward for all of mankind. The problem is, artificial intelligence as it exists today is not very flexible. Today, AIs are trading stocks, beating you at video games, filtering spam out of your email and handling a myriad of other tasks, each one specialized for its particular chore.
Therein lies the rub, each AI needs to be custom built by a programmer specializing in artificial intelligence or machine learning.  In other words, it is currently possible to build machines that learn, but these machines can not learn how to learn.  If we want machines that can truly solve problems, answer questions on their own, and eventually grow to be sentient minds, we need to overcome that obstacle.
I am joining in on this project and would encourage others interested in Artificial Intelligence to do the same.  Read more about the project at Eric's blog and get involved!

Tuesday, July 2, 2013

Extending the Range of the Drone

Another fascinating area that I have looked into has been how to extend the range of the drone.  After talking with another ham radio operator, the RFDude, I did some testing on my own.  He gave me a wifi antenna connector platform for me to test with and I built a 2.4 GHz "Cantenna" to try.  A cantenna is literally an antenna made from cans.  Surprisingly, it worked!  I followed these instructions for my build and added an extra can to improve the directionality and hopefully the distance.  Here's some pics after the break

AR Drone Developments

This past week has been chock-full of AR Drone developments.  First of all, I made the switch from Javascript (node.js) to Python development.  This was an important step because developing with Javascript was counter-intuitive and was becoming a pain for me.  I also wasn't interested in viewing the video online, but rather in an app on the computer, where I could do more filtering with OpenCV.  I am using a python library called libardrone (https://github.com/venthur/python-ardrone) that has given me control of the quadcopter with minimal complexity.  So far I have been able to do all sorts of development including autonomous and controlled flying.

Sunday, June 16, 2013

Getting to know the Parrot AR Drone 2.0

This summer, I am doing my final independent study project at RIT.  The project is to design a control mechanism for a quadcopter that can find a fire and track its movement.  This would be of use in a forest fire situation, where the quadcopter could track the fire as it moves, allowing the authorities to easily follow its progress via GPS.  I am using the Parrot AR Drone 2.0 as my vehicle because of its simplicity, great price, and awesome features.

The AR Drone includes:
- 2 HD Cameras that can be streamed back to a home computer
- Onboard 1 GHz Linux board
- Altitude sensors
- Full IMU (Inertial Measurement Unit)
- Protective foam padding (for when I inevitably crash it into something)

The drone comes ready to fly with IOS and Android apps that are available.  Right off the bat, I was able to record some video directly from the drone:

Sunday, June 2, 2013

Infrared Camera Hack

This summer I am doing a really cool project with a quadcopter and an infrared camera.  The idea is to create control system that uses image detection of a fire to fly around the fire and report its coordinates to a home computer.  In order for my project to work, I need an inexpensive digital infrared camera. A professor that I talked to told me that there is an easy way to modify a digital camera to an infrared (or close to IR) camera.  The method is to replace the visible spectrum filter that is in there with an IR filter.  After doing some research, it turns out that exposed 35 mm film negatives are excellent IR filters and can block out most of the visible range.  The goal of this project was to replace the filter in a webcam with an IR filter.  The result was a blurry, but usable IR camera.

First, I took apart an old Logitech webcam that I had lying around.  I took off the plastic casing and found the lens connected to the board.  This is what it looked like:
After removing the lens from the board, the filter sat on the back.  The lens could be unscrewed from the filter holder, so I removed that as well, being careful not to smudge the lens.  Lo and behold, inside the filter holder behind the lens was the visible spectrum filter.  I tried removing with a razor blade, but it did not budge, so I used the old brute force method and smashed it out.
More after the break

Wednesday, May 15, 2013

RIT Tigerbug

This is the RIT Tigerbug robot!  My partner, Andy Anthony and I designed, built and programmed this robot for our Advanced Robotics project at RIT.  The robot is built extremely solidly with 18 Roboard 1270 servos.  The body and legs are made of bi-weave carbon fiber and structural foam sandwich for added strength and reduced weight.  Currently it is being run by a windows PC communicating via serial cable, but we hope to implement an on-board computer such as the Roboard 100 Single Board Computer so that the robot will be completely wireless.  The robot is controlled by a wireless Xbox 360 controller and does a lot of processing.  Building this robot was a great experience, and I learned a ton about robotics.

CUPID Robot

So, it's been a while since I last posted.  I've been very busy working on my Master's degree.  Luckily, my degree is in robotics, so I have been working diligently on a few projects that I want to share.  During the winter quarter, I built a robot called the "CUPID" Robot.  It is a Nerf gun wielding autonomous robot, like those in Transformers.  It essentially finds the color red, aims at it and then shoots at it.  It uses a CMUCam4 to perform the color tracking, and has 2 little Hitec motors performing tilt/pan duties.  The onboard microcontroller is a Basic ATOM, so it is a little light on the processing.  However, the robot easily finds the color red and manages to hit it pretty accurately.  The toughest part was calibrating the color sensor to always find the color and not take in too much.  CMUCam4 is a cool little device that made it easy to do color tracking with the Basic ATOM.  I would love to use it in other projects with more advanced microcontrollers.  It's also a pretty good stepping stone to more advanced image processing techniques.

Here is a video of the CUPID robot:

Tuesday, September 25, 2012

What I Do at Work

This summer I have been working at a small company called Wells Research doing engineering design work. The company builds testing equipment for the optics industry.  The stuff that I am working on is really cool and I wanted to share a little about my experiences with the world.

Currently, I am working on a project to control a motor.  The motor controls the y position of a linear stage. Normally this setup is used to move a camera back and forth to adjust the focus.  Over the past month, I have been able to successfully model the position of the lens with MatLAB code.  The input of the system is kind of an odd function.  Instead introducing a force, the feedback control is done by inputting a trapezoidal or triangular velocity profile into the system's state space.  The input is essentially a curve that accelerates to a certain speed, holds that speed and then decelerates.  This tells the dynamic system to move a precise distance and then decelerate rapidly. It works quite well.

The biggest problem that I had was determining how the computer sends a signal to the motor.  There are constants that are defined in the program and the motor has a specific code developed by the company that gives it commands.  Determining what number to input in order to get a specific result was rather tricky, but eventually, after a lot of testing, I was able to get a suitable result.

The precise motor position was analyzed with an eddy current sensor.  I thought it was rather cool.  I attached a steel block to the top of the lens mount and then faced the sensor towards the block.  The sensor can read between 0 and 2 mm extremely precisely and the result can be measured with an oscilloscope and then converted to millimeters.  I really enjoyed testing and analyzing this system.  It was a lot of fun!

Sunday, July 1, 2012

We have movement folks...

So I finally got my autonomous robot code working! I would call this an alpha prototype, but it seems to work pretty well running around my kitchen. Take a look at the video below to see the DJ Ginobot in action.

This is an early prototype, but I am very pleased with my progress so far.  Eventually, I would like the robot to be scanning more frequently, so that it does not have to stop as much.  I am also having difficulty with the wheels turning at the same speed due to motor incongruity.  The best solution for this is encoders, which are a bit pricey.  However, for this project, they may not be necessary.

An idea that popped into my head yesterday about how I can take this project to the next level.  I have been reading about using MatLab to do mapping of space.  I could use my robot to perform mapping functions and send them wirelessly to the computer.  I could then use MatLab to interpret that data and make a map for me.  Imagine using this robot in a burning building where the firefighters don't know where to go.  They could send in the robot to map inside of the building for the firefighters outside.   Maybe this will be my next portion of the project.

Wednesday, June 6, 2012

Great Sites for Robot Enthusiasts

So, I wanted to add a list of sites that I find to be interesting, helpful and cool for robot lovers like me.  Here they are:

Tronixstuff - Great site for tutorials and reviews of kits.
Hackaday - Cool, new hacks and projects from around the web
DFRobot - Great for parts and tutorials
Let's Make Robots - Lots of awesome robots and a large forum
Yourduino - THE place to find parts on the cheap
RobotGrrl Blog - This girl makes a lot of robots and is quite good

These are just a few of the millions of sites out there for robotics.  A simple google search for robots will take you a long way.

Tuesday, June 5, 2012

Let's Get Moving...

This is a video of my robot taking infrared commands from an IHome remote that I rummaged from a pile of my junk.  I programmed the little guy in C and the code can be seen below.  I had to calibrate the motors to run at the same speed and they often don't go perfectly together.  If I used encoders, I could calibrate them much better, but that is a project for another day.

Monday, June 4, 2012

Arduino - The Do-Everything Microcontroller

In my wild hunt for robotic excellence, I came across the Arduino platform for robotics.  The Arduino is a microcontroller that is designed to be easy to use, program, wire-up and generally work with.  In search of a microcontroller, I ordered a version of the Arduino from dfrobot.com, called the DFRduino Romeo.  This particular version comes with two motor controllers built onto the board for easy access.  Otherwise, I would have had to build an H-Bridge circuit to control the motors.  Here is a picture of the Romeo in all of its glory:
Along with the Romeo, I ordered a robot platform called the Magician Chassis.  It is a small two wheeled chassis with motors included and an omni-wheel in front.  It is made with hobbyists in mind and is therefore perfect for my application.  Here is a picture of the Magician Chassis:
After everything arrived, I decided to put it all together and wire it up.  I have run some programs on it, but I will talk about those later...  Here is a picture of what my robot looks like now:

The ipod Amplifier

The first part of the project was to build a suitably loud ipod Amplifier that wouldn't break the bank.  I chose to follow this example:
I used the same circuit, but made some design adjustments to the casing and the speaker choice.  At first I used a speaker that I ripped out of an old telephone, but it overloaded in about 30 seconds.  So instead, I used a 2.5 inch, 8 ohm speaker from You-Do-It Electronics, which ran me about \$2.  I also found a pretty good looking box for my circuit lying around the house.  Here is the first edition of the assembly:
I used a cup to amplify the signal a little bit more.  However, after poorly soldering the circuit together, I had to re-do the whole thing and I ended up with a better result.  Here is an image of the new version's guts:

This little thing can pump a jam nicely and should work ever so well on the "yet to be named" robot.