Springer Tracts in Advanced Robotics, p. 25-41
DOI: 10.1007/978-3-540-45058-0_3
This paper describes a new efficient collision checker to test single straight-line segments in c-space, sequences of such segments, or more complex paths. This checker is particularly suited for probabilistic roadmap (PRM) planners applied to manipulator arms and multi-robot systems. Such planners spend most of their time checking local paths between randomly sampled configurations for collision. While commonly used approaches test intermediate configurations on a segment at a prespecified resolution, the checker presented in this paper is exact, i.e., it cannot fail to find an existing collision, even when some robot links and obstacles are very thin. Its efficiency relies on its core algorithm, which dynamically adjusts the required resolution by relating the distances between objects in the workspace to the maximum lengths of the paths traced out by points on these objects. The checker's efficiency is further increased by several additional techniques presented in this paper, which adequately approximate distances between objects and lengths of travelled paths in workspace, and order collision tests to reveal collisions as early as possible. The new checker has been extensively tested, first on segments randomly generated in c-space, next as part of an existing PRM planner, and finally as part of a path smoother/optimizer. These experiments show that the checker is faster than a resolution-based approach (with suitable resolution), with the enormous advantage that it never returns an incorrect answer. The checker also admits a number of straightforward extensions. For example, it can monitor a minimum workspace distance between each robot link and other objects (e.g., obstacles, links of other robots).