New algorithm leads to more efficient robots with predictable movement

Researchers from MIT combined two innovative algorithms developed there to build a new robotic motion-planning system that calculates much more efficient trajectories through free space. Although such tasks seem intuitive and simple to us, most of the existing path finding algorithms rely to collision avoiding rather than finding more efficient paths between the robot’s initial state and its goal.

Researchers at the MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) and Laboratory for Information and Decision Systems (LIDS) came up with a system which enables robots to move more efficiently, thus saving time and energy. Since it is more intuitive and efficient, the new algorithm also provides more predictable movement which is crucial for robots which interact with humans.

“People are most comfortable when the robot behaves in the way that a human would”, said Matthew Walter, a CSAIL research scientist. “You’d expect them to execute some form of optimal path. 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.”

Instead checking every possible path in order to find the most efficient and collision free course, motion-planning algorithms tend to randomly pick points in the environment and determine whether each is reachable from the closest point that’s already been evaluated. It enables lower resource consumption and faster reaction to changes in the surroundings.

Graduate student Sertac Karaman and associate professor of aeronautics and astronautics Emilio Frazzoli, both of LIDS, developed a new variation on that algorithm which finds the paths that are much closer to the optimum. Every time the algorithm evaluates a new, randomly selected point, 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.

The researchers adapted an algorithm which Alexander Shkolnik developed for his PhD thesis. Shkolnik’s algorithm 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. 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. In addition to testing the algorithm in simulations, the researchers also tested it on a PR2 robot at CSAIL. Research scientists at Willow Garage, the company that makes the PR2, claim they are already evaluating the MIT researchers’ new algorithm, with plans to add it to the suite of motion-planning software that comes with the robot.

For more information, you can read the paper named: “Asymptotically-optimal Path Planning for Manipulation using Incremental Sampling-based Algorithms” (PDF).