Masters Theses

Abstract

"Traveling Salesman Problem (TSP) solution techniques are often used for route planning for automated vehicles. Most TSP solution methods focus on path length as the fitness reference, however in many cases, traversal time is of more practical importance. Mutual Attraction Guided Search (MAGS) is a novel solution method that uses an iterative process to simultaneously optimize both angle of travel through each target as well as the ordering of the targets in order to optimize path traversal time. MAGS deterministically locates a locally optimum solution quickly and can optimize for the acceleration limits of a specific vehicle rather than requiring a constant vehicle speed. Since the basic form of MAGS finds a solution deterministically, it has no mechanism for escaping local minima, therefore an evolutionary form is also developed that alternates between local search with MAGS and global search using evolutionary operators to combine and mutate solutions. This hybridization provides the necessary balance between local and global search that is required to locate a globally optimal solution. A fitness based on approximate travel time based on the maximum velocity achievable at each point on the path is calculated using the curvature of the path and the dynamic constraints of the vehicle. The performance of both the basic and evolutionary forms of MAGS are compared against path length based Euclidean and curvature constrained TSP methods"--Abstract, page iii.

Advisor(s)

Wunsch, Donald C.

Committee Member(s)

Stutts, Daniel S.
Moss, Randy Hays, 1953-

Department(s)

Electrical and Computer Engineering

Degree Name

M.S. in Electrical Engineering

Sponsor(s)

Mary K. Finley Missouri Endowment
National Science Foundation (U.S.)

Publisher

Missouri University of Science and Technology

Publication Date

Summer 2011

Pagination

viii, 45 pages

Rights

© 2011 Jared Adam Nisbett, All rights reserved.

Document Type

Thesis - Open Access

File Type

text

Language

English

Subject Headings

Curvature -- Measurement
Evolutionary computation
Trajectory optimization
Traveling-salesman problem

Thesis Number

T 9850

Print OCLC #

785168781

Electronic OCLC #

742345448

Download

Share

 
COinS