Research On 4D Trajectory Planning Based On Quickhull Algorithm

With the accelerated development of technology and economy,the demand of global air transportation increases continously.The increasing of civil aircraft and air traffic flow leads to the congestion of air traffic network,the air traffic management is facing huge challenges.As a key technology of future Trajectory Based Operation(TBO),4D trajectory planning is widely focused and researched.This paper focuses on the aircraft's rerouting strategy and the Conflict Detection and Resolution(CD&R)problem of multiple aircrafts in 4D trajectory planning.It innovatively applies the Quickhull Algorithm into 4D trajectory planning problem,provides a new method to 4D trajectory planning.Convex hull is widely used in path planning problems due to its special properties,but there are still few studies on aircraft trajectory planning.In this paper,the convex hull and its related concepts are introduced,and the classical convex hull algorithms such as Jarvis march,Graham scan,incremental method,divide and conquer method are compared and analyzed,which illustrates the application advantages of the quickhull algorithm in the trajectory planning problem.In terms of the aircraft rerouting problem,the quickhull algorithm is used to simplify the planning space,which greatly reduces its complexity.Next,the quickhull idea is used to determine the feasible domain search range.Compared with the traditional trajectory planning algorithm,quickhull algorithm increases the utilization of the available airspace on the basis of ensuring flight safety,and improves the computational efficiency for the subsequent Dijkstra shortest path search algorithm.In terms of the conflict detection and resolution problem of multiple aircraft,we consider the possible maneuvering combinations of aircraft and use the quickhull algorithm to generate convex hulls in order to describe the uncertainty in the trajectory prediction process.Through the intersection between the convex hulls,the conflict situation of the aircraft can be judged.Then,the aircraft conflict resolution model is constructed by the constraint condition and the trajectory evaluation function,and the branch and bound algorithm is applied for conflict resolution.Simulation results show that the proposed algorithm is efficient and robust to aircraft conflict resolution.