Efficient Collision Prediction Among Many Moving Objects

Publisher Website
Google Scholar
Abstract
We consider the problem of flagging all collisions between a large number of dynamic objects. Because the number of possible collisions grows 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 exploiting the coherence of the world throughout time. This mechanism has a very 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 pair. Bounds on the urgency of collisions can be computed given minimal knowledge of the system dynamics. For example, we represent physical objects by their positions and by bounds on their relative speeds and accelerations. These are assumed to be available at all times. If the environment does not change too rapidly, the mechanism flags all collisions. False alarms may also be generated but can be eliminated with a specialized exact collision post-processor. We address the question of how often to perform the col lision checks while guaranteeing that all collisions will be caught. Given the large number of possible environments and motions, no general optimal answer can be provided. Yet the soundness and efficiency of the proposed algorithm is eaper imentally verified in the case of a simple world consisting of many spheres moving simultaneously and randomly.