Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning

Peter Yap, Neil Burch, Robert C. Holte, Jonathan Schaeffer

AAAI 2011 pp. 120-125

doi:10.1609/AAAI.V25I1.7813 /aaai/2011/yap2011aaai-block/

Abstract

We present three new ideas for grid-based path-planning algorithms that improve the search speed and quality of the paths found. First, we introduce a new type of database, the Local Distance Database (LDDB), that contains distances between boundary points of a local neighborhood. Second, an LDDB based algorithm is introduced, called Block A*, that calculates the optimal path between start and goal locations given the local distances stored in the LDDB. Third, our experimental results for any-angle path planning in a wide variety of test domains, including real game maps, show that Block A* is faster than both A* and the previously best grid-based any-angle search algorithm, Theta*.

PDF AAAI Semantic Scholar

Cite

Text

Yap et al. "Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7813

Markdown

[Yap et al. "Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/yap2011aaai-block/) doi:10.1609/AAAI.V25I1.7813

BibTeX

@inproceedings{yap2011aaai-block,
  title     = {{Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning}},
  author    = {Yap, Peter and Burch, Neil and Holte, Robert C. and Schaeffer, Jonathan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {120-125},
  doi       = {10.1609/AAAI.V25I1.7813},
  url       = {https://mlanthology.org/aaai/2011/yap2011aaai-block/}
}