Research On Path Planning On 3D Surface

Finding an algorithm for solving the minimal way on surface is concerned by theoretical and practical areas.The algorithm can be used for practical applications such as battlefield, the constructions of railway and highway, and so on.There are two ways to represent the 3D graphic objects: Boundary and Solid. Boundary includes polygon grid and parametric surface. Solid includes CSG and decompose model.So from the view of draw, 3D graphic objects can be represented to surface model and tissue model ,and grid can be the example for surface model.As two available approaches to represent 3D data, grid data structure and vector data structure both have advantages and limitations. Vector data structure can export fancy maps, but the constructor is too complex.In contract, grid data structure has a compact constructor and efficiency for use.Order grid is an offen adopted represent for 3D data. It use grid to represent DEM. The data format is simple, and easy to store. Triangulated irregular network is another way to represent DEM.It is very suitable for complex landform, but it has a complex topological relation to deal with.In contrast, order grid can be use easily.Path planning is a classical problem of AI. It starts from an initial state, and constantly chooses appropriate operate to change the state until reaches the goal state.There are many type of algorithm for solving the minimal way such as enumeration method, Dijkstra algorithm,traditional heuristic algorithm and genetic algorithm. Heuristic algorithm has the great significance for solving the minimal way on surface.After analysed the way to represent the 3D graphic objects and path planning finding, a new algorithm based on genetic algorithm and surface thinning for path planning on 3D surface is brought on.For the expression method of the environmental model, order grids are used to represent the 3D graphic objects in this paper. This can make solving simplify.An algorithm called Guotao Algorithm (GT) owned to Evolutionary Algorithm and surface thinning are used to find the minimal way on surface in this paper.GT is from TSP and plan on the minimal way on surface the differences of issues route in issueses, effective range in chromosomes(from the starting point to terminal point in the genes) and the range of choosings of genes (select gene C from the starting point to terminal point in the genes, select gene C from the Gene Database of C), wait for place revise to the algorithm, Introduce gene pool come and optimize some algorithms.Most way for surface thinning are fractionizing the whole surface. But this paper only fractionize the areas near the minimal way. The scale of problem is reduced in this way.Related algorithms are verified by the results of programs, attaining to the requirement.