next up previous contents
Next: Computer Aided Design of Up: Planning Previous: Trajectory Generation at or

Efficient Collision Prediction

V. Hayward, A. Foisy, S. Aubry, Y. Ghallab We have discovered an algorithm which dramatically reduces the computational burden required to detect collisions among many simultaneously moving objects. We have proposed to utilize bounds on the dynamics of the modelled object to efficiently schedule computations. Experiments recently confirmed this approach. We have tested this algorithm in the case of many spheres moving with randomly assigned velocity vectors. Experiments with up to 40 simultaneously moving objets have displayed a sub-linear growth of the computational burden with the number of objects. Naive algorithms display a quadratic complexity.

Thierry Baron
Mon Apr 7 12:54:24 EDT 1997