In this setting, the evader (i.e. us) has no direct access to manipulate the type, number and/or behavior of pursuers; we have access only to our ship's contact report data collected within our sensor's range. The Secnario Generator, developed by the E&S, created various types of pursuers and tactical situations. We control our vehicle (ownship) to evade the pursuers and to judiciously utilize our limited number of countermeasures. In this work we have developed and implemented a set of navigational schemes which aid a military vehicle evade two specific types of obstacles:
From a game-theoretic viewpoint, a pragmatic solution to differential game problems that involve multiple pursuers and a single evader has been developed using a semantic control approach. While such differential game problems have been addressed in the past, their solution has always been based on a determinate game, i.e., one in which the number of players does not change during the course of the game. Our approach transcends this earlier work by rendering a solution to dynamic games, where the number of players change. The latter class of problems is of preeminent interest because it represents the norm of combat situations encountered by military aircraft, ground vehicles, and ocean-going vessels, where the use of weapons and countermeasures form an intrinsic part of an engagement.
Identifier: The tasks for the Identifier are:
Goal Selector: The data from the identifier, describing the current situation (contact report data and the mission score), is passed to the goal selector which then suggest an appropriate course of action to the Adapter. The functional block diagram of the TDA is illustrated in Figures 2a-2b, the graphic user interface is shown in Figure 2c below.
The viability of the semantic control approach has been illustrated in this application with the help of a strategy table; the table qualifies tactical situations to be encountered and available courses of action, i.e. navigational schemes, to handle them.
For the two obstacles of interest, a weapon platform and a weapon, the tactical situations that can arise while our vehicle transits to its destination are: no sensor contact, weapon platform contact, weapon platform in pursuit, weapon contact, and weapon in pursuit. The operational objectives of the vehicle are: reach the destination, and disengage the pursuer. These define the strategy table shown below. The navigation schemes have been arranged on the table according to the navigation subproblems they address. Also shown on the table is the traditional course of action, the use of countermeasure devices. A quick glance at the table shows the considerable coverage afforded by the scheme set.
The navigation schemes are grouped into two classes: global navigation schemes and local navigation schemes. Global navigation is used to establish a course for our vehicle that takes into account the known location of other stationary or moving vehicles, and the destination point. Three schemes are presented: one based on the application of computational geometry, and two based on the solution of a system of central forces and potential fields. Local navigation is used to generate a course that temporarily disregards the vehicle's destination and seeks only to defeat an approaching weapon.
The schemes are employed as follows. The vehicle begins its journey following a course that was established during pre-mission planning based on the location of other vehicles known to exist in the region of interest. As it transits through the region the vehicle becomes aware of new threats. When this occurs global navigation is called upon to establish a new course. If a new threat happens to be a weapon then local navigation is called upon to establish a course that defeats the incoming weapon. Once the weapon is defeated the vehicle invokes global navigation to lay out a new course.
The two main classes of Known players in the game are Evader and Pursuer. Evader represents the "own vehicle", controlled by the user. Pursuers are subdivided into two classes: Primary and Secondary. Primary Pursuers represent the enemy vehicles, and Secondary Pursuers represent the weapons they launch (e.g., missiles). Shadowing Players are the countermeasure devices used to obscure the perception of the opponent. A Shadowing Player is classified as being either an Evader Shadowing Player or a Pursuer Shadowing Player, according to which side launched it. Neutral players are entities which are encountered but are not involved in the conflict and pose no threat to either side.
Each of the classes above has characteristics or "slots" which are particular to it. These slots are listed in Figure 4. Each class inherits all the slots of all its ancestors in the hierarchy. Notice that not every class in the hierarchy has slots which are unique to it. For instance, Primary and Secondary Pursuers have all the same slots, but they need to be distinguished in the hierarchy because of the qualitative differences between the two.
| Type of Data | Class | |||||
| Player | Known | Evader | Pursuer | Shadowing Player | ||
| Sensory Data | Spatial | Position Speed Range Bearing Heading Event | n/a | Home Destination | n/a | n/a |
| Descriptive | Contact ID Classification Confidence | n/a | Inventory | Effectiveness Inventory | Effectiveness | |
| A priori Data | n/a | Lifetime MaxSpeed Perception | Risk Level Panic Distance Max Safe Distance | n/a | Delay Duration Spatial Effectiveness | |
The a priori data slots reflect knowledge gained previously about a player's behavior and abilities. The sensory data slots store the dynamic information received by the Identifier. This datum can be either "spatial" or "descriptive." Spatial data relate to the location and movements of a player. Descriptive data pertain to a player's dynamic behavior and capabilities.
Maintenance: Sensor data are received by the Identifier in the form of "contact reports." A contact report is given for each entity detected by the evader's sensors. The data contained in these contact reports are shown in Figure 5. Upon receiving the contact report, the Identifier first looks at the "Classification" slot, which contains the class to which the player belongs. The Identifier uses the name provided in "ContactID" to see whether this class has an instance by this name. If not, a new instance is created in the appropriate class.
| Contact Report Data | |
|---|---|
| Spatial | Range Bearing Heading Speed Event |
| Descriptive | Contact ID Time Stamp Classification Confidence |
Figure 5: Contact Report Data
Local Navigation Methodologies: Several local evasion control algorithms have been developed and tested in a variety of one-on-one and two-on-one situations; these schemes are designed to handle a single pursuer. The evader's destination is usually disregarded while local navigation rules are fired; the eight schemes are:
The last two local scheme take the evader's destination into account (anti-pure pursuit II and anti-proportional guidance for two proportionally-guided pursuers).
At each step, OwnShip was given the choice of using one of the above control algorithms or heading directly toward his destination. Each algorithm had conditions under which it would initiate and terminate. The conditions were based on the range from the evader to the pursuer. Some promising results were obtained, but further work is necessary to determine the best conditions. Currently we are experimenting with using conditions based on threat and closing velocity as well as range. Ultimately it is hoped that genetic algorithms can be employed to assist in this tuning process.
Global Navigation (multi-pursuer situations): Three schemes have been developed to handle global navigation when faced with multi-pursuer engagements; they are:
Earlier developments of algorithms for heuristic evasion rules (e.g. RunFar, Travel, etc.) as well as an optimal control algorithm based on discrete optimization using Box's algorithm and the Hamiltonian equation were reported and published in 1992-93. For more recent results we refer the interest readers to our 1995 publications.
Concluding comments: The tactical decision aid is currently running on two platforms: a 33 MHz, `386DX (Dell 333DTM;) and a Dell 66MHz, '486DX personal computer using the KAPPA-PCTM; and ToolBookTM; software packages. These packages operate by interpreting source code written in their respective native language. The scenario generator was coded in the KAPPA-PC language KAL, translated to C using the KAL compiler; it has been compiled to executable code using the Borland C++ compiler.
In its present form the TDA implementation would be adequate for vehicles where sensor reports occur at intervals of 5 seconds or more. Translation of the native source code into C code, followed by the traditional compilation and linking steps, is expected to improve the system performance considerably. Our goal is to process reports arriving at 1 second or less intervals. With the availability of much faster processors, and array processor boards, we do not anticipate any major obstacles in confronting a system with the processing power needed to achieve this type of performance.
Furthermore, while the context of the discussion is military in nature the problem is not unique to that environment. The navigation schemes presented are applicable to other areas, e.g., autonomous vehicle navigation, intelligent vehicle-highway systems (IVHS), and commercial aircraft navigation. For autonomous vehicles, for example, Voronoi diagrams can be used to navigate terrain features such as mountains, lakes, and urban areas. In the IVHS area the concept of trajectory forces can be applied to vehicle control in an automated highway. And, in civil aviation Voronoi diagrams can be used to negotiate severe weather fronts, and line-of-sight forces can be used to ensure safe spacing between aircraft in flight.
