SGPE-S: Evolution of Interpretable Policies for Decentralized Multi-UAV Coverage in Communication- and GNSS-Denied Environments

Coverage by multiple unmanned aerial vehicles (UAVs) under communication and global navigation satellite system (GNSS) denial requires aircraft to make independent decisions from local observations, reduce redundant exploration without continuously sharing maps or motion intentions, and adapt to changes in map structure and team size. Fixed heuristics depend on predefined scoring rules, while learned policies can be sensitive to the training distribution. Language-model-driven program evolution offers a route to automatically constructing interpretable policies, but whole-program scores and textual reflection do not directly encode reusable local-rule information. We propose Single-stage Synergy-Guided Semantic Program Evolution (SGPE-S), which organizes target-scoring policies as condition–response primitives, records the performance of programs containing individual primitives and their combinations, and uses a cross-generation synergy archive to guide candidate generation and rule maintenance. Each UAV independently executes the resulting lightweight frozen program from local observations, without online language-model calls. Independent evolution records show improvements over the initial best program. Standard-map, unseen-configuration, and multi-city GIS blind tests support the coverage efficiency and transferability of the resulting policy. Ablation, model, and parameter studies characterize search gains and variability, while three-dimensional interface adaptation indicates potential for transfer to tasks with more complex dynamics.