next up previous contents
Next: Safe Collision Detection Up: Planning Previous: Trajectory Generation at

Efficient Collision Prediction

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. This is a worst case scenario since we can expect practical situations such as the motion of robot limbs to display a much higher degree of coherence which the algorithm exploits. 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.

V. Hayward, A. Foisy, S. Aubry, Y. Ghallab

Thierry Baron
Mon Nov 13 10:43:02 EST 1995