Visual-Navigation-Aware Multi-UAV Waypoint Assignment for Border Surveillance in GNSS-Denied Environments

Abstract Uncrewed Aerial Vehicle (UAV) swarms using visual navigation methods for border surveillance in Global Navigation Satellite System (GNSS)-denied environments have to maintain positional accuracy with recognisable visual features to reduce the risk of being lost en route. A scarcity of visually rich textures is more likely in rural border environments which makes judicious route planning important for successful visual navigation. Existing multi-UAV routing formulations mainly optimise distance, time, or coverage without deeply considering limited key features terrain for visual navigation. This work formulates a waypoint-assignment problem in which terrain navigability and border surveillance coverage are jointly considered. A terrain navigability framework is constructed from operational orthomosaic imagery using Scale-Invariant Feature Transform (SIFT) feature density and response quality. Candidate observation positions are extracted from the constructed navigability map and routes are evaluated using an A* planner. The assignment problem is formulated as a single-depot open min--max multiple Travelling Salesman Problem (mTSP) with two objectives: weakest-link route reliability and swarm union border coverage. Two independent solvers, Non-dominated Sorting Genetic Algorithm II with A-Star Search Algorithm (NSGA-II + A*) and Genetic Algorithm for the Multiple Traveling Salesperson Problem with A-Star Search Algorithm (GA-mTSP + A*), are evaluated with the same routing mechanism. Under the baseline configuration, both approaches achieve approximately 91.0% border coverage, with route-reliability scores of 0.3770 and 0.3707, respectively. Both identify five UAVs as the optimal swarm size under the baseline configuration and NSGA-II requires less computation time.