Navigation Using Hybrid Genetic Programming: Initial Conditions and State Transitions

Simske, Steven J.

HP Development Company

关键词: genetic algorithms;    navigation;    optimization;   

RP-ID  :  HPL-2003-56

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Real-time navigation requires the dynamic updating of node-node (state) transition costs. These state transition costs are based on, among other things, distance, traffic patterns, and intelligent clustering of nodes based on similarity in the navigator's intents at each destination, maximum distance preferred between nodes, and other pragmatic considerations. Such superimposed conditions require a hybrid genetic/rule-based system to accommodate the real-world considerations (rule-based) as well as providing efficient computation of minimized overall (summed) node-node costs (genetic algorithm-based; "traveling salesman "). This paper introduces the important elements of such a hybrid system, focusing on the use of rule-based & clustering techniques for initial conditions and node-node transition costs, while showing how genetic algorithms akin to those using gene linking can be used to efficiently compute best paths through a set of nodes with dynamic transition costs. 11 Pages