Fast Jump Point Search Based Path Planning for Mobile Robots

摘要

We propose a method to improve the performance of JPS for path planning on static grid map, including a fast neighbor pruning method and a symmetry-breaking heuristic function. First, we adopt a new and effective method to identify jump points quickly through bit operations at a single time. Second, we adopt a symmetry-breaking heuristic function to pruning redundant jump points by adding angle information and node sequence number in order to further speed up path planning search. We conducted simulation experiments on grid maps of different specifications and obstacle ratios to verify the effectiveness and feasibility of the proposed algorithm, comparing with JPS. The experimental results show that our improvement has more advantages on grid maps of different specifications and obstacle ratios, both in terms of search time and number of jump points.