{"id":24824,"date":"2024-03-10T20:38:57","date_gmt":"2024-03-10T14:53:57","guid":{"rendered":"https:\/\/www.revoscience.com\/en\/?p=24824"},"modified":"2024-03-10T20:41:36","modified_gmt":"2024-03-10T14:56:36","slug":"method-rapidly-verifies-that-a-robot-will-avoid-collisions","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/method-rapidly-verifies-that-a-robot-will-avoid-collisions\/","title":{"rendered":"Method rapidly verifies that a robot will avoid collisions"},"content":{"rendered":"

By Adam Zewe<\/p><\/div><\/div>\n\n\n

\"\"<\/figure>\n\n\n\n

CAMBRIDGE, Mass. — Before a robot can grab dishes off a shelf to set the table, it must ensure its gripper and arm won\u2019t crash into anything and potentially shatter the fine china. As part of its motion planning process, a robot typically runs \u201csafety check\u201d algorithms that verify its trajectory is collision-free. <\/p>\n\n\n\n

However, sometimes these algorithms generate false positives, claiming a trajectory is safe when the robot collides with something. Other methods that can avoid false positives are typically too slow for robots in the real world.<\/p>\n\n\n\n

Now, MIT researchers have developed a safety check technique that can prove with 100 percent accuracy that a robot\u2019s trajectory will remain collision-free (assuming the model of the robot and environment is itself accurate). Their method, which is so precise it can discriminate between trajectories that differ by only millimeters, provides proof in only a few seconds.<\/p>\n\n\n\n

But a user doesn\u2019t need to take the researchers\u2019 word for it \u2014 the mathematical proof generated by this technique can be checked quickly with relatively simple math.<\/p>\n\n\n\n

The researchers accomplished this using 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.<\/p>\n\n\n\n

This technique could be especially useful for robots that must move rapidly to avoid collisions in spaces crowded with objects, such as food preparation robots in a commercial kitchen. It is also well-suited for situations where robot collisions could cause injuries, like home health robots that care for frail patients.<\/p>\n\n\n\n

\u201cWith this work, we have shown that you can solve some challenging problems with conceptually simple tools. Sum-of-squares programming is a powerful algorithmic idea, and while it doesn\u2019t solve every problem, if you are careful in how you apply it, you can solve some pretty nontrivial problems,\u201d says Alexandre Amice, an electrical engineering and computer science (EECS) graduate student and lead author of a paper<\/a> on this technique.<\/p>\n\n\n\n

Amice is joined on the paper by fellow EECS graduate student Peter Werner and senior author Russ Tedrake, the Toyota Professor of EECS, Aeronautics and Astronautics, and Mechanical Engineering, 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.<\/p>\n\n\n\n

Certifying safety<\/strong><\/p>\n\n\n\n

Many existing methods that check whether a robot\u2019s 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\u2019t tell if the robot will collide with something in the intermediate seconds.<\/p>\n\n\n\n

This might not be a problem for a robot wandering around an open space with few obstacles, but for robots performing intricate tasks in small spaces, a few seconds of motion can make an enormous difference.<\/p>\n\n\n\n

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. 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.<\/p>\n\n\n\n

Instead, this new 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.<\/p>\n\n\n\n

The researchers used sum-of-squares programming, an algorithmic toolbox that can effectively turn a static problem into a function. This function is an equation that describes where the hyperplane needs to be at each point in the planned trajectory so it remains collision-free. <\/p>\n\n\n\n

Sum-of-squares can generalize the optimization program to find a family of collision-free hyperplanes. Often, sum-of-squares is considered a heavy optimization that is only suitable for offline use, but the researchers have shown that for this problem it is extremely efficient and accurate. <\/p>\n\n\n\n

\u201cThe key here was figuring out how to apply sum-of-squares to our particular problem. The biggest challenge was coming up with the initial formulation. If I don\u2019t want my robot to run into anything, what does that mean mathematically, and can the computer give me an answer?\u201d Amice says.<\/p>\n\n\n\n

In the end, as the name suggests, 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.\u00a0<\/p>\n\n\n\n

Trust but verify<\/strong><\/p>\n\n\n\n

By double-checking that the hyperplane function contains squared values, a human can easily verify that the function is positive, which means the trajectory is collision-free, Amice explains.<\/p>\n\n\n\n

While the method certifies with perfect accuracy, this assumes the user has an accurate model of the robot and environment; the mathematical certifier is only as good as the model.<\/p>\n\n\n\n

\u201cOne really nice thing about this approach is that the proofs are really easy to interpret, so you don\u2019t have to trust me that I coded it right because you can check it yourself,\u201d he adds.<\/p>\n\n\n\n

They tested their technique in simulation by certifying that complex motion plans for robots with one and two arms were collision-free. At its slowest, their method took just a few hundred milliseconds to generate a proof, making it much faster than some alternate techniques.<\/p>\n\n\n\n

While their 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 says.<\/p>\n\n\n\n

The researchers plan to accelerate their process by ignoring situations that don\u2019t require safety checks, like when the robot is far away from any objects it might collide with. They also want to experiment with specialized optimization solvers that could run faster.<\/p>\n\n\n\n

This work was supported, in part, by Amazon and the U.S. Air Force Research Laboratory.<\/p>\n","protected":false},"excerpt":{"rendered":"

Before a robot can grab dishes off a shelf to set the table, it must ensure its gripper and arm won\u2019t crash into anything and potentially shatter the fine china.<\/p>\n","protected":false},"author":2,"featured_media":24825,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,28],"tags":[],"class_list":["post-24824","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-research","category-techbiz"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",900,600,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-200x200.jpg",200,200,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-600x400.jpg",600,400,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-768x512.jpg",750,500,true],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-675x450.jpg",675,450,true],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",900,600,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",900,600,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",900,600,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-870x570.jpg",870,570,true],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-600x600.jpg",600,600,true],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-600x600.jpg",600,600,true],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-760x490.jpg",760,490,true],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-550x360.jpg",550,360,true],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0-95x65.jpg",95,65,true],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",640,427,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2024\/03\/MIT_Motion-Planning-01_0.jpg",150,100,false]},"author_info":{"info":["By Adam Zewe"]},"category_info":"Research<\/a> Tech<\/a>","tag_info":"Tech","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/24824","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=24824"}],"version-history":[{"count":2,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/24824\/revisions"}],"predecessor-version":[{"id":24827,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/24824\/revisions\/24827"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/24825"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=24824"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=24824"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=24824"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}