Tactile Recognition and Localization Using Object Models: The Case of Polyhedra on a Plane

Peter C. Gaston, Tomas Lozano-Perez

TL;DR

This seminal paper from MIT's AI Lab introduces a geometric approach to robotic tactile sensing that identifies and locates objects by matching sparse contact data to known models. By structuring the search as an interpretation tree and pruning it with simple distance and angle constraints, the system can efficiently recognize polyhedral objects using only a few points of contact.

What Problem Does This Paper Address?

For a robot to manipulate its environment, it needs to know exactly what it is holding and how that object is oriented. While computer vision is a powerful tool for this, it often fails due to occlusions (the robot's own hand blocking the view) or in environments where vision is unavailable, such as in murky underwater salvage or dark bins of parts.

Existing tactile recognition methods at the time were often split into two camps: statistical pattern recognition, which ignored the rich geometric constraints of object models, and global feature-finding, which was painstakingly slow because it required the robot to "trace" large sections of an object's surface. Gaston and Lozano-Pérez sought a middle ground: a method that uses sparse, local data (just a few contact points) and leverages complete geometric models to achieve rapid recognition and localization.

Methods

The authors propose a framework based on an Interpretation Tree (IT). When a robotic hand with $f$ fingers touches an object, it generates $f$ contact points. The goal is to determine which edge of a known object model corresponds to each contact point.

The Interpretation Tree structures the search for consistent pairings between contact points and object edges.

To prevent the search space from exploding combinatorially, they apply three levels of geometric pruning:

  1. Distance Constraint: For any two contact points, the distance between them must be a possible distance between the two edges they are assigned to. If the measured distance is impossible for those edges, that entire branch of the tree is pruned. Distance pruning checks if the measured distance between points falls within the range of possible distances between candidate edges.

  2. Angle Constraint: This uses the range of surface normals at the contact points. Crucially, it also incorporates "angle pockets"—ranges of forbidden orientations based on the fact that the sensor reached the contact point without hitting any other part of the object first. Angle pockets represent the range of orientations consistent with the sensor's approach path.

  3. Model Constraint: This is the final and most computationally expensive check. It attempts to solve for the exact transformation (position $x, y$ and orientation $\theta$) that places all contact points on their assigned edges.

Distance pruning checks if the measured distance between points falls within the range of possible distances between candidate edges.
Angle pockets represent the range of orientations consistent with the sensor's approach path.

Datasets

The study utilized simulated 2D polygonal models to evaluate the algorithm. These included a variety of shapes such as a twelve-sided polygon, a "gator" silhouette, and a complex "hand" shape with 66 edges. These models served as the "known objects" the system had to identify and locate.

Key Insights and Ideas

  • The Power of Sparse Data: You don't need a high-resolution "tactile image" to identify an object. A few points of contact, when combined with a geometric model, provide enough constraint to collapse thousands of possibilities down to one or two.
  • Negative Information is Information: One of the most clever insights is the use of the approach path. The fact that a sensor didn't hit anything on its way to the contact point provides a strong constraint on the object's orientation.
  • Efficiency through Hierarchy: For complex objects with many edges, the authors suggest using Strip Trees (hierarchical bounding boxes for edges). This allows the algorithm to prune entire sections of an object at once rather than checking every individual edge.
  • Tactile vs. Force Sensing: The paper clarifies that tactile arrays are superior to simple force sensors because they can distinguish between different contact distributions that might produce identical total force and torque. Tactile sensors can distinguish between force distributions that appear identical to a single force sensor.
Tactile sensors can distinguish between force distributions that appear identical to a single force sensor.

Key Results

The pruning strategy proved remarkably effective. In a test with a twelve-sided polygon (which has 1,728 possible interpretations for three contact points), the distance and angle tests eliminated all but 14 candidates. The expensive "Model Test" only had to be run on less than 1% of the total search space.

Quantitative "pruning efficiencies" (the ratio of interpretations eliminated) were frequently above 0.9 for complex models. The distance test, in particular, was highlighted as being surprisingly efficient, often pruning 70-80% of the tree at the very first stage.

Limitations and Future Work

  • Dimensionality: This paper focuses on the 3-degree-of-freedom case (polyhedra constrained to a plane). The authors acknowledge that extending this to the full 6-DOF 3D case is a significant next step.
  • Geometry: The method is designed for polyhedral objects with flat faces. Handling curved surfaces would require moving from analytical equation solving to more complex numerical optimization.
  • Sensor Noise: While the authors discuss extending distance pruning to handle measurement error, they note that high levels of noise significantly degrade the efficiency of the pruning process.

Summary updated

Abstract

This paper discusses how data from multiple tactile sensors may be used to identify and locate one object, from among a set of known objects. We use only local information from sensors: 1) the position of contact points and 2) ranges of surface normals at the contact points. The recognition and localization process is structured as the development and pruning of a tree of consistent hypotheses about pairings between contact points and object surfaces. In this paper, we deal with polyhedral objects constrained to lie on a known plane, i.e., having three degrees of positioning freedom relative to the sensors. We illustrate the performance of the algorithm by simulation.
BibTeX
@article{gaston1984tactile,
  author = {Peter C. Gaston and Tomas Lozano-Perez},
  title = {{Tactile Recognition and Localization Using Object Models: The Case of Polyhedra on a Plane}},
  journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
  year = {1984},
  doi = {10.1109/tpami.1984.4767518},
}
Figure