Accession Number:

ADA257454

Title:

Genetic Algorithms for the Development of Real-Time Multi-Heuristic Search Strategies

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1992-09-01

Pagination or Media Count:

131.0

Abstract:

Search of an unknown space by a physical agent such as an autonomous vehicle is unique in search as the customarily most important goal to reduce the computation time required to obtain the shortest distance is not as important as minimal movement. There is a real-time aspect since the agent is actually moving using energy each step of the way. Having limited energy resources and knowledge of the terrain only adjacent nodes, the key factor for the physical agents search algorithm is reduction of steps. Hence, any heuristic that can help keep step count to a minimum must be considered. Korf and Shing addressed this issue in separate works. Both made use of known information about the frontier nodes distance from the current node in addition to a heuristic estimating the distance from goal. In this thesis, we present a simple genetics-based method to produce adaptive, efficient multi-heuristic search strategies for the real-time problem. Extensive empirical study shows that this approach produced search strategies with much better performance over existing search algorithms for most terrain types. The methodologies used to develope these improved strategies for our specific case, are also applicable to a multitude of real-time searchoptimization problems in the general case.

Subject Categories:

  • Computer Programming and Software
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE