Rectangle expansion A*pathfinding for grid maps |
| |
Institution: | 1. School of Aeronautics, Northwestern Polytechnical University, Xian 710129, China;2. School of Electronics and Information, Northwestern Polytechnical University, Xian 710129, China |
| |
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. Experi-mental 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: | Breaking path symmetries Grid Heuristic algorithms Path search Variant of A* |
本文献已被 CNKI 万方数据 等数据库收录! |
|