SEARCH PROBLEMS IN MISSION PLANNING AND NAVIGATION OF AUTONOMOUS AIRCRAFT

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planer system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Prolem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes th flight trajectory by creating the control commands to fly the aircraft.

• Corporate Authors:

  Purdue University

  School of Aeronautics and Astronautics
  West Lafayette, IN  United States  47907
• Authors:
  • Krozel, J A
• Publication Date: 1988

Media Info

• Pagination: 197 p.

Subject/Index Terms

• TRT Terms: Aircraft; Algorithms; Navigation; Routing; Scheduling
• Subject Areas: Aviation; Highways; Vehicles and Equipment; I91: Vehicle Design and Safety;

Filing Info

• Accession Number: 00477064
• Record Type: Publication
• Source Agency: National Technical Information Service
• Report/Paper Numbers: NAS 1.26:182666, NASA-CR-182666
• Files: TRIS
• Created Date: Nov 30 1988 12:00AM