Jehyun Cha, Hanyang University; Drew McNeely, University of Texas at Austin; Joonghyun Ryu, Hanyang University; Misoon Mah, Air Force Office of Scientific Research (AFOSR); Moriba Jah, The University of Texas at Austin; Deok-Soo Kim, Hanyang University
Keywords:
Abstract:
Conjunction assessment is one of the critical tasks to keep the geospace safe and the development of an efficient yet accurate computational theory has always been an active research topic. In AMOS 2017, we reported an intermediate research result about the DVD-COOP (Conjunctive Orbital Object Predictor based on Dynamic Voronoi Diagram) algorithm/program which was based on a rigorous theory of Voronoi diagram in computational geometry. The motivation under the effort for developing DVD-COOP has been to provide new capabilities which has been lacking in existing algorithms/programs: i) To report a conjunction quickly without any missing conjunction case; ii) To provide efficient and accurate spatial analyses beyond pairwise conjunction prediction; iii) To provide a methodology to design an optimal collision-avoiding maneuver of a conjunctive object. We hope that the program will be eventually used by researchers in this community.
The fundamental capabilities of DVD-COOP inherit from the powerful computational geometric construct called Voronoi diagrams, particularly its dynamic version, which has been well-known for spatial reasoning among particles. To determine if a pair of objects in geospace are conjunctive within a threshold distance at an arbitrary moment, it is sufficient to check the faces in the Voronoi diagram of all objects at that moment. If the Voronoi diagram is correct, it is guaranteed that we can detect conjunctions without any missing cases. In addition, the computation is very efficient. And in the worst case, only O(M) time is sufficient where M is the number of the faces in the Voronoi diagram of N objects. It is known that M=O(N^2) in the worst case but M=O(N) on average, in particular for the objects in geospace. Many other geometric queries, even involving more objects, can be answered with a similar efficiency. It is noted that the Voronoi diagram we implemented in this research explores the three-dimensional (3D) spheres, not one dimensional points.
In this paper, we will report the progress of DVD-COOP since the initial announcement last year. First, in this paper, a new and advanced function of DVD-COOP will be introduced: The optimal design of collision-avoiding maneuver path. It is a general practice that an optimal decision is made by choosing the alternative with the best measure and by evaluating sufficiently many solution candidates. Given the event history of dynamic Voronoi diagram over time horizon, a candidate maneuver path can be evaluated using the dynamic Voronoi diagram by advancing time through the event history in the time horizon. The assessment of each candidate path thus takes O(E), where E is the number of flipping events of Voronoi edges and faces in time horizon, and E ? T, where T is the length of time horizon. In addition, different maneuver paths are perfectly scalable. Hence, given an event history of the dynamic Voronoi diagram, an optimal maneuver path among many candidates can be very efficiently found. This computational efficiency delivers an even more exciting news: With the DVD-COOP server running on a computational platform with a moderate computational resource, many researchers around the world can easily access the server to make optimal decisions provided that the issues related with securities can be handled separately.
Second, the conjunction prediction algorithm of DVD-COOP is based on the dynamic Voronoi diagram of which computational theory is known only when particles move linearly. Hence, elliptic orbits were approximated by piecewise linear polygons which inevitably introduce errors. In this paper, we improve the earlier-reported error analysis so that a strategy for optimal linear approximation can be designed from computation time point of view. It should be noted that an accurate error analysis is of importance in that a scheme to find a subset of Voronoi faces (i.e. the object pairs) which correctly contains the one with the minimum distance.
Third, the effectiveness and efficiency of the DVD-COOP methodology will be verified through a set of benchmark tests. The scope of the tests will be obviously constrained by the availability of codes, functions, data, etc.
Date of Conference: September 11-14, 2018
Track: Poster