Résumé
This paper presents an exact collision detection algorithm capable of determining the presence or absence of collisions along a path. For every pair of rigid bodies, using a known upper bound on their relative velocity along the path, if lower bounds on the distance between them can be computed at certain parameters along the path, portions of the path can then be validated. The algorithm proceeds by dichotomy until the whole path is validated or a collision is found. A proof of convergence of the algorithm is proposed, guaranteeing that any path can be validated or invalidated in finite time, except for one singular case. Three changes to this algorithm are then proposed, and are shown through experimental validation to reduce significantly the number of iterations needed to validate a path. The algorithm is also shown to perform better than a discretized collision detection method in terms of computation times, while missing no collision. Moreover, the method can be extended to take into accounts other types of constraints than those related to collision avoidance, and can be applied to various types of robots.