UAV Trajectory Planning with Network Age of Information Minimization

Yifan Luo, Jin Xu, Junting Chen, Jianwei HuangWCNC 2022 · OpenReview

Abstract

We investigate an unmanned aerial vehicle (UAV) trajectory planning problem for minimizing the Age of Information (AoI) over a sensor network defined on a square grid graph. Despite that the AoI-minimal trajectory planning problem is NP-hard, we derive the fundamental limit of minimum network AoI achieved among all feasible UAV trajectories. We show that such a lower bound is only achievable for graphs with a Hamiltonian Cycle (HC). Based on this finding, we develop an HPA algorithm for graphs with at least one Hamiltonian Path (HP). It achieves a time-average network AoI no more than of that of the optimal trajectory. For more general graphs, we propose a tree-searching algorithm (TSA) which achieves a time-average network AoI at most twice that of the optimal trajectory with a polynomial-time complexity. Numerical results show that the average performance of TSA could be much better than the theoretical bound, and both two algorithms significantly outperform the baseline scheme.
BibTeX
@inproceedings{luo2022uav,
  author = {Yifan Luo and Jin Xu and Junting Chen and Jianwei Huang},
  title = {{UAV Trajectory Planning with Network Age of Information Minimization}},
  booktitle = {WCNC},
  year = {2022},
  url = {https://openreview.net/forum?id=il6eYXbR7w},
}

Loading related content...

Figure