Anytime rectangle expansion A∗ algorithm for time-limited pathfinding

An Zhang, Chong Li, Wenhao Bi

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

4 引用 (Scopus)

摘要

Anytime algorithms are well suited for time-limited pathfinding problems, which find a feasible sub-optimal solution quickly and then continually work on improving it until time runs out. In this paper, a new anytime algorithm is introduced, called Anytime Rectangle Expansion A∗ (AREA∗), which is the anytime variant of basic Rectangle Expansion A∗ (REA∗). AREA∗ runs an accelerated sub-optimal search and then an incomplete REA∗ will repair the sub-optimality. AREA∗ can not only return the first feasible solution much faster than existing anytime algorithms but also converge to the optimal solution in almost the same speed with REA∗, which is an order of magnitude and more faster than A∗. AREA∗ also provides narrower and more accurate sub-optimality bounds of its solutions. Experimental results for typical benchmark problem sets show that, compared with the existing anytime techniques and the basic REA∗, the new algorithm shows a significant improvement in performance for time-limited pathfinding problems.

源语言英语
页(从-至)253-265
页数13
期刊International Journal of Robotics and Automation
34
3
DOI
出版状态已出版 - 11 4月 2019

指纹

探究 'Anytime rectangle expansion A∗ algorithm for time-limited pathfinding' 的科研主题。它们共同构成独一无二的指纹。

引用此