Fast Jump Point Search Based Path Planning for Mobile Robots

EasyChair Preprint 5136

Abstract

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.Abstract: 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.

Keyphrases: Jump Point Search, Prune rules, grid map, heuristic function, path planning

@booklet{EasyChair:5136,
  author    = {Yucong Tong and Huaiyu Wu and Xiujuan Zheng and Zhihuan Chen and Yang Chen},
  title     = {Fast Jump Point Search Based Path Planning for Mobile Robots},
  howpublished = {EasyChair Preprint 5136},
  year      = {EasyChair, 2021}}