Vector Graph-based Geometric Fast Route Planning Method Application Research

Sea warfare has always been an important part of the war. With modern warfare’srequirement on real-time response getting higher and higher, the rapidness of UAV routeplanning in marine environment is gaining more and more attention. Vector space reducesthe amount of data of the planning environment and making good use it can greatly reducethe planning time. Therefore, using the vector data as a planning space to achieve thepurposes of rapid route planning becomes a research trend in on-ship UAV route planningin recent years.The geometric approach turns the route planning problem into a problem of unknownrelationship between the basic geometry and geometric constraints. Its resulting route maynot be optimal but is always feasible, and its planning time requirement is very short.Therefore, vector-based sea route planning is of great validity and feasibility. So one ofthe issues of this paper is the geometric methods based route planning.Marine environment is usually described in S57standard electronic navigationalchart, which can extract land and islands to constitute the basic vector chart environment.The extracted land and islands, together with polygonal forbidden zones set manually areall treated as no-fly zones. In practical route planning problem, the main consideration isto satisfy the constraints and how to avoid no-fly zones, and to fulfill the requirement ofrapid planning.This paper presents an approach of calculating the length of line segment intersectingwith the polygon, which can effectively handle convex and concave polygons. This paperuses this approach to solve no-fly zone detecting problem.Based on sea vector data, after giving a brief summary of several geometry methods,this paper proposes an expanding-tree method. Then the tangent map method based onexpanding-tree is further proposed. The proposed methods mainly deal with the no-flyzones avoidance problem along the track, on the premise of satisfying various constraintsand route feasibility, they optimize the final track as far as possible, as well as reaching thegoal of rapid route planning. This paper describes the basic idea of expanding-tree method. It first solves the no-flyzones avoidance problem at the linear planning stage, and then smoothes the linear routeinto an actual route. The expansion strategy of expanding-tree method is studied in-depthand the method’s feasibility is stated. Various experiments have been done based onexpanding-tree method and the tangent map method, and the experiments results andtimeliness are analyzed. Experimental results show that the expanding-tree method can beadapt to solve the rapid marine route planning problem, the tangent chart method needs tobe further improved.