Static Rectangle Expansion A*Algorithm for Pathfinding

Li Chong, Jian Li, Liu XueQuanIEEE Transactions on Games 2020 · DOI

Abstract

Incremental pathfinding algorithms can reuse previous search efforts to benefit the current search; therefore, they can work like online algorithms in dynamical environments while being sped up automatically in static environments without offline preprocessing. However, current incremental technologies must reuse the task-based information from the previous searches, so a series of tasks must be searches that are similar to each other. The rectangle expansion A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> (REA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> ) is a recently proposed online algorithm that explores maps in units of unblocked rectangles and can speed up A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> by an order of magnitude or more. In this article, a new map-based incremental search technique is proposed and applied to the basic REA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> and a new algorithm is introduced, called the static rectangle expansion A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> (SREA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> ). SREA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> learns the map online and records the visited terrains with nonoverlapping static rectangles during each task. The static rectangles are valid over the whole life of the map, so the current search will benefit from previous searches by querying the accumulated static rectangles and avoiding unnecessary reexploration. The experimental results on typical benchmark sets show that SREA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> can significantly speed up REA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> without any extra cost or risk while retaining the completeness and optimality. SREA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> performs very well on the grid-based path planning competition server; compared with current incremental technologies, SREA <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> is not only much more efficient but is also not limited by “similar search” problems.
BibTeX
@article{chong2020static,
  author = {Li Chong and Jian Li and Liu XueQuan},
  title = {{Static Rectangle Expansion A<sup>*</sup>Algorithm for Pathfinding}},
  journal = {IEEE Transactions on Games},
  year = {2020},
  doi = {10.1109/tg.2020.3012602},
}

Loading related content...

Figure