The Combinatorics of Local Constraints in Model-Based Recognition and Localization,
Abstract
The problem of recognizing what objects are where in the workspace of a robot can be cast as one of searching for a consistent matching between sensory data elements and equivalent model elements. In principle, this search space is enormous and to contain the potential combinatorial explosion, constraints between the data and model elements are needed. We derive a set of constraints for sparse sensory data that are applicable to a wide variety of sensors and examine their completeness and exhaustiveness. We then derive general theoretical bounds on the number of interpretations expected to be consistent with the data under the effects of local constraints. These bonds are applicable to many types of local constraints, other than the specific examples used here. For the case of sparse, noisy three-dimensional sensory data, explicit values for the bounds are computed and are shown to be consistent with empirical results obtained earlier in (Grimson and Lozano-Perez 1984). The results are used to demonstrate the graceful degradation of the recognition technique with the presence of noise in the data, and to predict the number of data points needed in general to uniquely determine the object being sensed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1984
- Accession Number
- ADA148338
Entities
People
- W. E. L. Grimson
Organizations
- Massachusetts Institute of Technology