Learning Highly Accurate Conservative Strategy Based on Graph Neural Network for the Feasibility Prediction of Multi-UAV Task Planning

High-throughput multi-UAV task-planning systems must evaluate diverse task instances under limited computational budgets. However, calling a search-based planner for every candidate instance is costly, whereas rejecting a planner-solvable instance is operationally more consequential. Therefore, we study pre-planner screening for a fixed planning pipeline with three budget-dependent outcomes: Feasible, Infeasible, and Unresolved. Since retaining Unresolved as a distinct outcome prevents budget-limited outcomes from being conflated with infeasibility, we propose CONS-GNN, which represents each candidate instance as a relation-aware heterogeneous UAV–task–region graph and predicts the reference planner’s outcome using only pre-planner information. CONS-GNN rejects an instance only when its predicted probability of infeasibility exceeds a validation-selected threshold; all other instances are forwarded to the planner. We evaluate CONS-GNN on three independently seeded test sets, each containing 10,000 3D multi-UAV task instances. CONS-GNN achieves mean accuracy, macro-F1, and macro-averaged one-vs-rest PR-AUC scores of 0.9517, 0.9388, and 0.9831, respectively. At the selected operating points, it avoids an average of 41.36% of planner calls while rejecting 3 of 12,449 planner-feasible test instances, corresponding to an observed deployment FRR of 0.0241%. Ablation and scalability analyses identify the contributions of individual graph components and assess performance across UAV team sizes. Together, these results indicate that planner-conditioned screening can reduce planner use with few observed false rejections under the evaluated conditions.