大规模真实地形数据中的全局路径规划方法——基于遗传算法的研究

对基于遗传算法进行路径规划的方法进行了研究，重点在于解决基于真实数据据集进行路径规划时间问题的可解性及提高求解效率，与以往的一些方法的不同之处在于：一方面规划的数据集是根据大规模真实的地形数据构建的，其中包括高程数据和表示各种景物的文化特征数据；另一方面在遗传算法提供了全局求优的机制下，在染色体的编码，初始群体的产出和各种遗传算法中加入了相关的知识，使得该算法具有较好的求解局部问题的方法，提出了遗传算法求解实际的路径规划问题的能力和效率。

RESEARCH ON A GLOBAL PATH PLANNING METHOD BASED ON GENETIC ALGORITHM AND LARGE SCALE REAL TERRAIN DATA

A global path planning method based on genetic algorithm is studied with emphasis on how to find a path efficiently in large scale real terrain data set. This work is different from the previous work in two aspects. The first is the data set and the planned data is constructed using the real terrain data, including digital elevation data (DEM) and culture vector data. The vector data has topological information of points, lines and faces, including the culture such as area, river, bridge etc . The DEM and area data is organized using regular grid, the nodes of the grid store the elevation and area property. The river and road is organized used linked list. The advantage of the organizing method is its concision and convenience, and saving storage space. Second, domain knowledge is added into the framework of genetic algorithm, in the coding of chromosome, generating initial population and the operator of genetic algorithm. By adding these knowledge, the path planning problem can be solved more efficiently and effectively. The experimentation and the result are also given, and the result shows that the method improves the ability and efficiency of genetic algorithm in global path planning.