The act of picking up a coffee cup from a table, despite being relatively simple for a human being, actually involves extremely complex calculations as we spontaneously plan a trajectory around obstacles in free space to reach the cup. This complexity means such tasks can be incredibly difficult for an autonomous robot and results in most motion-planning algorithms settling for any path - no matter how inefficient - that will allow the robot to achieve its goal. Now researchers have developed a new motion-planning system that lets robots save time and energy by moving more efficiently, which also makes their movements more predictable - an important consideration if they are to interact with humans.
In principle, calculating the optimal path would entail evaluating every possible path, rejecting the ones that involved collisions with obstacles, and selecting the most efficient of those that remain. For a robot with enough freedom of movement, this would be a very time-consuming calculation. Because of this, motion-planning algorithms will typically start by randomly picking points in its environment and determining whether each is reachable from the closest point that's already been evaluated. This results in the algorithm building up a map of short, collision-free trajectories between points that sees the robot performing a series of unnatural zigzagging movements before finally reaching their goal.
By combining two 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.
The first algorithm doesn't just determine whether a new randomly selected point is reachable from the closest previously evaluated point, it 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 was combined with a second algorithm that assumes that every new point it adds to the map has a sphere of open space around it, so it doesn't evaluate any other points within that sphere. These spheres are rescaled as the map expands and the algorithm discovers new possible sources of collision. By making a few educated guesses right off the bat, the algorithm can very quickly plan an initial route, which is then refined using the first algorithm.
The end result is paths that are not only more efficient, which saves time and energy, but also more predictable, which the researchers point out is a crucial consideration for robots that 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. "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."
Simulations carried out by the researchers in which a robot is tasked with grasping an object with one hand saw the standard algorithm taking almost four times as along as the new one to calculate an initial path and resulted in a route through space that was almost three times as long.
The MIT researchers also tested the algorithm on a PR2 robot with the results obvious in the video below. Willow Garage, the company behind PR2, is already evaluating the new algorithm, with plans to add it to the suite of motion-planning software that comes with the robot.