Before the robot can pick up dishes from the shelf to set the table, it must make sure that its gripper and arm won’t hit anything and potentially break dainty china. As part of the motion planning process, the robot typically runs “safety check” algorithms that verify that its trajectory is collision-free.
However, these algorithms sometimes generate false positives, claiming that the trajectory is protected when the robot would actually collide with something. Other methods that can avoid false positives are usually too tardy for real-world robots.
Now, MIT researchers have developed a safety-checking technique that can demonstrate with 100 percent accuracy that a robot’s trajectory will remain collision-free (assuming the model of the robot and its environment itself is correct). Their method, so precise that it can distinguish between trajectories that differ by just millimeters, provides proof in mere seconds.
However, the user does not have to take the researchers’ word for it – the mathematical proof generated by this technique can be quickly checked using relatively uncomplicated mathematical calculations.
The researchers achieved this by using a special algorithmic technique called sum-of-squares programming and adapting it to effectively solve the security control problem. Using sum of squares programming allows their method to generalize to a wide range of complicated movements.
This technique could be particularly useful for robots that need to move quickly while avoiding collisions in spaces crowded with objects, such as food preparation robots in a commercial kitchen. It is also well suited to situations where robot collisions can cause injuries, such as home care robots that care for weak patients.
“Through this work, we have shown that it is possible to solve some tough problems with conceptually uncomplicated tools. Sum-of-squares programming is a powerful algorithmic idea, and while it doesn’t solve every problem, if you apply it carefully, you can solve some pretty non-trivial problems,” says Alexandre Amice, an electrical engineering and computer science graduate (EECS) and lead author of the book article about this technique.
Amice was joined by fellow EECS graduate student Peter Werner and senior author Russ Tedrake, a professor of EECS, aerospace, and mechanical engineering at Toyota and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL). The work will be presented at the International Conference on Robots and Automation.
Safety certification
Many existing methods for checking whether a robot’s planned motion is collision-free do so by simulating the trajectory and checking every few seconds whether the robot hits something. However, these stationary safety checks cannot tell whether the robot will hit something in the intervening seconds.
For a robot moving through an open space with few obstacles, this may not be a problem, but for robots performing complicated tasks in compact spaces, a few seconds of movement can make a huge difference.
Conceptually, one way to prove that the robot is not heading towards a collision would be to hold up a piece of paper separating the robot from any obstacles in the environment. Mathematically, this piece of paper is called a hyperplane. Many safety control algorithms work by generating a hyperplane at a single point in time. However, each time the robot moves, a modern hyperplane must be recalculated to perform the safety control.
Instead, this modern technique generates a hyperplane function that moves with the robot, so the entire trajectory can be proven to be collision-free, rather than moving in one hyperplane at a time.
The researchers used sum-of-squares programming, an algorithmic toolkit that can efficiently transform a stationary problem into a function. This function is an equation that describes where the hyperplane must be at each point of the planned trajectory to remain collision-free.
Sum of squares can generalize an optimization program to find a family of collision-free hyperplanes. Sum of squares is often considered a demanding optimization that is only suitable for offline apply, but researchers have shown that it is extremely competent and correct for this problem.
“The key here was figuring out how to apply the sum of squares to our particular problem. The biggest challenge was coming up with the initial formula. If I don’t want my robot to encounter something, what does that mean mathematically, and can the computer give me the answer?” Amice says.
Ultimately, as the name suggests, the sum of squares creates a function that is the sum of several squares of values. The function is always positive because the square of any number is always positive.
Trust but verify
By double-checking whether the hyperplane function contains quadratic values, a human can easily check whether the function is positive, which means the trajectory is collision-free, Amice explains.
While this method provides certification with perfect accuracy, it assumes that the user has an correct model of the robot and environment; the mathematical certification is only as good as the model.
“The really nice thing about this approach is that the evidence is really easy to interpret, so you don’t have to trust me that I’ve coded it right because you can check it yourself,” he adds.
They tested their technique in simulation, confirming that complicated motion plans for single- and dual-arm robots were collision-free. In the slowest case, it took just a few hundred milliseconds to generate a proof, making it significantly faster than some alternative techniques.
“This modern result suggests a novel approach to certifying that a complicated robot manipulator trajectory is collision-free, elegantly using mathematical optimization tools, transformed into surprisingly rapid (and publicly available) software. While it does not yet provide a complete solution for rapid trajectory planning in cluttered environments, this result opens the door to several intriguing directions for future research, says Dan Halperin, a professor of computer science at Tel Aviv University, who was not involved in this research.
While their approach is rapid enough to be used as a final safety check in some real-world situations, Amice says, it is still too tardy to be directly implemented in a robot’s motion planning loop, where decisions must be made in microseconds.
The researchers plan to speed up their process by ignoring situations that don’t require safety checks, such as when the robot is far from objects it might collide with. They also want to experiment with specialized optimization solvers that could run faster.
“Robots often get into trouble by brushing against obstacles because of poor approximations that are made when generating their paths. Amice, Werner, and Tedrake came to the rescue with a powerful new algorithm to quickly make sure the robots never overstep their bounds by carefully using advanced methods from computational algebraic geometry,” adds Steven LaValle, a professor at the Department of Information Technology and Electrical Engineering at the University of Oulu in Finland, who was not involved in the work.
This work was supported in part by Amazon and the U.S. Air Force Research Laboratory.