Ceres: solving complex problems using computing muscle

Today, Sameer Agarwal and Keir Mierle (as well as a couple others I'm sure) at Google open sourced the Ceres Non-Linear Least Squares Solver.

Since coming to Google, this is probably the most interesting code library that I have had a chance to work with. And now, you can use it too.   So, what exactly is a "non-linear least squares solver"? and why should you care?

It turns out that a solver like Ceres is at the heart of many modern computer vision and robotics algorithms. Anywhere you have a bunch of observed sensor data about the world and you want to create an explanation of all those observations, a non-linear least squares solver can probably do that for you. For example, if you have a bunch of distance sensors and you want to figure out where you are relative to the walls. Like this:



Or if you have a camera, and you want to figure out the position of the camera and objects in view:



Or say you have a quad copter, and you want to model how it will respond to thrust on different propellers:



or (as in the case of Google Street view) combining vehicle sensors in the cars with GPS data:



or even figure out the best way to position your plant so it gets the most amount of sun (assuming you could accurately measure the amount of sun hitting the leaves):

Non-linear least squares solvers, like Ceres, are a tool for optimizing many variables simultaneously in a complex model/formula to fit some target data. Many of the advanced engineering problems today come down to this.  It's basically a fancy version of your typical line fitting problem:

This is linear least-squares. The model here is:

y = m*x + b

This is "linear" because it is the simple addition of a scaled variable m*x and a constant b.  It is "least-squares" because it minimizes the square of the distance between the line and each of the data points. In this simple case, that algorithm is simply solving for m and b in the line equation. There are methods for directly computing these values. But, if the equation was non-linear such as:

y = (m*x - cos(x))^2/b

You now need a non-linear least squares solver.  Many real world problems are non-linear such as anything that involves rotation, camera projection, multiplicative effects, or compounding/exponential behavior.  You might be able to devise a clever way to calculate the optimal values for m and b directly, or you can use an iterative algorithm and let the computer tweak the values of m and b until the squared error to your data is minimized. While this example also only has two variables, Ceres can handle optimizing thousands of variables simultaneously and uses techniques for reaching an error minimizing solution quickly.  Though, it's important to note that it can only iteratively crawl toward the lowest error solution starting from the initial values of m and b you provide... like a drop of water sliding down to the bottom of a bowl.   If the bottom of the bowl is very bumpy, it can get stuck in one of the smaller divots and never reach the lowest part of the bowl.  This is known as getting stuck in a "local minima" and never finding the "global minimum" and the shape of the bowl is called the "cost surface".  When the cost surface of a problem is not very bowl-like, it can lead to problems.

Ceres can also handle something called "sparsity" efficiently.  This occurs when you have many many variables, but only a few of them interact with each other at a time. For example, the current position of a flying quad copter depends on the previous position and previous velocity. But, the current velocity doesn't really depend that much on the previous position.  Imagine if you made a giant table with all your input variables in the column names and all of your output values in row names and then put check mark in the table where ever the input was used to compute the output.  If most of the table is empty, then you have a "sparse matrix" and Ceres can take advantage of this emptiness (which indicates independence of the variables) to dramatically increase the speed of computation.

Anywhere you that have data, and you have a model (which just a fancy term for complicated formula) that should be able to generate that data and you want to tweak the values inside your generative model to best fit your data... a tool like Ceres might do the job.

For many problems, mathematicians and engineers have spent decades devising clever and complex formulas to solve them directly. But in many fields, having a computer perform non-linear optimization on data is becoming the preferred method because it makes it much easier to tackle very complicated problems with many variables, and often the result can be more stable to noisy input.

The neat thing about using a non-linear solver in a real-time system, is that the computer can respond to feedback in much the same way you do.  If an object is too far to the left of a target position, it knows to move it right.  If the wind starts blowing, and it drift backwards it will automatically respond by pushing forward.  As long as you have an equation to explain how the output will be affected by the controls.  It can figure out the best way to fiddle with the controls to minimize the distance from a target value.

If I find the time, I might try to post some tutorials on using Ceres. Because I believe this is one of the most powerful tools in modern engineering, and no one ever taught it to me in undergrad or high school.  It's like the difference between doing long division by hand and then being handed a calculator.

Projects at Google X

These past couple weeks, there have been a few videos released from the group I work in at Google. Congratulations to the many people in X who's hard work has gone into each of these.

Computer Controlling a Syma Helicopter

Recently, I've been playing with these inexpensive Syma Remote Control Helicopters. At the time they were only $20 (but seemed have been price adjusted for the holidays). They're quite robust to crashes and pretty easy to fly. For $20, they're a blast. The other interesting thing about these copters is that the controller transmits commands using simple infrared LEDs rather than a proper radio. This simplicity makes it tauntingly appealing to try reverse engineering. So tonight, I decided to do a little procrastineering and see if I could get my helicopter to become computer controlled.

For hardware, I've been liking these Teensy USB boards because they are cheap, small, versatile, and have a push-button boot loader that makes iteration very quick. They can be easily configured to appear as a USB serial port and respond to commands. For the IR protocol, I started with this web page which got the helicopter responding. But, the behavior I was getting was very stuttery and would not be sufficient for reliable autonomous control. So, I decided to take a closer look with an oscilloscope to get accurate timing from the stock remote control. Some of my measured numbers were fairly different for the web tutorial I found. But, now the control is fairly solid. So, here is the nitty gritty:

IR Protocol:

- IR signal is modulated at 38KHz.
- Packet header is 2ms on then 2ms off
- Packet payload is 4 bytes in big-endian order:
1. yaw (0-127) default 63
2. pitch (0-127) default 63
3. throttle (0-127 for channel A, 128-255 for channel B) default 0
4. yaw correction (0-127) default 63
- Packet ends with a stop '1' bit

Format of a '1' is 320us on then 680us off (1000us total)
Format of a '0' is 320us on then 280us off (600us total)

Packets are sent from the stock controller every 120ms. You can try to send commands faster, but the helicopter may start to stutter as it misses messages.

Download Teensy AVR Code (updated 11/30/2011)

The code is available at the above link. It's expecting 5 byte packets over the serial port at 9600 baud. The first byte of each packet must be 255, followed by yaw, pitch, throttle, and yaw correction (each ranging from 0-127). It will return a 'k' if 5 bytes are properly read. If it doesn't receive any serial data for 300ms, it will stop transmitting the IR signal.

Unfortunately, I can't help you write a program to communicate over serial since that will depend on your OS (Windows, Mac, Linux) and varies by language as well. But, it is fairly easy with lots of web tutorials. The harder challenge will be figuring out how to update the 3 analog values to keep it from crashing. =o) The most likely candidate is to use a camera (probably with IR markers) to monitor the position of the helicopter. But, getting that to work well is definitely a project unto itself.

Good Luck!

Shredder Challenge - Puzzle 2 done! Onto Puzzle 3

Puzzle 2 is now done! Puzzle 3 is a drawing (not text).

As we get to more complicated puzzles, it's clear that loading, rendering, and UI limitations will become a bigger and bigger issue. My colleague, Dan Maynes-Aminzade ("monzy" for short) is doing his best to figure out ways to handle that. There are a lot of not-ideal solutions.

It's also clear that more computer aided matching will be necessary to maintain progress. Here are zip files for the pieces of problem 4 and problem 5, if you want to try your hand at analyzing them directly.

Puzzle 4 pieces
Puzzle 5 pieces

If you come up with good ideas that work, post them in the comments.

Puzzle 1 done overnight!

Puzzle 1 was completed overnight! Very cool. They definitely get harder. But, the crowd helped UCSD complete puzzles 2 and 3 within a couple of days. So, we could easily catch up.

On to puzzle 2

DARPA Shredder Challenge - you could win $50,000

On October 27th, DARPA announced their Shredder Challenge. Try to unshred 5 documents for $50,000. There has been a few notable efforts such as UCSD's web based approach. But, that page has recently been compromised due to malicious users.

With the help of a few colleagues, we had also created a web-based version very early on. But, it was missing some of the login engineering and UI of the UCSD effort. So, we never made it public. But rather than attempt to build a full on competitor, we've decided to open up the tool we built for anyone to try to win the contest themselves!

http://www.unshred.me/1

You can create a private branch of each puzzle if you want to try to give it a go alone, or you can contribute to the main public copy of the puzzle. If our image analysis tinkering goes well, we may add some tools to help make finding matches easier.

NOTE: The deadline for submitting answers to DARPA is December 4, 2011 (11:59PM EST)! Only 13 days left.

GO!

Technology as a story

Generally, I consider myself a technologist. I work in technology, I choose environments that have people who are excellent at it. New technologies make the world move forward. If it is shared broadly enough, it is impossible to "un-invent" a technology and thus the world has been irrevocably changed, even if just by a little bit.

However, what saddens me is when I encounter technologists with the brilliance to create new and wonderful things, but lack a sense of what is beautiful to people. Technology is most often known for being ugly and unpleasant to use, because technologists most often build technology for other technologists.

But to touch millions of people, you have to tell a story - a story that they can believe in, a story that can inspire them. Technology is a tool by which new stories can be crafted. They are not the end product unto themselves. All too often, I find engineers and researchers who are eager to build the technology without understanding the story that goes around about why people should care, why what they built can be inspiring rather than just enabling.

It is not a skill you learn at school. I have encountered people who understand this, and others who don't. I can't say that I have mastered this ability. However, I can at least respect how powerful it can be and strive to be better at it.

As an engineer, as a technologist, as a researcher, or inventor... I encourage you understand the power of stories. A story isn't merely the sequence of events in a book or film. It can be a story about you, and how your life or the lives of the people around you could be a bit different... or how the world could be different than it is today.

It is inspiring to see what a talented artist can do with the very simplest of tools. I recently came across the following video which I feel exemplifies this idea.

When you build something or design something, take a moment to imagine the stories than can be told around what you create and to share that story with others.