基于两层编码遗传算法的机器人路径规划英文.pdf

17 3 Vol.17,No.3 　2000 6 CONTROL TH ORY AND APPLICATIONS Jun., 2000 　 Article ID:1000-8152(2000)03-0429-04 Robot Path Planning Based on Genetic Algorithms with Two-Layer Encoding ＊ LIU Yanfei　and 　QIU Yuhuang (Institute of Automation, Academia Sinica·Beijing, 100080, P.R.China) 　　Abstract:This paper focuses on the problem of finding an uclidean shortest path between two distinct locations, in (L ) 2 a known, obstacle-scattered, planar environment.We use a new kind of cell decomposition approach based on the genetic algo- rithms (GA).We propose a newkind of encoding for the genetic algorithms, called two-layer encoding, which comes from the genetics mechanism in molecular genetics.This new kind of encoding can improve the expressing ability of codes.The heart of the two-layer encoding is to decrease the complexity of exploration through the middle-layer codes. Key words:two-layer encoding;path planning;shortest paths;GA Document code:A 　 (·, 100080) 　　:, . ., ———. ... :;;; 1 　Introduction 　Cell decomposition approaches consist in subdividing 　Planning collision-free paths of the shortest distances an environment into discrete cells of a predefined shape through a known, obstacle-scattered, planar environment and size and then searching an undirected graph based on has been studied extensively[