An official website of the United States government
To provide a reliable wireless uplink for users in a given ground area, one can deploy Unmanned Aerial Vehicles (UAVs) as base stations (BSs). In another application, one can use UAVs to collect data from sensors on the ground. For a power efficient and scalable deployment of such flying BSs, directional antennas can be utilized to efficiently cover arbitrary 2-D ground areas. We consider a large-scale wireless path-loss model with a realistic angle-dependent radiation pattern for the directional antennas. Based on such a model, we determine the optimal 3-D deployment of N UAVs to minimize the average transmit-power consumption of the users in a given target area. The users are assumed to have identical transmitters with ideal omnidirectional antennas and the UAVs have identical directional antennas with given half-power beamwidth (HPBW) and symmetric radiation pattern along the vertical axis. For uniformly distributed ground users, we show that the UAVs have to share a common flight height in an optimal power-efficient deployment, by simulations. We also derive in closed-form the asymptotic optimal common flight height of N UAVs in terms of the area size, data-rate, bandwidth, HPBW, and path-loss exponent.
more »
« less
An algorithm with exact bounds for coverage path planning in UAV-based search and rescue under windy conditions
Unmanned aerial vehicles (UAVs) are increasingly utilized in global search and rescue efforts, enhancing operational efficiency. In these missions, a coordinated swarm of UAVs is deployed to efficiently cover expansive areas by capturing and analyzing aerial imagery and footage. Rapid coverage is paramount in these scenarios, as swift discovery can mean the difference between life and death for those in peril. This paper focuses on planning the flight paths for multiple UAVs in windy conditions to efficiently cover rectangular search areas in minimal time. We address this challenge by dividing the search area into a grid network and formulating it as a mixed-integer program (MIP). We derive a precise lower bound for the objective function and develop a fast algorithm with a proven capability of finding either the optimal solution or a near-optimal solution with a constant absolute gap to optimality. Notably, as the problem complexity increases, our solution exhibits a diminishing relative optimality gap while maintaining negligible computational costs compared to the MIP approach. The fast execution speed of the algorithms is demonstrated by numerical experiments with area sizes up to 10000 grid cells.
more »
« less
- Award ID(s):
- 1944068
- PAR ID:
- 10643483
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Computers operations research
- ISSN:
- 0305-0548
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Unmanned aerial vehicles (UAVs) can collaborate as teams to accomplish diverse mission objectives, such as target search and tracking. This paper introduces a method that leverages accumulated target-density information over the course of a UAV mission to adapt path-planning rewards, guiding UAVs toward areas with a higher likelihood of target presence. The target density is modeled using a Gaussian process, which is iteratively updated as the UAVs search the environment. Unlike conventional search algorithms that prioritize unexplored regions, this approach incentivizes revisiting target-rich areas. The target-density information is shared across UAVs using decentralized consensus filters, enabling cooperative path selection that balances the exploration of uncertain regions with the exploitation of known high-density areas. The framework presented in this paper provides an adaptive cooperative search method that can quickly develop an understanding of the region’s target-dense areas, helping UAVs refine their search. Through Monte Carlo simulations, we demonstrate this method in both a 2D grid region and road networks, showing up to a 26% improvement in target density estimates.more » « less
-
UAVs (unmanned aerial vehicles) or drones are promising instruments for video-based surveillance. Various applications of aerial surveillance use object detection programs to detect target objects. In such applications, three parameters influence a drone deployment strategy: the area covered by the drone, the latency of target (object) detection, and the quality of the detection output by the object detector. Previous works have focused on improving Pareto optimality along the area-latency frontier or the area-quality frontier, but not on the combined area-latency-quality frontier, because of which these solutions are sub-optimal for drone-based surveillance. We explore a three way tradeoff between area, latency, and quality in the context of autonomous aerial surveillance of targets in an area using drones with cameras and an object detection program. We propose Vega, a drone deployment framework that captures these tradeoffs to deploy drones efficiently. We make three contributions with Vega. First, we characterize the ability of the state-of-the-art mobile object detector, EfficientDet [CPVR '20], to detect objects from varying drone altitudes using confidence and IoU curves vs. drone altitude. Second, based on these characteristics of the detector, we propose a set of two algorithmic primitives for drone-based maneuvers, namely DroneZoom and DroneCycle. Using these two primitives, we obtain a more optimal Pareto frontier between our three target parameters - coverage area, detection latency, and detection quality for a single drone system. Third, we scale out our findings to a swarm deployment using higher-order Voronoi tessellations, where we control the swarm's spatial density using the Voronoi order to further lower the detection latency while maintaining detection quality.more » « less
-
In modeling battery energy storage systems (BESS) in power systems, binary variables are used to represent the complementary nature of charging and discharging. A conventional approach for these BESS optimization problems is to relax binary variables and convert the problem into a linear program. However, such linear programming relaxation models can yield unrealistic fractional solutions, such as simultaneous charging and discharging. In this paper, we develop a regularized mixed-integer programming (MIP) model for the optimal power flow (OPF) problem with BESS. We prove that, under mild conditions, the proposed regularized model admits a zero integrality gap with its linear programming relaxation; hence, it can be solved efficiently. By studying the properties of the regularized MIP model, we show that its optimal solution is also near optimal to the original OPF problem with BESS, thereby providing a valid and tight upper bound for the OPF problem with BESS. The use of the regularized MIP model allows us to solve a trilevel [Formula: see text]-[Formula: see text]-[Formula: see text] network contingency problem, which is otherwise intractable to solve. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: N. Jiang (as a graduate student at the Georgia Institute of Technology) and W. Xie were supported in part by the National Science Foundation [Grant 2246414] and the Office of Naval Research [Grant N00014-24-1-2066]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0771 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0771 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .more » « less
-
We consider multiple unmanned aerial vehi- cles (UAVs) serving a density of ground terminals (GTs) as mobile base stations. The objective is to minimize the outage probability of GT-to-UAV transmissions. In this context, the optimal placement of UAVs under different UAV altitude constraints and GT densities is studied. First, using a random deployment argument, a general upper bound on the optimal outage probability is found for any density of GTs and any number of UAVs. Lower bounds on the performance of optimal deployments are also deter- mined. The upper and lower bounds are combined to show that the optimal outage probability decays exponentially with the number of UAVs for GT densities with finite support. Next, the structure of optimal deployments are studied when the common altitude constraint is large. In this case, for a wide class of GT densities, it is shown that all UAVs should be placed to the same location in an optimal deployment. A design implication is that one can use a single multi-antenna UAV as opposed to multiple single-antenna UAVs without loss of optimality. Numerical optimization of UAV deployments are carried out using particle swarm optimization. Simulation results are also presented to confirm the analytical findings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.cor.2024.106822
