Ask someone with her hands in her lap to pick up a coffee mug on the table she’s sitting at, and she’ll extract her hand from under the table and stretch her arm out toward the mug.
Instruct an autonomous robot to perform the same feat, and it may think for a few seconds, zigzag its robotic hand back and forth under the table, then perform what look kind of like calisthenics for a few seconds more before finally reaching for the mug.
As intuitive as it seems to a human being, spontaneously planning a trajectory around obstacles in free space is a monstrously complex computation. As a consequence, most motion-planning algorithms give up on the idea of finding the most efficient path between the robot’s initial state and its goal, settling for any path that won’t introduce collisions.
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. And human actions tend to follow the most direct routes from origin to goal. “You’d expect them to execute some form of optimal path,” Walter 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.”
In principle, calculating the optimal path requires evaluating every possible path in turn, rejecting those that introduce collisions with obstacles and selecting the most efficient of those that remain. But for a robot with enough freedom of motion, that’s a prohibitively time-consuming calculation. So typically, Walter explains, a motion-planning algorithm will instead start randomly picking points in its environment, determining whether each is reachable from the closest point that’s already been evaluated.
In this way, the algorithm builds up a map of short, collision-free trajectories between points, rather like a subway map overlaid on the map of a city. As long as it sticks to these established trajectories, it knows it can get from any point to any other. But as with a subway map, the best route between two points could turn out to be very circuitous.
Earlier this summer, graduate student Sertac Karaman and associate professor of aeronautics and astronautics Emilio Frazzoli, both of LIDS, presented a new variation on that 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.
Frazzoli and Karaman join Walter, CSAIL professor Seth Teller, research affiliate Alexander Shkolnik PhD ’09 and Alejandro Perez (now at Cornell) on the new paper. To make their controller even more efficient, the researchers adapted yet another algorithm, which 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. 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.
Video: Sertac Karaman
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 (above) at CSAIL.
Sachin Chitta, 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, with plans to add it to the suite of motion-planning software that comes with the robot. At the moment, Chitta says, the algorithm is “probably slower than we’d like.” But increasing a new algorithm’s speed, he explains, “is sometimes a matter of code optimization.”
“It’s already almost there,” he says. “It definitely would be one of the options that people would look for.”
Instruct an autonomous robot to perform the same feat, and it may think for a few seconds, zigzag its robotic hand back and forth under the table, then perform what look kind of like calisthenics for a few seconds more before finally reaching for the mug.
As intuitive as it seems to a human being, spontaneously planning a trajectory around obstacles in free space is a monstrously complex computation. As a consequence, most motion-planning algorithms give up on the idea of finding the most efficient path between the robot’s initial state and its goal, settling for any path that won’t introduce collisions.
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. And human actions tend to follow the most direct routes from origin to goal. “You’d expect them to execute some form of optimal path,” Walter 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.”
In principle, calculating the optimal path requires evaluating every possible path in turn, rejecting those that introduce collisions with obstacles and selecting the most efficient of those that remain. But for a robot with enough freedom of motion, that’s a prohibitively time-consuming calculation. So typically, Walter explains, a motion-planning algorithm will instead start randomly picking points in its environment, determining whether each is reachable from the closest point that’s already been evaluated.
In this way, the algorithm builds up a map of short, collision-free trajectories between points, rather like a subway map overlaid on the map of a city. As long as it sticks to these established trajectories, it knows it can get from any point to any other. But as with a subway map, the best route between two points could turn out to be very circuitous.
Earlier this summer, graduate student Sertac Karaman and associate professor of aeronautics and astronautics Emilio Frazzoli, both of LIDS, presented a new variation on that 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.
Frazzoli and Karaman join Walter, CSAIL professor Seth Teller, research affiliate Alexander Shkolnik PhD ’09 and Alejandro Perez (now at Cornell) on the new paper. To make their controller even more efficient, the researchers adapted yet another algorithm, which 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. 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.
Video: Sertac Karaman
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 (above) at CSAIL.
Sachin Chitta, 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, with plans to add it to the suite of motion-planning software that comes with the robot. At the moment, Chitta says, the algorithm is “probably slower than we’d like.” But increasing a new algorithm’s speed, he explains, “is sometimes a matter of code optimization.”
“It’s already almost there,” he says. “It definitely would be one of the options that people would look for.”
