Adam J. Pohl

Date of Award

3-6-2008

Document Type

Thesis

Degree Name

Master of Science in Electrical Engineering

Department

Department of Electrical and Computer Engineering

First Advisor

Gary B. Lamont, PhD

Abstract

This investigation purports to develop a new model for multiple autonomous aircraft mission routing. Previous research both related and unrelated to this endeavor have used classic combinatoric problems as models for Unmanned Aerial Vehicle (UAV) routing and mission planning. This document presents the concept of the Swarm Routing Problem (SRP) as a new combinatorics problem for use in modeling UAV swarm routing, developed as a variant of the Vehicle Routing Problem with Time Windows (VRPTW). The SRP removes the single vehicle per target restraint and changes the customer satisfaction requirement to one of vehicle on location volume. The impact of these alterations changes the vehicle definitions within the problem model from discrete units to cooperative members within a swarm. This represents a more realistic model for multi-agent routing as a real world mission plan would require the use of all airborne assets across multiple targets, without constraining a single vehicle to a single target. Solutions to the SRP problem model result in route assignments per vehicle that successfully track to all targets, on time, within distance constraints. A complexity analysis and multi-objective formulation of the VRPTW indicates the necessity of a stochastic solution approach leading to the development of a multi-objective evolutionary algorithm. This algorithm design is implemented using C++ and an evolutionary algorithm library called Open Beagle. Benchmark problems applied to the VRPTW show the usefulness of this solution approach. A full problem definition of the SRP as well as a multi-objective formulation parallels that of the VRPTW method. Benchmark problems for the VRPTW are modified in order to create SRP benchmarks. These solutions show the SRP solution is comparable or better than the same VRPTW solutions, while also representing a more realistic UAV swarm routing solution.

AFIT Designator

AFIT-GE-ENG-08-22

DTIC Accession Number

ADA486956

Download

Share

COinS