Neighborhood Visibility Correlative Path Planning Research

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.