Incorporating aspect angle into route planners

Details Incorporating aspect angle into route planners Incorporating aspect angle into route planners

1999-03-11

2001-01-30

Zanelli, Michael J. (Department: 3661)

Data processing: vehicles, navigation, and relative location

Navigation

Determination of travel data based on the start point and...

C701S210000, C701S122000

Reexamination Certificate

active

06182007

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to route planning, and more particularly to the planning of routes in the presence of aspect angle constraints.
BACKGROUND OF THE INVENTION
Route planning is an important problem for a number of applications including, but not limited to, autonomous robotics, navigation/guidance of air, naval, and ground vehicles, intelligent transportation systems, and space related applications (i.e., planetary rovers, etc.), as described, for example, in Y. Hwang et al., Gross Motion Planning-a survey,
ACM Computing Surveys,
24(3): 219,291, September 1992; J. Latombe
Robot Motion Planning,
Kluwer, Boston, Mass. 1991; and R. Szczerba,
New Cell Decomposition Techniques for Planning Optimal Paths,
Doctoral Dissertation, University of Notre Dame, Notre Dame, Ind., 1996. Various applications require routes to have certain characteristics, parameters, and constraints depending on the application, or on the specific type of vehicle platform (aircraft, ship, tank, etc.).
When devising route planners, there are a number of desiderata which should be met to the extent possible, among which are real-time determination of relative costs for different types of vehicles in the presence of various types of environments. The result should be accurate, and should not rely on unrealistic approximations. The environment may be time-varying in nature, and may possibly even be represented by some sort of probability function (if exact locations are not known with a high degree of certainty). Furthermore, any such approach should be able to adapt, in real-time, to changing environmental conditions, given sufficient computing power.
Optimal solutions to the general case of route planning with the above-described constraints are considered to be NP-Complete in nature (corresponding to a particular class of problems in which no polynomial time solution is known to exist). Even if an optimal solution were to be found, which is believed to be unlikely, the convergence time and related memory requirements would likely be completely unrealistic for real-time applications using readily available processors. Thus, heuristic approaches have been used to generate efficient (based on computational and memory constraints) routes in real-time which are as good or better than a human could generate.
Most route planners for military operations are based on searching a digitized grid consisting of square cells of equal size. This technique is used because available terrain data generally comes from DTED (Digital Terrain Elevation Data) databases which are stored in grid-based formats. A route is then computed from a given “start” cell position to a “goal” cell position, with each cell representing a particular location in the environment. A cost estimation step is used to establish a “cost” value for a particular grid cell, corresponding to the cost incurred by an aircraft (or other vehicle) traveling through that particular region. This cost is used to represent any number of factors such as terrain features, threat exposure, weather conditions, cultural features, etc. The set of cost values for a particular environment is called its map cost (MC) array and is of size m×n , as described in C. Bodenhorn et al., Personalizing Onboard Route Re-Planning for Recon, Attack, and Special Operations Missions, 1997
American Helicopter Society Conference
(
Avionics and Crew Systems Technical Specialists Conference
), September 1997; P. N. Stiles et al., Highly Parallelizable Route Planner based on Cellular Automata Algorithms,
IBM Journal of Research and Development
38(2):167-181, March 1994; R. Szczerba et al., A Mission Adaptable Route Planner for Intelligent Guidance/Navigation Systems, 36th
AIAA Conference
(
Aerospace Sciences Meeting and Exhibit
), January 1998. A number of different route planning techniques use variations of such a cost array as input to compute the desired route. There are a very large number of different route planning techniques. A survey of various route planning algorithms, architectures, and techniques can be found in the Y. Hwang et al. and J. Latombe references.
Most route planners that use grid-based representations of the environment compare or correlate a proposed path segment in the form of a line overlayed on the square grid cell environment, to determine which grid cells the line intersects. A function is provided that adds up the relative cell costs (MC values) along cells lying on the particular segment of the route that is being considered in the route search process. The MC values of these cells are then added up and compared to the costs of other route segments being considered.
FIG. 1
represents a portion of a simple grid-based map
10
, showing the map cost for each cell or grid element. In
FIG. 1
, the cells are in a grid including five rows A, B, C, D, and E, and five columns 1, 2, 3, 4, and 5. All cells in row A have map values or costs of 34, and all cells in row B, except cell B
5
, have map costs of 34. Cell B
5
has a map cost of 12. In row C, cells C
1
and C
2
each have a cost of 34, cell C
3
has a cost of 88, C
4
has cost 10, and C
5
cost 23. In row D, the costs for columns 1, 2, 3, 4, and 5 are 34, 54, 33, 33, and 45, respectively. In row E, each cell has a map cost of 12. In
FIG. 1
, a line segment or path
12
represents a segment of a route. Line segment
12
intersects cells D
1
, D
2
, C
2
, C
3
, and C
4
. The cost of route segment
12
is determined by summing the map costs of cells D
1
, D
2
, C
2
, C
3
, and C
4
, which in the example is the sum of 34+54+34+88+10=220. In some cases, it may be desirable to average the cost per unit cell of the path traversed by the path segment, in order to more accurately assess the relative costs of equal-length path segments which happen to traverse different numbers of cells because of the differing directions of the path segments. A complete minimum-cost route is then generated by connecting various route segments which provide the least sum of map cost values.
The MC values of the grid cells of a grid map are usually computed off-line, taking into account data from a number of different sources. In determining the map cost, the cost of terrain features, threat exposure, cultural features (man-made features), etc. are all weighted and added together to generate the single cost value for each grid cell.
SUMMARY OF THE INVENTION
A method according to an aspect of the invention for planning a route includes the step of storing information pertaining to the environment, including the locations of threats, as map cost values in a grid-based map. A region of intervisibility is determined for each threat. A route is determined or planned through the environment by summing map cost values for each grid cell through which the vehicle may travel, and, only within the region of intervisibility, aspect-angle cost values are summed with the map cost values.


REFERENCES:
patent: 4812990 (1989-03-01), Adams et al.
patent: 4947350 (1990-08-01), Murray et al.
patent: 5122801 (1992-06-01), Hughes
patent: 5406286 (1995-04-01), Tran et al.
patent: 5504686 (1996-04-01), Lippitt et al.
patent: 5526260 (1996-06-01), Kodet et al.
patent: 5548773 (1996-08-01), Kemeny et al.
patent: 5631640 (1997-05-01), Deis et al.
patent: 5706011 (1998-01-01), Huss et al.
patent: 237 714 A1 (1987-09-01), None
patent: 7-12582 (1995-01-01), None
Teng et al.; Stealth terrain navigation; IEEE Systems, Man and Cbernetics; vol. 23, iss. 1; Jan.-Feb. 1993; pp. 96-110.
Bennett; The use of digital map data for airborne operations; IEE-Serious Low Flying; Feb. 1998; pp. 2/1-2/10.

Affiliated with

Also associated with

Rating

Incorporating aspect angle into route planners does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Incorporating aspect angle into route planners, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incorporating aspect angle into route planners will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2440620