Novel Techniques Used
Example of Use
Software Overview
Evaluation
The TEART facility provides terrain analysis tools (line-of-sight visibility, shortest path, etc.) to support the Commander in mission preparation of ASuW (Anti-Surface Warfare) operations:
line of sight visibility: computes the area covered by a sensor from a reference location (latitude, longitude and elevation) given its maximum range. Used to compute friend or foe optical sensor coverage. Up to four results usually returned in a couple of seconds up to 20 minutes.
constrained path: computes the optimal path from one location (latitude, longitude and elevation) to another satisfying various constraints (minimal length, maximal slope, threat areas to avoid, maximal altitude). Used to compute paths of friend or foe FPBs, aircrafts or helicopters avoiding sensor and missile range areas. Up to four results usually returned in a couple of seconds up to 60 minutes.
missile range area: checks if a missile trajectory is effective from the launcher location towards the target location and computes the associated warning time (time of detection by the target). Used to check Harpoon and Penguin missile trajectories. Up to four results usually returned in real-time up to a couple of seconds.
missile trajectory feasibility: computes the interception area of a missile from a reference location of the missile launcher (latitude, longitude and elevation) and given the missile features (maximum range, flight altitude, possible manoeuvres). Used to compute friend or foe Harpoon and Penguin missile range areas. Up to four results usually returned in a couple of seconds up to 30 minutes.
Due to its 'time-critical' implementation, the TEART facility is able to provide a first rough result in near real-time which can then be refined over time according to the availability of CPU resources.
The MPB/SP (Manoeuvre Plan Browser / Situation Predictor) facility provides the OTC with a graphical tool to draw his hypotheses of possible routes for his own units and also the enemy units. Combined with TEART, this facility has a great potential (not yet explored) to assess the threat areas along different routes according to the various on-board sensors and weapons.
The TED facility provides the OTC with a tool for generating coloured elevation maps from Digital Terrain Elevation Data (DTED) and displaying them. Furthermore, TED also provides simple tools for retrieving the altitude of a location and computing the distance between two locations. TED is a generic facility that can be used on both the Naval scenario set in Norway and on the Army scenario set in Italy.
This section describes what aspects of the application of AI, HCI or advanced software engineering in the facility represent an advance on previous work.
Among the three tools developed by MS&I, only TEART is really using innovative techniques, the other tools being ‘baseline tools’ developed to support the demonstrations of TEART. TEART’s novelty lies in the use of approximation techniques for running various terrain elevation based algorithms, in the use of an anytime agent controller and in the use of a modified version of the Djikstra algorithm for computing paths.
The use of the terrain approximation techniques enables reduction of the space of search for the terrain algorithms and therefore enables the user to get faster results at the expense of a minimal loss in quality. Two different types of terrain approximations are computed to make a clear distinction between the enemy and friend perspectives. This helps to ensure the coherency of the intermediate results along the calculation.
The anytime agent controller allows all the requests to be scheduled in a smart way. The algorithm used is based on a modified version of the Earliest Deadline First algorithm . This algorithm ensures that all TEART requests will be scheduled according to the level of terrain approximation used in order to give priority to new requests. Besides, the deadline specified by the user will be taken into account to give priority to the more urgent task of the lowest level. Once the first level of approximation is completed, the anytime agent controller is able to compute CPU time predictions for completing the next levels. This information is then used to schedule the requests in order to avoid the running of requests which cannot be completed on time.
Finally, TEART uses an adaptation of the Djikstra algorithm for computing paths while taking into account various constraints. These constraints can be the results of other TEART requests (e.g. missile range area, line-of-sight visibility area). If refined results appear while computing a path, then TEART will take them into account when computing the next level.
The figure below gives an example of the 3 approximate results and the final result which are returned by TeART when the user asks for a line-of-sight visibility calculation and lets the algorithm compute all the levels. The mark in black (in the centre of the image) shows the location of the enemy sensor. The circle delimits the maximum range of the sensor. The area in red represents the area covered by the sensor (threat area).
Results returned for a TeART line-of-sight visibility calculation
The figure below gives another example of display of results computed by TeART. In this case, it shows 2 different paths which were computed in 2 minutes for a Fast Patrol Boat (FPB) and a helicopter. In both cases, it was specified that the 2 threat areas (a line-of-sight visibility area and missile range area) be avoided while finding the paths. In addition to this constraint, the algorithm for the helicopter path had to take into account a maximum flight altitude (25 meters in this example).
TeART path calculation avoiding threat areas
TeART, TED and MPB/SP are provided as separate software tools, although it is necessary to run TED when running TeART in order to display Digital Terrain Elevation Data as a background.
TeART includes an Anytime Agent Controller, which takes control of a processor in order to provide predictable computation times and to schedule different tasks to optimally trade off solution quality against timeliness.
Operational and technical assessments of TEART, TED and MPB/SP have been performed at MS&I.
As far as technical evaluation is concerned, work has concentrated on TEART, which constitutes the more innovative application developed by MS&I for GRACE. Three main points have been assessed, which are listed below:
the ability of the TEART Anytime Controller to deal with user deadlines,
the quality of the time predictions done by the TEART Anytime Controller,
the quality of the approximated line-of-sight visibility calculations performed by TEART.
The detailed results of this evaluation can be found in PD75a and can be summarized as follows. The TEART Anytime Controller ensures that the deadlines are always met. The quality of time predictions is rather good with a mean deviation from reality of no more than 10%. It has to be noticed that this deviation decreases as the approximation level increases.
The operational evaluation concerned the three tools that MS&I developed. This task was carried out with the help of Jean-Philippe Arnaud (ex Frigate Commander) and Frederic Maury (responsible for Helicopter Mission Planning activities).
TED was estimated for its ability to produce good quality maps (90 meters for a pixel) and MPB/SP could be a very useful tool if used with TEART.
TEART’s interest is twofold: first in a operational mission planning context and secondly in the control of the planned mission. The use of approximated results appears to be very interesting. As such, it allows the Commander to quickly try and test several alternatives. From a general point of view, it enables the use of powerful but time-consuming algorithms in time-constrained situations. The use of the anytime approach is particularly useful since it allows the Commander to issue of initial orders based on first results which he can checked later on when refined results are available. Time predictions given by the TEART Anytime Controller are especially useful to know the current state of calculations since it enables the display to the user of progress bars. It is noted that the anytime approach may be applied to other parts of the planning process where time-critical reasoning is needed.
 |
 |
 |
| Produced by: Peter Martin / Russell Gordon /
Mike Pockney Updated: 30 March 1999 Copyright Logica 1999 |
 |