Optimal strategies for recognizing polygonal parts

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>