Robot motion planning is a complex process, and one of the key steps involved is ensuring the robot doesn’t collide with any objects in its path. This is especially crucial when the robot is handling delicate items, such as fine china. As part of this process, robots typically use ‘safety check’ algorithms to ensure their paths are collision-free.
However, these algorithms can sometimes generate false positives, indicating a safe trajectory when there’s actually a risk of collision. Other methods designed to avoid false positives are often too slow for real-world applications. To address this issue, researchers at MIT have developed a new safety check technique that can accurately ensure a robot’s path is collision-free.
A New Safety Check Technique
The new technique developed at MIT can verify with 100% accuracy that a robot’s path will remain free from collisions, assuming the models of the robot and its environment are accurate. This method is so precise that it can distinguish between trajectories differing by mere millimeters. Furthermore, it can provide this proof in just a few seconds.
The researchers achieved this by utilizing an algorithmic technique known as sum-of-squares programming and adapting it to effectively solve the safety check problem. This enables their method to generalize to a wide range of complex motions. The technique could be particularly beneficial for robots tasked with moving quickly to avoid collisions in crowded spaces, such as commercial kitchens or healthcare settings where collisions could result in injuries.
Sum-of-Squares Programming
Sum-of-squares programming is a powerful algorithmic technique that can effectively solve a variety of challenging problems. In this case, it was used to transform a static problem into a function. The function describes where a hyperplane – a mathematical concept used to separate the robot from potential obstacles – needs to be at each point in the planned trajectory to remain collision-free.
Typically, sum-of-squares is considered a heavy optimization suitable only for offline use, but the researchers demonstrated that it can be extremely efficient and accurate when applied to this problem.
Certifying Safety
Existing methods to verify a robot’s motion is collision-free typically do so by simulating the trajectory and checking at intervals to see whether the robot encounters any obstacles. However, these methods cannot determine whether the robot will collide with something during the intervals between checks. The new technique overcomes this issue by generating a hyperplane function that moves with the robot, thereby certifying an entire trajectory as collision-free.
Trust but Verify
The sum-of-squares method produces a function that is always positive, as it’s the sum of several squared values. This allows a quick and easy verification that the function is positive, therefore confirming that the trajectory is collision-free. It’s important to note, however, that while the method certifies with perfect accuracy, it does rely on having an accurate model of the robot and its environment.
Testing and Future Research
The researchers tested their technique by certifying that complex motion plans for robots with one and two arms were collision-free. Their method generated a proof within a few hundred milliseconds, making it significantly faster than some alternative techniques. However, it is currently still too slow to be implemented directly in a robot’s motion planning loop, where decisions need to be made within microseconds.
Future plans for this research include accelerating the process by bypassing situations that don’t require safety checks, such as when the robot is far from any objects it might collide with. The team also plans to experiment with specialized optimization solvers that could potentially run faster.
