Text

Static Rectangle Expansion A* Algorithm for Pathfinding

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 * (REA * ) is a recently proposed online algorithm that explores maps in units of unblocked rectangles and can speed up A * 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 * and a new algorithm is introduced, called the static rectangle expansion A * (SREA * ). SREA * 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 * can significantly speed up REA * without any extra cost or risk while retaining the completeness and optimality. SREA * performs very well on the grid-based path planning competition server; compared with current incremental technologies, SREA * is not only much more efficient but is also not limited by “similar search” problems.

Ketersediaan

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON GAMES; Vol.14 No.1 March 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 23-35

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PATH PLANNING
HEURISTIC ALGORITHM
INCREMENTAL ALGORITHM
BREAKING PATH SYMMETRIES
PATH SEARCH
VARIANT OF A*

Info Detail Spesifik

DOI: 10.1109/TG.2020.3012602

Pernyataan Tanggungjawab

Li Chong, Li Jian, Liu XueQuan

Versi lain/terkait

Lampiran Berkas

Komentar