A Directed Jump Point Search with Improved Preprocess for Path Planning
Zongquan Xie, Lei Cheng, Xiang Li, Xiuqi Chen · 2023
We introduce a new algorithm called directed JPS+(Jump Point Search Plus) that addresses the large memory overheads of JPS+ and improves its performance in cases where the obstacle scale is small. Our approach involves two main modifications. First, we reduce memory usage by recording only jump points in the preprocessing stage instead of eight labels for each nodes in JPS+. And we introduce a technique to connect these precomputed jump points into jump point set. Second, we apply an optimization to JPS+ that speeds up path planning in maps with small obstacle scale and it has no negative impact on other cases. We implement our algorithm in Python and evaluate its performance in terms of memory usage and planning time. Our results demonstrate that it saves memory and speeds up the path planning, particularly in maps with small obstacle scale.