The Relationship between “C-Space”, “Heuristic Methods”, and “Sampling Based Planner”

摘要

Defining the collision-free C-space is crucial in robotics to find whether a robot can successfully perform a motion. However, the complexity of defining this space increases according to the robot’s degree of freedom and the number of obstacles. Heuristics techniques, such as Monte Carlo’s simulation, help developers address this problem and speed up the whole process. Many well-known motion planning algorithms, such as RRT, base their popularity on their ability to find sufficiently good representations of the collision-free C-space very quickly by exploiting heuristics methods, but this mathematical relationship is not highlighted in most textbooks and publications. Each book focuses the attention of the reader on C-space at the beginning, but this concept is left behind page after page. Moreover, even though heuristics methods are widely used to boost algorithms, they are never formalized as part of the Optimization techniques subject. The major goal of this chapter is to highlight the mathematical and intuitive relationship between C-space, heuristic methods, and sampling based planner.