Tactical route planning method for use in simulated tactical engagements

• US 5,187,667 A
• Filed: 06/12/1991
• Issued: 02/16/1993
• Est. Priority Date: 06/12/1991
• Status: Expired due to Term

• Current Assignee: L-3 Communications Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Hughes Simulation Systems Incorporated (Rtx Corporation)
• Inventors: Short, Lee O.
• Primary Examiner(s): Chin, Gary
• Application Number:
  US07/713,946
• Time in Patent Office: 615 Days
• Field of Search: 364/443, 364/444, 364/449, 364/424.02, 364/436, 364/461, 73/178 R, 340/988, 340/990, 340/995
• US Class Current: 701/200
• CPC Class Codes: F41G 7/343 comparing observed and stored data of target position or of distinctive marks along the path towards the target
• CPC Class Codes: G05D 1/12 Target-seeking control
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18

Abstract

A method that may be implemented in software, that selects tactically sound paths for vehicles from an initial position to a goal position across a piece of terrain. The method searches through possible paths before selecting a desired path. It calculates a numerical heuristic to select promising paths to explore. By exploring only a few of the most promising paths, the method maintains high computational efficiency. Specifically, a list of paths is created (12) that begins with a vehicle'"'"'s initial section and moves to terrain sections surrounding the vehicle. The list of paths is sorted (13) using a minimum estimated total cost value to goal representing estimates of the relative combat values of different pieces of terrain while the vehicle is within engagement range of hostile positions. The total cost value is defined as the path'"'"'s current cost value plus the estimated cost value from the current position to the goal. Terrain cost values are defined for each of the sections, using a terrain tactical evaluation function. Each of the first three elements of the list of paths is then examined in order (14), and if any of the paths has reached the vehicle'"'"'s goal position, this path is selected and the method is complete (15, 16). Otherwise, new paths are then generated (17), by moving from the position at the end of the path to each of the adjacent terrain sections. These new paths are added to the list of paths, the original three paths are deleted, and the method (steps 13, 14, 15, 16) is repeated until the goal position is reached.

Claims

1. A computer-implemented method of providing for terrain evaluation and searching in simulated tactical engagements that employs a terrain database, and which determines an optimum path from a predetermined location in the terrain to a goal position, said method comprising the steps of:

dividing the terrain database into sections having uniform size and shape;

calculating a terrain cost value for each of the sections using a predefined terrain tactical evaluation function that corresponds to an estimate of the relative cost value of the terrain contained within each section;

selecting a set of paths starting with the predetermined location and ending with each of the terrain sections surrounding the predetermined location;

sorting the selected set of paths from the predetermined location to the goal position in terms of said terrain cost value;

processing each of a plurality of paths in the set of paths to determine if one of the paths has reached the goal position, and if the the goal position has been reached, computing a total cost value from the predetermined location to the goal position, and terminating the method;

if the goal position is not reached, generating a plurality of new paths by starting from the position at the end of a selected plurality of best paths to any of their adjacent terrain sections;

adding the plurality of new paths to the set of paths to create a new set of paths, and deleting the original path from the new set of paths; and

sorting the new set of paths and continuing the above steps until the optimum path from the predetermined location to the goal position is determined.

2. The method of claim 1 wherein the terrain tactical evaluation function is defined by the equation ##EQU7## and wherein M is the collection of all of the terrain in a scenario map M, which is divided into a number of equal-sized sections;

the map M is the collection of all such sections;

n is the size of the map M;

CN(q) is the concealment percentage offered by the section q, defined for all terrain sections q in the map M;

CV(q) is the cover percentage offered by the section q, defined for all terrain sections q in the map M;

V(q) is the raw terrain value of the section q, defined for all terrain sections q in the map M;

LOS(q,r) is the line-of-sight function from section q to section r, and equal to 1 if there is a clear line-of-sight, and is otherwise 0, defined for all terrain sections q and r in the map M;

F(q) is the raw fields-of-fire offered by section q, defined for all terrain sections q in the map M;

F'"'"'(q) is the fields-of-fire offered by section q, adjusted for fields-of-fire to key terrain, defined for all terrain sections q in the map M; and

V'"'"'(q) is the terrain value of the section q, adjusted for its fields-of-fire, defined for all terrain sections q in the map M.

3. A computer-implemented method of providing for terrain evaluation and searching in simulated tactical engagements that employs a terrain database, and which determines an optimum path from a predetermined vehicle location in the terrain to a goal position, said method comprising the steps of:

dividing the terrain database into sections of uniform size and shape;

creating a list of paths that comprises a set of paths, each of which begins with a vehicle'"'"'s initial section and moves to one of the terrain sections surrounding the vehicle;

calculating an estimated cost value to reach the goal position for each path, which is defined as each path'"'"'s current cost value plus an estimated remaining cost value from the current position to the goal position, and wherein said estimated cost value corresponds to an estimate of a relative combat value of each different piece of terrain while the vehicle is within engagement range of hostile positions;

sorting the list of paths in terms of said estimated cost value to the goal position;

examining in order each of the first three paths of the list of paths;

if one of the first three paths has reached the vehicle'"'"'s goal position, said one path is selected as the optimum path, and the method is terminated;

generating new paths from the three paths which were just considered, by moving from the position at the end of a selected one of the three paths to each respectively adjacent terrain section;

adding said new paths to the list of paths;

continuing the above steps until the vehicle'"'"'s goal position is reached and then terminating the method.

4. The method of claim 3 wherein the terrain tactical evaluation function is defined by the equation ##EQU8## and wherein M is the collection of all of the terrain in a scenario map M, which is divided into a number of equal-sized sections;

the map M is the collection of all such sections;

n is the size of the map M;

CN(q) is the concealment percentage offered by the section q, defined for all terrain sections q in the map M;

CV(q) is the cover percentage offered by the section q, defined for all terrain sections q in the map M;

V(q) is the raw terrain value of the section q, defined for all terrain sections q in the map M;

LOS(q,r) is the line-of-sight function from section q to section r, and equal to 1 if there is a clear line-of-sight, and is otherwise 0, defined for all terrain sections q and r in the map M;

F(q) is the raw fields-of-fire offered by section q, defined for all terrain sections q in the map M;

F(q) is the fields-of-fire offered by section q, adjusted for fields-of-fire to key terrain, defined for all terrain sections q in the map M; and

V'"'"'(q) is the terrain value of the section q, adjusted for its fields-of-fire, defined for all terrain sections q in the map M.

5. A computer-implemented method of providing for terrain evaluation and searching in simulated tactical engagements that employs a terrain database, and which determines an optimum path to be followed by a vehicle from a predetermined location in the terrain to a goal position, said method comprising the steps of:

dividing the terrain database into sections of uniform size and shape;

calculating terrain cost values representative of estimates of the relative combat values of different pieces of terrain while the vehicle is within engagement range of hostile positions for each of said sections, using a predefined terrain tactical evaluation function;

calculating, for each of the sections, an adjustment for said terrain cost values;

selecting a list of paths beginning with the vehicle'"'"'s initial section and ending at each of the terrain sections surrounding the vehicle;

calculating an estimated cost value to reach the goal position for each path, which is defined as each path'"'"'s current cost value plus an estimated remaining cost value from the current position to the goal position, wherein the estimated remaining cost value is defined as the number of remaining terrain sections times the average terrain cost value, and wherein the current cost value of a path is defined as the sum of the adjusted terrain cost values of the terrain sections defining the paths;

sorting the list of paths in terms of said estimated cost value to reach the goal position;

processing in order each of the first three paths of the list of paths, and if one of the first three paths has reached the vehicle'"'"'s goal position, computing a total cost value from the predetermined location to the goal position, and terminating the method;

if the goal position is not reached, for each of the three best paths, generating new paths which can be created by moving from the position at the end of each of the three best paths to their respectively adjacent terrain sections;

adding said new paths to the list of paths, and deleting the original path from the list of paths; and

sorting the list of paths and continuing the above steps until the method determines the vehicle'"'"'s path to the goal position.

6. The method of claim 5 wherein the terrain tactical evaluation function is defined by the equation ##EQU9## and wherein M is the collection of all of the terrain in a scenario map M, which is divided into a number of equal-sized sections;

the map M is the collection of all such sections;

n is the size of the map M;

CN(q) is the concealment percentage offered by the section q, defined for all terrain sections q in the map M;

CV(q) is the cover percentage offered by the section q, defined for all terrain sections q in the map M;

V(q) is the raw terrain value of the section q, defined for all terrain sections q in the map M;

LOS(q,r) is the line-of-sight function from section q to section r, and equal to 1 if there is a clear line-of-sight, and is otherwise 0, defined for all terrain sections q and r in the map M;

F(q) is the raw fields-of-fire offered by section q, defined for all terrain sections q in the map M;

F'"'"'(q) is the fields-of-fire offered by section q, adjusted for fields-of-fire to key terrain, defined for all terrain sections q in the map M; and

V'"'"'(q) is the terrain value of the section q, adjusted for its fields-of-fire, defined for all terrain sections q in the map M.