1Adaptive Dynamic Collision Checkingfor Single and Multiple Articulated Robotsin Complex EnvironmentsFabian Schwarzer, Mitul Saha, and Jean-Claude LatombeAbstract—Static collision checking amounts to testing a givenconfiguration of objects for overlaps. In contrast, the goal ofdynamic checking is to determine whether all configurationsalong a continuous path are collision-free. While there existeffective methods for static collision detection, dynamic checkingstill lacks methods that are both reliable and efficient. Acommon approach is to sample paths at some fixed, prespecifiedresolution and statically test each sampled configuration. Butthis approach is not guaranteed to detect collision wheneverone occurs, and trying to increase its reliability by refiningthe sampling resolution along the entire path results in slowchecking. This paper introduces a new method for testingstraight path segments in c-space or collections of suchsegments, that is both reliable and efficient. This methodlocally adjusts the sampling resolution by comparing lowerbounds on distances between objects in relative motion withhigher bounds on lengths of curves traced by points of thesemoving objects. Several additional techniques and heuristicsincrease the checker’s efficiency in scenarios with many movingobjects (e.g., articulated arms and/or multiple robots) andhigh geometric complexity. The new method is general, butparticularly well suited for use in probabilistic roadmap (PRM)planners. Extensive tests, in particular on randomly generatedpath segments and on multi-segment paths produced by PRMplanners, show that the new method compares favorably witha fixed-resolution approach at “suitable” resolution, with theenormous advantage that it never fails to detect collision.Keywords: Collision checking, motion planning, distance compu-tation, probabilistic roadmaps, roboticsI. INTRODUCTIONA. Dynamic collision checkingCOLLISION checking is a fundamental operation in robotmotion planning, graphic animation, and physical simu-lation [1], [2], [3]. While static checking amounts to testing asingle configuration of objects for overlaps, dynamic checkingrequires determining whether all configurations on a continu-ous path are collision-free.Four major families of methods have been proposed fordynamic collision checking:Feature-tracking methods track pertinent features (ver-tices, edges, faces) of two objects – usually, the pairof closest features – to determine if the objects remainseparated along a path. They rely on the followingThe authors are with the Robotics Laboratory, Departmentof Computer Science, Stanford University, CA 94305 USA. (e-mails: [email protected], [email protected],[email protected])coherence assumption: the pertinent features change rel-atively rarely and, when they do change, the new onescan be computed efficiently from the old ones [4], [5],[6], [7], [8]. These methods also require each objectto be made of few convex components and to haverelatively small geometric complexity. These assumptionsare poorly verified by kinematic chains (e.g., robot arms)in practical environments. Then, paths must be tested bytiny increments, to avoid missing collisions, especiallycollisions involving links at the end of the chains.Bounding-volume hierarchy (BVH) methods pre-compute, for each object (robot link, obstacle), ahierarchy of BVs (e.g., spheres, boxes) that approximatesthe geometry of the object at successive levels ofdetail [9], [10], [11], [12], [13], [14]. To check twoobjects for collision, their BVHs are searched fromthe top down, making it possible to quickly discardlarge subsets of the objects contained in disjoint BVs.Such methods have been applied to complex objectswith surfaces described by several 100,000 triangles,and more [9], [12]. But they are fundamentally staticmethods. To test a path, the common approach is tocheck intermediate configurations spaced along the pathat a prespecified resolution. If all these configurationsare found collision-free, then the path is declaredcollision-free, but this answer may not be correct.Swept-volume intersection methods compute the volumesswept out by the objects and test these volumes foroverlap [15], [16]. However, exact computation of sweptvolumes is expensive, especially when objects undergorotations and have complex geometry. Moreover, theoverlap test can no longer be speeded up by usingpre-computed data structures, such as BVHs. Anotherdifficulty is that swept volumes for pairs of movingobjects may overlap even when the objects do not collide.Hence, when multiple objects move relative to each other,one must either consider the relative motions for all pairs,or compute and test volumes swept out in 4D space-time.Both ways yield costly computations.Trajectory parameterization methods express the geom-etry of the objects along the tested path by algebraicpolynomials in a single variable [17], [18]. These poly-nomials are then used to construct a collision conditionon . In principle, finding the values of verifying thiscondition gives the exact intervals of collision alonga given path. But, in general, the polynomials have2Fig. 1. : Two skinny 20-DOF arms (320 triangles each) in environment with three fixed thin tori (6,000 triangles each), and detail showing arms in topring. : IRB 2400 robot with thin arc welding gun (3,500 triangles) and snapshots along a straight path segment in c-spacehigh degrees, so that solving the condition for can beprohibitively expensive and furthermore pose numericalproblems.B. Fixed-resolution dynamic checkingHence, while there exist effective methods for static col-lision checking (e.g., BVH methods), dynamic checking re-mains a practical bottleneck in many applications. In par-ticular, probabilistic roadmap (PRM) planners rely on theavailability of efficient checkers to test straight path segments(called local paths) between randomly sampled configurations(called milestones) [19], [20], [21], [22], [23], [24]. MostPRM planners use a static BVH method to test intermediateconfigurations spaced along each local path at some givenresolution (in the c-space metric). These configurations areusually obtained by recursively bisecting the local path, untileither a collision is found, or any two successive configurationsare closer apart than [24], [25].Choosing requires a delicate compromise between effi-ciency and reliability. This is especially true in scenarios witharticulated arms