EFFICIENT COLLISION PREDICTION AMONG MANY MOVING-OBJECTS

We consider the problem of flagging all collisions between a large num ber, of dynamic objects. Because the number of possible collisions gro ws quadratically with the number of objects, a brute force approach is not applicable with finite computational resources. Hence, we propose a scheduling mechanism that reduces the computational load by exploit ing the coherence of the world throughout time. This mechanism has a v ery simple structure and easily lends itself to distributed processing . It considers all pairwise interactions between objects and maintains a structure that reflects the imminence, or urgency, of collision for each pail: Bounds oil the urgency of collisions can be computed given minimal knowledge of the system dynamics. For example, we represent p hysical objects by their positions and by bounds on their relative spe eds and accelerations. These are assumed to he available at all times. IS the environment does not change too rapidly, the mechanism flags a ll collisions. False alarms may also he generated but can he eliminate d with a specialized exact collision post-processor. We address the qu estion of how often to perform the collision checks while guaranteeing flint all collisions will be caught. Given the large number of possib le environments find motions, no general optimal answer can be provide d. Yet the soundness and efficiency of rile proposed algorithm is expe rimentally verified ill the case of a simple world consisting of many spheres moving simultaneously and randomly.