Routing and Scheduling of Spatio-Temporal Tasks for Optimizing Airborne Sensor System Utilization


Airborne image sensing systems are equipped on piloted or remotely-piloted aerial vehicles to collect imagery data. Often the equipped image sensors are mostly underutilized. The objective is to increase the sensor system utilization by enabling dynamic multitasking so that ground operators can access and transmit sensor task requests to an aerial vehicle. However, this may deviate the original route of an aerial vehicle. In this paper, we will be investigating this new problem of generating a new route to follow, as long as the assigned target points and original waypoints are not affected. Our goal is to find an optimal route on the fly between the given original waypoints such that it satisfies the maximum number of sensor task requests from ground users, of minimum sum of deviations subject to maximum deviation from the original route, without violating the original mission and flight maneuvering constraints. With the given constraints, finding an optimal route is an NP-hard problem. Therefore, we proposed two heuristic-based methods: namely, the FPCA approach that utilizes the idea of footprint diameter, and the SWCA approach that tackles this problem via the use of task clustering. The performance of these algorithms are compared through experiments using data from real flight trajectories. Our results show that SWCA outperforms FPCA in most settings.

Meeting Name

10th ACM International Conference on Distributed and Event-Based Systems, DEBS 2016 (2016: Jun. 20-24, Irvine, CA)


Computer Science

Research Center/Lab(s)

Intelligent Systems Center


This work was funded by the National Science Foundation (NSFDGE-1433659, NSF-IIP-1332002), Department of Education (P200A120110).

Keywords and Phrases

Computational complexity; Embedded systems; Flight paths; Heuristic methods; Maneuverability; Software architecture; Vehicles; Air-borne sensors; Airborne images; Dynamic multitasking; Flight trajectory; Ground operator; Routing and scheduling; Spatio temporal; Task clustering; Optimization; Airborne sensor utilization; Optimal flight trajectory

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2016 Association for Computing Machinery (ACM), All rights reserved.

Publication Date

01 Jun 2016