US5347459A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Real time collision detection
Assignee: National Research Council Canada
•
Filing: 1993-03-17
•
Granted: 1994-09-13
•
Expires: 2013-03-17
Abstract
Abstract A method is provided for detecting a collision between a robot and one or more obstacles before it occurs. The robot is modeled by spheres in a voxelized workspace. Each voxel within the workspace is assigned a value which corresponds to its distance from the closest obstacle. A collision is determined to be imminent if the voxel value at the center of a sphere is less than the radius of the sphere in voxels.
Inventors
- 👤 Michael A. Greenspan
- 👤 Nestor Burtnyk
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 14:56
CPC Classifications
B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666; B25J19/00; B25J19/06; G; G05; G05B; G05B2219/00; G05B2219/30; G05B2219/39; G05B2219/39082; G05B2219/40; G05B2219/40442; G05B2219/40447; G05B2219/40492
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
250 words
In a device having one or more moveable elements residing within a finite space, a method of detecting a collision state between an object within the finite space and a model of the one or more moveable elements, comprising the steps of: (a) determining relative strengths of a set of discrete points throughout the space, the relative strength of any point being a measure of the distance from that point to the object; (b) storing values representative of the relative strengths in a memory; (c) determining a set of values of relative strengths of a set of reference points by approximating a volume occupied by the model of the one or more moveable elements by a set of spheres, each sphere being centered at one of the reference points, the relative strength value of each reference point, corresponding to a radius of a sphere centered at that point; (d) storing the set of values in a memory; (e) identifying the discrete points that correspond in location to each of the reference points; and, (f) comparing the stored values representative of the relative strengths of the reference points with the stored values representative of the relative strengths of the corresponding discrete points in the space, a collision state being detected when the ratio of any of the compared values representative of the relative strengths of the reference points and the values representative of the relative strengths of the corresponding discrete points in the space is greater than or equal to 1.
Claim 2
Dependent Claim
250 words
In a device having one or more moveable elements residing within a finite space, a method of detecting a collision state between an object within the finite space and a model of the one or more moveable elements, comprising the steps of: (a) determining relative strengths of a set of discrete points throughout the space, the relative strength of any point being a measure of the distance from that point to the object; (b) storing values representative of the relative strengths in a memory; (c) determining a set of values of relative strengths of a set of reference points by approximating a volume occupied by the model of the one or more moveable elements by a set of spheres, each sphere being centered at one of the reference points, the relative strength value of each reference point, corresponding to a radius of a sphere centered at that point; (d) storing the set of values in a memory; (e) identifying the discrete points that correspond in location to each of the reference points; and, (f) comparing the stored values representative of the relative strengths of the reference points with the stored values representative of the relative strengths of the corresponding discrete points in the space, a collision state being detected when the ratio of any of the compared values representative of the relative strengths of the reference points and the values representative of the relative strengths of the corresponding discrete points in the space is greater than or equal to 1.
Claim 3
Dependent Claim
21 words
The method defined in claim 1 further comprising the step of redirecting the moveable element if a collision state is detected.
Claim 4
Dependent Claim
54 words
The method as defined in claim 1 further comprising the step of: (g) repeating steps (e) to (f) for incrementally different positions of the model of the one or more moveable elements positioned at different locations within the finite space to determine a plurality of collision free states until a collision state is detected.
Claim 5
Dependent Claim
13 words
The method defined in claim 1 wherein each discrete point comprises a voxel.
Claim 6
Dependent Claim
157 words
In a device having at least one relatively moveable element, a method of detecting a collision state between an object and a model of the device comprising the steps of: a) determining the value of the strength of each of a plurality of voxels within a finite space, the strength of any voxel being an indicator of the distance from that voxel to the object; b) identifying the voxel strength at the center of one or more spheres which approximate a volume occupied by the model of the one or more moveable elements; and, c) comparing the values of the strengths of the voxels at the centers of the one or more spheres respectively with radii of the one or more spheres, a collision state being detected when a compared value of the strength of the voxel at the center of a sphere is less than or equal to the value of the radius of that sphere.
Claim 7
Dependent Claim
157 words
In a device having at least one relatively moveable element, a method of detecting a collision state between an object and a model of the device comprising the steps of: a) determining the value of the strength of each of a plurality of voxels within a finite space, the strength of any voxel being an indicator of the distance from that voxel to the object; b) identifying the voxel strength at the center of one or more spheres which approximate a volume occupied by the model of the one or more moveable elements; and, c) comparing the values of the strengths of the voxels at the centers of the one or more spheres respectively with radii of the one or more spheres, a collision state being detected when a compared value of the strength of the voxel at the center of a sphere is less than or equal to the value of the radius of that sphere.
Claim 8
Dependent Claim
61 words
The method according to claim 5 further comprising the step of preventing the at least one moveable element from moving closer to the object when the ratio of the value of the strength of the voxel at the center of the sphere divided by the number of adjacent voxels that correspond to the radius of the sphere is less than one.
Claim 9
Dependent Claim
46 words
The method as defined in claim 5 further comprising the step of: (d) repeating steps (b) and (c) for incrementally different positions of the model of the one or more moveable elements to determine a plurality of collision free states, until a collision state is detected.
Claim 10
Dependent Claim
145 words
The method according to claim 5 wherein the step of determining the value of the strength of each of a plurality of voxels within the finite space comprises the steps of: assigning all voxels located a distance from the object a value which corresponds to the distance in units of voxels from the object, wherein a first set of voxels occupying a space next to the object are assigned a value of one, and a second set of voxels occupying a space adjacent the first set of voxels and being a distance one voxel away from the object are assigned a value of two, and so on, such that a set of voxels that are located a distance less than the width of n voxels and greater than or equal to the width of n-1 voxels from the object are assigned a value of n.
Claim 11
Dependent Claim
48 words
The method according to claim 5 wherein the volume approximated by the one or more spheres corresponds in location to a layer extending along the surface of the moveable element, the thickness of the layer being equal or less than the diameter of the one or more spheres.
References Cited (Backward Citations)
US4578757A
Cited
US4922430A
Cited
US5086495A
Cited
US5047916A
Cited
US5038302A
Cited
US4985856A
Cited
US5056031A
Cited
US5150452A
Cited
US5255354A
Cited
US5150026A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-09-12 | 1998-03-14 | 1998-09-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-12 | 2002-03-14 | 2002-09-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-12 | 2006-03-14 | 2006-09-13 | $7700.00 | Window Closed / Lapsed |