An official website of the United States government
The line coverage problem is the coverage of linear environment features (e.g., road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e.g., battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge- Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4,658 edges and 4,504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network.
more »
« less
Path Planning for Optimal Coverage of Areas with Nonuniform Importance
Coverage of an inaccessible or challenging region with potential health and safety hazards, such as in a volcanic region, is difficult yet crucial from scientific and meteorological perspectives. Areas contained within the region often provide valuable information of varying importance. We present an algorithm to optimally cover a volcanic region in Hawai`i with an unmanned aerial vehicle (UAV). The target region is assigned with a nonuniform coverage importance score distribution. For a specified battery capacity of the UAV, the optimization problem seeks the path that maximizes the total coverage area and the accumulated importance score while penalizing the revisiting of the same area. Trajectories are generated offline for the UAV based on the available power and coverage information map. The optimal trajectory minimizes the unspent battery power while enforcing that the UAV returns to its starting location. This multi-objective optimization problem is solved by using sequential quadratic programming. The details of the competitive optimization problem are discussed along with the analysis and simulation results to demonstrate the applicability of the proposed algorithm.
more »
« less
- PAR ID:
- 10314696
- Date Published:
- Journal Name:
- AIAA SCITECH 2022 Forum
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study downlink transmission in a multi-band heterogeneous network comprising unmanned aerial vehicle (UAV) small base stations and ground-based dual mode mmWave small cells within the coverage area of a microwave (μW) macro base station. We formulate a two-layer optimization framework to simultaneously find efficient coverage radius for the UAVs and energy efficient radio resource management for the network, subject to minimum quality-of-service (QoS) and maximum transmission power constraints. The outer layer derives an optimal coverage radius/height for each UAV as a function of the maximum allowed path loss. The inner layer formulates an optimization problem to maximize the system energy efficiency (EE), defined as the ratio between the aggregate user data rate delivered by the system and its aggregate energy consumption (downlink transmission and circuit power). We demonstrate that at certain values of the target SINR τ introducing the UAV base stations doubles the EE. We also show that an increase in τ beyond an optimal EE point decreases the EE.more » « less
-
In this study, we design and analyze a reliability-oriented downlink wireless network assisted by unmanned aerial vehicles (UAVs). This network employs non-orthogonal multiple access (NOMA) transmission and finite blocklength (FBL) codes. In the network, ground user equipments (GUEs) request content from a remote base station (BS), and there are no direct connections between the BS and the GUEs. To address this, we employ a UAV with a limited caching capacity to assist the BS in completing the communication. The UAV can either request uncached content from the BS and then serve the GUEs or directly transmit cached content to the GUEs. In this paper, we first introduce the decoding error rate within the FBL regime and explore caching policies for the UAV. Subsequently, we formulate an optimization problem aimed at minimizing the average maximum end-to-end decoding error rate across all GUEs while considering the coding length and maximum UAV transmission power constraints. We propose a two-step alternating optimization scheme embedded within a deep deterministic policy gradient (DDPG) algorithm to jointly determine the UAV trajectory and transmission power allocations, as well as blocklength of downloading phase, and our numerical results show that the combined learning-optimization algorithm efficiently addresses the considered problem. In particular, it is shown that a well-designed UAV trajectory, relaxing the FBL constraint, increasing the cache size, and providing a higher UAV transmission power budget all lead to improved performance.more » « less
-
This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area.more » « less
-
In this paper, we investigate the reliability in an unmanned aerial vehicle (UAV) assisted caching-based downlink network where non-orthogonal multiple access (NOMA) transmission and finite blocklength (FBL) codes are adopted. In this network, the ground user equipments (GUEs) request contents from a distant base station (BS) but there are no direct links from the BS to the GUEs. A UAV with limited cache size is employed to assist the BS to complete the communication by either first requesting the uncached contents from the BS and then serving the GUEs or directly sending the cached contents to the GUEs. In this setting, we first introduce the decoding error rate in the FBL regime as well as the caching policy at the UAV, and subsequently we construct an optimization problem aiming to minimize the maximum end-to-end decoding error rate among all GUEs under both coding length and maximum UAV transmission power constraints. A two-step alternating algorithm is proposed to solve the problem and numerical results demonstrate that our algorithm can solve the optimization problem efficiently. More specifically, loosening the FBL constraint, enlarging the cache size and having a higher transmission power budget at the UAV lead to an improved performance.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.2514/6.2022-2546
