Avoiding Node Re-Expansions Can Break Symmetry Breaking

Authors

  • Mark Carlson Monash University
  • Daniel Harabor Monash University
  • Peter J. Stuckey Monash University

DOI:

https://doi.org/10.1609/socs.v17i1.31538

Abstract

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.

Downloads

Published

2024-06-01