Before robots can effectively assist in tasks like table setting, they need to ensure their movements are precise and free from collisions, especially when handling delicate items such as fine china. An essential aspect of motion planning involves the use of “safety check” algorithms, which assess whether a robot’s proposed path is collision-free.
However, existing algorithms can sometimes yield false positives, mistakenly indicating that a trajectory is safe when it could actually lead to a collision. While there are methods available that can minimize false positives, they often operate too slowly for practical use in real-world settings.
In a significant advancement, researchers at MIT have introduced a novel safety check method that guarantees 100 percent accuracy in determining whether a robot’s trajectory will avoid collisions, assuming an accurate model of both the robot and its environment. Remarkably, this technique can differentiate between trajectories even differing by a few millimeters and delivers results within seconds.
This breakthrough offers users peace of mind, as the mathematical proofs generated can be quickly verified through straightforward calculations.
The team achieved this using a unique approach called sum-of-squares programming, which they have adapted to effectively tackle the safety check dilemma. This approach has shown the potential to generalize across a vast range of complex motions.
This technique holds particular promise for robots operating in crowded environments, such as food prep robots in busy commercial kitchens, or for robots designed to assist vulnerable patients in home health care settings, where collision risks pose significant concerns.
“Our research demonstrates that challenging problems can be addressed with conceptually simple tools. Sum-of-squares programming is a strong algorithmic technique that, although not solving every issue, can effectively tackle complex problems when applied thoughtfully,” states Alexandre Amice, an electrical engineering and computer science (EECS) graduate student and lead author of a study detailing this technique.
Amice collaborated on the study with fellow EECS graduate student Peter Werner and senior author Russ Tedrake, who holds the Toyota Professorship and is a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. Their research will be showcased at the International Conference on Robots and Automation.
Ensuring Safety through Innovation
Traditional methods that verify whether a robot’s planned motions are collision-free typically simulate trajectories at intervals. However, these static safety checks fail to detect potential collisions in real-time, particularly during intricate tasks in confined spaces where each split-second can be critical.
Imagine physically separating a robot from obstacles using a piece of paper—mathematically referred to as a hyperplane. Many current safety algorithms generate this hyperplane at specific moments. This requires recalculating a new hyperplane every time the robot moves, which can be inefficient.
In contrast, the MIT researchers have devised a method that creates a hyperplane function that adapts alongside the robot, ensuring the entire trajectory is verified as collision-free rather than relying on individual hyperplane checks.
By utilizing sum-of-squares programming, a pragmatic toolbox that converts static problems into dynamic functions, they were able to articulate where to position the hyperplane throughout the robot’s path.
This approach presents a way to generate multiple collision-free hyperplanes efficiently, overcoming the common misconception that sum-of-squares programming is too computationally intensive for real-time applications. This research illustrates that, with careful application, significant challenges can be overcome.
“The key innovation was formulating how to leverage sum-of-squares for our specific challenge. We needed to articulate what it means mathematically for a robot to avoid collisions,” shares Amice.
The final output of the sum-of-squares process produces a function comprising the sum of squared values, which always yields a positive result since squaring any number results in a positive value.
Trustworthy Verification
Human users can easily confirm the accuracy of the hyperplane function by ensuring that the squared values are indeed positive, thus guaranteeing the trajectory is safe from collisions, Amice explains.
This method is founded on the assumption that users maintain an accurate model of their robot and the environment; the effectiveness of the mathematical proof relies on the model’s fidelity.
“What’s particularly rewarding about this approach is that the proofs are easy to understand. You can verify the accuracy yourself, so confidence in the code isn’t merely taken for granted,” he adds.
To validate their method, the researchers tested it in simulations, confirming that both simple and complex motion plans for one- and two-armed robots were collision-free. Their method typically provided results in just a few hundred milliseconds, demonstrating a clear speed advantage over many current techniques.
“This innovative result suggests a fresh take on certifying complex robot trajectories as collision-free, harnessing powerful methodologies from mathematical optimization that are efficient and available for public use. While it doesn’t completely resolve all aspects of rapid trajectory planning in cluttered environments, it paves the way for intriguing future research avenues,” notes Dan Halperin, a computer science professor at Tel Aviv University who was not involved in the research.
Although the current method is swift enough for final safety checks in various real-world scenarios, it remains too slow to be directly integrated into a robot’s motion planning feedback loop, where decisions must occur in fractions of a second, according to Amice.
The research team aims to improve their approach by omitting safety checks in situations where collisions are unlikely, such as when robots are navigating far from obstacles. They also plan to explore specialized optimization solvers that could enhance speed.
“Robots frequently encounter difficulties when they come too close to obstacles due to inaccurate routing approximations. Amice, Werner, and Tedrake are pioneering a robust new algorithm that ensures robots steer clear of dangers by effectively leveraging advanced methodologies in computational algebraic geometry,” states Steven LaValle, a professor in the Faculty of Information Technology and Electrical Engineering at the University of Oulu in Finland, who was not part of this study.
This research received support from Amazon and the U.S. Air Force Research Laboratory.
Photo credit & article inspired by: Massachusetts Institute of Technology
