Abstract Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we will study a number of different quality criteria on paths in particular length and clearance. We will describe a number of techniques to improve the quality of paths. These are based on a new approach to increase the path clearance. Experiments showed that the heuristics were able to generate paths of a much higher quality than previous approaches. Reference Roland Geraerts and Mark Overmars. Clearance Based Path Optimization for Motion Planning. In IEEE International Conference on Robotics and Automation (ICRA'04), 2004, pp. 2386-2392. Full text: [pdf] Presentation: [ppt]     Query path Retracted path No redundant branches The sequel of this work can be found here. We present an algorithm that improves the clearance along paths of a broader range of robots which may reside in arbitrary high-dimensional configuration spaces.