A Deterministic Path Planning Algorithm with Greedy Heuristics for Mobile Robots

Abstract

This paper proposes a novel global path planning algorithm for mobile robots. The path extends with samples taken under a greedy heuristic strategy so that samples close to the goal are prioritized. Inspired by graph-searching algorithms, it employs a vertex evaluation scheme to navigate around the obstacles. To remove redundant paths, a rewiring mechanism is proposed to fine-tune the planned path. Numerical simulation is conducted in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{R}^{2}$</tex> with different obstacle distributions. The proposed algorithm finds better paths with less computation cost than reference sampling-based planners. Compared with the optimality-guaranteed graph-search methods, the proposed algorithm is more robust against obstacle density while ensuring a solution quality close to the global optimum.