Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7154353 | Chinese Journal of Aeronautics | 2016 | 12 Pages |
Abstract
Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion Aâ (REAâ), is presented that improves the performance of Aâ significantly. REAâ explores maps in units of unblocked rectangles. All unnecessary points inside the rectangles are pruned and boundaries of the rectangles (instead of individual points within those boundaries) are used as search nodes. This makes the algorithm plot fewer points and have a much shorter open list than Aâ. REAâ returns jump and grid-optimal path points, but since the line of sight between jump points is protected by the unblocked rectangles, the resulting path of REAâ is usually better than grid-optimal. The algorithm is entirely online and requires no offline pre-processing. Experimental results for typical benchmark problem sets show that REAâ can speed up a highly optimized Aâ by an order of magnitude and more while preserving completeness and optimality. This new algorithm is competitive with other highly successful variants of Aâ.
Keywords
Related Topics
Physical Sciences and Engineering
Engineering
Aerospace Engineering
Authors
Zhang An, Li Chong, Bi Wenhao,