Dissertation > Excellent graduate degree dissertation topics show
Neighborhood Visibility Correlative Path Planning Research
Author: LiJie
Tutor: HongPeiLin；HuXiaoHui
School: University of Science and Technology of China
Course: Communication and Information System
Keywords: visual coverage complete coverage average horizon evolutionary computation hybrid evolutionary algorithm multiobjective multiobjectivization hypervolume
CLC: O224
Type: PhD thesis
Year: 2011
Downloads: 79
Quote: 0
Read: Download Dissertation
Abstract
Optimal path problem based on visibility analysis, whose cost is the information of terrain visibility, belongs to the field of space decision making and has significant meaning both in theory and practice. In traditional optimal path analysis the visibility information used to evaluate the traveling ability is just zerodimensional and independent in the neighborhood. However, it is not comprehensive to use the irrelative zerodimensional numerical values to represent the overlapping characteristic of viewshed from the different points of threedimensional terrain. Twodimensional viewshed is used in this work to describe threedimensional visibility and the rasterbased neighborhood visibility correlative optimal path problems are proposed. The total visibility information can be obtained by the viewshed amalgamation of all the points in the path, which is path visual coverage. Under the two optimality constraints of visual coverage and path length, optimal path problems are classified as several categories: (1)complete visual coverage shortest path problem; (2)minimal visual coverage shortest path problem; (3)maximal visual coverage path problem based on average horizon; (4)minimal visual coverage path problem based on average horizon; etc. All these problems are investigated in this work. By analyzing the property of each problem and tracing the hotspots in evolutionary computation, the direction and methodology for the work are established. On the basis of this, the new algorithms are designed and implemented for each problem as follows.(1) For minimal visual coverage in raster terrain, a new approach for observers siting is presented to overcome high complexity and imcomplete coverage of existing methods. The new method takes the accumulative visibility information as heuristics based on the viewshed overlay characteristic of adjacent observers in the terrain, called Reverse cumulative Visibility Redundancy Removal method(RVRR). Approximately minimal number of observers are obtained with low time complexity by removing those redundant observers. The new method is superior to the traditional greedy method in both the quality of solution and efficiency.(2) Based on the observers’set obtained by the new approach of RVRR, a hierarchical divide and conquer evolutionary algorithm is presented for the complete visual coverage shortest path problem. Firstly, the observers are divided into several clusters, each of which is called subregion. The optimal sequence of travelling all subregions is obtained by the genetic algorithm. Then the shortest path segment in each subregion is computed by a multipopulation evolutionary algorithm. The entire path is formed by linking each segment in the optimal sequence of subregions. The method can get the optimal path completely covering the terrain and be easy to be extended to the case of multiple paths covering the entire terrain.(3) Two basic properties are given and proved by analyzing the visual coverage path problem based on average horizon in detail. One property is that the problem of optimal path based on average horizon belongs to the type of optimal path including the arcs with negative weight, but no loops with negative weight. The other property is that optimal path based on average horizon does not satisfy the principle of optimality.(4) A hybrid single objective evolutionary algorithm is presented for the maximal visual coverage path problem based on average horizon by investigating the hybrid single objective evolutionary methods. By using the chromosome structure with variable length and limiting the number of key points, time and space consumption is reduced, and flexible various chromosomes are maintained. In addition, the mutators can be adaptively adjusted. The designed algorithm can rapidly find the approximately optimal solution compared with the simulated annealing algorithm.(5) Minimal visual coverage shortest path problem belongs to multiple objective combinatorial optimization. A hybrid multiobjective evolutionary algorithm is presented for the minimal visual coverage shortest path problem by investigating hybrid multiobjective evolutionary methods. Besides the variable length chromosome structure and adaptive mutators, a multilevel neighborhood structure is designed and variable neighborhood search is used as the local searcher. Furthermore, an external archive indexed by the viewshed is designed to store the better solutions generated during the evolution. The pareto front obtained by our method is closer to the true one than NSGAII.(6) A hypervolume based evolutionary algorithm is presented for the minimal visual coverage shortest path problem by using the hypervolume and a new strategy of population renewal. The designed elements of evolutionary algorithm are incorporated into the frameworks of NSGAII and SMSEMOA respectively to solve the minimal visual coverage shortest path problem. The experiment shows that our method is superior to both methods with respect to hypervolume, and the solutions are closer to the extremum of viewshed.(7) The modeling method is analyzed and the idea of multiobjectivization is applied to the minimal visual coverage path problem based on average horizon. The method is superior to both the simulated annealing algorithm and the evolutionary algorithm with single objective.This work provides the solutions for optimal path problems based on visibility, as well as new methodology and new ideas for further research.

Related Dissertations
 Research on Scheduling of Wholeset Orders in JSP Based on Differential Evolution Algorithm,F273
 Research on Subsea Pipeline Repair Coupling,TE973
 Mining resources based on genetic algorithm optimization model of,O224
 Study on Optimal Allocation of Regional Water Resources Based on PSO,TV213.4
 Research on the Complete Coverage Path Planning Algorithm of Mobile Robot,TP242
 Research on Optimal Global Path Planning for Complete Coverage with GPS Guidance on Tractor,TN967.1
 Multi license plate location method based on CNN's Intelligent Transportation Systems Research,TP391.41
 The Design and Implementation of ERP System in Mint,TP311.52
 Research and Application Based on Location and Path Optimization of Emergency Logistics Systems,F252
 Optimization of EDM Parameters,TG661
 Study on Emergency Logistics Vehicle Routing Mode Based on the Clonal Immune Algorithm,U116.2
 Analysis of Water Resources Carrying Capacity Based on a System Dynamic Model and System Optimization,X26
 Research on Fast Path Planning Method Based on Genetic Algorithm,TP18
 Research on DNA Encoding Based on Quantum Computing,Q75
 Multiobjective Optimal Operation for Reservoirs,TV697.1
 A Research on Power Coal Blending Model of Bituminous Coal Blended with Indonesian Coal,TK227.1
 The Research of Switching Power Amplifier for Microprocessor Relay Protection Testing System,TM774
 Multiobjective optimization problem procurement allocation study,F224
 Characteristic style of clothing based on cognitive research and implementation of self classification,TS941.11
 Optimization Research of Purchasing Decision Considering Multiple Transport Alternatives,F274
 Improved Ant Colony Algorithm Based Multiobjective scheduling problem of degradation,O221.6
CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Optimization of the mathematical theory
© 2012 www.DissertationTopic.Net Mobile
