Search Constraints

Start Over
Filtering by: Date Created 2014-01 Remove constraint Date Created: 2014-01

Search Results

  • A Formulation and Heuristic Approach to Task Allocation and Routing of UAVs under Limited Communication

    Article thumbnail: A Formulation and Heuristic Approach to Task Allocation and Routing of UAVs under Limited Communication
    Type:
    Article
    Description/Abstract:
    Unmanned Air Vehicle (UAV) teams are anticipated to provide surveillance support through algorithms, software, and automation. It is desirable to have algorithms that compute effective and efficient routes for multiple UAVs across a variety of missions. These algorithms must be realizable, practical, and account for uncertainties. In surveillance missions, UAVs act as mobile wireless communication nodes in a larger, underlying network consisting of targets where information is to be collected and base stations where information is to be delivered. The role of UAVs in these networks has primarily been to maintain or improve connectivity while undervaluing routing efficiency. Moreover, many current routing strategies for UAVs ignore communication constraints even though neglecting communication can lead to suboptimal tour designs. Generating algorithms for autonomous vehicles that work effectively despite these communication restrictions is key for the future of UAV surveillance missions. A solution is offered here based on a variation of the traditional vehicle routing problem and a simple communication model. In this work, the new routing formulation is defined, analyzed, and a heuristic approach is motivated and described. Simulation results show that the heuristic algorithm gives near-optimal results in real-time, allowing it to be used for large problem sizes and extended to dynamic scenarios.
    Creator/Author:
    Cohen, Kelly; Sabo, Chelsea, and Kingston, Derek
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/03/2017
    Date Modified:
    04/05/2017
    Date Created:
    2014-01
    License:
    All rights reserved

  • A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem

    Article thumbnail: A Hierarchical Market Solution to the Min–Max Multiple Depots Vehicle Routing Problem
    Type:
    Article
    Description/Abstract:
    The problem of assigning a group of Unmanned Aerial Vehicles (UAVs) to perform spatially distributed tasks often requires that the tasks will be performed as quickly as possible. This problem can be defined as the Min–Max Multiple Depots Vehicle Routing Problem (MMMDVRP), which is a benchmark combinatorial optimization problem. In this problem, UAVs are assigned to service tasks so that each task is serviced once and the goal is to minimize the longest tour performed by any UAV in its motion from its initial location (depot) to the tasks and back to the depot. This problem arises in many time-critical applications, e.g. mobile targets assigned to UAVs in a military context, wildfire fighting, and disaster relief efforts in civilian applications. In this work, we formulate the problem using Mixed Integer Linear Programming (MILP) and Binary Programming and show the scalability limitation of these formulations. To improve scalability, we propose a hierarchical market-based solution (MBS). Simulation results demonstrate the ability of the MBS to solve large scale problems and obtain better costs compared with other known heuristic solution.
    Creator/Author:
    Sharma, Balaji R.; Cohen, Kelly; Ernest, Nicholas; Kumar, Manish, and Kivelevitch, Elad
    Submitter:
    Kelly Cohen
    Date Uploaded:
    02/03/2017
    Date Modified:
    04/05/2017
    Date Created:
    2014-01
    License:
    All rights reserved