Now, MIT researchers have developed a safety-checking technique that can demonstrate with 100% accuracy that a robot's trajectory will remain collision-free (assuming the robot and environment models are accurate). Their method, so precise that it can distinguish between trajectories differing by only millimeters, provides the proof in just a few seconds.

But the user doesn't have to trust the researchers' word: the mathematical proof generated by this technique can be quickly verified with relatively simple mathematical operations.

The researchers achieved this using a special algorithmic technique called sum-of-squares programming, which they adapted to effectively solve the safety-checking problem. Sum-of-squares programming allows the method to be generalized to a wide range of complex motions.

This technique could be especially useful for robots that need to move quickly while avoiding collisions in cluttered spaces, such as robots preparing food in a commercial kitchen. It is also suitable for situations where robot collisions could cause injury, such as healthcare robots treating vulnerable patients.

"With this work, we have demonstrated that some difficult problems can be solved with conceptually simple tools. Sum-of-squares programming is a powerful algorithmic idea, and although it doesn't solve all problems, if applied carefully, it can solve some non-trivial ones," says Alexandre Amice, a graduate student in Electrical and Computer Engineering (EECS) and lead author of a paper on this technique.

Amice collaborated on the article with Peter Werner, another EECS student, and with Russ Tedrake, a Toyota Professor of Aeronautics and Astronautics and Mechanical Engineering at EECS, and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL). The work will be presented at the International Conference on Robotics and Automation.

Certify safety

Many current methods for checking whether a robot's planned movement is collision-free do so by simulating the trajectory and checking every few seconds whether the robot collides with anything. But these static safety checks cannot predict whether the robot will collide with something in the intervening seconds.

This may not be a problem for a robot wandering around an open space with few obstacles, but for robots performing intricate tasks in confined spaces, a few seconds of movement can make a huge difference.

Conceptually, one way to demonstrate that a robot is not heading for a collision would be to hold up a piece of paper that separates the robot from any obstacle in the environment. Mathematically, this piece of paper is called a hyperplane. Many safety control algorithms generate this hyperplane only once. However, every time the robot moves, a new hyperplane must be recalculated to perform the safety check.

In contrast, this new technique generates a hyperplane function that moves with the robot, so it can demonstrate that an entire trajectory is collision-free instead of working with a hyperplane each time.

The researchers used sum-of-squares programming, an algorithmic tool capable of converting a static problem into a function. This function is an equation that describes where the hyperplane must be at each point along the planned path to remain collision-free.

The sum of squares can be generalized to the optimization program to find a family of collision-free hyperplanes. Often considered a heavyweight optimization method suitable only for offline use, researchers have shown that for this problem it is extremely efficient and accurate.

"The key here was figuring out how to apply the sum of squares to our specific problem. The biggest challenge was coming up with the initial formulation. If I don't want my robot to bump into anything, what does that mean mathematically, and can the computer give me an answer?" says Amice.

Ultimately, as its name suggests, the sum of squares produces a function that is the sum of several squared values. The function is always positive, since the square of any number is always a positive value.

Trust, but verify

By double-checking that the hyperplane function contains squared values, a human can easily verify that the function is positive, meaning the path is collision-free, Amice explains.

Although the method certifies with perfect accuracy, this assumes that the user has an exact model of the robot and the environment; the mathematical certifier is only as good as the model.

"The great thing about this method is that the tests are very easy to interpret, so you don't have to rely on me coding it correctly because you can check it yourself," he adds.

They tested their technique in simulation, certifying that the complex movement plans of robots with one and two arms were collision-free. In its slowest version, the method took only a few hundred milliseconds to generate a test, making it much faster than other alternative techniques.

Although their method is fast enough to be used as a final safety check in some real-world situations, it is still too slow to be applied directly in a robot's motion planning loop, where decisions must be made in microseconds, Amice says.

The researchers plan to speed up the process by ignoring situations that don't require safety checks, such as when the robot is far from objects it could collide with. They also want to experiment with specialized optimization solvers that can operate faster.

This work has been funded, in part, by Amazon and the United States Air Force Research Laboratory.