A volume of space can be represented by a skeleton overlaid with shape primitives (e.g., sphere, cube, ellipsoid). The shape primitive skeleton is completely contained in the original space (i.e., does not overhang the boundary). As such, this structure can perform fast inclusion tests.
-
- Free Space Primitive Skeleton
-
- Obstacle Space Primitive Skeleton
-
- Collision Checking using Shape Primitive Skeletons
We use the shape primitive skeletons of both the obstacle space and the free space to make a quick decision about the collision status of an object. If the input point is contained in either shape primitive skeleton for either the free or obstacle space. If it is not contained in either, we resort to the original collision detection library. Our inclusion based collision checker can be used with any existing collision detector to improve their performance.
Collision detection flow chart using shape primitive skeletons.
As our shape primitive skeleton is defined in workspace, our method is useful or applicable to motion planning problems that involve checking collision of the robot’s geometry with workspace obstacles. For robots with linkages or joints, the geometry of each link or moveable part is checked for collision with the workspace obstacles. Our method is applicable to problems with a priori knowledge of the environments as our shape method skeleton construction method is for static space (i.e., with static obstacles).
We evaluate the impact in collision detection time with the use of shape primitive skeletons in our 2D and 3D test environments. Our results show that the use of the shape primitive skeletons improves the collision detection time (ranging from 20% to 70% in most cases) of two collision detection libraries when compared to the same without the use of skeletons. We observe the improvement in performance in our test environments irrespective of the underlying motion planning strategy. However, the improvement is dependent on the coverage provided by the shape primitive skeletons and the size of the primitives (compared to the size of the robot).
-
- Office environment with Kuka YouBot.
-
- Free space shape primitive skeleton.
-
- Obstacle space shape primitive skeleton.
-
- Nuclear power plant environment with quadrotor robot.
-
- Free space skeleton.
-
- Free space shape primitive skeleton.
-
- Obstacle space skeleton.
-
- Obstacle space shape primitive skeleton.
-
- Air duct environment with linkage robot.
-
- Free space skeleton.
-
- Free space shape primitive skeleton.
-
- Obstacle space skeleton.
-
- Obstacle space shape primitive skeleton.
-
- Lungs bronchi with linkage robot.
-
- Free space skeleton.
-
- Free space shape primitive skeleton.
-
- Obstacle space skeleton.
-
- Obstacle space shape primitive skeleton.
-
- Room environment with Kuka YouBot.
-
- Free space skeleton.
-
- Free space shape primitive skeleton.
-
- Obstacle space skeleton.
-
- Obstacle space shape primitive skeleton.