Genetic algorithms for the development of real-time multi-heuristic search strategies
Parker, Gary B.
MetadataShow full item record
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 every step of the way. Having limited energy resources and knowledge of the terrain (only adjacent nodes), the key factor for the physical agent's 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 in separate works. Both made use of known information about the frontier node's 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 develop these improved strategies for our specific case, are also applicable to a multitude of real-time search/optimization problems in the general case.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Smith, Douglas R. (Monterey, California. Naval Postgraduate School, 1979-11); NPS-52-79-004Many important problems in operations research, artificial intelligence, combinatorial algorithms, and other areas seem to require search in order to find an optimal solution. A branch and bound procedure, which imposes a ...
Xie, Geoffrey G.; Lam, Simon S. (1996-10);For many service disciplines that provide delay guarantees, the scheduler of a channel repeatedly searches for the smallest element in a set of priority values (or deadlines). It is required that each search finishes ...
Shing, Man-Tak; Mayer, Michael McClanahan (Monterey, California. Naval Postgraduate School, 1991-04); NPS-CS-91-011The research reported in this paper deals with the problem of searching through an unknown terrain by a physical agent such as a robot. The unknown terrain over which the agent will travel is represented by an undirected ...