Problem

Maps are valuable, but they are big.

 

Background

We expect the SWARM system to make heavy use of digital maps. Maps will track various types data for a variety of purposes.  Most maps will be two dimensional arrays of values. The most common example of this is the Digital Elevation Model, which may useful (for example) in piloting the craft.

A map of good size and resolution requires a great deal of memory. Base station computers have plenty of memory online and off, but  plane computers do not.

For example, even if all the onboard RAM were devoted to the map, and even if that map were limited to the half-mile-wide strip of terrain under the flightpath, we could only map two hours of flight time. (This assumes  the midlevel resolution of DTED Level2-  the  30 meter mesh).

 

Solution

Data compression is achieved using a quad-tree scheme that exploits the consistency of data. The world covered by the map is divided into four quadrants. Each of these quadrants is represented by either

 

This map has  a rugged mountain range running from the west to the southeast corner which  demands fine detail. It is flanked by foothill quadrants with less variation in elevation. The Northeast quadrant is a flat plain that compresses into a single node.

 

Demonstration

To experiment with the interactive demonstration, load the SWARMADA simulator.

Type 'Q' for QUADTREE to see the nodal compression demonstration.

These controls are active:

Please note that the SWAMADA simulator is currently using 1km data density. We expect far better compression ratios with more dense datasets. An elevation variation of 30m over 1 km is very likely. The same variation over 100 or 30 meters is quite rare. 

Implementation

Data compression is achieved using a quad-tree scheme that exploits the consistency of data. The world covered by the map is divided into four quadrants. Each of these quadrants is represented by either

The compression mechanism determines which form each node takes based on these criteria:

 

During flight preparation, the mapnode data are packed into this format:

Each node structure contains data for four quadrants:

 

QUAD II

 

QUAD I

 

QUAD III

 

QUAD IV

The structure always begins with one flag byte

TERMINAL NODE FLAGS NO FLY NODE
 FLAGS
QUAD I QUAD II QUAD III QUAD IV QUAD I QUAD II QUAD III QUAD IV

 

This is followed by four values each of which is a pointer, elevation or no fly. These three data types are each of different size, so our node structures are of variable length.

FLAGS

2 bits in struct

POINTER 3 byte array index
ELEVATION

2 byte value

NO FLY no data

 

Note that this data packing scheme as not been coded but merely simulated in our current software. Until Phase II, when we might  be loading code into target hardware and conducting precise performance tests, we will use flat 17 byte structures.  

 

 

 

Further Work

Variable Tolerance

The primary determinant of compression ratio is the tolerance factor (the maximum acceptable variation in elevation within any quad).  Currently we compress with a uniform tolerance across the entire map. Future schemes would (automatically or manually) select areas of interest and allocate tolerance accordingly.

 

Blocked regions

Currently no-fly areas are those in which altitude prohibits SWARM flight. A more sophisticated approach would also trim off portions of the map that are unreachable (such as those beyond unpassable mountain ranges) or otherwise forbidden.

 

Ultra Compression

More compression can be achievable at each node::

These techniques will be considered during Phase II of this project, and might reduce data below 50% of the current compression.

 

Related Topics

The structured information n this nodal view of terrain, might be valuable in way-finding and feature recognition.

Nodal compression might be an interesting tool for map creation as map reading. This would be used in various types of surveillance recording.

Even as metaphor, this approach may be instructive. The idea of pruning information density based on degree of interest and  degree of variation can be applied at many levels. It might suggest, for example smarter formations, for example better surveillance patterns than simply painting the territory with a shoulder-to-shoulder front of planes.