Data processing: generic control systems or specific application – Generic control system – apparatus or process – Digital positioning
Reexamination Certificate
1990-11-16
2003-08-05
Patel, Ramesh (Department: 2121)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
Digital positioning
C700S254000, C700S255000, C701S023000, C701S026000, C701S301000, C701S301000, C706S905000, C706S919000
Reexamination Certificate
active
06604005
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to (copyright or mask work) protection. The (copyright or mask work) owner has no objection to facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent And Trademark Office patent file or records, but otherwise reserves all (copyright or mask work) rights whatsoever.
The present application incorporates by reference the computer program listing in the appendix on one compact disc. The file names on the disk are
borderline.c—6 KB;
bud.c—8 KB;
canvas.c—20 KB;
copyright.1989—1 KB;
defines.h—7 KB;
demo.c—1 KB;
externs.h—12 KB;
globals.h—11 KB;
init.c—4 KB;
interpol.c—18 KB;
metric.c—2 KB;
path.c—5 KB;
print.c—2 KB;
show.c—11 KB;
trafo_data.c—10 KB .
The CD-ROM lists the creation date of the files as December 23, 2001, which was the date of the creation of the compact disc layout. The files were copied onto the compact disc on December 25, 2001.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to planning an optimal path for an object to follow from a given start point to a nearest one of a set of goals, taking into account constraints and obstacles.
2. The Prior Art
One of the most important outstanding problems in robotics is that of path planning with obstacle avoidance. In a typical task, the robot has to move from a start location to a goal location. Obstacles should be avoided along the way, and the movement as a whole should be as efficient as reasonably possible. The planning of the path should be as rapid as possible. The problem of providing such a “path” for a robot, for instance by giving a series of set points, is called the path planning problem.
There are a number of existing robots. Typically they are controlled using a programming language. One commonly used language is Val II, described in Unimation, Inc., “Programming Manual: User's Guide to Val II: Version 2.0 398AG1”, December 1986. Val II can be used to control products such as Unimation's Puma Robots and Adept Robots. Using Val II, a user can specify the movement of a robot, from a current point to a desired point, using the command MOVE POINT () on page 4-20 of the reference. Points are usually generated in joint coordinates. It is therefore sufficient for a path planning method to generate a series of set points to be inserted in the appropriate Val II command. The technology is in place for the robot to follow a path once the set points are generated.
Typical industrial robots use manually generated set points. Such manually generated set points are adequate for performing a simple repetitive task such as automated assembly in an environment which does not change from one task to the next. Manually generated set points are not practical and paths followed are often not efficient for dynamic situations, or for situations with large numbers of obstacles, or for obstacles with complex shapes. Therefore there is a need for a method to generate set points automatically.
One known method automatically generates a set of points along an optimal path. The set of points allows a robot to get from a start point to one of a set of goal points. One goal point is chosen over the others because it minimizes movement of the robot. This known method is disclosed in L. Dorst et al., “The Constrained Distance Transformation, A Pseudo-Euclidean, Recursive Implementation of the Lee-algorithm”,
Signal Processing III
(I. T. Young et al. eds; Elsevier Science Publishers B. V., EURASIP 1986) (“L. Dorst et al.”); and P. W. Verbeek et al., “Collision Avoidance and Path Finding through Constrained Distance Transformation in Robot State Space”, Proc. Conf. Dec. 8-11 1986, Amsterdam pp. 627-634. The known method plans paths in the configuration space of the robot. Obstacles to robot movement are represented by forbidden states in configuration space. In this space, the series of set points is represented in so-called joint coordinates, this is a set of coordinates that can be used to drive the joints of the robot directly. No complicated coordinate transformations are needed. An advantage of the known method is the simplicity with which it can be expanded to greater numbers of degrees of freedom.
In the prior art, the path in configuration space is found in three steps:
1) A transformation is made of the obstacles and the goals of the robot from points in task space to states in configuration space, The configuration space is discretized.
2) A cost field is created, specifying the total cost needed to reach the closest goal state at each state in configuration space. The particular method used to produce the cost field is described in L. Dorst et al. The method is a repeated scanning of the complete configuration space, while performing a basic cost propagation operation at each state.
3) From the start state, steps are taken in the direction of the cost gradient of the cost field until the goal state is reached. The states passed on the way form the shortest path from start to goal, and can be used as the series of set points.
Steps 1) and 2) are performed only once for a given robot and a given set of obstacles and goals. Using the same cost field, Step 3) can be performed for different start states.
The prior art method has a number of disadvantages. First, in step 2), the whole configuration space has to be scanned several times. Second, the kinds of cost metrics considered are restricted. In particular the cost of transitions between states in configuration space are considered to be the same for a given direction independent of the state at which cost is calculated. These restrictions limit practical applications. For instance, it is not possible to find a path for a robot arm with revolute joints that will result in minimal movement of an end-effector. Minimal time paths are only possible for a few robots which are of limited practical application. A third disadvantage is that following the gradient requires computation of the gradient at every point of the path.
SUMMARY OF THE INVENTION
It is an object of the invention to avoid repeated scanning of the configuration space during creation of the cost field.
It is a second object of the invention to allow use of cost metrics which vary at different states in configuration space. An example of this would be a cost function which allows minimization of the movement of the effector end of the robot.
It is a third object of the invention to avoid computation of the gradient at every state during establishment of a path.
It is a fourth object of the invention to create a path planning method which is easily adaptable to multiple degrees of freedom.
These objects are achieved according to the invention by a process referred to herein as “budding.”
These objects are further achieved according to the invention by the use of cost metrics which are referred to herein as “space-variant metrics.”
These objects are still further achieved according to the invention by a process referred to herein as “following the direction arrows”.
These objects are further achieved according to the invention by using the space-variant matrices in a multi-dimensional configuration space.
Further objects and advantages of the invention will become apparent in the remainder of the application.
REFERENCES:
patent: 4481568 (1984-11-01), Inaba et al.
patent: 4482968 (1984-11-01), Inaba et al.
patent: 4674048 (1987-06-01), Okumura
patent: 4764873 (1988-08-01), Libby
patent: 4862373 (1989-08-01), Meng
patent: 5751573 (1998-05-01), Cameron et al.
patent: 5764510 (1998-06-01), Cameron et al.
Lumelsky is related to Dynamic Path Planning for a Planar Articulated Robot Arm Moving Unknown, Automatica, vol. 23, No. 5, pp. 551-570 (1987) wnich is recited in this US Patent Application by the applicant.*
Lumelsky is related to Algorithmic and Complexity issues of Robots Motion in an Uncertain Environment, Journal of Complexity 3, 146-182 (1987) wnich is recited in this US Patent Application by the applicant.*
NASA's Jet Propulsion Laboratory
Dorst Leendert
Trovato Karen Irene
Koninklijke Philips Electronics , N.V.
Patel Ramesh
LandOfFree
Method and apparatus for path planning 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 and apparatus for path planning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for path planning will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3128537