Home/Efficient Aerial Coverage Search in Road Networks

Efficient Aerial Coverage Search in Road Networks

Michael Dille and Sanjiv Singh
Carnegie Mellon University, AIAA Conference on Guidance, Navigation, and Control, August, 2013

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


Wide-area coverage is well suited for small unmanned aircraft, however common coverage algorithms are particularly inefficient in many common environments such as urban areas. Classical open-loop spiral or lawn-mower patterns typically cannot represent large sub-regions that are unlikely to contain an object of interest that are thus wastefully covered. More general algorithms can maintain arbitrary likelihood distributions but fundamentally solve a complex continuous-space trajectory optimization problem, requiring a trade-off between look-ahead and computational complexity while providing at best asymptotic coverage guarantees. This paper considers generating global coverage patterns in the space of the coverage area, with specific focus on road networks, and mapping these to UAV actions. A new method is proposed for producing and following such patterns with dynamics-constrained vehicles, compared with existing coverage strategies, and shown to be advantageous in many realistic environments through simulations of real-world aircraft. Results suggest environment density as a metric for algorithm selection given a lack of dominance by any one strategy across all environments.

BibTeX Reference
title = {Efficient Aerial Coverage Search in Road Networks},
author = {Michael Dille and Sanjiv Singh},
booktitle = {AIAA Conference on Guidance, Navigation, and Control},
keyword = {UAV, coverage, search, Traveling Salesman Problem, TSP},
school = {Robotics Institute , Carnegie Mellon University},
month = {August},
year = {2013},
address = {Pittsburgh, PA},