By combining two innovative algorithms developed at MIT, researchers in the Computer Science and Artificial Intelligence Laboratory (CSAIL) and the Laboratory for Information and Decision Systems (LIDS) have built a new robotic motion-planning system that calculates much more efficient trajectories through free space. This month at the Institute of Electrical and Electronics Engineers’ (IEEE) International Conference on Intelligent Robots and Systems, they’ll present a paper that describes the application of the algorithm to a robotic arm.

Not only do robots guided by the system move more efficiently, saving time and energy, but they also move more predictably, a crucial consideration if they’re to interact with humans. “People are most comfortable when the robot behaves in the way that a human would,” says Matthew Walter, a CSAIL research scientist and one of the new paper’s co-authors.

Earlier this summer, graduate student Sertac Karaman and associate professor of aeronautics and astronautics Emilio Frazzoli, both of LIDS, presented a new variation on an algorithm that yields much more efficient trajectories. Every time the algorithm evaluates a new, randomly selected point, it doesn’t just determine whether it’s reachable from the closest previously evaluated point. Instead, it 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 leads to paths that are much closer to the optimum.

To make their controller even more efficient, the researchers adapted yet another algorithm, which assumes that every new point it adds to its map has a sphere of open space around it, so it doesn’t evaluate any other points within that sphere. As the map expands, the algorithm discovers new possible sources of collision and rescales the spheres accordingly. But by making a few educated guesses right off the bat, the algorithm can plan an initial route very quickly. The researchers’ new system then uses Frazzoli and Karaman’s algorithm to refine the 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 new one to calculate an initial path and ended up with a route through space that was almost three times as long.


Also: Learn how the FUSE mission uses the SOVA algorithm.