Reducing Computational Complexity of Rigidity-Based UAV Trajectory Optimization for Real-Time Cooperative Target Localization

Halim Lee and Jiwon Seo

Abstract:	Accurate and swift localization of the target is crucial in emergencies. However, accurate position data of a target mobile device, typically obtained from global navigation satellite systems (GNSS), cellular networks, or WiFi, may not always be accessible to first responders. For instance, 1) accuracy and availability can be limited in challenging signal reception environments, and 2) in regions where emergency location services are not mandatory, certain mobile devices may not transmit their location during emergencies. As an alternative localization method, a network of unmanned aerial vehicles (UAVs) can be employed to passively locate targets by collecting radio frequency (RF) signal measurements, such as received signal strength (RSS). In these situations, UAV trajectories play a critical role in localization performance, influencing both accuracy and search time. Previous studies optimized UAV trajectories using the determinant of the Fisher information matrix (FIM), but its performance declines under unfavorable geometric conditions, such as when UAVs start from a single base, leading to position ambiguity. To address this, our prior work introduced a rigidity-based approach, which improved the search time compared to FIM-based methods in our simulation case. However, the high computational cost of rigidity-based optimization, primarily due to singular value decomposition (SVD), limits its practicality. In this paper, we applied techniques to reduce computational complexity, including randomized SVD, smooth SVD, and vertex pruning. Simulations demonstrate that computational complexity can be reduced from O(l × max(m, n) × min(m, n) 2 ) to O(1), where l is the number of iterations for solving the optimization problem, and m and n are the dimensions of the rigidity matrix. Despite the significant reduction in computational cost, our investigation found no notable decrease in target localization performance, including both search time and root mean squared error (RMSE) of the position estimates. The proposed approach enables real-time UAV-based target localization in emergency scenarios.
Published in:	Proceedings of the 2025 International Technical Meeting of The Institute of Navigation January 27 - 30, 2025 Hyatt Regency Long Beach Long Beach, California
Pages:	80 - 87
Cite this article:	Lee, Halim, Seo, Jiwon, "Reducing Computational Complexity of Rigidity-Based UAV Trajectory Optimization for Real-Time Cooperative Target Localization," Proceedings of the 2025 International Technical Meeting of The Institute of Navigation, Long Beach, California, January 2025, pp. 80-87. https://doi.org/10.33012/2025.20004
Full Paper:	ION Members/Non-Members: 1 Download Credit Sign In