Multi-Star Observation Area Coverage Algorithm Based On Triangulation

The development of China’s aerospace industry is becoming more and more perfect,imaging satellites are more and more widely used in our daily life,when using imaging satellites for observation,often encounter such a situation,multiple satellites need to jointly observe a larger area.In this case,how to formulate the observation plan of the imaging satellite to cover a larger area is the problem of coverage optimization of the multi-satellite cooperative observation area based on triangulation based on triangulation studied in this paper.It is known that there is an area to be observed and multiple imaging satellites,and each imaging satellite is only a rectangular ribbon area at a time,and each ribbon area is smaller than the large area to be observed.When observing,the imaging camera can swing sideways,so the width and position of the bands formed at different side swing angles vary;The imaging camera can be adjusted for on time,so the length of the strip varies.In summary,the development of different satellite observation plans will produce different observation strips.Therefore,the optimization of satellite observations requires the development of a satellite observation plan to make the total area observed by all satellites in transit as large as possible.This problem is a combinatorial optimization problem,and the solution process is difficult and challenging.In this paper,the optimization solution process of this problem is studied in depth,and the solution method is proposed,and the results are as follows:(1)The large area is discretized by triangulation,divided into multiple small triangular cells to form a triangular network,and then a heuristic algorithm of polynomial time complexity is proposed,which makes the area covered by the satellite the largest in the case of limited resources,and simulation experiments are carried out,and the results show that in the case that the observation area is not particularly large,the heuristic algorithm can obtain an approximate optimal solution.(2)The approximation solving strategy based on nested grid is proposed,which is an optimization solution method proposed for large-scale areas to be observed that cannot be solved by heuristic algorithms alone,and the process is: first use heuristic algorithms to solve on the triangular network with coarse granularity,and after obtaining the solution scheme,take the midpoint connection on each side of the existing triangular cells and divide them into four to obtain a nested triangular grid with a smaller size,and then conduct a proximity search near the obtained coverage scheme to obtain a better solution.Because the second search process is performed on the solution obtained after the first search,the computation is small.Performing such approximation strategies multiple times can continuously refine the triangular mesh,resulting in higher quality solutions.The simulation results show that the proposed method has a certain effectiveness.(3)The optimization solution strategy of partition coverage is proposed,which is another optimization solution method for large-scale areas.The idea of this method is: divide a large area into multiple small regions,allocate coverage resources reasonably to each small region,and then use heuristics in each small area to finally merge all regions together to form a large area coverage scheme.Different ways to distribute coverage opportunities can directly impact the final solution.In order to obtain a high-quality solution,the simulated annealing algorithm is used to allocate the coverage resources.The simulation results show that the optimization scheme can solve large-scale studies well.(4)Satellite coverage schemes in a variety of situations were considered,including the effects of dynamic clouds and synthetic observations of adjacent areas.When the satellite transits,if the cloud cover in the area is large,it will have a certain impact on the satellite observation and imaging.In order to avoid waste of resources,satellite observation programs can be reasonably planned,and satellites can be arranged for observation when the cloud cover in the area is less observable.For adjacent areas,synthetic observations can be made if they are within the observation strip formed by the satellite transit.Through simulation experiments,the results show that heuristic algorithms can solve such problems.