Single-boundary rectangle expansion A* algorithm

Chong Li, An Zhang, Wenhao Bi

科研成果: 期刊稿件文章同行评审

5 引用 (Scopus)

摘要

A new single-boundary rectangle expansion A* (RE A*) algorithm is presented. The new algorithm adopts the forced expansion rule, and the two redundant adjacent boundaries between adjacent rectangles are replaced with a shared boundary during the process of exploring map in rectangular units, which will improve the efficiency, simplify the termination conditions and optimize the quality of the result paths. Without any offline pre-processing, the new algorithm can speed up a highly optimized A* algorithm by an order of magnitude and more. The algorithm guarantees the grid-optimal path point sequence, while the final result path (which consists of the straight lines between path points) is always shorter than grid-optimal path. Experimental results on typical benchmark problem sets show that compared with the existing RE A* algorithms, the ability to deal with complex maps and the upper limit of the algorithm efficiency are improved by the proposed algorithm. The shorter result paths and less turning points are achieved with the proposed algorithm, so the quality of result paths are better. The average speed of the proposed algorithm is also better than that of RE A*, except in the low complex and low open maps.

源语言英语
页(从-至)46-56
页数11
期刊Jiqiren/Robot
39
1
DOI
出版状态已出版 - 1 1月 2017

指纹

探究 'Single-boundary rectangle expansion A* algorithm' 的科研主题。它们共同构成独一无二的指纹。

引用此