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 multi-objective 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 zero-dimensional and independent in the neighborhood. However, it is not comprehensive to use the irrelative zero-dimensional numerical values to represent the overlapping characteristic of viewshed from the different points of three-dimensional terrain. Two-dimensional viewshed is used in this work to describe three-dimensional visibility and the raster-based 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 sub-region. The optimal sequence of travelling all sub-regions is obtained by the genetic algorithm. Then the shortest path segment in each sub-region is computed by a multi-population evolutionary algorithm. The entire path is formed by linking each segment in the optimal sequence of sub-regions. 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 multi-objective evolutionary algorithm is presented for the minimal visual coverage shortest path problem by investigating hybrid multi-objective evolutionary methods. Besides the variable length chromosome structure and adaptive mutators, a multi-level 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 NSGA-II.(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 NSGA-II and SMS-EMOA 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

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Research on Subsea Pipeline Repair Coupling,TE973
  3. Mining resources based on genetic algorithm optimization model of,O224
  4. Study on Optimal Allocation of Regional Water Resources Based on PSO,TV213.4
  5. Research on the Complete Coverage Path Planning Algorithm of Mobile Robot,TP242
  6. Research on Optimal Global Path Planning for Complete Coverage with GPS Guidance on Tractor,TN967.1
  7. Multi- license plate location method based on CNN's Intelligent Transportation Systems Research,TP391.41
  8. The Design and Implementation of ERP System in Mint,TP311.52
  9. Research and Application Based on Location and Path Optimization of Emergency Logistics Systems,F252
  10. Optimization of EDM Parameters,TG661
  11. Study on Emergency Logistics Vehicle Routing Mode Based on the Clonal Immune Algorithm,U116.2
  12. Analysis of Water Resources Carrying Capacity Based on a System Dynamic Model and System Optimization,X26
  13. Research on Fast Path Planning Method Based on Genetic Algorithm,TP18
  14. Research on DNA Encoding Based on Quantum Computing,Q75
  15. Multi-objective Optimal Operation for Reservoirs,TV697.1
  16. A Research on Power Coal Blending Model of Bituminous Coal Blended with Indonesian Coal,TK227.1
  17. The Research of Switching Power Amplifier for Microprocessor Relay Protection Testing System,TM774
  18. Multi-objective optimization problem procurement allocation study,F224
  19. Characteristic style of clothing based on cognitive research and implementation of self- classification,TS941.11
  20. Optimization Research of Purchasing Decision Considering Multiple Transport Alternatives,F274
  21. Improved Ant Colony Algorithm Based Multi-objective scheduling problem of degradation,O221.6

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > Optimization of the mathematical theory
© 2012 www.DissertationTopic.Net  Mobile