Data processing: generic control systems or specific application – Specific application – apparatus or process – Robot control
Reexamination Certificate
1998-09-25
2002-12-10
Cuchlinski, Jr., William A. (Department: 3661)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Robot control
C700S104000, C700S114000, C700S165000, C700S218000, C700S222000, C700S245000, C700S249000, C700S250000, C700S251000, C700S253000, C700S259000, C700S264000, C701S002000, C701S023000, C701S024000, C701S025000, C701S026000, C701S027000, C701S028000, C701S301000, C901S031000, C901S037000, C414S744300
Reexamination Certificate
active
06493607
ABSTRACT:
COPYRIGHT NOTICE
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
The present disclosure is related to the disclosures provided in the following U.S. applications filed on even date herewith: “Intelligent System for Generating and Executing a Sheet Metal Bending Plan,” filed in the names of David Alan Bourne et al. U.S. Application Ser. No. 08/338,113 “Methods for Backgaging and Sensor-Based Control of Bending Operations,” filed in the names of David Alan Bourne et al. U.S. Application Ser. No. 08/338,153; and “Fingerpad Force Sensing System,” filed in the names of Anne M. Murray et al. The contents of each of these related applications are expressly incorporated by reference herein in their entireties.
1. Field of the Invention
The present invention relates to methods for planning/controlling the motion of a robot, and various systems and sub-components related to the operation thereof.
2. Discussion of Background Information
Various methods have been disclosed in the literature for providing a geometric model of the “amount of free space”, a robot has to move within, and for producing a motion plan for the robot to move from a start position to a goal position within the free space. Approximate decomposition methods are among such methods for modeling a robot's free space, as disclosed by Jean-Claude Latombe in “Robot Motion Planning,” Kluwer Academic Publishers, Boston/Dordrecht/London (1991), the content of which is expressly incorporated herein by reference in its entirety. Approximate cell decomposition may be utilized to determine the amount of free space in a given physical environment. In some such methods, a rectangloid (i.e., a rectangle or parallelepiped) decomposition P is formed of &OHgr;=Cl(R), which is a rectangloid of R
m
, where m is the dimension of the configuration space. The resulting rectangloid decomposition P is utilized to search for a solution path connecting a start position Q
init
to a goal position Q
goal
. An algorithm that may be utilized to find the solution path is as follows:
(1) An initial rectangloid decomposition P
1
of a rectangloid &OHgr; within R is computed, and cells are thus produced, each of which is classified as: empty, if it does not intersect a C-obstacle region; full, if it is entirely contained in a C-obstacle region; and mixed if it partially intersects a C-obstacle region.
(2) The resulting decomposition P
i
is searched in order to obtain a channel that connects the initial cell containing Q
init
to the goal cell containing Q
goal
. The channel may either be an E-channel, comprising all empty cells, or an M-channel, comprising one or more mixed cells. If the outcome of the search is an E-channel, the algorithm will return with the free-space empty cell E-channel. If, however, the outcome of the search is an M-channel, the process will proceed to step (3) below. Otherwise, the algorithm will return with failure.
(3) For every mixed cell within a generated M-channel, a further rectangloid decomposition P
i
will be computed, and the process will return to step (2).
In computing a rectangloid decomposition of a MIXED cell, a divide-and-label method may be performed, as illustrated in FIG.
1
. The method comprises the steps of first dividing a cell into smaller cells, as illustrated in
FIG. 1
, and then labeling each newly created cell according to whether it intersects a C-obstacle region. A widely used technique for decomposing a rectangloid &OHgr; into smaller rectangloids is to compute a 2
m
-tree decomposition. In a 2
m
-tree decomposition, a tree is formed having nodes, each of which represents a rectangloid cell which is labeled as either EMPTY, FULL or MIXED. The root node of the tree is &OHgr;. Each node which represents a MIXED cell will then be decomposed to form 2
m
children nodes. Each child of a parent cell has the same dimensions, and is formed by dividing each edge of the parent cell into two segments of equal length. If m=3, the tree is called an octree.
FIG. 1
shows an octree decomposition of a parallelepiped representation
10
of a portion of configuration space, and displays a portion of an octree graph
12
. The overall height h of the tree (i.e., the depth of the deepest node) determines the resolution of the decomposition, and hence the size of the smallest cells in the decomposition. A maximum height h
max
of the tree may be specified to thereby limit the iterative process carried out by steps 2 and 3 of the algorithm noted above.
It is noted that octree graph
12
does not correspond precisely to the parallelepiped
10
depicted in FIG.
1
. Rather, the various rectangloids depicted in octree graph
12
are chosen randomly in order to simplify the illustration.
The above described approximate cell decomposition method utilizes a configuration space approach to spatial planning, whereby the position and orientation of an object A in relation to obstacles B is characterized as a single point in a configuration space, in which the coordinates of the point represent a degree of freedom of the object in relation to the obstacles. The configurations (i.e., the placements) forbidden to the object A, due to the presence of other objects/obstacles, are characterized as regions in the configuration space, called configuration space obstacles (C-obstacles). Much literature has been published concerning the use of a configuration-space representations of an object with respect to obstacles, including a paper by Tomas Lozano-Perez, entitled “Spatial Planning: A Configuration Space Approach”, IEEE Transactions on Computers, Vol. C-32, No. 2 (February 1983), the content of which is expressly incorporated by reference herein in its entirety. This paper presents several algorithms for computing configuration space obstacles formed by objects which are polygons or polyhedra.
FIG. 2A
illustrates a two-dimensional representation of a peg
26
and a hole
28
, wherein the goal is to place peg
26
within hole
28
, so that a bottom surface
27
of peg
26
makes flush contact with a bottom surface g of hole
28
. The position and orientation of peg
26
may be represented in two-dimensional euclidian space as a set of Cartesian coordinates (x,y,&thgr;), the origin of which is positioned at the center of bottom surface
27
of peg
26
. At the location illustrated in
FIG. 2A
, peg
26
will have the coordinates &thgr;=0, x=0, and y=0.
FIG. 2B
illustrates a configuration space representation of the real-space problem of
FIG. 2A. A
point P is shown in its initial position (as shown in
FIG. 2B
) and may be moved to any position along a portion G of C-surface
29
. C-surface
29
represents a C-obstacle
30
that corresponds to an obstacle (hole)
31
represented in real-space in
FIG. 2A
, and point P represents peg
26
.
The position of P determines the position of peg
26
in relation to hole
28
. The boundary of the shaded area shown in
FIG. 2B
represents the positions at which peg
26
would be in contact with obstacle
31
, if point P was along the boundary. The transformation from
FIG. 2A
to
FIG. 2B
amounts to shrinking the peg
26
to a point P, and expanding obstacle
31
to form a C-obstacle
30
. The transformation from
FIG. 2A
to
FIG. 2B
is a limited example of how one may reformulate a problem of moving a rigid object among other rigid objects as an equivalent problem of moving a point among transformed objects in a higher-dimensional space called the configuration space (C-space).
It is noted that
FIG. 2B
corresponds to the points at which peg
26
will collide with obstacle
31
, if the axes (x,y) of peg
26
and hole
28
are constrained to be parallel, thereby keeping &thgr; equal to 0.
FIG. 2C
illustrates how the C-surface c
Bourne David Alan
Krishnan Sivaraj Sivarama
Amada America, Inc.
Marc McDieunel
LandOfFree
Method for planning/controlling robot motion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for planning/controlling robot motion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for planning/controlling robot motion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2925368