Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
1998-07-20
2001-07-10
Cuchlinski, Jr., William A. (Department: 3664)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C701S201000, C701S202000, C701S210000, C705S400000, C705S417000, C705S418000, C340S989000, C340S995190
Reexamination Certificate
active
06259988
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to navigation and planning optimization systems and, more particularly, to route planning for travel paths subject to a variety of navigational constraints.
2. Description of the Prior Art
When a course of travel is not constrained by roads or other fixed structures, such as during travel by air or water or over unimproved land, careful navigation along a path extending from a starting point to a goal is required. The choice of a path may, in such a case, be constrained by many factors such as range or other physical limitations of a vehicle, weather conditions and other conditions which may compromise safety, and human factors, such as operator (e.g. pilot) workload. Some fixed structures may also affect the choice of path such as the orientation of a runway, the physical layout of harbors, docks and the like as well as physical obstacles which may be man-made or natural.
In the past, a trained navigator (generally a pilot, driver or ship officer, sometimes referred to collectively hereinafter as simply “pilot”) would choose a path or course based on the best available information concerning as many of the above matters as possible. However, in practice, often information would be available concerning only a few of the above matters. While greater availability of information has improved safety and efficiency of route choice, even highly trained navigators are unable to assimilate the amount of information which may be available or to assign an appropriate degree of importance to each item of information and are thus able to perform only the most rudimentary of quantitative optimization of route details. Further, planning by a navigator including responses to changes of conditions or circumstances is always subject to human error; the likelihood of which increases with the amount of information available for consideration.
Additionally, in recent years, many more types of information and constraints have been included in route planning which further complicates the route planning process for a human navigator. Such constraints may include, but are not limited to, minimum leg length (e.g. a minimum interval in time or distance between changes of course) and maximum turning angle (e.g. a limit of the vehicle or an angle at which likelihood of collision is not significantly increased when plural vehicles are traversing the route in close proximity to one another). Accordingly, attempts have been made to use automated data processing to plan travel routes.
Known route planning or optimization techniques generally follow one of two distinct methodologies: grid-based techniques and graph-based techniques. Each of these categories has its own distinct advantages and disadvantages.
Grid-based techniques are generally directed to optimization to the level of grid cell resolution employed and can generally converge to a relatively accurate solution in real time. However, grid-based techniques can accommodate quantitative metrics and limits and particular constraints only with difficulty and a solution complying therewith may not be found. Further, discontinuities in the search space may not allow some solutions to be reliably found, particularly an alternate solution which may be preferable to an optimum solution but which may be altered therefrom to a seemingly slight degree.
Graph-based techniques are generally very accurate and can generally accommodate metrics and constraints but often suffer from long convergence times, if they converge to a solution at all, since they carry out an exhaustive search of the search space while concurrently applying constraints. Therefore, graph-based techniques require large computing resources if they are to support even the possibility that a solution may be found within a practical amount of time. On the other hand, even large computing resources cannot guarantee that a solution will be found within an acceptable amount of time. Moreover, the possibility of changing circumstances effectively reduces the acceptable time period for finding a solution to a travel problem.
Additionally, the mode of transportation may greatly affect the detail of the planning as well as the relative importance of circumstances in development of a route plan. For example, speed of a vehicle may determine the level of relevant detail and the minimum time or distance between turns. The nature of the mission and the number of vehicles involved as well as speed and maneuverability thereof may affect the maximum allowed turn angle, and so forth.
Accordingly, it has been determined by the inventors that a need has existed for an automated system for travel route planning which could be easily customized to the constraints imposed by the vehicle and other circumstances to produce, in real-time, a route which is as good or better than could be produced by a trained navigator.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a system and methodology for providing real-time solutions to travel route problems which account for an arbitrary number of constraints of varying importance and other problems involving a sequence of changing conditions or constraints.
It is another object of the invention to provide a methodology for reduction of the search space for graph based optimization problems such as route planning.
It is a further object of the invention to provide a system and method for providing a real-time optimization methodology for route planning and other problems which can be readily customized to accommodate arbitrary metrics and constraints.
In order to accomplish these and other objects of the invention, a method of limiting a search space of a graphical optimization search process such as a route planning process is provided comprising the steps of determining a trajectory at a node to be expanded, defining sectors disposed around the trajectory in accordance with a first constraint, determining a lowest cost vector to a node which is separated by a length from the node in each sector, accumulating nodes corresponding to lowest cost vectors in a comparison engine such as a min-heap, and selecting and removing a further node to be expanded from the comparison engine.
REFERENCES:
patent: 4413316 (1983-11-01), Blue et al.
patent: 4812990 (1989-03-01), Adams et al.
patent: 4862373 (1989-08-01), Meng
patent: 4926336 (1990-05-01), Yamada
patent: 4962458 (1990-10-01), Verstraete
patent: 4999782 (1991-03-01), BeVan
patent: 5170353 (1992-12-01), Verstraete
patent: 5340061 (1994-08-01), Vaquier et al.
patent: 5408413 (1995-04-01), Gonser et al.
patent: 5459666 (1995-10-01), Casper et al.
patent: 5504686 (1996-04-01), Lippitt et al.
patent: 5548773 (1996-08-01), Kemeny et al.
patent: 5936631 (1999-08-01), Yano et al.
patent: 6016485 (2000-01-01), Amakawa et al.
patent: 6026384 (2000-02-01), Poppen
patent: 6038559 (2000-03-01), Ashby et al.
Galkowski Peggy J.
Glickstein Ira S.
Stiles Peter N.
Szczerba Robert J.
Cuchlinski Jr. William A.
Lockheed Martin Corporation
McGuireWoods LLP
To Tuan C
LandOfFree
Real-time mission adaptable route planner does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time mission adaptable route planner, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time mission adaptable route planner will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2454758