Browse Prior Art Database

SHAPE FROM PROBING

IP.com Disclosure Number: IPCOM000128188D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 11 page(s) / 35K

Publishing Venue

Software Patent Institute

Related People

Richard Cole: AUTHOR [+4]

Abstract

We consider a new problem motivated by robotics: how to determine shape and position from probes. We show that 3n probes are sufficient, but 3n - 1 arc n=ssay, to determine the shape and position of any n-gon. Under a mild assumption, 3n probes are aoaasazy. This work is done under the auspices of the NYLUCRWS Laboratory for Robotia and Fxpcrimca-taI Computer Sdenx. It is supported in part by granEs from the Digital Equipment Corporation, Sloan Foundation and ONR Grant N00014-82-K-0381.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SHAPE FROM PROBING

by Richard Cole & Chee K. Yap

Technical Report No. 104 Robotics Roport No. 15 December, Shape from probing

Rkhard Cole and Chet K. Yap Courant Institute of Mathematical Sciences New York University 251, Mercer Street New York, NY 10012

December 1983

ABSTRACT

We consider a new problem motivated by robotics: how to determine shape and position from probes. We show that 3n probes are sufficient, but 3n - 1 arc n=ssay, to determine the shape and position of any n-gon. Under a mild assumption, 3n probes are aoaasazy. This work is done under the auspices of the NYLUCRWS Laboratory for Robotia and Fxpcrimca-taI Computer Sdenx. It is supported in part by granEs from the Digital Equipment Corporation, Sloan Foundation and ONR Grant N00014-82-K-0381.

1. Introduction

Visual data (suitably digitized) is traditionally used when an- intelligent automatic system needs to determine shape or locality information of objects. In robotics, other types of sensory data such as touch and sound becomes relevant. Our motivation is the processing of touch-type sensory data. In particular, we are interested in what we might call the `shape from probing' problem (parallelling the 'shape frown shading' problem in vision). Of course, such data (which depends on physical contact) are more expensive, per unit of information, than say visual data. On the other hand, there are situations where there is no alternative to touch-type data: cameras for gathering visual data are more delicate and more bulky than a simple pressure sensitive device (the `finger') and thus some awkward positions may not be accessible to cameras. It should be realized that the suggestive terms like `touch' and `finger' need not be literal. For instance, at our robotics laboratory, a practical algorithm very similar to that described in this paper has been implemented by Mr. M. IC. IHor using the IBM RS-1 robot; `touch' data is obtained by an LED sensors across the two opposing robot fingers. The actile sensing literature is growing but the emphasis is usually on the physical and other properties of various devices, and algorithms are generally of a heuristic nature. See [GLP] for an extensive reference. Here we have approached the problem from a purely mathematical (geometrical) and complexity point of view, and this seems new. . We note that [GLP] has independently considered essentially the same model of probes as ours. We begin with the simplest cases in the plane. Let S be a planar body. To have a meaning-ful problem, we make two assumptions: (Al) Rough position: S contains the origin O of the coordinate system. Thus we do not have to `find' S. (A2) Rough shape: S is a closed convex polgon. To discover the shape and location of S, we are allowed probes where each probe can be formally defined to be a directed line L. Informally, imagine a point from infinity moving along and in the direction of L until...