Automated Path and Mission Planning for Aerial Platforms under Dynamic Conditions and Constraints

Award Information
Agency: Department of Defense
Branch: Navy
Contract: N00014-04-M-0321
Agency Tracking Number: N045-003-0401
Amount: $69,974.00
Phase: Phase I
Program: STTR
Awards Year: 2004
Solicitation Year: 2004
Solicitation Topic Code: N04-T003
Solicitation Number: N/A
Small Business Information
13766 S. Hawthorne Blvd., Hawthorne, CA, 90250
DUNS: 028281020
HUBZone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Ed Bachelder
 Principal Investigator
 (310) 679-2281
Business Contact
 Thomas Myers
Title: Vice President
Phone: (310) 679-2281
Research Institution
 Eric Feron
 77 Massachusetts Avenue, Building E19-750
Cambridge, MA, 02139
 (617) 253-1991
 Nonprofit college or university
The proposal herein merges two novel and different algorithms for unmanned platform dynamic path-planning in obstacle fields. The first employs a recently published technique, Focused Dynamic Programming [1], which offers the benefits of both the LAO* algorithm [2] (LAO* subsumes Dijkstra's algorithm) and the Prioritized Sweeping algorithm [3]. Focused Dynamic Programming uses heuristics to limit the number of states examined during the value iteration so that the value updates are used most effectively. The second algorithm formulates the path optimization as a Mixed Integer Linear Programming problem. This approach is particularly convenient because (i) it allows a wide range of operationally relevant elements to be accounted for in the optimization and (ii) the formulated problem can be immediately solved by existing commercial or non-commercial optimization software. Both of the proposed algorithms appear well-suited to account for multi-objective cost functions and incorporate constraints driven by platform dynamics and rules of engagement. Additionally, the algorithms have been selected because of their potential to produce solutions for rapidly changing battlespace conditions. MIT has already applied Mixed Integer Linear Programming to solve the path planning problem for a highly maneuverable UAV helicopter.

* Information listed above is at the time of submission. *

Agency Micro-sites

SBA logo
Department of Agriculture logo
Department of Commerce logo
Department of Defense logo
Department of Education logo
Department of Energy logo
Department of Health and Human Services logo
Department of Homeland Security logo
Department of Transportation logo
Environmental Protection Agency logo
National Aeronautics and Space Administration logo
National Science Foundation logo
US Flag An Official Website of the United States Government