Avoiding Node Re-Expansions Can Break Symmetry Breaking

Mark Carlson, Daniel Harabor, Peter J. Stuckey

Introduction: The Hidden Danger of Pruning

Pathfinding efficiency in modern applications often relies on two complementary techniques: symmetry breaking (such as Jump Point Search, or JPS) to prune redundant paths, and bounded suboptimal search (such as Weighted A, or WA) to prioritize speed by inflating heuristics. For years, the community assumed these techniques were "orthogonal"—that they could be combined without issue. Specifically, to maximize speed, researchers often disable "node re-expansion" in WA*, meaning once a node is visited, it is never visited again.

However, this paper reveals a critical flaw: JPS pruning rules are designed under the assumption that the search identifies optimal path prefixes. When WA* without re-expansion finds a suboptimal path to a node first, the JPS pruning logic may incorrectly conclude that the only remaining path to the goal is redundant and prune it. This leads to completeness failures where the search fails to find any path at all, even when one exists.

Figure 4: A grid example demonstrating how suboptimal path prefixes can lead to incorrect JPS pruning, potentially causing the search to fail.

Methodology: Focal List Search (FLS)

To resolve this conflict, the authors introduce Focal List Search (FLS). FLS is designed to maintain the speed of suboptimal search while ensuring the algorithm remains complete and robust against incorrect pruning.

FLS employs a dual-queue system:

  • OPEN List: Ordered by the standard $f = g + h$ to track the lower bound of the path cost.
  • FOCAL List: Ordered by the weighted $f_w = g + w \cdot h$ to guide the greedy search.

Crucially, FLS implements controlled re-expansion. Unlike standard WA*, which either re-expands everything or nothing, FLS allows a node to be expanded at most twice: once suboptimally from the FOCAL list and once optimally from the OPEN list. This approach guarantees completeness and stays within the suboptimality bound $w$ without the risk of exponential "node explosion" associated with unrestricted re-expansions.

Experimental Results

The authors conducted an extensive evaluation using over two million problem instances from the Moving AI and Iron Harvest benchmarks. The results confirmed that standard JPS variants (BJPS, CJPS, and JPSW) frequently failed when combined with WA* without re-expansions, particularly as the weight $w$ increased. In contrast, FLS successfully found paths in 100% of the tested cases.

Figure 5: Performance comparison on uniform cost maps showing that FLS (brown) maintains similar speedups to WA* (red) relative to optimal search, while providing a 100% success guarantee.

While FLS introduces a minor constant-factor overhead (approximately 10-25%) due to dual-queue management, it proves more robust on difficult map instances. It effectively avoids the "catastrophic explosions" in search time that can occur with full re-expansion while fixing the reliability issues of no-re-expansion WA*.

Conclusion and Future Work

This research highlights that the interaction between pruning and suboptimality is a "double-edged sword." While failures occur in less than 0.1% of cases, such a rate is unacceptable for high-stakes applications like robotics or AAA gaming. FLS offers a robust middle ground. Future work will investigate why "canonical" JPS appears resistant to these failures and explore how these findings generalize to non-grid domains like road networks or automated planning.

Summary updated

BibTeX
@inproceedings{carlson2024avoiding,
  author = {Mark Carlson and Daniel Harabor and Peter J. Stuckey},
  title = {{Avoiding Node Re-Expansions Can Break Symmetry Breaking}},
  booktitle = {SOCS},
  year = {2024},
  doi = {10.1609/socs.v17i1.31538},
}
Figure