The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data
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 control the potential combinatorial explosion,...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Online Access: | http://hdl.handle.net/1721.1/6398 |
| _version_ | 1811083608772837376 |
|---|---|
| author | Grimson, W. Eric L. |
| author_facet | Grimson, W. Eric L. |
| author_sort | Grimson, W. Eric L. |
| collection | MIT |
| description | 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 control 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 characteristics. We then use known bounds on the complexity of constraint satisfaction problems together with explicit estimates of the effectiveness of the constraints derived for the case of sparse, noisy three-dimensional sensory data to obtain general theoretical bounds on the number of interpretations expected to be consistent with the data. We show that these bounds are consistent with empirical results reported previously. 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. |
| first_indexed | 2024-09-23T12:35:47Z |
| id | mit-1721.1/6398 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:35:47Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/63982019-04-11T03:30:43Z The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data Grimson, W. Eric L. 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 control 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 characteristics. We then use known bounds on the complexity of constraint satisfaction problems together with explicit estimates of the effectiveness of the constraints derived for the case of sparse, noisy three-dimensional sensory data to obtain general theoretical bounds on the number of interpretations expected to be consistent with the data. We show that these bounds are consistent with empirical results reported previously. 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. 2004-10-04T14:54:56Z 2004-10-04T14:54:56Z 1986-03-01 AIM-763a http://hdl.handle.net/1721.1/6398 en_US AIM-763a 34 p. 5538748 bytes 4341952 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Grimson, W. Eric L. The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title | The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title_full | The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title_fullStr | The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title_full_unstemmed | The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title_short | The Combinatorics of Local Constraints in Model-Based Recognition and Localization from Sparse Data |
| title_sort | combinatorics of local constraints in model based recognition and localization from sparse data |
| url | http://hdl.handle.net/1721.1/6398 |
| work_keys_str_mv | AT grimsonwericl thecombinatoricsoflocalconstraintsinmodelbasedrecognitionandlocalizationfromsparsedata AT grimsonwericl combinatoricsoflocalconstraintsinmodelbasedrecognitionandlocalizationfromsparsedata |