Author name cluster

Mark Carlson

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

2 author rows

SoCS Conference 2024 Conference Paper

Avoiding Node Re-Expansions Can Break Symmetry Breaking

Mark Carlson
Daniel Harabor
Peter J. Stuckey

Symmetry breaking and weighted-suboptimal search are two popular speed up techniques used in pathfinding search. It is a commonly held assumption that they are orthogonal and easily combined. In this paper we illustrate that this is not necessarily the case when combining a number of symmetry breaking methods, based on Jump Point Search, with Weighted A*, a bounded suboptimal search approach which does not require node re-expansions. Surprisingly, the combination of these two methods can cause search to fail, finding no path to a target node when clearly such paths exist. We demonstrate this phenomena and show how we can modify the combination to always succeed with low overhead.

Details

AAAI Conference 2023 Conference Paper

Optimal Pathfinding on Weighted Grid Maps

Mark Carlson
Sajjad K. Moghadam
Daniel D. Harabor
Peter J. Stuckey
Morteza Ebrahimi

In many computer games up to hundreds of agents navigate in real-time across a dynamically changing weighted grid map. Pathfinding in these situations is challenging because the grids are large, traversal costs are not uniform, and because each shortest path has many symmetric permutations, all of which must be considered by an optimal online search. In this work we introduce Weighted Jump Point Search (JPSW), a new type of pathfinding algorithm which breaks weighted grid symmetries by introducing a tiebreaking policy that allows us to apply effective pruning rules in symmetric regions. We show that these pruning rules preserve at least one optimal path to every grid cell and that their application can yield large performance improvements for optimal pathfinding. We give a complete theoretical description of the new algorithm, including pseudo-code. We also conduct a wide-ranging experimental evaluation, including data from real games. Results indicate JPSW is up to orders of magnitude faster than the nearest baseline, online search using A*.

PDF Details DOI