The issue of motion planning for closed-loop mechanisms, such as parallel manipulators or robots, is still an open question. This paper proposes a novel approach for motion planning of spatial parallel robots. The framework for the geometric modeling is based on the visibility graph methodology. It is opted for a multiple-heuristics approach, where different influences are integrated in a multiplicative way within the heuristic cost function. Since the issue of singularities is a fundamental one for parallel robots, it is emphasized on the avoidance of such configurations. To include singularity-free planning within the heuristic approach, two heuristic functions are proposed, the inverse local dexterity as well as a novel defined "next-singularity" function, in such a way, well conditioned motions can be provided by a single planning procedure. The success of the method is illustrated by some examples. © 2008 Cambridge University Press.