GIGPRM: A Gradually Improving Guided Probabilistic Roadmap Strategy

Abstract

Skeleton-guided sampling-based motion planners, such as Dynamic Region PRM (DR-PRM), use a workspace skeleton to bias sampling toward topologically important regions of the environment, such as narrow passages. However, these methods assume that the skeleton is medially centered in the free space and that every skeleton vertex has sufficient clearance, meaning it is far enough from surrounding obstacles to allow valid configurations to be sampled in its vicinity. When this assumption is violated, structurally important regions may be discarded, and the planner may fail to find a feasible path. This thesis introduces Gradually Improving Guided PRM (GIGPRM), a strategy designed to remain reliable when workspace skeletons are imperfect. GIGPRM preserves low-clearance skeleton vertices and incrementally relocates expansion regions toward feasible nearby space during roadmap construction. This allows skeleton guidance to be adjusted during planning. We evaluate GIGPRM against DR-PRM in three benchmark environments under skeletons of varying quality, and show that GIGPRM achieves substantially higher path-finding rates, lower runtime, and dramatically fewer collision detection calls. Overall, GIGPRM achieves the efficiency of guided sampling without being constrained by skeleton quality.