MIT Researchers Develop Faster Algorithm for Household Robots to Identify Objects

For household robots ever to be practical, they’ll need to be able to recognize the objects they’re supposed to manipulate. But while object recognition is one of the most widely studied topics in artificial intelligence, even the best object detectors still fail much of the time.

Researchers at MIT's Computer Science and Artificial Intelligence Laboratory believe that household robots should take advantage of their mobility and their relatively static environments to make object recognition easier, by imaging objects from multiple perspectives before making judgments about their identity. Matching up the objects depicted in the different images, however, poses its own computational challenges.

In a paper appearing in a forthcoming issue of the International Journal of Robotics Research, the MIT researchers show that a system using an off-the-shelf algorithm to aggregate different perspectives can recognize four times as many objects as one that uses a single perspective, while reducing the number of misidentifications.

They then present a new algorithm that is just as accurate but that, in some cases, is 10 times as fast, making it much more practical for real-time deployment with household robots.

"If you just took the output of looking at it from one viewpoint, there's a lot of stuff that might be missing, or it might be the angle of illumination or something blocking the object that causes a systematic error in the detector," says Lawson Wong, a graduate student in electrical engineering and computer science and lead author on the new paper. "One way around that is just to move around and go to a different viewpoint."

First stab

Wong and his thesis advisors — Leslie Kaelbling, the Panasonic Professor of Computer Science and Engineering, and Tomás Lozano-Pérez, the School of Engineering Professor of Teaching Excellence — considered scenarios in which they had 20 to 30 different images of household objects clustered together on a table. In several of the scenarios, the clusters included multiple instances of the same object, closely packed together, which makes the task of matching different perspectives more difficult.

The first algorithm they tried was developed for tracking systems such as radar, which must also determine whether objects imaged at different times are in fact the same. "It's been around for decades," Wong says. "And there's a good reason for that, which is that it really works well. It's the first thing that most people think of."

For each pair of successive images, the algorithm generates multiple hypotheses about which objects in one correspond to which objects in the other. The problem is that the number of hypotheses compounds as new perspectives are added. To keep the calculation manageable, the algorithm discards all but its top hypotheses at each step. Even so, sorting through them all, after the last hypothesis has been generated, is a time-consuming task.

Representative sampling

In hopes of arriving at a more efficient algorithm, the MIT researchers adopted a different approach. Their algorithm doesn't discard any of the hypotheses it generates across successive images, but it doesn't attempt to canvass them all, either. Instead, it samples from them at random. Since there's significant overlap between different hypotheses, an adequate number of samples will generally yield consensus on the correspondences between the objects in any two successive images.

To keep the required number of samples low, the researchers adopted a simplified technique for evaluating hypotheses. Suppose that the algorithm has identified three objects from one perspective and four from another. The most mathematically precise way to compare hypotheses would be to consider every possible set of matches between the two groups of objects: the set that matches objects 1, 2, and 3 in the first view to objects 1, 2, and 3 in the second; the set that matches objects 1, 2, and 3 in the first to objects 1, 2, and 4 in the second; the set that matches objects 1, 2, and 3 in the first view to objects 1, 3, and 4 in the second, and so on. In this case, if you include the possibilities that the detector has made an error and that some objects are occluded from some views, that approach would yield 304 different sets of matches.

Instead, the researchers' algorithm considers each object in the first group separately and evaluates its likelihood of mapping onto an object in the second group. So object 1 in the first group could map onto objects 1, 2, 3, or 4 in the second, as could object 2, and so on. Again, with the possibilities of error and occlusion factored in, this approach requires only 20 comparisons.

It does, however, open the door to nonsensical results. The algorithm could conclude that the most likely match for object 3 in the second group is object 3 in the first — and it could also conclude that the most likely match for object 4 in the second group is object 3 in the first. So the researchers' algorithm also looks for such double mappings and re-evaluates them. That takes extra time, but not nearly as much as considering aggregate mappings would. In this case, the algorithm would perform 32 comparisons — more than 20, but significantly less than 304.

Featured Product

Universal Robots - Collaborative Robot Solutions

Universal Robots - Collaborative Robot Solutions

Universal Robots is a result of many years of intensive research in robotics. The product portfolio includes the UR5 and UR10 models that handle payloads of up to 11.3 lbs. and 22.6 lbs. respectively. The six-axis robot arms weigh as little as 40 lbs. with reach capabilities of up to 51 inches. Repeatability of +/- .004" allows quick precision handling of even microscopically small parts. After initial risk assessment, the collaborative Universal Robots can operate alongside human operators without cumbersome and expensive safety guarding. This makes it simple and easy to move the light-weight robot around the production, addressing the needs of agile manufacturing even within small- and medium sized companies regarding automation as costly and complex. If the robots come into contact with an employee, the built-in force control limits the forces at contact, adhering to the current safety requirements on force and torque limitations. Intuitively programmed by non-technical users, the robot arms go from box to operation in less than an hour, and typically pay for themselves within 195 days. Since the first UR robot entered the market in 2009, the company has seen substantial growth with the robotic arms now being sold in more than 50 countries worldwide.