Automatic recognition of parts is an important problem with applications in sorting parts for packing and assembly. Our objective is to recognize parts using inexpensive, widely-available robot hardware as an alternative to machine vision. Specifically, our aim is to determine the shape of a polygonal part from a sequence of diameter (width) measurements made by grasping the part with an instrumented parallel-jaw gripper. Since complete determination of shape is not possible using just diameter measurements, we consider the problem of recognizing a part from a known (finite) set of parts. Given a set of parts with a total of N faces, of which n are stable, we first construct an internal representation of the stable faces in O(N+n/sup 4/) time. Then we give two off-line planning algorithms: one constructs an optimal sensing plan in time O(n/sup 4/2/sup n/) the other constructs a suboptimal sensing plan in time O(n/sup 2/ log n). Neither plan requires more than n+1 online measurements.>

Graph width metrics have been widely studied for their relevance to VLSI design. Examples include cutwidth, pathwidth, bandwidth and several others that arise in circuit layout. When the width is bounded, graphs that satisfy these metrics can often be recognized by finite lists of obstruction tests. One of the most foundational tests is to determine whether K/sub 4/ is immersed in a graph. The authors present for the first time a fast, practical algorithm to perform this test, and discuss its relevance to cutwidth and other metrics.>