A Heuristic Algorithm for Optimized Routing of Unmanned Aerial Systems for the Interdiction of Improvised Explosive Devices

Abstract

Improvised explosive devices (IEDs) are effective weapons for insurgents targeting conventional military and security forces. Real-time information gathering about likely use of such weapons is one approach to reduce the effectiveness of IEDs. Unmanned aerial system (UASs) may provide the information gathering capability commanders need to interdict IEDs. Currently, UASs are not systematically utilized in that capacity. This research develops a routing tool that uses column-generation techniques and a greedy algorithm to route UASs through suspected IED locations for the purpose of IED interdiction as it transit to and from command directed missions. In empirical studies of data sets with up to 125 IED locations and missions, the routing tool provides optimal or near-optimal solutions in all instances tested. The tool produces de-conflicted routes for up to three UASs within five minutes of computing time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2008
Accession Number
ADA483643

Entities

People

  • Michael S. Scioletti

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms
  • Autonomy
  • Counter IED

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Artificial Intelligence
  • California
  • Combat Operations
  • Computer Programming
  • Data Sets
  • Ground Control Stations
  • Linear Programming
  • Mathematical Models
  • Military Aircraft
  • Military Operations
  • Operations Research
  • Spreadsheet Software
  • Unmanned Aerial Systems
  • Unmanned Aerial Vehicles
  • Warfare

Fields of Study

  • Computer science

Readers

  • Aerial Unmanned Vehicle Swarm Micro Periodontal Dentistry.
  • Irregular Warfare and Special Operations Cyberspace Operations against Adversarial Threats.
  • Munitions and Ordnance Engineering

Technology Areas

  • Autonomy
  • Autonomy - UAVs