Download PDFOpen PDF in browser

Fast Jump Point Search Based Path Planning for Mobile Robots

EasyChair Preprint 5136

7 pagesDate: March 12, 2021

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser