Data processing: generic control systems or specific application – Generic control system – apparatus or process – Digital positioning
Reexamination Certificate
1990-04-11
2004-04-27
Grant, William (Department: 2121)
Data processing: generic control systems or specific application
Generic control system, apparatus or process
Digital positioning
C700S254000, C700S255000, C701S023000, C701S301000, C701S026000, C701S301000, C706S905000, C706S919000
Reexamination Certificate
active
06728581
ABSTRACT:
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 fascimile reproduction by anyone of the patent document of the patent disclosure, as it appears in the Patent and trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to path planning and in particular to repropagating cost waves in a configuration space after some aspect of that space has been changed.
The invention also relates to path planning in a configuration space in which the location of obstacles is not known.
2. Prior Art
The field of path planning is one with many applications. The most common application is to controlling robots, for instance robot arms such as are used in the space shuttle. Other applications include electronic maps, traffic control, emergency vehicle control, and emergency exit systems.
The path planning problem, as applied to robots, typically involves getting a robot from a start point to a goal point while avoiding obstacles. Automating multi-dimensional path planning for robots is one of the great historical problems of robotics.
The present invention is an improvement on the invention disclosed U.S. patent application Ser. No. 123,502, now abandoned which is incorporated herein by reference as background material. That application disclosed, amongst other things, propagating cost waves through a configuration space by budding, using a space-variant metric.
After budding, some aspect of the configuration space may change, for instance, if an obstacle is removed or a goal added. In such a case, it may be inefficient to bud the entire configuration space again because only a small part of the configuration space may be affected.
Another problem which arises after a change in configuration space is that the precise location of the changes, particularly in obstacle location, may not be known. An approach to this problem is set forth in V. Lumelsky, “Algorithmic and Complexity Issues of Robot Motion in an Uncertain Environment”, Journal of Complexity 3, 146-182 (1987); and V. Lumelsky, “Dynamic Path Planning for a Planar Articulated Robot Arm Moving Amidst Unknown Obstacles”, Automatica, Vol. 23., No. 5, pp. 551-570 (1987). This approach suffers from certain shortcomings. For instance, the method disclosed is only able to deal with two dimensions. The method, also does not have a memory for previously encountered obstacles.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to deal with changes in a configuration space.
It is a second object to deal with changes in configuration space in the context of a space-variant metric.
It is a further object of the invention to deal with changes in a configuration space using budding.
It is still a further object of the invention to deal with changes in condition in multiple dimensions.
It is another object of the invention to deal with unsensed or partially sensed changes in conditions in the context of a space-variant metric.
It is yet another object of the invention to deal with unsensed or partially sensed changes in conditions using budding.
It is yet a further object of the invention to deal with unsensed or partially sensed changes in conditions with improved abilities to incorporate new data into the memory of the path planes.
These and other objects of the invention are achieved herein using a method referred to herein as differential budding.
The method involves identifying a region in configuration space which is affected by a change of conditions in task space. Precisely selected states referred to as a perimeter and which define this region are then placed on a “sifting heap” from which they are budded.
In the case of an added obstacle, the perimeter includes the front edge of the obstacle as well as surrounding a group of states which are connected via direction arrows to the back edge of the added obstacle.
In the case of removed obstacles, the perimeter states are neighbors of the removed obstacle states.
In the case of added goals, the perimeter states are the added goals themselves.
In the case of partially sensed changes in conditions, the changes in conditions are detected while following a precalculated path. Most changes in conditions can then be dealt with as an added obstacle, a removed obstacle, an added goal, or a removed goal. In one embodiment of the invention, the object first encounters a portion of the change in conditions iteratively follows a newly calculated path until the change in conditions is taken into account.
Further objects and advantages will become apparent in what follows.
REFERENCES:
patent: 4674048 (1987-06-01), Okumura
patent: 4764873 (1988-08-01), Libby
Dorst Leendert
Trovato Karen Irene
Grant William
North American Philips Corporation
Patel Ramesh
LandOfFree
Differential budding: 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 Differential budding: method and apparatus for path planning..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Differential budding: method and apparatus for path planning... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222560