Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons

Mukulika Ghosh, Shawna Thomas, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingChapter


In many robotics applications, the environment (robots and obstacles) often have very complex geometries. These result in expensive primitive computations such as collision detection which in turn, affect the overall performance of these applications. Approximating the geometry is a common approach to optimize computation. Unlike other applications of geometric approximation where it is applied to one space (usually obstacle space), we approximate both obstacle and free workspace with a set of geometric shape primitives that are completely contained within the space and represent its topology (skeleton). We use these “shape primitive skeletons” to improve collision detection performance in motion planning algorithms. Our results show that the use of shape primitive skeletons improves the performance of standard collision detection methods in motion planning problems by 20–70% in our 2D and 3D test environments regardless of motion planning strategy. We also show how the same shape primitive skeletons can be used with robots of different sizes to improve the performance of collision detection operation.

Original languageEnglish (US)
Title of host publicationSpringer Proceedings in Advanced Robotics
Number of pages16
StatePublished - 2020
Externally publishedYes

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Mechanical Engineering
  • Engineering (miscellaneous)
  • Artificial Intelligence
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons'. Together they form a unique fingerprint.

Cite this