CAMBRIDGE, MA—Engineers at the Massachusetts Institute of Technology (MIT) have developed a safety check technique that can prove with 100 percent accuracy that a robot’s trajectory will remain collision-free. Their method, which is so precise it can discriminate between trajectories that differ by only millimeters, provides proof in only a few seconds.
The engineers used a special algorithmic technique called sum-of-squares programming and adapted it to effectively solve the safety check problem. Using sum-of-squares programming enables their method to generalize to a wide range of complex motions.
“With this work, we have shown that you can solve some challenging problems with conceptually simple tools,” says Alexandre Amice, an electrical engineering and computer science graduate student at MIT. “Sum-of-squares programming is a powerful algorithmic idea, and while it doesn’t solve every problem, if you are careful in how you apply it, you can solve some pretty nontrivial problems.”
According to Amice, many existing methods that check whether a robot’s planned motion is collision-free do so by simulating the trajectory and checking every few seconds to see whether the robot hits anything. But, these static safety checks can’t tell if the robot will collide with something in the intermediate seconds.
Sometimes, these algorithms generate false positives, claiming a trajectory is safe when the robot would actually collide with something. Other methods that can avoid false positives are typically too slow for robots to use in the real world.
“Conceptually, one way to prove that a robot is not headed for a collision would be to hold up a piece of paper that separates the robot from any obstacles in the environment,” explains Amice. “Mathematically, this piece of paper is called a hyperplane.”
Many safety check algorithms work by generating this hyperplane at a single point in time. However, each time the robot moves, a new hyperplane needs to be recomputed to perform the safety check.
Instead, the new MIT technique generates a hyperplane function that moves with the robot, so it can prove that an entire trajectory is collision-free rather than working one hyperplane at a time.
“The key was figuring out how to apply sum-of-squares to our particular problem,” says Amice. “The biggest challenge was coming up with the initial formulation. If I don’t want my robot to run into anything, what does that mean mathematically, and can the computer give me an answer?”
While the approach is fast enough to be used as a final safety check in some real-world situations, it is still too slow to be implemented directly in a robot motion planning loop, where decisions need to be made in microseconds .
Amice and his colleagues plan to accelerate their process by ignoring situations that don’t require safety checks, like when a robot is far away from any objects it might collide with. They also want to experiment with specialized optimization solvers that could run faster.
