US5544282A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for planning motions of robot manipulators
Assignee: United States Department of Energy
•
Filing: 1991-04-05
•
Granted: 1996-08-06
•
Expires: 2011-04-05
Abstract
Abstract Method and apparatus for automatically planning motions of robot manipulators. The invention rapidly finds a collision-free path in a cluttered robot environment, if one exists, from any starting configuration of the robot manipulator to any ending configuration. The time to solution of a motion planning problem is not uniform, but proportional to the complexity of the problem.
Inventors
- 👤 Pang C. Chen
- 👤 Yong K. Hwang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 15:00
CPC Classifications
B; B25; B25J; B25J9/00; B25J9/16; B25J9/1656; B25J9/1664; B25J9/1666; G; G05; G05B; G05B2219/00; G05B2219/30; G05B2219/40; G05B2219/40424; G05B2219/40443; G05B2219/40463
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
122 words
A method for moving a robot manipulator comprising a plurality of joints through a workspace containing obstacles from a preselected starting robot manipulator configuration to a preselected goal robot manipulator configuration, the method comprising the steps of: a) selecting as subgoals robot manipulator configurations for which attitudinal positions are unspecified for one or more joints; b) generating a sequence of the subgoals that connect the starting robot manipulator configuration to the goal robot manipulator configuration; c) verifying that the generated sequence of subgoals is collision-free; and d) moving the robot manipulator from the starting robot manipulator configuration to the goal robot manipulator configuration such that a path of configurations defined by the generated sequence of subgoals is followed by the robot manipulator.
Claim 2
Independent Claim
122 words
A method for moving a robot manipulator comprising a plurality of joints through a workspace containing obstacles from a preselected starting robot manipulator configuration to a preselected goal robot manipulator configuration, the method comprising the steps of: a) selecting as subgoals robot manipulator configurations for which attitudinal positions are unspecified for one or more joints; b) generating a sequence of the subgoals that connect the starting robot manipulator configuration to the goal robot manipulator configuration; c) verifying that the generated sequence of subgoals is collision-free; and d) moving the robot manipulator from the starting robot manipulator configuration to the goal robot manipulator configuration such that a path of configurations defined by the generated sequence of subgoals is followed by the robot manipulator.
Claim 3
Dependent Claim
40 words
The invention of claim 1 wherein the step of selecting subgoals comprises selecting from a set of subgoals within a subspace of an existing subgoal, each member of the set having a refinement level one greater than the existing subgoal.
Claim 4
Dependent Claim
40 words
The invention of claim 2 wherein the step of selecting from the set of subgoals comprises selecting those subgoals having greatest distances from objects in the workspace and being greater than a specified edge cost away from other selected subgoals.
Claim 5
Dependent Claim
60 words
The invention of claim 1 wherein the step of generating a sequence of the subgoals that connect the starting robot manipulator configuration to the goal robot manipulator configuration comprises applying a shortest path method to the selected subgoals having no verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 6
Dependent Claim
83 words
The invention of claim 4 wherein the step of applying a shortest path method comprises the steps of: a) defining potential first points of the shortest path as a set of all robot manipulator configurations having a verified collision-free path of robot manipulator configurations from the starting robot manipulator configuration; and b) defining potential end points of the shortest path as a set of all robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from the goal robot manipulator configuration.
Claim 7
Dependent Claim
83 words
The invention of claim 4 wherein the step of applying a shortest path method comprises the steps of: a) defining potential first points of the shortest path as a set of all robot manipulator configurations having a verified collision-free path of robot manipulator configurations from the goal robot manipulator configuration; and b) defining potential end points of the shortest path as a set of all robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from the starting robot manipulator configuration.
Claim 8
Dependent Claim
45 words
The invention of claim 4 wherein the step of applying a shortest path method comprises defining an edge cost between two subgoal robot manipulator configurations as a sum of differences between commonly specified components of configuration space nodes representing the two subgoal robot manipulator configurations.
Claim 9
Dependent Claim
38 words
The invention of claim 1 wherein the step of verifying that the generated sequence of subgoals is collision-free comprises searching for a collision-free sequence of robot manipulator configurations for each pair of subgoals adjacent in the generated sequence.
Claim 10
Dependent Claim
21 words
The invention of claim 8 wherein the step of searching for a collision-free sequence of robot manipulator configurations comprises searching bi-directionally.
Claim 11
Dependent Claim
59 words
The invention of claim 9 wherein the step of searching bi-directionally comprises determining a direction of search by which of two robot manipulator configurations, having a verified collision-free sequence of robot manipulator configurations from the starting robot manipulator configuration and the goal robot manipulator configuration, respectively, has a smaller Euclidean distance from a corresponding nearest obstacle in the workspace.
Claim 12
Dependent Claim
66 words
The invention of claim 1 wherein the step of verifying that the generated sequence of subgoals is collision-free comprises choosing a robot manipulator configuration from a sampling of a preselected number of robot manipulator configurations within a single step of a robot manipulator configuration having a verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 13
Dependent Claim
39 words
The invention of claim 11 wherein the step of choosing a robot manipulator configuration from a sampling comprises choosing a robot manipulator configuration of the sampling having a greatest Euclidean distance from a corresponding nearest obstacle in the workspace.
Claim 14
Dependent Claim
15 words
The invention of claim 1 wherein the method comprises employing a dynamic graph data structure.
Claim 15
Dependent Claim
42 words
The invention of claim 13 wherein the method comprises employing vertices of the dynamic graph comprising subgoal robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 16
Dependent Claim
42 words
The invention of claim 13 wherein the method comprises employing vertices of the dynamic graph comprising subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 17
Dependent Claim
41 words
The invention of claim 13 wherein the method comprises employing vertices of the dynamic graph comprising robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 18
Dependent Claim
71 words
The invention of claim 13 wherein the method comprises employing edges of the dynamic graph comprising connections between subgoal robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration and subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 19
Dependent Claim
70 words
The invention of claim 13 wherein the method comprises employing edges of the dynamic graph comprising connections between subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration and robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either the starting robot manipulator configuration or the goal robot manipulator configuration.
Claim 20
Dependent Claim
35 words
The invention of claim 1 wherein the method comprises mapping possible robot manipulator configurations into a configuration space having a number of dimensions equal to a number of degrees of freedom of the robot manipulator.
Claim 21
Dependent Claim
35 words
The invention of claim 19 wherein the step of mapping possible robot manipulator configurations comprises defining an extent of each dimension dependent on a preselected stride value for a corresponding joint of the robot manipulator.
Claim 22
Dependent Claim
36 words
The invention of claim 20 further comprising the step of normalizing the preselected stride value such that each point on the robot manipulator moves approximately a same Euclidean distance for each step in a corresponding dimension.
Claim 23
Independent Claim
123 words
An apparatus for moving a robot manipulator comprising a plurality of joints through a workspace containing obstacles from a preselected starting robot manipulator configuration to a preselected goal robot manipulator configuration, said apparatus comprising: means for selecting as subgoals robot manipulator configurations for which attitudinal positions are unspecified for one or more joints; means for generating a sequence of said subgoals that connect said starting robot manipulator configuration to said goal robot manipulator configuration; means for verifying that said generated sequence of subgoals is collision-free; and means for moving said robot manipulator from said starting robot manipulator configuration to said goal robot manipulator configuration such that a path of configurations defined by said generated sequence of subgoals is followed by said robot manipulator.
Claim 24
Independent Claim
123 words
An apparatus for moving a robot manipulator comprising a plurality of joints through a workspace containing obstacles from a preselected starting robot manipulator configuration to a preselected goal robot manipulator configuration, said apparatus comprising: means for selecting as subgoals robot manipulator configurations for which attitudinal positions are unspecified for one or more joints; means for generating a sequence of said subgoals that connect said starting robot manipulator configuration to said goal robot manipulator configuration; means for verifying that said generated sequence of subgoals is collision-free; and means for moving said robot manipulator from said starting robot manipulator configuration to said goal robot manipulator configuration such that a path of configurations defined by said generated sequence of subgoals is followed by said robot manipulator.
Claim 25
Dependent Claim
42 words
The invention of claim 22 wherein said means for selecting subgoals comprises means for selecting from a set of subgoals within a subspace of an existing subgoal, each member of said set having a refinement level one greater than said existing subgoal.
Claim 26
Dependent Claim
42 words
The invention of claim 23 wherein said means for selecting from said set of subgoals comprises means for selecting those subgoals having greatest distances from objects in said workspace and being greater than a specified edge cost away from other selected subgoals.
Claim 27
Dependent Claim
62 words
The invention of claim 22 wherein said means for generating a sequence of said subgoals that connect said starting robot manipulator configuration to said goal robot manipulator configuration comprises means for applying a shortest path method to said selected subgoals having no verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 28
Dependent Claim
82 words
The invention of claim 25 wherein said means for applying a shortest path method comprises: means for defining potential first points of said shortest path as a set of all robot manipulator configurations having a verified collision-free path of robot manipulator configurations from said starting robot manipulator configuration; and means for defining potential end points of said shortest path as a set of all robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from said goal robot manipulator configuration.
Claim 29
Dependent Claim
82 words
The invention of claim 25 wherein said means for applying a shortest path method comprises: means for defining potential first points of said shortest path as a set of all robot manipulator configurations having a verified collision-free path of robot manipulator configurations from said goal robot manipulator configuration; and means for defining potential end points of said shortest path as a set of all robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from said starting robot manipulator configuration.
Claim 30
Dependent Claim
47 words
The invention of claim 25 wherein said means for applying a shortest path method comprises means for defining an edge cost between two subgoal robot manipulator configurations as a sum of differences between commonly specified components of configuration space nodes representing said two subgoal robot manipulator configurations.
Claim 31
Dependent Claim
40 words
The invention of claim 22 wherein said means for verifying that said generated sequence of subgoals is collision-free comprises means for searching for a collision-free sequence of robot manipulator configurations for each pair of subgoals adjacent in said generated sequence.
Claim 32
Dependent Claim
23 words
The invention of claim 29 wherein said means for searching for a collision-free sequence of robot manipulator configurations comprises means for searching bi-directionally.
Claim 33
Dependent Claim
61 words
The invention of claim 30 wherein said means for searching bi-directionally comprises means for determining a direction of search by which of two robot manipulator configurations, having a verified collision-free sequence of robot manipulator configurations from said starting robot manipulator configuration and said goal robot manipulator configuration, respectively, has a smaller Euclidean distance from a corresponding nearest obstacle in said workspace.
Claim 34
Dependent Claim
68 words
The invention of claim 22 wherein said means for verifying that said generated sequence of subgoals is collision-free comprises means for choosing a robot manipulator configuration from a sampling of a preselected number of robot manipulator configurations within a single step of a robot manipulator configuration having a verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 35
Dependent Claim
41 words
The invention of claim 32 wherein said means for choosing a robot manipulator configuration from a sampling comprises means for choosing a robot manipulator configuration of said sampling having a greatest Euclidean distance from a corresponding nearest obstacle in said workspace.
Claim 36
Dependent Claim
17 words
The invention of claim 22 wherein said apparatus comprises means for employing a dynamic graph data structure.
Claim 37
Dependent Claim
44 words
The invention of claim 34 wherein said apparatus comprises means for employing vertices of said dynamic graph comprising subgoal robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 38
Dependent Claim
44 words
The invention of claim 34 wherein said apparatus comprises means for employing vertices of said dynamic graph comprising subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 39
Dependent Claim
43 words
The invention of claim 34 wherein said apparatus comprises means for employing vertices of said dynamic graph comprising robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 40
Dependent Claim
73 words
The invention of claim 34 wherein said apparatus comprises means for employing edges of said dynamic graph comprising connections between subgoal robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration and subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 41
Dependent Claim
72 words
The invention of claim 34 wherein said apparatus comprises means for employing edges of said dynamic graph comprising connections between subgoal robot manipulator configurations having no verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration and robot manipulator configurations having a verified collision-free sequence of robot manipulator configurations from either said starting robot manipulator configuration or said goal robot manipulator configuration.
Claim 42
Dependent Claim
37 words
The invention of claim 22 wherein said apparatus comprises means for mapping possible robot manipulator configurations into a configuration space having a number of dimensions equal to a number of degrees of freedom of said robot manipulator.
Claim 43
Dependent Claim
37 words
The invention of claim 40 wherein said means for mapping possible robot manipulator configurations comprises means for defining an extent of each dimension dependent on a preselected stride value for a corresponding joint of said robot manipulator.
Claim 44
Dependent Claim
35 words
The invention of claim 41 further comprising means for normalizing said preselected stride value such that each point on said robot manipulator moves approximately a same Euclidean distance for each step in a corresponding dimension.
Claim 45
Dependent Claim
16 words
The invention of claim 22 further comprising means for sensing locations of objects within said workspace.
Claim 46
Dependent Claim
9 words
The invention of claim 22 further comprising a computer.
Claim 47
Dependent Claim
20 words
The invention of claim 22 further comprising means for display of a simulation of said workspace and said robot manipulator.
References Cited (Backward Citations)
US4578757A
Cited
US4636699A
Cited
US4862373A
Cited
US5220497A
Cited
US5047916A
Cited
US5172253A
Cited
US5150026A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-06 | 2000-02-05 | 2000-08-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-06 | 2004-02-05 | 2004-08-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-06 | 2008-02-05 | 2008-08-06 | $7700.00 | Window Closed / Lapsed |