Hilbert’s 17th question crossed from pure mathematics into real-world application around the year 2000. That’s when several different researchers figured out an algorithmic method for checking whether a polynomial is a sum of squares. They achieved this by translating the sum of squares question into a “semidefinite program,” which is a type of problem that computers know how to handle. This, in turn, made it possible for researchers in fields like computer science and engineering to use the power of nonnegativity to guide their search for optimal ways of solving problems.
But semidefinite programming has a big limitation: It is slow on large problems and can’t handle many of the most complicated polynomials researchers really care about. Semidefinite programming can be used to find a sum of squares decomposition for polynomials with a handful to about a dozen variables raised to powers no higher than about 6. The polynomials that characterize complex engineering problems — like how to ensure a humanoid robot stays on its feet — can involve 50 or more variables. A semidefinite program could chew on that kind of polynomial until the end of time and still not return a sum of squares answer.
In a paper posted online last June, Ahmadi and Majumdar explain a way to get around the slowness of semidefinite programming. Instead of trying to find a sum of squares decomposition by solving a single, slow semidefinite program, they show how to do it using a sequence of simpler problems that are much faster to compute.
These types of problems are called “linear programs,” and they were developed in the 1940s to answer optimization problems related to the war effort. Linear programs are now well understood and quick to solve. In their new work, Ahmadi and Majumdar show that you can solve many linked linear programs (or, in some cases, another kind of problem known as a second-order cone program) and combine the results to get an answer that’s almost as good as the answer you could get with a semidefinite program. The upshot is that engineers have a new, practical tool that they can use to test for nonnegativity and find sum of squares decompositions quickly.
“We looked at a number of problems from robotics and control theory and demonstrated that the quality of solution we were getting was still useful in practice and much quicker to compute,” said Majumdar.
The speed of solution means everything when you’re in a self-driving car. And in that situation, a polynomial can serve as a kind of mathematical barrier around obstacles you don’t want to hit — if you can find it fast enough.
Imagine a simple example: a self-driving car in a giant parking lot. There’s nothing in the lot except for a guard booth at the far end. Your goal is to program the car so that it will never drive into the booth.
In this case, you’d start by putting a coordinate grid on the lot. Now make a polynomial that takes points on the grid as inputs. Make sure that the value of the polynomial at the location of your car is negative, and the value at the location of the guard booth is positive.
At some set of points between your car and the booth, the polynomial will cross over from negative to positive. Since your car is allowed to be on points only where the polynomial is negative, these points form something like a wall.
“If I start in a certain location, I’m not going to cross to the other side of the line where the obstacle is. This gives you a formal proof of safety for collision avoidance,” said Ahmadi.
Now, it’s no good if this wall is midway between the car and the booth. You want to craft your polynomial so that the wall hugs the obstacle as closely as possible. This fences off the guard booth while giving the car plenty of space to move around.
In practice, you want to minimize a value — the distance between the wall and the booth — and so you shift the graph of the polynomial around to see how far you can push it before it ceases to be nonnegative. And you’re probing that line by testing whether the shifted polynomial remains a sum of squares.
A near-empty parking lot is one thing. But in realistic driving scenarios, a car’s sensors continually identify new and shifting obstacles — cars, bikes, kids. Every time a new obstacle appears, or an existing one moves, the car has to come up with elaborate new polynomials to fence them off. That’s a lot of sum of squares checks to do on the fly.
Seven years ago a different pair of researchers imagined that it might be possible to use such polynomial techniques to segregate autonomous cars from places they shouldn’t go. But at the time, computational speed made the idea a pipe dream.
Ahmadi and Majumdar’s new approach provides a way for carrying out such rapid-fire calculations. So, if and when self-driving cars are able to navigate the world safely, we’ll have Google and Tesla to thank — and also David Hilbert.
(562) 340-6284
