This paper considers the trajectory design problem for unmanned aerial vehicles (UAVs) via meta-reinforcement learning. It is assumed that the UAV can move in different directions to explore a specific area and collect data from the ground nodes (GNs) located in the area. The goal of the UAV is to reach the destination and maximize the total data collected during the flight on the trajectory while avoiding collisions with other UAVs. In the literature on UAV trajectory designs, vanilla learning algorithms are typically used to train a task-specific model, and provide near-optimal solutions for a specific spatial distribution of the GNs. However, this approach requires retraining from scratch when the locations of the GNs vary. In this work, we propose a meta reinforcement learning framework that incorporates the method of Model-Agnostic Meta-Learning (MAML). Instead of training task-specific models, we train a common initialization for different distributions of GNs and different channel conditions. From the initialization, only a few gradient descents are required for adapting to different tasks with different GN distributions and channel conditions. Additionally, we also explore when the proposed MAML framework is preferred and can outperform the compared algorithms.
more »
« less
Fine-Grained Trajectory Optimization of Multiple UAVs for Efficient Data Gathering from WSNs
The increasing availability of autonomous smallsize
Unmanned Aerial Vehicles (UAVs) has provided a promising
way for data gathering from Wireless Sensor Networks (WSNs)
with the advantages of high mobility, flexibility, and good speed.
However, few works considered the situations that multiple UAVs
are collaboratively used and the fine-grained trajectory plans
of multiple UAVs are devised for collecting data from network
including detailed traveling and hovering plans of them in the
continuous space. In this paper, we investigate the problem of
the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which
m UAVs are used to collect data from a given WSN, where
m ≥ 1. The problem entails not only to find the flight paths
of multiple UAVs but also to design the detailed hovering and
traveling plans on their paths for efficient data gathering from
WSN. The objective of the problem is to minimize the maximum
flight time of UAVs such that all sensory data of WSN is collected
by the UAVs and transported to the base station. We first propose
a mathematical model of the FTP problem and prove that the
problem is NP-hard. To solve the FTP problem, we first study
a special case of the FTP problem when m = 1, called FTP
with Single UAV (FTPS) problem. Then we propose a constantfactor
approximation algorithm for the FTPS problem. Based on
the FTPS problem, an approximation algorithm for the general
version of the FTP problem when m > 1 is further proposed,
which can guarantee a constant factor of the optimal solution.
Afterwards, the proposed algorithms are verified by extensive
simulations.
more »
« less
- Award ID(s):
- 1907472
- NSF-PAR ID:
- 10280175
- Date Published:
- Journal Name:
- IEEE/ACM Transactions on Networking
- ISSN:
- 1063-6692
- Page Range / eLocation ID:
- 1 to 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost k-cycle free graphs, for any constant k≥ 4. Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many 4- or 5-cycles in a worst-case instance had been the obstacle towards resolving major open questions. Hardness of approximation: Are there distance oracles with m1+o(1) preprocessing time and mo(1) query time that achieve a constant approximation? Existing algorithms with such desirable time bounds only achieve super-constant approximation factors, while only 3− factors were conditionally ruled out (Pătraşcu, Roditty, and Thorup; FOCS 2012). We prove that no O(1) approximations are possible, assuming the 3-SUM or APSP conjectures. In particular, we prove that k-approximations require Ω(m1+1/ck) time, which is tight up to the constant c. The lower bound holds even for the offline version where we are given the queries in advance, and extends to other problems such as dynamic shortest paths. The 4-Cycle problem: An infamous open question in fine-grained complexity is to establish any surprising consequences from a subquadratic or even linear-time algorithm for detecting a 4-cycle in a graph. This is arguably one of the simplest problems without a near-linear time algorithm nor a conditional lower bound. We prove that Ω(m1.1194) time is needed for k-cycle detection for all k≥ 4, unless we can detect a triangle in √n-degree graphs in O(n2−δ) time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms.more » « less
-
more » « less
Abstract We study the problem of planning a tour for an energy‐limited Unmanned Aerial Vehicle (UAV) to visit a set of sites in the least amount of time. We envision scenarios where the UAV can be recharged at a site or along an edge either by landing on stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as mobile recharging stations. This leads to a new variant of the Traveling Salesperson Problem (TSP) with mobile recharging stations. We present an algorithm that finds not only the order in which to visit the sites but also when and where to land on the charging stations to recharge. Our algorithm plans tours for the UGVs as well as determines the best locations to place stationary charging stations. We study three variants for charging: Multiple stationary charging stations, single mobile charging station, and multiple mobile charging stations. As the problems we study are nondeterministic polynomial time (NP)‐Hard, we present a practical solution using Generalized TSP that finds the optimal solution that minimizes the total time, subject to the discretization of battery levels. If the UGVs are slower than the UAVs, then the algorithm also finds the minimum number of UGVs required to support the UAV mission such that the UAV is not required to wait for the UGV. Our simulation results show that the running time is acceptable for reasonably sized instances in practice. We evaluate the performance of our algorithm through simulations and proof‐of‐concept field experiments with a fully autonomous system of one UAV and UGV.
-
Small Unmanned Aircraft Systems (sUAS) will be an important component of the smart city and intelligent transportation environments of the near future. The demand for sUAS related applications, such as commercial delivery and land surveying, is expected to grow rapidly in next few years. In general, sUAS traffic scheduling and management functions are needed to coordinate the launching of sUAS from different launch sites and plan their trajectories to avoid conflict while considering several other constraints such as expected arrival time, minimum flight energy, and availability of communication resources. However, as the airbone sUAS density grows in a certain area, it is difficult to foresee the potential airspace and communications resource conflicts and make immediate decisions to avoid them. To address this challenge, we present a temporal and spatial routing algorithm for sUAS trajectory management in a high density urban area. It plans sUAS movements in a spatial and temporal maze with the consideration of obstacles that are either static or dynamic in time. The routing allows the sUAS to avoid static no-fly areas (i.e. static obstacles) or other in-flight sUAS and areas that have congested communication resources (i.e. dynamic obstacles). The algorithm is evaluated using an agent-based simulation platform. The simulation results show that the proposed algorithm outperforms reference route management algorithms in many areas, especially in processing speed and memory efficiency. Detailed comparisons are provided for the sUAS flight time, the overall throughput, the conflict rate and communication resource utilization. The results demonstrate that our proposed algorithm can be used as a solution to improve the efficiency of airspace and communication resource utilization for next generation smart city and smart transportation.more » « less
-
Small Unmanned Aircraft Systems (sUAS) will be an important component of the smart city and intelligent transportation environments of the near future. The demand for sUAS related applications, such as commercial delivery and land surveying, is expected to grow rapidly in next few years. In general, sUAS traffic routing and management functions are needed to coordinate the launching of sUAS from different launch sites and determine their trajectories to avoid conflict while considering several other constraints such as expected arrival time, minimum flight energy, and availability of communication resources. However, as the airborne sUAS density grows in a certain area, it is difficult to foresee the potential airspace and communications resource conflicts and make immediate decisions to avoid them. To address this challenge, we present a temporal and spatial routing algorithm and simulation platform for sUAS trajectory management in a high density urban area that plans sUAS movements in a spatial and temporal maze taking into account obstacles that are either static or dynamic in time. The routing allows the sUAS to avoid static no-fly areas (i.e. static obstacles) or other in-flight sUAS and areas that have congested communication resources (i.e. dynamic obstacles). The algorithm is evaluated using an agent-based simulation platform. The simulation results show that the proposed algorithm outperforms other route management algorithms in many areas, especially in processing speed and memory efficiency. Detailed comparisons are provided for the sUAS flight time, the overall throughput, conflict rate and communication resource utilization. The results demonstrate that our proposed algorithm can be used to address the airspace and communication resource utilization needs for a next generation smart city and smart transportation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TNET.2020.3027555
