An application of heuristic search techniques to the problem of flight path generation in a military hostile environment

ABSTRACT

This paper is a study of the effectiveness of heuristic search algorithms in generating flight paths. Due to the need to generate and revise paths dynamically we are interested in execution speed as well as solution quality (conflict cost plus path length). Extensive tests with three search algorithms were made using a simple threat model. Using straight-forward heuristics, we found that two of the algorithms perform well then their weights are appropriately adjusted. One is A* and the other is a bidirectional search. Our results indicate that heuristic search is effective in flight path generation and provide details about algorithms which were successful.

REFERENCES

• 1: A. Bagchi , A. Mahanti, Three approaches to heuristic search in networks, Journal of the ACM (JACM), v.32 n.1, p.1-27, Jan. 1985 [doi>10.1145/2455.2458]
• 2: Dennis de Champeaux, Bidirectional Heuristic Search Again, Journal of the ACM (JACM), v.30 n.1, p.22-32, Jan. 1983 [doi>10.1145/322358.322360]
• 3: Lenie Sint , Dennis de Champeaux, An Improved Bidirectional Heuristic Search Algorithm, Journal of the ACM (JACM), v.24 n.2, p.177-191, April 1977 [doi>10.1145/322003.322004]
• 4: Hart, P.E., Nilsson, N.J., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Science and Cybernetics, 2 (100-107).
• 5: Kline, K.B. 1985. Generation of flight paths using hierarchic planDing. MS Thesis, Wright State 5niversity, Department of Computer Science.
• 6: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 7: Lizza, C.F. 1984. Generation of flight paths using heuristic search. MS. Thesis, Wright State University, Department of Computer Science.
• 8: Martelli, A. 1977. On the complexity of admissible search algorithms. Artificial Inte!liqence, 8 (1-13).
• 9: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 10: Pohl, Io 1969. Bi-directional~ and heuristic search in path problems. SLAC Report No. 104, Stanford Linear Accelerator Center.
• 11: Politowski, G. and Pohl, I., 1984. D-node retargeting in bidirectional heuristic search. Fourth National Conference on Artificial Intelligence (274-7).
• 12: Rao, V.N., Kumar, V., and Ramesh, K. 1987. A parallel implementation of iterative- Deepening-A*. Sixth National Conference on Artificial Intelligence, Volume 1 (178- 182) .
• 13: Wagner, C.E. 1985. Planning and search for generating flight paths in a large space. MS Thesis, Wright State University, Department of Computer Science.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Path and circuit problems

  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Military
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Military

General Terms:
Algorithms, Design, Theory