Author name cluster

Peter Yap

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 2011 Conference Paper

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

Peter Yap
Neil Burch
Robert Holte
Jonathan Schaeffer

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 gridbased any-angle search algorithm, Theta*.

PDF Details

IJCAI Conference 2003 Conference Paper

Comparison of Different Grid Abstractions for Pathfinding on Maps

Yngvi Bjornsson
Markus Enzenberger
Robert Holte
Jonathan Schaejfer
Peter Yap

Pathfinding on a map is a fundamental problem in many applications, including robotics and computer games. Typically a grid is superimposed over the map where each cell in the grid forms a unique state. A state-space-based search algorithm, such as A* or IDA*, is then used for finding the optimal (shortest) path. In this paper we analyze the search behavior of both A* and IDA* using different grid representations, providing various new insights via analytical and empirical results.

PDF