Graph neural network and dynamic graph reconstruction based adaptive path planning method for unmanned aerial vehicles(UAVs) in three-dimensional environments

Abstract In post-disaster urban search and rescue, multirotor unmanned aerial vehicles must navigate cluttered 3D spaces to search for survivors and assess passability inside collapsed structures and narrow corridors. Smoke, dust, occlusion, and moving objects make the environment partially observable and rapidly time-varying, which complicates real-time, dynamically feasible, collision-free planning. We propose a graph-based framework that couples spatiotemporal path prediction with probabilistic scene completion. From multi-sensor observations, we build a local environment graph at each time step and inject temporal encodings into node and edge features. A multi-layer spatiotemporal graph neural network (GNN) performs cross-temporal message passing to learn occupancy and motion patterns, and predicts feasible paths under dynamics and collision-avoidance constraints. To reason beyond the field of view, a conditional variational graph autoencoder reconstructs a global environment graph and outputs occupancy and motion uncertainty. We convert this uncertainty into chance constraints and risk costs for trajectory optimization, and update edge weights and connectivity online to follow fast environmental changes. Under the same compute budget, our method achieves higher task success and lower collision rates than Deep Q-Network, GNN-rapidly-exploring random tree (RRT), and *RRT*, especially under heavy occlusion and fast dynamics.