Data processing: vehicles – navigation – and relative location – Relative location – Collision avoidance
Reexamination Certificate
1994-12-20
2001-11-27
Elmore, Reba I. (Department: 2187)
Data processing: vehicles, navigation, and relative location
Relative location
Collision avoidance
C700S245000, C701S023000, C701S041000, C701S300000, C701S302000
Reexamination Certificate
active
06324476
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to planning maneuvers of one or more actors (machines or people), where movement is possible in at least two dimensions, and is subject to two independent space-variant constraints or scenarios. In particular, the invention is applicable to planning travel, for example through time or space, where a rendezvous is required between one actor and another actor or condition which is also moving through the time or space.
The most common application for path planning has been for controlling robots. In the typical robot path plan, a path is chosen to get the robot (or a portion of it, such as a gripping member) from a start point to a goal point while avoiding obstacles. Computer simulation/control has been one of the great advances in improving performance, particularly in multidimensional situations.
Other applications of the invention may lie in traffic or emergency vehicle controls or planning or predicting possible routes or activities of people or machines in dynamic situations.
2. Description of the Prior Art
The related applications listed above form a background to the invention. These applications disclose, among other things, propagating cost waves through a configuration space by budding, using a space-variant metric. In simple path-planning problems, the configuration space represents a two-dimensional physical condition which has been discretized. Using a typical rectangular coordinate system, each configuration state then represents a task state or physical condition which is described by various parameters having known values. A list of these values in a specific order, known as a tuple, describes each configuration state. The configuration space, then, covers or is the span of the tuples.
Goal locations or states are defined, and are fixed for a set of analyses. Selection of a starting position is one step of the planning method.
The cost of transition from one configuration state to another, known as a cost metric but also referred to herein simply as a metric, is defined for each configuration state in a configuration space, with respect to each of its neighbors. Where it is impossible or highly undesirable for an actor (e.g., a machine) to be in a particular configuration state, that state is considered an obstacle. Movement into that state may then be associated with a very high, or infinite, transition cost. The neighborhood may then be defined as including only those states whose transition cost is undefined, or has a finite value—that is, a permissible state change.
Budding starts at a source, usually the goal or goals in a given configuration space, and is used to generate a direction arrow and a cost-to-goal metric for each state, in a wave of calculations expanding from the goal. A graphical view of this expansion process gives rise to the term “cost wave propagation.” The direction arrows generated for each configuration space point back to the lowest cost path to the goal. In control processes for robots, this has the advantage that, in the event that the robot has deviated from the optimum path, identification of the state it is in immediately makes the new best path direction known.
A specific improvement to the budding process, described in U.S. Pat. No. 4,949,277, involves differential budding of only a small part of the configuration space when, for example, an obstacle or goal is added to, moved a small distance in, or removed from that space.
U.S. Pat. No. 5,083,256, a continuation-in-part of Ser. No. 166,599 referred to above, discloses a variation of differential budding which takes into account changes in transitions in a configuration space, rather than just changes in the states themselves.
SUMMARY OF THE INVENTION
An object of the invention is to identify a plurality of rendezvous regions within a larger space, in which a planned rendezvous satisfies global constraints.
Another object of the invention is to utilize cost wave propagation from different sources in a more efficient way.
Yet another object of the invention is to optimize paths for at least two actors between separate starting locations and a rendezvous, and for at least one of these actors from the rendezvous to a final goal.
A further object of the invention is to control an actor machine to follow an optimized path from a start to a rendezvous to a final goal.
A still further object of the invention is to provide an apparatus which displays rendezvous regions for at least two actors, which satisfy all global constraints,
Still another object of the invention is to provide an apparatus for controlling an actor machine to follow an optimized path from a start to a rendezvous to a final goal with efficient updating when the environment changes
According to the invention, configuration spaces are formed for each of the scenarios applicable to the respective actors, with obstacles and goals defined in the configuration spaces. Cost waves are then propagated in each of the configuration spaces, and the costs for each of the configuration states are stored. Separate Boolean evaluations are made for each task state which is valid for the respective actors, to identify the candidate rendezvous states, which are those that meet the global criterion for a rendezvous. The Boolean results are then the basis for providing this identification.
In a first preferred apparatus embodying the invention, responsive to the Boolean results, an apparatus provides control signals for an actor to optimize travel from that actor's start to a rendezvous location.
In another preferred embodiment, an apparatus provides a visual display, pictorial or as a list of setpoints, of the candidate rendezvous regions.
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: 4949277 (1990-08-01), Trovato et al.
patent: 5083256 (1992-01-01), Trovato et al.
patent: 5187667 (1993-02-01), Short
patent: 5544282 (1996-08-01), Chen et al.
patent: 5610821 (1997-03-01), Gazis et al.
patent: 5696674 (1997-12-01), Trovato et al.
patent: 5835684 (1998-11-01), Bourne et al.
patent: 5870303 (1999-02-01), Trovato et al.
Houghton Miffin Company, ‘The American Heritage® Dictionary of the English Language’, Electronic Version Licensed to INSO Corporation, 1992.
Elmore Reba I.
Marion Michael E.
Philips ElectronicsNorth America Corporation
LandOfFree
Method and apparatus for identifying or controlling travel... 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 identifying or controlling travel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for identifying or controlling travel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588299