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

Authors

  • Peter Yap University of Alberta
  • Neil Burch University of Alberta
  • Robert Holte University of Alberta
  • Jonathan Schaeffer University of Alberta

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*.

Downloads

Published

2011-08-04

How to Cite

Yap, P., Burch, N., Holte, R., & Schaeffer, J. (2011). Block A*: Database-Driven Search with Applications in Any-Angle Path-Planning. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 120-125. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7813

Issue

Section

Constraints, Satisfiability, and Search