UAV Trajectory Optimization for Sensing Exploiting Target Location Distribution Map

Xiangming Du, Shuowen Zhang, Liang Liu

TL;DR

This paper introduces a novel framework for optimizing UAV flight paths to find targets whose exact locations are unknown. By using a "target location distribution map" and a "radio map," the researchers developed algorithms that allow a UAV to maximize its chances of sensing a target while ensuring it never loses its cellular connection or exceeds its battery-limited flight time.

What Problem Does This Paper Address?

Most research on UAV sensing assumes we already know exactly where the target is. In the real world, this is rarely the case. Whether searching for a missing person or monitoring wildlife, we usually only have a probabilistic idea of where a target might be based on historical data or movement patterns.

The challenge is three-fold:

  1. Sensing Uncertainty: The UAV needs to prioritize flying over areas where the target is most likely to appear.
  2. Communication Constraints: To fly safely (especially beyond visual line-of-sight), a cellular-connected UAV must maintain a minimum signal strength (SNR) with ground base stations.
  3. Time/Energy Constraints: The UAV has a limited "fuel tank" (mission time), meaning it cannot simply visit every single point on the map.

Mathematically, this results in a "constrained longest path" problem, which is notoriously difficult to solve (NP-hard) because the UAV wants to take the "longest" path in terms of gathering sensing probability while staying within a "short" distance budget.

Methods

The authors propose a grid-based approach, discretizing the search area into square cells. They utilize two key data structures:

  • Target Location Distribution Map: A matrix representing the probability of a target being in each grid cell.
  • Radio Map: A matrix storing the expected signal quality (SNR) at each grid location.

To solve the optimization problem, they developed three hierarchical solutions:

  • Solution I (Lagrangian Relaxation): This converts the complex sensing maximization problem into a "constrained shortest path" problem. It uses a subgradient-based method to find a high-quality path that respects both signal and distance limits.
  • Solution II (Single-Point Deviation): Building on Solution I, this algorithm identifies high-probability grid points the initial path missed and attempts to "detour" through the single most promising one.
  • Solution III (Multi-Point ACO): This is the most advanced approach. It selects multiple high-probability waypoints and uses Ant Colony Optimization (ACO)—an algorithm inspired by how ants find paths to food—to solve a version of the Traveling Salesman Problem (TSP), creating a sophisticated trajectory that hits as many "hotspots" as possible within the distance budget.

Datasets

The paper relies on simulated environments rather than public datasets to maintain control over experimental variables:

  • Channel Model: They used the 3GPP Urban Micro (UMi) setup to simulate realistic cellular signal propagation.
  • Target Distribution: The "Target Location Distribution Map" was modeled using a 2D Gaussian Mixture Model (GMM), which represents clusters of high-probability areas (e.g., a target likely being near one of two specific landmarks).
  • Grid Setup: A 600m x 600m area was tested with grid granularities of 30m and 60m.

Key Insights and Ideas

  • The "Sensing vs. Distance" Trade-off: The optimal path isn't the shortest one. The UAV must "spend" its distance budget wisely, deviating from the straight line only when the increase in sensing probability justifies the extra battery drain.
  • Lower Bound Transformation: To make the math tractable, the authors transformed the objective function using the relationship between geometric and arithmetic means. This allowed them to turn a "maximization" problem into a "minimization" problem compatible with standard graph theory algorithms like Dijkstra’s.
  • Connectivity as a Filter: The Radio Map acts as a "hard filter." Before even considering sensing, the algorithm prunes the graph of any locations where the cellular signal is too weak, ensuring the resulting path is always safe.

Key Results

  • Superiority over Benchmarks: All three proposed solutions significantly outperformed the "shortest-distance" benchmark.
  • The Power of Detours: In a scenario with a 2700m distance budget, Solution III (the ACO-based approach) achieved a total sensing probability of 0.7404, compared to just 0.1649 for Solution II. This highlights that being able to visit multiple high-probability clusters is crucial.
  • Complexity vs. Performance: Using a finer grid (30m vs. 60m) improved sensing accuracy but increased computation time. However, even with the finer grid, the proposed suboptimal algorithms remained computationally efficient enough for practical use.

Limitations and Future Work

The authors acknowledge a few areas for expansion:

  • 2D vs. 3D: The current model assumes the UAV flies at a constant altitude. Real-world scenarios might require the UAV to change altitude to avoid obstacles or get a better sensor view.
  • Static Maps: The target distribution map is assumed to be known a priori and static. Future work could involve "active sensing," where the UAV updates its probability map in real-time as it gathers new data.
  • Multi-UAV Coordination: The study focuses on a single UAV. Coordinating a swarm of UAVs to cover a distribution map would be a natural next step.

Summary updated

Abstract

In this paper, we study the trajectory optimization of a cellular-connected unmanned aerial vehicle (UAV) which aims to sense the location of a target while maintaining satisfactory communication quality with the ground base stations (GBSs). In contrast to most existing works which assumed the target's location is known, we focus on a more challenging scenario where the exact location of the target to be sensed is unknown and random, while its distribution is known a priori and stored in a novel target location distribution map. Based on this map, the probability for the UAV to successfully sense the target can be expressed as a function of the UAV's trajectory. We aim to optimize the UAV's trajectory between two pre-determined locations to maximize the overall sensing probability during its flight, subject to a GBS-UAV communication quality constraint at each time instant and a maximum mission completion time constraint. Despite the non-convexity and NP-hardness of this problem, we devise three high-quality suboptimal solutions tailored for it with polynomial complexity. Numerical results show that our proposed designs outperform various benchmark schemes.
BibTeX
@misc{du2024uav,
  author = {Xiangming Du and Shuowen Zhang and Liang Liu},
  title = {{UAV Trajectory Optimization for Sensing Exploiting Target Location Distribution Map}},
  year = {2024},
  eprint = {2404.10605},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.10605},
}
Figure