Genetic Algorithms for the Development of Real-Time Multi-Heuristic Search Strategies
Man‐Tak Shing, Gary B. Parker · 1993
Search of an unknown space by a physical agent (such as an autonomous vehicle) is unique in search. There is a real-time aspect since the agent is actually moving; using energy each step of the way. The customarily most important goal (to reduce the computation time required to obtain the shortest distance) is not as important as minimal movement. 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. Any heuristic that can help keep step count to a minimum must be considered. In this paper, we present a simple genetic-algorithm-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 than 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.