Heuristic methods for randomized path planning in potential fields

Randomized path planning driven by a potential field is a well established technique for solving complex, many degrees of freedom motion planning problems. In this technique a suitable potential field shapes the search of the path toward the goal. However, randomized path planning can become relatively inefficient when deep local minima are present in the potential field. Indeed, the algorithm usually spends most its running time trying to escape from local minima by means of uninformed random motions. In this paper we present simple yet effective heuristics for escaping local minima, with the goal of improving overall planning performance. We integrate these heuristics into a path planner without sacrificing the overall probabilistic completeness of the algorithm. Experimental results on several test cases show a remarkable performance improvement, up to a factor of 4 for complex problem instances.