skip to main content

Title: Threat-Aware Selection for Target Engagement
This paper investigates the scheduling problem related to engaging a swarm of attacking drones with a single defensive turret. The defending turret must turn, with a limited slew rate, and remain facing a drone for a dwell time to eliminate it. The turret must eliminate all the drones in the swarm before any drone reaches the turret. In 2D, this is an example of a Traveling Salesman Problem with Time Windows (TSPTW) where the turret must visit each target during the window. In 2D, the targets and turret are restricted to a plane and the turret rotates with one degree of freedom. In 3D, the turret can pan and tilt, while the drones attempt to reach a safe zone anywhere along the vertical axis above the turret. This 3D movement makes the problem more challenging, since the azimuth angles of the turret to the drones vary as a function of time. This paper investigates the theoretical optimal solution for simple swarm configurations. It compares heuristic approaches for the path scheduling problem in 2D and 3D using a simulation of the swarm behavior. It provides results for an improved heuristic approach, the Threat-Aware Nearest Neighbor.  more » « less
Award ID(s):
1553063 2130793 1849303
Author(s) / Creator(s):
Date Published:
Journal Name:
18th IEEE International Conference on Automation Science and Engineering, CASE
Page Range / eLocation ID:
2042 to 2048
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. This paper investigates the pursuit-evasion problem of a defensive gun turret and one or more attacking drones. The turret must "visit" each attacking drone once, as quickly as possible, to defeat the threat. This constitutes a Shortest Hamiltonian Path (SHP) through the drones. The investigation considers situations with increasing fidelity, starting with a 2D kinematic model and progressing to a 3D dynamic model. In 2D we determine the region from which one or more drones can always reach a turret, or the region close enough to it where they can evade the turret. This provides optimal starting angles for n drones around a turret and the maximum starting radius for one and two drones.We show that safety regions also exist in 3D and provide a controller so that a drone in this region can evade the pan-tilt turret. Through simulations we explore the maximum range n drones can start and still have at least one reach the turret, and analyze the effect of turret behavior and the drones’ number, starting configuration, and behaviors. 
    more » « less
  2. null (Ed.)
    Unmanned Aerial Vehicles (UAVs) or drones are increasingly used for urban applications like traffic monitoring and construction surveys. Autonomous navigation allows drones to visit waypoints and accomplish activities as part of their mission. A common activity is to hover and observe a location using on-board cameras. Advances in Deep Neural Networks (DNNs) allow such videos to be analyzed for automated decision making. UAVs also host edge computing capability for on-board inferencing by such DNNs. To this end, for a fleet of drones, we propose a novel Mission Scheduling Problem (MSP) that co-schedules the flight routes to visit and record video at waypoints, and their subsequent on-board edge analytics. The proposed schedule maximizes the utility from the activities while meeting activity deadlines as well as energy and computing constraints. We first prove that MSP is NP-hard and then optimally solve it by formulating a mixed integer linear programming (MILP) problem. Next, we design two efficient heuristic algorithms, JSC and VRC, that provide fast sub-optimal solutions. Evaluation of these three schedulers using real drone traces demonstrate utility–runtime trade-offs under diverse workloads. 
    more » « less
  3. Drones are receiving popularity with time due to their advanced mobility. Although they were initially deployed for military purposes, they now have a wide array of applications in various public and private sectors. Further deployment of drones can promote the global economic recovery from the COVID-19 pandemic. Even though drones offer a number of advantages, they have limited flying time and weight carrying capacity. Effective drone schedules may assist with overcoming such limitations. Drone scheduling is associated with optimization of drone flight paths and may include other features, such as determination of arrival time at each node, utilization of drones, battery capacity considerations, and battery recharging considerations. A number of studies on drone scheduling have been published over the past years. However, there is a lack of a systematic literature survey that provides a holistic overview of the drone scheduling problem, existing tendencies, main research limitations, and future research needs. Therefore, this study conducts an extensive survey of the scientific literature that assessed drone scheduling. The collected studies are grouped into different categories, including general drone scheduling, drone scheduling for delivery of goods, drone scheduling for monitoring, and drone scheduling with recharge considerations. A detailed review of the collected studies is presented for each of the categories. Representative mathematical models are provided for each category of studies, accompanied by a summary of findings, existing gaps in the state-of-the-art, and future research needs. The outcomes of this research are expected to assist the relevant stakeholders with an effective drone schedule design. 
    more » « less
  4. Anti-drone technologies that attack drone clusters or swarms autonomous command technologies may need to identify the type of command system being utilized and the various roles of particular UAVs within the system. This paper presents a set of algorithms to identify what swarm command method is being used and the role of particular drones within a swarm or cluster of UAVs utilizing only passive sensing techniques (which cannot be detected). A testing configuration for validating the algorithms is also discussed. © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 
    more » « less
  5. null (Ed.)
    Given a set of a spatially distributed demand for a specific commodity, potential facility locations, and drones, an agency is tasked with locating a pre-specified number of facilities and assigning drones to them to serve the demand while respecting drone range constraints. The agency seeks to maximize the demand served while considering uncertainties in initial battery availability and battery consumption. The facilities have a limited supply of the commodity being distributed and also act as a launching site for drones. Drones undertake one-to-one trips (from located facility to demand location and back) until their available battery energy is exhausted. This paper extends the work done by Chauhan et al. and presents an integer linear programming formulation to maximize coverage using a robust optimization framework. The uncertainty in initial battery availability and battery consumption is modeled using a penalty-based approach and gamma robustness, respectively. A novel robust three-stage heuristic (R3SH) is developed which provides objective values which are within 7% of the average solution reported by MIP solver with a median reduction in computational time of 97% on average. Monte Carlo simulation based testing is performed to assess the value of adding robustness to the deterministic problem. The robust model provides higher and more reliable estimates of actual coverage under uncertainty. The average maximum coverage difference between the robust optimization solution and the deterministic solution is 8.1% across all scenarios. 
    more » « less