Algorithmic Overview of the Airborne Sensor Rover Route Algorithm


This function was developed to support Air Force Studies and Analysis programs by autogenerating a patrol for ISR aircraft that would cycle through a list of target spots requiring regular monitoring (e.g. grave sites). The objective was to develop an efficient method of flying groups of aircraft through a series of detection areas. The requirements were:

Many possible criteria, e.g. Survivability, were not included in this list.


The targets included in the flight must be defined in terms of:


The sensors assigned against each target set is defined according to the user and can include series of patrol start and end times for each aircraft.


Once the scenario is started the actual route taken for each airborne sensor is dynamically determined and updated throughout its route. At every step of the route the best direction (N, NE, E, SE, S, SW, W, and NW) is determined according to maximizing the number of otherwise targets not recently observed in the mission target set in that area and within reasonable range. This value for visiting every target in the list is weighted by the target priority. The target point is then set to the centroid of the area for a line that comes closest to the bulk of the targets not recently revisited in the selected vicinity. The coordination between multiple roving air sensors working the same target set is achieved by finding the best currently active rover for targets not recently (based on current proximity) visited and only incrementing the value for the rover being directed for targets where it is the best current selection; thereby ignoring targets best visited by other currently patrolling sensors.


There are parameters that could be adjusted in future use, but are currently set. These include the time defining whether a target is “recently” observed. This is currently set to 24 hours. The algorithm does not try to redetect target points covered within the last 24 hours, but will attempt redetecting targets whose information is over 24 hours old.


While perhaps not optimal, this has proven to be a simple, workable method of efficiently revisiting series of target sets by loosely coordinated swarms of airborne sensors (notionally UAVs). Moreover, the algorithm is fast, responsive to changes in target sets (both additions and subtractions as well as changes of priorities) and dynamic reallocation as aircraft become availably or land or are lost.