Static collision checking amounts to testing a given configuration of objects for overlaps. In contrast, the goal of dynamic checking is to determine whether all configurations along a continuous path (animation on above right) are collision-free. While effective methods are available for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach -- frequently used while computing collision-free trajectories for objects (esp. in PRM planning) -- is to sample paths at some fixed, pre-specified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, especially when objects are thin (end-effector of the ABB-IRB2400 robot in the above illustrations). One may increase the reliability of the approach by refining the sampling resolution along the entire path, but a finer resolution increases the running time of the collision checker. We introduce a new method for testing straight path segments in configuration space, or collections of such segments, which is both reliable and efficient. This method locally adjusts the sampling resolution (rightmost figure) by comparing lower bounds on distances between objects in relative motion with higher bounds on lengths of curves traced by points of these moving objects.
Several additional techniques and heuristics further improve the checker's efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. Our new method is general, but particularly well suited for use in PRM planners. Extensive tests, in particular on randomly generated path segments and on multi-segment paths produced by PRM planners, show that the new method compares favorably with a fixed-resolution approach at "suitable" resolution, with the enormous advantage that it never fails to detect collision.
|