Session A1: Alternatives, Backups, Complements to GNSS

Reducing Computational Complexity of Rigidity-Based UAV Trajectory Optimization for Real-Time Cooperative Target Localization
Halim Lee and Jiwon Seo, Yonsei University
Location: Beacon A

Accurate and swift localization of the target is of paramount importance in emergencies. In scenarios where global positioning system (GPS), cellular, or WiFi network-based positioning is unavailable, a network of unmanned aerial vehicles (UAVs) can be utilized to locate the target cooperatively. If the target transmits a radio frequency (RF) signal, UAVs can collect measurements such as time-of-arrival (TOA), angle-of-arrival (AOA), and received signal strength (RSS) to estimate its position. In UAV-enabled cooperative target localization, the trajectory of UAVs plays a crucial role in determining the performance of target localization, impacting both localization accuracy and search time.
Previous studies have primarily employed the Fisher information matrix (FIM) as an optimization metric for UAV trajectories. The Cramer-Rao lower bound (CRLB), which is the reciprocal of the Fisher information, provides a lower bound on the variance of any unbiased estimator. However, our recent work has confirmed that the performance of FIM-based UAV trajectory optimization diminishes when the initial geometric diversity of UAVs is unfavorable, such as when all UAVs commence missions from a single base. In such unfavorable UAV geometry scenarios, the position ambiguity problem can occur, in which multiple candidate position solutions yield similar sensor measurements. To address the position ambiguity problem, our previous work employed the concept of rigidity. In our previous work, we demonstrated that our rigidity-based approach can enhance target localization performance in terms of search time by 28.4% compared to the existing FIM-based approach. Despite its commendable performance, rigidity-based UAV trajectory optimization suffers from a drawback due to its high computational cost, primarily attributed to the singular value decomposition (SVD) operation of the rigidity matrix.
To overcome these limitations, we developed a method to reduce the computational complexity of the rigidity-based UAV trajectory optimization approach in this paper. We utilized 1) randomized SVD, 2) smooth SVD, and 3) vertex pruning to reduce the computational complexity. Randomized SVD approximates the singular values of the original matrix through partial matrix decomposition. Smooth SVD updates singular values for small perturbated or smooth time-varying matrices. When applying smooth SVD, the differential of the singular values can be expressed as a function of the initial SVD and the differential of the rigidity matrix. Consequently, the subsequent SVD can be approximated through simple matrix multiplication once the initial SVD has been computed. Vertex pruning is a method of eliminating vertices that are deemed less informative as the size of the rigidity matrix increases beyond a certain threshold. Our experiment confirmed that the proposed method reduces the computational complexity of solving the trajectory optimization problem from O(l*max(n,m)*min(n,m)^2) to O(1), where l represents the number of iterations for solving the optimization problem, and n and m denote the number of row and column elements of the rigidity matrix, respectively. Despite achieving a significant reduction in computational cost, our investigation revealed no noteworthy decrease in target localization performance, including both search time and root mean squared error (RMSE) of the position solutions. The computational cost reduction method proposed in this paper enables real-time cooperative target localization in emergency scenarios.