Genetic algorithms for the development of real-time multi-heuristic search strategies

Download
Author
Parker, Gary B.
Date
1992-09Advisor
Shing, Man-Tak
Second Reader
Lee, Yuh-Jeng
Metadata
Show full item recordAbstract
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.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
MODELING SUBMARINE ANTI-SHIPPING WARFARE IN THE SOUTH AND EAST CHINA SEAS
McDonough, Bryan P. (Monterey, CA; Naval Postgraduate School, 2019-09);With a strong nuclear arsenal, rapidly expanding Navy, and increasing economic influence, China is quickly turning into a peer adversary that matches the United States’ military and economic strength. Strategies must be ... -
A game theory analysis of proposed strategies of an aerial search for a mobile surface target.
Smith, Charles James (Monterey, California. U.S. Naval Postgraduate School, 1966-10);This thesis investigates the problem of aerial search for a mobile surface target. The initial position of the target is known, and a certain amount of time elapses before the search begins. The target has a variety of ... -
Optimized graph topologies for probabilistic search
Klaus, Christian; Chung, Timothy H. (IEEE, 2011-12);This paper investigates the effect on the performance of a mobile sensor search caused by the search environment. We model the search environment as a simple connected undirected graph. By adding non-existing edges to ...