In robotics, a collision or proximity query reports geometric information about the relative configuration or placement of two objects. Some common examples of such queries include checking whether two objects overlap in space, testing if their boundaries intersect, or computing the minimum Euclidean separation distance between their boundaries. Hundreds of papers have been published on different aspects of these queries in robotics and related areas such as computer-aided design and manufacturing, computational geometry, computer graphics, and virtual environments. These queries arise in different robotic applications, including robot motion planning, collision avoidance, grasping, manipulation, control, dynamic simulation, human-robot interaction, haptic rendering, and more. For example, in motion planning for a humanoid robot, it is critical that the planned motion should not result in any collisions between the robot and the surrounding obstacles. At the same time, there should be no self-collisions between different links of the robot (see Fig. 1). The robot’s linkages should not pass through each other, and objects in the environment should move as expected when pushed, pulled, or grasped by the robot. Such actions require fast and accurate collision detection between the geometric representations of both the robot(s) and objects in the scene. Another example is multiple-robot interaction, where the proximity relationships between all possible pairs of robot bodies need to be measured and maintained to realize plausible interaction among the robots. In Fig. 2, the motion of each Nao robot is tracked so as to maintain the safety distance between the two robots to generate physically plausible robotic interactions.
- Bounding Volume Hierarchy (BVHs)
- Continuous Collision Detection (CCD)
- General Polygonal Models
- Kinetic Data Structures (KDS)
- Proximity Queries