21st Congress of International Council of the Aeronautical Sciences, Melbourne, Australia, 13-18 September, 1998
Paper ICAS-98-6.2.3

ROUTING ALGORITHMS FOR REAL-TIME MISSION MANAGEMENT

Allerton D. J., Gia M. C.
Cranfield University, United Kingdom

Keywords: routing algorithms, real-time mission management

Digital Terrain Elevation Data (DTED) is widely used in Terrain Reference Navigation (TRN) for terrain avoidance, terrain following and mission planning. This paper describes the use of TRN methods applied to real-time mission management to provide dynamic routing between way-points during a mission. The DTED is converted to an oct -tree to compress the terrain and to provide fast access algorithms needed in searching functions to locate obstacles in the terrain database. Locational codes are introduced which are based on Morton ordering to provide pointerless tree structures and to simplify the transformations between oct-tree and quad-tree representations of terrain. The terrain is searched to extract the vertices of obstacles and form a visibility graph of possible routes through the terrain. An optimal route is computed according to specific mission constraints. The paper includes examples of real-time routing running on a PC using a public domain DTED. The use of oct-trees allows a trade-off between the resolution of the route and the extraction time. Several examples are included in the paper to illustrate the capability of the method and the performance of the routing algorithms.

view full paper