USA flag logo/image

An Official Website of the United States Government

Automated Path and Mission Planning for Aerial Platforms under Dynamic…

Award Information

Department of Defense
Award ID:
Program Year/Program:
2004 / STTR
Agency Tracking Number:
Solicitation Year:
Solicitation Topic Code:
Solicitation Number:
Small Business Information
Systems Technology Inc.
13766 Hawthorne Blvd. Hawthorne, CA 90250-
View profile »
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
Phase 1
Fiscal Year: 2004
Title: Automated Path and Mission Planning for Aerial Platforms under Dynamic Conditions and Constraints
Agency / Branch: DOD / NAVY
Contract: N00014-04-M-0321
Award Amount: $69,974.00


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.

Principal Investigator:

Ed Bachelder
Principal Investigator

Business Contact:

Thomas T. Myers
Vice President
Small Business Information at Submission:

13766 S. Hawthorne Blvd. Hawthorne, CA 90250

EIN/Tax ID: 951957989
Number of Employees:
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
Research Institution Information:
77 Massachusetts Avenue, Building E19-750
Cambridge, MA 02139
Contact: Eric Feron
Contact Phone: (617) 253-1991
RI Type: Nonprofit college or university