A Metaheuristic Approach for Inspection and Reconnaissance of Organized Areas

Abstract

In this paper, we present a metaheuristic approach for path planning for area surveillance and inspection using unmanned aerial vehicles. The focus is on organized areas, such as city streets or storage zones. We exploit the row-like spatial organization of these scenarios and formulate the problem as a Distance-Constrained Rural Postman Problem. We represent the area of interest as a graph, where edges correspond to surveillance targets, such as city streets or rows of field storage areas, and vertices to their entry and exit points. The subtour length constraints represent the limited flight time of unmanned aerial vehicles. The goal is then to traverse every target edge exactly once, resulting in paths inspecting the area of interest entirely. We propose a Greedy Randomized Adaptive Search Procedure metaheuristic as a solution to this problem. Furthermore, we show that the same problem formulation and metaheuristic can be used for deep inspection of specific locations identified for further inspection in the previous step.