Subscribe for email alerts

Don’t miss a single Science & Enterprise post. Sign up for our daily email alerts.

Donate to Science & Enterprise

Please share Science & Enterprise

More Efficient Algorithms Devised for Robotic Motions

Robotic movements (Sertac Karaman/MIT)

Time-lapse photo of robotic arms guided by new algorithm attempting to grasp a coffee cup on a desk. (Sertac Karaman/MIT)

Computer scientists at Massachusetts Institute of Technology have built a new robotic motion-planning system that calculates much more efficient trajectories through free space. The researchers in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) and the Laboratory for Information and Decision Systems (LIDS) will present their findings next week at the IEEE International Conference on Intelligent Robots and Systems.

Planning a trajectory around obstacles in free space may be intuitive for humans, but in robotics it’s a complex operation. As a result, say the researchers, most motion-planning algorithms settle for an expedient solution that avoids collisions rather than finding the most efficient path between the robot’s initial state and its goal.

Matthew Walter, a CSAIL researcher and a co-author of the paper says “The problem with most motion planners is that while they’re very good at finding feasible solutions for very complex systems, they’re not very good at finding optimal paths.” Calculating the optimal path can be a time consuming exercise, so motion-planning algorithms will instead often start randomly picking points in the device’s environment, determining whether each is reachable from the closest point that’s already been evaluated.

To address this issue, the researchers combined two separate algorithms reflecting different ways to plan the optimum path. Graduate student Sertac Karaman and professor of aeronautics and astronautics Emilio Frazzoli, both of LIDS, developed an algorithm earlier this year that determines if a point is reachable from the closest previously evaluated point, but also considers all the previously evaluated points within a fixed radius of the new one and determines which would offer the shortest path from the starting point. This method leads to paths that are much closer to the optimum.

Around the same time, CSAIL researchers Seth Teller, Alexander Shkolnik, and Alejandro Perez adapted an algorithm developed by Shkolnik for his doctoral dissertation. In that algorithm, every new point added to the map is assumed to have a sphere of open space around it, so it does not evaluate any other points within that sphere. As the map in Shkolnik’s method expands, the algorithm discovers new possible sources of collision and rescales the spheres accordingly. Making a few quick educated guesses, however, enables the algorithm to plan an initial route very quickly.

The new system started with the basic approach in Shkolnik’s algorithm, which reduced the time needed to plan the optimum route. The researchers then added Frazzoli and Karaman’s algorithm to refine that route.

In simulations of a robot trying to grasp an object with one robotic hand, the standard algorithm took almost four times as long as the researchers’ algorithm to calculate an initial path and ended up with a route through space that was almost three times as long. In addition to testing the algorithm in simulations, the researchers also tested it on a PR2 robot — pictured above and in the accompanying video.

A research scientist at Willow Garage, the company that makes the PR2, says that he and his colleagues are already evaluating the MIT researchers’ new algorithm.

Video: Sertac Karaman/MIT

Read more: University Spinoff Company Commercializes Robotic Modules

*     *     *

Comments are closed.