NASA NTRS1987
Collision Detection for Spacecraft Proximity Operations This thesis describes the development of a new collision detection algorithm to be used when two spacecraft are operating in the same vicinity. The two spacecraft are modelled as unions of convex polyhedra, where the polyhedron resulting from the union may be either convex or nonconvex. The relative motion of the two spacecraft is assumed to be such that one vehicle is moving with constant linear and angular velocity with respect to the other. The algorithm determines if a collision is possible and, if so, predicts the time when the collision will take place. The theoretical basis for the new collision detection algorithm is the C-function formulation of the configuration space approach recently introduced by researchers in robotics. Three different types of C-functions are defined that model the contacts between the vertices, edges, and faces of the polyhedra representing the two spacecraft. These C-functions are used to formulate three "collision" conditions. The first of these conditions limits the points representing potential collisions to the zeros of the C-functions. The new algorithm is fundamentally a search for the smallest zero of any C-function that satisfies the second and third collision conditions. The C-functions are shown to be transcendental functions of time for the assumed trajectory of the moving spacecraft. The zeros of these functions cannot be expressed in dosed form. Therefore, numerical search procedures are developed to find aLl of the zeros of a C-function in specified bounded intervals of time. These bounded intervals of time are found by examining the second and third collision conditions. The capabilities of the new algorithm are demonstrated for several example cases. These include examples of collisions determined by zeros of each of the three different types of C-functions. In addition to predicting the time of first contact of the polyhedra, the algorithm identifies the features of the two polyhedra that are touching at this time. The new collision detection algorithm is the first such algorithm that is capable of solving the collision detection problem exactly for the case where the moving object has constant linear and angular velocities. This is a significant improvement on previous collision detection algorithms described in the literature. In particular, the ability to handle constant angular velocity represents a more realistic type of rotational motion than those which have been used in other algorithms.